蟻群演算法tsp
㈠ 請教，採用蟻群演算法求解TSP問題的oliver30最優路徑
給你產考產考//蟻群演算法關於簡單的TSP問題求解//#include#include#include#include#include#defineM13//螞蟻的數量#defineN144//城市的數量#defineR1000//迭代次數#defineIN1//初始化的信息素的量#defineMAX0x7fffffff//定義最大值structcoordinate{charcity[15];//城市名intx;//城市相對橫坐標inty;//城市相對縱坐標}coords[N];doublegraph[N][N];//儲存城市之間的距離的鄰接矩陣,自己到自己記作MAXdoublephe[N][N];//每條路徑上的信息素的量doubleadd[N][N];//代表相應路徑上的信息素的增量doubleyita[N][N];//啟發函數,yita[i][j]=1/graph[i][j]intvis[M][N];//標記已經走過的城市intmap[M][N];//map[K][N]記錄第K只螞蟻走的路線doublesolution[M];//記錄某次循環中每隻螞蟻走的路線的距離intbestway[N];//記錄最近的那條路線doublebestsolution=MAX;intNcMax;//代表迭代次數,理論上迭代次數越多所求的解更接近最優解,最具有說服力doublealpha,betra,rou,Q;voidInitialize();//信息初始化voidInputcoords(FILE*fp);//將文件中的坐標信息讀入voidGreateGraph();//根據坐標信息建圖doubleDistance(int*p);//計算螞蟻所走的路線的總長度voidResult();//將結果保存到out.txt中voidInitialize(){alpha=2;betra=2;rou=0.7;Q=5000;NcMax=R;return;}voidInputcoords(FILE*fp){inti;intnumber;if(fp==NULL){printf("Sorry,thefileisnotexist\n");exit(1);}else{for(i=0;idrand)break;}vis[k][j]=1;//將走過的城市標記起來map[k][s]=j;//記錄城市的順序}s++;}memset(add,0,sizeof(add));for(k=0;k20)//設立一個上界,防止啟發因子的作用被淹沒phe[i][j]=20;}}memset(vis,0,sizeof(vis));memset(map,-1,sizeof(map));}Result();printf("Resultissavedinout.txt\n");return0;}
㈡ TSP中用蟻群演算法和遺傳演算法有區別么
TSP,只是一個普通但很經典的NP-C問題。具有大的難以想像的解空間。一般的branch-and-bound演算法是很難搞定的。於是,人們嘗試智能演算法,包括遺傳演算法,蟻群演算法,粒子群演算法等。遺傳演算法和蟻群演算法都是基於種群的。但是這兩個演算法有著本質區別。遺傳演算法的進化機制是基於個體競爭,而蟻群演算法的搜索機制則是螞蟻之間的信息素傳導機制下的群體合作。因此,蟻群演算法,粒子群演算法,人工魚群演算法等,被歸納為群智能演算法,成為了一個有別於遺傳演算法的另一個進化計算領域的分支。由於搜索機制的不同,這兩種演算法對於不同的問題,具有不同的效率。就拿標准遺傳演算法和標准蟻群演算法來說,應該是蟻群演算法更適合求解TSP。然而,無論是遺傳演算法還是蟻群演算法,都有大量的變種演算法或者稱為改進演算法,所以很難簡單的說誰更適合TSP。
記得採納啊
㈢ MATLAB 蟻群演算法求解TSP問題
n個城市，編號為1---n
for循環的次數是螞蟻重復城市的次數，比如5個螞蟻放到4個城市，需要重復兩遍才能放完螞蟻，每次循環產生n個1---n的隨機數,相當於隨機n個城市，產生城市序列
循環結束
Tabu一句表示將m個螞蟻隨機，每個螞蟻放到前面產生的城市序列中，每個螞蟻一個城市，需要m個，所以提取前面1：m個序列
'表示轉置，沒有多大用處，可能參與後面的計算方便。
我感覺如果m,n很大的話，你這樣做會產生很大的浪費，計算很多的隨機數，這樣的話更好，一句就得：(如果變數Randpos後面沒有用到的話，如果用到了，還要用你的程序)
Tabu=ceil(n*rand(1,m))'
㈣ 遺傳演算法和蟻群演算法在求解TSP問題上的對比分析
【原創】比遺傳演算法性能更好：蟻群演算法TSP(旅行商問題)通用matlab程序
聲明：本程序為本人原創，在研學論壇首次發表，本人保留一切權利，僅供學習交流用，如轉載請註明原作者！
function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)
%%=========================================================================
%% ACATSP.m
%% Ant Colony Algorithm for Traveling Salesman Problem
%% ChengAihua,PLA Information Engineering University,ZhengZhou,China
%% Email:[email protected]
%% All rights reserved
%%-------------------------------------------------------------------------
%% 主要符號說明
%% C n個城市的坐標，n×2的矩陣
%% NC_max 最大迭代次數
%% m 螞蟻個數
%% Alpha 表徵信息素重要程度的參數
%% Beta 表徵啟發式因子重要程度的參數
%% Rho 信息素蒸發系數
%% Q 信息素增加強度系數
%% R_best 各代最佳路線
%% L_best 各代最佳路線的長度
%%=========================================================================
%%第一步：變數初始化
n=size(C,1);%n表示問題的規模（城市個數）
D=zeros(n,n);%D表示完全圖的賦權鄰接矩陣
for i=1:n
for j=1:n
if i~=j
D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
else
D(i,j)=eps;
end
D(j,i)=D(i,j);
end
end
Eta=1./D;%Eta為啟發因子，這里設為距離的倒數
Tau=ones(n,n);%Tau為信息素矩陣
Tabu=zeros(m,n);%存儲並記錄路徑的生成
NC=1;%迭代計數器
R_best=zeros(NC_max,n);%各代最佳路線
L_best=inf.*ones(NC_max,1);%各代最佳路線的長度
L_ave=zeros(NC_max,1);%各代路線的平均長度
while NC<=NC_max%停止條件之一：達到最大迭代次數
%%第二步：將m只螞蟻放到n個城市上
Randpos=[];
for i=1:(ceil(m/n))
Randpos=[Randpos,randperm(n)];
end
Tabu(:,1)=(Randpos(1,1:m))';
%%第三步：m只螞蟻按概率函數選擇下一座城市，完成各自的周遊
for j=2:n
for i=1:m
visited=Tabu(i,1:(j-1));%已訪問的城市
J=zeros(1,(n-j+1));%待訪問的城市
P=J;%待訪問城市的選擇概率分布
Jc=1;
for k=1:n
if length(find(visited==k))==0
J(Jc)=k;
Jc=Jc+1;
end
end
%下面計算待選城市的概率分布
for k=1:length(J)
P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);
end
P=P/(sum(P));
%按概率原則選取下一個城市
Pcum=cumsum(P);
Select=find(Pcum>=rand);
to_visit=J(Select(1));
Tabu(i,j)=to_visit;
end
end
if NC>=2
Tabu(1,:)=R_best(NC-1,:);
end
%%第四步：記錄本次迭代最佳路線
L=zeros(m,1);
for i=1:m
R=Tabu(i,:);
for j=1:(n-1)
L(i)=L(i)+D(R(j),R(j+1));
end
L(i)=L(i)+D(R(1),R(n));
end
L_best(NC)=min(L);
pos=find(L==L_best(NC));
R_best(NC,:)=Tabu(pos(1),:);
L_ave(NC)=mean(L);
NC=NC+1
%%第五步：更新信息素
Delta_Tau=zeros(n,n);
for i=1:m
for j=1:(n-1)
Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);
end
Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);
end
Tau=(1-Rho).*Tau+Delta_Tau;
%%第六步：禁忌表清零
Tabu=zeros(m,n);
end
%%第七步：輸出結果
Pos=find(L_best==min(L_best));
Shortest_Route=R_best(Pos(1),:)
Shortest_Length=L_best(Pos(1))
subplot(1,2,1)
DrawRoute(C,Shortest_Route)
subplot(1,2,2)
plot(L_best)
hold on
plot(L_ave)
function DrawRoute(C,R)
%%=========================================================================
%% DrawRoute.m
%% 畫路線圖的子函數
%%-------------------------------------------------------------------------
%% C Coordinate 節點坐標，由一個N×2的矩陣存儲
%% R Route 路線
%%=========================================================================
N=length(R);
scatter(C(:,1),C(:,2));
hold on
plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])
hold on
for ii=2:N
plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)])
hold on
end
設置初始參數如下：
m=31;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100;
31城市坐標為：
1304 2312
3639 1315
4177 2244
3712 1399
3488 1535
3326 1556
3238 1229
4196 1004
4312 790
4386 570
3007 1970
2562 1756
2788 1491
2381 1676
1332 695
3715 1678
3918 2179
4061 2370
3780 2212
3676 2578
4029 2838
4263 2931
3429 1908
3507 2367
3394 2643
3439 3201
2935 3240
3140 3550
2545 2357
2778 2826
2370 2975
運行後得到15602的巡遊路徑，
㈤ 關於神經網路，蟻群演算法和遺傳演算法
神經網路並行性和自適應性很強，應用領域很廣，在任何非線性問題中都可以應用，如控制、信息、預測等各領域都能應用。
蟻群演算法最開始應用於TSP問題，獲得了成功，後來又廣泛應用於各類組合優化問題。但是該演算法理論基礎較薄弱，演算法收斂性都沒有得到證明，很多參數的設定也僅靠經驗，實際效果也一般，使用中也常常早熟。
遺傳演算法是比較成熟的演算法，它的全局尋優能力很強，能夠很快地趨近較優解。主要應用於解決組合優化的NP問題。
這三種演算法可以相互融合，例如GA可以優化神經網路初始權值，防止神經網路訓練陷入局部極小且加快收斂速度。蟻群演算法也可用於訓練神經網路，但一定要使用優化後的蟻群演算法，如最大-最小蟻群演算法和帶精英策略。
㈥ 蟻群演算法
在螞蟻種群中，螞蟻間相互交流的方式是通過一種名為信息素的物質，它可以是螞蟻行動時留下的物質，可以被其他螞蟻所感知。
在尋找食物的過程中，如左圖所示，三角形ABC是等邊三角形，螞蟻窩在A點，C點有食物，A點的兩只螞蟻選擇了兩條路線前往C點，一條為AB->BC，另一條A->C，當走遠路的螞蟻，到達C點時，延AC邊上的螞蟻已經走了一個來回，路徑上信息素如右圖所示。後到會感知到邊AC上的信息素濃度更高一些，於是他也會選擇AC來行走，因為相同時間內，信息素濃度更高的說明，路程更短。
蟻群演算法便是基於這樣的一個思想來解決如TSP等優化問題，一下介紹便是拿TSP問題來介紹蟻群演算法
信息素用符號τ來表示，如下式，下標i，j表示從城市i到城市j這條道路上的信息素，上標0表示這是初次計算，也就是初始信息素，初始信息素都設置為1，或者一個較小的常數，表示每條道路上的信息素都相等，這樣通過運算螞蟻爬向各個城市的概率都相等
基於信息素，每隻螞蟻都有一個選擇道路的公式，如下式
其中
當所有螞蟻完成一次周遊後，各個路徑上的信息素進行一次更新
㈦ 蟻群演算法解決TSP問題，最優解是多少，參數如何選擇
概念：蟻群演算法(ant colony optimization, ACO)，又稱螞蟻演算法，是一種用來在圖中尋找優化路徑的機率型演算法。它由Marco Dorigo於1992年在他的博士論文中提出，其靈感來源於螞蟻在尋找食物過程中發現路徑的行為。蟻群演算法是一種模擬進化演算法,初步的研究表明該演算法具有許多優良的性質.針對PID控制器參數優化設計問題,將蟻群演算法設計的結果與遺傳演算法設計的結果進行了比較,數值模擬結果表明,蟻群演算法具有一種新的模擬進化優化方法的有效性和應用價值
其原理：為什麼小小的螞蟻能夠找到食物？他們具有智能么？設想，如果我們要為螞蟻設計一個人工智慧的程序，那麼這個程序要多麼復雜呢？首先，你要讓螞蟻能夠避開障礙物，就必須根據適當的地形給它編進指令讓他們能夠巧妙的避開障礙物，其次，要讓螞蟻找到食物，就需要讓他們遍歷空間上的所有點；再次，如果要讓螞蟻找到最短的路徑，那麼需要計算所有可能的路徑並且比較它們的大小，而且更重要的是，你要小心翼翼的編程，因為程序的錯誤也許會讓你前功盡棄。這是多麼不可思議的程序！太復雜了，恐怕沒人能夠完成這樣繁瑣冗餘的程序
應用范圍：螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數為速度半徑（一般是3），那麼它能觀察到的范圍就是3*3個方格世界，並且能移動的距離也在這個范圍之內
引申：跟著螞蟻的蹤跡，你找到了什麼？通過上面的原理敘述和實際操作，我們不難發現螞蟻之所以具有智能行為，完全歸功於它的簡單行為規則，而這些規則綜合起來具有下面兩個方面的特點： 1、多樣性 2、正反饋 多樣性保證了螞蟻在覓食的時候不置走進死胡同而無限循環，正反饋機制則保證了相對優良的信息能夠被保存下來。我們可以把多樣性看成是一種創造能力，而正反饋是一種學習強化能力。正反饋的力量也可以比喻成權威的意見，而多樣性是打破權威體現的創造性，正是這兩點小心翼翼的巧妙結合才使得智能行為涌現出來了。 引申來講，大自然的進化，社會的進步、人類的創新實際上都離不開這兩樣東西，多樣性保證了系統的創新能力，正反饋保證了優良特性能夠得到強化，兩者要恰到好處的結合。如果多樣性過剩，也就是系統過於活躍，這相當於螞蟻會過多的隨機運動，它就會陷入混沌狀態；而相反，多樣性不夠，正反饋機制過強，那麼系統就好比一潭死水。這在蟻群中來講就表現為，螞蟻的行為過於僵硬，當環境變化了，螞蟻群仍然不能適當的調整。 既然復雜性、智能行為是根據底層規則涌現的，既然底層規則具有多樣性和正反饋特點，那麼也許你會問這些規則是哪裡來的？多樣性和正反饋又是哪裡來的？我本人的意見：規則來源於大自然的進化。而大自然的進化根據剛才講的也體現為多樣性和正反饋的巧妙結合。而這樣的巧妙結合又是為什麼呢？為什麼在你眼前呈現的世界是如此栩栩如生呢？答案在於環境造就了這一切，之所以你看到栩栩如生的世界，是因為那些不能夠適應環境的多樣性與正反饋的結合都已經死掉了，被環境淘汰了！ 蟻群演算法的實現 下面的程序開始運行之後，螞蟻們開始從窩里出動了，尋找食物；他們會順著屏幕爬滿整個畫面，直到找到食物再返回窩。 其中，『F』點表示食物，『H』表示窩，白色塊表示障礙物，『+』就是螞蟻了。
具體參考http://ke..com/view/539346.htm
希望對你有幫助，謝謝。
㈧ 量子蟻群演算法求解TSP問題的matlab編程實現
可以的 你的點坐標都是多少
㈨ TSP是什麼意思啊
TSP即旅行商問題，即TSP問題（Traveling Salesman Problem）又譯為旅行推銷員問題、貨郎擔問題，是數學領域中著名問題之一。
假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市，路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。
TSP問題是一個組合優化問題。該問題可以被證明具有NPC計算復雜性。因此，任何能使該問題的求解得以簡化的方法，都將受到高度的評價和關注。
(9)蟻群演算法tsp擴展閱讀：
描述
TSP問題作為圖論問題可以用無向加權圖來對TSP建模，則城市是圖的頂點，道路是圖的邊，道路的距離就是該邊的長度。它是起點和終點都在一個特定頂點，訪問每個頂點恰好一次的最小化問題。通常，該模型是一個完全圖（即每對頂點由一條邊連接）。
如果兩個城市之間不存在路徑，則增加一條非常長的邊就可以完成圖，而不影響計算最優迴路。
TSP問題非對稱和對稱，在對稱TSP問題中，兩座城市之間來回的距離是相等的，形成一個無向圖。這種對稱性將解的數量減少了一半。
㈩ 幾種蟻群演算法介紹
最早的蟻群演算法，其在小規模TSP中性能尚可，再大規模TSP問題中性能下降，容易停滯。其解決旅行商問題（TSP）過程大致如下：
在初始時刻，m只螞蟻被隨機的放到城市中，在各條路徑上的信息素初始值相等。
螞蟻按照隨機比例規則從允許的城市中選擇下一個城市：
τ為信息素，η 為啟發式因子，a_k 為下一步被允許城市的集合。
使用禁忌表記錄螞蟻走過的城市，不允許螞蟻選擇已經訪問過的城市。
所有螞蟻完成一次周遊後，計算每隻螞蟻的路徑長度，裂顫保存最短路徑長度。敬桐
更新每個城市信息素：
τ=(1−ρ)τ+∑Δτ, 0≤ρ≤1
Δτ=1/d
由上可知，先揮發信息素，再增加信息素。其中d為路徑距離，路徑越短，信息素增加越多。∑Δτ表示所有本次覓食過程中所有經過此城市的覓食成功的路線的信息素累加。
清空禁忌表，開始下一次周遊。
對演算法每次循環之後給予最亮源坦優路徑額外的信息素。
對於普通路徑中的每個城市：
τ(t+1)=(1−ρ)τ(t)+∑Δτ
對於最優路徑中的每個城市：
τ(t+1)=(1−ρ)τ(t)+∑Δτ+eΔτ^(bs)
Δτ^(bs)=1/L
其中L代表最優路徑長度，e是一個參數，表示權值大小。
目前解決TSP問題最好的蟻群演算法之一，在螞蟻系統的基礎上進行了如下更改：
對於一般城市： τ(t+1)=(1−ρ)τ(t)
對於最優路徑上的城市：τ(t+1)=(1−ρ)τ(t)+∑Δτ