مقاله با موضوع تولید جمعیت اولیه و الگوریتم ژنتیک

Change concepts with yellow paper airplane leading among white
[do_widget id=kl-erq-2]

(3-17)
(3-18)
(3-19)
(3-20)
(3-21)
در مدل فوق تابع هدف شماره (12-3) مجموع هزینه های در اختیار گرفتن تمام منابع برای اجرای فعالیت ها در کل دوره زمانی برنامه ریزی و برای تمامی حالت های اجرای را به علاوه هزینه تخطی از افق زمانبندی نهایی پروژه را کمینه می نماید. تابع هدف (13-3) کل زمان پروژه را کمینه می کند. محدودیت شماره (14-3) تضمین می کند که هر فعالیت در تمام دروه برنامه ریزی و در تمام حالت های اجرایی فقط یکبار اجرا شود. محدودیت شماره (15-3) روابط تقدم و تاخر از نوع پایان به آغاز با مقداری تاخیر/تعجیل بین فعالیت های پیش نیاز و پس نیاز را با در نظر گرفتن کل حالت های اجرایی و کل دوره برنامه ریزی پروژه ارضا می کند. محدودیت شماره (16-3) رابطه میان زمان پایان و زمان شروع یک فعالیت را با در نظر گرفتن تمام حالت های اجرایی در کل دوره برنامه ریزی را ارضا می کند. محدویت شماره (17-3) به کمک متغیر آزاد در علامت y کمک می کند تا حد بالای پروژه ارضا شود و در غیر اینصورت در تابع هدف جریمهای برای تخطی از حد بالای پروژه در نظر گرفته شده است) (y+. محدودیت های (18-3) الی (21-3) نوع متغیرهای تصمیم مساله را شرح می دهند.
مدل فوق علاوه بر کمینه کردن مجموع مربعات منابع مصرفی در کل دوره ها (سعی در تسطیح مقدار مصرف منابع) در حالت منابع نامحدود، سعی در کمینه کردن زمان کل پروژه نیز دارد. همچنین برای تخطی از زمانبندی فراتر از کل افق برنامه ریزی یک جریمه به پای تابع هدف گذاشته می شود.
الگوریتم ژنتیکNSGA-II
این الگوریتم با اضافه شدن دو عملگر ضروری به الگوریتم ژنتیک تک هدفه معمولی، به یک الگوریتم چند هدفه تبدیل شده است که بجای یافتن بهترین جواب، دسته ای از بهترین جوابها را می دهد که با نام پارتو فرانت شناخته می شوند. این دو عملگر عبارتند از:
عملگری که یک معیار برتری (رتبه) براساس مرتب سازی نامغلوب به اعضای جمعیت اختصاص می دهد.
عملگری که تنوع جواب را در میان جوابهای با رتبه برابر حفظ نگه میدارد.
طرح پایه
قبل از اینکه الگوریتم ژنتیک اجرا گردد، ما یک روند پیش پردازش (معرفی شده توسط
Sprecher et al.1997)، بمنظور تطبیق داده های مسئله بامدل و کاهش فضای جستجو انجام می دهیم. بعد از روند پیش پردازش، الگوریتم چند هدفه NSGA-II اجرا شده که مراحل آن به صورت زیر می باشد:
تولید جمعیت اولیه (Pt)با N کروموزوم(جمعیت اولیه به صورت تصادفی انتخاب شده به صورتی که هیچیک از کروموزوم ها تکراری نباشند.)
تولید جمعیت ثانویه ای(Qt)با Nکروموزوم با اعمال تزویج و جهش برN کروموزوم اولیه (Pt).
یافتن کروموزوم های بیرونی و نزدیکتر به مبدا از جمعیت 2N کروموزوم (Pt+Qt)(یافتن نقاط غیرپست با استفاده از الگوریتم مرتب سازی بر اساس نقاط غیر پست )
انتخاب N عضو غیرپست (Pt+1) از مجموعه نقاط غیر پست با 2N عضو از جبهه پارتو (Pt+Qt). (با استفاده از فضای مختصاتی زمان-هزینه-تسطیح منبع، تعداد N کروموزومی که نزدیک ترین فاصله نسبت به مبدا مختصات را دارا می باشند، انتخاب می گردد.)
اعمال انتخاب، آمیزش و جهش بر نسل قدیم (Pt+1) و تولید نسل جدید با اندازه N کروموزوم (Qt+1).
در ادامه برای توضیح واضحتر مولفههای الگوریتم ژنتیک، شبکه فعالیتهای یک پروژه ساده با 6 فعالیت مانند شکل (2-3) را در نظر می گیریم.

شکل 2-3- پروژه نمونه