خانه / مقالات / داده کاوی و هوش مصنوعی / پیاده سازی الگوریتم ۸ وزیر با استفاده از الگوریتم ژنتیک

پیاده سازی الگوریتم ۸ وزیر با استفاده از الگوریتم ژنتیک

پیاده سازی الگوریتم ۸ وزیر با استفاده از الگوریتم ژنتیک

 

راهکاری که برای حل یک مسئله با الگوریتم ژنتیک استفاده می شود تکامل می یابد. الگوریتم ژنتیک مثل هر الگوریتم بهینه سازی دیگر با تعریف متغیرهای بهینه سازی آغاز می شود و مانند الگوریتم های بهنیه سازی دیگر نیز خاتمه می یابد یعنی با تست همگرایی.

 

یک الگوریتم 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  برای انتخاب نمونه ها است، با اختصاص رتبه به فرضیه ای که بسیار بهتر از بقیه عمل میکند.

مسئله ۸ وزیر:

بدین ترتیب دیدیم که مسیر میان اجزای الگوریتم ژنتیک به ترتیب زیر است:

  1. تعریف توابع و متغیرها
  2. تولید جمعیت اولیه
  3. دیکد کردن کروموزوم ها
  4. پیدا کردن هزینه برای هر کروموزوم
  5. انتخاب جفت ها
  6. جفت گیری
  7. میوتیشن
  8. بررسی همگرایی
  9. خاتمه یا بازگشت به مرحله دیکد کردن کروموزوم ها

ژن عددی از ۰ تا 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;

}

 

 

تابع فوق اندازه جمعیت را به صورت پارامتر می گیرد و لیستی از کروموزوم هایی که دربردارنده ژن های تولید شده تصادفی هستند را بر می گرداند. مقدار ژن ها بصورت تصادفی از لیستی که شامل اعداد ۰ تا ۷ است انتخاب می شود. در حین اینکه مقادیر از لیست انتخاب می شوند، مقادیر انتخاب شده پاک می شوند تا از تکراری شدن ژن ها در کروموزوم جلوگیری شود. اندازه لیست مساوی با اندازه جمعیت است. پس از ایجاد جمعیت اولیه با استفاده از این تابع، لیست کروموزوم هایی که برمیگرداند به تابع 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<Chromosome> parents, double probability)

