ACO演算法對於TSP問題的實現

Ⅰ 蟻群優化的目錄

1 從真實螞蟻到人工螞蟻
1.1 螞蟻的覓食行為及其優化過程
1.2 向人工螞蟻轉換
1.3 人工螞蟻和最小成本路徑
1.4 書目評注
1.5 需要牢記的知識點
1.6 思考與計算習題
2 蟻群優化元啟發式演算法
2.1 組合優化
2.2 ACO元啟發式演算法
2.3 如何應用ACO
2.4 其他元啟發式演算法
2.5 書目評注
2.6 需要牢記的知識點
2.7 思考與計算習題
3 旅行商問題中的蟻群優化演算法
3.1 旅行商問題
3.2 TSP中的ACO演算法
3.3 螞蟻系統及其直接後續演算法
3.4 螞蟻系統的擴展
3.5 並行執行
3.6 實驗測評
3.7 添加局部搜索的ACO
3.8 ACO演算法的實現
3.9 書目評注
3.10 需要牢記的知識點
3.11 思考與計算習題
4 蟻群優化理論
4.1 ACO的理論思考
4.2 問題和演算法
4.3 收斂性證明
4.4 ACO與基本模型的搜索
4.5 書目評注
4.6 需要牢記的知識點
4.7 思考與計算習題
5 NP-難問題的蟻群優化
6 數據網路路由中的ACO演算法
7 總結與對未來的展望
附錄 有關ACO領域的信息來源
參考文獻
索引

Ⅱ 蟻群演算法求解TSP問題的源程序及簡要說明

該程序試圖對具有31個城市的VRP進行求解，已知的最優解為784.1，我用該程序只能優化到810左右，應該是陷入局部最優，但我不知問題出在什麼地方。請用過蟻群演算法的高手指教。
蟻群演算法的matlab源碼，同時請指出為何不能優化到已知的最好解

%
%
% the procere of ant colony algorithm for VRP
%
% % % % % % % % % % %

%initialize the parameters of ant colony algorithms
load data.txt;
d=data(:,2:3);
g=data(:,4);

m=31; % 螞蟻數
alpha=1;
belta=4;% 決定tao和miu重要性的參數
lmda=0;
rou=0.9; %衰減系數
q0=0.95;
% 概率
tao0=1/(31*841.04);%初始信息素
Q=1;% 螞蟻循環一周所釋放的信息素
defined_phrm=15.0; % initial pheromone level value
QV=100; % 車輛容量
vehicle_best=round(sum(g)/QV)+1; %所完成任務所需的最少車數
V=40;

% 計算兩點的距離
for i=1:32;
for j=1:32;
dist(i,j)=sqrt((d(i,1)-d(j,1))^2+(d(i,2)-d(j,2))^2);
end;
end;

%給tao miu賦初值
for i=1:32;
for j=1:32;
if i~=j;
%s(i,j)=dist(i,1)+dist(1,j)-dist(i,j);
tao(i,j)=defined_phrm;
miu(i,j)=1/dist(i,j);
end;
end;
end;

for k=1:32;
for k=1:32;
deltao(i,j)=0;
end;
end;

best_cost=10000;
for n_gen=1:50;

print_head(n_gen);

for i=1:m;
%best_solution=[];
print_head2(i);
sumload=0;
cur_pos(i)=1;
rn=randperm(32);
n=1;
nn=1;
part_sol(nn)=1;
%cost(n_gen,i)=0.0;
n_sol=0; % 由螞蟻產生的路徑數量
M_vehicle=500;
t=0; %最佳路徑數組的元素數為0

while sumload<=QV;

for k=1:length(rn);
if sumload+g(rn(k))<=QV;
gama(cur_pos(i),rn(k))=(sumload+g(rn(k)))/QV;
A(n)=rn(k);
n=n+1;
end;
end;

