مقاله دسته بندی و مقایسه روش های فراابتکاری برای کاربرد در بهینه سازی چندهدفه

بخشی از مقاله

خلاصه

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

.1 مقدمه

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

درصورتیکه مسئله مورد نظر تنها دارای یک تابع هدف باشد آنرا یک مسئلهی تک هدفه یا تک معیاره مینامند ولی چنانچه دارای چندین تابع هدف باشد به آن، مسئله بهینهسازی چند هدفه یا چند معیاره میگویند. در اغلب مسائل بهینهسازی چندهدفه توابع هدف در تضاد با یکدیگر هستند مانند کمینهکردن همزمان وزن - هدفاول - و تغییرشکل یک سازه - هدف دوم - تحت بارگذاری معلوم، چرا که کاهش تغییر شکل غالبا نیازمند کاربرد مقاطع قویتر و احیانا افزایش وزن کل اعضای سازه می باشد.

رقابتی بودن اهداف در مسائل چند معیاره، باعث تغییر در مفهوم بهینه شده چرا که عملا یافتن مجموعهای از پاسخها و یک قضاوت و انتخاب بین آنها لازم است. مفهوم این نوع بهینه در سال 1881 م. توسط [1] Edgeworth ارائه شد    پس از آن Pareto در سال 1896م. این مفهوم را تعمیم داد .[2] ارائه اصول پایه ریاضی بهینهسازی چندهدفه را میتوان در دوره 1895 تا 1906 م. ردیابی کرد .[3] در این دوره [4] Cantor و [5] Hausdorff اصول فضای مرتب ابعادی نامحدود را بنا نهادند.

کاربرد بهینهسازی چندهدفه در حوزههای علم اقتصاد بیرونی توسط [6] Koopmans با ارائه نظریه ای در سال 1951 م. و اقدامات [7] Marglin در سال 1967 م. در برنامه ریزی استفاده از منابع آبی آغاز شد. کاربرد اولیه مهندسی بهینهسازی چندهدفه در مقاله Zadeh در سال 1963 م. ارائه گردید [8] و تا سال 1970 م. این قبیل کاربردها گسترش یافت. با گسترش و کاربرد روشهای فراابتکاری الگوریتمهای جدیدتری برای مسائل چند هدفه ارائه شد .[9] در ادامه مقاله ابتدا تعاریف اولیه و فرمولبندی واحد برای مسائل جندهدفه مرور میشود و سپس اهم شیوه-های فراابتکاری برای حل آن مورد بررسی قرار میگیرند.

.2 فرمول بندی بهینهیابی چندهدفه

توابع هدفی که بیشینهسازی آنها مدنظر است را میتوان با ضرب در -1 به تابع کمینهسازی تبدیل نمود. بهینه-یابی چندهدفه با ارائه مفهوم مغلوب یا نامغلوب بودن پاسخها نسبت به یکدیگر همراه است. شکل -1 - الف - فضای جستجوی یک مسئله - S - با دو متغیر طراحی 1 و 2 را نشان میدهد. اگر مقادیر فضای جستجو در ضابطه توابع هدف 1 و 2 محاسبه شوند، مجموعهY تشکیل میگردد. اگر هدف مسئله مینیمم کردن هر دو تابع هدف باشد، میتوان گفت منحنی پررنگ شده شکل -1 - ب - دارای مجموعهای از بهترین پاسخها است که بر سایر پاسخهای مجموعه Y غلبه دارد.

به دیگرسخن، پاسخهای روی لبه منحنی در شکل - 1 - نسبت به سایرین هم در تابع 1 و هم در تابع 2 مقادیر کمتری داشتهاند. ضمنا اعضای این مجموعه، هیچکدام بر یکدیگر غلبه ندارند چنانکه در بعضی از نقاط مقدار 1 کمتر و مقدار 2 بیشتر بوده و در سایر نقاط برعکس این حالت رخ میدهد. به این مجموعه از پاسخها که توسط هیچ پاسخی مغلوب نشده و اعضای خود نیز بر یکدیگر غلبه ندارند، مجموعه نامغلوب1 میگویند.

این راهکار حل مسائل بهینهسازی چندهدفه در سال 1980 م. توسط Schaffer ارائه شد [11] که جزء نخستین و ساده ترین روشهای مبتنی بر الگوریتم ژنتیک به شمار میآید. وقتی تعداد توابع هدف K و تعداد اعضای جمعیت یا نسل اولیه الگوریتم ژنتیک N باشد، Schaffer به این ایده رسید تا جمعیت را در هر نسل به K زیر جامعه N/K عضوی برابر تقسیم نماید و هر کدام از این زیرجامعهها یکی از توابع هدف را بهصورت جداگانه بهینه کند Zitzler .[12]، Thiele و Deb با مقایسه چندین روش و مشاهده نتایج توابع تست ZDT به این نتیجه رسیدند که VEGA نسبت به NPGA به نتایج بهتری میرسد.[13] این موضوع در توابع گسسته نمود بیشتری دارد. در شکل - 2 - گردشنمای این روش آمده است.

MOGA2.4 Fonesca و Fleming در سال 1993 م. ایده اختصاص رتبه Goldberg را بهکار برده، روش MOGA را ارائه کردند 14]و.[15 در این روش رتبهی یک شخص خاص از جمعیت براساس تعداد اشخاصی که در همان جمعیت، شخص مورد نظر را مغلوب میکنند، تعیین میگردد. بهعنوان مثال شخص   در نسل G توسط   - - شخص در همان نسل مغلوب شده است. رتبهی اختصاص یافته به شخص مورد نظر از رابطهی - 2 - محاسبه میشود .[12]

به تمامی پاسخهای نامغلوب رتبهی 1 و به سایر پاسخهای مغلوب رتبهی بیشتر از 1 اختصاص مییابد. پس از پایان رتبهبندی برای هر شخص یک میزان شایستگی3 تعیین میگردد. Fonesca و Fleming دو روش برای اختصاص شایستگی هر ذره ارائه کردند 14]، - 1 .[15 روش اختصاص رتبه بر اساس شایستگی - 2 روش رتبه بندی نیچه. پس از اختصاص شایستگی پاسخها برای تمامی رتبهها عملگرهای انتخاب، پیوند و جهش الگوریتم ژنتیک اجرا شده و نسل بعد به وجود میآید. تا ارضا شدن شرایط توقف، عملیات رتبهبندی و اختصاص شایستگی بر روی نسل جدید تکرار شده و در نهایت مجموعهی نامغلوب به عنوان پاسخ ارائه میگردد. شکل - 3 - گردشنمای این روش را نشان میدهد .[12]

NSGA - II - 4.5روش مرتب سازی نامغلوب براساس الگوریتم ژنتیک توسط Deb و همکارانش در سال 2000 م. ارائه شد .[16] مراحل این روش به صورت زیر است.

- 1  جمعیت اولیه   با N عضو به صورت تصادفی تشکیل میشود.

- 2  توسط عملگر انتخاب، جهش و پیوند جمعیت فرزندان   به وجود میآید.

- 3 جمعیت فرزندان و والدین - جمعیت اولیه در تکرار اول - با یکدیگر ترکیب شده، مجموعهی جدیدی با 2N عضو به وجود میآورند.