تحقیق مقاله پیاده سازی و ارزیابی الگوریتم ها و سیر تکاملی و انواع زبان های برنامه نویسی

AI به دو مکتب فکری تقسیم می شود:

AI قراردادی (Coventional AI) : توسط رسمی سازی (formalism)، تحلیل آماری، تعاریف و اثبات مشخص می گردد (مثل یادگیری ماشین و سیستم های خبره).

هوش محاسباتی: با ویژگی های غیررسمی، غیراحتمالی و اغلب با رویکردهای آزمون و خطا شناخته می شود. هوش محاسباتی به سه بخش اصلی تقسیم می گردد:

شبکه های عصبی

سیستم های فازی

محاسبه تکاملی

الگوریتم های تکاملی تکنیک پیاده سازی مکانیزم هایی مانند تولید مجدد[1] ، جهش، ترکیب مجدد(ادغام)، انتخاب طبیعی (فرایندی که توسط آن افرادی دارای مشخصه های مطلوب با احتمال بیشتری برای تولید افراد بعدی به کار می روند. پس مشخصه های مطلوب در نسل بعد عمومی تر می شوند) و بقای شایسته ترین است. ولی محاسبات تکاملی دارای مشخصه های زیر می باشند:

پیشروی، رشد یا توسعه تکراری

مبنی بر جمعیت

جستجوی تصادفی هدایت شده

پردازش موازی

ملهم از زیست شناسی

محاسبات تکاملی اغلب شامل الگوریتم های بهینه سازی فرااکتشافی است مانند:

الگوریتم های تکاملی (شامل الگوریتم ژنتیک، برنامه نویسی تکاملی، استراتژی تکاملی، برنامه نویسی ژنتیک و سیستم های طبقه بندی کننده یادگیر (Learning Classifier Systems) )

هوش گروهی[2] (شامل بهینه سازی گروه مورچگان و بهینه سازی گروه ذرات[3])

و تا حد کمتری شامل:

خودسازماندهی (نقشه های خودسازمانده ، گاز عصبی در حال رشد، یادگیری رقابتی)

تکامل تفاضلی (دیفرانسیلی)

زندگی مصنوعی

الگوریتم های فرهنگ

سیستم های ایمنی مصنوعی

مدل تکاملی قابل یادگیری

هوش گروهی  (SI) یک تکنیک هوش مصنوعی مبنی بر بررسی رفتار جمعی در سیستم های غیر متمرکز و خودسازمانده است . این واژه توسط Wang  و Beni در سال 1989 و در مبحث سیستم های رباتی سلولی[4] مطرح شد.

SI  معمولا از جمعیتی از عاملهای ساده تشکیل شده که به طور محلی با یکدیگر و محیطشان تعامل دارند. با اینکه ساختار کنترلی متمرکزی برای تحمیل رفتار عاملها وجود ندارد، تعاملات محلی بین عاملها اغلب منجر به بروز یک رفتار سراسری می گردد. مثال:گروه مورچگان، ازدحام پرندگان و دسته حیوانات.

سیستم های نمونه:

ACO: یک الگوریتم بهینه سازی فرااکتشافی است که می تواند راه حلهای تقریبی را برای مسایل بهینه سازی ترکیبی مشکل بیابد. در ACO، مورچه های مصنوعی با حرکت روی گراف مساله راه حلها را می سازند و با تقلید از مورچه های حقیقی، روی گراف فرومون مصنوعی به جا می گذارند، به نحوی که مورچه های مصنوعی آینده راه حلهای بهتری بیابند. ACO می تواند با موفقیت بر روی مسایل بهینه سازی زیادی اجرا شود. ؟؟؟؟؟؟؟؟؟ مسایل مناسب در مقاله Dorigo

