ACS

發佈日期: 作者:

Ant Algorithm(螞蟻演算法)
1991年由Dorigo首次提出
1997年提出ACS(Ant Colony System),也為較經典之版本
一種尋優演算法,原理為費洛蒙機制

費洛蒙機制:
1.pheromone記憶與更新:也就是正向及反向反饋機制
將常走路徑之pheromone變強,不常走路徑的pheromone變弱,並將較好路徑之pheromone加強
2.根據pheromone決定路徑:也就是機率尋優方法
該路徑pheromone越高,選擇該路徑機率越高


………………………………
以下規則以1997版之ACS為主

參數配置
n:節點數量
ant數量,建議設為n
b:決定pheromone和距離之相對重要性,通常設2
q0:為選擇探索或追蹤的參數,0p:用於區域更新的殘留系數,0a:用於全域更新的殘留系數,0T0:用來當一開始初路徑之pheromone,以及local update的pheromone,建議設(n*Lnn)^-1
ps:Lnn=nearest neighbor heuristic為所有節點之間最短路徑

ant步驟
大致如下
1 各ant根據state transi
tion rule決定下一個目地,但要避開之前走過的
2 各ant對剛走的路徑進行pheromone local updating 3 返回步驟1直到所有節點都完成
4 挑選最佳路徑進行pheromone global updating
5 清空本次ant路徑
6 返回步驟1直到終止條件
ps:終止條件
通常設為最大世代數,例如500
或是到最後每個世代的解都相同時

程式碼大致如下
while(terminal){//未達終止條件下不斷重複執行
　while(untraved){ //將各節點都走過
　　while(ant){ //各ant執行state_transiton決定路徑
　　　state_transition();
　　}
　　pheromone_local_update; //每走過一個節點就更新兩點之間pheromone
　}
　pheromone_global_update //全部節點走完後找出最好路徑,並只更新該路徑pheromone
}


State Transition Rule
q0為選擇探索或追蹤的參數
q為系統產生之隨機數,0 < q < １ 
若q>q0則根據以下取最大值,決定的目地
MAX(ph_rs*n_rs^b)
ps:b是determines the relative importance of pheromone versus distance,通常設2
若qpb_rs=ph(r,s)*n(r,s)^b / sum(ph(r,u)*n(r,u)^b)
ph(r,s)=從r到s的pheromone
ph(r,u)=從r到u的pheromone
n(r,s)=從r到s的local heuristic,通常為1/distance_rs
n(r,u)=從r到u的local heuristic
b=同上
注意:u是未到訪的節點,r是出發節點,s是某個目地的點


區域更新費洛蒙
pheromone local updating
用在區域,每走一個節點更新一次
公式為:ph(r,s)+=(1-p)ph(r,s)+(p)ph_add(r,s)
where ph_add(r,s)=init-pheromone　,以初始pheromone做值
參數有以下
p=殘留系數
ph(r,s)=該路徑(r到s)目前的pheromone
ph_add(r,s)=當該路徑(r到s)被走過時,需增加pheromone的量,若該路徑這次沒被走過則值為0

全域更新費洛蒙
pheromone global updating
用在全域,走完全部節點在更新最好路徑上的pheromone
公式為:ph(r,s)+=(1-a)ph(r,s)+(a)ph_add(r,s)
where ph_add(r,s)= best_L^-1 , best_L為最好的路徑長度
參數有以下
a=pheromone decay parameter,0ph(r,s)同上
ph_add(r,s)同上

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

//使用的變數如下
nodeall=所有節點數
t.max=欲執行的次數

map_d
//2維陣列型態,代表各節點之distance
//map_d=map

map_h
//2維陣列型態,代表各節點之heuristic
//map_h=map

ph
//2維陣列型態,記錄各路徑的費洛蒙
//ph=map
//ex:從a節點到b節點的費洛蒙為0.2
//ph[a][b]=0.2

antpath
//2維陣列型態,記錄各ant路徑
//antpath[ant_k][step]=node
// ex:第1隻ant走的路徑為abdc,則記錄如下
//antpath[1]={a,b,d,c}

