Siavash

الگوریتم ژنتیک یا Genetic Algorithm (GA) در واقع شبیه سازی بقای انسان هست! تا حالا پیش خودتون فکر کردین این همه سال گذشته چطوری انسان ها از بین نرفتن و نسلشون پا برجاس؟ فکر می کنید رمز موفقیتشون چیه؟

فکر کنم 183462130973.347928374261010000001 باشه!
" ... "

انسان ها بقا دارن چون با یه قانون خاصی پیش میرن که واضحه که موفق بوده!
حالا همین قانون رو توی کامپیوتر میشه شبیه سازی کرد! اما چجوری؟
فکر کنید میخوایم جواب این تابع رو بدست بیاریم:
بنظر خیلی پیچیده میاد! شاید با روش های تحلیلی حل نشه و نیاز به محاسبات عددی باشه! یکی از راه ها الگوریتم ژنتیک هست که بعضی اوقات به شکل باور نکردنی سریع به جواب میرسه.
خوب پس من با یه مقدمه ازش شروع می کنم:


اولین مرحله اینه که ما یک سری کرومزوم به عنوان جمعیت اولیه بصورت تصادف انتخاب می کنیم. هر کرومزوم یه عدد هست در مبنای دو.
مثلا این کرومزوم هارو به عنوان جمعیت اولیه در نظر می گیریم:بعد از اینکه جمعیت اولیه معلوم شد این کرومزوم ها توی تابع Fitness امتحان میشن و بر حسب اینکه به جواب مورد نظر نزدیکن یا نه یه عدد بین صفر تا یک بهشون اختصاص داده میشه که صفر یعنی اصلا بدرد نمی خوره و یک یعنی عالیه!
بر حسب سلامتی کرومزوم ها چند تا از اون ها به عنوان والدین نسل بعدی انتخاب میشن! مرحله ی بعدی مرحله ی Breed هست که طبق فرایند Crossover کرومزوم ها با هم ازدواج می کنن و بچه دار میشن!

وااای مگه یه مشت صفرو یکم می تونن با هم ازدواج کنن!
" یکم صبر کنی میبینی که می تونن! "

خوب حالا فرآیند Crossover چطور انجام میشه؟
از کرومزوم های برگزیده دوتا دوتا انتخاب میشن و فرایند Crossover روی هر زوج بصورت زیر انجام میشه:
در بالا فرآیند Crossover رو برای زوج اول می بینید! همونطور که مشخصه اول هر کزومزوم از بیت 5ام به دو قسمت تقسیم شدن و 5 بیت اول کرومزوم اول با 3 بیت دوم کرومزوم دوم ترکیب شده و برعکس. به این ترتیب دو فرزند جدید بوجود اومد.
همین کار برای بقیه ی کرومزوم ها هم انجام میشه، ممکنه یک کرومزوم دو یا چند بار در فرآیند Crossover بکار برده شه، احتمال شرکت کرومزوم هایی که سلامت بهتری دارند توی فرآیند Crossover بیشتره!
بعد از فرآیند Crossover یک مرحله داریم که احتمال وقوعش خیلی کم هست به نام جهش یا Mutation. توی این فرآیند یک بیت تصادفی از یه کرومزوم تصادفی رو عوض می کنند. مثلا اگر بیت چهارم یک کرومزوم انتخاب بشه در صورتی که صفر باشه اونو یک می کنند یا بلعکس.
این فرایند تو واقعیت هم وجود داره مثلا در یک آدم جهشی به وجود میاد و نابغه میشه یا در یه آدم دیگه جهش بوجود میاد و ناقص میشه! در الگوریتم ژنتیک هم همینطوره، یک جهش ممکنه کاملا مفید یا کاملا مضر باشه.
بعد از این مرحله دوباره کرومزوم های جدید به جمعیت اولیه برای نسل بعد بر می گردند و این فرآیند ها تکرار میشه تا با یک تلورانسی به جوابی که می خوایم نزدیک شیم! این روش در مقایسه با بقیه ی روش های آزمایش و خطا خیلی پیشرفته تره و خیلی وقت ها بسیار سریعتر به نتیجه ی مطلوب میرسه!

منبع: سیاوش محمودیان - بلاگ - مقدمه ای بر هوش مصنوعی

__________________

A162

ممنون از شما !
بسيار جالب بود
حالا چطور اون معادله اولي كه فرموديد رو ميشه به اين روش حل كرد؟
با تشكر دوباره

