مسئله چند وزیر قسمت 3
فانکش استفاده از میوتیشن برای نسل فعلی:
ابتدا یک کروموزوم رندوم انتخاب می شود (کروموزومی به غیر از بهترین کروموزومی که در صدر لیست قرار دارد). سپس دو ژن رندوم از این کروموزوم انتخاب می شود و با هم جابجا می شود. افزایش تعداد میوتیشن ها آزادی الگوریتم را در جستجو خارج از فضای حالات کروموزوم ها بیشتر می کند.
همان طور که گفته شد ژن عددی از ۰ تا ۷ است که به معنی شماره سطری است که وزیر در آن قرار گرفته است. موقعیت ژن در یک کروموزوم به معنی شماره ستون قرار گیری وزیر است. مشخص کردن مکان قرار گیری هر وزیر را باید حتما در هر سطر و ستون مشخص کرد.
کروموزوم نیز مجموعه ای از ۸ ژن است. و این طور فرض می شود که هیچ ژنی در یک کروموزوم دوبار تکرار نشود. برای مثال اگر کروموزوم ما ۰|۱|۴|۲|۳|۶|۷|۵ باشد یعنی ۸ وزیر در خانه های زیر از ماتریس قرار گرفته اند.
(۰,۰), (۱,۱), (۲,۴), (۳,۲), (۴,۳), (۵,۶), (۶,۷), (۷,۵)
در اینجا میوتیشن با 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;
}
تابع فوق اندازه جمعیت را به صورت پارامتر می گیرد و لیستی از کروموزوم هایی که دربردارنده ژن های تولید شده تصادفی هستند را بر می گرداند. مقدار ژن ها بصورت تصادفی از لیستی که شامل اعداد ۰ تا ۷ است انتخاب می شود. در حین اینکه مقادیر از لیست انتخاب می شوند، مقادیر انتخاب شده پاک می شوند تا از تکراری شدن ژن ها در کروموزوم جلوگیری شود. اندازه لیست مساوی با اندازه جمعیت است. پس از ایجاد جمعیت اولیه با استفاده از این تابع، لیست کروموزوم هایی که برمیگرداند به تابع DoMating داده می شود.
public void DoMating(ref List<Chromosome> initPopulation,
int generations, double probCrossver, double probMutation)
{
int totalFitness = 0;
CalcFitness(ref initPopulation, ref totalFitness);
for (int generation = 0; generation < generations; generation++)
{
PrepareRuletteWheel(ref initPopulation,totalFitness);
Crossover(ref initPopulation, probCrossver);
Mutate(ref initPopulation, probMutation);
CalcFitness(ref initPopulation, ref totalFitness);
if (initPopulation[initPopulation.Count – 1].fitness == 28)
break;
if (progress != null)
{
progress(generation + 1);
}
}
initPopulation.Sort(new FitnessComparator());
}
این تابع لیست کروموزوم ها را به عنوان جمعیت اولیه ، تعداد نسل هایی که می خواهیم در الگوریتم پخش شوند، احتمال crossover و احتمال mutation را به عنوان پارامتر می گیرد. مسئولیت این تابع هندل کردن پخش جمعیت به نسل مورد نیاز با فراخوانی توابع CalcFitness،PrepareRuletteWheel،CrossoverوMutate است.
public void CalcFitness(ref List<Chromosome> chromosome, ref int totalFitness)
{
int collisions = 0;
totalFitness = 0;
for (int k = 0; k < chromosome.Count; k++)
{
for (int i = 0; i < chromosome[k].genes.Length – 1; i++)
{
int x = i;
int y = chromosome[k].genes[i];
for (int j = i + 1; j < chromosome[k].genes.Length; j++)
{
if (Math.Abs(j – x) == Math.Abs
(chromosome[k].genes[j] – y))
collisions++;
}
}
Chromosome temp = chromosome[k];
temp.fitness = MAX_FIT – collisions;
chromosome[k] = temp;
totalFitness += chromosome[k].fitness;
collisions = 0;
}
}
این تابع فیتنس هر کروموزوم را اندازه می گیرد و fitness value را به مشخصه fitness هر کروموزوم تخصیص می دهد. فیتنس با محاسبه تعداد برخوردها و کم کردن آن از ماکزیمم تعداد برخورد ها محاسبه می کند. در این کد فیتنس تابعی است که هرچه مقدارش بیشتر باشد بهتر است. علاوه بر محاسبه فیتنس هر کروموزوم، این تابع می تواند فیتنس کلی جمعیت را نیز محاسبه کند زیرا در مرحله بعدی برای محسابه نرخ فیتنس هر کروموزوم به آن نیاز داریم.
private void PrepareRuletteWheel(ref List<Chromosome> parents,int total)
{
int currentTotalFitness=0;
for (int i = 0; i < parents.Count; i++)
{
currentTotalFitness += parents[i].fitness;
Chromosome temp = parents[i];
temp.cumAvgFitness = currentTotalFitness / (double)total;
parents[i] = temp;
}
}
rulette wheel که بر مبنای فیتنس کروموزوم است برای انتخاب والدین برای جفت گیری برای ایجاد نسل جدید استفاده می شود. این تابع مسئول آماده سازی rulette wheel بوده و لیستی از کروموزوم ها را به عنوان جمعیت فعلی و فیتنس کلی جمعیت می گیرد. این تابع نرخ فیتنس هر کروموزوم تا فیتنس کلی را محاسبه می کند سپس مجموع آن را برای اختصاص به مشخصه cumAvgFitness کروموزوم محاسبه می کند.
با تابع RuletteWheel می توان احتمال انتخاب را بر اساس نرخ فیتنس تعیین کرد. با این روش کروموزم هایی با fitness value بالاتر احتمال بیشتری برای انتخاب در ساخت نسل بعدی دارند در حالی که کروموزم هایی با fitness value پایین تر با احتمال کمتری شرکت داده می شوند
public void Crossover(ref List<Chromosome> parents, double probability)
{
List<Chromosome> offspring = new List<Chromosome>();
for (int i = 0; i < parents.Count; i++)
{
if (Assay(probability)) //if the chance is to crossover
{
Chromosome parentX = AssayRuletteWheel(parents);
Chromosome parentY = AssayRuletteWheel(parents);
List<int> child = new List<int>();
for (int j = 0; j < 8; j++)
{
if (Assay(0.5)) //select from parentX
{
for (int k = 0; k < parentX.genes.Length; k++)
{
if (!child.Contains
(parentX.genes[k]))//instead of
//deleting the similar genes
//from parents select the
//next non-contained number
{
child.Add(parentX.genes[k]);
break;
}
}
}
else //select from parentY
{
for (int k = 0; k < parentY.genes.Length; k++)
{
if (!child.Contains
(parentY.genes[k]))//instead of
//deleting the similar genes from
//parents select the next
//non-contained number
{
child.Add(parentY.genes[k]);
break;
}
}
}
}
Chromosome offSpr = new Chromosome();
offSpr.genes = child.ToArray();
offspring.Add(offSpr);
}
else //else the chance is to clone
{
Chromosome parentX = AssayRuletteWheel(parents);
offspring.Add(parentX);
}
}
while (offspring.Count > parents.Count)
{
offspring.RemoveAt((int)GetRandomVal(0, offspring.Count – 1));
}
parents = offspring;
}
تابع فوق مسئول انجام عمل cross over است. تابع لیستی از کروموزم ها را به عنوان جمعیت فعلی و احتمال crossover را به عنوان پارامتر می گیرد. تابع Assay(int probability) با احتمال داده شده true بر می گرداند بنابراین با احتمال crossover برای تعیین اینکه عملیات crossover است یا cloning استفاده می شود.
if (Assay(probability)) //if the chance is to crossover
{
Chromosome parentX = AssayRuletteWheel(parents);
Chromosome parentY = AssayRuletteWheel(parents);
List<int> child = new List<int>();
for (int j = 0; j < 8; j++)
{
if (Assay(0.5)) //select from parentX
{
for (int k = 0; k < parentX.genes.Length; k++)
{
if (!child.Contains(parentX.genes[k]))//instead of
//deleting the similar genes from parents
//select the next non-contained number
{
child.Add(parentX.genes[k]);
break;
}
}
}
else //select from parentY
{
for (int k = 0; k < parentY.genes.Length; k++)
{
if (!child.Contains(parentY.genes[k]))//instead of
//deleting the similar genes from parents
//select the next non-contained number
{
child.Add(parentY.genes[k]);
break;
}
}
}
}
Chromosome offSpr = new Chromosome();
offSpr.genes = child.ToArray();
offspring.Add(offSpr);
}
این بخش از کد مسئول crossover دو پرنت parentX و parentY می باشد. به منظور ایجاد فرزند، ژنها از دو والدین با احتمال ۰٫۵ انتخاب می شوند در حالیکه از تکرار ژنها در کروموزوم ها اجتناب می شود. در عملیات cloning یکی از والدین مستقیما به نسل بعدی آورده می شود.
public void Mutate(ref List&lt;Chromosome&gt; parents, double probability)
{
List&lt;Chromosome&gt; offsprings = new List&lt;Chromosome&gt;();
for (int i = 0; i &lt; parents.Count; i++)
{
Chromosome offspring = parents[i];
for (int mutatePosition = 0; mutatePosition &lt; 8; mutatePosition++)
{
if (Assay(probability)) //if the chance is to mutate
{
int newGeneIndex = (int)(GetRandomVal(0,6)+0.5);
if (newGeneIndex&gt;=mutatePosition)
{
newGeneIndex += 1;
}
int swapTemp = offspring.genes[mutatePosition];
offspring.genes[mutatePosition] =
offspring.genes[newGeneIndex];
offspring.genes[newGeneIndex] = swapTemp;
}
}
offsprings.Add(offspring);
}
parents = offsprings;
}
این تابع اپراتور mutation را با احتمال داده شده استفاده می کند. این تابع تغییر میوتیش را در حین انتقال ژن ها در جمعیت فعلی بررسی می کند. اگر باید برای ژنی از میوتیشن استفاده شود آنگاه مقدار آن با یک ژنی که بصورت تصادفی انتخاب شده در همین کروموزوم (ژنی به جز خود ژنی که می خواهیم روی آن میوتیشن انجام دهیم) swap می شود.
زمانی که به یک راه حل می رسیم آرایه ژن های کروموزومی که شامل راه حل هستند را میتوان به پراپرتی به نام Genes در کلاس Board اختصاص داد.
این برنامه این امکان را می دهد که اندازه جمعیت، تعداد نسل ها، احتمال crossover و احتمال mutation را مشخص کنید.
تمام کروموزوم های نسل آخر در جدول نشان داده می شوند و بهترین نتیجه در صفحه شطرنج گرافیکی نمایش داده می شود.
هیچ محدودیتی برای تعداد نسل ها وجود ندارد تازمانی که از ماکزیمم مقداری که یک متغیر اینتیجر می تواند بگیرد بیشتر نشود. از آنجایی که این الگوریتم بر اساس فرایند احتمالاتی است نمی توان همیشه انتظار پاسخ صحیح را داشت. به عبارت دیگر از آنجایی که این روش احتمالاتی است می توان با تکرار اجرای آن به راه حل های مختلفی دست یافت.
این سوال ها سالها مطرح بوده است که بین crossover و mutation کدامیک بهتر است؟ کدامیک لازم است؟ کدامیک اصلی است؟ پاسخی که تاکنون بیشتر از بقیه پاسخها مورد قبول بوده این است که هر کدام نقش مخصوص خود را دارد. در حالت کلی بهتر است از هر دو استفاده شود. میتوان الگوریتمی داشت که فقط از mutation استفاده کند ولی الگوریتمی که فقط ازcrossover استفاده کند کار نخواهد کرد. Crossover خاصیت جستجوگرانه و یا explorative دارد. میتواند با انجام پرشهای بزرگ به محل هائی دربین والدین رفته و نواحی جدیدی را کشف نماید. Mutation خاصیت گسترشی و یا exploitive دارد. میتواند با انجام تغییرات کوچک تصادفی به نواحی کشف شده وسعت ببخشد. Crossoverاطلاعات والدین را ترکیب میکند درحالیکه mutation میتواند اطلاعات جدیدی اضافه نماید. رسیدن به یک پاسخ بهینه در mutation شانسی است.
نتایج اجرای این الگوریتم نشان می دهد که جمعیت عامل بسیاری مهمی بوده و تاثیر زیادی دارد و crossover probability و mutation rate تاثیر غیر قابل انکاری بر اجرای الگوریتم ژنتیک دارند زیرا با هر بار تغییر در هر یک از این پارامترها نتایج به شدت تغییر می کند. در حقیقت نحوه انتخاب اپراتورهای GA یک تریدآف بین همگرایی سریع تر و حفظ قابلیت اکتشافی بودن الگوریتم (برای جلوگیری از همگرایی اشتباه) است. Crossover پارامتری است که به تنظیم رفتار الگوریتم ژنتیک کمک می کند. کم کردن احتمال crossover باعث می شود در نسل بعدی افراد بیشتری بدون تغییر باقی بمانند. بسته به مسئله کاهش یا افزایش مقدار احتمال crossover می تواند تاثیر مثبت یا منفی داشته باشد.
پس از اجراهای متوالی الگوریتم می توان دید که هیچ جوابی وجود ندارد گه به طور قطع بتوان گفت از بقیه بهتر است و بتوان گفت که مقدار تنظیم شده برای پارامترهای الگوریتم ژنتیک در این حالت از همه بهتر است. این بهترین مقادیر به عوامل زیادی وابسته هستند. برای مثال اگر الگوریتم شما generational است میخواهید احتمالی را برای این در نظر بگیرید که برخی از والدین بدون تغییر باقی بمانند. در غیر اینصورت برخی راه حل های خوب را از دست خواهید داد. بنابراین بهتر است crossover rate را نزدیک به ۰٫۷ تنظیم کرد. برخی از الگوریتم ها نیز هستند که به طور کامل به mutation وابسته اند و برای آنها crossover rate مساوی با ۰ در نظر گرفته می شود. اگر crossover probability برابر با ۱۰۰درصد باشد همه فرزندان توسط crossover ایجاد می شوند. اگر ۰ درصد باشد همه نسل جدید کپی دقیقی از کروموزوم فعلی جمعیت قدیمی است ولی به این معنی نیست که نسل جدید دقیقا همان نسل قبلی است.
انتخاب اپراتورهای الگوریتم توازنی میان سرعت و دقت همگرایی است یعنی exploration در مقابل exploitation.
اینطور که گفته شده بهتر است mutation بین ۰٫۰۱۵ تا ۰٫۰۲ باشد. چرا؟
Exploration یعنی جستجوی فضای حالت در حد امکان در حالی که exploitation یعنی تمرکز بر یک نقطه که امیدواریم global optimum باشد.
در GA اپراتورهای mutation اغلب برای exploration و اپراتور های Crossover اغلب برای exploitation یعنی هدایت جمعیت به سوی همگرایی به یک راه حل خوب استفاده می شوند. در نتیجه وقتی Crossover سعی در همگرایی به یک نقطه مشخص دارد mutation سعی خود را می کند که همگرایی صورت نگیرد و فضای بیشتری کاوش شود.
در ابتدای فرایند جستجو ترجیح ما بر این است که جستجوی بیشتری به منظور اکتشاف فضا صورت گیرد. از طرف دیگر در انتهای فرایند جستجو exploitations بیشتری ترجیح داده می شود که همگرایی جمعیت به سمت global optimum تضمین شود. تنها یک استثناء وجود دارد؛ زمانی که جمعیت به سمت بهینه محلی همگرا می شود اگر بتوانیم باید پراکندگی حمیت را افزایش دهیم تا فضای بیشتری جستجو شود و در دام بهینه محلی نیفتد. با توجه به این نکته mutation rate بالا باعث افزایش احتمال جستجوی فضای بیشتری از فضای جستجو می شود با این حال از همگرایی جمعیت به یک جواب بهینه جلوگیری می کند. از طرف دیگر اگر mutation rate خیلی کوچک باشد باعث همگرایی زودهنگام و نارس می شود و به حای رسیدن به global optimum در دام بهینه محلی گرفتار می شود.مقداری که انتخاب می شود به ماهیت مسئله و نحوه پیاده سازی الگوریتم بستگی دارد. پس mutation rate های بسیار بالا از همگرایی الگوریتم جلوگیری کرده و رسیدن به راه حل بهینه را تضمین نمی کنند. بنابراین عاقلانه تر این است که از mutation rate های کوچک تر استفاده شود. مقدار کوچک برای mutation rate تضمین می کند که میوتیشن های زیادی در آن واحد اتفاق نیفتد ولی این نیز به تعداد ژن های موجود در هر کروموزوم از جمعیت بستگی دارد. بهتر این است که با مقادیر کم شروع کرده و به تدریج آنها را افزایش داد و کارایی هر یک را بررسی کرد مثلا به ترتیب: ۰٫۰۰۱، ۰٫۰۱، ۰٫۰۵، ۰٫۱، ۰٫۲ و … . در رابطه با جستجو در فضای حالت در مقایسه با mutation rate بالاتر، جمعیت بزرگتر ترجیح داده می شود.
در مقابل استفاده از mutation rate مناسب منجر به رسیدن سریع به نتایج خوب می شود و استفاده از mutation rate های بیش از حد کوچک فرایند را بسیار کند می کند زیرا کوناگونی را کم کرده و در نهایت ممکن است حتی همگرایی به درستی صورت نگیرد. mutation rate های بسیار بزرگ نیز همگرا شدن را بسیار سخت می کنند زیرا باعث می شوند جواب صحیح به راحتی از دست برود. بهترین راه تغییر تدریجی mutation rate است. مثلا به عنوان راه حل دیگر می توان با mutation rate های بزرگ شروع کرد تا گوناگونی بیشتری تزریق کرده از افتادن در دام بهینه محلی جلوگیری کرد سپس با انتها رسیدن الگوریتم یعنی تکرار آخر، این مقدار را کاهش داده و بهترین راهکار پیدا شود.
Exploitation = (crossover + انتخاب بر اساس فیتنس) ما را به جواب بهینه نهایی می رساند.
این طور گفته می شود که اندازه جمعیت کوچکتر سرعت همگرایی بیشتری به الگوریتم می دهد ولی الگوریتم راحتتر در بهینه محلی گرفتار می شود. احتیاط بر این است که از جمعیت های بیش از حد کوچک استفاده نشود. معمولا به احتمال crossover و mutation بسیار بزرگ نیاز نخواهید داشت و جمعیتی با اندازه متوسط مناسب است.
است.
مسئله چند وزیر قسمت 1
مسئله چند وزیر قسمت 2
مسئله چند وزیر قسمت 3
مسئله چند وزیر قسمت 4
دیدگاه خود را ثبت کنید
تمایل دارید در گفتگوها شرکت کنید؟در گفتگو ها شرکت کنید.