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

مقدمه

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

[1] individual

[2] Survival of the fittest

[3] fitness

[4] mutation

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

#pragma once

typedef struct _Prob_vector

{

      double  p[97] ;

    double totalFitness ;

} PVector ;

typedef struct _Population

{

      PVector *pop[600] ;

      long PopSize ;

} Population ;

کلاسی که در آن اعمال اصلی الگوریتم ژنتیکی (CrossOver،جهش، جایگزینی) انجام می­شود:

#include "stdafx.h"

#include "Population.h"

using namespace std ;

CPopulation::CPopulation()

{

}

CPopulation::~CPopulation()

{

}

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

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.طرح کلی  الگوریتم تکاملی

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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