Siavash

سوال خیلی خوبیه!
فرض کنید می خوایم اون معادلرو حل بکنیم.
یک راه اینه که مثلا یک متغیر رو مقدارش رو صفر قرار بدیم و 0.1 0.1 به اون اضافه کنیم و هر بار جواب رو توی معادله قرار بدیم تا یک جواب نزدیک به دست بیاریم. این کار اولین روشی هست که شاید به ذهن هر کسی برسه. ولی مشکلات زیادی داره. اولا لزوما به جواب نمی رسه. چون ممکنه 0.1 خیلی مقدار بزرگی نسبت به جواب باشه یا مثلا جواب منفی باشه.

راه بعدی استفاده از روش های مختلف محاسبات عددی معمول هست. مثل تکرار ساده یا روش نیوتن یا ... این روش ها روش های خوبی هستند نسبت به روش قبل. اما خیلی وقت ها این روش ها همگرا نمیشن. یا توی یک اکسترمم نسبی میفتن!

روشی که می خوایم بگیم خیلی وقت ها از این دو روش بهتر هست همین الگوریتم ژنتیک هست! اما چطوری؟
خوب تو این روش اول یک تابع سلامت یا Fitness Function تعریف می شه. این تابع سلامت هر کروموزوم رو تعیین می کنه. بعد روش Cross over و Mutation رو باید انتخاب کنیم و جمعیت اولیرو تولید می کنیم.
در آموزش بالا من ساده ترین نوع و در واقع روش کلاسیک تولید جمعیت اولیه و Crossover و Mutation رو گفتم.
حالا می خوام نوع دیگه ای از اون رو معرفی کنم. این بار جای اینکه اعداد باینری رو به عنوان جمعیت اولیه در نظر بگیریم، کلی اعداد حقیقی تولید می کنیم به عنوان جمعیت اولیه. مثلا 100، -10.5، 57.2 و ...
خوب حالا سوال پیش میاد پس عملیات Crossover و Mutation چطور خواهند بود؟
باز هم روش های مختلفی هستند. ما ساده ترینش رو انتخاب می کنیم. یعنی به عنوان عملیات Crossover از دو کروموزوم پدر و مادر میانگین می گیریم و به عنوان عملیات Mutation بعضی اوقات عدد رو با یک درصد کمی از خودش جمع یا تفریق می کنیم.
خوب حالا شروع می کنیم به بررسی فرآیند حل اون معادله. اول همونطوری که گفتم یک جمعیت اولیه داریم. مقدار هر کدوم از کروموزوم های جمعیت اولیرو به جای X در سمت چپ معادله قرار می دیم. این مقدار باید در نهایت 12 بشه (سمت راست معادله).
پس تابع سلامت رو این طور تعریف می کنیم: تفاضل جواب بدست اومده از قرار دادن کرومزوم های جمعیت اولیه در سمت چپ معادله منهای عدد 12.
پس یعنی اگر تابع سلامت 0 بشه ما دقیقا به جواب رسیدیم. برای تمام کروموزوم ها مقدار سلامتیشون رو بدست میاریم. از بین سالم ترین کرومزوم ها (یعنی کرومزوم هایی که مقدار تابع سلامتشون بیشتر به صفر نزدیکه)، تعدادی انتخاب می کنیم. این کرومزوم ها روشون عملیات Crossover و Mutation انجام میشه. یعنی با انتخاب دو به دو ی اون ها و میانگین گرفتن یک جمعیت جدید ایجاد میشه! به این روش انتخاب، انتخاب Elite ها یا بهترین ها در هر مرحله میگن. روش های دیگری هم برای قسمت انتخاب وجود داره.
حالا یک جمعیت کروموزوم های جدید داریم و مجددا عملیات تکرار می شه تا بالاخره یکی از کروموزوم ها مقدار تابع سلامتش تا حدی که ما می خوایم به 0 نزدیک بشه، مثلا 0.0001
شاید به نظر کمی عجیب بیاد که این روش واقعا بتونه معادلرو حل کنه. اما این روش که مثل اکثر روش های بهینه سازی دیگه بر مبنای آزمایش و خطا هست در بعضی مواقع بسیار زودتر ما رو به نتیجه ی مورد نظر می رسونه. کافیه امتحان کنید.

__________________

m.shh