بهینه سازی گروه ذرات: PSO الگوریتم بهینه سازی سراسری برای بحث در مورد مسایلی است که در آنها بهترین راه حل به صورت یک نقطه یا سطح در فضای چندبعدی نشان داده می شود. فرضیه ها در این فضا رسم می شوند و با یک سرعت اولیه و کانال ارتباطی بین ذرات شروع می شوند. سپس ذرات در فضای راه حل حرکت می کنند و بعد از هر مهر زمانی، براساس معیار شایستگی، مورد ارزیابی قرار می گیرند. بعد از مدتی ذرات به طرف ذراتی که دارای مقادیر شایستگی بهتر در گروه ارتباطی خودشان هستند، سرعت می گیرند. مزیت اصلی این رویکرد نسبت به سایر استراتژی های کمینه سازی مانند آنیلینگ شبیه سازی شده این است که تعداد زیاد افرادی که گروه ذرات را تشکیل می دهند، تکنیکی بسیار ارتجاعی را برای مساله کمینه سازی محلی به کار می برند.

ذرات دارای دو قابلیت هستند : حافظه مربوط به بهترین موقعیت خود و دانش بهترین موقعیت گروه. افراد یک دسته موقعیتهای خوب را با یکدیگر مبادله می کنند و موقعیت و سرعت خود را برمبنای این موقعیتهای خوب تنظیم می سازند. این ارتباط از دو طریق صورت می گیرد:

بهترین سراسری که برای همه شناخته شده است.

بهترین های همسایه که هر ذره فقط با زیرمجموعه ای از دسته در مورد بهترین موقعیتها ارتباط دارد.

جستجوی پخشی احتمالی[5]: SDS یک جستجوی سراسری مبنی بر عامل و تکنیک بهینه سازی است که برای مسایلی که تابع هدف می تواند به چندین تابع جزئی مستقل تجزیه شود مناسب است. هر عامل یک فرضیه را نگهداری می کند که به طور مکرر با یک تابع هدف جزئی که به طور تصادفی انتخاب می شود ارزیابی می شود که پارامترهای آن با فرضیه فعلی عامل تعیین می گردد. اطلاعات فرضیه ها از طریق ارتباط بین عاملی در جمعیت پخش می گردد. برخلاف ارتباط stigmergetic  مورد استفاده در ACO، در SDS عاملها فرضیه ها را از طریق استراتژی ارتباطی یک به یک، مبادله می کنند. SDS هم الگوریتم جستجو و هم Optimisation قدرتمند و موثری است که به خوبی به بیان ریاضی توصیف می گردد.

کاربرد تکنیکهای مبنی بر هوش گروهی : کنترل خودروهای بدون سرنشین، نقشه برداری نجومی.

EP: اولین بار در 1960 توسط  Lawrence J.Fogel  برای تکامل شبیه سازی شده به عنوان یک فرایند یادگیری با هدف تولید هوش مصنوعی به کار رفت. Fogel ماشینهای حالت متناهی را به عنوان پیشگویی کننده به کار برد و آنها را تکامل داد.

امروزه EP برخلاف سایر گویشها، گویشی از محاسبه تکاملی با ساختار (نمایش) غیرثابت است و به سختی از استراتژی های تکاملی شناخته می شود.

عملگر تغییر اصلی در آن جهش است، اعضای یک جمعیت به جای اعضای یک species به عنوان بخشی از species  خاص درنظر گرفته می شوند، پس هر والد با استفاده از یک انتخاب بازمانده () یک فرزند تولید می کند.

برنامه نویسی ژنتیک(GP)

یک متدولوژی خودکار الهام گرفته شده از تکامل زیستی است برای یافتن برنامه های کامپیوتری که الگوریتمی تکاملی را برای بهینه کردن جمعیتی از برنامه های کامپیوتری برحسب چشم انداز شایستگی تعیین شده توسط توانایی برنامه برای انجام وظیفه محاسباتی داده شده به کار می رود.

در ابتدا دستورات برنامه و مقادیر داده در قالب ساختارهای درختی سازماندهی می شدند بنابراین از زبانهایی استفاده می شد که به طور طبیعی دارای چنین ساختارهایی بودند مانند Lisp، اما امروزه برنامه­های کامپیوتری در GP می توانند با زبانهای متنوعی نوشته شوند.

