- جمعیت آنتی بادیهای را بوسیله ترکیب و تشکیل دهید؛ به مرحله ۲ بروید.
هنگامیکه تعداد آنتی بادیهای غالب، بزرگتر از حداکثر محدودیت شود و اندازه جمعیت غالب بزرگتر از حداکثر اندازه جمعیت فعال شود، هر دو کاهش جمعیت غالب و انتخاب آنتی بادیهای فعال، از فاصله ازدحام استفاده میکنند. اپراتورهای تکثیر نسبی، بازترکیب و جهش، به صورت زیر تشریح میشوند.
تکثیر نسبی: در این الگوریتم، به طور خلاصه، اعضاء با مقدار فاصله ازدحام بیشتر، بیشتر تولید میشوند. عضوی که مقدار فاصله ازدحام بیشتری دارد، بیشتری دارد، به خاطر اینکه مقدار فاصله ازدحام حلهای مرزی، مثبت بینهایت است، قبل از محاسبه مقدار هر آنتی بادی فعّال، مقدار اعضاء کرانهها را برابر دوبرابر مقدار حداکثر مقدار آنتی بادیهای فعال (به استثنای اعضاء مرزی) قرارمیدهیم. بنابراین، مقدار به صورت زیر محاسبه میشود:
(۳۱.۲)
که به مقدار فاصله ازدحام آنتی بادی اشاره دارد.
بازترکیب: برای بازترکیب، هر عضو مجموعه را با یک عضو از که به صورت تصادفی انتخاب شدهاست، عملگر تقاطع را انجام میدهیم.
جهش: بعد از بازترکیب، عملگر جهش را به صورت یکسان و با احتمال برابر، بر روی تک تک اعضاء اجرا میکنیم. بنابراین، هر عضو از جمعیت ، دستخوش جهش میشود که m ، اندازه بردار متغیرها و یا تعداد ژنهای هر آنتی بادی و یک عدد تصادفی مانند میباشد.
۲-۵- روشهای اندازه گیری عملکرد الگوریتمهای چندهدفه [۳]
یکی از مشکلاتی که در حل مسائل چندهدفه با آن مواجه می شویم، چگونگی ارزیابی کیفیت حلهای نهایی است که بدلیل تناقض اهداف بکار رفته، گاهاً این امر کاری پیچیده خواهد بود.
به این منظور و در اوایل دهه ۹۰ میلادی از روشهای دیداری (مشاهده ای) برای مقایسه مجموعههای پارتو استفاده می کردند. بدیهی است این روشها دارای دو مشکل اساسی بودند ، اولاً اینکه ما در مقایسات علمی نیازمند مبنایی قابل اندازه گیری و کمّی بودیم و صرف اظهار نظر کیفی اشخاص، نمی توانست محکی مناسب در اندازه گیری کارایی الگوریتمها باشد. ثانیاً مشکل اساسی دیگر این روشها در مقایسه مجموعههای پارتو این بود که فقط برای حداکثر مسأله ۳ هدفه کاربرد داشتند. به این دلیل که امکان ترسیم فضای بیشتر از سه بعد برای مقایسه مجموعه جوابها وجود نداشت. تمام این مشکلات باعث شد تا پژوهشگران به فکر بیافتند تا روشهای منطقی، جامع و مناسب را به ا ین منظور ارائه نمایند. در مسائل تک هدفه، در پایان اجرای الگوریتمها، حلی را با توجه به نوع هدف (ماکزیمم یا مینیمم)، به عنوان بهترین حل انتخاب می شود و در این حالی است که در مسائل چندهدفه در پایان حل، مجموعه ای از جوابها ایجاد می شوند که بایستی با توجه به این مجموعه حلها راجع به عملکرد الگوریتم اظهارنظر شود. این روشها از این جهت مهم هستند که به پژوهشگر کمک می کنند تا عملکرد الگوریتمهای مورد بررسی را با روشی کمّی، ارزیابی و انحراف الگوریتم را مدیریت نمایند.
در این روشها غالباً مبنای اصلی طراحی هر معیار عملکرد بر مبنای یکی از سه حالت زیر است:
- تعداد حلهای غیرغالب بدست آمده توسط الگوریتم
- تراکم و نزدیکی بین حلهای بدست آمده و حلهای بهینه (اگر حلهای بهینه موجود باشد)
- پوشش، توزیع و پراکندگی حلهای غیرغالب
در این بخش، ابتدا مروری بر معروفترین این روشها میکنیم. برای بیان روشهای مرتبط با این بخش لازم است اصطلاحات زیر تعریف شوند:
: مجموعه حلهای غیرمغلوب نهایی الگوریتم
: مجموعه حلهای بهینه (یا بهترین جوابهای شناخته شده)
البته همیشه مجموعه حلهای بهینه برای مسائل چندهدفه موجود نمی باشد و گاهی تعیین آن غیرممکن است.
۲-۵-۱- فاصله نسلی[۱۰۸]
این روش اولین بار در سال ۲۰۰۰ توسط وَن وِلدهویزِن و لامونت[۱۰۹] پیشنهاد شدهاست. این معیار، فاصله بین و را اندازه گیری میکند. برای تعیین این مقیاس، لازم است که پژوهشگر، را دراختیار داشته باشد. نمایش ریاضی این معیار به صورت زیر است:
(۳۲.۲)
که در این رابطه، n، نشان دهنده تعداد بردارها در است و فاصله اقلیدسی بین هر عضو از مجموعه با نزدیکترین عضو در مجموعه میباشد. لذا هنگامیکه GD=0 است، و معادل هم هستند.
اما در مسائل بهینه سازی چندهدفه، همانند مسأله ما، همیشه مجموعه دراختیار نیست. در این مطالعه برای رفع این مشکل، روش تغییریافتهای از این الگو به کار رفتهاست. نحوه محاسبه عملکرد مجموعه جوابهای پارتو، بصورت رابطه زیر خواهد بود:
(۳۳.۲)
که فاصله اقلیدسی بین هر عضو از مجموعه از مبدأ مختصات بوده که از رابطه بدست میآید. در این رابطه منظور از ، مقدار kامین تابع هدف در بردار جواب پارتو iام است. بدیهی است که برای مجموعههای موردمقایسه، هرچقدر که این مقدار کوچکتر باشد، مطلوبیت آن مجموعه بیشتر خواهدبود.
۲-۵-۲- درجه توازن در رسیدن همزمان به اهداف
در اینجا، روش دیگری مبتنی بر مسافت پیشنهاد شدهاست. اما ابتدا لازم است مقدماتی راجع به کیفیت حلها بیان شود.
در شکل (۲-۱۰)، حلهای مناسب مسأله دوهدفی را نشان داده شدهاست و همچنان که مشاهده میشود، اگر حلی درامتداد یک محور باشد، مناسب نیست، زیرا آن حل تنها برای یک هدف مناسب بوده و برای هدف دیگر عملکرد مناسبی نداشتهاست، ولی حلهایی که با فلش نشان داده شدهاند، حلهای مناسبی هستند، زیرا که به یک توازن قابل قبول بین اهداف مسأله رسیدهاند. حال با این توصیف، در اینجا لازم است معیاری کمّی برای اندازه گیری رسیدن به این توازن در بین اهداف مختلف مسأله تعریف شود. به این منظور، در این مطالعه رابطه زیر پیشنهاد شدهاست:
(۳۴.۲)
هدف ۱
هدف ۲
جوابهای متوازن
شکل ۲-۱۰- نمایش حلهای مناسب
که در این رابطه است.
۲-۵-۳- مساحت زیر خط رگرسیون
روش مبتنی بر مساحت پوشش، روشی است که برای مقایسه مجموعههای پارتو، از مفهوم مساحت زیر نمودار برازش شده به هر مجموعه پارتو استفاده کرده و به منظور این برازش، از مفهوم رگرسیون خطی استفاده میکند. هدف در این روش، عبور دادن بهترین خط راست از مجموعه جوابهای غیرمغلوب، بااستفاده از روابط شیب و عرض از مبدأ است.
با توجه به شکل (۲-۱۱)، در این روش، هدف تعیین و مقایسه مثلثهای و AOB میباشد. همچنان که در شکل مشاهده میکنید، مساحت مثلث کوچکتر از مساحت مثلث AOB بوده و کاملاً مشخص است از لحاظ رسیدن به مقادیر بهتر در دو تابع هدف، الگوریتم متناظر با خط کارایی بهتری دارد.
بدیهی است هر چه این خط تخمینی به نقطه (۰.۰) نزدیکتر باشد، آنگاه محل تقاطع آن با محورها کوچکتر بوده و درنتیجه، مساحت مثلث زیر خط برازش شده کوچکتر خواهدبود که این امر، نشان دهنده بهتر بودن مجموعه حلهای غیرمغلوب متناظر آن خط است.
هدف ۱
هدف ۲
حلهای غیرمغلوب
[شنبه 1400-08-22] [ 02:11:00 ب.ظ ]
|