最近由于畢設(shè)在研究OMNet++,一頭霧水，主要過去學(xué)習(xí)不認(rèn)真，現(xiàn)在發(fā)現(xiàn)不但新知識(shí)學(xué)習(xí)的亂七八糟，主要是過去的東西也亂七八糟，所以學(xué)習(xí)和人生都是一個(gè)慢慢積累慢慢豐富的過程。
發(fā)現(xiàn)了個(gè)螞蟻算法，相關(guān)內(nèi)容附上，做個(gè)筆記。
蟻群算法(ant colony optimization, ACO)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型技術(shù)。它由Marco Dorigo于1992年在他的博士論文中引入，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。
為什么小小的螞蟻能夠找到食物？他們具有智能么？設(shè)想，如果我們要為螞蟻設(shè)計(jì)一個(gè)人工智能的程
序，那么這個(gè)程序要多么復(fù)雜呢？首先，你要讓螞蟻能夠避開障礙物，就必須根據(jù)適當(dāng)?shù)牡匦谓o它編進(jìn)指令讓他們能夠巧妙的避開障礙物，其次，要讓螞蟻找到食
物，就需要讓他們遍歷空間上的所有點(diǎn)；再次，如果要讓螞蟻找到最短的路徑，那么需要計(jì)算所有可能的路徑并且比較它們的大小，而且更重要的是，你要小心翼翼
的編程，因?yàn)槌绦虻腻e(cuò)誤也許會(huì)讓你前功盡棄。這是多么不可思議的程序！太復(fù)雜了，恐怕沒人能夠完成這樣繁瑣冗余的程序。
然而，事實(shí)并沒有你想得那么復(fù)雜，上面這個(gè)程序每個(gè)螞蟻的核心程序編碼不過100多行！為什么
這么簡單的程序會(huì)讓螞蟻干這樣復(fù)雜的事情？答案是：簡單規(guī)則的涌現(xiàn)。事實(shí)上，每只螞蟻并不是像我們想象的需要知道整個(gè)世界的信息，他們其實(shí)只關(guān)心很小范圍
內(nèi)的眼前信息，而且根據(jù)這些局部信息利用幾條簡單的規(guī)則進(jìn)行決策，這樣，在蟻群這個(gè)集體里，復(fù)雜性的行為就會(huì)凸現(xiàn)出來。這就是人工生命、復(fù)雜性科學(xué)解釋的
規(guī)律！那么，這些簡單規(guī)則是什么呢？下面詳細(xì)說明：
1、范圍：
螞蟻觀察到的范圍是一個(gè)方格世界，螞蟻有一個(gè)參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個(gè)方格世界，并且能移動(dòng)的距離也在這個(gè)范圍之內(nèi)。
2、環(huán)境：
螞蟻所在的環(huán)境是一個(gè)虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個(gè)螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息。環(huán)境以一定的速率讓信息素消失。
3、覓食規(guī)則：
在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過去。否則看是否有信息素，并且比較在
能感知的范圍內(nèi)哪一點(diǎn)的信息素最多，這樣，它就朝信息素多的地方走，并且每只螞蟻多會(huì)以小概率犯錯(cuò)誤，從而并不是往信息素最多的點(diǎn)移動(dòng)。螞蟻找窩的規(guī)則和
上面一樣，只不過它對(duì)窩的信息素做出反應(yīng)，而對(duì)食物信息素沒反應(yīng)。
4、移動(dòng)規(guī)則：
每只螞蟻都朝向信息素最多的方向移，并且，當(dāng)周圍沒有信息素指引的時(shí)候，螞蟻會(huì)按照自己原來運(yùn)
動(dòng)的方向慣性的運(yùn)動(dòng)下去，并且，在運(yùn)動(dòng)的方向有一個(gè)隨機(jī)的小的擾動(dòng)。為了防止螞蟻原地轉(zhuǎn)圈，它會(huì)記住最近剛走過了哪些點(diǎn)，如果發(fā)現(xiàn)要走的下一點(diǎn)已經(jīng)在最近
走過了，它就會(huì)盡量避開。
5、避障規(guī)則：
如果螞蟻要移動(dòng)的方向有障礙物擋住，它會(huì)隨機(jī)的選擇另一個(gè)方向，并且有信息素指引的話，它會(huì)按照覓食的規(guī)則行為。
7、播撒信息素規(guī)則：
每只螞蟻在剛找到食物或者窩的時(shí)候撒發(fā)的信息素最多，并隨著它走遠(yuǎn)的距離，播撒的信息素越來越少。
根據(jù)這幾條規(guī)則，螞蟻之間并沒有直接的關(guān)系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過信息素這個(gè)
紐帶，實(shí)際上把各個(gè)螞蟻之間關(guān)聯(lián)起來了。比如，當(dāng)一只螞蟻找到了食物，它并沒有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當(dāng)其它的螞蟻經(jīng)過它附
近的時(shí)候，就會(huì)感覺到信息素的存在，進(jìn)而根據(jù)信息素的指引找到了食物。
說了這么多，螞蟻究竟是怎么找到食物的呢？
在沒有螞蟻找到食物的時(shí)候，環(huán)境沒有有用的信息素，那么螞蟻為什么會(huì)相對(duì)有效的找到食物呢？這
要?dú)w功于螞蟻的移動(dòng)規(guī)則，尤其是在沒有信息素時(shí)候的移動(dòng)規(guī)則。首先，它要能盡量保持某種慣性，這樣使得螞蟻盡量向前方移動(dòng)（開始，這個(gè)前方是隨機(jī)固定的一
個(gè)方向），而不是原地?zé)o謂的打轉(zhuǎn)或者震動(dòng)；其次，螞蟻要有一定的隨機(jī)性，雖然有了固定的方向，但它也不能像粒子一樣直線運(yùn)動(dòng)下去，而是有一個(gè)隨機(jī)的干擾。
這樣就使得螞蟻運(yùn)動(dòng)起來具有了一定的目的性，盡量保持原來的方向，但又有新的試探，尤其當(dāng)碰到障礙物的時(shí)候它會(huì)立即改變方向，這可以看成一種選擇的過程，
也就是環(huán)境的障礙物讓螞蟻的某個(gè)方向正確，而其他方向則不對(duì)。這就解釋了為什么單個(gè)螞蟻在復(fù)雜的諸如迷宮的地圖中仍然能找到隱蔽得很好的食物。
當(dāng)然，在有一只螞蟻找到了食物的時(shí)候，其他螞蟻會(huì)沿著信息素很快找到食物的。
螞蟻如何找到最短路徑的？這一是要?dú)w功于信息素，另外要?dú)w功于環(huán)境，具體說是計(jì)算機(jī)時(shí)鐘。信息
素多的地方顯然經(jīng)過這里的螞蟻會(huì)多，因而會(huì)有更多的螞蟻聚集過來。假設(shè)有兩條路從窩通向食物，開始的時(shí)候，走這兩條路的螞蟻數(shù)量同樣多（或者較長的路上螞
蟻多，這也無關(guān)緊要）。當(dāng)螞蟻沿著一條路到達(dá)終點(diǎn)以后會(huì)馬上返回來，這樣，短的路螞蟻來回一次的時(shí)間就短，這也意味著重復(fù)的頻率就快，因而在單位時(shí)間里走
過的螞蟻數(shù)目就多，灑下的信息素自然也會(huì)多，自然會(huì)有更多的螞蟻被吸引過來，從而灑下更多的信息素……；而長的路正相反，因此，越來越多地螞蟻聚集到較短
的路徑上來，最短的路徑就近似找到了。也許有人會(huì)問局部最短路徑和全局最短路的問題，實(shí)際上螞蟻逐漸接近全局最短路的，為什么呢？這源于螞蟻會(huì)犯錯(cuò)誤，也
就是它會(huì)按照一定的概率不往信息素高的地方走而另辟蹊徑，這可以理解為一種創(chuàng)新，這種創(chuàng)新如果能縮短路途，那么根據(jù)剛才敘述的原理，更多的螞蟻會(huì)被吸引過
來。
引申:
跟著螞蟻的蹤跡，你找到了什么？通過上面的原理敘述和實(shí)際操作，我們不難發(fā)現(xiàn)螞蟻之所以具有智能行為，完全歸功于它的簡單行為規(guī)則，而這些規(guī)則綜合起來具有下面兩個(gè)方面的特點(diǎn)：
1、多樣性
2、正反饋
多樣性保證了螞蟻在覓食的時(shí)候不置走進(jìn)死胡同而無限循環(huán)，正反饋機(jī)制則保證了相對(duì)優(yōu)良的信息能
夠被保存下來。我們可以把多樣性看成是一種創(chuàng)造能力，而正反饋是一種學(xué)習(xí)強(qiáng)化能力。正反饋的力量也可以比喻成權(quán)威的意見，而多樣性是打破權(quán)威體現(xiàn)的創(chuàng)造
性，正是這兩點(diǎn)小心翼翼的巧妙結(jié)合才使得智能行為涌現(xiàn)出來了。
引申來講，大自然的進(jìn)化，社會(huì)的進(jìn)步、人類的創(chuàng)新實(shí)際上都離不開這兩樣?xùn)|西，多樣性保證了系統(tǒng)
的創(chuàng)新能力，正反饋保證了優(yōu)良特性能夠得到強(qiáng)化，兩者要恰到好處的結(jié)合。如果多樣性過剩，也就是系統(tǒng)過于活躍，這相當(dāng)于螞蟻會(huì)過多的隨機(jī)運(yùn)動(dòng)，它就會(huì)陷入
混沌狀態(tài)；而相反，多樣性不夠，正反饋機(jī)制過強(qiáng)，那么系統(tǒng)就好比一潭死水。這在蟻群中來講就表現(xiàn)為，螞蟻的行為過于僵硬，當(dāng)環(huán)境變化了，螞蟻群仍然不能適
當(dāng)?shù)恼{(diào)整。
既然復(fù)雜性、智能行為是根據(jù)底層規(guī)則涌現(xiàn)的，既然底層規(guī)則具有多樣性和正反饋特點(diǎn)，那么也許你
會(huì)問這些規(guī)則是哪里來的？多樣性和正反饋又是哪里來的？我本人的意見：規(guī)則來源于大自然的進(jìn)化。而大自然的進(jìn)化根據(jù)剛才講的也體現(xiàn)為多樣性和正反饋的巧妙
結(jié)合。而這樣的巧妙結(jié)合又是為什么呢？為什么在你眼前呈現(xiàn)的世界是如此栩栩如生呢？答案在于環(huán)境造就了這一切，之所以你看到栩栩如生的世界，是因?yàn)槟切┎?
能夠適應(yīng)環(huán)境的多樣性與正反饋的結(jié)合都已經(jīng)死掉了，被環(huán)境淘汰了！
參數(shù)說明：
最大信息素：螞蟻在一開始擁有的信息素總量，越大表示程序在較長一段時(shí)間能夠存在信息素。信息素消減的速度：隨著時(shí)間的流逝，已經(jīng)存在于世界上的信息素會(huì)消減，這個(gè)數(shù)值越大，那么消減的越快。
錯(cuò)誤概率表示這個(gè)螞蟻不往信息素最大的區(qū)域走的概率，越大則表示這個(gè)螞蟻越有創(chuàng)新性。
速度半徑表示螞蟻一次能走的最大長度，也表示這個(gè)螞蟻的感知范圍。
記憶能力表示螞蟻能記住多少個(gè)剛剛走過點(diǎn)的坐標(biāo)，這個(gè)值避免了螞蟻在本地打轉(zhuǎn)，停滯不前。而這個(gè)值越大那么整個(gè)系統(tǒng)運(yùn)行速度就慢，越小則螞蟻越容易原地轉(zhuǎn)圈。
-----例子-----
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML
1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"><HEAD>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
<title>蟻群算法js版</title>
<style>
.ant{
position:absolute;
background-color:#000000;
overflow:hidden;
width:2px;
height:2px;
}
.food{
position:absolute;
background-color:#0000ff;
overflow:hidden;
width:2px;
height:2px;
}
.nest{
position:absolute;
background-color:#ff0000;
overflow:hidden;
width:2px;
height:2px;
}
</style>
<script type="text/JavaScript">
//============================
//系統(tǒng)參數(shù)初始化
//----------------------------
//生命體數(shù)量與軌跡長度
Unit=10;Path=30;
//生命體速度上下限
v0=2;vM=10;
//生命體加速度變化范圍
Kr=0.1;Kv=0.1*(vM-v0);
//生命體運(yùn)動(dòng)范圍
x0=0;xM=document.documentElement.clientWidth;
y0=0;yM=document.documentElement.clientHeight;
//生命體出生地(巢穴)
xi0=x0+(xM-x0)*Math.random();
yi0=y0+(yM-y0)*Math.random();
str0='<div class="ant" style="left:'+xi0+';top:'+yi0+';"></div>';
//食物所在地
xf=x0+(xM-x0)*Math.random();
yf=y0+(yM-y0)*Math.random();
//氣味感知范圍
R_2=5*5;
//============================
var r=new Array();
var v=new Array();
var dr=new Array();
var dv=new Array();
var x=new Array();
var y=new Array();
var life=new Array();
//單擊暫停
var xi0,yi0,xf,yf;
var Time0,str0;
window.status='pause';
function document.onclick(){
if(window.status=='pause'){
window.status=0;
nest.style.left=xi0;
nest.style.top=yi0;
food.style.left=xf;
food.style.top=yf;
//測試初始化時(shí)間用
Time0=(new Date()).getTime();
init(0);
}else{
window.status='pause';
}
}
//窗口大小調(diào)整后刷新頁面以調(diào)整系統(tǒng)參數(shù)
function window.onresize(){
// window.location.href=document.location;
}
//初始化函數(shù)
function init(i){
if(window.status!='pause'&&i<Unit){
if(!life
){
document.body.appendChild(life=document.createElement(str0));
x=xi0;
y=yi0;
r=Math.random();
v=1/Math.random();
dr=Kr*Math.random();
dv=Kv*Math.random();
}
Move(i);
window.status=i+1;
setTimeout('init('+(i+1)+')',i);
// }else{
// alert('生成耗時(shí)：'+((new Date()).getTime()-Time0)+'ms');
}
}
//運(yùn)動(dòng)函數(shù)
Total=Unit*Path;
P2=2*Math.PI;
function Move(i){
if(window.status!='pause'){
k=i%Unit;
X=x[k];
Y=y[k];
R=r[k];
V=v[k];
if(!life){
str='<div class="ant" style="left:'+X+';top:'+Y+';"></div>';
document.body.appendChild(life=document.createElement(str));
}
obj=life;
R+=dr[k]*(2*Math.random()-1);
V+=dv[k]*(2*Math.random()-1);
X+=Math.sin(P2*R)*V;
Y+=Math.cos(P2*R)*V;
//遇到食物原路返回并減小角度變化
distance=(X-xf)*(X-xf)+(Y-yf)*(Y-yf);
if(distance<R_2){
R+=0.5;
r/=2;
v*=2;
}
distance=(X-xi0)*(X-xi0)+(Y-yi0)*(Y-yi0);
if(distance<R_2){
R+=0.5;
r/=2;
v*=2;
}
/*----------------------------------
/*================================*/
//碰撞邊界反彈
R=(X<x0||X>xM)?-R:R;
R=(Y<y0||Y>yM)?0.5-R:R;
X=x[k]+Math.sin(P2*R)*V;
Y=y[k]+Math.cos(P2*R)*V;
/*================================*/
//溢出邊界重生(類似流星效果)
if(X<x0||X>xM||Y<y0||Y>yM){
X=xi0;
Y=yi0;
}
/*----------------------------------
/*================================*/
//邊界限制
x[k]=X=(X<x0)?x0:(X>xM)?xM-2:X;
y[k]=Y=(Y<y0)?y0:(Y>yM)?yM-2:Y;
r[k]=R>1?R-1:R<0?R+1:R;
v[k]=V=(V<v0)?v0:((V<vM)?V:vM);
/*================================*/
obj.style.left=x[k]=X;
obj.style.top=y[k]=Y;
setTimeout('Move('+(i+Unit)%Total+')',Unit);
}
}
//根據(jù)瀏覽器自動(dòng)加載動(dòng)畫
switch(navigator.appName.toLowerCase()){
case "netscape":
window.addEventListener("load",document.onclick,false);
break;
case "microsoft internet explorer":
default:
window.attachEvent("onload",document.onclick);
break;
}
</script>
</head>
<body scroll="no">
<div id="food" class="food"></div>
<div id="nest" class="nest"></div>
</body>
</html>