GA

發佈日期: 作者:

GA(Genetic Algorithms)
GA的應用包括,排程,排序,派車問題(先分群在排序的問題),群組技術,工廠佈置,選址問題(設點問題)
GA的隨機搜尋技術是建立在一種天擇的機制 

ps:
Evolutionary computation(演化式計算)
是一種隨機最佳化技術
模擬人類自然演化過程,以解決困難問題,也就是NP-HARD(ex:2^n,分群)
常見的3類如下
GA(genetic algorithm) ,應用最廣
EP(evolutionary programming) 特殊狀況時可用
ESs(evolution strategies) 

GA term
population(母體):染色體的集合
chromosome(染色體):binary bit string,就是一個solution(解)
genes(基因):bits,就是解的一部份
generation(世代):在演算法中是一個迴圈
fitness(適應值):值較高被挑中的機率就高
offspring(子代):新的chromosome,也就是chromosome的後代
crossover(交配):由2個chromosome產生offspring的動作
mutation(突變):chromosome產生offspring時被改變
phenotype:解碼後的內容solution
genotype:編碼後的內容,也就是chromosome

…………………………………

GA步驟大致如下
1
encoding(soluation)->population=many chromosomes
將真實世界的資料編碼成多個binary bit string,也就是多個染色體,就會形成一個母體
2
(crossover(chromosomes_x,chromosomes_y) or mutation(chromosomes_z))->offspring
透過交配將2個位元字串合成為新的位元字串
或是將一個位元字串突變成另一個新的位元字串
此新的位元字串也就是子代
ps:這邊是盲目操作,完全不管真實世界的資料
3
evaluate(decoding(offspring)) -> phenotype
將子代解碼並透過適應性計算取得解碼後的內容
解碼內容會有3種類型:illegal one(不合法的),infeasible one(不可行解)
4
selection(phenotype)-> new population=many chromosomes
在透過天擇挑選成為新的母體
5
重覆2-4步驟直到得到最佳解

ps:
selection通常有2種做法
regular sampling space:offspring產生後會取代population內部份chromosome,在進行天擇
enlarged sampling space:offspring產生後會附加在parent後,在進行天擇,實作較易

虛擬碼如下
設P(t)為parents,C(t)為現在t世代的子代

Begin
　t = 0;
　initialize P(t); //產生population
　evaluate P(t);
　While (not termination condition) do //這裡的迴圈是指generation
　　recombine P(t) to yield C(t);　　　//crossover or mutation
　　evaluate C(t); //decoding offspring
　　select P(t+1) from P(t) and C(t); //天擇形成new population
　　t = t + 1;
　End
End

……………………………………..

crossover operator(交配)
交配率高則會探索更多解空間,會因假的最佳解而減少安定的機會,而且會增加計時間
交配方式有:單點,兩點,多點,均一
交配率建議參數:高
交配率建議使用時間:演化晚期
ps:探索不夠大,容易陷入區域最佳解

mutation operator(突變)
用途:
1透過突變補救回來之前從母體遺失的基因
2母體原本沒有讓基因,透過突變變出來
突變率太低:
1很多基因無法被嘗試
突變率太高:
1會有干擾,可能會將好的染色體變成壞的染色體
2代與代之間失去相似性,承襲能力喪失
3演算法會失去歷史學習能力
突變率建議參數:低
突變率建議使用時間:演化早期

……………..

GA search特色:
1運作在coding sapce解空間
2從一群解中search,而非單一解search
3使用獎賞機制,也就是fitness(適應值)來導引到最佳解,也就是只有好的解有高機率留下來
4使用probabilistic transition rule(概率過度規則),而非deterministic rules

GA search使用的技術
ga使用fitness做導引,並用crossover和mutation隨機搜尋,平衡搜尋空間中的exploitation和exploration

1.exploitation(開發)
主要用於改善現有的解
適用於演化早期,及local search

2.exploration(探索)
主要用於尋找新的解
適用於演化晚期,及gobal search

ps:搜尋策略有
blind strategies(盲目策略)
heuristic strategies(啟發式策略)

3.population-based search
用多行程執行search
傳統search使用點對點方式,容易陷入區域最佳解
GA使用population-based search可避免這個問題

…………………………..

產生population
以最佳化問題為例,將決策變數編碼並形成母體
設多項式j為a<=x<=b,
步驟如下
1從2^(m-1) < (b-a)*10^4 <=2^m-1 求得m,也就是編碼的bit範圍
ps:10^4是自訂的
2根據m的範圍隨機產生不同bit組合的substring
ps:若要解碼可用公式:x=a+decimal(substring)*(b-a)/(2^m-1)
3將多個substring合在一起形成一個chromosome
4重覆2-3步驟產生多個chromosome形成母體