fid=fopen('out_customer.txt','a+');
fprintf(fid,'%s %i\t','the current position is:',cur_pos(i));
fprintf(fid,'\n%s','the possible customer set is:')
fprintf(fid,'\t%i\n',A);
fprintf(fid,'------------------------------\n');
fclose(fid);

p=compute_prob(A,cur_pos(i),tao,miu,alpha,belta,gama,lmda,i);
maxp=1e-8;
na=length(A);
for j=1:na;
if p(j)>maxp
maxp=p(j);
index_max=j;
end;
end;

old_pos=cur_pos(i);
if rand(1)<q0
cur_pos(i)=A(index_max);
else
krnd=randperm(na);
cur_pos(i)=A(krnd(1));
bbb=[old_pos cur_pos(i)];
ccc=[1 1];
if bbb==ccc;
cur_pos(i)=A(krnd(2));
end;
end;

tao(old_pos,cur_pos(i))=taolocalupdate(tao(old_pos,cur_pos(i)),rou,tao0);%對所經弧進行局部更新

sumload=sumload+g(cur_pos(i));

nn=nn+1;
part_sol(nn)=cur_pos(i);
temp_load=sumload;

if cur_pos(i)~=1;
rn=setdiff(rn,cur_pos(i));
n=1;
A=[];
end;

if cur_pos(i)==1; % 如果當前點為車場,將當前路徑中的已訪問用戶去掉後,開始產生新路徑
if setdiff(part_sol,1)~=[];
n_sol=n_sol+1; % 表示產生的路徑數,n_sol=1,2,3,..5,6...,超過5條對其費用加上車輛的派遣費用
fid=fopen('out_solution.txt','a+');
fprintf(fid,'%s%i%s','NO.',n_sol,'條路徑是:');
fprintf(fid,'%i ',part_sol);
fprintf(fid,'\n');
fprintf(fid,'%s','當前的用戶需求量是:');
fprintf(fid,'%i\n',temp_load);
fprintf(fid,'------------------------------\n');
fclose(fid);

% 對所得路徑進行路徑內3-opt優化
final_sol=exchange(part_sol);

for nt=1:length(final_sol); % 將所有產生的路徑傳給一個數組
temp(t+nt)=final_sol(nt);
end;
t=t+length(final_sol)-1;

sumload=0;
final_sol=setdiff(final_sol,1);
rn=setdiff(rn,final_sol);
part_sol=[];
final_sol=[];
nn=1;
part_sol(nn)=cur_pos(i);
A=[];
n=1;

end;
end;

if setdiff(rn,1)==[];% 產生最後一條終點不為1的路徑
n_sol=n_sol+1;
nl=length(part_sol);
part_sol(nl+1)=1;%將路徑的最後1位補1

% 對所得路徑進行路徑內3-opt優化
final_sol=exchange(part_sol);

for nt=1:length(final_sol); % 將所有產生的路徑傳給一個數組
temp(t+nt)=final_sol(nt);
end;

cost(n_gen,i)=cost_sol(temp,dist)+M_vehicle*(n_sol-vehicle_best); %計算由螞蟻i產生的路徑總長度

for ki=1:length(temp)-1;
deltao(temp(ki),temp(ki+1))=deltao(temp(ki),temp(ki+1))+Q/cost(n_gen,i);
end;

if cost(n_gen,i)<best_cost;
best_cost=cost(n_gen,i);
old_cost=best_cost;
best_gen=n_gen; % 產生最小費用的代數
best_ant=i; %產生最小費用的螞蟻
best_solution=temp;
end;

if i==m; %如果所有螞蟻均完成一次循環，，則用最佳費用所對應的路徑對弧進行整體更新
for ii=1:32;
for jj=1:32;
tao(ii,jj)=(1-rou)*tao(ii,jj);
end;
end;

for kk=1:length(best_solution)-1;
tao(best_solution(kk),best_solution(kk+1))=tao(best_solution(kk),best_solution(kk+1))+deltao(best_solution(kk),best_solution(kk+1));
end;
end;

