فرض میکنیم که منظور از بهینه سازی کمینه سازی توابع هدف است. مسأله بهینه سازی چند هدفه را به صورت کلی میتوان به شکل زیر بیان نمود.:
در این مسأله مقصود کمینه سازی توابع هدف است. p نامعادله قید (۱) و q معادله قید (۲) محدودیت های مسأله بوده و منطقه شدنی را مشخص میکنند. پس در این مسأله به دنبال متغیرهای تصمیمی نظیر هستیم که ضمن ارضای محدودیت های (۱) و (۲) کم ترین مقادیر توابع هدف را دارا باشند.
توابع هدف بیشینه سازی را میتوان به تبدیل خطی با ضریب منفی به کمینه سازی تبدیل نمود. هم چنین معادلات و نامعادلات قیدی نیز با تبدیل خطی به شکل بیان شده در رابطهها درمی آیند. پس صورت کلی مسأله بهینه سازی که بیان گردید لطمهای به عمومیت آن نمیزند.
۳-۳-۲- فضای شدنی
فضای شدنی عبارت است مجموعه شدنی که زیر مجموعه فضای تصمیم بوده و قیود مسأله را ارضا نماید.
(۳-۱۲)
بردارهای G(X) و H(X) معادلات و نامعادلاتی هستند که پیش از این به عنوان قیود مسأله تعریف گردیدند. که توسط بردار F از در فضای هدف تصویر میشود فضای شدنی را در فضای هدف تعریف میکند.
(۳-۱۳)
(۳-۱۴)
۳-۳-۳- روابط بین بردارهای هدف
با فرض این که منظور از بهینه سازی کمینه سازی توابع هدف است بین هر دو بردار هدف ممکن است حالت های زیر اتفاق بیفتد.
(۳-۱۵)
در این حالت گفته می شود برابرند.
(۳-۱۶)
در این حالت گفته میشود بدتر از نیست.
(۳-۱۷)
در این حالت گفته میشود مطلقاً بهتر از است.
ممکن است هیچ یک از حالات فوق رخ ندهد در چنین شرایطی یا مطلقاً بهتر از است که این معادل حالت سوم میباشد و یا حالت چهارمی است که اصطلاحاً گفته میشود نسبت به یک دیگر بیتفاوت هستند. بیان ریاضی حالت چهارم به شکل زیر است:
(۳-۱۸)
شکل۳-۱۳: روابط میان پاسخ ها[۵]
در شکل ۳-۱۳ که چند نقطه در فضای هدف یک مسأله با دو هدف را نشان میدهد روابط زیر بین نقاط F,C,B,A برقرار است:
۳-۳-۴- غلبه پارتو
براساس مفهوم غلبه پارتو[۹۳] برای دو بردار تصمیم اگر در همه اهداف بدتر از نباشد و حداقل در یک هدف مطلقا بهتر از باشد گفته میشود بردارد بردار را مغلوب میکند[۹۴]. بیان ریاضی این مفهوم با فرض کمینه سازی به شکل زیر است:
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
(۳-۱۹)
بنابراین با توجه به مفهوم غلبه و روابط تعریف شده بین بردارهای هدف برای هر دو بردار تصمیم روابط زیر تعریف میگردد.
(۳-۲۰)
در این حالت گفته میشود بر غلبه دارد.
(۳-۲۱)
در این حالت گفته میشود بر غلبه ضعیف دارد.
(۳-۲۲)
در این حالت گفته میشود نسبت به بی تفاوت است[۹۵].
حالت های گفته شده در مثال شکل ۳-۱۳ کاملاً مشهودند. در این مثال بردارهای متناظر با نقاط موجود در مستطیل بالا- راست مغلوب بردار متناظر B میباشند. بردارهای متناظرنقاط موجود در مستطیل پایین- چپ بر بردار متناظر B غلبه دارند. پاسخ هایی که بردار هدف متناظر آن ها در دو منطقه گفته شده نیست نسبت به بردار متناظر B بیتفاوت میباشند.
۳-۳-۵- بهینگی پارتو
برای تعریف بهینگی پارتو[۹۶] لازم است مفهوم نامغلوبی یک پاسخ بیان گردد. بردار تصمیمم نسبت به مجموعه نامغلوب است اگر و تنها اگر:
(۳-۲۳)
حال تعریف میشود که بهینه پارتو است اگر و تنها اگر نسبت به نامغلوب باشد. نقاط توپر شکل ۳-۱۳ بهینه پارتو هستند. این نقاط نسبت به یک دیگر بی تفاوت میباشند. تفاوت اساسی میان بهینه سازی تک هدفه و چند هدفه در این مثال به خوبی روشن است. مسأله بهینه چند هدفه مانند مثال شکل ۳-۱۴ محدود به یک پاسخ بهینه منفرد نمیشود. بلکه مجموعهای از پاسخ های بهینه برای آن وجود دارد که هیچ یک بر دیگری برتری ندارد و تنها ترجیحات تصمیم ساز است که از میان این پاسخ ها یکی را برمیگزیند.
شکل ۳-۱۴: بهینگی پارتو در فضای هدف[۵]
۳-۳-۶- مجموعه و جبهه بهینه پارتو و نقطه ایدهآل
مجموعه پاسخ های بهینه پارتو برای یک مسأله چند هدفه را مجموعه بهینه پارتو[۹۷] میگویند. هم چنین بردارهای هدف متناظر با آن به جبهه بهینه پارتو[۹۸] معروف است. تعریف دیگری که میتواند در انتخاب پاسخ بهینه کمک کند نقطه ایدهآل است. نقطه ایدهآل[۹۹] نقطهای است که مقادیر تمام توابع هدف برای آن کمینه باشد. این نقطه غالباً در ناحیه شدنی فضای هدف قرار ندارد. نقطه پاد ایده آل نیز نقطهای است که مقادیر تمامی توابع هدف برآن بیشینه است. شکل ۳-۱۵ به صورت شماتیک برای یک مسأله دو هدف جبهه پارتو و نقاط ایدهآل و پاد ایدهآل را نشان میدهد.
شکل ۳-۱۵: جبهه پارتو و نقاط ایده آل و پاد ایده آل در فضای هدف[۵]
۳-۳-۷- تعادل
از شکل جبهه پارتو میتوان اطلاعاتی راجع به تعادل[۱۰۰] میان اهداف به دست آورد. تعادل بیانگر حساسیت اهداف نسبت به تغییرات یک دیگر است. هنگامی که جبهه پارتو به نقطه ایدهآل خیلی نزدیک میشود تعادل ضعیف است. در این حالت میتوانیم به نقطه ایدهآل نزدیک شویم اما در تغییرات اهداف نسبت به هم بسیار سریع است و میتواند مسأله را به سرعت از حالت مناسب که اهداف در محدوده منطقی باشند خارج نماید. اما هنگامی که جبهه پارتو به گونهای است که زیاد به نقطه ایدهآل نزدیک نمیشود تعادل قوی است و تغییر در اهداف نسبت به یک دیگر به آرامی صورت میگیرد در این حالت اگر چه نمیتوانیم به پاسخ بهینهای نزدیک به نقطه ایدهآل برگزینیم امّا محدوده انتخاب بزرگ تری وجود دارد و دست تصمیم ساز برای انتخاب های گوناگون گستردهتر است. شکل ۳-۱۶ برای یک مسأله بهینهسازی دو هدفه به صورت شماتیک تعادل ضعیف و قوی را در کنار نقطه ایدهآل نشان میدهد. حساسیت اهداف در تعادل قوی و ضعیف در این شکل قابل مقایسه است.
شکل ۳-۱۶: تعادل قوی و ضعیف بین اهداف[۵]
۳-۴- بهینه سازی چند هدفه با بهره گرفتن از الگوریتم ژنتیک
استفاده از الگوریتمهای تکاملی در حل مسایل بهینه سازی چند هدفه را نخستین بار Rosenberg (1967) پیشنهاد کرد. اما نخستین کاربرد عملی آن بوسیله Schaffer (1984) انجام شد. الگوریتمی که Schaffer با نام VEGA [۱۰۱]ارائه نمود [۱۶] بدین ترتیب بوده که جمعیت هر نسل را به تعداد اهداف تقسیم مینمود و در هر بخش یکی از اهداف به صورت مستقل مبنای تکامل همان جمعیت کوچک تر قرار میگرفت وسپس کل جمعیت از طریق عملگرهای ژنتیکی به جمعیت نسل بعد انتقال مییافت. ایراد الگوریتم Schaffer در این بود که بدلیل عدم توجه به همه اهداف در هر بخش همه نقاط جبهه بهینه را ارائه نمیداد و پاسخ ها به سمت نقاط مرزی جبهه بهینه متمایل میشد.
نخستین بار Goldberg (1989) بکارگیری مفهوم بهینگی پارتو در الگوریتم های ژنتیکی چند هدفه را مطرح نمود[۱۷]. در روشی که Goldberg پیشنهاد کرد تمامی اعضای جامعه بر حسب درجه نامغلوب بودن آن ها مرتب میشوند. بدین ترتیب که ابتدا تمامی اعضای نامغلوب جمعیت موجود شناسایی و به آن ها رتبه نامغلوبی ۱ اختصاص مییابد. سپس با حذف فرضی اعضای رتبه ۱ دومین دسته از اعضای نامغلوب جمعیت شناسایی شده و در رتبه ۲ قرار میگیرند و به همین ترتیب این فرایند تا رتبه بندی همه اعضای جمعیت ادامه مییابد. براساس این روش رتبه نامغلوبی هر عضو معیار شایستگی آن برای عملگر ژنتیکی انتخاب میباشد. اعضای هم رتبه شانسی برابر برای تولید فرزندان و حضور در جمعیت نسل بعدی دارند. اما شانس رتبههای بعدی که در واقع مغلوب رتبههای پیشین خود بودهاند کمتر است. این روش بنام رتبه بندی پاسخ های نامغلوب[۱۰۲] شناخته میشود. شکل ۳-۱۷ دسته بندی اعضای یک جمعیت را در بهینه سازی دو هدفه به صورت شماتیک نشان میدهد.
شکل ۳-۱۷: رتبه بندی پاسخ های نامغلوب[۵]
در سال های اخیر الگوریتم های بسیاری بر اساس مفهوم بهینگی پارتو ارائه شدهاند و به طور عمومی به آنها الگوریتم های بر مبنای پارتو [۱۰۳] گفته میشود. ویژگی های مهمی که در الگوریتم های بر مبنای پارتو تفاوت میان آنها را مشخص میکند عبارت است از:
روش اختصاص رتبه شایستگی به پاسخ ها که چگونگی هدایت جمعیت پاسخ ها را به سمت جبهه پارتو در حین پیشرفت نسل ها مشخص میکند.
حفظ توزیع پاسخ ها در طول تمامی جبهه پارتو به منظور شناخت بهتر تعادل میان اهداف.
سرعت همگرایی به سمت جبهه پارتو و زمان و حافظه موردنیاز اجرای الگوریتم.
شکل های ۳-۱۸ و ۳-۱۹ چگونگی هدایت پاسخ ها به سمت جبهه پارتو و منظور از توزیع آن ها در طول جبهه را به صورت شماتیک در یک مسأله بهینهسازی دو هدفه نشان میدهد.
شکل۳-۱۸: دو روش متمایز رتبه بندی و هدایت پاسخ ها[۵]
شکل ۳-۱۹: اثر حفظ پخش پاسخ ها در طول جبهه پارتو a) مطلوب b) نامطلوب[۵]
[سه شنبه 1401-04-14] [ 03:42:00 ب.ظ ]
|