ex:
設以下目標函式
f(x1,x2)=max
及以下多項式
-3 <= x1 <= 12.1
4.1 <= x2 <= 5.8
population產生步驟如下
1
從2^(m-1) < (b-a)*10^4 <=2^m-1 求得m
從多項式1求m1
2^17 < 12.1-(-3)*10^4 <= 2^18
2^17 < 151000 <= 2^18
m1=18
從多項式2求m2
2^14 < (5.8-4.1)*10^4 <= 2^15
2^14 < 17000 <= 2^15
m2=15
2
根據m的範圍隨機產生不同bit組合的substring
因m1=18,隨機產生一組substring1
ex:000001010100101001
因m2=15,隨機產生一組substring2
ex:101111011111110
ps:
若要解碼可用以下公式
x=a+decimal(substring)*(b-a)/(2^m-1)
substring1解碼
=-3+decimal(000001010100101001)*(12.1-(-3))/(2^18-1)
=-3+5417*(12.1-(-3))/(2^18-1)=-2.687969
substring2解碼
=4.1+decimal(101111011111110)*(5.8-4.1)/(2^15-1)
=4.1+24318*(5.8-4.1)/(2^15-1)=5.361653
3
將多個substring合在一起形成一個chromosome
chromosome=substring1+substring2
000001010100101001101111011111110
4
重覆2-3步驟產生多個chromosome形成population
假設該母體只有10個chromosome,產生以下10個
v1=000001010100101001 101111011111110
v2=001110101110011000 000010101001000
v3=111000111000001000 010101001000110
v4=100110110100101101 000000001011101
v5=000010111101100010 001110001101000
v6=111110101011011000 000010110011001
v7=110100010011111000 100110011101101
v8=001011010100001100 010110011001100
v9=111110001011101100 011101000111101
v10=111101001110101010 000010101101010

…………………………

從population解碼到天擇
步驟如下
1
decoding and evaluate
1.1將population中的chromosome decoding成真實世界的資料
1.2將各資料放入目標函數取得適應值,以下為各chromosome適應值
2
selection
2.1先將各chromosome適應值轉換成介於0~1之間的比率
2.2依適應值百分比分配在一條線上
2.3根據輪盤法隨機產生10個介於0-1的數字,並依數字選取新的chromosome
ps:
之後需進行以下步驟
crossover
設定crossover率為Pc,ex:0.25
在根據Pc值隨機從母體中挑選n個1對chromosome進行crossover
假若挑選chromosome數量為奇數,則將其中一個刪除,或是在挑選一個chromosome做crossover
mutation
設定mutation率為Pm,ex:0.01
在根據Pm隨機從母體中挑選chromosome進行mutation

ex
以上述最佳化範例為例,步驟如下
1
decoding and evaluate
1.1將population中的chromosome decoding成真實世界的資料
v1=(-2.687968,5.361653)
v2=(0.474101,4.170144)
V3=(10.419457,4.661461)
V4=(6.159951,4.109598)
V5=(-2.301286,4.477282)
V6=(11.788084,4.174346)
V7=(9.342067,5.121702)
V8=(-0.330256,4.694977)
V9=(11.671267,4.873501)
V10=(11.446273,4.171908)
1.2將各資料放入目標函數取得適應值,以下為各chromosome適應值
eval(V1)=f(-2.687969,5.361653)=19.805119
eval(V2)=f(0.474101,4.170144)=17.370896
eval(V3)=f(10.419457,4.661461)=9.590546
eval(V4)=f(6.159951,4.109598)=29.406122
eval(V5)=f(-2.301286,4.477282)=15.68091
eval(V6)=f(11.788084,4.477282)=11.900541
eval(V7)=f(9.342067,5.121702)=17.958717
eval(V8)=f(-0.330256,4.694977)=19.763190
eval(V9)=f(11.671267,4.873501)=26.401669
eval(V10)=f(11.446273,4.171908)=10.252480
2
selection
2.1先將各chromosome適應值轉換成介於0~1之間的比率
p1=0.111180
p2=0.097515
p3=0.053839
P4=0.165077
p5=0.088057
p6=0.066806
P7=0.100815
p8=0.11.945
p9=0.148211
P10=0.057554
2.2依適應值百分比分配在一條線上
q1=0.111180
q2=0.208695
q3=0.262534
q4=0.427611
q5=0.515668
q6=0.582475
q7=0.683290
q8=0.794234
q9=0.942446
q10=1.000000
2.3根據輪盤法隨機產生10個介於0-1的數字,並依數字選取新的chromosome
0.301431(v4)
0.322062(v4)
0.766503(v8)
0.881893(v9)
0.350871(v4)
0.583392(v7)
0.177618(v2)
0.343242(v4)
0.343242(v1)
0.197577(v2)
因此新的population為
v1=上一代v4=100110110100101101 000000001011101
v2=上一代v4=100110110100101101 000000001011101
v3=上一代v8=001011010100001100 010110011001100
v4=上一代v9=111110001011101100 011101000111101
v5=上一代v4=100110110100101101 000000001011101
v6=上一代v7=110100010011111000 100110011101101
v7=上一代v2=001110101110011000 000010101001000
v8=上一代v4=100110110100101101 000000001011101
v9=上一代v1=000001010100101001 101111011111110
v10=上一代v2=001110101110011000 000010101001000