fid=fopen('out_solution.txt','a+');
fprintf(fid,'%s%i%s','NO.',n_sol,'路徑是:');
fprintf(fid,'%i ',part_sol);
fprintf(fid,'\n');
fprintf(fid,'%s %i\n','當前的用戶需求量是:',temp_load);
fprintf(fid,'%s %f\n','總費用是:',cost(n_gen,i));
fprintf(fid,'------------------------------\n');
fprintf(fid,'%s\n','最終路徑是:');
fprintf(fid,'%i-',temp);
fprintf(fid,'\n');
fclose(fid);
temp=[];
break;
end;
end;

end;
end;
我現在也在研究它,希望能共同進步.建義可以看一下段海濱的關於蟻群演算法的書.講的不錯,李士勇的也可以,還有一本我在圖書館見過,記不得名字了.

Ⅲ TSP問題的演算法

你是說有10個點，想選4個點么，找4個點+起點的周遊最小值？
點比較少，枚舉4個點，C(10,4) = 210 種情況，然後找所有情況的最小值。那麼最後這4個點就是你要的4個點。

Ⅳ 蟻群演算法解決TSP問題，最優解是多少，參數如何選擇

概念：蟻群演算法(ant colony optimization, ACO)，又稱螞蟻演算法，是一種用來在圖中尋找優化路徑的機率型演算法。它由Marco Dorigo於1992年在他的博士論文中提出，其靈感來源於螞蟻在尋找食物過程中發現路徑的行為。蟻群演算法是一種模擬進化演算法,初步的研究表明該演算法具有許多優良的性質.針對PID控制器參數優化設計問題,將蟻群演算法設計的結果與遺傳演算法設計的結果進行了比較,數值模擬結果表明,蟻群演算法具有一種新的模擬進化優化方法的有效性和應用價值

其原理：為什麼小小的螞蟻能夠找到食物？他們具有智能么？設想，如果我們要為螞蟻設計一個人工智慧的程序，那麼這個程序要多麼復雜呢？首先，你要讓螞蟻能夠避開障礙物，就必須根據適當的地形給它編進指令讓他們能夠巧妙的避開障礙物，其次，要讓螞蟻找到食物，就需要讓他們遍歷空間上的所有點；再次，如果要讓螞蟻找到最短的路徑，那麼需要計算所有可能的路徑並且比較它們的大小，而且更重要的是，你要小心翼翼的編程，因為程序的錯誤也許會讓你前功盡棄。這是多麼不可思議的程序！太復雜了，恐怕沒人能夠完成這樣繁瑣冗餘的程序

應用范圍：螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數為速度半徑（一般是3），那麼它能觀察到的范圍就是3*3個方格世界，並且能移動的距離也在這個范圍之內

引申：跟著螞蟻的蹤跡，你找到了什麼？通過上面的原理敘述和實際操作，我們不難發現螞蟻之所以具有智能行為，完全歸功於它的簡單行為規則，而這些規則綜合起來具有下面兩個方面的特點： 1、多樣性 2、正反饋 多樣性保證了螞蟻在覓食的時候不置走進死胡同而無限循環，正反饋機制則保證了相對優良的信息能夠被保存下來。我們可以把多樣性看成是一種創造能力，而正反饋是一種學習強化能力。正反饋的力量也可以比喻成權威的意見，而多樣性是打破權威體現的創造性，正是這兩點小心翼翼的巧妙結合才使得智能行為涌現出來了。 引申來講，大自然的進化，社會的進步、人類的創新實際上都離不開這兩樣東西，多樣性保證了系統的創新能力，正反饋保證了優良特性能夠得到強化，兩者要恰到好處的結合。如果多樣性過剩，也就是系統過於活躍，這相當於螞蟻會過多的隨機運動，它就會陷入混沌狀態；而相反，多樣性不夠，正反饋機制過強，那麼系統就好比一潭死水。這在蟻群中來講就表現為，螞蟻的行為過於僵硬，當環境變化了，螞蟻群仍然不能適當的調整。 既然復雜性、智能行為是根據底層規則涌現的，既然底層規則具有多樣性和正反饋特點，那麼也許你會問這些規則是哪裡來的？多樣性和正反饋又是哪裡來的？我本人的意見：規則來源於大自然的進化。而大自然的進化根據剛才講的也體現為多樣性和正反饋的巧妙結合。而這樣的巧妙結合又是為什麼呢？為什麼在你眼前呈現的世界是如此栩栩如生呢？答案在於環境造就了這一切，之所以你看到栩栩如生的世界，是因為那些不能夠適應環境的多樣性與正反饋的結合都已經死掉了，被環境淘汰了！ 蟻群演算法的實現 下面的程序開始運行之後，螞蟻們開始從窩里出動了，尋找食物；他們會順著屏幕爬滿整個畫面，直到找到食物再返回窩。 其中，『F』點表示食物，『H』表示窩，白色塊表示障礙物，『+』就是螞蟻了。