{

List<Chromosome> offsprings = new List<Chromosome>();

for (int i = 0; i < parents.Count; i++)

{

Chromosome offspring = parents[i];

for (int mutatePosition = 0; mutatePosition < 8; mutatePosition++)

{

if (Assay(probability)) //if the chance is to mutate

{

int newGeneIndex = (int)(GetRandomVal(0,6)+0.5);

if (newGeneIndex>=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 بسیار بزرگ نیاز نخواهید داشت و جمعیتی با اندازه متوسط مناسب است.

به عنوان یک قانون کلی که در مقالهOptimum population size and mutation rate for a simple real genetic algorithm that optimizes array factors  به آن اشاره شده (لینک مقاله در انتها آورده شده) اندازه جمعیت به تعداد ژن ها بستگی دارد. بنابراین ۹ ژن  به ۱۶ کروموزوم نیاز دارد و ۱۶ ژن به ۳۲ کروموزوم. معمولا با انتخاب اندازه حمعیتی معادل با ۱٫۵ تا ۲ برابر تعداد ژن ها شروع می شود تا به ماکزیمم اندازه جمعیت ۱۰۰ برسیم.

 

برای فضاهای حالت پیچیده احتمال crossover بالاتر (بیش از ۰٫۵) به جستجو در ابتدای کار کمک می کند. با این وجود در ادامه باید به مقادیری نزدیک به ۰٫۱ یا ۰٫۲ کاهش یابد. احتمال میوتیشن باید پایین نگه داشته شود (۰٫۰۱ – ۰٫۱). در غیر اینصورت همگرایی بی دلیل به تعویق می افتد.

پس برای مسائل مختلف و نحوه پیاده سازی مختلف الگوریتم ها تنظیم پارامترها متفاوت است و نمی توان به یک روال خاص در رابطه با کوچک یا بزرگ در نظر گرفتن جمعیت یا احتمالات میوتیشن و crossover اکتفا کرد. و بهترین راه تنظیم این پارامترها معمولا سعی و خطا و بازی با پارامترهاست.

ولی به عنوان یک قانون کلی:

اگر احتمال میوتیشن بسیار کوچک باشد: جمعیت بیش از حد زود همگرا می شود

اگر احتمال crossover بسیار بزرگ باشد: جمعیت هیچ گاه همگرا نمی شود

 

در ادامه الگوریتم مورد استفاده برای مسئله ۸ وزیر بارها وبارها با پارامترهای مختلف اجرا شده است تا بهترین پارامترها در نظر گرفته شود.

به این صورت عمل شده است که از آنجایی که تعداد ژن ها برابر با ۸ است ابتدا از ۱٫۵ برابر آن یعنی ۱۲ شروع شده است. یعنی مقدار جمعیت برای بار اول برابر با ۱۲ قرار داده شده است. تعداد نسل ها برابر با تعداد تکرار است. تعداد نسل را نصف تعداد جمعیت قرار می دهیم و از احتمال میویتش ۰٫۰۱ و احتمال crossover 0.5 استفاده می کنیم. لینک دانلود مرجع کد برنامه در انتها آورده شده است.

همان طور که مشاهده می شود نتیجه خوب نیست

تغییر تعداد جمعیت به دو برابر تعداد ژن ها:

هنوز به فیتنس ۲۸ یعنی تعداد برخوردهای ۰ نرسیده ایم.

در محله بعدی تکرار افزایش می یابد:

 

 

حال برای مقایسه مقدار crossover افزایش می یابد:

در این حالت هم به global maximum نرسیدیم و در دام بهینه محلی افتادیم.

مقدار crossover را مجددا کمتر کرده و مقدار میوتیشن را کمی افزایش می دهم:

نتیجه بدتر شد. مجددا به حالت قبل بر می گردانیم:

مشاهده می شود این بار نتیجه از بار قبل که با همین مقادیر اجرا شد بهتر است. چون الگوریتم ژنتیک احتمالاتی است هر بار اجرای آن نتیجه متفاوتی دارد. مثلا ژنی که برای میوتیشن انتخاب می شود تغییر می کند و کروموزوم حاصل در نسل بعدی نتیجه را تغییر می دهد.

در مرحله بعد تعداد جمعیت را به ۲۰ افزایش میدهیم:

نتیجه تغییر چندانی ندارد.

همان طور که در شکل بالا مشاهده می شود اندازه نسل نیز افزایش یافت ولی تغییر چندانی حاصل نشد.

به نظر می رسد تعداد جمعیت باید تغییر زیادی داشته باشد تا نتیجه بیشتر تغییر کند:

در این مرحله تعداد جمعیت را برابر با تعداد ژنها به توان ۲ در نظر می گیریم (در تحقیقی ثابت شده بهتر است همواره جمعیت بیشتر از دوبرابر تعداد ژنها باشد که این طور که از نتایج مشخص است این روش خوبی است).

حال می توان میتویشن و crossover را تغییر داد:

کاهش crossover در این حالت نتیجه را خراب کرد

در حالت فوق میوتیشن کمی افزایش داده شد

در حالت فوق جمعیت و تکرار را افزایش می دهیم که ابتدا به دو راه حل بهینه می رسد و البته سرعت اجرا بسیار کند می باشد ولی بعد از افزایش میوتیشن تعداد راه حل های بهینه افزایش پیدا کرده و سرعت کندتر می شود. یعنی هزینه اجرایی بالا می رود.

در تصویر فوق به علت قرار دادن یک عدد بزرگ برای میوتیشن فقط یک جواب بهینه پیدا کرد و سریع در دام بهینه های محلی افتاد.

 

 

در تصویر فوق مشاهده می شود که به علت قرار گیری عدد بزرگ در crossover به هیچ وجه همگرا نمی شود

تا کنون بهترین حالتی که مشاهده شد تصویر فوق است. که با در نظر گرفتن جمعیت نرمال ۱۰۰ ، تعداد تکرار نصف جمعیت یعنی ۵۰ و مقدار احتمال میوتیشن ۰,۰۱ و crossover برابر با ۰٫۰۷ به ۶ جواب بهینه رسیدیم. یعنی ۶ کروموزومی پیدا شدند که فیتنس ۲۸ و ماکزیمم دارند.

اجرای ۸ وزیر در متلب:

در کد زیر که با الهام از الگوریتم تپه نوردی نوشته شده پس از اجرا برای جمعیت برابر با ۱۰۰۰ و تعداد تکراری برابر با ۱۰۰ به ۲۰ جواب بهینه رسیدیم. در اینجا نیز تنظیم پارامترها دست شما است و می توان به جواب بهتری رسید

 

pop=1000;                                         %total population always

gen=100;                                           %total generations

n=8;

max_fitness=(((n-1)*n)/2);

initpop=zeros(pop,n);                            %initial population

pop_fitness=zeros(pop,1);                        %population fitness matrix

pop_fitness_sorted=zeros(pop,1);                 %for sorted fitness

fitness_temp=0;                                  %fitness temporary variable used in fitness loops between k and j

actual_pop_temp=zeros(1,n);

actual_pop_sorted=zeros(pop,n);

z=0;                                             %temporary variable used for simplicity

s=1;

w=0;

solution=zeros(1000,n);                           % solution matrix

 

cross_over_temp_mat=zeros(pop/2,n);              %cross-over variables

cross_over_ready_pop=zeros(pop,n);

cross_over_pop_final=zeros(pop,n);

 

cross_over_point=0;

 

cross_over_pop_temp_one=zeros(1,n);

cross_over_pop_temp_two=zeros(1,n);

cross_over_pop_temp_adjust=0;

 

cross_over_child_two_flipped=zeros(1,n);

cross_over_child_one=zeros(1,n);

cross_over_child_two=zeros(1,n);

 

mutation_temp_one=0;                             %mutation variables

mutation_temp_two=0;

mutation_temp_data=0;

 

for i=1:pop

initpop(i,:)=randperm(n);   %random initial population –indicates queen position on board

end;

actual_pop=initpop;                                 %duplication for working on this variable and keeping initial population intact

 

 

%generations loop

 

 

for q=1:gen

 

%for one generation

 

for i = 1:pop

fitness_temp=0;

 

%fitness calculation loop

 

for k=1:(n-1)                                               %calculates fitness by position manipulation

for j=k+1:n                                         %queen movements have been covered using j and k manipulation

z=abs(actual_pop(i,k)-actual_pop(i,j));          % for example   : when one queen is at (3,1)–(row,column)

if (ne(z,0)&& ne(z,(j-k)))                      %                next queens cant be at {(2,2),(3,2),(4,2) } {(1,3),(3,3),(5,3)}

fitness_temp=fitness_temp+1;               %                now you can observe that subtraction of each queen position and next

end                                             %                column queen position tells us a lot of information.

end                                                 %                remember the actual pop contains queen position dont confuse them with ‘i’ & ‘j’

end

pop_fitness(i,1)=fitness_temp;

end

 

%sort for individuals with good fitness

 

pop_fitness_sorted=pop_fitness;

actual_pop_sorted=actual_pop;

for i=1:(pop-1)

for j=i+1:pop

if(pop_fitness_sorted(i,1)<pop_fitness_sorted(j,1))

fitness_temp=pop_fitness_sorted(i,1);

pop_fitness_sorted(i,1)=pop_fitness_sorted(j,1);

pop_fitness_sorted(j,1)=fitness_temp;

 

actual_pop_temp(1,:)=actual_pop_sorted(i,:);

actual_pop_sorted(i,:)=actual_pop_sorted(j,:);

actual_pop_sorted(j,:)=actual_pop_temp(1,:);

end

end

end

 

 

% for unique solution gathering

%specified a vector of 100 rows ‘n’ columns

 

for i=1:pop

if(pop_fitness_sorted(i,1)==max_fitness)

for j=1:s

if actual_pop_sorted(i,:)==solution(j,:)

w=w+1;

else

w=w;

end

end

if w==0

solution(s,:)=actual_pop_sorted(i,:);

s=s+1;

else

continue;

end

end

w=0;

end

 

%selection

 

for i=1:(pop/2)

cross_over_temp_mat(i,:)=actual_pop_sorted(i,:);

end

cross_over_ready_pop=repmat(cross_over_temp_mat,2,1);

cross_over_pop_final=cross_over_ready_pop;

 

%cross over part begins

%for detail explaination cross over logic refer to the pdf attached

%logic—get random crossover point–then cross over at that point

%if two same values of rows in one individual..then adjust crossover

%according to the logic give in the pdf

while 1,

cross_over_point=floor(n*rand(1));

if cross_over_point~=0

break;

end

end

 

 

i=1;

while i<(pop-1),

 

cross_over_pop_temp_one(1,:)=cross_over_ready_pop(i,:);         %copied parents

cross_over_pop_temp_two(1,:)=cross_over_ready_pop(i+1,:);       %copied parents

%for child one

for j=1:cross_over_point

for k=j:n

if (cross_over_pop_temp_one(1,j)==cross_over_pop_temp_two(1,k))

cross_over_pop_temp_adjust=cross_over_pop_temp_two(1,j);

cross_over_pop_temp_two(1,j)=cross_over_pop_temp_two(1,k);

cross_over_pop_temp_two(1,k)=cross_over_pop_temp_adjust;

break;

end

end

end

for j=1:cross_over_point

cross_over_child_one(1,j)=cross_over_pop_temp_one(1,j);

end

for j=cross_over_point:n

cross_over_child_one(1,j)=cross_over_pop_temp_two(1,j);

end

 

 

%for child two

 

cross_over_pop_temp_two(1,:)=cross_over_ready_pop(i,:);         %copied parents

cross_over_pop_temp_one(1,:)=cross_over_ready_pop(i+1,:);       %copied parents

 

for j=1:cross_over_point

for k=j:n

if (cross_over_pop_temp_one(1,j)==cross_over_pop_temp_two(1,k))

cross_over_pop_temp_adjust=cross_over_pop_temp_two(1,j);

cross_over_pop_temp_two(1,j)=cross_over_pop_temp_two(1,k);

cross_over_pop_temp_two(1,k)=cross_over_pop_temp_adjust;

break;

end

end

end

for j=1:cross_over_point

cross_over_child_two(1,j)=cross_over_pop_temp_one(1,j);

end

for j=cross_over_point:n

cross_over_child_two(1,j)=cross_over_pop_temp_two(1,j);

end

 

cross_over_pop_final(i,:)=cross_over_child_one(1,:);

cross_over_child_two_flipped=wrev(cross_over_child_two);                 %flipped

cross_over_pop_final(i+1,:)=cross_over_child_two_flipped(1,:);

 

i=i+2;

end

 

 

%mutation introduced

%mutation occours  :at every 5th individual..swapping of two random

%                   column values(that is queen positions)

i=5;

while i<pop,

mutation_temp_one=floor(rand(1)*n/2);

mutation_temp_two=floor(2*(rand(1)*n/2));

if (mutation_temp_one==0 || mutation_temp_two==0)

continue;

else

mutation_temp_data=cross_over_pop_final(i,mutation_temp_one);

cross_over_pop_final(i,mutation_temp_one)=cross_over_pop_final(i,mutation_temp_two);

cross_over_pop_final(i,mutation_temp_two)=mutation_temp_data;

end

i=i+5;

end

i=0;

 

 

actual_pop=cross_over_pop_final;%the most important statement for my code

end

f=figure(‘Position’,[50 100 1000 600]);

cnames = {‘1′,’2′,’3′,’4′,’5′,’6′,’7′,’8′,’9′,’10’,’11’,’12’};

rnames = {‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’};

t = uitable(‘Parent’,f,’Data’,solution,’ColumnName’,cnames,…

‘RowName’,rnames,’Position’,[10 100 1000 500]);

 

 

 

با تغییر جمعیت به ۱۰۰ و تکرار به ۵۰:

به ۳ جواب بهینه رسیدیم:

 

 

با اجرای کد زیر ۹۲ کروموزوم به عنوان خروجی برگردانده می شود یعنی ۸ وزیر ۹۲ جواب دارد که ۱۲ جواب آن منحصر به‌فرد است یعنی بقیه جواب‌ها از تقارن جواب‌های اصلی به‌دست می‌آید.

 

function queen

clc;

counter = 0;

n = 8;

board = zeros(1,n);

[board,counter] = back(1, board,counter);

fprintf(‘Solution count: %d\n’,counter);

%%

function value =  isSolution(board)

 

for  i = 1:length(board)

for  j = (i+1): length(board)

if abs(board(i) – board(j)) == abs(i-j)

value = false;

return;

end

end

end

value = true;

%%

function [board,counter] =  back(depth, board,counter)

 

if  (depth == length(board)+1) && isSolution(board)

counter = counter + 1;

disp(board);

end

 

if ( depth <= length(board))

for  i = 1:length(board)

if ~any(board==i)

board(1,depth) = i;

[~,counter] = back(depth+1, board,counter);

end

end

end

 

 

بخشی از جواب ها بصورت زیر است:

۱     ۵     ۸     ۶     ۳     ۷     ۲     ۴

۱     ۶     ۸     ۳     ۷     ۴     ۲     ۵

۱     ۷     ۴     ۶     ۸     ۲     ۵     ۳

۱     ۷     ۵     ۸     ۲     ۴     ۶     ۳

۲     ۴     ۶     ۸     ۳     ۱     ۷     ۵

۲     ۷     ۵     ۸     ۱     ۴     ۶     ۳

۲     ۸     ۶     ۱     ۳     ۵     ۷     ۴

۳     ۱     ۷     ۵     ۸     ۲     ۴     ۶

۳     ۵     ۲     ۸     ۱     ۷     ۴     ۶

۳     ۵     ۲     ۸     ۶     ۴     ۷     ۱

۳     ۵     ۷     ۱     ۴     ۲     ۸     ۶

۳     ۵     ۸     ۴     ۱     ۷     ۲     ۶

۳     ۶     ۲     ۵     ۸     ۱     ۷     ۴

۳     ۶     ۲     ۷     ۱     ۴     ۸     ۵

۳     ۶     ۲     ۷     ۵     ۱     ۸     ۴

۳     ۶     ۴     ۱     ۸     ۵     ۷     ۲

۳     ۶     ۴     ۲     ۸     ۵     ۷     ۱

۳     ۶     ۸     ۱     ۴     ۷     ۵     ۲

۳     ۶     ۸     ۱     ۵     ۷     ۲     ۴

۳     ۶     ۸     ۲     ۴     ۱     ۷     ۵

۳     ۷     ۲     ۸     ۵     ۱     ۴

Solution count: 92

 

 

 

 

 

مراجع:

 

http://www.researchgate.net/post/How_to_calculate_the_Crossover_Mutation_rate_and_population_size_for_Genetic_algorithm

http://www.researchgate.net/publication/265015154_Structural_bias_in_population-based_algorithms

http://www.researchgate.net/publication/265015154_Structural_bias_in_population-based_algorithms

http://www-cs.stanford.edu/people/nuwans/docs/GA.pdf      (Genetic Algorithms: The Crossover-Mutation Debate)

http://www.researchgate.net/post/What_is_the_role_of_mutation_and_crossover_probability_in_Genetic_algorithms

http://stackoverflow.com/questions/25459096/apply-mutation-with-small-probability-to-the-offspring

http://www.codeproject.com/Articles/207144/Solve-Eight-Queens-Puzzle-with-Genetic-Algorithm-i

http://www.codeproject.com/Articles/12004/Queens-Solution-with-Genetic-Algorithm

http://stackoverflow.com/questions/10778530/what-effect-do-crossover-probabilities-have-in-genetic-algorithms-genetic-progra

http://stackoverflow.com/questions/2877895/what-is-crossover-probability-mutation-probability-in-genetic-algorithm-or-gen

http://www.researchgate.net/post/Why_is_the_mutation_rate_in_genetic_algorithms_very_small

http://www.researchgate.net/go.Deref.html?url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpl%2Flogin.jsp%3Ftp%3D%26arnumber%3D875398%26url%3Dhttp%253A%252F%252Fieeexplore.ieee.org%252Fiel5%252F7012%252F18933%252F00875398

http://artificial.ir/intelligence/thread619.html

http://nn4e.blogfa.com/post/468

http://www.mathworks.com/matlabcentral/linkexchange/links/3491-an-application-of-genetic-algorithm-to-solve-n-queens-problem

http://freesourcecode.net/matlabprojects/56883/genetic-algorithm-for-n-queen-problem-in-matlab#.VfKumBGqqkp

http://www.codeforge.com/s/0/matlab-8-queens-problem-genetic-algorithm

http://www.mathworks.com/matlabcentral/fileexchange/35820-genetic-algorithm-for-n-queen-problem

http://blog.jeroenpelgrims.be/solving-8-queens-problem-on-an-8×8-board-with-a-genetic-algorithm/

http://www.mathworks.com/matlabcentral/fileexchange/35820-genetic-algorithm-for-n-queen-problem

 

 

دیدگاهتان را ثبت کنید

آدرس ایمیل شما منتشر نخواهد شدعلامتدارها لازمند *

*

x

شاید بپسندید

آیا در کارها حضور بشر لازم است؟

رشد تکنولوژی، نیاز به نیروی کار را انسانی را در بسیاری از ...