《用蚁群算法求解有线路约束的TSP问题.doc》由会员分享，可在线阅读，更多相关《用蚁群算法求解有线路约束的TSP问题.doc（2页珍藏版）》请在三一文库上搜索。
1、用蚁群算法求解有线路约束的 TSP问题【摘要】本文利用01矩阵，设计了新型的蚁群算法，用于解决有线路约束 的经典旅行商问题，并求出了在有线路约束下，走遍不同城市的行程最短的最佳 路线和最佳路线的长度。【关键词】蚁群算法；01矩阵;matlab;最佳路线;最佳路线长度本文将结合一个具体的事例，给出相关的解决方案的蚁群算法的matlab代码。1 问题的提出给定76个城市的坐标，城市之间相互通路信息如图1所示，请设计线路，能走遍所有城市，行程最短，并用画图的方式展示所求结果。图1相互联系信息2问题分析与求解这是一个最短路优化问题，如果没有线路的约束，我们可以运用原始的蚁群 算法，求得最佳路线。但是现
2、在城市之间有了线路约束， 所以需要改进原来的算 法。原始蚁群算法分析：原始的蚁群算法中有一个启发因子 Eta，算法中Eta=1./D,其中D是城市之 间的距离矩阵，D （i,j）为D的元素。可以看出，启发因子是跟距离有关的唯一 量，D（i,j）越小，Eta （i,j）越大，i,j两个城市之间的线路进入最佳路线的可能性 就越大。另外，若i工,，显然有D（i，j）,1从而有Eta （i，j） <1解决方案：首先建立01矩阵a，i、j之间存在通路，a （i，j ）=1, i、j之间不存在通路， a（i，j） =0。令Eta=1./D+a（i,j）,显然有当i、j之间存在通路，I、m之间不存在通 路时有：Eta （i，j）> Eta（l，m），这样就使得新的算法可以求解有路线约束的 TSP问题。3.符号说明R_best:各代最佳路线L_best:各代最佳路线的长度