基于蚁群算法求解浙江省5A级旅游景区的遍历问题

基于蚁群算法求解浙江省5A级旅游景区的遍历问题摘要：蚁群算法是一种常用的用来在图中寻找优化路径的智能算法，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。本文主要研究了蚁群算法的发展现状，然后应用该理论解决如何从华东理工大学奉贤校区出发，不重复地遍历浙江省所有5A级旅游景区的实际问题，并对算法中的主要参数进行了灵敏度分析。同时绘制出了交互式图形用户界面，直观展现最佳环游路径示意图。关键词：蚁群算法；旅行商问题；灵敏度分析；图形用户界面1引言根据蚂蚁“寻找食物”的群体行为，意大利著名学者等于1991年在法国巴黎召开的第一届欧洲人工生命会议上最早提出了蚁群算法的基本模型。1992年，DorigoM又在其博士学位论文中进一步阐明了蚁群算法的核心思想。蚁群算法是一种基于种群的启发式仿生进化系统。该算法通过模拟自然界的蚂蚁觅食过程对目标进行搜索，而在搜索过程中人工蚂蚁会在其经过的路径上释放信息素，蚁群依赖于同类散发在周围环境中的特殊物质—信息素的轨迹来决定自己的去向。当某些路径上走过的蚂蚁越来越多时，留下的信息素也会越来越多，以致后蚂蚁选择该路径的概率也越来越高，从而更增加了该路径的吸引强度，逐渐形成了一条它们自己事先并未意识到的最短路线。蚁群算法创立十多年来，无论在算法理论还是在算法应用方面都取得了很多突破性研究进展。它已经从单纯地解决对称拓展到解决非对称、指派问题以及车间作业调度问题等。尤其是近几年来，这种新兴的仿生优化算法已经显示出强大的生命力和广阔的发展前景。2文献综述群居性昆虫行为的研究为计算机科学家提供了设计分布式控制和优化算法的有力方法。对以蚁群算法为代表的群集智能的研究已经成为一个研究热点。不少学者对经典蚁群算法中的一些缺点进行了改进，得到了更出色的算法，使得该算法不断地到完善。[1]吴斌等人首先在蚁群算法的基础上提出了相遇算法，提高了蚁群算法蚂蚁一次周游的质量，然后将相遇算法与采用并行策略的分段算法相结合，提出一种基于蚁群算法的TSP问题分段求解算法。[2]詹士昌对基本蚁群算法参数的合理选取进行了实验分析，给出了算法参数选取的基本原则，有利于蚁群算法在优化问题中的推广和应用。[3]王颖提出一种自适应的蚁群算法以克服易于限于局部最小点等缺陷。通过自适应地改变算法的挥发度等系数，可以在保证收敛速度的条件下提高解的全局性，通过对TSP问题的仿真证明算法相对与原始的蚁群算法收敛速度和解的性能都有一定的提高。[5]毕军等人应用蚁群算法求解最短路径问题，对算法的选择策略，局部搜索，信息量修改三方面进行改进，使算法不易陷入局部最优解，并且能较快地收敛到全局最优解。同时各行各业的学者将蚁群算法应用到了不同的领域中来解决实际中的问题，取得了良好的效果。[4]汪镭将蚁群算法引入连续空间的函数寻优问题求解，通过将传统蚁群算法中的"信息量留存"过程拓展为连续空间中的"信息量分布函数"，定义了相应的求解算法。对多极值函数和非线性连续函数的寻优实例仿真取得了良好的结果，显示了蚁群算法在连续空间优化问题中的应用前景。[6]张勇德将离散空间问题求解的蚁群算法引入连续空间，针对多目标优化问题的特点，提出一种用于求解带有约束条件的多目标函数优化问题的蚁群算法。该方法定义了连续空间中信息量的留存方式和蚂蚁的行走策略，并将信息素交流和基于全局最优经验指导两种寻优方式相结合，用以加速算法收敛和维持群体的多样性。通过3组基准函数来测试算法性能，并与NSGAII算法进行了仿真比较。实验表明该方法搜索效率高，向真实Pareto前沿逼近的效果好，获得的解的散布范围广，是一种求解多目标优化问题的有效方法。反向传播算法是神经网络中应用广泛的一种多层前馈神经网络模型。但算法有求解精度低、搜索速度慢、易于陷入极小的缺点。蚁群算法是一种新型的模拟进化算法，有正反馈、分布式计算、启发性收敛等特性。这些特性使得解题过程加快，易于实现分布式计算。[7]洪炳熔将蚁群算法和神经网络相结合起来，实现了非线性模型的辨识问题及倒立摆的控制。仿真实验表明：用蚁群算法训练神经网络，可兼有神经网络广泛映射能力和蚁群算法快速全局收敛的性能。近几年优化领域中新出现的蚁群算法采用分布式并行计算机制，易于与其它方法结合，具有较强的鲁棒性，但易限于局部最优解是其最突出的缺点。云模型是一种新的实现定性概念和定量数值之间转换的有力工具，在介绍云模型理论的基础上，[9]段海滨提出了一种利用云模型来有效限制蚁群算法陷入局部最优解的方法，最后将基于云模型理论的改进蚁群算法与未改进的蚁群算法分别应用于著名的CHC144TSP进行实验。改进后的蚁群算法采用升半正态云规则进行控制，并选取了500个云滴，仿真计算结果证明了该方法的有效性和可行性。蚂蚁等群居类昆虫被看作能解决复杂问题的分布式系统，研究者从它们的协作性能以及自组织、信息素通信、任务划分等机理中获得灵感，已在组合优化、通信网络、机器人等许多应用领域找到解决问题的新方法。聚类作为一种无监督的学习，能根据数据间的相似程度自动地进行分类。基于蚁群算法的聚类方法已经在当前数据挖掘研究中得到应用。[10]杨燕提出的基于蚁群算法的聚类组合新方法，模仿多蚁群的协作性能，将运动速度类型各异的多个蚁群，独立而并行地进行聚类分析，然后组合其聚类结果为超图，再用蚁群算法对超图进行2次划分。实验结果表明，该方法能自动决定聚类的数目，聚类组合方法能明显改善聚类质量。3蚁群算法基本原理本文以常见的旅行商问题为例，来解释蚁群算法的原理及基本步骤。3.1旅行商问题旅行商问题（TravelingSalesmanProblem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。旅行商问题是一种比较经典的NP难题，问题描述较简单，而获得最优解却十分困难。求解TSP问题不仅为其他算法提供了使用平台，而且算法的优劣性能也可通过其求得TSP问题的解集来验证。蚁群算法实现TSP过程为：将m只蚂蚁放入到n个随机选择的城市中，那么每个蚂蚁每步的行动是：根据一定的依据选择下一个它还没有访问的城市；同时在完成一步（从一个城市到达另一个城市）或者一个循环（完成对所有n个城市的访问）后，更新所有路径上的信息素浓度。3.2算法基本概念下面以求解平面上个城市的为例来简要地介绍一下用于的基本蚁群算法。蚁群算法模型个城市的即为寻找通过个城市各一次且最后回到出发点的最短路径。假设有个城市，只蚂蚁，令表示城市之间距离，表示在时刻城市之间路径上残留信息素强度。蚂蚁在行进的过程中，根据各条路径上残留信息素强度来决定下一步行进的路径，用表示在时刻蚂蚁由城市转移到城市的概率，则有：表示蚂蚁下一步允许的城市集，列表为蚂蚁的禁忌表。当所有个城市都被列入到中时，蚂蚁游历了所有城市，现回到出发点便完成了一次遍历，则蚂蚁所经过的路径就是该的一个可行解。是启发式因子，表示蚂蚁从城市行进到城市的期望程度，通常取的倒数；分别表示信息素和启发式因子在方程中相对重要程序；当所有蚂蚁完成一次遍历之后，各路径上的信息素再进行全局更新：其中，表示挥发系数，表示持久性系数，表示本次迭代后信息素的增量，表示第只蚂蚁在本次迭代中残留在边上的信息素量。根据信息素不同的更新策略，提出了三种不同的蚁群算法模型，即模型、模型及模型。它们的主要区别在于模型及模型中利用的是局部信息，即蚂蚁完成一步后更新路径上的信息素；而在模型中利用的是整体信息，即蚂蚁完成一次遍历后更新整条路径上的所有信息素。由于模型中信息增量考虑了全局变化，所以在求解时具有较好性能，通常作为蚁群算法的基本模型。3.3算法求解流程参数初始化。令时间，设置为常数，。循环次数。蚂蚁的禁忌表索引号。蚂蚁的数目。蚂蚁个体根据状态转移概率式1所计算的概率选择元素并前进，。修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素，并把该元素移动到蚂蚁个体的禁忌表中。若集合C中元素未遍历完，k<m,则跳转到第4步，否则执行第8步。根据式2和式3更新每条路径上信息量。若满足结束条件，则循环结束并输出程序计算结果，否则清空禁忌表并跳转到第2步。蚁群算法解决遍历问题的逻辑代码（完整程序代码见附录）：FunctionACATSP

