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

چكيده

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

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

فهرست مطالب

فصل اول – الگوريتم هاي تكاملي. 10

1-1-  مقدمه. 10

1-2-علت استفاده از الگوريتم هاي تكاملي. 13

1-3-انواع الگوريتم هاي تكاملي. 13

1-3-1: استراتژي هاي تكاملي. 14

1-3-2: برنامه ريزي تكاملي. 15

فصل دوم: الگوريتم ژنتيك. 17

2-1: ژنتيك در طبيعت. 17

2-2: الگوريتم ژنتيك استاندارد:. 18

فصل سوم: الگوريتم تكاملي سيمبيوتيك (SEA). 20

3-1: علت معرفي SEA.. 20

3-2: عملگر تركيب سيمبيوتيك:. 21

3-3: ايده كلي SEA:. 22

فصل چهارم: توصيف فضاي مسئله. 26

4-1: agent 28

4-2: تابع محاسبه شايستگي. 34

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

5-1Pac-Man : با الگوريتم ژنتيكي. 36

5-2Pac-Man : با الگوريتم SEA.. 38

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

فصل ششم: مستندات كلاسهاي پياده سازي شده. 45

6-1: پياده سازي الگوريتم ژنتيكي. 45

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

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

مراجع. 69

پيوست. 71

فهرست اشكال

شكل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