الگوریتم ژنتیک و کاربرد های آن

الگوریتم ژنتیک یکی از روش های بهینه سازی فرا ابتکاری است که در مسائل بهینه سازی گوناگون مورد استفاده قرار می گیرد و بسیاری از مسائل NP-hard در علوم مهندسی خصوصا مهندسی صنایع با استفاده از این الگوریتم حل می گردد.لذا آشنایی با آن به تمامی مهندسین صنایع توصیه می گردد.

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

الگوریتم ژنتیک(GA)یک روش فرا ابتکاری(metaheuristic) برای یافتن جواب بهینه مسائل مدل سازی می باشد.

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

هر کدام از جواب های کاندید،دارای مجموعه ویژگی ها یا کروموزوم هستند که می تواند جهش یابند و تغییر کنند.به طور سنتی،جواب ها به صورت باینری صفر و یک نمایش داده می شوند اما کد گذاری های دیگر نیز قابل استفاده می باشند.

تکامل معمولا با  جمعیتی از جواب های تولید شده تصادفی آغاز می شود و فرآیندی تکراری می باشد و جمعیت در هر تکرار تولید نامیده می شود.

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

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

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

الگوریتم ژنتیک جمعیتی از n کروموزوم(جواب)را با مقادیر برازندگی مربوطه حفظ می کند و سپس والد(parent) ها را بر اساس برازندگی انها انتخاب می کند تا جواب های بعدی را تولید کنند.

در نتیجه جواب های بهتر از شانس بیشتری برای قرار گیری به عنوان والد در جواب های بعدی برخوردارند.

کاربرد الگوریتم ژنتیک در مهندسی صنایع

این الگوریتم در مسائل بهینه سازی که دستیابی به جواب دقیق مسائل بنا به دلایلی همچون زمان بر بودن و np-hard بودن مسئله،نظیر مسائل پیچیده مسیریابی بسیار پرکاربرد است و در زمان معقولی می توان به جواب های قابل قبول و مناسبی دست یافت.

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

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

1-آغاز

یک جمعیت تصادفی از n کروموزوم ایجاد کنید.

2-برازندگی:

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

3-جمعیت جدید:

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

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

ب)جابجایی(crossover):با در نظر گرفتن احتمالات جابجای،برای ایجاد جواب های جدید(فرزندان)بین والد ها جابجایی ایجاد کنید.اگر هیچ جابجایی انجام نشود،فرزندان دقیقا مشابه والد ها خواهند بود.

ج)جهش:با احتمال جهش،در فرزندان جهش ایجاد کنید.

د)پذیرفتن:فرزندان جدید را در میان جمعیت قرار دهید.

4-جایگزینی:

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

5-آزمایش:

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

6-لوپ:

به گام 2 برگردید.

در شکل زیر فلوچارت پیاده سازی این الگوریتم را برای یک مسئله بهینه سازی مشاهده می کنید:

امیدواریم مقاله آشنایی با الگوریتم ژنتیک برای شما مهندسین و مدیران گرامی در ورود به بازار کار مهندسی صنایع مفید واقع گردد.

در صورت نیاز به مشاوره و کسب اطلاعات بیشتر با شماره های ٠٢١٧٧٢٩٨۶٨٢ و ٠٢١٧٧٢٩٧٩٠١ تماس حاصل فرمایید.