سلام
پروژه پایانی من الگوریتم ژنتیکه . من کد حل N Queen In C# With GA و TSP IN Mathlab with GA گذاشتم تو پروژه ام حالا استاد راهنما گفته باید حتما بلاک به بلاک کد ها را براش توضیح فارسی بذاری . من هم هیچ بلد نیستم . یه روز دو روز هم بیشتر فرصت ندارم . تورو خدا یکی کمک کنه.

A ) N Queen In C# With GA

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace chess2
{
public partial class Form1 : Form
{
int c = 0;
public Form1()
{

InitializeComponent();
}
private int[] rand(int n, int x)
{
Random random = new Random(x + DateTime.Now.Millisecond);
int t = random.Next(0, n);
int[] inta = new int[n];
int c;
string[] abc = new string[n]; ;
for (int i = 0; i < n; i++) { a: t = random.Next(0, n); c = 1; while ((i - c) >= 0)
{
if (inta[i - c] == t)
{
abc[i] = t.ToString();
goto a;

}
c++;
}
for (int i2 = 0; i2 <= i; i2++)
{
if (abc[i2] == t.ToString())
goto a;
}
inta[i] = t;
}
return inta;
}
private Double fib(int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;
Double tmp = 0;
for (int i = 0; i <= n; i++)
{
tmp += i;
}
return tmp + 0.0;
}

private int[,] cross(int[] pop1, int[] pop2, int n)
{
int[,] pop_4_return = new int[2, n];
for (int c = 0; c < 2; c++)
{
for (int i = 0; i < n; i++) { if ((n / 2) > i)
{
if (c == 0)
{
pop_4_return[c, i] = pop2[i];
}
else
{
pop_4_return[c, i] = pop1[i];
}
}
else
{
if (c == 0)
{
pop_4_return[c, i] = pop1[i];
}
else
{
pop_4_return[c, i] = pop2[i];
}
}
}
}
return pop_4_return;
}
private Double fit(int[] nff, int n)
{
int[,] inta = new int[n, n];
int tmp = 0, fitness = 0;
for (int c = 0; c < n; c++)
{
inta[c, nff[c]] = 1;
}

for (int i = 0; i < n; i++)
{
for (int ii = 0; ii < n; ii++)
{
if (inta[i, ii] == 1)
{
tmp = ii;
goto a;
}
}
a:
for (int i2 = 1; i2 < n; i2++)
{
if (((i + i2) < n))
if ((tmp + i2) < n)
if (inta[i + i2, tmp + i2] == 1)
fitness++;
if (((i + i2) < n)) if ((tmp - i2) >= 0)
if (inta[i + i2, tmp - i2] == 1)
fitness++;
if ((i + i2) < n)
if (inta[i + i2, tmp] == 1)
fitness++;
}
}
Double fibonachi = fib(n - 1) + 0.0;
Double r = 100 - (fitness * (100 / fibonachi));
return r;
}
private int[,] pop_generator(int n)
{
int[,] inta = new int[n, n];
int[] intb = new int[n];
intb = rand(n, c);
c++;
for (int i = 0; i < n; i++)
{
intb = rand(n, c);
while ((fit(intb, n)) < 50.0)
intb = rand(n, c); c++;
for (int j = 0; j < n; j++)
{
inta[i, j] = intb[j];
}
c++;
}
return inta;
}
private int arr_to_var(int[] narr, int n)
{
string nvar = "";
for (int i = 0; i < n; i++)
{
nvar += narr[i].ToString();
}
Int32 n_for_return = Int32.Parse(nvar);
return n_for_return;

}
private int[,] crossover(int[,] pop, int n)
{
int[,] pop_for_return = new int[n, n];
int[,] crosstemp = new int[2, 2];
int[] tmp1 = new int[n];
int[] tmp2 = new int[n];
for (int i = 0; i < n; i += 2)
{
for (int j = 0; j < n; j++)
{
tmp1[j] = pop[i, j];
tmp2[j] = pop[i + 1, j];
}
crosstemp = cross(tmp1, tmp2, n);
for (int j2 = 0; j2 < n; j2++)
{
pop_for_return[i, j2] = crosstemp[0, j2];
pop_for_return[i + 1, j2] = crosstemp[1, j2];
}
}
return pop_for_return;
}
private void printc(int[] arr_4_print, int n)
{
int[,] tmp = new int[n, n];
for (int i = 0; i < n; i++)
tmp[arr_4_print[i], i] = 1;
for (int i = 0; i < n; i++)
{
label1.Text += "\n\r";
for (int j = 0; j < n; j++)
{
if (tmp[i, j] == 1)
label1.Text += "*";
else
label1.Text += "0";
}
}
}
private void Form1_Load(object sender, EventArgs e)
{

}

private void button1_Click(object sender, EventArgs e)
{
Int32 n = Int32.Parse(textBox1.Text);
int[,] pop = new int[n, n];
int[,] cros = new int[n, n];
int[] tmp = new int[n];
pop = pop_generator(n);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
tmp[j] = pop[i, j];
}
if (fit(tmp, n) == 100.0)
{
printc(tmp, n);
goto a;
}
}
int comp = 1;
int counter = 0;
cros = crossover(pop, n);
while (comp == 1)
{
this.Text = counter.ToString();
counter++;
label1.Text = "";
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
label1.Text += cros[i, j];
}
label1.Text += "\n\r";
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
tmp[j] = cros[i, j];
}
if (fit(tmp, n) == 100.0)
{
printc(tmp, n);
comp = 0;
goto a;

}
}
cros = crossover(cros, n);
}
a:
this.Text = "find";
}
}
}


