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

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

قالب بندی: 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