۳،۳،۰

۱،۱،۱

۲،۲،۰

۳،۱،۱

۲،۱،۰

۱،۲،۱

۳،۲،۰

۲،۳،۰

۱،۳،۰

شکل ‏۳‑۴: یک کروموزوم نمونه با در نظر گرفتن نگهداری ماشین
برای مثال در کروموزوم شکل ۳ ژن چهارم ۱،۲،۱ است که نشان می دهد عملیات دوم از کار اول در ماشین شماره ۱ انجام شود و چون فیلد نگهداری این ماشین برابر ۱ است این ماشین پس از پردازش این عمل برای مدت زمان تعیین شده به مرحله نگهداری می رود و نمی تواند عملیات جدیدش را پردازش نماید.

( اینجا فقط تکه ای از متن پایان نامه درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

شکل ۳-۵ نمودار گانت شکل ۳-۴ را نشان می دهد.
شکل ‏۳‑۵: نمودار گانت شکل ۳-۴
ایجاد جمعیت اولیه
الگوریتم پیشنهادی از ویژگی چند جمعیتی در الگوریتم ژنتیک برخوردار است که به صورت موازی، هر جمعیت در حال پردازش کروموزوم های خود برای رشد جمعیتش می‌باشد. در این الگوریتم از ۳ جمعیت مجزا استفاده شده است. ابتدا ۲ جمعیت به صورت کاملا تصادفی کروموزوم­های خود را تولید و کار خود را شروع می کنند. سپس جمعیت سوم برای شروع پردازش­های خود، ۵۰% بهترین کروموزوم های دو جمعیت فوق را دریافت می‌کند و همزمان کار خود را برای رشد جمعیت خود و ایجاد نسل بعد شروع می کند. در این هنگام جمعیت سوم نیز ۵% بهترین کروموزوم تولید شده در هر نسل خود را به دو جمعیت دیگر می‌دهد. با این کار ما کروموزوم­های نخبه هر جمعیت را به یکدیگر پاس میدهیم تا هر سه جمعیت به صورت یکپارچه کروموزوم­های بهینه را در اختیار داشته باشند و به اتفاق هم به سمت جواب بهینه حرکت کنند.
شکل ۳-۶ این عملکرد را به خوبی نشان می‌دهد.
شکل ‏۳‑۶: ایجاد جمعیت اولیه با بهره گرفتن از ویژگی چند جمعیتی
در نظر گرفتن چند جمعیت باعث پخش شدن جواب ها در مجموعه جواب در مساله می­گردد و مسئله در الگوریتم ژنتیک را در جهت پوشش کل مسئله می گردد.
کد مربوط به جمعیت اولیه:
if (!stateLoad)
{
int x = job * machine;
t = new ArrayList(x);
Random r = new Random(cc++);
for (int i = 0; i <= x - 1; i++)
{
int b = r.Next(10, 80);
t.Add(b);
}
}
شایستگی
شایستگی یک کروموزوم برابر است با ماکزیمم زمان اتمام پردازش^[۱۰۴] عملیات وابسته به ماشین متناظر در بین زمانبندی ماشین های موجود. کدینگ حل این مسئله برای محسابه میزان شایستگی در زیر آمده است.

• )

انتخاب
با توجه به نظریه داروین و برای تولید نسل جدید از جمعیت فعلی ، باید کروموزوم هایی از این جمعیت را برای ادغام و تکثیر انتخاب کنیم که هنگام اجرای عمل انتخاب، کروموزوم هایی که از بهینگی بیشتری برخوردارند ( بهینگی هر کروموزوم با بهره گرفتن از تابع بهینگی محاسبه می شود ) شانس بیشتری برای انتخاب دارا باشند. کروموزوم های انتخاب شده برای ادغام با دیگر کروموزوم ها به منظور تولید نسل جدید در محل دیگری جمع آوری می شوند. عمل ادغام و تولید کروموزوم های جدید در این محل که آن را حوضچه ژنتیک می نامیم انجام می پذیرد. عملگر انتخاب در الگوریتم پیشنهادی، روش تصادفی دو نقطه ای است. به این صورت که جمعیت اولیه را به دو قسمت تقسیم کرده و از هر قسمت یک ‌کروموزوم به صورت تصادفی برای انجام تبادل انتخاب می شوند.
عملگر تبادل
در الگوریتم پیشنهادی هر کدام از جمعیت ها دارای عملگر تبادل مخصوص به خود است تا تنوع کروموزوم ها در هر جمعیت بیشتر باشد. عملگرهای تبادل مورد استفاده در این الگوریتم شامل:

• عملگر تبادل دو نقطه ای

• عملگر تبادل تک نقطه ای

• عملگر تبادل چند نقطه ای

عملگر تبادل دو نقطه ای
در عملگر تبادل دو نقطه ای پس از انتخاب دو کروموزوم به عنوان والد دو عدد بصورت تصادفی به عنوان اندیس ژن ها تولید می شوند. سپس ژن های مربوط به سمت چپ اندیس اول از والد اول در فرزند قرار می گیرد و در والد دوم ژن های مربوطه حذف می شوند. سپس ژن های مربوط به سمت راست والد دوم در فرزند قرار می گیرند و در آخر ژن های باقیمانده نیز در کروموزوم فرزند قرار داده می شود.
شکل ۳-۷ عملگر تبادل دو نقطه ای را نشان می دهد.
شکل ‏۳‑۷: عملگر تبادل دو نقطه ای
کد مربوط به تبادل دو نقطه ای:
public Chromosome Cross2Point(Chromosome tmp)
{