//演算法如下
while(t　for(node=0;node　　pb=path_probability(ph);
　　//根據公式(費洛蒙及各node相連之成本)產生各node去不同node的機率
　　dest=ant_decision(pb);
　　//根據機率並透過方法決定在多個目地時應選擇那一個目地
　　antpath=antpath_update(dest);
　　//更新ant路徑表以表示ant移動的狀況
　　ph=pheromone_update_local(antpath);
　　//根據實際去的node,重新計算費洛蒙的值
　}
ph=pheromone_update_global(antpath);
ph=pheromone_update_global_best(antpath);
best=selectbest_antpath(antpath); //從各ant實際走的路徑中選擇最好的路徑
}

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

acs for php example

/////////////////////////////////////////////////////////////////////////////////////////
//////// acs usage description //////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////
/*
1.acs() need "map distance" data and array named as "$para['map_d']", as follow
$para['map_d']=array(
'1'=>array('1'=>0,'2'=>3,'3'=>5,'4'=>5),
'2'=>array('1'=>3,'2'=>0,'3'=>4,'4'=>6),
'3'=>array('1'=>5,'2'=>4,'3'=>0,'4'=>2),
'4'=>array('1'=>5,'2'=>6,'3'=>2,'4'=>0));

2.acs($para) will return acs result with the array representation ,refer to function evaluate()
$result_array=acs($para);
*/

////////////// acs example as follow /////////////////////////////////////////////////////
//phase 1
//read data
$inputdata = file('map.txt'); //in the each line of map.txt` is x,y
while($line=each($inputdata)){
  $i++;
  $tmp=explode(',',$line['value']);
  $node[$i]['x']=trim($tmp[0]);
  $node[$i]['y']=trim($tmp[1]);
}
$nodecount=count($node);
for($i=1;$i<=$nodecount;$i++){
  for($j=1;$j<=$nodecount;$j++){
    $map_d[$i][$j]=0;
    if($i!=$j)$map_d[$i][$j]= sprintf("%.5f",sqrt( pow($node[$i]['x']-$node[$j]['x'],2) + pow($node[$i]['y']-$node[$j]['y'],2) ));
  }
}
$para['map_d']=$map_d; // data for acs()
//$para['node_xy']=$node; //the data for graph()

//phase 2
//excute acs
$para['antpath_value']=acs($para);
echo 'global best='.$para['antpath_value']['sumbest_global'].'< br>';
graph($para['antpath_value']['pathbest_global'],$node);
/////////// acs example end ////////////////////////////////////////////////////////////

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

////////////////////////////////////////////////////////////////////////////////////////
//////// main function ///////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////
function acs($para){
$para['a']=0.1;//0$para['b']=2;//relative importance of local heuristic or pheromone
$para['p']=0.1;//trail evaporates,the value must is < 1
$para['q0']=0.9;//explorse or tracking $para['gn']=100;//generation number
$para['gn']=500;//generation number

$para['node']=count($para['map_d']);//node sum
$para['ant']=$para['node'];//ant sum
$para['initph']=(1/($para['node']*nearest_neighbor_heuristic($para)));
$para['map_h']=init('map_h',$para);
$para['map_hb']=init('map_hb',$para);
$para['ph']=init('ph',$para);//init pheromone by random

while($t<$para['gn']){
  $t++;
  $para['antpath']=init('antpath',$para);
  $para['unvisited']=init('unvisited',$para);
  for($i=0;$i<$para['node'];$i++){
    $para['unvisited']=unvisitednode($para);
    reset($para['antpath']);
      while($ant=each($para['antpath'])){
        $para['antpath'][$ant[0]][]=state_transition($ant[0],$para);
      }
    $para['ph']=pheromone_update($para);
  }
  $para['antpath_value']=evaluate($para);
  $para['ph']=pheromone_update_global($para);
}

return $para['antpath_value'];

}