具體參考http://ke..com/view/539346.htm
希望對你有幫助，謝謝。

Ⅳ 什麼是tsp問題，數學模型中的一種模型問題

Traveling Saleman Problem 旅行商問題
「旅行商問題」常被稱為「旅行推銷員問題」，是指一名推銷員要拜訪多個地點時，如何找到在拜訪每個地點一次後再回到起點的最短路徑。規則雖然簡單，但在地點數目增多後求解卻極為復雜。以42個地點為例，如果要列舉所有路徑後再確定最佳行程，那麼總路徑數量之大，幾乎難以計算出來。多年來全球數學家絞盡腦汁，試圖找到一個高效的演算法，近來在大型計算機的幫助下才取得了一些進展。 TSP問題在物流中的描述是對應一個物流配送公司，欲將n個客戶的訂貨沿最短路線全部送到。如何確定最短路線。 TSP問題最簡單的求解方法是枚舉法。它的解是多維的、多局部極值的、趨於無窮大的復雜解的空間，搜索空間是n個點的所有排列的集合，大小為（n-1）。可以形象地把解空間看成是一個無窮大的丘陵地帶，各山峰或山谷的高度即是問題的極值。求解TSP，則是在此不能窮盡的丘陵地帶中攀登以達到山頂或谷底的過程。

具體參見網路
http://ke..com/view/1162183.htm

多個旅行商同時出發的問題稱為MTSP問題。設立虛點轉化為TSP即可求解。
數學模型是可以用線性規劃來描述，但是在多項式求解時間內無解，所以才出現了各種啟發式演算法，什麼遺傳演算法，模擬退火，蟻群演算法之類的

Ⅵ 急求蟻群演算法解決 VRPTW問題的matlab代碼，最好是ACS或者MMAS的！

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=length(C); %n 為市個數
for i=1:n %坐標矩陣轉換為距離矩陣
for j=1:n
D(i,j)=sqrt((x(i,1)-x(j,1))^2+(x(i,2)-x(j,2))^2);
end
end
for i=1:n %Eta為啟發因子，這里設為距離的倒數
for j=1:n %原文作者少考慮的當D=0是MATLAB提示出錯
if i~=j
Eta(i,j)=1./D(i,j);
end
end
end
for i=1:n
Eta(i,i)=0;
end
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));
DrawRoute(C,Shortest_Route) %調用函數繪圖

Ⅶ tSp Concorder演算法原理

