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

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

پایان نامه کارشناسی- مهندسی کامپیوتر

قالب بندی: word

تعداد صفحات: 110

قسمتی از متن:

همان طور که تاریخ الگوریتم های تکاملی نشان می دهد، گونه های زیادی از الگوریتم‌های تکاملی وجود دارند. ولی ایده همه آنها یکی است: با داشتن جمعیتی از گونه‌ها، فشار محیطی باعث انتخاب می شود (القاء بهترین) و این افزایش شایستگی جمعیت را نتیجه می دهد. با داشتن یک تابع کیفیتی که می خواهیم بیشینه شود، می توان مجموعه ای از جواب های کاندید را به طور تصادفی تولید کرد و تابع کیفیت را به عنوان معیاری برای محاسبه شایستگی به کار برد – (هر چه بیشتر، بهتر) بر اساس این شایستگی ، بعضی از کاندیدهای بهتر انتخاب می شوند، تا به عنوان هسته ای برای تولید نسل بعد به کار روند. بر روی این کاندیدها ترکیب و یا جهش اعمال می شود. ترکیب بر روی دو یا بیشتر کاندید اعمال می شود (والدین) و نتیجه آن تولید فرزند (فرزندانی) است.

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

در این عمل دو نیروی اصلی وجود دارد که پایه سیستم تکاملی است:

- عملگرهای تغییر (ترکیب و جهش) که باعث ایجاد گوناگونی لازم و در نتیجه نوآوری می شود.

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

فهرست مطالب:

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

1-1- مقدمه

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

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

1-3-1: استراتژی های تکاملی

1-3-2: برنامه ریزی تکاملی

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

2-1: ژنتیک در طبیعت

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

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

3-1: علت معرفی SEA

3-2: عملگر ترکیب سیمبیوتیک

3-3: ایده کلی SEA

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

4-1: agent

4-2: تابع محاسبه شایستگی

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

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

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

5-3: نتایج حاصل از پیاده سازی

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

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

6-2: پیاده سازی الگوریتم SEA

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

مراجع

پیوست

 فهرست اشکال

شکل1-1.طرح کلی الگوریتم تکاملی------------------------------------------------11

شکل1-2: شبه کد استراتژی تکاملی-------------------------------------------------15

شکل1-3: شبه کد برنامه ریزی تکاملی-----------------------------------------------16

شکل2-1: شبه کد الگوریتم ژنتیکی-------------------------------------------------19

شکل3-1: نمونه ای از ترکیب Symbiotic------------------------------------------21

شکل3-2: نمونه ای از الگوریتم جستجو symbiotic-----------------------------------23

شکل3-3: شبه کد الگوریتمSEA--------------------------------------------------24

شکل4-1: نقطه آغاز یک بازی Pac-Man-------------------------------------------26

شکل4-2:نقشه زمین بازی Pac-Man به همراه تمام حالات گردش-----------------------28

شکل4-3:شبه کد استراتژیagent برای بازی Pac-Man------------------------------31

شکل 5-1: مقایسه کارایی در الگوریتم GA وSEA برای بازی pac-man.اندازه جمعیت درGA برابر 150 می باشد--------------------------------------------------------------40

شکل 5-2: مقایسه کارایی در الگوریتم GA وSEA برای بازی pac-man.اندازه جمعیت درGA برابر 200 می باشد--------------------------------------------------------------41

شکل 5-3: مقایسه هزینه در دو الگوریتم GA وSEA برای نمودار 5-1.-------------------41

شکل 5-4: مقایسه هزینه در دو الگوریتم GA وSEA برای نمودار 5-2.-------------------42

 فهرست جدولها

جدول4-1: تعیین وضعیت روح با توجه به موقعیت Pac-Man و روح نسبت به هم. ----------30

جدول4-2: شرح پارامتر­های استفاده شده برای تعیین حرکت agent----------------------32

جدول5-1: پارامترهای مطرح شده در SEA------------------------------------------38

جدول5-2: بهترین مقادیر برای هر پارامتر SEA--------------------------------------39