الگوریتم بهینه سازی ژنتیک چند هدفه (NSGA-II)

از منظر ریاضی، مسئله چند هدفه بدین صورت تعریف می شود:
کمینه یا بیشینه کردن بردار f(x)، که در آن x بردارn بعدی متغیرهای تصمیم x=(x1, x2,…xn) از مجموعه S است یا به عبارت دیگر:

بنابراین مسئله چند هدفه شامل n متغیر و q شرط و m هدف است که در آن توابع هدف می‌‌توانند خطی یا غیر خطی باشند. تابع ارزیابی F در مسئله چند هدفه، مجموعه را در متغیر تصمیم تصویر می‌‌کند: یعنی SfF در روش‌‌های وزندهی پیش از حل مسئله چند هدفه تبدیل به مسئله ای تک هدفه می‌‌شود. به عبارت دیگر، در این روش برای پیدا کردن جواب‌‌های مؤثر این مسئله چند معیاره:

می‌‌بایست جواب بهینه این مسئله تک معیاره را یافت:

که در آن fm(x) توابع هدف، f(x) تابع هدف نهایی است که از تلفیق توابع هدف مسئله به وجود آمده و هدف بهینه کردن آن است، و wk نیز وزن‌‌های توابع هدف اند.
در این حالت شرط لازم برای اینکه یک نقطه بهینه ی کلی باشد، آن است که شرایط کان و تاکر برقرار باشد و شرط کافی این است که برنامه ریزی محدب باشد.
در شرایط کان و تاکر چنین بیان می‌‌شود:
1- تابع هدف z(x) تابعی مقعر باشد (در حالت حداکثر کردن)؛
2- مجموعه جواب‌‌های پذیرفتی، مجموعه ای محدب باشد (در حالت حداکثر کردن)؛ و
3- توابع هدف مشتق پذیر باشند.
همان طور که ملاحظه می‌‌شود، این روش علاوه بر محدودیت‌‌هایی که در شرایط اجرا دارد (شرایط کان و تاکر)، در وزن دهی نیز با مشکلاتی مواجه است و جواب خروجی وابسته به وزن‌‌های ورودی است. به علاوه در این روش‌‌ها برای به دست آوردن مجموعه ی جواب‌‌های مؤثر، لازم است الگوریتم به دفعات حل شود و در هر اجرا می‌‌بایست جواب جدیدی به دست آید.

در روش‌‌های وزن دهی پس از حل، مشکلات ناشی از وزن دهی، که در روش مذکور بیان شد، وجود ندارد. همچنین با استفاده از الگوریتم‌‌های تکاملی در این روش‌‌ها، یک بار حل مسئله به مجموعه ای از جواب‌‌های مؤثر منجر خواهد شد. همچنین این الگوریتم‌‌ها با تأکید بر حرکت به سوی جواب بهینه کار می‌‌کنند و با تعریف تابع هزینه در آن می‌‌توان شرایط بهینگی را تعریف کرد. از طرفی، در این الگوریتم‌‌ها تأکیدی بر شرایط کان و تاکر، نظیر آنچه که در روش‌‌های وزن دهی پیش از حل وجود داشت، نیست. در دهه اخیر الگوریتم‌‌های تکاملی چند هدفه بسیاری پیشنهاد شده است. از جمله این الگوریتم‌‌ها می‌‌توان به الگوریتم‌‌های VEGA و FFGA ، SPEA و NSGA اشاره کرد. الگوریتم ژنتیک دارای مشخصاتی است که کاربرد آن را در مسائل چند هدفه، در قیاس با دیگر الگوریتم‌‌ها آسان تر می‌‌سازد:
• الگوریتم ژنتیک از کدهای دودویی برای کدینگ متغیرهای تصمیم گیری استفاده می‌‌کند.
• الگوریتم ژنتیک از چرخه ی احتمال برای انتخاب والد استفاده می‌‌کند و این خود باعث نزدیک شدن به بهترین جواب می‌‌شود.

جبهه ی جواب‌‌های مؤثر

