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