{"id":498,"date":"2011-06-20T20:52:00","date_gmt":"2011-06-20T12:52:00","guid":{"rendered":"http:\/\/note.systw.net\/note\/?p=498"},"modified":"2023-11-02T20:54:38","modified_gmt":"2023-11-02T12:54:38","slug":"acs","status":"publish","type":"post","link":"https:\/\/systw.net\/note\/archives\/498","title":{"rendered":"ACS"},"content":{"rendered":"\n

Ant Algorithm(\u879e\u87fb\u6f14\u7b97\u6cd5)<\/strong>
1991\u5e74\u7531Dorigo\u9996\u6b21\u63d0\u51fa
1997\u5e74\u63d0\u51faACS(Ant Colony System)<\/strong>,\u4e5f\u70ba\u8f03\u7d93\u5178\u4e4b\u7248\u672c
\u4e00\u7a2e\u5c0b\u512a\u6f14\u7b97\u6cd5,\u539f\u7406\u70ba\u8cbb\u6d1b\u8499\u6a5f\u5236<\/p>\n\n\n\n

\u8cbb\u6d1b\u8499\u6a5f\u5236:
1.pheromone\u8a18\u61b6\u8207\u66f4\u65b0<\/strong>:\u4e5f\u5c31\u662f\u6b63\u5411\u53ca\u53cd\u5411\u53cd\u994b\u6a5f\u5236
\u5c07\u5e38\u8d70\u8def\u5f91\u4e4bpheromone\u8b8a\u5f37,\u4e0d\u5e38\u8d70\u8def\u5f91\u7684pheromone\u8b8a\u5f31,\u4e26\u5c07\u8f03\u597d\u8def\u5f91\u4e4bpheromone\u52a0\u5f37
2.\u6839\u64dapheromone\u6c7a\u5b9a\u8def\u5f91<\/strong>:\u4e5f\u5c31\u662f\u6a5f\u7387\u5c0b\u512a\u65b9\u6cd5
\u8a72\u8def\u5f91pheromone\u8d8a\u9ad8,\u9078\u64c7\u8a72\u8def\u5f91\u6a5f\u7387\u8d8a\u9ad8<\/p>\n\n\n\n


………………………………
\u4ee5\u4e0b\u898f\u5247\u4ee51997\u7248\u4e4bACS\u70ba\u4e3b<\/p>\n\n\n\n

\u53c3\u6578\u914d\u7f6e<\/strong>
n:\u7bc0\u9ede\u6578\u91cf
ant\u6578\u91cf,\u5efa\u8b70\u8a2d\u70ban
b:\u6c7a\u5b9apheromone\u548c\u8ddd\u96e2\u4e4b\u76f8\u5c0d\u91cd\u8981\u6027,\u901a\u5e38\u8a2d2
q0:\u70ba\u9078\u64c7\u63a2\u7d22\u6216\u8ffd\u8e64\u7684\u53c3\u6578,0p:\u7528\u65bc\u5340\u57df\u66f4\u65b0\u7684\u6b98\u7559\u7cfb\u6578,0a:\u7528\u65bc\u5168\u57df\u66f4\u65b0\u7684\u6b98\u7559\u7cfb\u6578,0T0:\u7528\u4f86\u7576\u4e00\u958b\u59cb\u521d\u8def\u5f91\u4e4bpheromone,\u4ee5\u53calocal update\u7684pheromone,\u5efa\u8b70\u8a2d(n*Lnn)^-1
ps:Lnn=nearest neighbor heuristic\u70ba\u6240\u6709\u7bc0\u9ede\u4e4b\u9593\u6700\u77ed\u8def\u5f91<\/p>\n\n\n\n

ant\u6b65\u9a5f<\/strong>
\u5927\u81f4\u5982\u4e0b
1 \u5404ant\u6839\u64dastate transi
tion rule\u6c7a\u5b9a\u4e0b\u4e00\u500b\u76ee\u5730,\u4f46\u8981\u907f\u958b\u4e4b\u524d\u8d70\u904e\u7684
2 \u5404ant\u5c0d\u525b\u8d70\u7684\u8def\u5f91\u9032\u884cpheromone local updating 3 \u8fd4\u56de\u6b65\u9a5f1\u76f4\u5230\u6240\u6709\u7bc0\u9ede\u90fd\u5b8c\u6210
4 \u6311\u9078\u6700\u4f73\u8def\u5f91\u9032\u884cpheromone global updating
5 \u6e05\u7a7a\u672c\u6b21ant\u8def\u5f91
6 \u8fd4\u56de\u6b65\u9a5f1\u76f4\u5230\u7d42\u6b62\u689d\u4ef6
ps:\u7d42\u6b62\u689d\u4ef6
\u901a\u5e38\u8a2d\u70ba\u6700\u5927\u4e16\u4ee3\u6578,\u4f8b\u5982500
\u6216\u662f\u5230\u6700\u5f8c\u6bcf\u500b\u4e16\u4ee3\u7684\u89e3\u90fd\u76f8\u540c\u6642<\/p>\n\n\n\n

\u7a0b\u5f0f\u78bc\u5927\u81f4\u5982\u4e0b
while(terminal){\/\/\u672a\u9054\u7d42\u6b62\u689d\u4ef6\u4e0b\u4e0d\u65b7\u91cd\u8907\u57f7\u884c
\u3000while(untraved){ \/\/\u5c07\u5404\u7bc0\u9ede\u90fd\u8d70\u904e
\u3000\u3000while(ant){ \/\/\u5404ant\u57f7\u884cstate_transiton\u6c7a\u5b9a\u8def\u5f91
\u3000\u3000\u3000state_transition();
\u3000\u3000}
\u3000\u3000pheromone_local_update; \/\/\u6bcf\u8d70\u904e\u4e00\u500b\u7bc0\u9ede\u5c31\u66f4\u65b0\u5169\u9ede\u4e4b\u9593pheromone
\u3000}
\u3000pheromone_global_update \/\/\u5168\u90e8\u7bc0\u9ede\u8d70\u5b8c\u5f8c\u627e\u51fa\u6700\u597d\u8def\u5f91,\u4e26\u53ea\u66f4\u65b0\u8a72\u8def\u5f91pheromone
}<\/p>\n\n\n\n


State Transition Rule<\/strong>
q0\u70ba\u9078\u64c7\u63a2\u7d22\u6216\u8ffd\u8e64\u7684\u53c3\u6578
q\u70ba\u7cfb\u7d71\u7522\u751f\u4e4b\u96a8\u6a5f\u6578,0 < q < \uff11 
\u82e5q>q0<\/strong>\u5247\u6839\u64da\u4ee5\u4e0b\u53d6\u6700\u5927\u503c,\u6c7a\u5b9a\u7684\u76ee\u5730
MAX(ph_rs*n_rs^b)<\/strong>
ps:b\u662fdetermines the relative importance of pheromone versus distance,\u901a\u5e38\u8a2d2
\u82e5qpb_rs=ph(r,s)*n(r,s)^b \/ sum(ph(r,u)*n(r,u)^b)<\/strong>
ph(r,s)=\u5f9er\u5230s\u7684pheromone
ph(r,u)=\u5f9er\u5230u\u7684pheromone
n(r,s)=\u5f9er\u5230s\u7684local heuristic,\u901a\u5e38\u70ba1\/distance_rs
n(r,u)=\u5f9er\u5230u\u7684local heuristic
b=\u540c\u4e0a
\u6ce8\u610f:u\u662f\u672a\u5230\u8a2a\u7684\u7bc0\u9ede,r\u662f\u51fa\u767c\u7bc0\u9ede,s\u662f\u67d0\u500b\u76ee\u5730\u7684\u9ede<\/p>\n\n\n\n


\u5340\u57df\u66f4\u65b0\u8cbb\u6d1b\u8499<\/strong>
pheromone local updating<\/strong>
\u7528\u5728\u5340\u57df,\u6bcf\u8d70\u4e00\u500b\u7bc0\u9ede\u66f4\u65b0\u4e00\u6b21
\u516c\u5f0f\u70ba:ph(r,s)+=(1-p)ph(r,s)+(p)ph_add(r,s)<\/strong>
where ph_add(r,s)=init-pheromone<\/strong>\u3000,\u4ee5\u521d\u59cbpheromone\u505a\u503c
\u53c3\u6578\u6709\u4ee5\u4e0b
p=\u6b98\u7559\u7cfb\u6578
ph(r,s)=\u8a72\u8def\u5f91(r\u5230s)\u76ee\u524d\u7684pheromone
ph_add(r,s)=\u7576\u8a72\u8def\u5f91(r\u5230s)\u88ab\u8d70\u904e\u6642,\u9700\u589e\u52a0pheromone\u7684\u91cf,\u82e5\u8a72\u8def\u5f91\u9019\u6b21\u6c92\u88ab\u8d70\u904e\u5247\u503c\u70ba0<\/p>\n\n\n\n

\u5168\u57df\u66f4\u65b0\u8cbb\u6d1b\u8499<\/strong>
pheromone global updating<\/strong>
\u7528\u5728\u5168\u57df,\u8d70\u5b8c\u5168\u90e8\u7bc0\u9ede\u5728\u66f4\u65b0\u6700\u597d\u8def\u5f91\u4e0a\u7684pheromone
\u516c\u5f0f\u70ba:ph(r,s)+=(1-a)ph(r,s)+(a)ph_add(r,s)<\/strong>
where ph_add(r,s)= best_L^-1<\/strong> , best_L\u70ba\u6700\u597d\u7684\u8def\u5f91\u9577\u5ea6
\u53c3\u6578\u6709\u4ee5\u4e0b
a=pheromone decay parameter,0ph(r,s)\u540c\u4e0a
ph_add(r,s)\u540c\u4e0a<\/p>\n\n\n\n

…………………………………………………………………….<\/p>\n\n\n\n

\/\/\u4f7f\u7528\u7684\u8b8a\u6578\u5982\u4e0b
nodeall=\u6240\u6709\u7bc0\u9ede\u6578
t.max=\u6b32\u57f7\u884c\u7684\u6b21\u6578<\/p>\n\n\n\n

map_d
\/\/2\u7dad\u9663\u5217\u578b\u614b,\u4ee3\u8868\u5404\u7bc0\u9ede\u4e4bdistance
\/\/map_d=map<\/p>\n\n\n\n

map_h
\/\/2\u7dad\u9663\u5217\u578b\u614b,\u4ee3\u8868\u5404\u7bc0\u9ede\u4e4bheuristic
\/\/map_h=map<\/p>\n\n\n\n

ph
\/\/2\u7dad\u9663\u5217\u578b\u614b,\u8a18\u9304\u5404\u8def\u5f91\u7684\u8cbb\u6d1b\u8499
\/\/ph=map
\/\/ex:\u5f9ea\u7bc0\u9ede\u5230b\u7bc0\u9ede\u7684\u8cbb\u6d1b\u8499\u70ba0.2
\/\/ph[a][b]=0.2<\/p>\n\n\n\n

antpath
\/\/2\u7dad\u9663\u5217\u578b\u614b,\u8a18\u9304\u5404ant\u8def\u5f91
\/\/antpath[ant_k][step]=node
\/\/ ex:\u7b2c1\u96bbant\u8d70\u7684\u8def\u5f91\u70baabdc,\u5247\u8a18\u9304\u5982\u4e0b
\/\/antpath[1]={a,b,d,c}<\/p>\n\n\n\n

\/\/\u6f14\u7b97\u6cd5\u5982\u4e0b
while(t\u3000for(node=0;node\u3000\u3000pb=path_probability(ph);
\u3000\u3000\/\/\u6839\u64da\u516c\u5f0f(\u8cbb\u6d1b\u8499\u53ca\u5404node\u76f8\u9023\u4e4b\u6210\u672c)\u7522\u751f\u5404node\u53bb\u4e0d\u540cnode\u7684\u6a5f\u7387
\u3000\u3000dest=ant_decision(pb);
\u3000\u3000\/\/\u6839\u64da\u6a5f\u7387\u4e26\u900f\u904e\u65b9\u6cd5\u6c7a\u5b9a\u5728\u591a\u500b\u76ee\u5730\u6642\u61c9\u9078\u64c7\u90a3\u4e00\u500b\u76ee\u5730
\u3000\u3000antpath=antpath_update(dest);
\u3000\u3000\/\/\u66f4\u65b0ant\u8def\u5f91\u8868\u4ee5\u8868\u793aant\u79fb\u52d5\u7684\u72c0\u6cc1
\u3000\u3000ph=pheromone_update_local(antpath);
\u3000\u3000\/\/\u6839\u64da\u5be6\u969b\u53bb\u7684node,\u91cd\u65b0\u8a08\u7b97\u8cbb\u6d1b\u8499\u7684\u503c
\u3000}
ph=pheromone_update_global(antpath);
ph=pheromone_update_global_best(antpath);
best=selectbest_antpath(antpath); \/\/\u5f9e\u5404ant\u5be6\u969b\u8d70\u7684\u8def\u5f91\u4e2d\u9078\u64c7\u6700\u597d\u7684\u8def\u5f91
}<\/p>\n\n\n\n

<\/p>\n\n\n\n

…………………………………………………………………….<\/p>\n\n\n\n

acs for php example<\/p>\n\n\n\n

\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\/\/\/\/\/\/\/\/ acs usage description \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\/*\n1.acs() need \"map distance\" data and array named as \"$para['map_d']\", as follow\n$para['map_d']=array(\n'1'=>array('1'=>0,'2'=>3,'3'=>5,'4'=>5),\n'2'=>array('1'=>3,'2'=>0,'3'=>4,'4'=>6),\n'3'=>array('1'=>5,'2'=>4,'3'=>0,'4'=>2),\n'4'=>array('1'=>5,'2'=>6,'3'=>2,'4'=>0));\n\n2.acs($para) will return acs result with the array representation ,refer to function evaluate()\n$result_array=acs($para);\n*\/\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/ acs example as follow \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\/\/phase 1\n\/\/read data\n$inputdata = file('map.txt'); \/\/in the each line of map.txt` is x,y\nwhile($line=each($inputdata)){\n\u00a0 $i++;\n\u00a0 $tmp=explode(',',$line['value']);\n\u00a0 $node[$i]['x']=trim($tmp[0]);\n\u00a0 $node[$i]['y']=trim($tmp[1]);\n}\n$nodecount=count($node);\nfor($i=1;$i<=$nodecount;$i++){\n\u00a0 for($j=1;$j<=$nodecount;$j++){\n\u00a0 \u00a0 $map_d[$i][$j]=0;\n\u00a0 \u00a0 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) ));\n\u00a0 }\n}\n$para['map_d']=$map_d; \/\/ data for acs()\n\/\/$para['node_xy']=$node; \/\/the data for graph()\n\n\/\/phase 2\n\/\/excute acs\n$para['antpath_value']=acs($para);\necho 'global best='.$para['antpath_value']['sumbest_global'].'< br>';\ngraph($para['antpath_value']['pathbest_global'],$node);\n\/\/\/\/\/\/\/\/\/\/\/ acs example end \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\/\/\/\/\/\/\/\/ main function \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction acs($para){\n$para['a']=0.1;\/\/0$para['b']=2;\/\/relative importance of local heuristic or pheromone\n$para['p']=0.1;\/\/trail evaporates,the value must is < 1\n$para['q0']=0.9;\/\/explorse or tracking $para['gn']=100;\/\/generation number\n$para['gn']=500;\/\/generation number\n\n$para['node']=count($para['map_d']);\/\/node sum\n$para['ant']=$para['node'];\/\/ant sum\n$para['initph']=(1\/($para['node']*nearest_neighbor_heuristic($para)));\n$para['map_h']=init('map_h',$para);\n$para['map_hb']=init('map_hb',$para);\n$para['ph']=init('ph',$para);\/\/init pheromone by random\n\nwhile($t<$para['gn']){\n\u00a0 $t++;\n\u00a0 $para['antpath']=init('antpath',$para);\n\u00a0 $para['unvisited']=init('unvisited',$para);\n\u00a0 for($i=0;$i<$para['node'];$i++){\n\u00a0 \u00a0 $para['unvisited']=unvisitednode($para);\n\u00a0 \u00a0 reset($para['antpath']);\n\u00a0 \u00a0 \u00a0 while($ant=each($para['antpath'])){\n\u00a0 \u00a0 \u00a0 \u00a0 $para['antpath'][$ant[0]][]=state_transition($ant[0],$para);\n\u00a0 \u00a0 \u00a0 }\n\u00a0 \u00a0 $para['ph']=pheromone_update($para);\n\u00a0 }\n\u00a0 $para['antpath_value']=evaluate($para);\n\u00a0 $para['ph']=pheromone_update_global($para);\n}\n\nreturn $para['antpath_value'];\n\n}\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\/\/\/\/\/\/\/\/ sub function \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction nearest_neighbor_heuristic($para){\nfor($i=1;$i<=$para['node'];$i++){\n\u00a0 $traved[$i]=0;\n}\n\n$path[]=1;\n$traved[1]=1;\nwhile(array_sum($traved)<$para['node']){\n\u00a0 $start=end($path);\n\u00a0 reset($traved);\n\u00a0 $distance=null;\n\u00a0 while($d=each($traved)){\n\u00a0 \u00a0 $dst=$d[0];\n\u00a0 \u00a0 if($d[1]!=1){\n\u00a0 \u00a0 \u00a0 $distance[$dst]=$para['map_d'][$start][$dst];\n\u00a0 \u00a0 }\n\u00a0 }\n\u00a0 asort($distance);\n\u00a0 $n=each($distance);\n\u00a0 $traved[$n[0]]=1;\n\u00a0 $path[]=$n[0];\n\u00a0 $length[]=$n[1];\n}\n$start=end($path);\nreset($traved);\n$distance=null;\nwhile($d=each($traved)){\n\u00a0 $dst=$d[0];\n\u00a0 if($d[1]!=1){\n\u00a0 \u00a0 $distance[$dst]=$para['map_d'][$start][$dst];\n\u00a0 \u00a0 $traved[$dst]=1;\n\u00a0 \u00a0 $path[]=$dst;\n\u00a0 \u00a0 $length[]=$distance[$dst];\n\u00a0 }\n}\n\n$totallength=array_sum($length);\nreturn $totallength;\n}\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction init($type,$para){\nif($type=='antpath'){\n\u00a0 for($i=1;$i<=$para['ant'];$i++){\n\u00a0 \u00a0 $antpath[$i][]=$i;\n\u00a0 }\n\u00a0 return $antpath;\n}\n\nif($type=='unvisited'){\n\u00a0 for($i=1;$i<=$para['ant'];$i++){\n\u00a0 \u00a0 $n=1;\n\u00a0 \u00a0 while($n<=$para['node']){$unvisited[$i][]=$n++;}\n\u00a0 }\n\u00a0 return $unvisited;\n}\n\n\/\/compute heuristic(1\/distance=heuristic)\nif($type=='map_h' or $type=='ph' or $type=='map_hb'){\n\u00a0 while($i=each($para['map_d'])){\n\u00a0 \u00a0 while($j=each($i['value'])){\n\u00a0 \u00a0 \u00a0 if($j['value']){\n\u00a0 \u00a0 \u00a0 \u00a0 $map_h[$i['key']][$j['key']]=1\/$j['value'];\n\u00a0 \u00a0 \u00a0 \u00a0 $map_hb[$i['key']][$j['key']]=pow($map_h[$i['key']][$j['key']],$para['b']);\n\u00a0 \u00a0 \u00a0 \u00a0 $ph[$i['key']][$j['key']]=$para['initph'];\n\u00a0 \u00a0 \u00a0 }else{\n\u00a0 \u00a0 \u00a0 \u00a0 $map_h[$i['key']][$j['key']]=0;\n\u00a0 \u00a0 \u00a0 \u00a0 $map_hb[$i['key']][$j['key']]=0;\n\u00a0 \u00a0 \u00a0 \u00a0 $ph[$i['key']][$j['key']]=0;\n\u00a0 \u00a0 \u00a0 }\n\u00a0 \u00a0 }\n\u00a0 }\n}\nif($type=='map_h'){return $map_h;}\nif($type=='map_hb'){return $map_hb;}\nif($type=='ph'){return $ph;}\n\n}\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction unvisitednode($para){\nwhile($ant=each($para['antpath'])){\n\u00a0 $lastnode=end($para['antpath'][$ant[0]]);\n\u00a0 \u00a0 while($u=each($para['unvisited'][$ant[0]])){\n\u00a0 \u00a0 \u00a0 if($u[1]!=$lastnode)$unvisited_new[$ant[0]][]=$u[1];\n\u00a0 \u00a0 }\n\u00a0 }\nreturn $unvisited_new;\n}\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction state_transition($k,$para){\n$r=end($para['antpath'][$k]);\n\n$dstcount=count($para['unvisited'][$k]);\nif($dstcount<1){$antdest[$k]=$para['antpath'][$k][0];}\nif($dstcount==1){\n\u00a0 $lastdst=each($para['unvisited'][$k]);\n\u00a0 $antdest[$k]=$lastdst[1];\n}\nif($dstcount>1){\n\n\/\/computer state value\n\u00a0 $u_pb_sum=0;\n\u00a0 while($unvisited=each($para['unvisited'][$k])){\n\u00a0 $u=$unvisited[1];\n\u00a0 $u_pb_each[$u]=$para['ph'][$r][$u]*$para['map_hb'][$r][$u];\n}\n\n\/\/select explore or tracked by q0\n$q=rand(0,100)\/100;\nif($q<=$para['q0']){\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/select best pheromone dest start\n\u00a0 $ph_comp=$u_pb_each;\n\u00a0 arsort($ph_comp);\n\u00a0 $dstary=each($ph_comp);\n\u00a0 $antdest[$k]=$dstary[0];\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/select best pheromone dest end\n}else{\n\/\/\/\/\/\/\/\/\/\/\/\/\/random select dest by probability start\n\u00a0 $u_pb_sum=array_sum($u_pb_each);\n\u00a0 while($s=each($u_pb_each)){\n\u00a0 \u00a0 if($s[1]!=0){\n\u00a0 \u00a0 \u00a0 $pb[$r][$s[0]]=$s[1]\/$u_pb_sum;\n\u00a0 \u00a0 }else{\n\u00a0 \u00a0 \u00a0 $pb[$r][$s[0]]=0;\n\u00a0 \u00a0 }\n\u00a0 }\n\/\/select\n\u00a0 $pbsum=array_sum($pb[$r]);\n\u00a0 $selectpoint=(rand(0,$pbsum*10000)\/10000);\n\u00a0 while($s=each($pb[$r])){\n\u00a0 \u00a0 $nowposition+=$s[1];\n\u00a0 \u00a0 if($nowposition>=$selectpoint){\n\u00a0 \u00a0 \u00a0$antdest[$k]=$s[0];\n\u00a0 \u00a0 \u00a0break;\n\u00a0 \u00a0}\n\u00a0 }\n\/\/\/\/\/\/\/\/\/\/\/\/\/random select dest by probability end\n}\n\n}\n\nreturn $antdest[$k];\n}\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction pheromone_update($para){\nreset($para['antpath']);\nwhile($ant=each($para['antpath'])){\n\u00a0 $j=end($para['antpath'][$ant[0]]);\n\u00a0 $i=prev($para['antpath'][$ant[0]]);\n\u00a0 $ph_add[$i][$j]=$para['initph'];\n\u00a0 $ph_add_tmp=0;\n\n\/\/have only traveled update\n\u00a0 $para['ph'][$i][$j]=(1-$para['p'])*$para['ph'][$i][$j]+$para['p']*$ph_add[$i][$j];\n}\nreturn $para['ph'];\n}\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction pheromone_update_global($para){\n$ph_add=pow($para['antpath_value']['sumbest_global'],-1);\nwhile($node=each($para['antpath_value']['pathbest_global'])){\n\u00a0 if($i!=null){\n\u00a0 \u00a0 $j=$node[1];\n\u00a0 \u00a0 $para['ph'][$i][$j]=(1-$para['a'])*$para['ph'][$i][$j]+$para['a']*$ph_add;\n\u00a0 }\n\u00a0 $i=$node[1];\n}\nreturn $para['ph'];\n}\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction evaluate($para){\n$antpath_value=$para['antpath_value'];\n$antpath_value['unit']=null;\nwhile($ant=each($para['antpath'])){\n\u00a0 $i=null;\n\u00a0 $j=null;\n\u00a0 while($path=each($ant['value'])){\n\u00a0 \u00a0 if($i!=null){\n\u00a0 \u00a0 \u00a0 $j=$path['value'];\n\u00a0 \u00a0 \u00a0 $antpath_value['unit'][$ant['key']][]=$para['map_d'][$i][$j];\n\u00a0 \u00a0 }\n\u00a0 \u00a0 $i=$path['value'];\n\u00a0 }\n$antpath_value['sum'][$ant['key']]=array_sum($antpath_value['unit'][$ant['key']]);\n}\n\nasort($antpath_value['sum']);\n$bestdata=each($antpath_value['sum']);\n$bestant=$bestdata[0];\n$antpath_value['sumbest']=$bestdata[1];\n$antpath_value['pathbest']=$para['antpath'][$bestant];\n$antpath_value['sumbest_history'][]=$antpath_value['sumbest'];\n\nif($antpath_value['sumbest_global']==null or $antpath_value['sumbest_global']>$antpath_value['sumbest']){\n\u00a0 $antpath_value['sumbest_global']=$antpath_value['sumbest'];\n\u00a0 $antpath_value['pathbest_global']=$antpath_value['pathbest'];\n}\n$antpath_value['sumbest_global_history'][]=$antpath_value['sumbest_global'];\n\n\/*\n$antpath_value['unit'] array ,each ant each cost of path node\n$antpath_value['sum'] array ,each ant sum cost of path node\n$antpath_value['pathbest'] array\n$antpath_value['sumbest'] int\n$antpath_value['sumbest_history'] array\n$antpath_value['pathbest_global'] array\n$antpath_value['sumbest_global'] int\n$antpath_value['sumbest_global_history'] array\n*\/\n\necho $antpath_value['sumbest_global'].\",\";\n\nreturn $antpath_value;\n}\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\/\/\/\/\/\/\/\/\/\/ optional \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction caclutime(){\n$time = explode( \" \", microtime());\n$usec = (double)$time[0];\n$sec = (double)$time[1];\nreturn $sec + $usec;\n}\n\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\nfunction graph($path,$node_xy){\n\/\/$path=$data['antpath_value']['pathbest_global'];\n\/\/$node_xy=$data['node_xy'];\n$im = imagecreate(500,500);\n$green = imagecolorallocate($im,214,235,214);\n$black = imagecolorallocate ($im, 0, 0, 0);\n$count=count($path)-1;\nfor($i=0;$i<$count;$i++){\n\u00a0 $ix=$node_xy[$path[$i]]['x']*5;\n\u00a0 $iy=$node_xy[$path[$i]]['y']*5;\n\u00a0 $jx=$node_xy[$path[$i+1]]['x']*5;\n\u00a0 $jy=$node_xy[$path[$i+1]]['y']*5;\n\u00a0 imageline($im,$ix,$iy,$jx,$jy,$black);\n}\nimagepng($im, \"a.png\");\necho \"< img src='a.png' >\";\nimagedestroy($im);\n}<\/code><\/pre>\n\n\n\n

………………………………………………………………………..<\/p>\n\n\n\n

\u5176\u4ed6\u53ef\u53c3\u8003\u7684\u6587\u737b
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<\/p>\n","protected":false},"excerpt":{"rendered":"
Ant Algorithm(\u879e\u87fb\u6f14\u7b97\u6cd5)1991\u5e74\u7531Dori …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"","fifu_image_alt":"","_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[13],"tags":[],"class_list":["post-498","post","type-post","status-publish","format-standard","hentry","category-dataanalysis"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/498","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/comments?post=498"}],"version-history":[{"count":0,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/498\/revisions"}],"wp:attachment":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/media?parent=498"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/categories?post=498"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/tags?post=498"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}