B ) TSP IN Mathlab with GA

clear;clc

matris=rand(50,50);
matris=round(matris*1)+1;
siz=size(matris);
for i=1:siz(2)
for j=1:siz(2)
% m(i,j)=m(j,i);
if i==j
matris(i,j)=0;
end
end
end

qtybest=10;
n=siz(2);
N=100;
F=n+1;
C=40;
M=60;
for i = 1:N
for j= 1 :n
pop (i,j)=j;
end

for i2=1:n
r1=round(rand*(n-1))+1;
r2=round(rand*(n-1))+1;
t=pop(i,r1);
pop(i,r1)=pop(i,r2);
pop(i,r2)=t;
end
end
k=1;
for i=1:N
pop(i,F)=Fitness(pop(i,1:n ),siz(2),matris);
end
while( pop(1,F) ~= siz(2)-1 )
Plot(k)=pop(1,F);
k=k+1;
for i=N+1:N+C
r1=round(rand*(N-1))+1;
pop(i,1:n)=Crossover(pop(r1,1:n),siz(2) );
end
for i=N+C+1:N+C+M
r1=round(rand*(N-1))+1;
pop(i,1:n)=Mutation(pop(r1,1:n),siz(2));
end
for i=N+1:N+C+M
pop(i,F)=Fitness(pop(i,1:n ),siz(2),matris);
end
pop1=Selection(pop,N+M+C,N,F);
pop2=Sort(pop,F,N+C+M);
for i=1:qtybest
pop3(i,1:F)=pop2(i,1:F);
end
for i=qtybest+1:N
pop3(i,1:F)=pop1((i-qtybest),1:F);
end
pop=pop3;
fasele=pop(1,F)
generation=k
clear pop1;clear pop2; clear pop3
for i = 1:siz(2)-1
x(i)=matris(pop(1,i),pop(1,i+1));
end
x(F)=pop(1,F);
end
plot(Plot);
function ret=Selection(pop,L,n,F)
for i=1:n
r1=round(rand*(L-1))+1;
r2=round(rand*(L-1))+1;
if pop(r1,F)<pop(r2,F)
P(i,1:F)=pop(r1,1:F);
else
P(i,1:F)=pop(r2,1:F);
end
end
ret=P;
function ret=Crossover(A,si)
r=round(rand*(si-1))+1;
for i=1:r
B(i)=A(i);
end
j=si;
for i=r+1:si
B(i)=A(j);
j=j-1;
end
ret=B;
function ret=Mutation(A,si)
r1=round(rand*(si-1))+1;
B=A;
r2=round(rand*(si-1))+1;
B(r1)=A(r2);
B(r2)=A(r1);
ret=B;
function ret=Fitness(A,si,matris1)
x=0;
for i = 1:si-1
x=x+matris1(A(i),A(i+1));
end
ret=x;
function ret=Sort(P,b,N)
for i=1:N
for j=i+1:N
if (P(i,b)>P(j,b))
T(1:b)=P(i,1:b);
P(i,1:b)=P(j,1:b);
P(j,1:b)=T(1:b);
end
end
end
ret=P;

sara20012

میشه لطف کنید و نحوه نوشتن تابع fitness رو برای مسئله هشت وزریر توضیح بدید (با مطلب)