اشنایی با الگوریتم ژنتیک

اشنایی با الگوریتم ژنتیک بصورت خلاصه و با بیان مراحل کار:

نحوه کار الگوریتم ژنتیک به این شکل است که برای حل مسئله ابتدا باید کروموزوم ها را تشکیل دهیم

کروموزوم: یک راه حل برای مسئله مورد نظر می باشد . بعنوان مثال اگر مسئله ما 3 متغیر داشته باشد یک کروموزوم یعنی سه مقدار ممکن برای این سه متغیر.

در مسئله جدول فروشنده دوره گرد هر کروموزوم یعنی یک ترتیب از اعداد 1 تا n که به این معنی که n شهر را به چه ترتیبی برویم

بعد از تعریف  کروموزوم باید یک جمعیت اولیه بسازیم. جمعیت اولیه یعنی تعدادی کروموزوم در کنار یکدیگر.

بعنوان اگر ما اندازه جمعیت اولیه را 50 در نظر گرفتیم ، یعنی 50 عدد کروموزم باید ایجاد کنیم.هر کروموزوم بعنوان یک فرد در جمعیت شناخته میشود.

1) گام اوال: ساخت جمعیت اولیه

2) گام دوم : ارزیابی جمعیت اولیه

بعد از ساخت جمعیت اولیه کار بعدی ، ارزیابی جمعیت می باشد . به این معنی که هر کروموزوم را بررسی کنیم که برای مسئله ما به چه میزان مناسب هستند و جوابی که میدهد به چه میزان خوب می باشد.

برای ارزیابی کروموزوم ها بایستی یک تابع شایستگی تعریف کنیم. تابع شایستگی یا Fitness  با توجه به مسئله ای که میخواهیم توسط الگوریتم ژنتیک حل کنیم تعریف میشود . بعنوان مثال برای حل فروشنده دوره گرد توسط الگوریتم ژنتیک ، جوابی مناسب است که از هر شهر فقط یکبار عبور کنیم و همچنین کمترین مسافت ممکن را طی کنیم

3) گام سوم : انتخاب جمعیت والد

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

4) گام چهارم : ترکیب

پس از مرحله انتخاب  ، مرحله ترکیب یا cross over می باشد . در این مرحله دو فرد از جمعیت را به تصادف انتخاب میکنیم و با هم ترکیب میکنیم تا دو فرد جدید ساخته شود. این مرحله مشابه عمل ازدواج می باشد به این صورت که دو نفر با هم ازدواج میکنند و دو فرزند جدید به دنیا می اورند.

5) گام پنجم : جهش

پس از مرحله انتخاب ، مرحله جهش یا mutation می باشد . در مرحله جهش یکی یا چند ژن از کروموزوم را انتخاب میکنیم و مقدار انها را با یک مقدار تصادفی جایگزین میکنیم.

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

این کار را تا زمانی انجام میدهیم که به جواب مسئله با دقت مورد نظر برسیم.

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

شماره تماس: 09120563264