MATLAB实验报告

1一、问题分析（10分）设计智能算法算法求解以下30个城市的最短旅行路径，城市坐标参数见下表。城市编号12345678910111213141516横坐标7628673149651315796423354436226纵坐标49557558614241976733746068767626城市编号1718192021222324252627282930横坐标982010191512525150453265355纵坐标762555697522638895114838这实际上是一个TSP问题，宜用蚁群算法求解：设有30个城市C=（1，2,...,30），任意两个城市i，j之间的距离为dij，求一条经过每个城市的路径γ=（γ（1），γ（2），...，γ（30）），使得距离最小。二、实验原理与数学模型（20分）1、算法来源蚁群算法的基本原理来源于自然界蚂蚁觅食的最短路径原理，根据昆虫学家的观察，发现自然界的蚂蚁虽然视觉不发达，但它可以在没有任何提示的情况下找到从食物源到巢穴的最短路径，并且能在环境发生变化（如原有路径上有了障碍物）后，自适应地搜索新的最佳路径。2、实验原理主要符号说明C30个城市的坐标，30×2的矩阵NC_max最大迭代次数m蚂蚁个数Alpha表征信息素重要程度的参数Beta表征启发式因子重要程度的参数Rho信息素蒸发系数Q信息素增加强度系数R_best各代最佳路线L_best各代最佳路线的长度2求解TSP问题的蚂蚁算法中，每只蚂蚁是一个独立的用于构造路线的过程，若干蚂蚁过程之间通过自适应的信息素值来交换信息，合作求解，并不断优化。这里的信息素值分布式存储在图中，与各弧相关联。蚂蚁算法求解TSP问题的过程如下：（1）首先初始化，设迭代的次数为NC。初始化NC=0（2）将m个蚂蚁置于n个顶点上（3）m只蚂蚁按概率函数选择下一座城市，完成各自的周游每个蚂蚁按照状态变化规则逐步地构造一个解，即生成一条回路。蚂蚁的任务是访问所有的城市后返回到起点，生成一条回路。设蚂蚁k当前所在的顶点为i，那么，蚂蚁k由点i向点j移动要遵循规则而不断迁移，按不同概率来选择下一点。（4）记录本次迭代最佳路线（5）全局更新信息素值应用全局信息素更新规则来改变信息素值。当所有m个蚂蚁生成了m个解，其中有一条最短路径是本代最优解，将属于这条路线上的所有弧相关联的信息素值进行更新。全局信息素更新的目的是在最短路线上注入额外的信息素，即只有属于最短路线的弧上的信息素才能得到加强，这是一个正反馈的过程，也是一个强化学习的过程。在图中各弧上，伴随着信息素的挥发，全局最短路线上各弧的信息素值得到增加。（6）终止若终止条件满足，则结束；否则NC=NC+1，转入步骤（2）进行下一代进化。终止条件可指定进化的代数，也可限定运行时间，或设定最短路长的下限。（7）输出结果33、数学模型设m表示蚂蚁总数量，用)1,,1,0,(dnjiij表示节点i和节点j之间的距离，)(ijt表示在t时刻ij连线上的信息素浓度。在初始时刻，m只蚂蚁会被随机地放置，各路径上的初始信息素浓度是相同的。在t时刻，蚂蚁k从节点i转移到节点j的状态转移概率为otherpallowedttttkijkallowedkijijijijkij,0j,)()()()(pk1-2其中，kktabucallowed表示蚂蚁k下一步可以选择的所有节点，C为全部节点集合；为信息启发式因子，在算法中代表轨迹相对重要程度，反映路径上的信息量对蚂蚁选择路径所起的影响程度，该值越大，蚂蚁间的协作性就越强；可称为期望启发式因子，在算法中代表能见度的相对重要性。ij是启发函数，在算法中表示由节点i转移到节点j的期望程度，通常可取ijijd/1。在算法运行时每只蚂蚁将根据(2-1)式进行搜索前进。在蚂蚁运动过程中，为了避免在路上残留过多的信息素而使启发信息被淹没，在每只蚂蚁遍历完成后，要对残留信息进行更新处理。由此，在t+n时刻,路径(i,j)上信息调整如下)()(1ttntijijij(2-2))()(1ttmkkijij(2-3)在式中，常数1,0表示信息素挥发因子,表示路径上信息量的损耗程度,的大小关系到算法的全局搜索能力和收敛速度，则可用-1代表信息素残留因子,)(tkij表示一次寻找结束后路径(i,j)的信息素增量。在初始时刻00ij,)(tkij表示第k只蚂蚁在本次遍历结束后路径(i,j)的信息素。4由于信息素更新策略有所不同，学者DorigoM研究发现了三种不同的基本蚁群算法模型，分别记为“蚁周系统”(Ant-Cycle)模型、“蚁量系统”(Ant-Quantity)模型及“蚁密系统”(Ant-Density)模型，三种模型求解)(tkij方式存在不同。“蚁周系统”(Ant-Cycle)模型otherLQkkij,0,第k只蚂蚁走过ij(2-4)“蚁量系统”(Ant-Quantity)模型otherdQijkij,0,第k只蚂蚁在t和t+1之间走过ij(2-5)“蚁密系统”(Ant-Density)模型otherQkij,0,第k只蚂蚁在t和t+1之间走过ij(2-6)三、实验过程记录（含基本步骤、程序代码及异常情况记录等）（60分）1、数据准备为防止既有变量的干扰，首先将环境变量清空。然后从Excle文件中读取城市的位置坐标，并保存在变量为City的矩阵中（第一列为城市的横坐标，第二列为城市的纵坐标）。2、计算城市距离矩阵53、MATLAB程序源代码：%%数据准备%清空环境变量clearallclc%程序运行计时开始t0=clock;%导入数据citys=xlsread('citys_data.xlsx','B2:C31');%--------------------------------------------------------------------------%%计算城市间相互距离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=75;%蚂蚁数量alpha=1;%信息素重要程度因子beta=5;%启发函数重要程度因子vol=0.2;%信息素挥发(volatilization)因子Q=10;%常系数Heu_F=1./D;%启发函数(heuristicfunction)Tau=ones(n,n);%信息素矩阵Table=zeros(m,n);%路径记录表iter=1;%迭代次数初值iter_max=100;%最大迭代次数Route_best=zeros(iter_max,n);%各代最佳路径Length_best=zeros(iter_max,1);%各代最佳路径的长度Length_ave=zeros(iter_max,1);%各代路径的平均长度6Limit_iter=0;%程序收敛时迭代次数%-------------------------------------------------------------------------%%迭代寻找最佳路径whileiter=iter_max%随机产生各个蚂蚁的起点城市start=zeros(m,1);fori=1:mtemp=randperm(n);start(i)=temp(1);endTable(:,1)=start;%构建解空间citys_index=1:n;%逐个蚂蚁路径选择fori=1:m%逐个城市路径选择forj=2:ntabu=Table(i,1:(j-1));%已访问的城市集合(禁忌表)allow_index=~ismember(citys_index,tabu);%参加说明1（程序底部）allow=citys_index(allow_index);%待访问的城市集合P=allow;%计算城市间转移概率fork=1:length(allow)P(k)=Tau(tabu(end),allow(k))^alpha*Heu_F(tabu(end),allow(k))^beta;endP=P/sum(P);%轮盘赌法选择下一个访问城市Pc=cumsum(P);%参加说明2(程序底部)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%计算最短路径距离及平均距离7ifiter==1[min_Length,min_index]=min(Length);Length_best(iter)=min_Length;Length_ave(iter)=mean(Length);Route_best(iter,:)=Table(min_index,:);Limit_iter=1;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,:);Limit_iter=iter;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-vol)*Tau+Delta_Tau;%迭代次数加1，清空路径记录表iter=iter+1;Table=zeros(m,n);end%--------------------------------------------------------------------------%%结果显示[Shortest_Length,index]=min(Length_best);Shortest_Route=Route_best(index,:);Time_Cost=etime(clock,t0);disp(['最短距离:'num2str(Shortest_Length)]);disp(['最短路径:'num2str([Shortest_RouteShortest_Route(1)])]);disp(['收敛迭代次数:'num2str(Limit_iter)]);disp(['程序执行时间:'num2str(Time_Cost)'秒']);8%---------------------------------------