الگوریتم ژنتیک(Genetic Algorithm - GA) تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده می‌کند.

الگوریتمهای ژنتیک معمولاً به عنوان یک شبیه‌ساز کامپیوتر که در آن جمعیت یک نمونهٔ انتزاعی (کروموزومها) از نامزدهای راه‌حل یک مسأله بهینه‌سازی به راه حل بهتری منجر شود، پیاده‌سازی می‌شوند. به طور سنتی راه‌حلها به شکل رشته‌هایی از ۰ و ۱ بودند، اما امروزه به گونه‌های دیگری هم پیاده‌سازی شده‌اند. فرضیه با جمعیتی کاملاً تصادفی منحصر بفرد آغاز می‌شود و در نسلها ادامه می‌یابد. در هر نسل گنجایش تمام جمعیت ارزیابی می‌شود، چندین فرد منحصر در فرایندی تصادفی از نسل جاری انتخاب می‌شوند (بر اساس شایستگیها) و برای شکل دادن نسل جدید، اصلاح می‌شوند (کسر یا دوباره ترکیب می‌شوند) و در تکرار بعدی الگوریتم به نسل جاری تبدیل می‌شود.

عملگرهای یک الگوریتم ژنتیک

در هر مسئله قبل از آنکه بتوان الگوریتم ژنتیک را برای یافتن یک پاسخ به کار برد به دو عنصر نیاز است: اول روشی برای ارائه یک جواب به شکلی که الگوریتم ژنتیک بتواند روی آن عمل کند لازم است. به شکل سنتی یک جواب به صورت یک رشته از بیتها، اعداد یا نویسه ها.نمایش داده می‌شود.دوم روشی لازم است که بتواند کیفیت هر جواب پیشنهاد شده را با استفاده از توابع تناسب محاسبه نماید. مثلاً اگر مسئله هر مقدار وزن ممکن را برای یک کوله پشتی مناسب بداند بدون اینکه کوله پشتی پاره شود، (مسئله کوله پشتی را ببینید) یک روش برای ارائه پاسخ می‌تواند به شکل رشته ای از بیتهای ۰ و۱ در نظر گرفته شود, که ۱ یا ۰ بودن نشانه اضافه شدن یا نشدن وزن به کوله پشتی است.تناسب پاسخ، با تعیین وزن کل برای جواب پیشنهاد شده اندازه گیری می‌شود.

الگوریتم ژنتیک : الگوریتم ژنتیک که به‌عنوان یکی از روشهای تصادفی بهینه یابی شناخته شده, توسط جان هالند در سال ۱۹۶۷ ابداع شده‌است. بعدها این روش با تلاشهای گلدبرگ ۱۹۸۹, مکان خویش را یافته و امروزه نیز بواسطه تواناییهای خویش , جای مناسبی در میان دیگر روشها دارد. روال بهینه یابی در الگوریتم ژنتیک براساس یک روند تصادفی- هدایت شده استوار می‌باشد. این روش , بر مبنای نظریه تکامل تدریجی و ایده‌های بنیادین داروین پایه گذاری شده‌است.در این روش , ابتدا برای تعدادی ثابت که جمعیت نامیده می‌شود مجموعه‌ای از پارامترهای هدف بصورت اتفاقی تولید می‌شود , پس از اجرای برنامه شبیه ساز عددی را که معرف انحراف معیار و یا برازش آن مجموعه از اطلاعات است را به آن عضو از جمعیت مذکور نسبت می‌دهیم. این عمل را برای تک تک اعضای ایجاد شده تکرار می‌کنیم , سپس با فراخوانی عملگرهای الگوریتم ژنتیک از جمله لقاح , جهش و انتخاب نسل بعد را شکل می‌دهیم و این روال تا ارضای معیار همگرایی ادامه داده خواهد شد.