…………………………………..

simple ga example in php(beta)
以解該問題為例
maxf(x1,x2)=21.5+x1sin(4pi*x1)+x2sin(20pi*x2)
-3.0≤x1≤12.1
4.1≤ x2≤5.8

//scripts as follows

$limit=1000;
$pm=0.25;
$pc=0.5;

if(is_numeric($_GET['limit'])){$limit=$_GET['limit'];}
if(is_numeric($_GET['pc'])){$pc=$_GET['pc'];}
if(is_numeric($_GET['pm'])){$pm=$_GET['pm'];}

if($limit>5000)$limit=5000;
if($pc>=1)$pc=0.99;
if($pm>=1)$pm=0.99;
echo 'limit generation:'.$limit.' pc:'.$pc.' pm:'.$pm.'

';

/////////////////////////

$count=10;
echo $count.'statistic< br>';
for($i=1;$i<=$count;$i++){
$result[]=ga($limit,$pc,$pm,$info);
}
calresult($result);

echo '< br>The results of the implementation of 1 ga< br>';
ga($limit,$pc,$pm,$info);
graph($info['allmax']);
print_r($info['allmax']);

/////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////
function ga($limit,$pc,$pm,&$info){
$info=NULL;
initialize($v);
while($t<$limit){
crossover($v,$pc);
mutation($v,$pm);
evaluate($v);
select($v,$info);
$t++;
}
return $info['max'];
}

/////////////////////////////////////////////////////////////////////////////////////////
function calresult(&$data){
$count=count($data);
for($i=0;$i<$count;$i++){
$result=$data[$i];
if($max<$result)$max=$result;
if($min>$result || $min==null)$min=$result;
$sum+=$result;
}
$avg=$sum/$count;

for($i=1;$i<=$count;$i++){
$std+=pow($data[$i]-$avg,2);
}
$std=sqrt($std/$count);

echo '
max='.$max.'< br>
min='.$min.'< br>
avg='.$avg.'< br>
std='.$std.'< br>
';
}

/////////////////////////////////////////////////////////////////////////////////////////
function select(&$v,&$info){
$p_size=10;
$v_count=count($v);
$info['max']=0;
$info['t']++;

for($i=1;$i<=$p_size;$i++){
$rand=rand(0,10000)/10000;
for($j=1;$j<=$v_count;$j++){
if($rand > $v[$j-1]['rateend'] && $rand <=$v[$j]['rateend']){
//echo $v[$j-1]['rateend'].'<'.$rand.'<'.$v[$j]['rateend']."n";
$new_v[$i]=$v[$j];
}
}
if($info['max']<$new_v[$i]['fitness'])$info['max']=$new_v[$i]['fitness'];
}
$v=$new_v;
$info['allmax'][]=$info['max'];

/*
if($info['best']<$info['max']){
$info['best']=$info['max'];
$info['best_t']=$info['t'];
}
if($info['worst']==0){$info['worst']=$info['max'];}
if($info['worst']>$info['max']){
$info['worst']=$info['max'];
$info['worst_t']=$info['t'];
}
*/

}

/////////////////////////////////////////////////////////////////////////////////////////
function mutation(&$v,$pm){
$pm*=100;
$v_count=10;
$all=33;

for($i=1;$i<=$v_count;$i++){
for($j=0;$j<$all;$j++){
if(rand(0,100)<$pm){
$mutate=1;
$gene=substr($v[$i]['chro'],$j,1);
if($gene=='0')$v_new[$i]['chro']=substr_replace($v[$i]['chro'], '1',$j,1);
if($gene=='1')$v_new[$i]['chro']=substr_replace($v[$i]['chro'], '0',$j,1);
}
}
if($mutate==1){
$mutate=0;
$v[]['chro']=$v_new[$i]['chro'];
}
}

}

