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

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

برای ارزیابی از تابع هدف بیان شده برای مساله مکان یابی هاب که به کمینه سازی مجموع هزینه های مسیر یابی و هزینه های ایجاد می پردازد، استفاده می کنیم.
مقدار ارزیابی کروموزوم t ام را با نشان می دهیم.
شکل(3-3) روند ارزیابی
3-3-4- معیار توقف :
معیار توقف برای خاتمه دادن الگوریتم ، رسیدن به تعداد نسل های تعریف شده می باشد.
3-3-5- نخبه گرایی
در الگوریتم پیشنهادی ، تعدادی از بهترین جواب های هر نسل یعنی آن جواب هایی که تابع هدف کمتری دارند با احتمال PElitism به نسل بعدی منتقل می شود.
3-3-6- عملگر تقاطع
در الگوریتم ژنتیک، عملیات تقاطع ، دو کروموزوم والد را به دو کروموزوم فرزند که دارای ویژگی های والدین هستندترکیب می کند. در این تحقیق برای انتخاب والدین ، از روش مسابقه ای و بصورت تصادفی استفاده شده است.
در عملگر تقاطع ،دو عدد تصادفی غیریکسان بین 1 تا N تولید می کنیم. آن ها را r و sمی نامیم (rشکل(3-4) عملگر تقاطع
3-3-7- عملگر جهش
عملیات جهش در الگوریتم ژنتیک با ایجاد تغییرات تصادفی برنامه ریزی نشده در یک کروموزوم، امکان جستجوی قسمت های وسیع تری از فضای جواب را فراهم کرده و از همگرایی پیش از موعد الگوریتم جلوگیری می کند. در الگوریتم ژنتیک بکار گرفته شده در این تحقیق ، دو نوع عملگر جهش استفاده شده است.
در عملگر جهش نوع 1 دو عدد تصادفی غیر یکسان بین 1 تا N انتخاب می کنیم. محتوای ژن های متناظر با این دو عدد تصادفی با هم عوض می شوند. این عملگر Swap نام دارد.
شکل(3-5) عملگر جهش نوع 1
در عملگر جهش نوع 2 ،محتوای کروموزوم انتخاب شده، N-5 عدد به سمت راست جابجا می شود.
مثلا برای N=7 عملگر جهش نوع 2 بصورت زیر عمل می کند:
شکل(3-6)عملگر جهش نوع 2
3-3-8- انتخاب
انتخاب کروموزوم های واجد شرایط برای پیاده سازی عملگرهای تقاطع و جهش و تولید فرزندان جدید ،ارائه شده در این تحقیق، براساس روش مسابقه ای می باشد.بدین ترتیب که دو جواب بصورت تصادفی انتخاب شده و هرکدام که مقدار تابع هدف کمتری داشت، به عنوان والد انتخاب می شود.
3-3-9- معیار توقف
شرط توقف الگوریتم، می تواند عدم تغییر جواب در چند تکرار متوالی ، سپری شدن مدت زمان معینی از حل یا هر شرط خاص دیگر باشد. در الگوریتم ژنتیک پیشنهادی، شرط توقف، تولید معینی نسل (Max-Gen) از جمعیت اولیه است. فلوچارت الگوریتم ژنتیک پیشنهادی در شکل
(3-6) آمده است.
شکل(3-7) فلوچارت الگوریتم ژنتیک

Share