Upgrading labor

۳-۵- ساختار کلی الگوریتم مرتب­سازی نامغلوب ژنتیک (NSGA-II)
در دو دهه اخیر، الگوریتم­های تکاملی^[۶۱](EAs) مختلفی برای حل مسائل بهینه­سازی چندهدفه پیشنهاد و ارائه شده است. در این میان الگوریتم NSGA-II که بعنوان یک الگوریتم تکاملی جمعیت محور^[۶۲] توسط دِب و همکاران [۶۴] ارائه شد، برای حل مسائل مختلف استفاده شده است و کارایی آن در تولید جواب­های بهینه پارتوی متعدد و متنوع به اثبات رسیده است. در ادامه ساختار این الگوریتم شرح داده می­ شود.

۳-۵-۱- رویه مرتب­سازی نامغلوب سریع^[۶۳]
برای رتبه ­بندی یک مجموعه از جواب­ها و قرار دادن آن­ها در جبهه­های مختلف از نظر میزان درجه نامغلوب بودن، ابتدا دو پارامتر زیر برای هر کدام از جواب­ها محاسبه می­ شود؛ n_p که در واقع تعداد جواب­هایی است که بر جواب p غلبه کرده ­اند، و S_p که مجموعه جواب­هایی است که توسط جواب p مغلوب شده ­اند.
تمامی جواب­هایی که دارند، رتبه یک را اختیار می­ کنند و در جبهه اول قرار می­گیرند  .سپس، برای هر جواب p با رتبه یک، هر عضو (q) از مجموعه S_p ملاقات شده و آن یک واحد کاهش می­یابد. با این کار اگر شود، آن گاه جواب q رتبه دو را اختیار می­ کند و در جبهه دوم قرار می­گیرد. به همین ترتیب جبهه­های بعدی نیز تشکیل می­یابند. در زیرنحوه مرتب سازی نامغلوب سریع به صورت شکل و شبه­کد^[۶۴] ارائه شده است.
شکل ۳-۱- نحوه مرتب سازی جواب های نامغلوب یک جمعیت
Fast Non-dominated Sorting(P)
for each
for each
if then If p dominates q
Add q to the set of solutions dominated by p
else if then
Increment the domination counter of p
if then p belongs to the first front
rank of solutions in the first front
i=1 Initialize the front counter
while
Used to store the members of the next front
for each
for each
i f then q belongs to the next front
شکل۳-۲٫ شبه­کد رویه مرتب­سازی نامغلوب سریع
۳-۵-۲- رویه حفظ تنوع و پراکندگی
یکی از فاکتورهای مهم و تأثیرگذار بر عملکرد الگوریتم­های تکاملی، در جهت همگرایی به مجموعه جواب بهینه پارتو، داشتن رویکردی گسترش گرایانه در جستجوی جواب­ها، در فضای حل است. دستیابی به جواب­های با کیفیت بهتر، به کمک جواب­های متنوع­تر امکا­ن­پذیر است. در واقع در شرایطی که دو جواب از نظر برازندگی وضعیت یکسانی را دارند، جوابی ترجیح داده می­ شود که نسبت به دیگر جواب­های جستجو شده جمعیت، از میزان پراکندگی بیشتری برخوردار باشد. از این رو، در الگوریتم NSGA-II نیز رویه­ای برای این منظور طراحی شده است. جهت تشریح این رویکرد، ابتدا مفهومی را تحت عنوان فاصله تراکمی ارائه می­کنیم.
فاصله تراکمی^[۶۵]
برای بدست آوردن تخمینی از چگالی جواب­های موجود در کنار یک جواب خاص، مانند جواب i ام در جمعیت، میانگین فاصله دو جواب واقع در طرفین جواب i ام برای هر کدام از M تابع هدف، محاسبه می­ شود. مقدار عددی d_i که از محاسبه تقریبی فضای مکعبی اطراف جواب i با بکار بردن نزدیکترین همسایه­های آن بدست می ­آید را فاصله تراکمی می­نامیم. در شکل (۳-۲) فاصله تراکمی جواب i ام برابر است با میانگین طول اضلاع مستطیلی که رئوس آن، نقاط مجاور جواب i ام می­باشند.
شکل۳-۲٫ فاصله تراکمی
برای محاسبه فاصله تراکمی جواب­ها، لازم است که ابتدا هر تابع هدف به ترتیب نزولی مرتب شود و بردار اندیس­های مرتب شده جواب­ها ایجاد گردد. سپس، برای جواب­های ابتدایی و انتهایی بردار اندیس­های مرتب شده، فاصله تراکمی، بینهایت مقداردهی می­ شود و برای مابقی، فاصله تراکمی هر جواب بر اساس تفاضل مقادیر تابع هدف جواب بعد و قبل آن در بردار اندیس، طبق رابطه زیر محاسبه می­ شود:

(۳-۳۸)

که در آن و به ترتیب بیشترین و کمترین مقدار بدست آمده برای تابع هدف m ام در جمعیت حاضر است و و بترتیب مقدار تابع هدف m ام برای جواب بعدی و قبلی جواب j ام در بردار اندیس مرتب­شده تابع هدف m ام می­باشند. ذکر این نکته لازم است که برای هر جواب j ام، دو جواب j+1 ام و j-1 ام بعنوان همسایگان جواب j ام، برای تمام توابع هدف یکسان نمی­باشند. به ویژه برای همسایه­ها متفاوت خواهند بود. بعلاوه با توجه به ناهمسان بودن مقادیر توابع هدف، شکل نرمالیزه­شده آن­ها در نظر گرفته شده است. در ادامه شبه­کد مربوط به محاسبه فاصله تراکمی جواب­ها ارائه می­گردد.
Crowding Distance Assignment(P)
number of solutions in P
for each i, set d_i=0 initialize distance
for each objective m
sort using each objective value
so that boundary points are always selected
for j=2 to (l-1) for all other points
شکل۳-۳٫ شبه­کد محاسبه فاصله تراکمی