基本蟻群算法

1、蟻群算法淺析摘要：介紹了什么是蟻群算法，蟻群算法的種類，對(duì)四種不同的蟻群算法進(jìn)行了分析對(duì)比。詳細(xì)闡述了蟻群算法的基本原理，將其應(yīng)用于旅行商問(wèn)題，有效地解決了問(wèn)題。通過(guò)對(duì)旅行商問(wèn)題C+模擬仿真程序的詳細(xì)分析，更加深刻地理解與掌握了蟻群算法。關(guān)鍵詞：蟻群算法；旅行商問(wèn)題；信息素；輪盤選擇一、引言蟻群算法（Ant Colony Optimization, ACO），是一種用來(lái)在圖中尋找優(yōu)化路徑的算法。它由Marco Dorigo于1992年在他的博士論文中提出，其靈感來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。蟻群算法是一種模擬進(jìn)化算法，初步的研究表明該算法具有許多優(yōu)良的性質(zhì)。蟻群算法成功解決了旅行商

2、問(wèn)題（Traveling Salesman Problem, TSP）：一個(gè)商人要到若干城市推銷物品，從一個(gè)城市出發(fā)要到達(dá)其他各城市一次而且最多一次最后又回到第一個(gè)城市。尋找一條最短路徑，使他從起點(diǎn)的城市到達(dá)所有城市一遍，最后回到起點(diǎn)的總路程最短。若把每個(gè)城市看成是圖上的節(jié)點(diǎn)，那么旅行商問(wèn)題就是在N個(gè)節(jié)點(diǎn)的完全圖上尋找一條花費(fèi)最少的回路。最基本的蟻群算法見(jiàn)第二節(jié)。目前典型的蟻群算法有隨機(jī)蟻群算法、排序蟻群算法和最大最小蟻群算法，其中后兩種蟻群算法是對(duì)前一種的優(yōu)化。本文將終點(diǎn)介紹隨機(jī)蟻群算法。二、基本蟻群算法（一）算法思想各個(gè)螞蟻在沒(méi)有事先告訴他們食物在什么地方的前提下開(kāi)始尋找食物。當(dāng)一只找到食

3、物以后，它會(huì)向環(huán)境釋放一種信息素，信息素多的地方顯然經(jīng)過(guò)這里的螞蟻會(huì)多，因而會(huì)有更多的螞蟻聚集過(guò)來(lái)。假設(shè)有兩條路從窩通向食物，開(kāi)始的時(shí)候，走這兩條路的螞蟻數(shù)量同樣多（或者較長(zhǎng)的路上螞蟻多，這也無(wú)關(guān)緊要）。當(dāng)螞蟻沿著一條路到達(dá)終點(diǎn)以后會(huì)馬上返回來(lái)，這樣，短的路螞蟻來(lái)回一次的時(shí)間就短，這也意味著重復(fù)的頻率就快，因而在單位時(shí)間里走過(guò)的螞蟻數(shù)目就多，灑下的信息素自然也會(huì)多，自然會(huì)有更多的螞蟻被吸引過(guò)來(lái)，從而灑下更多的信息素。因此，越來(lái)越多地螞蟻聚集到較短的路徑上來(lái)，最短的路徑就找到了。蟻群算法的基本思想如下圖表示：圖1 等概率選擇 圖2 最優(yōu)路徑 圖3 最優(yōu)比重（二）算法描述基本蟻群算法的算法簡(jiǎn)單描述

4、如下：1所有螞蟻遇到障礙物時(shí)按照等概率選擇路徑，并留下信息素；2隨著時(shí)間的推移，較短路徑的信息素濃度升高；3螞蟻再次遇到障礙物時(shí)，會(huì)選擇信息素濃度高的路徑；4較短路徑的信息素濃度繼續(xù)升高，最終最優(yōu)路徑被選擇出來(lái)。三、隨機(jī)蟻群算法（一）算法思想在基本蟻群算法中，螞蟻會(huì)在多條可選擇的路徑中，自動(dòng)選擇出最短的一條路徑。但是，一旦蟻群選擇了一條比之前短的路徑，就會(huì)認(rèn)為這條路徑是最好的，在這條路徑上一直走下去。這樣的算法存在問(wèn)題：螞蟻可能只是找到了局部的最短路徑，而忽略了全局最優(yōu)解。因此，在基本蟻群算法的基礎(chǔ)上，需要對(duì)螞蟻選路的方案加以改善：有些螞蟻并沒(méi)有象其它螞蟻一樣總重復(fù)同樣的路，他們會(huì)另辟蹊徑，也

