%====================================
%蟻群算法求解TSP問題
%====================================
clc
clear?all;
close?all;
%初始化蟻群
fid=fopen（‘Cities.txt‘‘rt‘）;
C=fscanf（fid‘%g‘[234]）;%讀取城市的坐標矩陣
fclose（fid）;
C=C‘;%城市坐標采用n*2的矩陣存儲
Nc_max=1500;%最大迭代次數
alpha=1;%螞蟻在運動過程中所積累信息（即信息素）在螞蟻選擇路徑時的相對重要程度，alpha過大時，算法迭代到一定代數后將出現停滯現象
beta=5;%啟發式因子在螞蟻選擇路徑時的相對重要程度
rho=0.5;%0Q=100;%螞蟻釋放的信息素量，對本算法的性能影響不大

%變量初始化
n=size（C1）;%表示TSP問題的規模，亦即城市的數量
m=n;%蟻群中螞蟻的數量，當m接近或等于城市個數n時，本算法可以在最少的迭代次數內找到最優解
D=ones（nn）;%表示城市完全地圖的賦權鄰接矩陣，記錄城市之間的距離

for?i=1:n
????for?j=1:n
????????if?i????????????D（ij）=sqrt（（C（i1）-C（j1））^2+（C（i2）-C（j2））^2）;
????????end
????D（ji）=D（ij）;
????end
end
eta=1./D;%啟發式因子，這里設為城市之間距離的倒數
pheromone=ones（nn）;%信息素矩陣這里假設任何兩個城市之間路徑上的初始信息素都為1
tabu_list=zeros（mn）;%禁忌表，記錄螞蟻已經走過的城市，螞蟻在本次循環中不能再經過這些城市。當本次循環結束后，禁忌表被用來計算螞蟻當前所建立的解決方案，即經過的路徑和路徑的長度
Nc=0;%循環次數計數器
repeat_num=0;%迭代終止參數，當最短路徑重復重復次數，當達此條件時停止迭代
routh_best=zeros（Nc_maxn）;%各次循環的最短路徑
length_best=ones（Nc_max1）;%各次循環最短路徑的長度
length_average=ones（Nc_max1）;%各次循環所有路徑的平均長度
tic
while?Nc????%將m只螞蟻放在n個城市上
????rand_position=[];
????for?i=1:ceil（m/n）
????????rand_position=[rand_positionrandperm（n）];
????end
????tabu_list（:1）=（rand_position（1:m））‘;%將螞蟻放在城市上之后的禁忌表，第i行表示第i只螞蟻，第i行第一列元素表示第i只螞蟻所在的初始城市
????%m只螞蟻按概率函數選擇下一座城市，在本次循環中完成各自的周游
????for?j=2:n
????????for?i=1:m
????????????city_visited=tabu_list（i1:（j-1））;%已訪問的城市
????????????city_remained=zeros（1（n-j+1））;%待訪問的城市
????????????probability=city_remained;%待訪問城市的訪問概率
????????????cr=1;
????????????for?k=1:n%for循環用于求待訪問的城市。比如如果城市個數是5，而已訪問的城市city_visited=[2?4]則經過此for循環后city_remanied=[1?3?5]
????????????????if?isempty（find（city_visited==k））
????????????????????city_remained（cr）=k;
????????????????????cr=cr+1;
????????????????end
????????????end
????????????%狀態轉移規則****************************************
????????????q0=0.5;
????????????if?rand>q0
????????????????for?k=1:length（city_remained）
????????????????????probability（k）=（pheromone（city_visited（end）city_remained（k）））^alpha*（eta（city_visited（end）city_remained（k）））^beta;
????????????????end
????????????????path=find（probability==max（probability））;
????????????????to_visit=city_remained（path（1））;
????????????else
????????????????for?k=1:length（city_remained）
????????????????????probability（k）=（pheromone（city_visited（end）city_remained（k）））^alpha*（eta（city_visited（end）city_remained（k）））^beta;
????????????????end
????????????????probability=probability/sum（probability）;
????????????????pcum=cumsum（probability）;
????????????????select=find（pcum>=rand）;
????????????????to_visit=city_remained（select（1））;
????????????end
????????????tabu_list（ij）=to_visit;
????????????%**************************************************************
????????end
????end
????if?Nc>0
????????tabu_list（1:）=routh_best（Nc:）;%將上一代的最優路徑（最優解）保留下來，保證上一代中的最適應個體的信息不會丟失
????end
????%記錄本次循環的最佳路線
????tot

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件????????931??2012-12-11?16:29??Cities.txt

?????文件???????6481??2012-12-11?16:42??ACA_TSP.m

-----------?---------??----------?-----??----

?????????????????7412????????????????????2