foreachedge

setinitialpheromonevaluet0

end%%初始化参数whilenotstop

foreachantk

randomlychooseaninitialcity

fori=1ton

choosenextcityjwithprobability

end

end%%构建解空间

computethelengthCkofthetourconstructedbythekthant

foreachedge

updatethepheromonevalue

end%%更新信息素

end

printresult

end%%输出解脱绘图4算法应用4.1问题描述蚁群问题中最常见的应用就是旅行时候的线路规划问题，解决如何在避免走回头路，使得总路程最短。许多旅行社在设计，管理旅行路线的时候，必须考虑线路的合理性和经济性，以实现利润最大化和顾客满意度最高。本问题的起点和终点都在华东理工大学奉贤校区，地图上共有杭州西湖等11处浙江省5A级旅游景区，按照实际地图等比例缩放后分布。需要寻找一条总路程最短的路线，使得路线不重复地通过所有景区并最后回到起点。4.2数据来源本文为了尽可能地贴近现实，从谷歌地图上获取了精确的景区经纬度之后，为了绘图清晰方便，本文选择东经120°，北纬30°为坐标原点，同时横纵坐标等比例放大2000为调整后的经纬度。具体数据如下：表1.各景区调整前后的经纬度数据浙江5A景区东经北纬调整后经度调整后维度1-杭州西湖风景区120.139130.2518278.12503.542-杭州西溪湿地旅游区120.074030.2746148.01549.243-杭州淳安千岛湖风景区119.021529.6019-1957.09-796.254-绍兴市鲁迅故里－沈园景区120.592629.99851185.27-2.925-嘉兴南湖旅游区120.771030.74791541.981495.726-嘉兴桐乡乌镇古镇旅游区120.494430.7545988.811509.087-宁波奉化溪口－滕头旅游景区121.224929.68652449.83-627.098-舟山普陀山风景区122.386129.98094772.22-38.169-温州乐清市雁荡山风景区121.074028.37872148.10-3242.6210-金华东阳横店影视城景区120.369829.1636739.62-1672.8911-衢州开化根宫佛国文化旅游区118.400329.1392-3199.34-1721.6912-华理奉贤校区121.510630.83603021.151672.09不同于以往文献中简单地将两点之间的直线距离作为两者距离，本文为了使得数据具有现实意义，任意两点之间的距离通过百度地图的推荐路径规划中的公里数作为最终两景区之间的距离数据。具体数据如下：表2.各景区之间的距离矩阵景区123456789101112108.9162.767.292.483.9180.8256.9304.4147.2274.5161.128.90148.973.797.887.6188.6264.6312.2154.8271.8168.23162.7148.90206.2256.2246.7339.6415.7369.4221.8120.6330.1467.273.7206.20110.3111.1139.5218.2250.1118.3312.3157.7592.497.8256.2110.3035.1180.5248.5314.1218.5363.385.7683.987.6246.7111.135.10208.3276.2341.9202.9355.5120.97180.8188.6339.6139.5180.5208.30163.3203.8141.5335.2204.78256.9264.6415.7218.2248.5276.2163.30318.4141.1481.4272.69304.4312.2369.4250.1314.1341.9203.8318.40186.4391.4364.810147.2154.8221.8118.3218.5202.9141.5141.1186.40243.726911274.5271.8120.6312.3363.3355.5335.2481.4391.4243.70438.212161.1168.2330.1157.785.7120.9204.7272.6364.8269438.204.3实验结果根据历史经验，蚂蚁个数的取值不应大于景点总个数，表示信息素重要程度的参数α取1，表示启发式因子重要程度的参数β取5，表示信息素挥发速度的参数Rho取0.1，表示信息素增强程度的参数Q取100为较优的参数取值水平。在该水平下，如果取最大迭代次数NC_max=500，则最佳路径规划如图1所示，每次平均总路程和最短路程收敛图如图2所示：图1.蚁群算法运算结果图图2.蚁群算法平均和最短路线变化图通过枚举方法验证，此结果为本算法的最优解。从上图中可以看到，程序在迭代了两百多次之后就最终收敛到了最优值，可以说在数据量并不大的情况下，蚁群算法的收敛速度相当之快，在较短的时间能获得较优解甚至最优解。4.4灵敏度分析 本文主要对蚁群算法ACATSP中的主要参数进行灵敏度分析，相关灵敏度分析结果如下所示：1）蚂蚁数量m m的取值范围为[1,20]，其余参数（NC_max,Alpha,Beta,Rho,Q）固定为（500,1,5,0.1,100）。最优参数取最大景点数12比较合理。2）信息素重要程度αα的取值范围为[0.25,6]，其余参数（NC_max,m,Beta,Rho,Q）固定为（500,12,5,0.1,100）。最优参数取1比较合理。3）启发式因子重要程度ββ的取值范围为[1,10]，其余参数（NC_max,m,Alpha,Rho,Q）固定为（500,12,1,0.1,100）。最优参数取5比较合理。4）信息素挥发速度RhoRho的取值范围为[0.05,0.5]，其余参数（NC_max,m,Alpha,Beta,Q）固定为（500,12,1,5,100）。最优参数取0.1比较合理。图3(a).参数m的灵敏度分析图3(b).参数的灵敏度分析图3(c).参数的灵敏度分析图3(d).参数的灵敏度分析4.5GUI图形用户界面图4.集成各项功能的图形用户界面使用者可以在左上角选择全部或者部分自己感兴趣的旅游景点，左下角可以更改最大迭代次数，蚂蚁个数，和信息素增强系数。并且如果蚂蚁个数输入的数值大于景点总个数，系统自动调整为景点总个数，以便实现程序的最优效果。右半部分界面为算法计算所得的路线图和运算结果收敛图。如果更改了所选城市或者相关参数，在进行下一次计算之前需要先清空右侧图片。5总结本次实验是通过matlab编程来实现蚁群优化算法，通过实验结果，我们发现虽然我们找到了问题的最优解，但是最优解的收敛性并不乐观，并不能求得问题的精确解，并且随着参数的调节运行结果有随机性。另外，在蚁群算法求解过程中，蚂蚁的数量和景点的数量差距对结果也是具有一定影响的。蚁群算法是近年来产生的一种源于大自然生物世界的新的启发式优化方法。通过以上对蚁群算法的基本原理及其实际应用的介绍可以发现该算法有如下主要特点：正反馈机制：经过蚂蚁越多的路径，后续蚂蚁选择该路径的可能性就越大，通过信息素的不断更新最终收敛于最优路径上。较强的通用性：算法模型只需做很少修改就可运用于别的组合优化问题。分布式并行计算能力：算法在全局的多点同时进行解的搜索，具有本质上的并行性，易于并行实现。当然蚁群算法也有不足之处，几乎每个实用的启发式搜索算法都是由某个参数集控制的，蚁群优化算法也不例外，事先无法找到参数的一个最优选择，使得它对于任何问题都能达到最优性能，一般只能分析了具体问题后，在实验过程中凭借经验不断调整参数，以期得到最优解。6参考文献[1]吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报,2001,12期(12):1328-1333.DOI:doi:10.3321/j.issn:0254-4164.2001.12.014.[2]詹士昌,徐婕,吴俊.蚁群算法中有关算法参数的最优选择[J].科技通报,2003,05期:381-386.DOI:doi:10.3969/j.issn.1001-7119.2003.05.008.[3]王颖,谢剑英.一种自适应蚁群算法及其仿真研究[J].系统仿真学报,2002,第1期:31-33.DOI:doi:10.3969/j.issn.1004-731X.2002.01.010.[4]汪镭,吴启迪.蚁群算法在连续空间寻优问题求解中的应用[J].控制与决策,2003,18(1):45-48.DOI:doi:10.3321/j.issn:1001-0920.2003.01.009.[5]毕军,付梦印,张宇河.一种改进的蚁群算法求解最短路径问题[J].计算机工程与应用,2003,03期(3):107-109.DOI:doi:10.3321/j.issn:1002-8331.2003.03.036.[6]张勇德,黄莎白.多目标优化问题的蚁群算法研究[J].控制與決策,2005,20(2):170-173.DOI:doi:10.3321/j.issn:1001-0920.2005.02.011.[7]洪炳熔,金飞虎,高庆吉.基于蚁群算法的多层前馈神经网络[J].哈尔滨工业大学学报,2003,07期:823-825.DOI:doi:10.3321/j.issn:0367-6234.2003.07.017.[8]周勇,陈洪亮.蚁群算法的研究现状及其展望[J].微型电脑应用,2002,02期:5-7.DOI:doi:10.3969/j.issn.1007-757X.2002.02.001.[9]段海滨,王道波,于秀芬,等.基于云模型理论的蚁群算法改进研究[J].哈尔滨工业大学学,2005,01期:115-119.DOI:doi:10.3321/j.issn:0367-6234.2005.01.030.[10]杨燕,靳蕃,Mohamed,等.一种基于蚁群算法的聚类组合方法[J].铁道学报,2004,第4期:64-69.DOI:doi:10.3321/j.issn:1001-8360.2004.04.014.7Matlab完整代码7.1蚁群算法求解函数function[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP_ZJ(C,D,NC_max,m,Alpha,Beta,Rho,Q)%%=========================================================================%%?ACATSP.m%%?AntColonyAlgorithmforTravelingSalesmanProblem%%-------------------------------------------------------------------------%%?主要符号说明%%?Cn个城市的坐标，n×2的矩阵%%?Dn个城市距离邻接矩阵%%?NC_max最大迭代次数%%?m蚂蚁个数，<=n%%?Alpha表征信息素重要程度的参数，=1%%?Beta表征启发式因子重要程度的参数，=5%%?Rho信息素蒸发系数，=0.1%%?Q信息素增加强度系数%%?R_best各代最佳路线%%?L_best各代最佳路线的长度%%=========================================================================%%第一步：变量初始化n=size(C,1);%n表示问题的规模（城市个数）Eta=1./D;%Eta为启发因子，这里设为距离的倒数Tau=ones(n,n);%Tau为信息素矩阵Tabu=zeros(m,n);%存储并记录路径的生成NC=1;%迭代计数器R_best=zeros(NC_max,n);%各代最佳路线L_best=inf.*ones(NC_max,1);%各代最佳路线的长度L_ave=zeros(NC_max,1);%各代路线的平均长度whileNC<=NC_max%停止条件之一：达到最大迭代次数%%第二步：将m只蚂蚁放到n个城市上Randpos=[];fori=1:(ceil(m/n))Randpos=[Randpos,randperm(n)];endTabu(:,1)=(Randpos(1,1:m))';%%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游forj=2:nfori=1:mvisited=Tabu(i,1:(j-1));%已访问的城市J=zeros(1,(n-j+1));%待访问的城市P=J;%待访问城市的选择概率分布Jc=1;%统计待访问城市坐标fork=1:niflength(find(visited==k))==0J(Jc)=k;Jc=Jc+1;endend%下面计算待选城市的概率分布fork=1:length(J)P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);endP=P/(sum(P));%按概率原则选取下一个城市Pcum=cumsum(P);Select=find(Pcum>=rand);to_visit=J(Select(1));Tabu(i,j)=to_visit;endendifNC>=2Tabu(1,:)=R_best(NC-1,:);end%%第四步：记录本次迭代最佳路线L=zeros(m,1);fori=1:mR=Tabu(i,:);forj=1:(n-1)L(i)=L(i)+D(R(j),R(j+1));endL(i)=L(i)+D(R(1),R(n));endL_best(NC)=min(L);pos=find(L==L_best(NC));R_best(NC,:)=Tabu(pos(1),:);L_ave(NC)=mean(L);NC=NC+1;%%第五步：更新信息素Delta_Tau=zeros(n,n);fori=1:mforj=1:(n-1)Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);endDelta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);endTau=(1-Rho).*Tau+Delta_Tau;%%第六步：禁忌表清零Tabu=zeros(m,n);end%%第七步：输出结果Pos=find(L_best==min(L_best));Shortest_Route=R_best(Pos(1),:);Shortest_Length=L_best(Pos(1));end5.2画路线图的子函数functionDrawRoute(C,R,b)%%====================================================================%%?DrawRoute.m%%?画路线图的子函数%%--------------------------------------------------------------------%%?C???Coordinate???????节点坐标，由一个N×2的矩阵存储%%?R???Route????????????路线%%====================================================================N=length(R);[a,c]=size(C);holdonforj=1:ascatter(C(j,1),C(j,2),'fill');ifb(j)~=12;text(C(j,1)+80,C(j,2)+80,num2str(b(j)),'FontSize',12,'FontWeight','bold');elsetext(C(j,1)+80,C(j,2)+80,'华东理工大学','FontSize',12,'FontWeight','bold');endendplot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)]);holdonforii=2:Nplot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)]);holdonendH=get(gca);new_XLim=H.XLim(2)+500;new_YLim=H.YLim(2)+500;set(gca,'XLim',[H.XLim(1),new_XLim],'YLim',[H.YLim(1),new_YLim]);set(gca,'fontsize',11,'FontWeight','bold');xlabel('调整后经度','FontSize',12,'FontWeight','bold');ylabel('调整后纬度','FontSize',12,'FontWeight','bold');boxontitle('\bf最佳环游路径示意图','fontsize',12);end5.3GUI图形用户界面程序functionvarargout=trip(varargin)%TRIPMATLABcodefortrip.fig%TRIP,byitself,createsanewTRIPorraisestheexisting%singleton*.%%H=TRIPreturnsthehandletoanewTRIPorthehandleto%theexistingsingleton*.%%TRIP('CALLBACK',hObject,eventData,handles,...)callsthelocal%functionnamedCALLBACKinTRIP.Mwiththegiveninputarguments.%%TRIP('Property','Value',...)createsanewTRIPorraisesthe%existingsingleton*.Startingfromtheleft,propertyvaluepairsare%appliedtotheGUIbeforetrip_OpeningFcngetscalled.An%unrecognizedpropertynameorinvalidvaluemakespropertyapplication%stop.Allinputsarepassedtotrip_OpeningFcnviavarargin.%%*SeeGUIOptionsonGUIDE'sToolsmenu.Choose"GUIallowsonlyone%instancetorun(singleton)".%%Seealso:GUIDE,GUIDATA,GUIHANDLES%Edittheabovetexttomodifytheresponsetohelptrip%LastModifiedbyGUIDEv2.514-Jun-201516:43:44%Begininitializationcode-DONOTEDITgui_Singleton=1;gui_State=struct('gui_Name',mfilename,...'gui_Singleton',gui_Singleton,...'gui_OpeningFcn',@trip_OpeningFcn,...'gui_OutputFcn',@trip_OutputFcn,...'gui_LayoutFcn',[],...'gui_Callback',[]);ifnargin&&ischar(varargin{1})gui_State.gui_Callback=str2func(varargin{1});endifnargout[varargout{1:nargout}]=gui_mainfcn(gui_State,varargin{:});elsegui_mainfcn(gui_State,varargin{:});end%Endinitializationcode-DONOTEDIT%---Executesjustbeforetripismadevisible.functiontrip_OpeningFcn(hObject,eventdata,handles,varargin)%Thisfunctionhasnooutputargs,seeOutputFcn.%hObjecthandletofigure%eventdatareserved-tobedefinedinafutureversionofMATLAB%handlesstructurewithhandlesanduserdata(seeGUIDATA)%varargincommandlineargumentstotrip(seeVARARGIN)%Choosedefaultcommandlineoutputfortriphandles.output=hObject;%Updatehandlesstructureguidata(hObject,handles);%UIWAITmakestripwaitforuserresponse(seeUIRESUME)%uiwait(handles.figure1);%---Outputsfromthisfunctionarereturnedtothecommandline.functionvarargout=trip_OutputFcn(hObject,eventdata,handles)%varargoutcellarrayforreturningoutputargs(seeVARARGOUT);%hObjecthandletofigure%eventdatareserved-tobedefinedinafutureversionofMATLAB%handlesstructurewithhandlesanduserdata(seeGUIDATA)%Getdefaultcommandlineoutputfromhandlesstructurevarargout{1}=handles.output;%---Executesonbuttonpressincheckbox1.functioncheckbox1_Callback(hObject,eventdata,handles)%hObjecthandletocheckbox1(seeGCBO)%eventdatareserved-tobedefinedinafutureversionofMATLAB%handlesstructurewithhandlesanduserdata(seeGUIDATA)%Hint:get(hObject,'Value')returnstogglestateofcheckbox1%---Executesonbuttonpressincheckbox2.functioncheckbox2_Callback(hObject,eventdata,handles)%hObjecthandletocheckbox2(seeGCBO)%eventdatareserved-tobedefinedinafutureversionofMATLAB%handlesstructurewithhandlesanduserdata(seeGUIDATA)%Hint:get(hObject,'Value')returnstogglestateofcheckbox2%---Executesonbuttonpressincheckbox3.functioncheckbox3_Callback(hObject,eventdata,handles)%hObjecthandletocheckbox3(seeGCBO)%eventdatareserved-tobedefinedinafutureversionofMATLAB%handlesstructurewithhandlesanduserdata(seeGUIDATA)%Hint:get(hObject,'Value')returnstogglestateofcheckbox3%---Executesonbuttonpressincheckbox4.functioncheckbox4_Callback(hObject,eventdata,handles)%hObjecthandletocheckbox4(seeGCBO)%eventdatareserved-tobedefinedinafutureversionofMATLAB%handlesstructurewithhandlesanduserdata(seeGUIDATA)%Hint:get(hObject,'Value')returnstogglestateofcheckbox4%---Executesonbuttonpressincheckbox5.functioncheckbox5_Callback(hObject,eventdata,handles)%hObjecthandletocheckbox5(seeGCBO)%eventdatareserved-tobedefinedinafutureversionofMATLAB%handlesstructurewithhandlesanduserdata(seeGUIDATA)%Hint:get(hObject,'Value')returnstogglestateofcheckbox5%---Executesonbuttonpressincheckbox6.functioncheckbox6_Callback(hObject,eventdata,handles)%hObjecthandletocheckbox6(seeGCBO)%eventdatareserved-tobedefinedinafutureversionofMATLAB%handlesstructurewithhandlesanduserdata(seeGUIDATA)%Hint:get(hObject,'Value')returnstogglestateofcheckbox6%---Executesonbuttonpressincheckbox7.functioncheckbox7_Callback(hObject,eventdata,handles)%hObjecthandletocheckbox7(seeGCBO)%eventdatareserved-tobedefinedinafutureversionofMATLAB%handlesstructurewithhandlesanduserdata(seeGUIDATA)%Hint:get(hObject,'Value')returnstogglestateofcheckbox7%---Executesonbuttonpressincheckbox8.functioncheckbox8_Callback(hObject,eventdata,handles)%hObjecthandletocheckbox8(seeGCBO)%eventdatareserved-tobedefinedinafutureversionofMATLAB%handlesstructurewithhandlesanduserdata(seeGUIDATA)%Hint:get(hObject,'Value')returnstogglestateofcheckbox8%---Executesonbuttonpressincheckbox9.functioncheckbox9_Callback(hObject,eventdata,handles)%hObjecthandletocheckbox9(seeGCBO)%eventdatareserved-tobedefinedinafutureversionofMATLAB%handlesstructurewithhandlesanduserdata(seeGUIDATA)%Hint:get(hObject,'Value')returnstogglestateofcheckbox9%---Executesonbuttonpressincheckbox10.functioncheckbox10_Callback(hObject,eventdata,handles)%hObjecthandletocheckbox10(seeGCBO)%eventdatareserved-tobedefinedinafutureversionofMATLAB%handlesstructurewithhandlesanduserdata(seeGUIDATA)%Hint:get(hObject,'Value')returnstogglestateofcheckbox10%---Executesonbuttonpressincheckbox11.functioncheckbox11_Callback(hObject,eventdata,handles)%hObjecthandletocheckbox11(seeGCBO)%eventdatareserved-tobedefinedinafutureversionofMATLAB%handlesstructurewithhandlesanduserdata(seeGUIDATA)%Hint:get(hObject,'Value')returnstogglestateofcheckbox11functionedit1_Callback(hObject,eventdata,handles)%hObjecthandletoedit1(seeGCBO)%eventdatareserved-tobedefinedinafutureversionofMATLAB%handlesstructurewithhandlesanduserdata(seeGUIDATA)%Hints:get(hObject,'String')returnscontentsofedit1astext%str2double(get(hObject,'String'))returnscontentsofedit1asadoubles_edit1=str2double(get(hObject,'String'));ifisnan(s_edit1)set(hObject,'String','500')endifs_edit1<0|s_edit1>10000set(hObject,'String','500')end%---Executesduringobjectcreation,aftersettingallproperties.functionedit1_CreateFcn(hObject,eventdata,handles)%hObjecthandletoedit1(seeGCBO)%eventdatareserved-tobedefinedinafutureversionofMATLAB%handlesempty-handlesnotcreateduntilafterallCreateFcnscalled%Hint:editcontrolsusuallyhaveawhitebackgroundonWindows.%SeeISPCandCOMPUTER.ifispc&&isequal(get(hObject,'BackgroundColor'),get(0,'defaultUicontrolBackgroundColor'))set(hObject,'BackgroundColor','white');endfunctionedit2_Callback(hObject,eventdata,handles)%hObjecthandletoedit2(seeGCBO)%eventdatareserved-tobedefinedinafutureversionofMATLAB%handlesstructurewithhandlesanduserdata(seeGUIDATA)%Hints:get(hObject,'String')returnscontentsofedit2astext%str2double(get(hObject,'String'))returnscontentsofedit2asadoublea(1)=get(handles.checkbox1,'Value');a(2)=get(handles.checkbox2,'Value');a(3)=get(handles.checkbox3,'Value');a(4)=get(handles.checkbox4,'Value');a(5)=get(handles.checkbox5,'Value');a(6)=get(handles.checkbox6,'Value');a(7)=get(handles.checkbox7,'Value');a(8)=get(handles.checkbox8,'Value');a(9)=get(handles.checkbox9,'Value');a(10)=get(handles.checkbox10,'Value');a(11)=get(handles.checkbox11,'Value');s_edit2=str2double(get(hObject,'String'));ifisnan(s_edit2)set(hObject,'String','1')endasum=sum(a)+1;ifs_edit2<0set(hObject,'String','1');elseifs_edit2>asumset(hObject,'String',num2str(asum));end%---Executesduringobjectcreation,aftersettingallproperties.functionedit2_CreateFcn(hObject,eventdata,handles)%hObjecthandletoedit2(seeGCBO)%eventdatareserved-tobedefinedinafutureversionofMATLAB%handlesempty-handlesnotcreateduntilafterallCreateFcnscalled%Hint:editcontrolsusuallyhaveawhitebackgroundonWindows.%SeeISPCandCOMPUTER.ifispc&&isequal(get(hObject,'BackgroundColor'),get(0,'defaultUicontrolBackgroundColor'))set(hObject,'BackgroundColor','white');end%---Executesonbuttonpressinpushbutton1.functionpushbutton1_Callback(hObject,eventdata,handles)%hObjecthandletopushbutton1(seeGCBO)%eventdatareserved-tobedefinedinafutureversionofMATLAB%handlesstructurewithhandlesanduserdata(seeGUIDATA)a(1)=get(handles.checkbox1,'Value');a(2)=get(handles.checkbox2,'Value');a(3)=get(handles.checkbox3,'Value');a(4)=get(handles.checkbox4,'Value');a(5)=get(handles.checkbox5,'Value');a(6)=get(handles.checkbox6,'Value');a(7)=get(handles.checkbox7,'Value');a(8)=get(handles.checkbox8,'Value');a(9)=get(handles.checkbox9,'Value');a(10)=get(handles.checkbox10,'Value');a(11)=get(handles.checkbox11,'Value');C_initial=[278.120000000000,503.540000000000;148.010000000000,549.240000000000;-1957.09000000000,-796.250000000000;1185.27000000000,-2.92000000000000;1541.98000000000,1495.72000000000;988.810000000000,1509.08000000000;2449.83000000000,-627.090000000000;4772.22000000000,-38.1600000000000;2148.10000000000,-3242.62000000000;739.620000000000,-1672.89000000000;-3199.34000000000,-1721.69000000000;30211672.09000000000];D_initial=[0,8.90000000000000,162.700000000000,67.2000000000000,92.4000000000000,83.9000000000000,180.800000000000,256.900000000000,304.400000000000,147.200000000000,274.500000000000,161.100000000000;8.90000000000000,0,148.900000000000,73.7000000000000,97.8000000000000,87.6000000000000,188.600000000000,264.600000000000,312.200000000000,154.800000000000,271.800000000000,168.200000000000;162.700000000000,148.900000000000,0,206.200000000000,256.200000000000,246.700000000000,339.600000000000,415.700000000000,369.400000000000,221.800000000000,120.600000000000,330.100000000000;67.2000000000000,73.7000000000000,206.200000000000,0,110.300000000000,111.100000000000,139.500000000000,218.200000000000,250.100000000000,118.300000000000,312.300000000000,157.700000000000;92.4000000000000,97.8000000000000,256.200000000000,110.300000000000,0,35.1000000000000,180.500000000000,248.500000000000,314.100000000000,218.500000000000,363.300000000000,85.7000000000000;83.9000000000000,87.6000000000000,246.700000000000,111.100000000000,35.1000000000000,0,208.300000000000,276.200000000000,341.900000000000,202.900000000000,355.500000000000,120.900000000000;180.800000000000,188.600000000000,339.600000000000,139.500000000000,180.500000000000,208.300000000000,0,163.300000000000,203.800000000000,141.500000000000,335.200000000000,204.700000000000;256.900000000000,264.600000000000,415.700000000000,218.200000000000,248.500000000000,276.200000000000,163.300000000000,0,318.400000000000,141.100000000000,481.400000000000,272.600000000000;304.400000000000,312.200000000000,369.400000000000,250.100000000000,314.100000000000,341.900000000000,203.800000000000,318.400000000000,0,186.400000000000,391.400000000000,364.800000000000;147.200000000000,154.800000000000,221.800000000000,118.300000000000,218.500000000000,202.900000000000,141.500000000000,141.100000000000,186.400000000000,0,243.700000000000,269;274.500000000000,271.800000000000,120.600000000000,312.300000000000,363.300000000000,355.500000000000,335.200000000000,481.400000000000,391.400000000000,243.700000000000,0,438.200000000000;161.100000000000,168.200000000000,330.100000000000,157.700000000000,85.7000000000000,120.900000000000,204.700000000000,272.600000000000,364.800000000000,269,438.200000000000,0];C=C_initial;D=D_initial;x=find(a==0);C(x,:)=[];D(x,:)=[];D(:,x)=[];y=find(a==1);b=[y,12];NC_max=str2double(get(handles.edit1,'String'));m=str2double(get(handles.edit2,'String'));Alpha=1;Beta=5;Rho=0.1;Q=str2double(get(handles.edit3,'String'));[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP_ZJ(C,D,NC_max,m,Alpha,Beta,Rho,Q);%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%开始画图axes(handles.axes1);%画图1DrawRoute(C,Shortest_Route,b);axes(handles.axes2);%画图2holdonH2=plot(L_best,'r','linewidth',2);H1=plot(L_ave);legend([H1,H2],'\bf平均路线长度','\bf最短路线长度')holdofftitle('运行过程中路线长度变化示意图','FontSize',12,'FontWeight','bold');xlabel('运行次数','FontSize',12,'FontWeight','bold');ylabel('长度',