5、就是它會(huì)按照一定的概率不往信息素高的地方。如果令開(kāi)辟的道路比原來(lái)的其他道路更短，那么，漸漸地，更多的螞蟻被吸引到這條較短的路上來(lái)。最后，經(jīng)過(guò)一段時(shí)間運(yùn)行，可能會(huì)出現(xiàn)一條最短的路徑被大多數(shù)螞蟻重復(fù)著，這就是優(yōu)化的隨機(jī)蟻群算法。為了實(shí)現(xiàn)螞蟻的“隨機(jī)”選路，我們需要做以下假設(shè)：1范圍：螞蟻觀察到的范圍是一個(gè)方格世界，螞蟻有一個(gè)參數(shù)為速度半徑，如果半徑等于2，那么它能觀察到的范圍就是2*2個(gè)方格世界，并且能移動(dòng)的距離也在這個(gè)范圍之內(nèi)。2環(huán)境：環(huán)境以一定的速率讓信息素消失。3覓食規(guī)則：在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過(guò)去。否則看是否有信息素，并且比較在能感知的范圍內(nèi)哪一點(diǎn)的信息素最多

6、，那么它朝哪個(gè)方向走的概率就大。這就意味著每只螞蟻多會(huì)以小概率犯錯(cuò)誤，從而并不是往信息素最多的點(diǎn)移動(dòng)。4避障規(guī)則：如果螞蟻要移動(dòng)的方向有障礙物擋住，它會(huì)隨機(jī)的選擇另一個(gè)方向，并且有信息素指引的話，它會(huì)按照覓食的規(guī)則行為。 5播撒信息素規(guī)則：每只螞蟻在找到食物后撒發(fā)的信息素。自然想到一個(gè)問(wèn)題：開(kāi)始時(shí)環(huán)境沒(méi)有信息素，螞蟻為什么會(huì)相對(duì)有效的找到食物呢？這個(gè)問(wèn)題用螞蟻的移動(dòng)規(guī)則同樣可以解釋。首先，它要能盡量保持某種慣性，這樣使得螞蟻盡量向前方移動(dòng)（開(kāi)始，這個(gè)前方是隨機(jī)固定的一個(gè)方向），而不是原地?zé)o謂的打轉(zhuǎn)或者震動(dòng)；其次，螞蟻要有一定的隨機(jī)性，雖然有了固定的方向，但它也不能像粒子一樣直線運(yùn)動(dòng)下去，而是有

7、一個(gè)隨機(jī)的干擾。這樣就使得螞蟻運(yùn)動(dòng)起來(lái)具有了一定的目的性，盡量保持原來(lái)的方向，但又有新的試探，這就解釋了為什么單個(gè)螞蟻在復(fù)雜的諸如迷宮的地圖中仍然能找到隱蔽得很好的食物。（二）算法描述隨機(jī)蟻群算法的算法描述如下：算法輸入：城市數(shù)量N，兩兩城市間的距離，所有路徑的信息素濃度算法輸出：螞蟻?zhàn)哌^(guò)的路徑長(zhǎng)度1設(shè)置全部城市都沒(méi)有去過(guò)，走過(guò)的路徑長(zhǎng)度為0；2隨機(jī)選擇一個(gè)出發(fā)的城市；3i = 14while(i < N)4 根據(jù)可選擇路徑的信息素濃度，計(jì)算出各自選中的概率；5 根據(jù)不同選擇的概率，使用輪盤選擇算法，得到選擇的下一個(gè)城市；6 將所在城市標(biāo)記為不可選擇；7end8計(jì)算走過(guò)路徑的長(zhǎng)度；用隨機(jī)

8、蟻群算法解決旅行商問(wèn)題，實(shí)際上是多次使用蟻群算法，不斷更新最短路徑的過(guò)程。由此，我們?nèi)菀椎玫铰眯猩虇?wèn)題的算法描述：算法輸入：所有城市的X、Y坐標(biāo)，螞蟻數(shù)量n，迭代次數(shù)K算法輸出：旅行商的最短路徑1計(jì)算兩兩城市間的距離，初始化所有路徑信息素為0；2for i = 1 : K3 for j = 1 : n4 第j只螞蟻搜索一遍；5 if 走過(guò)的路徑小于最短路徑6 更新最短路徑；7 更新走過(guò)路徑的信息素；8 end9end四、改進(jìn)的隨機(jī)蟻群算法（一）排序蟻群算法與隨機(jī)蟻群算法不同的是，當(dāng)螞蟻遇到障礙物選擇路徑時(shí)，根據(jù)不同路徑上信息素的濃度，通過(guò)計(jì)算可能達(dá)到最優(yōu)解的概率算法，將路徑進(jìn)行排序，選擇最好的

