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

شکل (1-2): رهیافتهای مختلف رتبه بندی پارتو
در شکل سمت چپ، به اعضای جمعیت حاضر مقدارهای برازندگی نسبی براساس روش Goldberg نسبت داده شده است مقدار برازندگی 1، به جوابهای غیرپست جمعیت اختصاص داده می شود و جوابهای دارای این برازندگی از درون جمعیت حذف می شوند. سپس برازندگی 2 به جوابهای غیرپست باقیمانده در مجموعه حاضر تعلق می گیرد و آنها هم کنار می روند. این روال تا جایی که تمامی اعضای جمعیت دارای برازندگی خاص خود شوند ادامه می یابد. در شکل سمت راست، روش نسبت دادن مقدار برازندگی نسبی بدین صورت است که اگر هیچ جوابی وجود نداشت که بر راه حل مورد نظر ما غلبه نماید به آن راه حل مقدار 1، اگر یک جواب بر آن غلبه نماید مقدار 2، و اگر دو جواب وجود داشت که بر آن غلبه می کرد، مقدار 3 برای برازندگی آن درنظرگرفته می شود. این فرایند تا جایی که تمامی جوابها دارای مقدار برازندگی شوند ادامه می یابد.
2-3-1- الگوریتمهای تعاملی چند هدفه (Multi-Objective Evolutionary Algorithms)
پس از ارائه پیشنهاد بسیار کارآمد Goldberg، در دهه اخیر تعدادی از الگوریتمهای تکاملی چند هدفه (MOEAs)‌ پیشنهاد شدهاند که در زیر نام تعدادی از آنها آورده شده است.
1-بردار ارزیابی الگوریتم ژنتیک (VEGA)
2-الگوریتم ژنتیک چند هدفه (MOGA)
3-الگوریتم ژنتیک جبهه پارتو نیچه (NPGA)
4-الگوریتم ژنتیک برپایه وزن دهی (WBGA)
5-الگوریتم ژنتیک برپایه مرتب سازی غیرپست (NSGA)
6-الگوریتم تکاملی با استفاده از پارتو SPEA))
7-الگوریتم پیشرفته (SPEA-II) SPEA
8-استراتژی تکاملی پارتو (PAES)
9-الگوریتم انتخابی برپایه پارتو (PESA)
10-الگوریتم تکاملی چندهدفه پویا (DMOEA)
بعضی از ویژگیهای این الگوریتمها در جدول (2-1) آمده است.
در الگوریتمهای بهینه سازی چند هدفه، فضا یا موقعیت معمولا توسط فاصله اعضاء از هم و در فضای هدف تعریف می شود. تقسیم برازندگی یا دیگر روشهای مشابه به منظور حفظ پراکندگی جوابها در فضای هدف مورد استفاده قرار می گیرند. شکل (2-2) برخی از این روشها را نمایش میدهد.
در شکلهای شماتیک فوق،‌راه حل های غیرپست توسط نقاط توپر و راه حلهای مغلوب توسط نقاط توخالی نمایش داده شدهاند.
در شکل (2-2) در قسمت (a) به اشتراک گذاردن برازندگی نمایش داده شده که در این روش همانند آنچه که در NSGA و MOGA مورد استفاده قرار گرفته است، از مقدار برازندگی عضوی که در فضای عضو دیگر قرار می‌گیرد کاسته می شود.

جدول (2-1): ویژگیهای تعدادی از الگوریتمهای تکاملی چندهدفه
ردیف
الگوریتم
تابع برازشی
نخبه‌گرایی
جمعیت خارجی
مزیت‌ها
اشکالات
1
VEGA
تطبیق هر زیر جمعیت با اهداف متفاوت
ندارد
ندارد
الگوریتم روبه جلوی چندهدفه
همگرایی در حد هر حدف
2
MOGA
جبهه پارتو
ندارد
ندارد
توسعه الگوریتم ژنتیک چندهدفه
همگرایی به کندی
3
NPGA
بدون هیچ تابع هدف
ندارد
ندارد
انتخاب مسابقه‌ای
وجود پارامترهای اضافی
4
WBGA
اهدف نرمال‌شده با وزن‌دهی متوسط
ندارد
ندارد
توسعه الگوریتم
مشکل اندازه پارامتر Niche
5
NSGA
بر پایه مرتب سازی غیر پست
ندارد
ندارد
همگرایی سریع
غیرهمگرایی در تابع هدف
6
SPEA
بر پایه مرتب سازی غیرپست خارجی
دارد
دارد
روش بدون پارامتر
مشکل اندازه
7
SPEA-II
توانایی در نقاط غالب
دارد
دارد
اطمینان از حصول نقاط حدی
برازش دشوار
8
PAES
جبهه پارتو
دارد
دارد
جهش تصادفی با رویکرد اجرایی ساده
رویکرد غیراجرایی
9
PESA
نبود تابع ارزیابی
دارد
دارد
سادگی در اجرای محاسبات
رویکرد
10
DMDEA
رده‌بندی بر پایه عضو
دارد
ندارد
قابلیت بهنگام کردن چگالی اعضا
دشواری اجرا

