پایان نامه ساخت پایگاه دانش تولید رفتار با الگوریتم تکاملی سیمبایو جنسیس

چکیده

در این پژوهش، الگوریتمی به نام سیمبایوجنسیس را برای ساخت پایگاه داده تولید رفتار به کار می بریم. این الگوریتم از مجموعه الگوریتم های تکاملی است که با مجموعه ای از اعضا سروکار دارد و هدف بهینه کردن شایستگی اعضای جمعیت است. طی آزمایش های انجام شده روی این روش، این نتیجه بدست آمده است که سیمبایوجنسیس برای استفاده در مسائلی که توصیف کاملی از صورت مسئله وجود ندارد، کارایی خوبی دارد.

برای آزمایش این گونه یادگیری، از بازی Pac-Man به عنوان مسئله مورد بررسی استفاده کردیم. سعی داریم در این مسئله agent ای را آموزش دهیم که بتواند در زمین بازی، بهترین بازی خود را انجام دهد و بیشترین زمان ممکن نیز زنده بماند. برای مقایسه نتایج حاصل از آزمایش، یکی دیگر از معروف ترین الگوریتم های تکاملی، یعنی الگوریتم ژنتیکی را برای این مسئله پیاده سازی کردیم. نتایج حاصل از این پیادهسازی ها را ارایه خواهیم کرد و مقایسه ای روی آنها انجام خواهیم داد.

الگوریتم تکاملی سیمبایوجنسیس در ساخت پایگاه داده تولید رفتار

فهرست مطالب

فصل اول الگوریتم های تکاملی

مقدمه

علت استفاده از الگوریتم های تکاملی

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

استراتژی های تکاملی

برنامه ریزی تکاملی

فصل دوم: الگوریتم ژنتیک

ژنتیک در طبیعت

الگوریتم ژنتیک استاندارد

فصل سوم: الگوریتم تکاملی سیمبیوتیک (SEA)

علت معرفی SEA

عملگر ترکیب سیمبیوتیک

ایده کلی SEA

فصل چهارم: توصیف فضای مسئله

agent

تابع محاسبه شایستگی

فصل پنجم: تعریف الگوریتم ها برای مسئله Pac-Man

Pac-Man : با الگوریتم ژنتیکی

Pac-Man : با الگوریتم SEA

نتایج حاصل از پیاده سازی

فصل ششم: مستندات کلاسهای پیاده سازی شده

پیاده سازی الگوریتم ژنتیکی

پیاده سازی الگوریتم SEA

فصل هفتم: نتیجه گیری و پیشنهادات

مراجع

پیوست

فهرست اشکال

فهرست جدولها

*****************

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

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

1. الگوریتم های ژنتیکی (GA) ارایه شده توسط Holland و مطالعه شده توسط Goldberg

2. استراتژی های تکاملی (ES) ارایه شده توسط Rechenberg و Schwefel

3. برنامه ریزی تکاملی (EP) ارائه شده توسط L.J. Fogel et. Al و اصلاح شده توسط D.B. Fogel

هر کدام سه روش بالا اثبات شده اند که با داشتن فضای مسئله پیچیده، پیوسته و چند کیفیتی به جواب تقریباً بهینه می رسند.

از دسته بندی بالا، گروه اول (الگوریتم های ژنتیکی) را به تفسیر در فصول بعدی بررسی می کنیم. در مورد دو دسته دیگر به طور اختصار توضیح می دهیم.

استراتژی های تکاملی

استراتژی های تکاملی ارایه شده توسط Rechenberg، Schwefel از لحاظ تاریخی به منظور حل مسائل بهینه سازی پارامترها تعریف شدند. در نتیجه هر گونه در جمعیت به صورت لیستی از اعداد حقیقی تعریف می شد.علاوه بر این هر گونه شامل یک سری پارامترهای استراتژی نیز بود. این پارامترها برای کنترل رفتار عملگرهای جهش استفاده می شدند.

...