پیاده سازی الگوریتم ۸ وزیر با استفاده از الگوریتم ژنتیک
طراحی وب سايت
راهکاری که برای حل یک مسئله با الگوریتم ژنتیک استفاده می شود تکامل می یابد. الگوریتم ژنتیک مثل هر الگوریتم بهینه سازی دیگر با تعریف متغیرهای بهینه سازی آغاز می شود و مانند الگوریتم های بهنیه سازی دیگر نیز خاتمه می یابد یعنی با تست همگرایی.
یک الگوریتم GA دارای پارامترهای زیر است:
: Fitnessتابعی برای ارزیابی یک فرضیه که مقداری عددی به هر فرضیه نسبت میدهد
: Fitness_threshold مقدار آستانه که شرط پایان را معین میکند
: population تعداد فرضیه هائی که باید در جمعیت در نظر گرفته شوند
: crossover rate در صدی از جمعیت که در هر مرحله توسط الگوریتم crossover جایگزین میشوند
:mutation rate نرخ mutation
الگوریتم GA به صورت زیر کار می کند:
: Initializeجمعیت را با تعداد population فرضیه بطور تصادفی مقدار دهی اولیه کنید.
: Evaluateبرای هر فرضیه h در population مقدار تابع Fitness(h) را محاسبه نمائید.
تا زمانیکه[maxh Fitness(h)] < Fitness_threshold یک جمعیت جدید ایجاد کنید.
فرضیه ای که دارای بیشترین مقدار Fitness است را برگردانید.
روش های مختلف crossover:
Single-point crossover
یک نقطه تصادفی در طول رشته انتخاب میشود.
والدین در این نقطه به دوقسمت میشوند.
هر فرزند با انتخاب تکه اول از یکی از والدین و تکه دوم از والد دیگر بوجود میاید.
روشهای دیگر Crossover
در crossover یکنواخت بیتها بصورت یکنواخت از والدین انتخاب می شوند.
اپراتورهای ژنتیکی Mutation :
اپراتور mutation برای بوجود آوردن فرزند فقط از یک والد استفاده میکند. اینکار با انجام تغییرات کوچکی در رشته اولیه بوقوع میپیوندد.
با استفاده از یک توزیع یکنواخت یک بیت بصورت تصادفی اتنخاب و مقدار آن تغییر پیدا میکند.
معمولا mutation بعد از انجام crossover اعمال میشود.
تابع fitness معیاری برای رتبه بندی فرضیه هاست که کمک میکند تا فرضیه های برتر برای نسل بعدی جمعیت انتخاب شوند. نحوه انتخاب این تابع بسته به کاربر مورد نظر دارد
در روش معرفی شده در الگوریتم ساده GA احتمال انتخاب یک فرضیه برای استفاده در جمعیت بعدی بستگی به نسبت fitness آن به fitness بقیه اعضا دارد. این روش Roulette Wheel selectionنامیده میشود.
روش جستجوی GA با روشهای دیگر مثل شبکه های عصبی تفاوت دارد:
در شبکه عصبی روش Gradient descent بصورت هموار از فرضیه ای به فرضیه مشابه دیگری حرکت میکند در حالیکه GA ممکن است بصورت ناگهانی فرضیه والد را با فرزندی جایگزین نماید که تفاوت اساسی با والد آن داشته باشد.از اینرو احتمال گیر افتادن GA در مینیمم محلی کاهش می یابد. با این وجود GA با مشکل دیگری روبروست که crowding نامیده میشود crowding پدیده ای است که در آن عضوی که سازگاری بسیاربیشتری از بقیه افراد جمعیت دارد بطور مرتب تولید نسل کرده و با تولید اعضای مشابه درصد عمده ای از جمعیت را اشغال میکند. راه حل رفع مشکل Crowdingاستفاده از ranking برای انتخاب نمونه ها است، با اختصاص رتبه به فرضیه ای که بسیار بهتر از بقیه عمل میکند.
مسئله ۸ وزیر:
بدین ترتیب دیدیم که مسیر میان اجزای الگوریتم ژنتیک به ترتیب زیر است:
تعریف توابع و متغیرها
تولید جمعیت اولیه
دیکد کردن کروموزوم ها
پیدا کردن هزینه برای هر کروموزوم
انتخاب جفت ها
جفت گیری
میوتیشن
بررسی همگرایی
خاتمه یا بازگشت به مرحله دیکد کردن کروموزوم ها
ژن عددی از ۰ تا n-1 است در ۸ وزیر n برابر با ۸ است بنابراین ژن عددی از ۰ تا ۷ می شود و کروموزوم آرایه ای از ژن هاست. که می تواند پاسخ مسئله باشد.
جمعیت هر نسل می تواند تعداد کروموزوم ها را تعیین کند.
جمعیت اولیه از انتخاب رندومی از کروموزوم ها ایجاد می شود. تعداد نسل هایی که برای همگرایی مورد نیاز است به جمعیت تصادفی اولیه بستگی دارد.
برای پیدا کردن هزینه مربوط به هر کروموزوم یک تابع هزینه تعریف می شود. نتیجه تابع هزینه یک cost value است که در نهایت میانگین cost valueهای هر نسل به نتیجه مطلوب نزدیک می شود.
کروموزوم هایی که فیتنس بالاتری (هزینه پایین تر) دارند برای تولید نسل بعدی استفاده می شوند.
در فرایند cross over فرزندان توسط والدین تولید می شوند که ترکیب آنها شامل ترکیب ژن های آنهاست. اگر نسل جدید حاوی کروموزومی باشد که نزدیک یا برابر با نتایج مطلوب باشد آنگاه مسئله حل شده است. در غیر اینصورت فرایند قبلی در نسل جدید هم پیاده سازی می شود مانند فرایندی که برای والدین آنها اتفاق افتاد. تا زمانی که به راه حل مناسب برسیم این روال ادامه دارد.
در شطرنج وزیر می تواند هر طور که مایل بود حرکت کند افقی عمودی یا در قطر. صفحه شطرنج ۸ در ۸ است یعنی ۸ سطر و ۸ ستون دارد . در مسئله ۸ وریز استاندارد به دنبال این هستیم که چگونه ۸ وزیر در خانه های جدول به گونه ای قرار بگیرند که هیچ یک دیگری را تهدید نکنند. در اینجا با الگوریتم ژنتیک این کار را انجام می دهیم.
برای تولید فرزندان از والیدن نیاز به crossover داریم که تصمیم می گیرد از دو والدین کدام ژن باید انتخاب شود.
فانکش استفاده از میوتیشن برای نسل فعلی:
ابتدا یک کروموزوم رندوم انتخاب می شود (کروموزومی به غیر از بهترین کروموزومی که در صدر لیست قرار دارد). سپس دو ژن رندوم از این کروموزوم انتخاب می شود و با هم جابجا می شود. افزایش تعداد میوتیشن ها آزادی الگوریتم را در جستجو خارج از فضای حالات کروموزوم ها بیشتر می کند.
همان طور که گفته شد ژن عددی از ۰ تا ۷ است که به معنی شماره سطری است که وزیر در آن قرار گرفته است. موقعیت ژن در یک کروموزوم به معنی شماره ستون قرار گیری وزیر است. مشخص کردن مکان قرار گیری هر وزیر را باید حتما در هر سطر و ستون مشخص کرد.
کروموزوم نیز مجموعه ای از ۸ ژن است. و این طور فرض می شود که هیچ ژنی در یک کروموزوم دوبار تکرار نشود. برای مثال اگر کروموزوم ما ۰|۱|۴|۲|۳|۶|۷|۵ باشد یعنی ۸ وزیر در خانه های زیر از ماتریس قرار گرفته اند.
(۰,۰), (۱,۱), (۲,۴), (۳,۲), (۴,۳), (۵,۶), (۶,۷), (۷,۵)
در اینجا میوتیشن با swap کردن ژنی که باید mutate شود با یک ژن تصادفی (به جز ژنی که می خواهیم میوتیشن را روی آن انجام دهیم) از همان کروموزوم انجام می شود.
در crossover ژن ها از کروموزوم های دو والدین با احتمال ۰٫۵ گرفته می شود. یک ژن از یکی از والدین گرفت می شود و به کروموزوم فرزند اضافه می شود. ژنی که تولید می شود در پرنت دیگر پاک می شود. این مرحله انقدر ادامه می یابد تا کروموزوم های پدر و مادر هر دو، خالی شود و فرزند آنها همه ژن ها را داشته باشد.
تابع فیتنس: زمانی که دو وزیر طوری قرار بگیرند که یکدیگر را تهدید کنند یعنی در یک سطر، ستون یا قطر مشابه باشند. از آنجایی که کروموزوم ها ژن های تکراری ندارند بنابراین این اطمینان وجود دارد که هیچ دو وزیری در یک ستون قرار نمی گیرند. پس تنها باید برخوردهای قطری را بررسی و محاسبه کرد. بنابراین ماکزیمم تعداد برخوردها می تواند ۲۸ باشد. تابع فیتنس مقدارش هر چه بیشتر باشد بهتر است بنابراین اگر یک راه حل ۰ برخورد (تهدید دو وزیر) داشته باشد فیتنس آن ۲۸ است که با تفریق مقدار برخوردهایی که در حالت فعلی رخ می دهند از ۲۸ به دست می آید.
در کد c# مورد استفاده :
class GeneticAlgo: کلاسی است که مسئولیت همه عملیات الگوریتم ژنتیک را بر عهده دارد.
class FitnessComparator: یک کلاس مقایسه کننده است که کروموزوم ها را با fitness value مرتب می کند تا جمعیت نهایی را در جدول نشان دهد. بیشترین فیتنس در بالای جدول قرار می گیرد و کمترین آنها در پایین جدول.
struct Chromosome: ساختاری است که کروموزومی که حاوی ژنهااست، فیتنس و مجموع میانگین فیتنس ها را نشان می دهد.
class MainFrame: این کلاس موظف به کنترل اینترفیس کاربر و ایجاد جمعیت اولیه به منظور انتقال آن به الگوریتم ژنتیک است.
class Board: این کلاس گرافیک و عملیات صفحه شطرنج را بر عهده دارد.
متغیر private const int MAX_FIT = ۲۸ بیشترین مقدار فیتنس را دارد.
توابع:
private List<chromosome> GetInitialPopulation(int population)
{
List<chromosome> initPop = new List<chromosome>();
GeneticAlgo RandomGen = new GeneticAlgo();
for (int i = 0; i < population; i++)
{
List<int> genes = new List<int>(new int[] {0, 1, 2, 3, 4, 5, 6, 7});
Chromosome chromosome = new Chromosome();
chromosome.genes = new int[8];
for (int j = 0; j < 8; j++)
{
int geneIndex = (int)(RandomGen.GetRandomVal
(۰,genes.Count-1)+0.5);//randomly select a gene
chromosome.genes[j] = genes[geneIndex];
genes.RemoveAt(geneIndex);//remove selected gene
}
initPop.Add(chromosome);
}
return initPop;
}