شکل (2-2): فرمهای مختلف محاسبه فضا و موقعیت را در الگوریتمهای MOEA جهت ایجاد پراکندگی
قسمت (b)‌ نشان می دهد که رتبه بندی شلوغی همانند آنچه که در الگوریتم NSGA-II مورد استفاده قرار گرفته است. فاصله نزدیک ترین راه حل غیرپست را تا جواب موردنظر محاسبه می نماید. در قسمت (c) موقعیت خطوط مشخصه نشان داده شده است. همانند آنچه که در الگوریتمهای PAES، PESA‌ و PESA_II مورد استفاده قرار گرفته است. هرچه تعداد راه حلهای داخل یک خانه مشخص بیشتر باشد، امکان انتخاب شدن کمتری در انتظار اعضای آن خانه میباشد.
قسمت (d) چیرگی‌است در این روش، آن راه حلی که دقیقا بر راه حلهای اطراف خود غلبه می کند توسط پارامتر ε نمایش داده میشود. با این تفاسیر قرار گرفتن جوابهای بسیار نزدیک به مجموعه غیرپست در میان مجموعه جواب نهایی عملا غیرممکن می گردد.
تاکنون بیشترین بررسیها بر روی الگوریتمهای NSGA، MOGA و NPGA صورت گرفته است و مقبولیت زیادی در میان الگوریتمهای بهینه سازی تکاملی چندهدفه دارا می باشند. امروزه نیز بسیاری از الگوریتمهای MOEA به نوعی مفهوم رتبه بندی چیرگی را مورد استفاده قرار می دهند و در عین حال، گاهاً برای حفظ پراکندگی بر روی فضای هدف، نخبه گرایی و یا فرمهای دیگری از نسبت دادن برازندگی براساس فضا و موقعیت جواب نیز مورد استفاده قرار می گیرند.

2-3-2- الگوریتمهای بهینه سازی نخبه گرا براساس رتبه بندی پارتو
عبارت نخبه گرائی در ادبیات الگوریتمهای تکاملی به معنای نگهداری و حفظ والدین خوب و انتقال آنها از نسلی به نسل دیگر جهت شرکت دادن آنها در فرآیند انتخاب و ترکیب می باشد. سابقه اولین استفاده از مفهوم نخبه گرائی حدودا به همان سالهای اولیه توسعه الگوریتمهای MOGA، NSGA و NPGA برمیگردد و به طور مشخص و مفصل در حدود سال های 94-1993 مورد بررسی قرار گرفت.
در بعضی الگوریتمهای MOEA نخبه گرا، استراتژی نخبه گرائی، حفظ جوابهای غیرپست می باشد. حفظ این جوابها معمولا توسط یک جمعیت خارجی ممکن میشود. بسیاری از طرح های اولیه این الگوریتم توسط Zitzler‌ مورد بررسی قرار گرفت ولی اولین مقاله منتشر شده در این زمینه، مقاله Parks و Miller است. آنان در الگوریتم خود از یک جمعیت خارجی استفاده کردند که اعضای آن تقریباً تمامی راهحلهای غیرپست می باشند. در این الگوریتم، جمعیت موردنظر محدود بوده و یک راه حل تنها در صورتی میتواند وارد آن شود که به طور قانع کنندهای با جوابهای موجود متفاوت باشد. در ادامه کار، طی فرآیند انتخاب، الگوریتم بهینه سازی به طور فعالی از جمعیت موردنظر استفاده مینماید. در مقاله مذکور، استراتژیهای مختلف انتخاب از میان جمعیت خارجی، مورد بررسی قرار گرفتهاند.
حدوداً سالهای 1994،‌ Zitzler و Thiele کاربردی‌ترین الگوریتم MOEA را که تا به حال ارائه شده است، پیشنهاد دادند. این الگوریتم که SPGA نام دارد از دو جمعیت مجزا که یکی خارجی و دیگری داخلی میباشد استفاده شده است. در الگوریتم مذکور، جمعیت خارجی که محدود نیز می باشد جهت ذخیره جوابهای غیرپست قبلی مورد استفاده قرار می گیرد. در ادامه روند بهینه سازی، با به دست آوردن یک جواب غیرپست جدید از درون جمعیت جدید داخلی و وارد شدن آنها به مجموعه پارتو دو اتفاق رخ می دهد:
الف) جوابهایی که جواب غیرپست جدید بر آنها چیره شده است از این مجموعه حذف می شوند.
ب) تعدادی از این راه حلها نیز به صورت دستهای از جمعیت خارج می شوند.
اتفاق دوم برای اطمینان از محدود بودن مجموعه پارتو رخ می دهد.
در این الگوریتم، جمعیت داخلی جدید با انتخاب از درون مجموعه ای که ترکیب دو جمعیت داخلی و خارجی قبلی است حاصل می گردد. ایده جالب یا شاید نقطه قوت این الگوریتم نوع تعامل دو جمعیت داخلی و خارجی در نسبت دادن مقادیر برازندگی می باشد.
در الگوریتم SPGA، به هر عضو از جمعیت خارجی و براساس تعداد جوابهایی از جواب داخلی که جواب مذکور می تواند بر آنها غلبه کند یک توانایی نسبت داده می شود سپس به هرکدام از اعضای مجموعه داخلی یک عدد تقریبی برازندگی براساس مجموع تواناییهای جوابهای خارجی غلبه کننده بر آن نسبت داده می شود. فرایند تخصیص برازندگی مذکور یک رهیافت تکاملی- همکاری بین دو جمعیت خارجی و داخلی می باشد.
تعداد زیادی از الگوریتم های مختلف MOEA‌ نیز بر همین اساس ولی با تغییرات کوچکی در نحوه نسبت دادن مقادیر برازندگی، نحوه انتخاب از جمعیت و نیز روشهای مختلف حفظ پراکندگی ارائه شده است. الگوریتمهایی نظیر PAES، PESA و NSGA-II از آن جملهاند. هدف اصلی آنها ایجاد تغییراتی در ساختار این الگوریتمها جهت حفظ پراکندگی و محدود کردن فضای هدف که الگوریتمهای MOGA و NSGA با آنها دست به گریبان بوده اند می باشد. علاوه بر این، کنترل میزان نخبه گرائی از جمله مواردی است که در همین راستا مورد بررسی قرار گرفت

دسته بندی : No category

دیدگاهتان را بنویسید