الگوریتمهای ژنتیک (با نماد اختصاری GA) تکنیک جستجویی در علم رایانه برای یافتن راهحل تقریبی برای بهینهسازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیستشناسی فرگشتی مانند وراثت و جهش استفاده میکند. این الگوریتم برای اولین بار توسط جان هنری هالند معرفی شد.
مسئله چند وزیر یک معمای شطرنجی و ریاضیاتی است که بر اساس آن باید n وزیر شطرنج در یک صفحه n×n شطرنج بهگونهای قرار داده شوند که هیچیک زیر ضرب دیگری نباشند. با توجه به اینکه وزیر بهصورت افقی، عمودی و اُریب حرکت میکند، باید هر وزیر را در طول، عرض و قطر متفاوتی قرار داد .
در این آموزش با استفاده از الگوریتم ژنتیک و زبان برنامه نویسی سی شارپ به حل مساله خواهیم پرداخت.
ابتدا یک پروژه از نوع ویندوزی ایجاد میکنیم . و سپس متغیر و اشیای اولیه مساله را بصورت زیر ایجاد میکنیم.
const int n = 8;
Panel[,] pnl = new Panel[n, n];
const int p = 100;
int[,] firstGen = new int[p, n+1];
int[,] secondGen = new int[p, n+1];
در قطعه کد بالا متغیرهایی برای ساختن مجموعه ژنهای نسل جاری و آینده را ایجاد نمودیم .
برای تعیین مقادیر اولیه برای ژنهای نسل اول از کدهای زیر استفاده میکنیم.
Random r = new Random();
for(int i=0;i<p;i++)
{
for(int j=0;j<n;j++)
{
firstGen[i, j] = r.Next(0, n);
}
}
تابع fitness جهت ارزیابی کروموزومها و تابع sort جهت مرتب سازی آنها را بصورت زیر درج کنید.
public void Fitness(int[,] gen)
{
int count = 0;
for(int i=0;i<p;i++)
{
count = 0;
for(int j=0;j<n;j++)
{
for(int l=j+1;l<n;l++)
{
if(gen[i,j]==gen[i,l])
{
count++;
}
if(Math.Abs(j-l)==Math.Abs(gen[i,j]-gen[i,l]))
{
count++;
}
}
}
gen[i, n ] = count;
}
}
public void Sort(int[,]gen)
{
int temp;
for(int i=0;i<p-1;i++)
{
for(int j=i+1;j<p;j++)
{
if (gen[i, n] > gen[j, n])
{
for(int l=0;l<=n;l++)
{
temp = gen[i, l];
gen[i, l] = gen[j, l];
gen[j, l] = temp;
}
}
}
}
}
عمل ایجاد نسل جدید با توجه به الگوریتم ژنتیک تا زمانیکه مساله حل نشده است تکرار خواهد شد. با توجه به قطعه کدهای زیر.
bool tf = true;
// bool ft = false;
int ftt = 0;
int t = 0;
while (tf)
{
t++;
for (int i = 0; i < (p / 2); i++)
{
for (int l = 0; l < n; l++)
{
secondGen[i, l] = firstGen[i, l];
}
}
for (int i = 0; i < (p / 2); i += 2)
{
for (int l = 0; l <= n; l++)
{
if (l < n / 2)
{
secondGen[i + (p / 2), l] = firstGen[i, l];
secondGen[i + (p / 2) + 1, l] = firstGen[i + 1, l];
}
else
{
secondGen[i + (p / 2), l] = firstGen[i + 1, l];
secondGen[i + (p / 2) + 1, l] = firstGen[i, l];
}
}
secondGen[i, r.Next(n)] = r.Next(n);
secondGen[i + 1, r.Next(n)] = r.Next(n);
}
Fitness(secondGen);
Sort(secondGen);
t++;
if(secondGen[ftt,n]==0)
{
pic0.Top = 10;
pic0.Left = 10;
pic1.Top = 10;
pic1.Left = 10;
pic2.Top = 10;
pic2.Left = 10;
pic3.Top = 10;
pic3.Left = 10;
pic4.Top = 10;
pic4.Left = 10;
pic5.Top = 10;
pic5.Left = 10;
pic6.Top = 10;
pic6.Left = 10;
pic7.Top = 10;
pic7.Left = 10;
// ftt++;
this.Text=(t.ToString());
int col1 = secondGen[0, 0];
pnl[0, col1].Controls.Add(pic0);
int col2 = secondGen[0, 1];
pnl[1, col2].Controls.Add(pic1);
int col3 = secondGen[0, 2];
pnl[2, col3].Controls.Add(pic2);
int col4 = secondGen[0, 3];
pnl[3, col4].Controls.Add(pic3);
int col5 = secondGen[0, 4];
pnl[4, col5].Controls.Add(pic4);
int col6 = secondGen[0, 5];
pnl[5, col6].Controls.Add(pic5);
int col7 = secondGen[0, 6];
pnl[6, col7].Controls.Add(pic6);
int col8 = secondGen[0, 7];
pnl[7, col8].Controls.Add(pic7);
tf = false;
button1.Enabled = true;
}
else
{
firstGen = secondGen;
}
}
شکل خروجی برنامه :