/////////////////////////////////////////////////////////////////////////////////////
//////// sub function //////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////////
function nearest_neighbor_heuristic($para){
for($i=1;$i<=$para['node'];$i++){
  $traved[$i]=0;
}

$path[]=1;
$traved[1]=1;
while(array_sum($traved)<$para['node']){
  $start=end($path);
  reset($traved);
  $distance=null;
  while($d=each($traved)){
    $dst=$d[0];
    if($d[1]!=1){
      $distance[$dst]=$para['map_d'][$start][$dst];
    }
  }
  asort($distance);
  $n=each($distance);
  $traved[$n[0]]=1;
  $path[]=$n[0];
  $length[]=$n[1];
}
$start=end($path);
reset($traved);
$distance=null;
while($d=each($traved)){
  $dst=$d[0];
  if($d[1]!=1){
    $distance[$dst]=$para['map_d'][$start][$dst];
    $traved[$dst]=1;
    $path[]=$dst;
    $length[]=$distance[$dst];
  }
}

$totallength=array_sum($length);
return $totallength;
}

////////////////////////////////////////////////////////////////////////////////
function init($type,$para){
if($type=='antpath'){
  for($i=1;$i<=$para['ant'];$i++){
    $antpath[$i][]=$i;
  }
  return $antpath;
}

if($type=='unvisited'){
  for($i=1;$i<=$para['ant'];$i++){
    $n=1;
    while($n<=$para['node']){$unvisited[$i][]=$n++;}
  }
  return $unvisited;
}

//compute heuristic(1/distance=heuristic)
if($type=='map_h' or $type=='ph' or $type=='map_hb'){
  while($i=each($para['map_d'])){
    while($j=each($i['value'])){
      if($j['value']){
        $map_h[$i['key']][$j['key']]=1/$j['value'];
        $map_hb[$i['key']][$j['key']]=pow($map_h[$i['key']][$j['key']],$para['b']);
        $ph[$i['key']][$j['key']]=$para['initph'];
      }else{
        $map_h[$i['key']][$j['key']]=0;
        $map_hb[$i['key']][$j['key']]=0;
        $ph[$i['key']][$j['key']]=0;
      }
    }
  }
}
if($type=='map_h'){return $map_h;}
if($type=='map_hb'){return $map_hb;}
if($type=='ph'){return $ph;}

}

//////////////////////////////////////////////////////////
function unvisitednode($para){
while($ant=each($para['antpath'])){
  $lastnode=end($para['antpath'][$ant[0]]);
    while($u=each($para['unvisited'][$ant[0]])){
      if($u[1]!=$lastnode)$unvisited_new[$ant[0]][]=$u[1];
    }
  }
return $unvisited_new;
}

/////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////
function state_transition($k,$para){
$r=end($para['antpath'][$k]);

$dstcount=count($para['unvisited'][$k]);
if($dstcount<1){$antdest[$k]=$para['antpath'][$k][0];}
if($dstcount==1){
  $lastdst=each($para['unvisited'][$k]);
  $antdest[$k]=$lastdst[1];
}
if($dstcount>1){

//computer state value
  $u_pb_sum=0;
  while($unvisited=each($para['unvisited'][$k])){
  $u=$unvisited[1];
  $u_pb_each[$u]=$para['ph'][$r][$u]*$para['map_hb'][$r][$u];
}

//select explore or tracked by q0
$q=rand(0,100)/100;
if($q<=$para['q0']){
//////////////select best pheromone dest start
  $ph_comp=$u_pb_each;
  arsort($ph_comp);
  $dstary=each($ph_comp);
  $antdest[$k]=$dstary[0];
//////////////select best pheromone dest end
}else{
/////////////random select dest by probability start
  $u_pb_sum=array_sum($u_pb_each);
  while($s=each($u_pb_each)){
    if($s[1]!=0){
      $pb[$r][$s[0]]=$s[1]/$u_pb_sum;
    }else{
      $pb[$r][$s[0]]=0;
    }
  }
//select
  $pbsum=array_sum($pb[$r]);
  $selectpoint=(rand(0,$pbsum*10000)/10000);
  while($s=each($pb[$r])){
    $nowposition+=$s[1];
    if($nowposition>=$selectpoint){
     $antdest[$k]=$s[0];
     break;
   }
  }
/////////////random select dest by probability end
}

}

return $antdest[$k];
}