9、路徑作為下一個(gè)通往的城市。（二）最大最小蟻群算法與隨機(jī)蟻群算法和排序蟻群算法都不同的是，當(dāng)螞蟻遇到障礙物選擇路徑時(shí)，使用貪心策略，優(yōu)先選擇達(dá)到下一個(gè)城市最短的城市，即得到局部最優(yōu)解。這樣以來(lái)，更多的信息素將在較短的路徑聚集，使算法更快地得到全局最短路徑。五、算法比較本文介紹了四種蟻群算法，其中第一種比較簡(jiǎn)單，描述了最基本的蟻群算法思想。但是，它忽略了更優(yōu)路徑存在的可能性，沒(méi)有考慮到更普遍的情況。因此，該算法只適用于小規(guī)模，無(wú)特殊情況的問(wèn)題。后三種蟻群算法屬于實(shí)際中典型的蟻群算法，對(duì)不同情況的考慮比較全面，因此應(yīng)用比較廣泛。三者的差別主要在于螞蟻對(duì)不同路徑的選擇上，其中，隨機(jī)蟻群算法首先根據(jù)不同

10、路徑上信息素的濃度，計(jì)算出選擇各條路徑的概率，而后使用輪盤算法選擇一條路徑，適用于規(guī)模不太大的場(chǎng)合；排序蟻群算法則根據(jù)選擇各條路徑的概率，對(duì)路徑進(jìn)行優(yōu)先排序，選擇最好的路徑作為下一個(gè)通往的城市，這樣做增加了空間復(fù)雜度，有效改善了時(shí)間復(fù)雜度，適用于規(guī)模較大的場(chǎng)合；最大最小蟻群算法則是采用貪心策略，優(yōu)先選擇達(dá)到下一個(gè)城市最短的城市，先得到局部最優(yōu)解，再通過(guò)聚類效應(yīng)得到全局最短路徑，適合對(duì)時(shí)間和空間要求都較高的場(chǎng)合。參考文獻(xiàn)： 1. 丁洋. 蟻群優(yōu)化算法分析. 論文期刊. 2012.5.2. 蟻群優(yōu)化算法. 附錄： 1預(yù)編譯所需頭文件 Stdafx.h#pragma once/ Stdafx.h :

11、 標(biāo)準(zhǔn)系統(tǒng)包含文件的包含文件，/ 或是常用但不常更改的項(xiàng)目特定的包含文件#include <iostream>#include <tchar.h>#include <math.h>#include <time.h>2算法參數(shù)頭文件 Common.h#pragma onceconst int N_CITY_COUNT=51; /城市數(shù)量const int N_ANT_COUNT=34; /螞蟻數(shù)量const int N_IT_COUNT=50; /迭代次數(shù)/蟻群算法參數(shù)const double ALPHA=1.0;const double BETA

12、=2.0;const double ROU=0.5; /信息素傳遞參數(shù)const double DBQ=100.0; /總的信息素const double DB_MAX=10e9; /最大標(biāo)志數(shù)extern double g_TrialN_CITY_COUNTN_CITY_COUNT; /兩兩城市間信息素extern double g_DistanceN_CITY_COUNTN_CITY_COUNT; /兩兩城市間距離extern int rnd(int nLow,int nUpper); /返回隨機(jī)整數(shù)extern double rnd(double dbLow,double dbUpper

13、);/返回隨機(jī)浮點(diǎn)數(shù)extern double ROUND(double dbA);/浮點(diǎn)數(shù)四舍五入extern double x_AryN_CITY_COUNT;extern double y_AryN_CITY_COUNT;3螞蟻類頭文件 Ant.h#pragma once#include "Common.h"/螞蟻類class CAntpublic:CAnt();CAnt();int m_nPathN_CITY_COUNT; /螞蟻?zhàn)叩穆窂絛ouble m_dbPathLength; /螞蟻?zhàn)哌^(guò)的路徑長(zhǎng)度int m_nAllowedCityN_CITY_COUNT;

14、/沒(méi)去過(guò)的城市int m_nCurCityNo; /當(dāng)前所在城市編號(hào)int m_nMovedCityCount; /已經(jīng)去過(guò)的城市數(shù)量int ChooseNextCity(); /選擇下一個(gè)城市void Init(); /初始化void Move(); /螞蟻在城市間移動(dòng)void Search(); /搜索路徑void CalPathLength(); /計(jì)算螞蟻?zhàn)哌^(guò)的路徑長(zhǎng)度;4旅行商類頭文件 Stdafx.h#pragma once#include "Common.h"#include "Ant.h"/旅行商類class CTsppublic:CTs

