پیشینه  الگوریتم ژنتیک چند هدفه (NSGA)

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

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

الگوریتم ژنتیک با مرتب سازی نامغلوب، یکی از مطرح ترین و پرکاربردترین الگوریتم های بهینه سازی در زمینه ی بهینه سازی چندهدفه می باشد. اسرینیباس و دِب در سال ۱۹۹۵ روش بهینه سازی (NSGA)  را برای حل مسائل بهینه سازی چند هدفه معرفی نمودند. نکات برجسته ای که در مورد این روش بهینه سازی وجود دارند، عبارتند از:

• جوابی که هیچ جواب دیگری، به طور قطع بهتر از آن نباشد، دارای امتیاز بیشتری است. جواب ها بر اساس این که چند جواب بهتر از آن ها وجود داشته باشند، رتبه بندی و مرتب می شوند.
• شایستگی (برازندگی) برای جواب ها بر حسب رتبه آن ها و عدم غلبه سایر جواب ها، اختصاص می یابد.
• از شیوه اشتراک برازندگی (Fitness Sharing) برای جواب های نزدیک استفاده می شود تا به این ترتیب پراکندگی جواب ها به نحو مطلوبی تنظیم شود و جواب های به طور یکنواخت در فضای جستجو پخش شوند.

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

توسط دِب و همکارانش در سال ۲۰۰۰ معرفی گردید [54]. ویژگی های عمده این الگوریتم عبارتند از:

• تعریف فاصله تراکمی (Crowding Distance) به عنوان ویژگی جایگزین برای شیوه هایی مانند اشتراک برازندگی
• استفاده از عملگر انتخاب تورنومنت دو-دویی
• ذخیره و آرشیو کردن جواب های نامغلوب که در مراحل قبلی الگوریتم به دست آمده اند (نخبه گرایی)

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