/////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////
function pheromone_update($para){
reset($para['antpath']);
while($ant=each($para['antpath'])){
  $j=end($para['antpath'][$ant[0]]);
  $i=prev($para['antpath'][$ant[0]]);
  $ph_add[$i][$j]=$para['initph'];
  $ph_add_tmp=0;

//have only traveled update
  $para['ph'][$i][$j]=(1-$para['p'])*$para['ph'][$i][$j]+$para['p']*$ph_add[$i][$j];
}
return $para['ph'];
}
///////////////////////////////////////////////////////////////////////////////
function pheromone_update_global($para){
$ph_add=pow($para['antpath_value']['sumbest_global'],-1);
while($node=each($para['antpath_value']['pathbest_global'])){
  if($i!=null){
    $j=$node[1];
    $para['ph'][$i][$j]=(1-$para['a'])*$para['ph'][$i][$j]+$para['a']*$ph_add;
  }
  $i=$node[1];
}
return $para['ph'];
}

///////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////
function evaluate($para){
$antpath_value=$para['antpath_value'];
$antpath_value['unit']=null;
while($ant=each($para['antpath'])){
  $i=null;
  $j=null;
  while($path=each($ant['value'])){
    if($i!=null){
      $j=$path['value'];
      $antpath_value['unit'][$ant['key']][]=$para['map_d'][$i][$j];
    }
    $i=$path['value'];
  }
$antpath_value['sum'][$ant['key']]=array_sum($antpath_value['unit'][$ant['key']]);
}

asort($antpath_value['sum']);
$bestdata=each($antpath_value['sum']);
$bestant=$bestdata[0];
$antpath_value['sumbest']=$bestdata[1];
$antpath_value['pathbest']=$para['antpath'][$bestant];
$antpath_value['sumbest_history'][]=$antpath_value['sumbest'];

if($antpath_value['sumbest_global']==null or $antpath_value['sumbest_global']>$antpath_value['sumbest']){
  $antpath_value['sumbest_global']=$antpath_value['sumbest'];
  $antpath_value['pathbest_global']=$antpath_value['pathbest'];
}
$antpath_value['sumbest_global_history'][]=$antpath_value['sumbest_global'];

/*
$antpath_value['unit'] array ,each ant each cost of path node
$antpath_value['sum'] array ,each ant sum cost of path node
$antpath_value['pathbest'] array
$antpath_value['sumbest'] int
$antpath_value['sumbest_history'] array
$antpath_value['pathbest_global'] array
$antpath_value['sumbest_global'] int
$antpath_value['sumbest_global_history'] array
*/

echo $antpath_value['sumbest_global'].",";

return $antpath_value;
}

/////////////////////////////////////////////////////////////////////////////////
////////// optional ////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////////////////////////
function caclutime(){
$time = explode( " ", microtime());
$usec = (double)$time[0];
$sec = (double)$time[1];
return $sec + $usec;
}

//////////////////////////////////////////////////////////////////////////////////////////////
function graph($path,$node_xy){
//$path=$data['antpath_value']['pathbest_global'];
//$node_xy=$data['node_xy'];
$im = imagecreate(500,500);
$green = imagecolorallocate($im,214,235,214);
$black = imagecolorallocate ($im, 0, 0, 0);
$count=count($path)-1;
for($i=0;$i<$count;$i++){
  $ix=$node_xy[$path[$i]]['x']*5;
  $iy=$node_xy[$path[$i]]['y']*5;
  $jx=$node_xy[$path[$i+1]]['x']*5;
  $jy=$node_xy[$path[$i+1]]['y']*5;
  imageline($im,$ix,$iy,$jx,$jy,$black);
}
imagepng($im, "a.png");
echo "< img src='a.png' >";
imagedestroy($im);
}


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


其他可參考的文獻
http://sjchen.im.nuu.edu.tw/Project_Courses/ML/AntAlgo.pdf
http://bm.nsysu.edu.tw/tutorial/iylu/2008%20IQM/QT2_%C3%C6%B8s%BAt%BA%E2%AAk%A9%F3%A6v%B0t%B7~%B8%F4%BDu%B3%CC%A8%CE%A4%C6%A4%A7%AC%E3%A8s.pdf
http://ccckmit.wikidot.com/so:antcolony