15、p();CTsp();CAnt m_cAntAryN_ANT_COUNT;CAnt m_cBestAnt; /保存結(jié)果void InitData(); /初始化數(shù)據(jù)void Search(); /開(kāi)始搜索void UpdateTrial();/更新環(huán)境信息素;5預(yù)編譯所需文件 Stdafx.cpp/ stdafx.cpp : 只包括標(biāo)準(zhǔn)包含文件的源文件/ City.pch 將成為預(yù)編譯頭/ stdafx.obj 將包含預(yù)編譯類型信息#include "Stdafx.h"6數(shù)據(jù)及全局函數(shù)文件Common.cpp#include "stdafx.h"#inc

16、lude "common.h"double g_TrialN_CITY_COUNTN_CITY_COUNT; /兩兩城市間信息素double g_DistanceN_CITY_COUNTN_CITY_COUNT; /兩兩城市間距離/城市坐標(biāo)數(shù)據(jù)double x_AryN_CITY_COUNT=37,49,52,20,40,21,17,31,52,51,42,31,5,12,36,52,27,17,13,57,62,42,16,8,7,27,30,43,58,58,37,38,46,61,62,63,32,45,59,5,10,21,5,30,39,32,25,25,48,5

17、6,30;double y_AryN_CITY_COUNT=52,49,64,26,30,47,63,62,33,21,41,32,25,42,16,41,23,33,13,58,42,57,57,52,38,68,48,67,48,27,69,46,10,33,63,69,22,35,15,6,17,10,64,15,10,39,32,55,28,37,40;/返回指定范圍內(nèi)的隨機(jī)整數(shù)int rnd(int nLow,int nUpper)return nLow+(nUpper-nLow)*rand()/(RAND_MAX+1);/返回指定范圍內(nèi)的隨機(jī)浮點(diǎn)數(shù)double rnd(double

18、 dbLow,double dbUpper)double dbTemp=rand()/(double)RAND_MAX+1.0);return dbLow+dbTemp*(dbUpper-dbLow);/返回浮點(diǎn)數(shù)四舍五入取整后的浮點(diǎn)數(shù)double ROUND(double dbA)return (double)(int)(dbA+0.5);7螞蟻類定義文件Ant.cpp#include "Stdafx.h"#include "Ant.h"CAnt:CAnt()CAnt:CAnt()/搜索一次void CAnt:Search()/初始出發(fā)點(diǎn)Init();

19、/所有城市走一遍while(m_nMovedCityCount < N_CITY_COUNT)Move();/計(jì)算走過(guò)路徑長(zhǎng)度CalPathLength();void CAnt:Init()for (int i=0;i<N_CITY_COUNT;i+)m_nAllowedCityi=1; /設(shè)置全部城市為沒(méi)有去過(guò)m_nPathi=0; /螞蟻?zhàn)叩穆窂饺吭O(shè)置為0/螞蟻?zhàn)哌^(guò)的路徑長(zhǎng)度設(shè)置為0m_dbPathLength=0.0; /隨機(jī)選擇一個(gè)出發(fā)城市m_nCurCityNo=rnd(0,N_CITY_COUNT);/設(shè)置出發(fā)城市m_nPath0=m_nCurCityNo;/標(biāo)識(shí)出發(fā)

20、城市為已經(jīng)去過(guò)了m_nAllowedCitym_nCurCityNo=0; /已經(jīng)去過(guò)的城市數(shù)量設(shè)置為1m_nMovedCityCount=1; /選擇下一個(gè)城市，返回值為城市編號(hào)int CAnt:ChooseNextCity()int nSelectedCity=-1; /返回結(jié)果，先暫時(shí)把其設(shè)置為-1/計(jì)算當(dāng)前城市和沒(méi)去過(guò)的城市之間的信息素總和double dbTotal=0.0;double probN_CITY_COUNT; /保存城市被選中的概率for (int i=0;i<N_CITY_COUNT;i+)if (m_nAllowedCityi = 1) /城市沒(méi)去過(guò)/該城市被

