مقدمه

همان طور که تاریخ الگوریتم های تکاملی نشان می دهد، گونه های زیادی از الگوریتم‌های تکاملی وجود دارند. ولی ایده همه آنها یکی است: با داشتن جمعیتی از گونه‌ها[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