وبلاگ

با معرفی معیار فاصله تراکمی، برای مقایسه دو جواب، عملگری تحت عنوان عملگر مقایسه تراکمی ارائه می­ شود.

عملگر مقایسه تراکمی^[۶۶]
عملگر مقایسه تراکمی برای فرایند انتخابی که در ادامه ذکر می­ شود، طراحی شده است. فرض می­ شود که هر جواب i دو ویژگی زیر را دارد:

1. 1. یک رتبه یا درجه نامغلوب بودن که آن را با r_i نشان می­دهیم.

1. 1. یک فاصله تراکمی محلی که آن را با d_i نمایش می­دهیم.

فاصله تراکمی d_i یک اندازه از فضای جستجو حول جواب i است که توسط هیچ جواب دیگری از جمعیت اشغال نشده باشد. بر پایه دو ویژگی بیان شده، می­توانیم عملگر مقایسه تراکمی را با قاعده زیر تعریف کنیم:
تعریف: جواب i در مقایسه با جواب j پیروز می­ شود ، اگر و تنها اگر یکی از شرایط زیر برقرار باشد:

• • 1. 1. جواب i دارای رتبه بهتری باشد یا .

     

    1. 1. اگر جواب­های i و j هم رتبه­اند ، جواب i فاصله تراکمی بهتری را داشته باشد یا .

     

     

شرط اول این اطمینان را بوجود می­آورد که جواب پیروز از درجه نامغلوب بودن بهتری نسبت به حریف خود برخوردار است و شرط دوم که در هنگام هم­رتبه بودن جواب­ها با آن روبرو خواهیم شد، این اطمینان را می­دهد که جواب پیروز از ناحیه تراکمی بزرگتری برخوردار باشد.
با مطالب ارائه شده در فوق می­توانیم مراحل الگوریتم NSGA-II را گام به گام تشریح سازیم.
۳-۵-۳- مراحل الگوریتم NSGA-II
ابتدا جمعیت اولیه والدین با اندازه N بصورت تصادفی ایجاد می­ شود. سپس جمعیت تولید شده، مرتب­سازی نامغلوب گشته و جواب­ها در سطوح مختلفی از درجه نامغلوب بودن دسته­بندی می­شوند. به هر جواب بر حسب اینکه در چه جبهه­ای قرار دارد، ارزش یا رتبه­ای اختصاص داده می­ شود (جواب­های جبهه اول که در پایینترین سطح قرار دارند رتبه یک، جواب­های جبهه دوم رتبه دو و به همین ترتیب بقیه رتبه ­بندی می­شوند). در ادامه با بهره گرفتن از روش انتخاب مسابقه دودویی^[۶۷] مبتنی بر عملگر مقایسه تراکمی و عملگرهای تقاطع و جهش، جمعیت فرزندان با اندازه N تولید می­گردد. از ترکیب دو جمعیت والدین و فرزندان، جمعیت با اندازه ۲N حاصل می­ شود. از جمعیت به دست آمده نسل بعد انتخاب می­ شود. از آنجا که الگوریتم رویکردی نخبه گرایانه دارد، مجدداً اعضای با روش مرتب­سازی نامغلوب دسته­بندی می­شوند و پس از ایجاد جبهه­های متفاوت از نظر درجه نامغلوب بودن، جمعیت نسل بعد با اندازه N بترتیب از جبهه اول به بعد به طریقی که در ادامه بیان می­ شود، پر می­گردد. با ایجاد همان مراحلی که برای ذکر شد، انجام می­ شود و این حلقه تا رسیدن به شرط پایان و توقف الگوریتم ادامه می­یابد. در نهایت جبهه اول حاصل از مرتب­سازی آخرین نسل، بعنوان مجموعه جواب­های بهینه پارتو معرفی می­ شود.
فرض می­کنیم جمعیت حاصل از ترکیب والدین و فرزندان آن ، مرتب­سازی نامغلوب شده است و جبهه­های برای ایجاد گشته است. اینک جواب­های موجود در جبهه اول بعنوان بهترین جواب­های موجود در نسل حاضر، اولین کاندید برای پیوستن به نسل بعد می­باشند. اگر تعداد اعضای کمتر از می­باشد، همه آن­ها به منتقل می­شوند. مابقی اعضای از و بعد از آن از و الی آخر انتخاب می­شوند. این رویه ادامه دارد تا زمانی که بعنوان آخرین جبهه­ای که قرار است باقیمانده اعضای از آن انتخاب گردد، در نظر گرفته شود. در این هنگام چون تعداد کل اعضای از تعداد مورد نیاز باقیمانده بیشتر است، ابتدا اعضای به ترتیب کاهش فاصله تراکمی مرتب می­شوند و سپس تعداد مورد نیاز باقیمانده، از ابتدای این لیست انتخاب می­گردند. شکل (۳-۸) این رویه را بهتر نمایش می­دهد.

sorting
Crowding-distance
sorting
Rejected
P_t
Q_t
R_t
F₁
F₂
F₃
P_t+1
شکل۳-۴ . نمایشی از عملکرد NSGA-II
در ادامه شبه­کد تولید نسل بعد و فلوچارت کلیه مراحل الگوریتم آورده می­ شود.
Procedure of next generation(P_t+1)
combine parent and offspring population
F=fast-non-dominated-sort(R_t) F=(F₁,F₂,…), all nondominated fronts of R_t
until until the parent population is not filled
crowding-distance-assignment(F_i) calculate crowding-distance in F_i