蚁群算法人工智能实验报告

人工智能实验报告姓名：学号：班级：实验时间：蚁群算法实验原理：蚂蚁在觅食过程中可以找出巢穴到食物源的最短路径，为什么？（1）信息素(pheromone)（2）正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。（3）挥发现象：路径上的信息素浓度会随着时间推进而逐渐衰减。蚁群算法的缺点：1）收敛速度慢2）易于陷入局部最优改进：1）采用局部优化，设计了三种优化算子。2）采用蚁群优化算法。3）其它优化算法实验内容：旅行商问题（TSP,travelingsalesmanproblem）：一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。实验步骤：算法代码：%%蚁群算法的优化计算——旅行商问题(TSP)优化%%清空环境变量clearallclc%%导入数据loadcitys_data.mat%%计算城市间相互距离n=size(citys,1);D=zeros(n,n);fori=1:nforj=1:nifi~=jD(i,j)=sqrt(sum((citys(i,:)-citys(j,:)).^2));elseD(i,j)=1e-4;endendend%%初始化参数m=50;%蚂蚁数量alpha=1;%信息素重要程度因子beta=5;%启发函数重要程度因子rho=0.1;%信息素挥发因子Q=1;%常系数Eta=1./D;%启发函数Tau=ones(n,n);%信息素矩阵Table=zeros(m,n);%路径记录表iter=1;%迭代次数初值iter_max=200;%最大迭代次数Route_best=zeros(iter_max,n);%各代最佳路径Length_best=zeros(iter_max,1);%各代最佳路径的长度Length_ave=zeros(iter_max,1);%各代路径的平均长度%%迭代寻找最佳路径whileiter=iter_max%随机产生各个蚂蚁的起点城市start=zeros(m,1);fori=1:mtemp=randperm(n);%返回n个[0,n]间的随机元素向量start(i)=temp(1);endTable(:,1)=start;%构建解空间citys_index=1:n;%访问1~n这n个城市%逐个蚂蚁路径选择fori=1:m%逐个城市路径选择forj=2:n%各个蚂蚁都需要访问n-1个城市tabu=Table(i,1:(j-1));%已访问的城市集合(禁忌表)allow_index=~ismember(citys_index,tabu);%判断citys_index中元素有没有在tabu中出现，出现用1表示，否则用0表示。allow=citys_index(allow_index);%待访问的城市集合P=allow;%计算城市间转移概率fork=1:length(allow)P(k)=Tau(tabu(end),allow(k))^alpha*Eta(tabu(end),allow(k))^beta;endP=P/sum(P);%轮盘赌法选择下一个访问城市Pc=cumsum(P);%返回矩阵不同维数的累加target_index=find(Pc=rand);%选择下一个访问城市，往往转移概率大的城市被选中的概率也更大。target=allow(target_index(1));Table(i,j)=target;%已选定的下一个待访问城市endend%计算各个蚂蚁的路径距离Length=zeros(m,1);fori=1:mRoute=Table(i,:);forj=1:(n-1)Length(i)=Length(i)+D(Route(j),Route(j+1));endLength(i)=Length(i)+D(Route(n),Route(1));%构成环end%计算最短路径距离及平均距离ifiter==1[min_Length,min_index]=min(Length);Length_best(iter)=min_Length;Length_ave(iter)=mean(Length);Route_best(iter,:)=Table(min_index,:);%Table,访问城市列表，也就是路径记录表else[min_Length,min_index]=min(Length);Length_best(iter)=min(Length_best(iter-1),min_Length);Length_ave(iter)=mean(Length);ifLength_best(iter)==min_LengthRoute_best(iter,:)=Table(min_index,:);elseRoute_best(iter,:)=Route_best((iter-1),:);endend%更新信息素Delta_Tau=zeros(n,n);%逐个蚂蚁计算fori=1:m%逐个城市计算forj=1:(n-1)Delta_Tau(Table(i,j),Table(i,j+1))=Delta_Tau(Table(i,j),Table(i,j+1))+Q/Length(i);endDelta_Tau(Table(i,n),Table(i,1))=Delta_Tau(Table(i,n),Table(i,1))+Q/Length(i);endTau=(1-rho)*Tau+Delta_Tau;%所有蚂蚁在各连接路径上的信息素浓度，不同迭代层间有关联%迭代次数加1，清空路径记录表iter=iter+1;Table=zeros(m,n);end%%结果显示[Shortest_Length,index]=min(Length_best);Shortest_Route=Route_best(index,:);disp(['最短距离:'num2str(Shortest_Length)]);disp(['最短路径:'num2str([Shortest_RouteShortest_Route(1)])]);%%绘图figure(1)plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...[citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-');gridonfori=1:size(citys,1)text(citys(i,1),citys(i,2),[''num2str(i)]);endtext(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),'起点');text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),'终点');xlabel('城市位置横坐标')ylabel('城市位置纵坐标')title(['蚁群算法优化路径(最短距离:'num2str(Shortest_Length)')'])figure(2)plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:')legend('最短距离','平均距离')xlabel('迭代次数')ylabel('距离')title('各代最短距离与平均距离对比')实验结果：