۱

۱

شکل ۱۴-۳ نمایش نهایی بخش دوم کروموزوم توزیع کننده کننده
شکل۱۳-۳ نمایش نهایی بخش اول کروموزوم تولید کننده
در ادامه گام های الگوریتم را مورد بررسی قرار میدهیم .شکل زیر برگرفته از تحقیق تیانری وانگ و همکاران[۱۳۳] گام های الگوریتم ژنتیک مرتب سازی نامغلوب را که برای حل مدل از آن استفاده شده است را نشان میدهد. در ادامه برای تشریح الگوریتم، قدم های الگوریتم مورد بررسی میگیرد.

شکل ۳-۱۵ قدم های الگوریتم NASG II [۲۷]
۳-۶-۳-۳٫ مقدار دهی اولیه^[۸۶] :
در این بخش اطلاعات اولیه که برای شروع الگوریتم نیاز میباشد شامل :
۳-۶-۳-۴٫ اندازه جمعیت اولیه^[۸۷] :
تعدادی از کروموزومها با هم یک جمعیت را تشکیل میدهند. اندازه جمعیت اولیه همان تعداد کروموزومها میباشد که در هر مرحله باید نگهداری شوند. در یک جمعیت، همه ی کروموزومها اندازه ی یکسان دارند و بصورت اندازه جمعیت نشان داده میشود . اگر اندازه جمعیت کوچک باشد . همگرایی الگوریتم سریعتر خواهد بود اما همگرایی زودرس ممکن است منجر به افتادن در دام یک بهینه ی محلی شود. الگوریتم NAGA-II با یک سری جوابها به عنوان جواب اولیه شروع به کار میکند. جمعیت اولیه شامل یکسری جوابهای مسأله است که به طور ابتکاری یا تصادفی تولید شده اند.
۳-۶-۳-۵٫ تولید نسل^[۸۸] :
تولید مثل معمولاً اولین عملی است که بر روی جمعیت اعمال میشود. در این روش یک سری کروموزوم از میان جمعیت انتخاب شده که در نهایت با عمل ادغام منجر به تولید فرزندان^[۸۹] میشوند. اندازهی تولید نسل بر اساس روش سعی و خطا و پیشنهاد پژوهشگران مقدارهای ۵۰ ، ۷۵ و ۱۵۰ پیشنهاد شده است که با تنظیم پارامتر میتوان مقدار مناسب را تعیین نمود. در این مساله به تعداد نسل اولیه جواب تصادفی تولید میشود و از استراتژی ردی جهت رد جواب های تصادفی تولید شده ی نشدنی وتولید جواب دیگر استفاده میشود . بدین معنی که تولید جواب های تصادفی تا جایی ادامه پیدا میکند تا به تعداد نسل اولیه مورد نیاز جواب تصادفی شدنی تولید شود . سپس از روش لبه بندی (مرتب سازی) نامغلوب سریع استفاده کرده و جواب ها را لبه بندی میکنیم.
۳-۶-۳-۶٫ روش مرتب سازی سریع نامغلوب^[۹۰]
مرتب کردن جمعیت بر اساس نامغلوبها با بهره گرفتن از مفهوم غلبه و مغلوب صورت میگیرد . به طور کلی برای مرتب کردن جمعیتی با اندازه N بر اساس سطوح نامغلوبها، هرجواب با تمام جوابهای دیگر موجود در جمعیت مقایسه میشود تا مشخص شود که آن جواب مغلوب میشود یا خیر. در نهایت یک تعداد حل وجود دارد که هیچ کدام غالب و مغلوب همدیگر نمیشوند لذا این جوابها، اولین مرز لبه^[۹۱] از مرزهای نامغلوب را تشکیل می دهند . برای تعیین جوابهای موجود درلبه های بعدی، جوابهای موجود در لبه اول به طور موقت نادیده گرفته میشود و فرایند فوق دوباره تکرار میشود. این فرایند تا زمانی که تمام جواب ها درون مرزهای نامغلوب قرار گیرند ادامه مییابد. در شکل زیر به صورت شماتیک این روش نشان داده شده است .
شکل ۱۶-۳ روش مرتب سازی نامغلوب سریع [۴]
۳-۶-۳-۷٫ فاصله ازدحام^[۹۲]:
یکی از معیارهایی که یک الگوریتم تکاملی در راه رسیدن به مرز بهینه پارتو همواره مدنظر قرار میدهد حفظ و گستردگی جوابها در مجموعه جوابهای بدست آمده میباشد. در واقع مرتب کردن غیرمغلوبها رویهای است در جهت رسیدن به جوابهای بهتر و مکانیزم تنوع هم درصدد تنوع گستردگی در این جوابها میباشد که در این الگوریتم این کار توسط فاصله ازدحام به این صورت انجام میشود.
برای تخمین تراکم اطراف یک جواب خاص در جمعیت، متوسط فاصله این جواب از هر دو جواب مجاور در دو سمت این جواب را براساس مقادیر اهداف محاسبه میکنیم. این مقدار را فاصله ازدحام مینامیم. برای محاسبه فاصله ازدحامی یک جواب خاص موجود دریک مرز، بزرگترین مستطیلی که آن جواب خاص درون مستطیل و دو جواب مجاور در دو سمت جواب، رأسهای مستطیل باشند را در نظر میگیریم و مجموع یک طول و یک عرض آن را به عنوان فاصله ازدحامی برای آن جواب خاص محاسبه میکنیم. الگوریتم زیر نحوه محاسبات مربوط به فاصله ازدحامی برای عضو دلخواه i م از یک مرزهای غیرمغلوب را نشان میدهد. برای محاسبه فاصله ازدحامی، ابتدا باید افراد جمعیت بر اساس مقدار هر تابع هدف به صورت صعودی مرتب شوند. سپس جوابهای موجود در ابتدا و انتهای هر مرز )جوابهای با بیشترین و کمترین مقدار تابع هدف( مقدار فاصله ازدحامی بینهایت به خود میگیرند .در زیر رویه محاسبه فاصله ازدحامی برای تمام جوابهای موجود در مرز نامغلوب f آورده شده است.
شکل ۳-۱۷ رویه محاسبه فاصله ازدحامی [۲۸]
در این الگوریتم مقدار تابع هدف m ام برایi امین عضو مجموعه nمیباشد. یک جواب با مقدار کمتری فاصله ازدحامی بیانکننده تراکم بیشتر جواب در اطراف آن جواب است. بنابراین مطلوب است برای مرحله بعد جوابهایی انتخاب شوند که در ناحیه با تراکم کمتر یا به عبارتی دارای فاصله ازدحامی بیشتر هستند چرا که با این کار تنوع و پراکندگی در جواب- های بدست آمده بیشتر میشود [۶۵].
شکل ۳-۱۸ محاسبه فاصله ازدحام [۲۸]
۳-۶-۳-۸٫ ارزیابی کروموزوم^[۹۳] :
در این مرحله باید کروموزوم های تولید شده ارزیابی شوند . برای این منظور تابع برازندگی^[۹۴] تعریف میشود . تابع برازندگی در این مساله همان مقادیر تابع هدف تعریف شده است.بدین معنی که برای ارزیابی کروموزوم ها مقادیر تابع هدف اول و دوم آنها مورد مقایسه قرار میگیرد .
۳-۶-۳-۹٫ استراتژی انتخاب^[۹۵] :
در این مساله برای استراتژی انتخاب از روش تورنومنت استفاده شده است . روش کار بدین صورت است که دو کروموزم به صورت تصادفی انتخاب شده ، کروموزوم با رتبه لبه کوچکتر از بین این دو انتخاب میشود و در صورت برابر بودن رتبه لبه، فاصله ازدحام کروموزوم ها بررسی میشود . این عمل دو بار تکرار میشود تا دو کروموزوم والدین برای عملگر تقاطع مهیا شود .
۳-۶-۳-۱۰٫ عملگر تقاطع^[۹۶] :
اندازهی احتمال عملگر تقاطع بر اساس روش سعی و خطا و پیشنهاد پژوهشگران مقدارهای ۰٫۸ ، ۰٫۸۵ و ۰٫۹ پیشنهاد شده است که با تنظیم پارامتر میتوان مقدار مناسب را تعیین نمود.عملگر تقاطع بر روی دو کروموزوم والد حاصل از عملگر انتخاب، با احتمال عمل میکند و با ترکیب دو والد فرزند جدیدی را به وجود میآورد.
تعداد کل جمعیت * نرخ تقاطع= تعداد اعمال تقاطع
عملگر تقاطع در این مساله بصورت زیر انجام میشود.
پس از استفاده از روش تورنومنت و انتخاب والدین جهت اعمال عملگر تقاطع به صورت زیر عمل میکنیم.
با احتمال ۲/۱ تولید کننده یا توزیع کننده انتخاب میشود .
یک نقطه از کروموزم به تصادف انتخاب میشود .
دو قسمت ایجاد شده توسط نقطه مشخص شده در کروموزوم با هم جابجا میشوند .
در شکل زیر این گام ها نمایش داده شده است.
فرض کنید تولید کننده انتخاب شد. نقطه تقاطع

۰

۱

۱

۰

فرزند جدید