蟻群演算法解決tsp問題
① TSP是什麼意思啊
TSP即旅行商問題，即TSP問題（Traveling Salesman Problem）又譯為旅行推銷員問題、貨郎擔問題，是數學領域中著名問題之一。
假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市，路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。
TSP問題是一個組合優化問題。該問題可以被證明具有NPC計算復雜性。因此，任何能使該問題的求解得以簡化的方法，都將受到高度的評價和關注。
(1)蟻群演算法解決tsp問題擴展閱讀：
描述
TSP問題作為圖論問題可以用無向加權圖來對TSP建模，則城市是圖的頂點，道路是圖的邊，道路的距離就是該邊的長度。它是起點和終點都在一個特定頂點，訪問每個頂點恰好一次的最小化問題。通常，該模型是一個完全圖（即每對頂點由一條邊連接）。
如果兩個城市之間不存在路徑，則增加一條非常長的邊就可以完成圖，而不影響計算最優迴路。
TSP問題非對稱和對稱，在對稱TSP問題中，兩座城市之間來回的距離是相等的，形成一個無向圖。這種對稱性將解的數量減少了一半。
② TSP解決之道——蟻群演算法
蟻群演算法java實現以及TSP問題蟻群演算法求解
蟻群演算法原理與應用講解
蟻群演算法原理與應用1 -自然計算與群體智能
1、蟻群演算法(Ant Clony Optimization,ACO)是一種群智能演算法，它是由一群無智能或有輕微智能的個體（Agent）通過相互協作而表現出智能行為，從而為求解復雜問題提供了一個新的可能性。
2、是一種仿生學的演算法，是由自然界中螞蟻覓食的行為而啟發。（artificial ants；雙橋實驗）
3、運作機理：當一定路徑上通過的螞蟻越來越多時，其留下的信息素軌跡也越來越多，後來螞蟻選擇該路徑的概率也越高，從而更增加了該路徑的信息素強度，而強度大的信息素會吸引更多的螞蟻，從而形成一種正反饋機制。
4、蟻群演算法歐化過程中的兩個重要原則：
a、螞蟻在眾多路徑中轉移路線的選擇規則。
b、全局化信息素更新規則。信息素更新的實質就是人工螞蟻根據真實螞蟻在訪問過的邊上留下的信息素和蒸發的信息素來模擬真實信息素數量的變化，從而使得越好的解得到越多的增強。這就形成了一種自催化強化學習(Autocatalytic Reinforcement Learning)的正反饋機制。
1、描述：螞蟻數量m；城市之間的信息素矩陣pheromone；每次迭代的m個螞蟻的最短路徑 BestLength；最佳路徑BestTour。 每隻螞蟻都有 ：禁忌表(Tabu)存儲已訪問過的城市，允許訪問的城市表(Allowed)存儲還可以訪問的城市，矩陣（ Delta ）來存儲它在一個循環（或者迭代）中給所經過的路徑釋放的信息素。
2、 狀態轉移概率 ：在搜索過程中，螞蟻根據各條路徑上的信息量及路徑的啟發信息來計算狀態轉移概率。在t時刻螞蟻k由元素（城市）i轉移到元素（城市）j的狀態轉移概率：
τij (t) ：時刻路徑(i, j)上的信息量。ηij=1/dij ：啟發函數。
α為信息啟發式因子 ，表示軌跡的相對重要性，反映了螞蟻在運動過程中積累的信息在螞蟻運動時所起的作用，其值越大，則該螞蟻越傾向於選擇其它螞蟻經過的路徑，螞蟻之間的協作性越強；
β為期望啟發式因子 ，表示能見度的相對重要性，反映螞蟻在運動過程中啟發信息在螞蟻選擇路徑中的受重視程度，其值越大，則該狀態狀態轉移概率越接近於貪心規則；
3、 息素更新規則 ：
ρ表示信息素揮發系數；Δτij(t)表示本次循環中路徑(i, j)上的信息素增量，初始時刻Δτij(t) =0。
4、三種信息增量計算方法：
區別：第一種利用了全局信息，在走一圈後更新。二、三中都利用的是局部信息。通常使用第一種。
5、TSP中流程圖
③ 蟻群演算法的相關研究
跟著螞蟻的蹤跡，你找到了什麼？通過上面的原理敘述和實際操作，我們不難發現螞蟻之所以具有智能行為，完全歸功於它的簡單行為規則，而這些規則綜合起來具有下面兩個方面的特點：
1、多樣性
2、正反饋
多樣性保證了螞蟻在覓食的時候不至走進死胡同而無限循環，正反饋機制則保證了相對優良的信息能夠被保存下來。我們可以把多樣性看成是一種創造能力，而正反饋是一種學習強化能力。正反饋的力量也可以比喻成權威的意見，而多樣性是打破權威體現的創造性，正是這兩點小心翼翼的巧妙結合才使得智能行為涌現出來了。
引申來講，大自然的進化，社會的進步、人類的創新實際上都離不開這兩樣東西，多樣性保證了系統的創新能力，正反饋保證了優良特性能夠得到強化，兩者要恰到好處的結合。如果多樣性過剩，也就是系統過於活躍，這相當於螞蟻會過多的隨機運動，它就會陷入混沌狀態；而相反，多樣性不夠，正反饋機制過強，那麼系統就好比一潭死水。這在蟻群中來講就表現為，螞蟻的行為過於僵硬，當環境變化了，螞蟻群仍然不能適當的調整。
既然復雜性、智能行為是根據底層規則涌現的，既然底層規則具有多樣性和正反饋特點，那麼也許你會問這些規則是哪裡來的？多樣性和正反饋又是哪裡來的？我本人的意見：規則來源於大自然的進化。而大自然的進化根據剛才講的也體現為多樣性和正反饋的巧妙結合。而這樣的巧妙結合又是為什麼呢？為什麼在你眼前呈現的世界是如此栩栩如生呢？答案在於環境造就了這一切，之所以你看到栩栩如生的世界，是因為那些不能夠適應環境的多樣性與正反饋的結合都已經死掉了，被環境淘汰了！ 蟻群演算法的由來：螞蟻是地球上最常見、數量最多的昆蟲種類之一，常常成群結隊地出現在人類的日常生活環境中。這些昆蟲的群體生物智能特徵，引起了一些學者的注意。義大利學者M.Dorigo，V.Maniezzo等人在觀察螞蟻的覓食習性時發現，螞蟻總能找到巢穴與食物源之間的最短路徑。經研究發現，螞蟻的這種群體協作功能是通過一種遺留在其來往路徑上的叫做信息素(Pheromone)的揮發性化學物質來進行通信和協調的。化學通信是螞蟻採取的基本信息交流方式之一，在螞蟻的生活習性中起著重要的作用。通過對螞蟻覓食行為的研究，他們發現，整個蟻群就是通過這種信息素進行相互協作，形成正反饋，從而使多個路徑上的螞蟻都逐漸聚集到最短的那條路徑上。
這樣，M.Dorigo等人於1991年首先提出了蟻群演算法。其主要特點就是：通過正反饋、分布式協作來尋找最優路徑。這是一種基於種群尋優的啟發式搜索演算法。它充分利用了生物蟻群能通過個體間簡單的信息傳遞，搜索從蟻巢至食物間最短路徑的集體尋優特徵，以及該過程與旅行商問題求解之間的相似性。得到了具有NP難度的旅行商問題的最優解答。同時，該演算法還被用於求解Job-Shop調度問題、二次指派問題以及多維背包問題等，顯示了其適用於組合優化類問題求解的優越特徵。
多年來世界各地研究工作者對蟻群演算法進行了精心研究和應用開發，該演算法現已被大量應用於數據分析、機器人協作問題求解、電力、通信、水利、采礦、化工、建築、交通等領域。
蟻群演算法之所以能引起相關領域研究者的注意，是因為這種求解模式能將問題求解的快速性、全局優化特徵以及有限時間內答案的合理性結合起來。其中，尋優的快速性是通過正反饋式的信息傳遞和積累來保證的。而演算法的早熟性收斂又可以通過其分布式計算特徵加以避免，同時，具有貪婪啟發式搜索特徵的蟻群系統又能在搜索過程的早期找到可以接受的問題解答。這種優越的問題分布式求解模式經過相關領域研究者的關注和努力，已經在最初的演算法模型基礎上得到了很大的改進和拓展。
經過一定時間，從食物源返回的螞蟻到達D點同樣也碰到障礙物，也需要進行選擇。此時A, B兩側的信息素濃度相同，它們仍然一半向左，一半向右。但是當A側的螞蟻已經完全繞過障礙物到達C點時，B側的螞蟻由於需走的路徑更長，還不能到達C點，圖3表示蟻群在障礙物前經過一段時間後的情形。
此時對於從蟻巢出發來到C點的螞蟻來說，由於A側的信息素濃度高，B側的信息素較低，就傾向於選擇A側的路徑。這樣的結果是A側的螞蟻越來越多，最終所有螞蟻都選擇這條較短的路徑，圖4 表示蟻群最終選擇的路徑
上述過程，很顯然是由螞蟻所留下的信息素的「正反饋」過程而導致的。螞蟻個體就是通過這種信息的交流來達到搜索食物的目的。蟻群演算法的基本思想也是從這個過程轉化而來的。
蟻群演算法的特點：
1)蟻群演算法是一種自組織的演算法。在系統論中，自組織和它組織是組織的兩個基本分類，其區別在於組織力或組織指令是來自於系統的內部還是來自於系統的外部，來自於系統內部的是自組織，來自於系統外部的是他組織。如果系統在獲得空間的、時間的或者功能結構的過程中，沒有外界的特定干預，我們便說系統是自組織的。在抽象意義上講，自組織就是在沒有外界作用下使得系統熵減小的過程(即是系統從無序到有序的變化過程)。蟻群演算法充分體現了這個過程，以螞蟻群體優化為例子說明。當演算法開始的初期，單個的人工螞蟻無序的尋找解，演算法經過一段時間的演化，人工螞蟻間通過信息激素的作用，自發的越來越趨向於尋找到接近最優解的一些解，這就是一個無序到有序的過程。
2)蟻群演算法是一種本質上並行的演算法。每隻螞蟻搜索的過程彼此獨立，僅通過信息激素進行通信。所以蟻群演算法則可以看作是一個分布式的多agent系統，它在問題空間的多點同時開始進行獨立的解搜索，不僅增加了演算法的可靠性，也使得演算法具有較強的全局搜索能力。
3)蟻群演算法是一種正反饋的演算法。從真實螞蟻的覓食過程中我們不難看出，螞蟻能夠最終找到最短路徑，直接依賴於最短路徑上信息激素的堆積，而信息激素的堆積卻是一個正反饋的過程。對蟻群演算法來說，初始時刻在環境中存在完全相同的信息激素，給予系統一個微小擾動，使得各個邊上的軌跡濃度不相同，螞蟻構造的解就存在了優劣，演算法採用的反饋方式是在較優的解經過的路徑留下更多的信息激素，而更多的信息激素又吸引了更多的螞蟻，這個正反饋的過程使得初始的不同得到不斷的擴大，同時又引導整個系統向最優解的方向進化。因此，正反饋是螞蟻演算法的重要特徵，它使得演算法演化過程得以進行。
4)蟻群演算法具有較強的魯棒性。相對於其它演算法，蟻群演算法對初始路線要求不高，即蟻群演算法的求解結果不依賴於初始路線的選擇，而且在搜索過程中不需要進行人工的調整。其次，蟻群演算法的參數數目少，設置簡單，易於蟻群演算法應用到其它組合優化問題的求解。
蟻群演算法的應用進展以蟻群演算法為代表的蟻群智能已成為當今分布式人工智慧研究的一個熱點，許多源於蜂群和蟻群模型設計的演算法己越來越多地被應用於企業的運轉模式的研究。美國五角大樓正在資助關於群智能系統的研究工作-群體戰略(Swarm Strategy)，它的一個實戰用途是通過運用成群的空中無人駕駛飛行器和地面車輛來轉移敵人的注意力，讓自己的軍隊在敵人後方不被察覺地安全進行。英國電信公司和美國世界通信公司以電子螞蟻為基礎，對新的電信網路管理方法進行了試驗。群智能還被應用於工廠生產計劃的制定和運輸部門的後勤管理。美國太平洋西南航空公司採用了一種直接源於螞蟻行為研究成果的運輸管理軟體，結果每年至少節約了1000萬美元的費用開支。英國聯合利華公司己率先利用群智能技術改善其一家牙膏廠的運轉情況。美國通用汽車公司、法國液氣公司、荷蘭公路交通部和美國一些移民事務機構也都採用這種技術來改善其運轉的機能。鑒於群智能廣闊的應用前景，美國和歐盟均於近幾年開始出資資助基於群智能模擬的相關研究項目，並在一些院校開設群體智能的相關課程。國內，國家自然科學基金」十五」期間學科交叉類優先資助領域中的認知科學及其信息處理的研究內容中也明確列出了群智能領域的進化、自適應與現場認知主題。
蟻群優化演算法最初用於解決TSP問題，經過多年的發展，已經陸續滲透到其他領域中，比如圖著色問題、大規模集成電路設計、通訊網路中的路由問題以及負載平衡問題、車輛調度問題等。蟻群演算法在若干領域己獲得成功的應用，其中最成功的是在組合優化問題中的應用。
在網路路由處理中，網路的流量分布不斷變化，網路鏈路或結點也會隨機地失效或重新加入。蟻群的自身催化與正向反饋機制正好符合了這類問題的求解特點，因而，蟻群演算法在網路領域得到一定應用。蟻群覓食行為所呈現出的並行與分布特性使得演算法特別適合於並行化處理。因而，實現演算法的並行化執行對於大量復雜的實際應用問題的求解來說是極具潛力的。
在某群體中若存在眾多無智能的個體，它們通過相互之間的簡單合作所表現出來的智能行為即稱為集群智能(Swarm Intelligence)。互聯網上的交流，不過是更多的神經元連接(人腦)通過互聯網相互作用的結果，光纜和路由器不過是軸突和突觸的延伸。從自組織現象的角度上看，人腦的智能和蟻群也沒有本質上的區別，單個神經元沒有智能可言，單個螞蟻也沒有，但是通過連接形成的體系，是一個智能體。（作者： 李精靈 編選：中國電子商務研究中心）
④ 蟻群演算法求解TSP問題的源程序及簡要說明
簡單蟻群演算法求解TSP的源程序(我幫你找的)
蟻群演算法是新興的仿生演算法，最初是由義大利學者Dorigo M於1991年首次提出，由於具有較強的魯棒性，優良的分布式計算機制和易於與其它方法結合等優點，成為人工智慧領域的一個研究熱點。本程序是實現簡單的蟻群演算法，TSP問題取的是att48，可從http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95獲取，程序運行時間可能會比較長，在我的這台CPU 1.6G+內存256M的機器上運行時間大概是13分鍾左右。我用的語言是MATLAB 7.1。此程序僅供學習所用，如有問題請反饋。謝謝。（註：程序沒有計算最後一個城市回來起點城市的距離）
function [y,val]=QACS
tic
load att48 att48;
MAXIT=300; % 最大循環次數
NC=48; % 城市個數
tao=ones(48,48);% 初始時刻各邊上的信息最為1
rho=0.2; % 揮發系數
alpha=1;
beta=2;
Q=100;
mant=20; % 螞蟻數量
iter=0; % 記錄迭代次數
for i=1:NC % 計算各城市間的距離
for j=1:NC
distance(i,j)=sqrt((att48(i,2)-att48(j,2))^2+(att48(i,3)-att48(j,3))^2);
end
end
bestroute=zeros(1,48); % 用來記錄最優路徑
routelength=inf; % 用來記錄當前找到的最優路徑長度
% for i=1:mant % 確定各螞蟻初始的位置
% end
for ite=1:MAXIT
for ka=1:mant %考查第K只螞蟻
deltatao=zeros(48,48); % 第K只螞蟻移動前各邊上的信息增量為零
[routek,lengthk]=travel(distance,tao,alpha,beta);
if lengthk<routelength % 找到一條更好的路徑
routelength=lengthk;
bestroute=routek;
end
for i=1:NC-1 % 第K只螞蟻在路徑上釋放的信息量
deltatao(routek(i),routek(i+1))=deltatao(routek(i),routek(i+1))+Q/lengthk;
end
deltatao(routek(48),1)=deltatao(routek(48),1)+Q/lengthk;
end
for i=1:NC-1
for j=i+1:NC
if deltatao(i,j)==0
deltatao(i,j)=deltatao(j,i);
end
end
end
tao=(1-rho).*tao+deltatao;
end
y=bestroute;
val=routelength;
toc
function [y,val]=travel(distance,tao,alpha,beta) % 某隻螞蟻找到的某條路徑
[m,n]=size(distance);
p=fix(m*rand)+1;
val=0; % 初始路徑長度設為 0
tabuk=[p]; % 假設該螞蟻都是從第 p 個城市出發的
for i=1:m-1
np=tabuk(length(tabuk)); % 螞蟻當前所在的城市號
p_sum=0;
for j=1:m
if isin(j,tabuk)
continue;
else
ada=1/distance(np,j);
p_sum=p_sum+tao(np,j)^alpha*ada^beta;
end
end
cp=zeros(1,m); % 轉移概率
for j=1:m
if isin(j,tabuk)
continue;
else
ada=1/distance(np,j);
cp(j)=tao(np,j)^alpha*ada^beta/p_sum;
end
end
NextCity=pchoice(cp);
tabuk=[tabuk,NextCity];
val=val+distance(np,NextCity);
end
y=tabuk;
function y=isin(x,A) % 判斷數 x 是否在向量 A 中，如在返回 1 ，否則返回 0
y=0;
for i=1:length(A)
if A(i)==x
y=1;
break;
end
end
function y=pchoice(A)
a=rand;
tempA=zeros(1,length(A)+1);
for i=1:length(A)
tempA(i+1)=tempA(i)+A(i);
end
for i=2:length(tempA)
if a<=tempA(i)
y=i-1;
break;
end
end
⑤ 關於神經網路，蟻群演算法和遺傳演算法
神經網路並行性和自適應性很強，應用領域很廣，在任何非線性問題中都可以應用，如控制、信息、預測等各領域都能應用。
蟻群演算法最開始應用於TSP問題，獲得了成功，後來又廣泛應用於各類組合優化問題。但是該演算法理論基礎較薄弱，演算法收斂性都沒有得到證明，很多參數的設定也僅靠經驗，實際效果也一般，使用中也常常早熟。
遺傳演算法是比較成熟的演算法，它的全局尋優能力很強，能夠很快地趨近較優解。主要應用於解決組合優化的NP問題。
這三種演算法可以相互融合，例如GA可以優化神經網路初始權值，防止神經網路訓練陷入局部極小且加快收斂速度。蟻群演算法也可用於訓練神經網路，但一定要使用優化後的蟻群演算法，如最大-最小蟻群演算法和帶精英策略。
⑥ 蟻群演算法與遺傳演算法的區別
都屬於智能優化演算法
但是蟻群演算法具有一定的記憶性，遺傳演算法沒有
蟻群演算法有幾種原則，比如覓食原則，避障原則等，遺傳演算法沒有
蟻群演算法屬於群智能優化演算法，具有並行性，每個粒子都可以主動尋優，遺傳演算法不行
蟻群演算法基於信息素在環境中的指示，遺傳演算法是基於優勝劣汰的生物進化思想
遺傳演算法有選擇，交叉，變異三種運算元，每種運算元又有各自的不同方法，通過對運算元方法的修改和搭配，可以得到不同的改進遺傳演算法
蟻群演算法則多和其他智能演算法相結合，得到改進的蟻群演算法