姓名：高潔
學(xué)號：19021210933
轉(zhuǎn)載自：https://blog.csdn.net/XYYHHH11/article/details/102917942
【嵌牛導(dǎo)讀】蟻群算法是對自然界螞蟻的尋徑方式進(jìn)行模似而得出的一種仿生算法：螞蟻在運(yùn)動過程中，能夠在它所經(jīng)過的路徑上留下信息素(pheromone)的物質(zhì)進(jìn)行信息傳遞，而螞蟻在運(yùn)動過程中能夠感知這種物質(zhì)澈蟆，并以此指導(dǎo)自己的運(yùn)動方向炸站。
【嵌牛鼻子】蟻群算法 信息素重要程度因子 啟發(fā)函數(shù)重要程度因子?信息素?fù)]發(fā)因子?
【嵌牛提問】蟻群算法的原理是什么？該算法如何實(shí)現(xiàn)？
【嵌牛正文】
1、基本原理
????蟻群算法是對自然界螞蟻的尋徑方式進(jìn)行模似而得出的 一種仿生算法：螞蟻在運(yùn)動過程中，能夠在它所經(jīng)過的路 徑上留下信息素(pheromone)的物質(zhì)進(jìn)行信息傳遞司致，而螞蟻在運(yùn)動過程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的 運(yùn)動方向聋迎。由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多脂矫，則后來者選擇該路徑的概率就越大。
2霉晕、基本概念和流程
????在ACO 算法中庭再，人工螞蟻實(shí)際上代表的是一個解的隨機(jī)構(gòu)建過程，從最初的空解開始娄昆，通過不斷地向部分解添加解的成分而構(gòu)建出一個完整的解佩微。
????? 解的構(gòu)建：每只螞蟻?zhàn)畛醵紡碾S機(jī)選擇出來的城市出發(fā)，每經(jīng)過一次迭代螞蟻就向解中添加一個還沒有訪問過的城市萌焰。當(dāng)所有城市都被螞蟻訪問過之后哺眯，解的構(gòu)建就終止。對于每只螞蟻k扒俯，路徑記憶向量按照訪問順序記錄了所有k已經(jīng)經(jīng)過的城市序號奶卓。設(shè)螞蟻k當(dāng)前所在城市為i一疯， 則其選擇城市j作為下一個訪問對象的概率為：
????? 信息素更新：這里m是螞蟻個數(shù), ρ是信息素的蒸發(fā)率，規(guī)定0≤ρ≤1,在AS中通常設(shè)置為ρ=0.5夺姑，△ζij是第k只螞蟻在它經(jīng)過的邊上釋放的信息素量墩邀，它等于螞蟻k本輪構(gòu)建路徑長度的倒數(shù)。C表示路徑長度盏浙，它是Rk中所有邊的長度和眉睹。
3、流程圖和偽代碼
4废膘、代碼實(shí)現(xiàn)
%% 導(dǎo)入數(shù)據(jù)
load citys_data.mat
%% 計(jì)算城市間相互距離
fprintf('Computing Distance Matrix... \n');
n = size(citys,1);
D = zeros(n,n);
for i = 1:n
? ? for j = 1:n
? ? ? ? if i ~= j
? ? ? ? ? ? D(i,j) = sqrt(sum((citys(i,:) - citys(j,:)).^2));
? ? ? ? else
? ? ? ? ? ? D(i,j) = 1e-4;? ? ?
? ? ? ? end
? ? end? ?
end
%% 初始化參數(shù)
fprintf('Initializing Parameters... \n');
m = 75;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? % 螞蟻數(shù)量
alpha = 1;? ? ? ? ? ? ? ? ? ? ? ? ? % 信息素重要程度因子
beta = 5;? ? ? ? ? ? ? ? ? ? ? ? ? ? % 啟發(fā)函數(shù)重要程度因子
rho = 0.5;? ? ? ? ? ? ? ? ? ? ? ? ? % 信息素?fù)]發(fā)因子
Q = 1;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? % 常系數(shù)
Eta = 1./D;? ? ? ? ? ? ? ? ? ? ? ? ? % 啟發(fā)函數(shù)
Tau = ones(n,n);? ? ? ? ? ? ? ? ? ? % 信息素矩陣
Table = zeros(m,n);? ? ? ? ? ? ? ? ? % 路徑記錄表
iter = 1;? ? ? ? ? ? ? ? ? ? ? ? ? ? % 迭代次數(shù)初值
iter_max = 160;? ? ? ? ? ? ? ? ? ? ? % 最大迭代次數(shù)
Route_best = zeros(iter_max,n);? ? ? % 各代最佳路徑? ? ?
Length_best = zeros(iter_max,1);? ? % 各代最佳路徑的長度?
Length_ave = zeros(iter_max,1);? ? ? % 各代路徑的平均長度?
%% 迭代尋找最佳路徑
figure;
while iter <= iter_max
? ? fprintf('迭代第%d次\n',iter);
? ? % 隨機(jī)產(chǎn)生各個螞蟻的起點(diǎn)城市
? ? ? start = zeros(m,1);
? ? ? for i = 1:m
? ? ? ? ? temp = randperm(n);
? ? ? ? ? start(i) = temp(1);
? ? ? end
? ? ? Table(:,1) = start;
? ? ? % 構(gòu)建解空間
? ? ? citys_index = 1:n;
? ? ? % 逐個螞蟻路徑選擇
? ? ? for i = 1:m
? ? ? ? ? % 逐個城市路徑選擇
? ? ? ? for j = 2:n
? ? ? ? ? ? tabu = Table(i,1:(j - 1));? ? ? ? ? % 已訪問的城市集合(禁忌表)
? ? ? ? ? ? allow_index = ~ismember(citys_index,tabu);
? ? ? ? ? ? allow = citys_index(allow_index);? % 待訪問的城市集合
? ? ? ? ? ? P = allow;
? ? ? ? ? ? % 計(jì)算城市間轉(zhuǎn)移概率
? ? ? ? ? ? for k = 1:length(allow)
? ? ? ? ? ? ? ? P(k) = Tau(tabu(end),allow(k))^alpha * Eta(tabu(end),allow(k))^beta;
? ? ? ? ? ? end
? ? ? ? ? ? P = P/sum(P);
? ? ? ? ? ? % 輪盤賭法選擇下一個訪問城市
? ? ? ? ? ? Pc = cumsum(P);? ?
? ? ? ? ? ? target_index = find(Pc >= rand);
? ? ? ? ? ? target = allow(target_index(1));
? ? ? ? ? ? Table(i,j) = target;
? ? ? ? end
? ? ? end
? ? ? % 計(jì)算各個螞蟻的路徑距離
? ? ? Length = zeros(m,1);
? ? ? for i = 1:m
? ? ? ? ? Route = Table(i,:);
? ? ? ? ? for j = 1:(n - 1)
? ? ? ? ? ? ? Length(i) = Length(i) + D(Route(j),Route(j + 1));
? ? ? ? ? end
? ? ? ? ? Length(i) = Length(i) + D(Route(n),Route(1));
? ? ? end
? ? ? % 計(jì)算最短路徑距離及平均距離
? ? ? if iter == 1
? ? ? ? ? [min_Length,min_index] = min(Length);
? ? ? ? ? Length_best(iter) = min_Length;?
? ? ? ? ? Length_ave(iter) = mean(Length);
? ? ? ? ? Route_best(iter,:) = Table(min_index,:);
? ? ? else
? ? ? ? ? [min_Length,min_index] = min(Length);
? ? ? ? ? Length_best(iter) = min(Length_best(iter - 1),min_Length);
? ? ? ? ? Length_ave(iter) = mean(Length);
? ? ? ? ? if Length_best(iter) == min_Length
? ? ? ? ? ? ? Route_best(iter,:) = Table(min_index,:);
? ? ? ? ? else
? ? ? ? ? ? ? Route_best(iter,:) = Route_best((iter-1),:);
? ? ? ? ? end
? ? ? end
? ? ? % 更新信息素
? ? ? Delta_Tau = zeros(n,n);
? ? ? % 逐個螞蟻計(jì)算
? ? ? for i = 1:m
? ? ? ? ? % 逐個城市計(jì)算
? ? ? ? ? for j = 1:(n - 1)
? ? ? ? ? ? ? Delta_Tau(Table(i,j),Table(i,j+1)) = Delta_Tau(Table(i,j),Table(i,j+1)) + Q/Length(i);
? ? ? ? ? end
? ? ? ? ? Delta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i);
? ? ? end
? ? ? Tau = (1-rho) * Tau + Delta_Tau;
? ? % 迭代次數(shù)加1竹海，清空路徑記錄表
%? figure;
%最佳路徑的迭代變化過程
? ? [Shortest_Length,index] = min(Length_best(1:iter));
? ? Shortest_Route = Route_best(index,:);
? ? plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...
? ? [citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-');
? ? pause(0.3);
? ? iter = iter + 1;
? ? Table = zeros(m,n);
% end
end
%% 結(jié)果顯示
[Shortest_Length,index] = min(Length_best);
Shortest_Route = Route_best(index,:);
disp(['最短距離:' num2str(Shortest_Length)]);
disp(['最短路徑:' num2str([Shortest_Route Shortest_Route(1)])]);
%% 繪圖
figure(1)
plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...
? ? [citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-');
grid on
for i = 1:size(citys,1)
? ? text(citys(i,1),citys(i,2),['? ' num2str(i)]);
end
text(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),'? ? ? 起點(diǎn)');
text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),'? ? ? 終點(diǎn)');
xlabel('城市位置橫坐標(biāo)')
ylabel('城市位置縱坐標(biāo)')
title(['蟻群算法優(yōu)化路徑(最短距離:' num2str(Shortest_Length) ')'])
figure(2)
plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:')
legend('最短距離','平均距離')
xlabel('迭代次數(shù)')
ylabel('距離')
title('各代最短距離與平均距離對比')
5、參數(shù)調(diào)試記錄
? ??蟻群算法主要有5個參數(shù)
????alpha：信息素重要程度因子
????beta：啟發(fā)函數(shù)重要程度因子
????rho ：信息素?fù)]發(fā)因子
????m ：螞蟻數(shù)量
????iter_max：迭代次數(shù)
????這次主要研究alpha丐黄，beta斋配，rho對結(jié)果的影響，因此螞蟻數(shù)量m固定為75灌闺，迭代次數(shù)iter_max固定為200次艰争。
????用C語言寫的簡單生成隨機(jī)數(shù)程序，生成了40個點(diǎn)坐標(biāo)（X∈[0,6000],Y∈[0,5000]）桂对，代表40個城市甩卓。
控制啟發(fā)函數(shù)重要程度因子beta和信息素?fù)]發(fā)因子rho不變（beta=5,rho=0.5），改變信息素重要程度因子alpha蕉斜。
????alpha=1：
????最短距離：28558.1822
????alpha=2：
????最短距離:28898.1839
????alpha=3：
????最短距離:29094.3054
????alpha=4：
????最短距離:29094.3054
分析
????alpha在1的時候最短距離最小猛频，但是當(dāng)alpha小于1的時候沒有試。隨著alpha增加蛛勉，最短距離越來越小，平均距離收斂得越快睦柴，但最后都穩(wěn)定在3.4左右诽凌。
控制信息素重要程度因子alpha和信息素?fù)]發(fā)因子rho不變（alpha=3，rho=0.5）坦敌，改變啟發(fā)函數(shù)重要程度因子beta
????beta=1：
????最短距離:30344.8553
????beta=2：
????最短距離:29145.7761
????beta=4：
????最短距離:28978.882
????beta=6：
????最短距離：29094.3054
分析
????當(dāng)beta為4的時候侣诵，最短距離最小，當(dāng)beta為6時狱窘，平均距離最小杜顺，在3.4以下.
控制信息素重要程度因子alpha和啟發(fā)函數(shù)重要程度因子beta（alpha=1，beta=5）蘸炸，改變信息素?fù)]發(fā)因子rho
????rho=0.1：
????最短距離:28898.1839
????rho=0.3：
?????最短距離:29047.2567
?????rho=0.7：
????最短距離:28542.8334
分析
????當(dāng)rho為0.7左右時躬络，最短距離最短，并且rho越大時搭儒，平均距離收斂得越快穷当。
6提茁、結(jié)論
????1、alpha信息素重要程度因子馁菜，alpha越大茴扁，最短距離越大，但收斂速度越快
????2汪疮、beta啟發(fā)函數(shù)重要程度因子峭火，除了beta特別小以外，beta對最短距離影響不大智嚷，在一定區(qū)間里面浮動
????3卖丸、rho信息素?fù)]發(fā)因子，隨著rho增加纤勒，收斂速度變快坯苹，并且最短距離變短，但是如果當(dāng)?shù)螖?shù)夠多的話摇天，最短距離會穩(wěn)定下來粹湃。
????4、因?yàn)檫@次實(shí)驗(yàn)有40個城市泉坐，但是只迭代了200次为鳄，并且對alpha和beta取值范圍不是很懂，所以導(dǎo)致結(jié)果基本沒有出現(xiàn)最優(yōu)解腕让，只是都卡在了局部最優(yōu)孤钦，迭代次數(shù)我覺得應(yīng)該要500次左右，才能得出完整的結(jié)論纯丸。
????5偏形、TSP問題是一類經(jīng)典的組合優(yōu)化問題，即在給定城市個數(shù)和各城市之間距離的條件下觉鼻，找到一條遍歷所有城市且每個城市只能訪問一次的總路程最短的路線俊扭。蟻群算法在TSP問題應(yīng)用中取得了良好的效果，但是也存在一些不足：
????①比如alpha和beta設(shè)置不當(dāng)坠陈，導(dǎo)致求解質(zhì)量很差萨惑。
????②基本蟻群算法計(jì)算量大，求解所需時間較長仇矾。
