ی ماشین
برای مثال در کروموزوم شکل 3 ژن چهارم 1،2،1 است که نشان می دهد عملیات دوم از کار اول در ماشین شماره 1 انجام شود و چون فیلد نگهداری این ماشین برابر 1 است این ماشین پس از پردازش این عمل برای مدت زمان تعیین شده به مرحله نگهداری می رود و نمی تواند عملیات جدیدش را پردازش نماید.
شکل 3-5 نمودار گانت شکل 3-4 را نشان می دهد.
شکل ‏35: نمودار گانت شکل 3-4
ایجاد جمعیت اولیه
الگوریتم پیشنهادی از ویژگی چند جمعیتی در الگوریتم ژنتیک برخوردار است که به صورت موازی، هر جمعیت در حال پردازش کروموزوم های خود برای رشد جمعیتش می‌باشد. در این الگوریتم از 3 جمعیت مجزا استفاده شده است. ابتدا 2 جمعیت به صورت کاملا تصادفی کروموزومهای خود را تولید و کار خود را شروع می کنند. سپس جمعیت سوم برای شروع پردازشهای خود، 50% بهترین کروموزوم های دو جمعیت فوق را دریافت می‌کند و همزمان کار خود را برای رشد جمعیت خود و ایجاد نسل بعد شروع می کند. در این هنگام جمعیت سوم نیز 5% بهترین کروموزوم تولید شده در هر نسل خود را به دو جمعیت دیگر می‌دهد. با این کار ما کروموزومهای نخبه هر جمعیت را به یکدیگر پاس میدهیم تا هر سه جمعیت به صورت یکپارچه کروموزومهای بهینه را در اختیار داشته باشند و به اتفاق هم به سمت جواب بهینه حرکت کنند.
شکل 3-6 این عملکرد را به خوبی نشان می‌دهد.
شکل ‏36: ایجاد جمعیت اولیه با استفاده از ویژگی چند جمعیتی
در نظر گرفتن چند جمعیت باعث پخش شدن جواب ها در مجموعه جواب در مساله میگردد و مسئله در الگوریتم ژنتیک را در جهت پوشش کل مسئله می گردد.
کد مربوط به جمعیت اولیه:
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);
}
}
شایستگی
شایستگی یک کروموزوم برابر است با ماکزیمم زمان اتمام پردازش104 عملیات وابسته به ماشین متناظر در بین زمانبندی ماشین های موجود. کدینگ حل این مسئله برای محسابه میزان شایستگی در زیر آمده است.
Fit=Max(S(M_0 ),S(M_1 ),…(S(M_k))
O_(i,j) i=Number of Job &&
j= Number of machine
T_(i,k) Time Process operation k of Job i
M_k=O_(i,k)
Proceesing operation k of Job i on Machine k
S(M_k)=〖TA〗_(m(k))+ 〖TM〗_(m(k))+ 〖GAP〗_(m(k))
Proceesing operation k of Job i on Machine k
〖TA〗_m(k) =∑_(i=1)^m▒T_(i,k)
Proceesing Activating time Machine k
〖TM〗_(m(k))=(∑_(i=0)^m▒〖TPMG_i 〗)- TPMG_(m-1)
〖TM〗_(m(k))=Time Maintenance Machine k
〖GAP〗_(m(k))=T-(〖TA〗_m(k) +〖TM〗_m(k) )
انتخاب
با توجه به نظریه داروین و برای تولید نسل جدید از جمعیت فعلی ، باید کروموزوم هایی از این جمعیت را برای ادغام و تکثیر انتخاب کنیم که هنگام اجرای عمل انتخاب، کروموزوم هایی که از بهینگی بیشتری برخوردارند ( بهینگی هر کروموزوم با استفاده از تابع بهینگی محاسبه می شود ) شانس بیشتری برای انتخاب دارا باشند. کروموزوم های انتخاب شده برای ادغام با دیگر کروموزوم ها به منظور تولید نسل جدید در محل دیگری جمع آوری می شوند. عمل ادغام و تولید کروموزوم های جدید در این محل که آن را حوضچه ژنتیک می نامیم انجام می پذیرد. عملگر انتخاب در الگوریتم پیشنهادی، روش تصادفی دو نقطه ای است. به این صورت که جمعیت اولیه را به دو قسمت تقسیم کرده و از هر قسمت یک ‌کروموزوم به صورت تصادفی برای انجام تبادل انتخاب می شوند.
عملگر تبادل
در الگوریتم پیشنهادی هر کدام از جمعیت ها دارای عملگر تبادل مخصوص به خود است تا تنوع کروموزوم ها در هر جمعیت بیشتر باشد. عملگرهای تبادل مورد استفاده در این الگوریتم شامل:
عملگر تبادل دو نقطه ای
عملگر تبادل تک نقطه ای
عملگر تبادل چند نقطه ای
عملگر تبادل دو نقطه ای
در عملگر تبادل دو نقطه ای پس از انتخاب دو کروموزوم به عنوان والد دو عدد بصورت تصادفی به عنوان اندیس ژن ها تولید می شوند. سپس ژن های مربوط به سمت چپ اندیس اول از والد اول در فرزند قرار می گیرد و در والد دوم ژن های مربوطه حذف می شوند. سپس ژن های مربوط به سمت راست والد دوم در فرزند قرار می گیرند و در آخر ژن های باقیمانده نیز در کروموزوم فرزند قرار داده می شود.
شکل 3-7 عملگر تبادل دو نقطه ای را نشان می دهد.
کد مربوط به تبادل دو نقطه ای:
public Chromosome Cross2Point(Chromosome tmp)
{
Chromosome NewChro = new Chromosome();
Random rnd11 = new Random(c++);
Random rnd22 = new Random(c++);
int a = rnd11.Next(0, this.chro.Count);
int b = rnd22.Next(0, this.chro.Count);
int ss;
while (a == b)
{
b = rnd22.Next(0, this.chro.Count – 1);
}
if (a b)
{
ss = a;
a = b;
b = ss;
}
عملگر تبادل تک نقطه ای
در این روش انتخاب دو والد جهت انجام تبادل مانند روش 2 نقطه ای است ولی در این روش یک عدد به عنوان اندیس ژن انتخاب می‌شود. سپس ژن های مربوط در سمت چپ والد اول در فرزند کپی می‌شود و در والد دوم این ژن ها حذف می‌شوند. در ادامه ژن های مربوط به سمت راست والد دوم در فرزند قرار داده می شود و در انتها اگر ژن هایی باقی ماندند در کروموزوم فرزند قرار می‌گیرند.
شکل 3-8 عملگر تبادل تک نقطه ای را نشان می‌دهد.
شکل ‏38: عملگر تبادل تک نقطه ای
کد مربوط به تبادل تک نقطه ای:
public Chromosome Cross1Point(Chromosome tmp)
{
Random rand = new Random(c++);
Chromosome newChro = new Chromosome();
Chromosome temp = new Chromosome(tmp);
int x = rand.Next(2, this.chro.Count – 1);
for (int i = 0; i x; i++)
{
newChro.Chro.Add(new Gene(((Gene)this.chro[i])));
for (int j = 0; j temp.chro.Count; j++)
{
if (((Gene)temp.chro[j]).Job == ((Gene)newChro.chro[i]).Job && ((Gene)temp.chro[j]).Operation == ((Gene)newChro.chro[i]).Operation)
{
temp.chro.RemoveAt(j);
}
}
}
for (int k = 0; k temp.chro.Count; k++)
{
newChro.chro.Add(new Gene(((Gene)temp.chro[k])));
}
newChro.Fit();
return newChro;
}
عملگر تبادل چند نقطه ای
در این روش به جای انتخاب یک یا دو نقطه، چند نقطه به عنوان اندیس ژن ها تولید می‌شوند. شکل زیر عملگر تبادل چند نقطه‌ای را نشان می‌دهد.
شکل ‏39: عملگر تبادل چند نقطه ای
کد مربوط به تبادل چند نقطه ای:
public Chromosome CrossMultiPoint(Chromosome tmp)
{
Random rnd = new Random(c++);
Chromosome parent1 = new Chromosome(this);
Chromosome parent2 = new Chromosome(tmp);
Chromosome newChro = new Chromosome();
int a = rnd.Next(1, qtyMachine * qtyJob / 4);
int b = rnd.Next(qtyMachine * qtyJob / 4, qtyMachine * qtyJob / 3);
int d = rnd.Next(qtyMachine * qtyJob / 3, qtyMachine * qtyJob / 2);
int e = rnd.Next(qtyMachine * qtyJob / 2, qtyMachine * qtyJob);
for (int i = 0; i a; i++)
{
newChro.chro.Add(new Gene((Gene)parent1.chro[i]));
}
for (int j = a; j b; j++)
{
bool conflict = false;
for (int k = 0; k newChro.chro.Count; k++)
{
if (((Gene)parent2.chro[j]).Job == ((Gene)newChro.chro[k]).Job && ((Gene)parent2.chro[j]).Operation == ((Gene)newChro.chro[k]).Operation)
{
conflict = true;
break;
}
}
if (!conflict)
{
newChro.chro.Add(new Gene((Gene)parent2.chro[j]));
}
}
for (int j = b; j d; j++)
{
bool conflict = false;
for (int k = 0; k newChro.chro.Count; k++)
{
if (((Gene)parent1.chro[j]).Job == ((Gene)newChro.chro[k]).Job && ((Gene)parent1.chro[j]).Operation == ((Gene)newChro.chro[k]).Operation)
{
conflict = true;
break;
}
}
if (!conflict)
{
newChro.chro.Add(new Gene((Gene)parent1.chro[j]));
}
}
for (int j = d; j e; j++)
{
bool conflict = false;
for (int k = 0; k newChro.chro.Count; k++)
{
if (((Gene)parent2.chro[j]).Job == ((Gene)newChro.chro[k]).Job && ((Gene)parent2.chro[j]).Operation == ((Gene)newChro.chro[k]).Operation)
{
conflict = true;
break;
}
}
if (!conflict)
{
newChro.chro.Add(new Gene((Gene)parent2.chro[j]));
}
}
for (int i = 0; i parent1.chro.Count; i++)
{
bool conflict = false;
for (int j = 0; j newChro.chro.Count; j++)
{
if (((Gene)newChro.chro[j]).Job == ((Gene)parent1.chro[i]).Job && ((Gene)newChro.chro[j]).Operation == ((Gene)parent1.chro[i]).Operation)
{
conflict = true;
break;
}
}
if (conflict)
{
parent1.chro.RemoveAt(i);
i = -1;
}
else
{
newChro.chro.Add(new Gene((Gene)parent1.chro[i]));
}

این مطلب رو هم توصیه می کنم بخونین:   تحقیق دربارهحمل و نقل، چند محصوله
دسته‌ها: No category

دیدگاهتان را بنویسید