95蟻群算法求解TSP的基本思想

1、Ch9 蟻群算法9.1 生物學(xué)知識(shí)1、蟻群算法(Ant Colony Algorithm ,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í)，留下的信息素也會(huì)越來(lái)越多，以致后螞蟻選擇該路徑的

3、概率也越來(lái)越高，從而更增加了該路徑的吸引強(qiáng)度，逐漸形成了一條它們自己事先并未意識(shí)到的最短路線。螞蟻會(huì)以較大的概率優(yōu)先選擇信息素濃度較高的路徑，并釋放一定量的信息素，以增強(qiáng)該條路徑的信息素的濃度，形成一個(gè)正反饋。路徑上的信息濃度會(huì)隨時(shí)間的推進(jìn)，而不斷揮發(fā)，從而不斷降低，這似乎也是變異。9.2ACA 算法的基本思想左圖表示初始狀態(tài)中，在結(jié)點(diǎn)A 與 C 有 30 只螞蟻，線上的數(shù)字(1,0)表示距離為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á)到了，

4、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 倍，因此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)：1

5、0+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=50再出發(fā)A 點(diǎn)： A-B 方向 =25*35/85=10 A-D 方向?yàn)?15 只。 兩邊各占0.41:0.59C 點(diǎn)： C-B 是 10 只， 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+1

6、5+15=80 ， C-D 為 50+15+15=80再出發(fā)50/130=0.46 80/130=0.54A 點(diǎn)： A-B 方向 =20*50/130=6 A-D 方向?yàn)?14只。C 點(diǎn)： C-B 是 6 只， C-D 是 14 只B 點(diǎn)： B-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.38 108/174=0.629.3 優(yōu)缺點(diǎn)優(yōu)點(diǎn)：(1

7、)蟻群算法是一種分布式內(nèi)在并行算法。單個(gè)螞蟻的搜索過(guò)程是彼此獨(dú)立的，易于局部最優(yōu)，通過(guò)個(gè)體間不斷的信息交流和傳遞有利于發(fā)現(xiàn)較好解。(2)蟻群算法是一種正反饋算法。路徑上的信息素濃度較高，將吸引更多的螞蟻沿這條路徑運(yùn)動(dòng)，又使得信息素濃度增加，加快了算法的進(jìn)化過(guò)程。(3)蟻群算法具有較強(qiáng)的自適應(yīng)性，對(duì)其模型稍做修改，可應(yīng)用于其他問(wèn)題。(4)易于其他方法組合，以改善算法的效率。缺點(diǎn)：(1)需要較長(zhǎng)時(shí)間搜索。主要是因?yàn)楦魑浵伒倪\(yùn)動(dòng)是隨機(jī)的，當(dāng)群體規(guī)模稍大時(shí)，需要很長(zhǎng)時(shí)間才能收斂。(2)易出現(xiàn)停滯現(xiàn)象，早熟現(xiàn)象。9.4 蟻群算法的研究進(jìn)展1、 20 世紀(jì) 90 年代 意大利 Dorigo 、 Manie

8、zzo 等人提出該算法。2、 1999 年， Dorigo 提出了蟻群優(yōu)化(Ant Colony Optimization) 的通用框架。3、 2002 年 8 月，出版蟻群優(yōu)化算法的特刊。4、從1998 年起，每隔二年在比利時(shí)的布魯塞爾舉行一次蟻群算法的國(guó)際會(huì)議。5、涉及到領(lǐng)域有生物學(xué)、物理學(xué)、工程學(xué)、計(jì)算機(jī)科學(xué)。6、 Bichev 和 parmee提出了求解連續(xù)空間的蟻群算法模型。7、 2004 年李士勇等蟻群算法的專(zhuān)著8、 2005 年段海濱蟻群算法原理及應(yīng)用專(zhuān)著9、 2006 年吳啟迪智能蟻群算法及應(yīng)用9.5 蟻群算法求解TSP 的基本思想1、基本參數(shù)、信息素濃度公式、擇路概率設(shè)螞蟻的

