資源描述：
《蟻群算法求解TSP的基本思想.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、Ch9蟻群算法9.1生物學(xué)知識(shí)1、蟻群算法(AntColonyAlgorithm,ACA)是由意大利M.Dorigo等人于1990到2000發(fā)展起來(lái)的，模擬進(jìn)化算法。模擬了自然界螞蟻群體的覓食行為。2、蟻群社會(huì)在昆蟲(chóng)世界中，螞蟻的組成是一種群居的蓼襲大家庭，稱(chēng)為蟻群。蟻群中除了親緣上的互助關(guān)系外，成蟻劃分為世襲制的蟻王和工蟻兩個(gè)等級(jí)，蟻群的大小從幾十個(gè)到幾千萬(wàn)個(gè)，蟻群具有高度組織的社會(huì)性，彼此間的溝通不僅可以借助觸覺(jué)的的聯(lián)系，在大規(guī)模的協(xié)調(diào)行動(dòng)上，借助外激素之類(lèi)的生化信息介質(zhì)。其中每個(gè)工蟻具有如下的職能：平時(shí)在巢穴附近作無(wú)規(guī)則行走；一旦發(fā)現(xiàn)食物，如果獨(dú)自能搬的
2、就往回搬，否則就回巢穴搬兵；一路上它會(huì)留下外激至少的嗅跡，其強(qiáng)度與食物的品質(zhì)和數(shù)量成正比；其他工蟻遇到嗅跡，就會(huì)循跡前進(jìn)，也會(huì)有一定的走失率(選擇其他路徑)，走失率與嗅跡的強(qiáng)度成反比。蟻群的行為表現(xiàn)出一種信息正反饋的現(xiàn)象；某一路徑上走過(guò)的螞蟻越多，則后來(lái)選擇該路徑的概率就大，螞蟻個(gè)體間就是通過(guò)這種信息的交流達(dá)到搜索食物的目的。3、蟻群覓食過(guò)程意大利學(xué)者M(jìn).Dorigo是最早發(fā)現(xiàn)螞蟻的覓食習(xí)性的，螞蟻總能找到巢穴與食物源之間的最短路徑。螞蟻在尋找食物源后，會(huì)在其經(jīng)過(guò)的路徑上釋放一種信息素，并能夠感知其他螞蟻釋放的信息素。當(dāng)某些路徑上走過(guò)的螞蟻越來(lái)越多時(shí)，留下的信
3、息素也會(huì)越來(lái)越多，以致后螞蟻選擇該路徑的概率也越來(lái)越高，從而更增加了該路徑的吸引強(qiáng)度，逐漸形成了一條它們自己事先并未意識(shí)到的最短路線。螞蟻會(huì)以較大的概率優(yōu)先選擇信息素濃度較高的路徑，并釋放一定量的信息素，以增強(qiáng)該條路徑的信息素的濃度，形成一個(gè)正反饋。路徑上的信息濃度會(huì)隨時(shí)間的推進(jìn)，而不斷揮發(fā)，從而不斷降低，這似乎也是變異。9.2ACA算法的基本思想30(0.5,0)(0.5,0)(1,0)(1,0)ABCD301515(0.5,30)(0.5,30)(1,15)(1,15)ABCD30左圖表示初始狀態(tài)中，在結(jié)點(diǎn)A與C有30只螞蟻，線上的數(shù)字(1,0)表示距離為
4、1，信息素為0。此時(shí)每條邊上的信息素均為0，故螞蟻按隨機(jī)行走，A、C出發(fā)時(shí)，走兩邊的概率相等。單位時(shí)間后，A出發(fā)的螞蟻，15只達(dá)到了B、15只經(jīng)D到達(dá)C。C出發(fā)的螞蟻，15只達(dá)到了Ｂ，15只經(jīng)D到達(dá)了A，如右上圖所示。各邊的信息素如右圖所示，A-B有15只螞蟻?zhàn)哌^(guò)，留下的信息素是15個(gè)單位，C-B也是15只螞蟻，留下的信息素也是15，此時(shí)到B的螞蟻是15+15=30只。A-D-C的螞蟻是15只，C-D-A的也是15只，故該條較短路線上的信息素為30個(gè)單位。螞蟻再往前走：A點(diǎn)：由于A-B的信息素是15個(gè)單位，A-D是30單位，故A-D的螞蟻數(shù)是A-B的2倍，因此
5、A-B的螞蟻5只，A-D是10只C點(diǎn)：C-B是5只，C-D是10只B點(diǎn)：B-A是15只，B-C是15只單位時(shí)間后：A點(diǎn)：10+15=25C點(diǎn)：10+15=25B點(diǎn)：5+5=10信息素：A-B為15+15+5=35，C-B為15+15+5=35，A-D=30+10+10=50，C-D為30+10+10=501515(0.5,30)(0.5,30)(1,15)(1,15)ABCD302525(0.5,50)(0.5,50)(1,35)(1,35)ABCD10再出發(fā)A點(diǎn)：A-B方向=25*35/85=10A-D方向?yàn)?5只。兩邊各占0.41:0.59C點(diǎn)：C-B是1
6、0只，C-D是15只B點(diǎn)：B-A是5只，B-C是5只單位時(shí)間后：A點(diǎn)：5+15=20C點(diǎn)：5+15=20B點(diǎn)：10+10=20信息素：A-B為35+10+5=50，C-B為35+5+10=50，A-D=50+15+15=80，C-D為50+15+15=802020(0.5,80)(0.5,80)(1,50)(1,50)ABCD202424(0.5,108)(0.5,108)(1,66)(1,66)ABCD12再出發(fā)50/130=0.4680/130=0.54A點(diǎn)：A-B方向=20*50/130=6A-D方向?yàn)?4只。C點(diǎn)：C-B是6只，C-D是14只B點(diǎn)：B-
7、A是10只，B-C是10只單位時(shí)間后：A點(diǎn)：10+14=24C點(diǎn)：10+14=24B點(diǎn)：6+6=12信息素：A-B為50+6+10=66，C-B為50+6+10=66，A-D=80+14+14=108，C-D為80+14+14=108兩邊濃度比為66/174=0.38108/174=0.629.3優(yōu)缺點(diǎn)優(yōu)點(diǎn)：(1)蟻群算法是一種分布式內(nèi)在并行算法。單個(gè)螞蟻的搜索過(guò)程是彼此獨(dú)立的，易于局部最優(yōu)，通過(guò)個(gè)體間不斷的信息交流和傳遞有利于發(fā)現(xiàn)較好解。(2)蟻群算法是一種正反饋算法。路徑上的信息素濃度較高，將吸引更多的螞蟻沿這條路徑運(yùn)動(dòng)，又使得信息素濃度增加，加快了算法的
8、進(jìn)化過(guò)程。(3)蟻群算法具有較強(qiáng)的自適