tsp問題遺傳演算法將多目標按照線性加權的方式轉化為單目標，然後應用傳統遺傳演算法求解
其中w_i表示第i個目標的權重，f_k表示歸一化之後的第i個目標值。我們很容易知道，這類方法的關鍵是怎麼設計權重。比如，Random Weight Genetic Algorithm (RWGA) 採用隨機權重的方式，每次計算適應度都對所有個體隨機地產生不同目標的權重，然後進行選擇操作。Vector-Evaluated Genetic Algorithm (VEGA) 也是基於線性加權的多目標遺傳演算法。如果有K個目標，VEGA 會隨機地將種群分為K個同等大小子種群，在不同的子種群按照不同的目標函數設定目標值，然後再進行選擇操作。VEGA 實質上是基於線性加權的多目標遺傳演算法。VEGA 是第一個多目標遺傳演算法，開啟了十幾年的研究潮流。
1.TSP問題是指假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。本文使用遺傳演算法解決att30問題，即30個城市的旅行商問題。旅行商問題是一個經典的組合優化問題。一個經典的旅行商問題可以描述為：一個商品推銷員要去若干個城市推銷商品，該推銷員從一個城市出發，需要經過所有城市後，回到出發地。應如何選擇行進路線，以使總的行程最短。從圖論的角度來看，該問題實質是在一個帶權完全無向圖中，找一個權值最小的Hamilton迴路。由於該問題的可行解是所有頂點的全排列，隨著頂點數的增加，會產生組合爆炸，它是一個NP完全問題。TSP問題可以分為對稱和不對稱。在對稱TSP問題中，兩座城市之間來回的距離是相等的，形成一個無向圖，而不對稱TSP則形成有向圖。對稱性TSP問題可以將解的數量減少了一半。所以本次實驗的TSP問題使用att48數據，可在tsplib中下載數據包。演化演算法是一類模擬自然界遺傳進化規律的仿生學演算法，它不是一個具體的演算法，而是一個演算法簇。遺傳演算法是演化演算法的一個分支，由於遺傳演算法的整體搜索策略和優化計算是不依賴梯度信息，所以它的應用比較廣泛。我們本次實驗同樣用到了遺傳演算法（用MATLAB編寫）來解決TSP問題。

Ⅷ C++演算法，動態規劃法實現TSP問題

c++listmatrixiteratoriostream演算法
[cpp] view plainprint?

#include
#include
using namespace std ;
typedef list<</SPAN>int> LISTINT;
LISTINT listAnother;
LISTINT list_result;
int d[4][4]={{-1,3,6,7},{2,-1,8,6},{7,3,-1,5,},{7,3,7,-1}}; //路徑權值
int matrix_length=4;
int getPath(int n,LISTINT list_org)
{
LISTINT::iterator i;
int minValue;
if(n==1)
{
i=list_org.begin();
minValue= d[*i-1][0];
if(list_org.size()==matrix_length-1)
{
list_result=list_org;
}
}
else
{
int temp;
i=list_org.begin();
temp=*i;
list_org.erase(i);
i=list_org.begin();
minValue=d[temp-1][*(i)-1]+getPath(n-1,list_org);
if(list_org.size()==matrix_length-1)
{
list_result=list_org;
}
for(int j=2;j
{
i=list_org.begin();
for(int k=1;k
{
i++;
}
int tempvalue=*i;
list_org.erase(i);
list_org.push_front(tempvalue);
i=list_org.begin();
tempvalue=d[temp-1][*(i)-1]+getPath(n-1,list_org);
if(tempvalue
{
if(list_org.size()==matrix_length-1)
{
list_result=list_org;
}
minValue=tempvalue;
}
}
}
return minValue;
}
int main(int argc, char* argv[])
{
LISTINT list_org;
LISTINT::iterator h;
list_org.push_front(4);
list_org.push_front(3);
list_org.push_front(2);
list_org.push_front(1);
cout<<"旅行商問題動態規劃演算法"<<endl;
cout<<"路線長度的矩陣表示如下 （-1表示無限大）"<<endl;
for(int j=0;j
cout<<endl;
for(int k=0;k
cout<<" "<<d[j][k];
}
}
cout<<endl;
cout<<"計算結果:"<<getPath(4,list_org)<<endl;
list_result.push_front(1);
list_result.push_back(1);
cout<<"要走的路徑:---->:";
for (h = list_result.begin(); h != list_result.end(); ++h)
cout << *h << " ";
cout << endl;
int i;
cin>>i;
return 0;
}