9、數(shù)量為m，城市的數(shù)量為n，城市 i 與城市 j 之間的距離為dij，t 時(shí)刻城市i 與城市 j 之間的信息素濃度為tij (t)， 初始時(shí)刻，各個(gè)城市間連接路徑上的信息素濃度相同，不妨記為tij(0)=t0 .螞蟻 k(k=1,2,.,m) 根據(jù)各城市間連接路徑上的信息素濃度，決定其下一個(gè)要訪問(wèn)的城市，設(shè)Pijk(t)表示t 時(shí)刻，螞蟻k 從城市 i 到城市 j 的概率，其計(jì)算公式為如下：s allow ks allowtij (t) ij (t)Pijktij (t) ij(t)s allow0其中：ij(t)為啟發(fā)式函數(shù)，ij(t)=1/dij ，表示螞蟻從城市i 轉(zhuǎn)移到城市j 的期望程序

10、allowk(k=1,2,m)表示螞蟻k 待訪問(wèn)的城市的集合，開(kāi)始時(shí)allowk為其他 n-1 城市，隨著時(shí)間推進(jìn)，其中的元素不斷減少，直至為空，表示所有城市訪問(wèn)完，即遍歷所有城市。為信息素的重要程度因子，其值越大，轉(zhuǎn)移中起的作用越大為啟發(fā)函數(shù)的重要程度因子，其值越大，表示啟發(fā)函數(shù)在轉(zhuǎn)移中的作用越大，即螞蟻以較大的概率轉(zhuǎn)移到距離短的城市。螞蟻釋放的信息素會(huì)隨時(shí)間的推進(jìn)而減少，設(shè)參數(shù) (0 1)表示信息素的揮發(fā)度，當(dāng)所有螞蟻完成一次循環(huán)后，各個(gè)城市間連接路徑上的信息素濃度，需要實(shí)時(shí)更新。ntij(t+1)=(1- )tij(t)+ tij， tij=tikjk1其中：tijk 表示螞蟻k 在城市

11、 i 與城市 j 的連接路徑上，釋放的信息素濃度tij表示所有螞蟻在城市i 與城市 j 的連接路徑上，釋放的信息素濃度。2、tijk的計(jì)算方法Dorigo 曾給出了3 種不同的模型，分別如下：(1)ant cycle systemktij =Q/Lk0第 k只螞蟻從城市i 訪問(wèn)城市j其他其中：Q 為常數(shù)，表示螞蟻循環(huán)一次釋放的信息素的總量dij 為第k 只螞蟻經(jīng)過(guò)路徑的長(zhǎng)度，Length一般選用該模型(2)ant quantity systemt k= Q/dijtij =0第 k只螞蟻從城市i 訪問(wèn)城市j其他其中：Q 為常數(shù)，表示螞蟻循環(huán)一次釋放的信息素的總量dij 為城市 i 到城市 j

12、的距離。(3)ant density systemk Q 第 k只螞蟻從城市i 訪問(wèn)城市jti k=tij = 0其他其中：Q 為常數(shù)，表示螞蟻循環(huán)一次釋放的信息素的總量9.6 蟻群算法解決TSP 問(wèn)題的基本步驟1、初始化參數(shù)螞蟻數(shù)量m，信息素重要程度，啟發(fā)函數(shù)重要程度，信息素?fù)]發(fā)因子，信息素釋放總量Q，最大迭代次數(shù)iter_max。獲取各城市之間的距離dij，為了保證啟發(fā)式函數(shù)ij =1/dij 能順利進(jìn)行，對(duì)于 i=j 即自己到自己的距離不能給為0， 而是給成一個(gè)很小的距離，如10-4或10-5。2、構(gòu)建解空間將各個(gè)螞蟻隨機(jī)地置于不同出發(fā)點(diǎn)，對(duì)每個(gè)螞蟻按歸照下式，確定下一城市。s allo

13、w ks allow ktij (t) ij (t)Pijktij (t) ij(t)s allow03、更新信息素計(jì)算各個(gè)螞蟻經(jīng)過(guò)的路徑長(zhǎng)度Lk， 記錄當(dāng)前迭代次數(shù)中的最優(yōu)解(即最短路徑)， 根據(jù)如下公式更新信息素：ntij(t+1)=(1- )tij(t)+ tij，tij=tikjk1ktij =Q/Lk0第 k只螞蟻從城市i 訪問(wèn)城市j其他4、判斷是否終止2。若沒(méi)有到最大次數(shù)，則清空螞蟻經(jīng)過(guò)路徑的記錄表，返回步驟9.7 TSP 實(shí)例1、訪問(wèn)我國(guó)每個(gè)省會(huì)城市一次也僅一次的最短路徑，共有31 個(gè)2、如果采用枚舉法，巡回路徑可能1.326 1032種。3、城市的坐標(biāo)citys，這是直角坐標(biāo)，