/////////////////////////////////////////////////////////////////////////////////////////
function mutation2(&$v,$pm){
$pm*=100;
$v_count=count($v);
$all=33;
$cut=rand(0,$all);

for($i=1;$i<=$v_count;$i++){
if(rand(0,100)<$pm){
$gene=substr($v[$i]['chro'],$cut,1);
if($gene=='0')$offspring=substr_replace($v[$i]['chro'], '1',$cut,1);
if($gene=='1')$offspring=substr_replace($v[$i]['chro'], '0',$cut,1);
$j++;
$v[$v_count+$j]['chro']=$offspring;
}
}

}

/////////////////////////////////////////////////////////////////////////////////////////
function crossover(&$v,$pc){
$pc*=100;
$v_count=count($v);
$j=1;
for($i=1;$i<=$v_count;$i++){
if(rand(0,100)<$pc){
$parent[$j++]=$v[$i]['chro'];
}
}

$p_count=count($parent);
$all=35;
$cut=rand(0,$all);

for($i=1;$i<$p_count;$i++){
$parent_a1=substr($parent[$i],0,$cut);
$parent_a2=substr($parent[$i],$cut,$all-$cut);
$parent_b1=substr($parent[$i+1],0,$cut);
$parent_b2=substr($parent[$i+1],$cut,$all-$cut);
$offspring1=$parent_a1.$parent_b2;
$offspring2=$parent_b1.$parent_a2;

$v[$v_count+1]['chro']=$offspring1;
$v[$v_count+2]['chro']=$offspring2;

$i++;
}

}

/////////////////////////////////////////////////////////////////////////////////////////
function evaluate(&$v,&$max=null){
$v_count=count($v);
for($i=1;$i<=$v_count;$i++){
$x1=vdecode(substr($v[$i]['chro'],0,18),-3,12.1,18);
$x2=vdecode(substr($v[$i]['chro'],18,15),4.1,5.8,15);
$v[$i]['fitness']=maxfunction($x1,$x2);
$fitnesstotal+=$v[$i]['fitness'];
if($max<$v[$i]['fitness'])$max=$v[$i]['fitness'];
}

for($i=1;$i<=$v_count;$i++){
$v[$i]['rate']=$v[$i]['fitness']/$fitnesstotal;
$rate+=$v[$i]['rate'];
$v[$i]['rateend']=$rate;
}

}

/////////////////////////////////////////////////////////////////////////////////////////
function maxfunction($x1,$x2){
$pi=pi();
return 21.5+$x1*sin(4*$pi*$x1)+$x2*sin(20*$pi*$x2);
}

/////////////////////////////////////////////////////////////////////////////////////////
function vdecode($binary,$min,$max,$m){
$x=$min+bindec($binary)*($max-($min))/(pow(2,$m)-1);
return $x;
}

/////////////////////////////////////////////////////////////////////////////////////////
function initialize(&$v){
/*
$min=-3;
$max=12.1;
$multiple=10000;
$min*=$multiple;
$max*=$multiple;
$range=$max-$min;
$offsend=rand(0,$range);
$value=($min+$offsend)/$multiple;
*/

$p_size=10;
$m1=18;
$m2=15;
$m=$m1+$m2;

for($j=1;$j<=$p_size;$j++){
for($i=1;$i<=$m;$i++){
$v[$j]['chro'].=rand(0,1);
}
}

//print_r($v);
}

/////////////////////////////////////////////////////////////////////////////////////////
function graph($data){
$im = imagecreate(1100,370);
$green = imagecolorallocate($im,214,235,214);
$black = imagecolorallocate ($im, 0, 0, 0);
imageline($im,10,300,1000,300, $black );
imageline($im,10,5,10,300, $black );
imagestring($im,3,1000,300,"generation",$black);
imagestring($im,3,8,1,"soluation",$black);

$x = 10;
$y = 300;
$count=count($data)-1;
for($i=0;$i<$count;$i++){
imageline($im,$x+$i,450-$data[$i]*10,$x+$i+1,450-$data[$i+1]*10,$black);
}

for ($i=0;$i<6;$i++){
imagestring( $im,2,1,450-(20+$i*5)*10,20+$i*5,$black);
}
for ($i=0;$i<=10;$i++){
imagestring( $im,2,$x+$i*100,$y+11,$i*100,$black);
}

imagepng($im, "a.png");
echo "< img src='a.png' >";
imagedestroy($im);

}