جواب مؤثر از مفاهیم پایه ای در مسائل چند هدفه است. اگر در مسئله ای f1 و f2 و … fk توابع هدف باشند، x جواب مؤثر یا غیر غالب است البته در صورتی که برای تمامی i=1,2,…,k این دو شرط برقرار باشد.
جواب xi در تمامی هدف‌‌ها بدتر از xj نباشد؛ یعنی

1- جواب xi حداقل در یک هدف بهتر از xj است؛ یعنی

در فضای جست و جوی SRn فضای توابع هدف FRm و تابع هدف f:S→F={f(x:x∈S)}، بردار xS، جوابی مؤثر در S و F است اگر وجود نداشته باشد yF به قسمی که f_k (y)≤f_k (x) برای 1,…,m و حداقل برای یک k f_k (y)<f_k (x) باشد. در حقیقت یک نقطه ی جواب مؤثر است اگرهیچ نقطه ی دیگری در فضای جست و جو وجود نداشته باشد به نحوی که در همه ی توابع هدف بهتر از آن نقطه باشد. مفهوم جواب مؤثر منجر به تعریف جبهه ی جواب مؤثر خواهد شد اگر به جای یک نقطه، مفهوم به مجموعه ای از نقاط تعمیم داده شود. به عبارت دیگر، جبهه ی جواب مؤثر مجموعه ای از نقاط جواب است که هیچ کدام بر یکدیگر غلبه نمی کنند. (Sumathi et al., 2008) و در بین مجموعه ای از جواب، جبهه ای که اعضای دیگر جبهه‌‌ها بر آن غلبه نکنند جبهه ی پارتو تقریبی است.

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

روش کار و الگوریتم کلی NSGA-II به شرح زیر است:
1- ایجاد جمعیت اولیه
2- محاسبه معیارهای برازندگی
3- مرتب کردن جمعیت بر اساس شرط‌‌های غلبه کردن
4- محاسبه فاصله ازدحامی
انتخاب: به محض اینکه جمعیت اولیه بر اساس شرط‌‌های غلبه کردن مرتب شد، مقدار فاصله ازدحامی در آن محاسبه خواهد شد و انتخاب از میان جمعیت اولیه آغاز می‌‌شود. این انتخاب بر اساس دو المان صورت می‌‌پذیرد:
رتبه جمعیت: جمعیت‌‌ها در رتبه‌‌های پایین تر انتخاب می‌‌شوند و
محاسبه فاصله: با فرض اینکه p و q دو عضو از یک رتبه باشند، عضوی انتخاب می‌‌شود که فاصله ازدحامی بیشتری دارد. لازم به ذکر است که اولویت انتخاب ابتدا با رتبه و سپس بر اساس فاصله ازدحامی است.
انجام تقاطع و جهش برای تولید فرزندان جدید، این کار با استفاده از روش انتخاب دودویی انجام می‌‌گیرد.
تلفیق جمعیت اولیه و جمعیت به دست آمده از تقاطع و جهش
جایگزین کردن جمعیت والدین با بهترین اعضای جمعیت تلفیق شده در مراحل قبل، در مرحله اول، اعضای رتبه‌‌های پایین تر جایگزین والدهای قبلی می‌‌شوند و سپس بر اساس فاصله ازدحامی مرتب می‌‌شوند. این فرایند به صورت خلاصه در شکل 2-16 نشان داده شده است. همان طور که شکل 2-16 نشان می‌‌دهد، جمعیت اولیه و جمعیت ناشی از تقاطع و جهش، ابتدا بر حسب رتبه دسته بندی می‌‌شوند و قسمتی از آن‌‌ها که دارای رتبه پایین تری هستند، حذف میگردند. در مرحله بعد، جمعیت باقیمانده بر اساس فاصله ازدحامی مرتب می‌‌شوند. در اینجا مرتب سازی داخل یک جبهه انجام می‌‌شود.
تمامی مراحل تا نسل (و یا شرایط بهینگی) مورد نظر تکرار می‌‌شوند.

شکل ‏2 16: نحوه مرتب کردن جمعیت در الگوریتم NSGA-II که در آن P جمعیت اولیه و Q جمعیت ناشی از تقاطع و جهش است و Fi نشان دهنده جبهه است.
4556 بازدید