%蟻群算法求解TSP問題的matlab程序
clear?all
close?all
clc

%初始化蟻群
m=31;%蟻群中螞蟻的數(shù)量，當(dāng)m接近或等于城市個(gè)數(shù)n時(shí)，本算法可以在最少的迭代次數(shù)內(nèi)找到最優(yōu)解
C=[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];%城市的坐標(biāo)矩陣
Nc_max=200;%最大循環(huán)次數(shù)，即算法迭代的次數(shù)，亦即螞蟻出動(dòng)的撥數(shù)（每撥螞蟻的數(shù)量當(dāng)然都是m）
alpha=1;%螞蟻在運(yùn)動(dòng)過程中所積累信息（即信息素）在螞蟻選擇路徑時(shí)的相對重要程度，alpha過大時(shí)，算法迭代到一定代數(shù)后將出現(xiàn)停滯現(xiàn)象
beta=5;%啟發(fā)式因子在螞蟻選擇路徑時(shí)的相對重要程度
rho=0.5;%0Q=100;%螞蟻釋放的信息素量，對本算法的性能影響不大

%變量初始化
n=size（C1）;%表示TSP問題的規(guī)模，亦即城市的數(shù)量
D=ones（nn）;%表示城市完全地圖的賦權(quán)鄰接矩陣，記錄城市之間的距離
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;%啟發(fā)式因子，這里設(shè)為城市之間距離的倒數(shù)
pheromone=ones（nn）;%信息素矩陣這里假設(shè)任何兩個(gè)城市之間路徑上的初始信息素都為1
tabu_list=zeros（mn）;%禁忌表，記錄螞蟻已經(jīng)走過的城市，螞蟻在本次循環(huán)中不能再經(jīng)過這些城市。當(dāng)本次循環(huán)結(jié)束后，禁忌表被用來計(jì)算螞蟻當(dāng)前所建立的解決方案，即經(jīng)過的路徑和路徑的長度
Nc=0;%循環(huán)次數(shù)計(jì)數(shù)器
routh_best=zeros（Nc_maxn）;%各次循環(huán)的最短路徑
length_best=ones（Nc_max1）;%各次循環(huán)最短路徑的長度
length_average=ones（Nc_max1）;%各次循環(huán)所有路徑的平均長度

while?Nc????%將m只螞蟻放在n個(gè)城市上
????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只螞蟻按概率函數(shù)選擇下一座城市，在本次循環(huán)中完成各自的周游
????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循環(huán)用于求待訪問的城市。比如如果城市個(gè)數(shù)是5，而已訪問的城市city_visited=[2?4]則經(jīng)過此for循環(huán)后city_remanied=[1?3?5]
????????????????if?length（find（city_visited==k））==0
????????????????????city_remained（cr）=k;
????????????????????cr=cr+1;
????????????????end
????????????end
????????????%for循環(huán)計(jì)算待訪問城市的訪問概率分布，此概率和兩個(gè)參數(shù)有關(guān)，一是螞蟻當(dāng)前所在城市（即city_visited（end））和待訪問城市（即city_remained（k））路徑上的信息素，一是這兩者之間的啟發(fā)因子即距離的倒數(shù)????????????
????????????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）;
????????????%按概率選取下一個(gè)要訪問的城市????????????????????????????????
????????????pcum=cumsum（probability）;
????????????select=find（pcum>=rand）;
????????????to_visit=city_remained（select（1））;
????????????tabu_list（ij）=to_visit;
????????end
????end
????if?Nc>0
????????tabu_list（1:）=routh_best（Nc:）;%將上一代的最優(yōu)路徑（最優(yōu)解）保留下來，保證上一代中的最適應(yīng)個(gè)體的信息不會(huì)丟失
????end
????%記錄本次循環(huán)的最佳路線
????total_length=zeros（m1）;%m只螞蟻在本次循環(huán)中分別所走過的路徑長度
????for?i=1:m
????????r=tabu_list（i:）;%取出第i只螞蟻在本次循環(huán)中所走的路徑
????????for?j=1:（n-1）
????????????total_length（i）=total_length（i）+D（r（j）r（j+1））;%第i只螞蟻本次循環(huán)中從起點(diǎn)城市到終點(diǎn)城市所走過的路徑長度
????????end

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件???????5947??2008-05-14?08:44??ant_colony.m

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

?????????????????5947????????????????????1