14、根據(jù)二個(gè)城市的坐標(biāo)值，可以用D= (x1 x2)2 (y1 y2)2 可計(jì)算出任意二個(gè)城市間的距離。citys =130423123639131541772244371213993488153533261556323812294196100443127904386570300719702562175627881491238116761332695371516783918217940612370378022123676257840292838426329313429190835072367339426433439320129353240314035502545235727782826237029

15、75程序清單% 蟻群算法計(jì)算旅行商問(wèn)題(TSP)% 清空環(huán)境變量clear allclc% 導(dǎo)入數(shù)據(jù)load citys_data.mat% 計(jì)算城市間相互距離n = size(citys,1); % 城市的個(gè)數(shù)D = zeros(n,n); %n 行 n 列的矩陣，即任意二個(gè)城市之間的距離for i = 1:nfor j = 1:nif i = jD(i,j) = sqrt(sum(citys(i,:) - citys(j,:).2); elseD(i,j) = 1e-4;endendend% 初始化參數(shù)% 螞蟻數(shù)量% 信息素重要程度因子% 啟發(fā)函數(shù)重要程度因子m = 50;alpha =

16、1;beta = 5;% 信息素?fù)]發(fā)因子% 常系數(shù)% 啟發(fā)函數(shù)% 信息素矩陣,全 1 矩陣% 路徑記錄表，全0 矩陣，每只螞蟻依次走過(guò)的城% 迭代次數(shù)初值% 最大迭代次數(shù)% 各代最佳路徑% 各代最佳路徑的長(zhǎng)度% 各代路徑的平均長(zhǎng)度rho = 0.1;Q = 1;Eta = 1./D;Tau = ones(n,n);Table = zeros(m,n);市iter = 1;iter_max = 200;Route_best = zeros(iter_max,n);Length_best = zeros(iter_max,1);Length_ave = zeros(iter_max,1);% 迭代

17、尋找最佳路徑while iter = rand);target = allow(target_index(1);Table(i,j) = target;endend% 計(jì)算各個(gè)螞蟻的路徑距離Length = zeros(m,1);%m 行 1 列的矩陣 for i = 1:mRoute = Table(i,:);% 第 i 只螞蟻的路線for j = 1:(n - 1)%依次計(jì)算第i 只螞蟻所走過(guò)的各城市間的距離j-j+1Length(i) = Length(i) + D(Route(j),Route(j + 1);endLength(i) = Length(i) + D(Route(n),R

18、oute(1);% 加上最后城市到首個(gè)城市的距離 end % 計(jì)算最短路徑距離及平均距離 if iter = 1min_Length,min_index = min(Length); % 各只螞義中路長(zhǎng)的最小值Length_best(iter) = min_Length;Length_ave(iter) = mean(Length);Route_best(iter,:) = Table(min_index,:);% 取取最短路線 elsemin_Length,min_index = min(Length);% 如果不是第一輪，則要與上輪最小路長(zhǎng)進(jìn)行比較Length_best(iter) = m

19、in(Length_best(iter - 1),min_Length);Length_ave(iter) = mean(Length);if Length_best(iter) = min_LengthRoute_best(iter,:) = Table(min_index,:);elseRoute_best(iter,:) = Route_best(iter-1),:);end end % 更新信息素Delta_Tau = zeros(n,n);% 逐個(gè)螞蟻計(jì)算for i = 1:m% 逐個(gè)城市計(jì)算for j = 1:(n - 1)Delta_Tau(Table(i,j),Table(i,

20、j+1) = Delta_Tau(Table(i,j),Table(i,j+1) + Q/Length(i); endDelta_Tau(Table(i,n),Table(i,1) = Delta_Tau(Table(i,n),Table(i,1) + Q/Length(i); endTau = (1-rho) * Tau + Delta_Tau;% 迭代次數(shù)加1 ，清空路徑記錄表iter = iter + 1;Table = zeros(m,n);end % 結(jié)果顯示Shortest_Length,index = min(Length_best);Shortest_Route = Route_best(index,:);disp(最短距離: num2str(Shortest_Length);disp(最短路徑: num2str(Shortest_Route Shortest_Route(1);% 繪圖figure(1)plot(citys(Shortest_Route,1);citys(Shortest_Route(1),1),.citys(Shortest_Route,2);citys(Shortest_Route(1),2)