۳-۴-۱- مقایسه روش ها و الگوریتم های ارائه شده
Fleming و Fonseca الگوریتمی با نام MOGA [۱۰۴] (۱۹۹۳) ارائه کردند [۱۷] که در آن رتبه هر عضو بر اساس تعداد اعضایی که آن را مغلوب کردهاند تعیین میشود. با بهره گرفتن از این روش علاوه بر غلبه پارتو فشردگی پاسخ ها در اطراف هر پاسخ نیز در رتبه بندی دخالت دارد و در نواحی فشرده رتبه بدتری به پاسخ ها اختصاص داده میشود. بدین ترتیب سعی شده تا پخش یکنواخت پاسخ ها در طول جبهه بهینه حفظ شود.
روش دیگری که در برخی الگوریتم ها از جمله SPEA [۱۰۵] (۱۹۹۸) و SPEA2 (2001) برای رتبه بندی به کار گرفته شده است[۱۷]. استفاده از پارامتری بنام ضریب قدرت است که برای هر عضو برابر تعداد اعضایی است که مغلوب آن شدهاند. رتبه شایستگی هر عضو برابر جمع ضرایب قدرت اعضایی است که بر آن غلبه نمودهاند. این روش نیز فشردگی پاسخ ها را در رتبه بندی منظور می کند و هنگامی که فشردگی پاسخ ها بیش تر است رتبه بندی بدتری به آن ها میدهد. ضعف دو روش گفته شده در آن است که هنگامی که تعداد پاسخ هایی که نسبت به هم بیتفاوت اند زیاد باشد کارایی خوبی ندارند.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
روش قلمرو سازی و اشتراک برازندگی روش دیگری است که در الگوریتم های NSGA [۱۰۶] (۱۹۹۴)، PAES [۱۰۷] (۱۹۹۹) و (۱۹۹۸)SPEA ، NPGA [۱۰۸] (۱۹۹۴) از آن استفاده شده است. در این روش پارامتری با عنوان شعاع قلمرو تعیین میگردد. اعضای با فاصله کم تر از شعاع قلمرو مجاور یک دیگر محسوب شده و از رتبه شایستگی یک دیگر میکاهند. لذا پاسخ هایی که در نواحی پر ازدحامتر حضور دارند احتمال کم تری برای انتخاب دارند. بدین ترتیب میتوان از پخش یکنواخت پاسخ ها در طول جبهه بهینه اطمینان بیش تری حاصل نمود.
ضعف روش قلمروسازی و اشتراک برای زندگی در وابستگی آن به تعیین درست شعاع قلمرو است. هم چنین پیچیدگی محاسباتی آن به دلیل نیاز به محاسبه فاصله همه پاسخ ها از یک دیگر بالا است. الگوریتم NPGA برای کاستن از پیچیدگی محاسبات مقایسه فاصله را به بخشی از پاسخ ها محدود کرده است اما این خود به دلیل عدم مقایسه همه پاسخ ها یک ایراد است.
روش تخمین چگالی روشی است که به دلیل نداشتن ضعف ها و ایرادات روش های دیگر بر آن ها برتری دارد. این روش به کمک تخمین چگالی پاسخ ها در کنار درجه نامغلوبی آن ها که پیش از این شرح داده شد برای تعیین رتبه شایستگی پاسخ ها به کار میرود. این روش که در الگوریتم های SPEA2 ، NSGAII از آن استفاده شده است بدین صورت است که ابتدا پارامتری به نام اندیس فاصله idistance برای هر پاسخ در هر یک از اهداف محاسبه میشود. اندیس فاصله عبارت است از نسبت تفاضل هدف در پاسخ هایی که پاسخ مورد نظر را احاطه کردهاند به تفاضل بیشینه و کمینه همان هدف. اندیس فاصله برای هدف kام از پاسخ jام به صورت زیر می باشد:
(۳-۲۴)
در نهایت مقیاس تخمین چگالی از جمع اندیس های فاصله برای هر یک از پاسخ ها به دست میآید. اندیس فاصله برای نقاط مرزی پاسخ های متناظر بیشینه و کمینه هدف بینهایت است. زیرا لازم است این نقاط جهت افزایش گستره جستجو در جمعیت نسل بعد حضور داشته باشند. مقیاس چگالی بزرگ تر به معنی تراکم کم تر برای یک پاسخ بوده و طبیعتاً به آن رتبه شایستگی بهتری اختصاص خواهد یافت. شکل ۳-۲۰ به طور شماتیک اندیس فاصله را در یک بهینه سازی دو هدفه به خوبی نشان میدهد.
شکل ۳-۲۰: تخمین چگالی پاسخ ها با بهره گرفتن از اندیس فاصله[۱۷]
۳-۴-۲- الگوریتم ژنتیک مرتب سازی پاسخ های نامغلوب بهبود یافته NSGAII
در این مطالعه از الگوریتم NSGAII برای بهینه سازی چند هدفه استفاده شده است.
الگوریتم NSGAII بهبود یافته الگوریتم NSGA که پیش تر توسط Deb و Srinivas ارائه شده بود. این الگوریتم توسط Deb و همکاران با رفع ایرادات الگوریتم NSGA ارائه گردید[۱۷]. در الگوریتم NSGA پاسخ ها براساس مفهوم غلبه پارتو با روش مرتبسازی پاسخ های نامغلوب به لایههای نامغلوب دسته بندی می شوند. وضعیت لایهها در جمعیت P به شکل زیر خواهد بود.
(۳-۲۵)
به بیان دیگر جمعیت P به لایه دسته بندی شده است که اشتراک آنها دو به دو با یک دیگر تهی بوده و اجتماع شان برابر کل جمعیت است. برازندگی یا رتبه شایستگی مجازی هر عضو برابر شماره لایهای است که در آن قرار گرفته است. انتخاب براساس برازندگی مجازی و با بهره گرفتن از روش مسابقهای با اندازه مسابقه دو انجام میپذیرد. بنابراین اعضای لایه نخست که برازندگی مجازی ۱ دارند بیش ترین شانس حضور در نسل بعدی را خواهند داشت. این الگوریتم برای خفظ توزیع یکنواخت پاسخ ها در طول جبهه بهینه از روش قلمروسازی و اشتراک برازندگی استفاده میکند. شکل ۳-۲۱ نمودار گردش کار این الگوریتم را نشان می دهد.
شکل ۳-۲۱: نمودار گردش کار الگوریتم NSGA [17]
این الگوریتم در مقایسه با الگوریتم های دیگر نتایج خوبی را نشان داده است اما ایراداتی نیز دارد که مهم ترین آنها عبارت است از:
پیچیدگی محاسباتی بالا : پیچیدگی محاسباتی این الگوریتم بدلیل مقایسه همه جواب ها در فرایند لایه بندی بالا است. اگر M هدف و N عضو در هر جمعیت وجود داشته باشد تعداد مقایسه انجام گرفته در این الگوریتم از مرتبه است. هم چنین روش قلمروسازی و اشتراک برازندگی نیز پیچیدگی محاسباتی بالایی دارد.
به دلیل عدم نگهداری مجموعه نخبه در الگوریتم NSGA پاسخ های نامغلوب ممکن است طی فرایند تکامل و در اثر عملکرد عملگرهای ژنتیکی از جمعیت خارج شوند که این امر موجب کاهش کارایی الگوریتم میشود.
مشکل وابستگی الگوریتم به تعیین درست شعاع قلمرو به دلیل استفاده از روش قلمروسازی و اشتراک برازندگی برای توزیع مطلوب پاسخ ها در طول جبهه بهینه در این الگوریتم وجود دارد.
در الگوریتم NSGAII از راهکارهای زیر برای رفع ایرادات فوق استفاده شده است:
در الگوریتم NSGAII برای لایه بندی پاسخ ها روش پیشنهادی با عنوان مرتبسازی سریع پاسخ های نامغلوب به کار گرفته شده است که پیچیدگی محاسبات را بدون از دست رفتن کیفیت لایهبندی کاهش میدهد.
در الگوریتم NSGAII مجموعه نخبه شامل پاسخ های نامغلوب حفظ
می گردد و بدین ترتیب به کارایی و همگرایی سریع تر الگوریتم کمک می شود.
الگوریتم NSGAII از روش تخمین چگالی و عملگری بنام عملگر مقایسه ازدحام[۱۰۹] برای حفظ توزیع مطلوب پاسخ ها در طول جبهه بهینه استفاده میکند که علاوه برای عدم وابستگی به پارامترهای تعیین شده توسط کاربر سرعت اجرا را نیز افزایش میدهد.
۳-۴-۲-۱- روش مرتب سازی سریع پاسخ های نامغلوب
در این روش ابتدا برای هر یک از پاسخ ها دو پارامتر تعیین می گردد:
: شماره غلبه که برابر است با تعداد اعضایی که عضو مورد نظر را مغلوب نمودهاند.
: مجموعه اعضایی که عضو مورد نظر آن ها را مغلوب می کند.
بدیهی است پاسخ هایی که برابر۰ دارند مجموعه نامغلوب جمعیت موجود را تشکیل
می دهند و در لایه ۱ قرار میگیرند. لایه ۱ شامل شایسته ترین اعضا بوده و جبهه بهینه را ایجاد خواهد نمود. برای یافتن اعضای لایه ۲ یک شماره از شماره غلبه پاسخ هایی که جزء مجموعه مغلوب اعضای لایه ۱ باشند کم میشود. پاسخ هایی که پس از کسر یک عدد شماره غلبهشان صفر گردد مجموعه اعضای لایه دوم را تشکیل می دهند. به همین ترتیب یک شماره از شماره غلبه پاسخ های مغلوب اعضای آخرین لایه مشخص شده کسر می گردد و پاسخ هایی که شماره غلبه شان صفر گردد لایه بعدی را تشکیل می دهند و این روند تا لایه بندی کلیه اعضای جمعیت ادامه مییابد. در این روش برای مساله M هدفه که N عضو در هر جمعیت داشته باشد تعداد مقایسههای لازم برای لایه بندی کل جمعیت از مرتبه است که بسیار سریع تر از الگوریتم NSGA است.
۳-۴-۲-۲- عملگر مقایسه ازدحام
این عملگر که برای حفظ پخش یکنواخت پاسخ ها در تمام طول جبهه بهینه در الگوریتم NSGAII بکار میرود به صورت زیر تعریف می شود.
(۳-۲۶)
در تعریف این رابطه a و b دو عضو از یک جمعیت و rank رتبه عضو و برابر شماره لایه آن و مقیاس چگالی عضو است. پیش از این مقیاس چگالی به صورت حاصل جمع اندیس های فاصله تعریف گردید. در صورتیکه M هدف وجود داشته باشد مقیاس فاصله عضو jام به صورت زیر است:
(۳-۲۷)
با توجه به رابطه (۳-۲۶) عملگر مقایسه ازدحام از میان دو عضو حاضر در جمعیت عضوی را بر میگزیند که شماره لایه کوچک تری داشته باشد. چنان چه هر دو عضو در یک لایه باشند عضوی که مقیاس چگالی بزرگتری داشته باشد برگزیده می شود.
۳-۴-۲-۳- استراتژی برخورد با قیود
استراتژی های گوناگونی برای برخورد با قیود در الگوریتم های ژنتیکی اتخاذ میشود. بطور کلی اعمال قیود و محدودیت ها در الگوریتم های ژنتیکی بسیار ساده است. در الگوریتم NSGAII با بهره گرفتن از مفهومی به نام غلبه محدودیتی قیود مساله در بهینهسازی چند هدفه اعمال می شوند. بر این اساس که قیود مساله در مساله بهینه سازی چند هدفه ناحیه شدنی را در فضای هدف مشخص میکنند برای هر دو عضو در جمعیت ممکن است یکی از سه حالت زیر به وجود آید:
هر دو پاسخ در ناحیه شدنی باشند.
یکی از پاسخ ها در ناحیه شدنی و دیگر خارج از ناحیه شدنی باشند.
هر دو پاسخ خارج از ناحیه شدنی باشند.
با توجه به حالت های فوق غلبه محدودیتی به صورت زیر تعریف می شود:
پاسخ A بر پاسخ B غلبه محدودیتی دارد هرگاه یکی از حالت های زیر برقرار باشد:
پاسخ A شدنی و B ناشدنی باشد.
پاسخ A و B هر دو ناشدنی باشند و A نسبت به B انحراف کم تری از قیود داشته باشد.
پاسخ A و B هر دو شدنی باشند و A بر B غلبه پارتو داشته باشد.
با به کارگیری عملگر غلبه محدودیتی الگوریتم طی تکامل نسل ها پاسخ ها را به سمت ناحیه شدنی در فضای هدف و پاسخ های شدنی به سمت جبهه بهینه پارتو هدایت میشوند.
۳-۴-۲-۴- روند اجرای الگوریتم NSGAII
حلقه اصلی الگوریتم NSGA که برای مطالعه حاضر نوشته شده است مراحل زیر را یک به یک اجرا می کند:
از آن جا که در الگوریتم NSGAII از نمایش اعداد حقیقی برای رمزنگاری کروموزوم ها استفاده می شود ابتدا می بایست جمعیت نخستین تولید گردد. جمعیت نخستین یک جمعیت کاملاً تصادفی است که به صورت ماتریسی از اعداد حقیقی ما بین یا برابر ۰ و ۱ تولید میگردد. تعداد ستون های ماتریس به تعداد معین شده برای جمعیت N و ستون های آن به تعداد متغیرهای تصمیم خواهد بود. فرض میکنیم این جمعیت، مربوط به نسل t باشد.
پس از رمزگشایی پاسخ های اعضای جمعیت مقادیر توابع هدف و توابع قیدی محاسبه و با بهره گرفتن از غلبه محدودیتی براساس غلبه پارتو و روش سریع مرتب سازی پاسخ های نامغلوب لایهبندی میشوند و برازندگی مجازی برابر با شماره لایه هر عضو به آن اختصاص مییابد.
با بهره گرفتن از روش انتخاب مسابقهای با اندازه مسابقه ۲ و براساس برازندگی مجازی اختصاص یافته تعداد N عضو در مجموعه کروموزوم های والد[۱۱۰] قرار داده میشوند. ممکن است بین اعضای این مجموعه کروموزوم های تکراری حضور داشته باشند زیرا در هر بار مسابقه دو عضو برای مقایسه به صورت تصادفی و بدون هیچ پیش شرطی از میان همه اعضای جمعیت برگزیده میشود.
از N کروموزوم والد با بهره گرفتن از عملگرهای ژنتیکی پیوند و جهش N فرزند تولید میگردد.
فرزندان با جمعیت نسل موجود ترکیب شده و جمعیت میانه را با اندازه ۲N تشکیل می دهند.
جمعیت میانه به کمک فرایند مرتب سازی سریع پاسخ های نامغلوب لایهبندی میشوند.
اعضای لایهها به ترتیب از لایه ۱ به جمعیت نسل بعد منتقل میشوند تا زمانی که در صورت اضافه کردن اعضای یک لایه به جمعیت سبب شود که اندازه جمعیت از N بزرگ تر شود. در این زمان اعضای لایه مذکور با بهره گرفتن از عملگر مقایسه ازدحام به صورت نزولی مرتب می شوند و بهترین اعضای موجود در آن به ترتیب به جمعیت منتقل میشوند تا اندازه آن به N برسد.
جمعیت نسل جدید برای شروع دوباره فرایند تکامل آماده است و مراحل گفته شده از مرحله ۲ برای آن تکرار میگردد تا زمانی که معیار توقف که در این الگوریتم تعداد از پیش تعیین شده نسل ها است سبب توقف الگوریتم گردد.
نکته قابل ذکر در مورد الگوریتم فوق آن است که در مرحله انتخاب اولیاء انتخاب براساس عملگر مقایسه انجام میپذیرد تا کروموزوم های با درجه نامغلوبی بهتر که در نواحی کم ازدحامتری قرار دارند فرزندان بیش تری تولید نمایند. بدین ترتیب علاوه بر همگرایی ، پاسخ ها به سمت جبهه بهینه پارتو به بخش یکنواخت و مطلوب پاسخ ها در طول جبهه نیز کمک می شود.
[سه شنبه 1401-04-14] [ 02:28:00 ق.ظ ]
|