END

شکل شماره ‏۳‑۶ در قالب فلوچارت الگوریتمهای تکاملی را نمایش می دهد:
شکل شماره ‏۳‑۶ : فلوچارت عمومی الگوریتم های تکاملی
اجزای اصلی الگوریتمهای تکاملی عبارتند از عضو، تابع تکامل (تابع تطبیق)، جمعیت، مکانیزم انتخاب والدین، عملگر بازترکیب و جهش، مکانیزم انتخاب بازماندگان (مکانیزم جایگزینی).
از شناخته شده ترین الگورتمیهای تکاملی می توان به الگوریتمهای زیر اشاره نمود:
الگوریتم ژنتیک[۴۹]، الگوریتم توده مورچگان[۵۰]، الگوریتم توده زنبور عسل[۵۱]، الگوریتم استراتژی تکامل[۵۲]، الگوریتم تبرید شبیه سازی شده[۵۳]، الگوریتم بهینه سازی ازدحام ذرات[۵۴]
۳-۳-۳-۱ الگوریتم ژنتیک
الگوریتم ژنتیک [۲۰] روش یادگیری بر پایه تکامل بیولوژیک است که در سال ۱۹۷۰ توسط John Holland معرفی گردید. یک الگوریتم ژنتیک برای حل یک مساله مجموعه بسیار بزرگی از راه حل های ممکن را تولید می کند. هر یک از راه حل ها با استفاده از یک تابع تناسب مورد ارزیابی قرار گرفته و تعدادی از بهترین راه حل ها در فرایندی به نام تکامل کاندید تولید راه حل های جدید می شوند. بدین ترتیب فضای جستجو در جهتی تکامل پیدا می کند که به راه حل مطلوب برسد.
الگوریتم ژنتیک در مسائلی که فضای جستجوی بزرگی داشته باشند می تواند به کار گرفته شود. همچنین در مسائلی که با فضای فرضیه پیچیده که تاثیر اجزای آن در فرضیه کلی ناشناخته باشند می توان از این الگوریتم برای جستجو استفاده نمود. بهینه سازی گسسسته از دیگر کاربردهای این الگوریتم بوده و مزیت حداقل بودن احتمال به تله افتادن در کمینه محلی در آن نسبت به سایر الگوریتم های تکاملی مناسب تر می باشد. این الگوریتم از لحاظ محاسباتی پرهزینه بوده و ضمنا تضمینی برای رسیدن به جواب بهینه ندارد.
روش متداول پیاده سازی الگوریتم ژنتیک بدین ترتیب می باشد که ابتدا مجموعه ای از حل ها (کاندیداها) که جمعیت[۵۵] نامیده می شود تولید و به طور متناوب با حل های دیگر جایگزین می شوند. در هر مرتبه، تمامی حل ها با استفاده از یک تابع تناسب[۵۶] مورد ارزیابی قرار داده می شوند. آنگاه تعدادی از بهترین حل ها با استفاده از یک تابع احتمال، انتخاب شده و جمعیت جدید را تشکیل می دهد. تعدادی از فرضیه های انتخاب شده به همان صورت مورد استفاده واقع شده و مابقی با استفاده از عملگرهای ژنتیکی نظیر ترکیب[۵۷] و جهش[۵۸] برای تولید فرزندان به کار می روند.
به صورت کلی می توان این الگوریتم را به صورت شبه کد نمایش داد:
جدول شماره ‏۳‑۳: شبه کد الگوریتم ژنتیک

برای دانلود متن کامل پایان نامه به سایت  fotka.ir  مراجعه نمایید.

// Initialise generation 0:
k := 0;
Pk := a population of n randomly-generated individuals;
// Evaluate Pk:
Compute fitness(i) for each i ∈ Pk;
do
{
// Create generation k + 1:
// ۱٫ Copy:
Select (1 − χ) × n members of Pk and insert intoPk+1;
// ۲٫ Crossover:
Select χ × n members of Pk; pair them up; produce offspring; insert the offspring intoPk+1;
// ۳٫ Mutate:
Select µ × n members of Pk+1; invert a randomly-selected bit in each;
// Evaluate Pk+1:
Compute fitness(i) for each i ∈ Pk;
// Increment:
k := k + 1;
}
while fitness of fittest individual in Pk is not high enough;
return the fittest individual from Pk;