21、選中的概率=該城市和當(dāng)前城市間的信息素總量*(1/距離)2probi=pow(g_Trialm_nCurCityNoi,ALPHA)*pow(1.0/g_Distancem_nCurCityNoi,BETA);dbTotal=dbTotal+probi; /累加信息素，得到總和elseprobi=0.0;/輪盤選擇double dbTemp=0.0;if (dbTotal > 0.0) /總的信息素值大于0dbTemp=rnd(0.0,dbTotal); /取一個(gè)隨機(jī)數(shù)for (int i=0;i<N_CITY_COUNT;i+)if (m_nAllowedCityi = 1) /

22、城市沒(méi)去過(guò)dbTemp=dbTemp-probi; /轉(zhuǎn)動(dòng)輪盤if (dbTemp < 0.0) /輪盤停止轉(zhuǎn)動(dòng)，記下城市編號(hào)，直接跳出循環(huán)nSelectedCity=i;break;/如果城市間的信息素非常小，由于浮點(diǎn)運(yùn)算的誤差原因，可能沒(méi)有城市被選擇出來(lái)/出現(xiàn)這種情況，就把第一個(gè)沒(méi)去過(guò)的城市作為返回結(jié)果if (nSelectedCity = -1)for (int i=0;i<N_CITY_COUNT;i+)if (m_nAllowedCityi = 1) /城市沒(méi)去過(guò)nSelectedCity=i;break;/返回結(jié)果return nSelectedCity;void CA

23、nt:Move()int nCityNo=ChooseNextCity(); /選擇下一個(gè)城市m_nPathm_nMovedCityCount=nCityNo; /記錄螞蟻?zhàn)叩穆窂絤_nAllowedCitynCityNo=0;/標(biāo)記城市已經(jīng)去過(guò)m_nCurCityNo=nCityNo; /記錄當(dāng)前所在城市編號(hào)m_nMovedCityCount+; /去過(guò)的城市數(shù)量加一/計(jì)算螞蟻?zhàn)哌^(guò)的路徑長(zhǎng)度void CAnt:CalPathLength()m_dbPathLength=0.0;int m=0;int n=0;/計(jì)算走過(guò)路徑的長(zhǎng)度和for (int i=1;i<N_CITY_COUNT;

24、i+)m=m_nPathi;n=m_nPathi-1;m_dbPathLength=m_dbPathLength+g_Distancemn;/加上從最后城市返回出發(fā)城市的距離n=m_nPath0;m_dbPathLength=m_dbPathLength+g_Distancemn;8旅行商類定義文件Tsp.cpp#include "Stdafx.h"#include "Tsp.h"CTsp:CTsp()m_cBestAnt.m_dbPathLength=DB_MAX;CTsp:CTsp()/初始化數(shù)據(jù)void CTsp:InitData() /先把最佳結(jié)

25、果的路徑設(shè)置成最大m_cBestAnt.m_dbPathLength=DB_MAX; /計(jì)算兩兩城市間距離double dbTemp=0.0;for (int i=0;i<N_CITY_COUNT;i+)for (int j=0;j<N_CITY_COUNT;j+)dbTemp=(x_Aryi-x_Aryj)*(x_Aryi-x_Aryj)+(y_Aryi-y_Aryj)*(y_Aryi-y_Aryj);dbTemp=pow(dbTemp,0.5);g_Distanceij=ROUND(dbTemp);/初始化環(huán)境信息素為0for (int i=0;i<N_CITY_COUN

26、T;i+)for (int j=0;j<N_CITY_COUNT;j+)g_Trialij=0.0;/更新環(huán)境信息素void CTsp:UpdateTrial()/臨時(shí)保存信息素double dbTempAryN_CITY_COUNTN_CITY_COUNT;memset(dbTempAry,0,sizeof(dbTempAry); /先全部設(shè)置為0/計(jì)算新增加的信息素,保存到臨時(shí)數(shù)組里int m=0;int n=0;for (int i=0;i<N_ANT_COUNT;i+) /計(jì)算每只螞蟻留下的信息素for (int j=1;j<N_CITY_COUNT;j+)m=m_c

27、AntAryi.m_nPathj;n=m_cAntAryi.m_nPathj-1;dbTempArynm=dbTempArynm+DBQ/m_cAntAryi.m_dbPathLength;dbTempArymn=dbTempArynm;/最后城市和開(kāi)始城市之間的信息素n=m_cAntAryi.m_nPath0;dbTempArynm=dbTempArynm+DBQ/m_cAntAryi.m_dbPathLength;dbTempArymn=dbTempArynm;/更新環(huán)境信息素for (int i=0;i<N_CITY_COUNT;i+)for (int j=0;j<N_CITY_COUNT;j+)g_Trialij=g_Trialij*ROU+dbTempAryij; /最新的環(huán)境信息素 = 留