📄 新建 文本文档 (2).txt
字号:
function [bestSolution,bestRoute]=ACA8(filePath,numOfAnts,initao,alpha,beta,Q,rou,NCmax)
% Basic Ant Colony Algorithm for TSP Matlab Version
% Rewrite by Hzsong(hzsong123@126.com),2008.01.04
% 《蚁群算法原理及其应用》段海滨，P36,P426
% numOfAnts：蚂蚁个数
% initao：有向图上每条边的初始化信息量
% alpha：信息启发因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用，
% 其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间协作性越强。
% beta：期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中受重视程度，
% 其值越大，则该状态转移概率越接近于贪心规则。
% Q：表示信息素强度，它在一定程序上影响算法的收敛速度。
% rou：信息素挥发系数，1-rou：信息残留因子。rou取[0，1)。
% NCmax：最大迭代次数
% Demo1——
% filePath numOfAnts initao alpha beta Q rou NCmax
% [bestSolution,bestRoute]=ACA8( '', 20, 0.1, 1.0, 5.0,500,0.4,4000);
% ——[bestSolution,bestRoute]=ACA8('ulysses16-tsp.txt',10,0.1,1.0,5.0,150,0.2,80)
% Demo2:
% for i=1:10
% figure;
% ACA('ulysses16-tsp.txt',10,0.1,1.0,5.0,500,0.6,80);
% end
% % % % % % % % 初始化阶段 % % % % % % % %
% A0：城市坐标参数 numOfCitys：城市个数
close all;clc;tic;
if isempty(filePath)
filePath='E:\hzs\MatlabProgram\ACA\TSP\TSP\mat\att48.mat';
end
if exist(filePath,'file')
load(filePath);% bestSolution,bestRoute,cityPos,description
numOfCitys=size(cityPos,2);
else
[filePath,cityPos,numOfCitys]=openCityFile;
end
% 为了计算最优路线的信息量而添加的语句，可删。
bestRoute0=bestRoute;totalTaos0=zeros(1,NCmax);
totalTaos=zeros(1,NCmax);
x=cityPos(2,:); % 得到X-坐标
y=cityPos(3,:); % 得到Y-坐标
% 利用文件中的数据来确定蚂蚁个数和Q值
Q=0;numOfAdd=0;
numOfAnts=numOfCitys/2;
% 距离矩阵
for i=1:numOfCitys-1
for j=i+1:numOfCitys
distance(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2);
distance(j,i)=sqrt((x(j)-x(i))^2+(y(j)-y(i))^2);
Q=Q+distance(i,j);numOfAdd=numOfAdd+1;
end
end
Q=Q/numOfAdd;
% (1)将m只蚂蚁放在n个城市里.g(NC,k)的值表示第NC次迭代时，第k只蚂蚁所在城市的序号
for NC=1:NCmax
for k=1:numOfAnts
g(NC,k)=fix((numOfCitys-1)*rand(1))+1;
end
end
tao=zeros(numOfCitys,numOfCitys);%有向图上每条边的初始化信息量
yita=zeros(numOfCitys,numOfCitys);%启发函数，表示蚂蚁从城市i转移到城市j的期望程度
for i=1:numOfCitys
for j=1:numOfCitys
if j~=i %不在矩阵对角线时
tao(i,j)=initao;%(1)令有向图上每条边的初始化信息量tao(i,j)为常数
yita(i,j)=1/distance(i,j);
end
end
end
% initao=initao.*ones(numOfCitys,numOfCitys);%(1)令有向图上每条边的初始化信息量tao(i,j)为常数
bestSolution=1000000000;% 最优解
bestSolutions=zeros(1,NCmax);
selectNum=3;
% solutionsSelected=zeros(NCmax,3);%最优解，次优解，次次优解
% 如果有上一次的计算值,接着计算
if exist('d:\1\result.mat','file')
load('d:\1\result.mat');% to get tao & bestSolution
end
% % % % % % % % 蚂蚁建立路线阶段 % % % % % % % %
for NC=1:NCmax
detatao=zeros(numOfCitys,numOfCitys);%初始时刻信息量增量detatao(i,j)=0;
if mod(NC,10)==0
disp([num2str(NC),' of ',num2str(NCmax)]);
end
% 禁忌表tabu：0表示可以转移，1表示不可转移
tabu=zeros(numOfAnts,numOfCitys); % 在每一次循环时清空禁忌表
route=zeros(numOfAnts,numOfCitys);% route:numOfAnts*(numOfCitys-1)的矩阵：route(k,t)表示蚂蚁k第s次经过的城市标号
route(:,1)=(g(NC,:))';% 每只蚂蚁出发时所在的城市标号
solution=zeros(1,numOfAnts);
for k=1:numOfAnts % 第k只蚂蚁
tabu(k,g(NC,k))=1;
maxp=zeros(1,numOfCitys); % maxp:1*n的矩阵，用来记录每一次迭代第k只蚂蚁状态转移概率的最大值
% 公式2.4.3 计算第k只蚂蚁从选择的第s个城市route(k,t+1)到城市1-n的状态转移概率
currentCity=route(k,1);% 蚂蚁当前所在的城市标号
for t=1:numOfCitys-1 % 遍历时间
maxp(t)=0;
% 从城市route(k,t+1)到城市j(1,2,...numOfCitys)
for j=1:numOfCitys
if tabu(k,j)==0 % 蚂蚁k可以转移到城市j
pTJ(t,j)=(tao(currentCity,j)^alpha).*(yita(currentCity,j)^beta);
else
pTJ(t,j)=0;
end
end
% maxp(t)=max(pTJ(t,:));
% maxpFlag=find(pTJ(t,:)==maxp(t));
% nextCity=maxpFlag(1);% 找到蚂蚁k下一个要去的城市标号
% 查看pTJ的大小情况,可删除
pT=pTJ(t,:);
% if sum(pT)<0.0000001
% pT(1:4)*10000000
% end
pT=pT/sum(pT);
[result1,index1]=sort(pT,2,'descend');
selectRate=rand(1,2).*result1(1:2);
if selectRate(1)>selectRate(2)
nextCity=index1(1);
else
nextCity=index1(2);
end
solution_medium(k,t)=distance(currentCity,nextCity);
route(k,t+1)=nextCity;
tabu(k,nextCity)=1;
tao(currentCity,nextCity)=...
(1-rou)*tao(currentCity,nextCity)+rou*Q/distance(currentCity,nextCity);
tao(nextCity,currentCity)=...
(1-rou)*tao(nextCity,currentCity)+rou*Q/distance(nextCity,currentCity);
solution(k)=solution(k)+solution_medium(k,t);
% disp([num2str(currentCity),'-->',num2str(nextCity)]);
currentCity=nextCity;% 为下一次循环准备
end %'for t=2:numOfCitys-1'循环结束
% 当s=n的时候，终点--->起点
nextCity=route(k,1); % 返回起点
solution_medium(k,numOfCitys)=distance(currentCity,nextCity);
tao(currentCity,nextCity)=...
(1-rou)*tao(currentCity,nextCity)+rou*Q/distance(currentCity,nextCity);
tao(nextCity,currentCity)=...
(1-rou)*tao(nextCity,currentCity)+rou*Q/distance(nextCity,currentCity);
solution(k)=solution(k)+solution_medium(k,numOfCitys);
solution_NC(NC,k)=solution(k);
end %'for k=1:numOfAnts'循环结束
%=====================第2部分=================
% % % % % % % % 全局更新阶段 % % % % % % % %
% 公式2.4.6
[result,index]=sort(solution_NC(NC,:));
for i=1:selectNum
for t=1:numOfCitys-1
detatao(route(index(i),t),route(index(i),t+1))=...
detatao(route(index(i),t),route(index(i),t+1))+Q*numOfCitys/solution(index(i));
detatao(route(index(i),t+1),route(index(i),t))=...
detatao(route(index(i),t+1),route(index(i),t))+Q*numOfCitys/solution(index(i));
end
detatao(route(index(i),numOfCitys),route(index(i),1))=...
detatao(route(index(i),numOfCitys),route(index(i),1))+Q*numOfCitys/solution(index(i));
detatao(route(index(i),1),route(index(i),numOfCitys))=...
detatao(route(index(i),1),route(index(i),numOfCitys))+Q*numOfCitys/solution(index(i));
end % 'for i=1:bb'循环结束
% 公式2.4.5
tao=(1-rou)*tao+rou*detatao;
% for i=1:numOfCitys-1
% for j=i+1:numOfCitys
% tao(i,j)=(1-rou)*tao(i,j)+rou*detatao(i,j);
% tao(j,i)=(1-rou)*tao(j,i)+rou*detatao(j,i);
% end
% end
% 更新最优解和最优路径
if bestSolution>solution_NC(NC,index(1))
bestSolution=solution_NC(NC,index(1));
bestRoute=route(index(1),:);
end
bestSolutions(NC)=bestSolution;
% 计算最优路线的信息量而添加的语句，可删。
bestRoute1=bestRoute;
totalTao0=tao(bestRoute0(numOfCitys),bestRoute0(1));
totalTao1=tao(bestRoute1(numOfCitys),bestRoute1(1));
for i=1:numOfCitys-1
totalTao0=totalTao0+tao(bestRoute0(i),bestRoute0(i+1));
totalTao1=totalTao1+tao(bestRoute1(i),bestRoute1(i+1));
end
totalTaos0(NC)=totalTao0;
totalTaos1(NC)=totalTao1;
% 计算最优路线的信息量而添加的语句，可删。
% initao=tao;
end % 'for NC=1:NCmax'循环结束
save('d:\1\result.mat','tao','bestSolution','bestRoute');
% % % % % % % % 输出TSP问题的迭代结果 % % % % % % % %
% bestRoute=bestRoute_NC(bestSolutionFlag,:);
figure(1);
strTitle=['第',num2str(NCmax),'次迭代的最优解为:',num2str(bestSolution)];
strColor='rgb';
dispASAResult(bestRoute,x,y,strTitle,strColor,tao);
saveas(gcf,'d:\1\1','emf');
% % % % % % % % 输出TSP问题的最优结果 % % % % % % % %
if exist(filePath,'file')
load(filePath);% bestSolution,bestRoute,cityPos,description
if ~isempty(bestRoute)
figure(2);
strTitle=['系统的最优解为:',num2str(bestSolution)];
strColor='ymc';
dispASAResult(bestRoute,x,y,strTitle,strColor,tao);
saveas(gcf,'d:\1\2','emf');
end
end
% 计算最优路线的信息量而添加的语句，可删。
figure(3);
plot(totalTaos0,'r');
hold on;
plot(totalTaos1,'g');
legend('最优值路线上的信息总量','每一步迭代时的信息总量');
xlabel('迭代次数');ylabel('信息总量');
title('信息总量');
hold off;
saveas(gcf,'d:\1\3','emf');
figure(4);
plot(bestSolutions);title('每一次迭代最优解的变化');
saveas(gcf,'d:\1\4','emf');
toc % end of programe
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
% % % % % % % % % % % % % %自己写的函数 % % % % % % % % % % % % % % % %
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
% RGB Value Short Name Long Name
% [1 1 0] y yellow
% [1 0 1] m magenta
% [0 1 1] c cyan
% [1 0 0] r red
% [0 1 0] g green
% [0 0 1] b blue
% [1 1 1] w white
% [0 0 0] k black
function dispASAResult(bestRoute,x,y,strTitle,strColor,tao) % 根据最优路线，和城市坐标画出ACA计算结果
% bestRoute:最优路线
% cityPos:城市坐标
% strTitle:Figure名字
set(gcf,'units','normalize','position',[0.1 0.1 0.8 0.75]);
set(gca,'position',[0.05 0.05 0.9 0.9]);
hold on;
numOfCitys=length(x);
try
lineColors=strColor;
catch
lineColors='rgb';
end
for j=1:numOfCitys-1
% 画线
lineColor=lineColors(mod(j-1,3)+1);
line([x(bestRoute(j)),x(bestRoute(j+1))],[y(bestRoute(j)),y(bestRoute(j+1))],'color',lineColor);
% 画城市
plot(x(bestRoute(j)),y(bestRoute(j)),'marker','o','markersize',12);
text(x(bestRoute(j)),y(bestRoute(j)),num2str(bestRoute(j)));
% 画信息量
strTemp=num2str(tao(bestRoute(j),bestRoute(j+1)));
indexOfDot=find(strTemp=='.');
text((x(bestRoute(j))+x(bestRoute(j+1)))/2,...
(y(bestRoute(j))+y(bestRoute(j+1)))/2,...
strTemp(1:indexOfDot+1) );
end
% 画线
lineColor=lineColors(mod(numOfCitys-1,3)+1);
line([x(bestRoute(numOfCitys)),x(bestRoute(1))],[y(bestRoute(numOfCitys)),y(bestRoute(1))],'color',lineColor);
% 画城市
plot(x(bestRoute(numOfCitys)),y(bestRoute(numOfCitys)),'marker','o','markersize',12);
text(x(bestRoute(numOfCitys)),y(bestRoute(numOfCitys)),num2str(bestRoute(numOfCitys)));
% 画信息量
strTemp=num2str(tao(bestRoute(numOfCitys),bestRoute(1)));
indexOfDot=find(strTemp=='.');
text((x(bestRoute(numOfCitys))+x(bestRoute(1)))/2,...
(y(bestRoute(numOfCitys))+y(bestRoute(1)))/2,...
strTemp(1:indexOfDot+1) );
% 画起点
plot(x(bestRoute(1)),y(bestRoute(1)),'color','r','marker','s','markersize',10);
% 画终点
plot(x(bestRoute(numOfCitys)),y(bestRoute(numOfCitys)),'color','r','marker','d','markersize',10);
grid on;
xlabel('X-坐标');
ylabel('Y-坐标');
title(strTitle);
hold off;
% 函数：打开和导入TSP问题城市坐标文件
function [filePath,cityPos,numOfCitys]=openCityFile
[fname,pname,filterindex]=uigetfile('*.*','所有文件(*.*)');
filePath=[pname,fname];
fid=fopen(filePath,'r');
if fid==-1
warndlg('不能打开文件','警告');
fclose(fid);
return;
end
[A0,COUNT]=fscanf(fid,' %g');
numOfCitys=COUNT/3;
fclose(fid);
cityPos=reshape(A0,3,numOfCitys);% 得到TSP问题中的城市坐标
indexOfDot=find(filePath=='.');
if isempty(indexOfDot)
filePath=[filePath,'-my'];
else
filePath=[filePath(1:indexOfDot-1),'-my',filePath(indexOfDot:end)];
end
% if exist(filePath)
fidmy=fopen(filePath,'wt');
fprintf(fidmy,'%5i%8.2f%8.2f\numOfCitys',cityPos);
fclose(fidmy);
% disp('文件写入完毕');
att48.mat里面的内容：
bestRoute,1*48的矩阵，最优路径
bestSolution,最优路径值
cityPos,3*48的矩阵，城市编号、X坐标、Y坐标
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -