论文部分内容阅读
摘要：介绍了蚁群算法的特点，提出了基于蚁群算法的TSP问题的求解方法，并分别建立基本蚁群算法及MAX—MIN蚁群算法模型，并引入“三步走”法确定模型参数的最优组合，还结合了交叉局部优化相关的求凸壳顶点的算法进行预处理，进行仿真分析比较。实验结果表明基于MMAS模型相对于基本蚁群算法模型，有比较好最短路径选择能力及良好的可扩展性能，能够较好地适应物流配送系统的要求。
关键词：TSP；MMAS；信息素；三步走法
中图分类号：F224文献标识码：A文章编号：1002-3100(2009)01-0027-03
Abstract: Introduces the features of ant colony optimization, puts forward solving method of TSP based on ant colony optimization, establishes these models of basic ant colony optimization and max-min ant colony optimization respectively, ascertains optimum combination of model parametric by three-step method and carries out reprocessing combining algorithm of convex hull peak related to cross-regional optimization to carry on simulation analysis and comparison. The result indicates that MMAS is superior to basic ant colony optimization because it chooses the shortest path and better meets the demand of logistics distribution system.
Key words: TSP; MMAS; pheromone; three-step method
0引言
蚁群算法，是一种用来在图中寻找优化路径的机率型技术，由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，经过各种数值仿真结果表明该算法具有许多优良的性质，具有一种新的模拟进化优化方法的有效性和应用价值，是一种求解组合最优化问题的新型通用启发式方法，具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点，通过建立适当的数学模型，可以解决一维静态优化问题甚至多维动态组合优化问题。
本文采用蚁群算法对TSP问题进行研究，设计一个基本的蚁群算法解决最短路径问题的模型，并提出一种最大——最小蚂蚁系统（MMAS）模型，通过引入“三步走”法确定模型参数的最优组合，使所选参数让性能达到最优；改进信息素更新规律及动态调整参数；并且引进去交叉局部优化相关的求凸壳顶点的算法，改进算法的局部搜索能力，对MMAS模型加以改进，最终使收敛速度和收敛效果达到令人满意的结果。
1基本蚁群算法及MMAS在TSP中的应用
1.1问题描述
旅行商问题（traveling salesman problem，TSP）是著名NP 完全问题之一，常被用于测试和评价算法的性能。该问题可以简单描述如下：有一个商人需要选择一条最短的哈密顿回路拜访各城市，即所有城市必须经过且只经过一次，而最后要回到原来出发的城市。如果用穷举的办法解决该问题，时间复杂度显然是很大。当比较大的时候，现有的计算机是无法在可接受的时间内求解该问题的。因此很多高效的算法被用于尝试求解TSP。本文采用蚁群算法对TSP问题进行研究，并通过基本蚁群算法、MMAS、改进的MMAS三者直接的比较得出最优解。
1.2算法设计
（1）蚁群算法构造TSP问题的基本数学模型
设bt表示t时刻位于元素i城市的蚂蚁数目，m表示蚂蚁的总数目，n表示城市的规模：
t+n=p•t+△t（1）
t为t时刻路径i,j上的信息量，则m=bt在初始时刻各路径上的信息量相等，并设0＝const。
蚂蚁kk＝1,2,…,m在运动过程中，根据各路径上的信息量决定其转移方向。这里用禁忌表tabu（k＝1,2,3,…,m）来记录蚂蚁k当前所走过的城市，集合随着tabu进化过程做动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率：pt表示在t时刻蚂蚁k由城市i转移到城市j的状态转移概率：
pt=，若j∈allowed0，否则 （2）
上式中，allowed＝C-tabu表示蚂蚁下一步允许选择的城市，C表示所有城市的集合；表示路径i,j距离d的倒数即
=1/d；α、β分别表示信息素和路径信息对转移概率的影响程度。随着时间的推移，以前留下来的信息素会逐渐挥发，用参数p表示信息素的挥发程度。经过n个时刻，每个蚂蚁都完成一次循环，各条路径上的信息素须做调整：
t+n=1-p•t+△ （3）
其中0＜p＜1，△表示本次循环中所有经历过的路径ij的蚂蚁留在该路径上的信息量的增量，局部调整用ant-cycle system调整信息素的方法：
△=Q/L，ant经过i,j0，否则 （4）
其中，Q为常数，表示蚂蚁循环一周所释放的总信息量，L表示ant在这次循环中所走的路径的长度。
（2）最大最小信息素算法（MMAS）
MMAS与基本蚁群算法的主要区别在于把信息素数量＝,，较好地避免了搜索面的局部停滞（早熟现象）。每次迭代路径上增加的最大信息素为1/Ls，其中Ls为对应全局最好解的路径长度，更新最好解时，同时更新，，与信息素挥发因子p及Ls成反比，而与精英蚂蚁的数目成正比。这里可按照以下策略动态的确定t和t。
①在最初信息素还未得到更新时（即产生第一代解前），采用下式确定t和t：
t=g （5）
t= （6）
②一旦信息素更新以后则采用下式才更新t：
t=g+ （7）
（3）去交叉局部优化
在这里引进去交叉局部优化相关的求凸壳顶点的算法对MMAS算法进行改进，凸壳问题（convex hull problem）是几何学中的基本问题之一，在TSP中主要是对各点进行预处理。设S是平面上的非空点集，z和z是S中的任意两点，t是0与1之间的任意实数。如果满足公式8的点Z属于S，则S为凸集。
z＝tz+1-tz0≤t≤1（8）
凸集S中的凸壳是包含S的周长最小的凸多边形，凸壳必包含凸集，在TSP的预处理算法中，从某一凸壳的顶点开始，需要判断与其不相邻的下一个凸壳顶点是否在同一条直线上，若不是，则消去此线，然后以此类推对其余的凸壳顶点进行同样处理。
2实例仿真
实例：中国的31个省会城市的坐标C=[1 304 2 312；3 639 1 315；4 177 2 244；3 712 1 399；3 488 1 535；3 326 1 556；3 238 1 229；4 196 1 004；4 312 790；4 386 570；3 007 1 970；2 562 1 756；2 788 1 491；2 381 1 676；1 332 695；3 715
1 678；3 918 2 179；4 061 2 370；3 780 2 212；3 676 2 578；4 029 2 838；4 263 2 931；3 429 1 908；3 507 2 367；3 394
2 643；3 439 3 201；2 935 3 240；3 140 3 550；2 545 2 357；2 778 2 826；2 370 2 975]，下面以31个城市的坐标为参考模型，分别建模仿真。
首先采用“三步走”方法选择蚁群算法的最优参数组合：
（1）确定蚂蚁的数目，当城市规模大致是蚂蚁数目的1.5倍时，蚁群算法的全局收敛性和收敛速度都比较好。显然这里蚂蚁数目m选20比较适宜，城市n选31。
（2）参数粗调，调整取值范围较大的信息启发因子，期望启发式因子β以及信息素强度Q等参数以得到较理想的解。经过调整取＝1.0，β＝5.0，Q=100。
（3）参数微调，在较小范围内调整信息素挥发因子ρ。信息挥发素ρ取值为0.04。
实践证明运用此方法后在减少计算量、快速搜索、收敛性、收敛速度等方面都有较好的效果。在MMAS模型中σ取5，0＝2。进行仿真后得到以下数据：图1为运行10次基本蚁群算法模型得到的最优路径；图2为运行10次改进的MMAS模型得到的最优路径；图3为运行10次未改进的MMAS模型得到的最优路径；表1中为两种方法中的最短路径的距离、平均距离、得到最优最小迭代数及平均迭代数。
上述数据表明改进型的MMAS对于基本蚁群算法及MMAS有一定的优越性，所得的结果在收敛性、稳定性、收敛速度等方面都有很大的改进，并且改进型MMAS不会出现图3中的那种交叉路径，能够起到避免出现过早呆滞和及时纠正交叉的作用。图4列出改进的MMAS在实验过程中得到实时路径数据。
3小结
本文主要是分析了蚁群算法及两种类型蚁群算法在旅行商问题中的应用，通过MATLAB编程仿真了所建立模型，并把获得的结果进行了比较分析，由实时路径图也可以看到此算法的稳定性能较强，能够较好的应用来解决旅行商问题。
参考文献：
[1] 段海滨. 蚁群算法原理及其应用[M]. 北京：科学技术出版社，2005.
[2] 赵霞. MAX-MIN蚂蚁系统算法及其收敛性证明[J]. 计算机工程与应用，2006(8):70-72.
[3] 陈宝文，宋申民. 应用于车辆路径问题的多蚁群算法[C]//第25届中国控制会议论文集（下册），2006:1723-1726.
[4] Yang Haiqing, Yang Haihong. An self-organizing neural network with convex-hull expanding property for TSP[C]//Neural Net-works and Brain, ICNN&B' 05, International Conference on Volume1，2005:379-383.
[5] 蔡之华，彭锦国，高伟,等. 一种改进的求解TSP问题的演化算法[J]. 计算机学报，2005(28):823-828.
[6] 周培德. 求凸包定点的一种算法[J]. 北京理工大学学报，1993(13):69-72.
[7]赵凯，熊红云. 模糊车辆配送问题的改进算法[J]. 物流科技，2008(2):24-27.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
关键词：TSP；MMAS；信息素；三步走法
中图分类号：F224文献标识码：A文章编号：1002-3100(2009)01-0027-03
Abstract: Introduces the features of ant colony optimization, puts forward solving method of TSP based on ant colony optimization, establishes these models of basic ant colony optimization and max-min ant colony optimization respectively, ascertains optimum combination of model parametric by three-step method and carries out reprocessing combining algorithm of convex hull peak related to cross-regional optimization to carry on simulation analysis and comparison. The result indicates that MMAS is superior to basic ant colony optimization because it chooses the shortest path and better meets the demand of logistics distribution system.
Key words: TSP; MMAS; pheromone; three-step method
0引言
蚁群算法，是一种用来在图中寻找优化路径的机率型技术，由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，经过各种数值仿真结果表明该算法具有许多优良的性质，具有一种新的模拟进化优化方法的有效性和应用价值，是一种求解组合最优化问题的新型通用启发式方法，具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点，通过建立适当的数学模型，可以解决一维静态优化问题甚至多维动态组合优化问题。
本文采用蚁群算法对TSP问题进行研究，设计一个基本的蚁群算法解决最短路径问题的模型，并提出一种最大——最小蚂蚁系统（MMAS）模型，通过引入“三步走”法确定模型参数的最优组合，使所选参数让性能达到最优；改进信息素更新规律及动态调整参数；并且引进去交叉局部优化相关的求凸壳顶点的算法，改进算法的局部搜索能力，对MMAS模型加以改进，最终使收敛速度和收敛效果达到令人满意的结果。
1基本蚁群算法及MMAS在TSP中的应用
1.1问题描述
旅行商问题（traveling salesman problem，TSP）是著名NP 完全问题之一，常被用于测试和评价算法的性能。该问题可以简单描述如下：有一个商人需要选择一条最短的哈密顿回路拜访各城市，即所有城市必须经过且只经过一次，而最后要回到原来出发的城市。如果用穷举的办法解决该问题，时间复杂度显然是很大。当比较大的时候，现有的计算机是无法在可接受的时间内求解该问题的。因此很多高效的算法被用于尝试求解TSP。本文采用蚁群算法对TSP问题进行研究，并通过基本蚁群算法、MMAS、改进的MMAS三者直接的比较得出最优解。
1.2算法设计
（1）蚁群算法构造TSP问题的基本数学模型
设bt表示t时刻位于元素i城市的蚂蚁数目，m表示蚂蚁的总数目，n表示城市的规模：
t+n=p•t+△t（1）
t为t时刻路径i,j上的信息量，则m=bt在初始时刻各路径上的信息量相等，并设0＝const。
蚂蚁kk＝1,2,…,m在运动过程中，根据各路径上的信息量决定其转移方向。这里用禁忌表tabu（k＝1,2,3,…,m）来记录蚂蚁k当前所走过的城市，集合随着tabu进化过程做动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率：pt表示在t时刻蚂蚁k由城市i转移到城市j的状态转移概率：
pt=，若j∈allowed0，否则 （2）
上式中，allowed＝C-tabu表示蚂蚁下一步允许选择的城市，C表示所有城市的集合；表示路径i,j距离d的倒数即
=1/d；α、β分别表示信息素和路径信息对转移概率的影响程度。随着时间的推移，以前留下来的信息素会逐渐挥发，用参数p表示信息素的挥发程度。经过n个时刻，每个蚂蚁都完成一次循环，各条路径上的信息素须做调整：
t+n=1-p•t+△ （3）
其中0＜p＜1，△表示本次循环中所有经历过的路径ij的蚂蚁留在该路径上的信息量的增量，局部调整用ant-cycle system调整信息素的方法：
△=Q/L，ant经过i,j0，否则 （4）
其中，Q为常数，表示蚂蚁循环一周所释放的总信息量，L表示ant在这次循环中所走的路径的长度。
（2）最大最小信息素算法（MMAS）
MMAS与基本蚁群算法的主要区别在于把信息素数量＝,，较好地避免了搜索面的局部停滞（早熟现象）。每次迭代路径上增加的最大信息素为1/Ls，其中Ls为对应全局最好解的路径长度，更新最好解时，同时更新，，与信息素挥发因子p及Ls成反比，而与精英蚂蚁的数目成正比。这里可按照以下策略动态的确定t和t。
①在最初信息素还未得到更新时（即产生第一代解前），采用下式确定t和t：
t=g （5）
t= （6）
②一旦信息素更新以后则采用下式才更新t：
t=g+ （7）
（3）去交叉局部优化
在这里引进去交叉局部优化相关的求凸壳顶点的算法对MMAS算法进行改进，凸壳问题（convex hull problem）是几何学中的基本问题之一，在TSP中主要是对各点进行预处理。设S是平面上的非空点集，z和z是S中的任意两点，t是0与1之间的任意实数。如果满足公式8的点Z属于S，则S为凸集。
z＝tz+1-tz0≤t≤1（8）
凸集S中的凸壳是包含S的周长最小的凸多边形，凸壳必包含凸集，在TSP的预处理算法中，从某一凸壳的顶点开始，需要判断与其不相邻的下一个凸壳顶点是否在同一条直线上，若不是，则消去此线，然后以此类推对其余的凸壳顶点进行同样处理。
2实例仿真
实例：中国的31个省会城市的坐标C=[1 304 2 312；3 639 1 315；4 177 2 244；3 712 1 399；3 488 1 535；3 326 1 556；3 238 1 229；4 196 1 004；4 312 790；4 386 570；3 007 1 970；2 562 1 756；2 788 1 491；2 381 1 676；1 332 695；3 715
1 678；3 918 2 179；4 061 2 370；3 780 2 212；3 676 2 578；4 029 2 838；4 263 2 931；3 429 1 908；3 507 2 367；3 394
2 643；3 439 3 201；2 935 3 240；3 140 3 550；2 545 2 357；2 778 2 826；2 370 2 975]，下面以31个城市的坐标为参考模型，分别建模仿真。
首先采用“三步走”方法选择蚁群算法的最优参数组合：
（1）确定蚂蚁的数目，当城市规模大致是蚂蚁数目的1.5倍时，蚁群算法的全局收敛性和收敛速度都比较好。显然这里蚂蚁数目m选20比较适宜，城市n选31。
（2）参数粗调，调整取值范围较大的信息启发因子，期望启发式因子β以及信息素强度Q等参数以得到较理想的解。经过调整取＝1.0，β＝5.0，Q=100。
（3）参数微调，在较小范围内调整信息素挥发因子ρ。信息挥发素ρ取值为0.04。
实践证明运用此方法后在减少计算量、快速搜索、收敛性、收敛速度等方面都有较好的效果。在MMAS模型中σ取5，0＝2。进行仿真后得到以下数据：图1为运行10次基本蚁群算法模型得到的最优路径；图2为运行10次改进的MMAS模型得到的最优路径；图3为运行10次未改进的MMAS模型得到的最优路径；表1中为两种方法中的最短路径的距离、平均距离、得到最优最小迭代数及平均迭代数。
上述数据表明改进型的MMAS对于基本蚁群算法及MMAS有一定的优越性，所得的结果在收敛性、稳定性、收敛速度等方面都有很大的改进，并且改进型MMAS不会出现图3中的那种交叉路径，能够起到避免出现过早呆滞和及时纠正交叉的作用。图4列出改进的MMAS在实验过程中得到实时路径数据。
3小结
本文主要是分析了蚁群算法及两种类型蚁群算法在旅行商问题中的应用，通过MATLAB编程仿真了所建立模型，并把获得的结果进行了比较分析，由实时路径图也可以看到此算法的稳定性能较强，能够较好的应用来解决旅行商问题。
参考文献：
[1] 段海滨. 蚁群算法原理及其应用[M]. 北京：科学技术出版社，2005.
[2] 赵霞. MAX-MIN蚂蚁系统算法及其收敛性证明[J]. 计算机工程与应用，2006(8):70-72.
[3] 陈宝文，宋申民. 应用于车辆路径问题的多蚁群算法[C]//第25届中国控制会议论文集（下册），2006:1723-1726.
[4] Yang Haiqing, Yang Haihong. An self-organizing neural network with convex-hull expanding property for TSP[C]//Neural Net-works and Brain, ICNN&B' 05, International Conference on Volume1，2005:379-383.
[5] 蔡之华，彭锦国，高伟,等. 一种改进的求解TSP问题的演化算法[J]. 计算机学报，2005(28):823-828.
[6] 周培德. 求凸包定点的一种算法[J]. 北京理工大学学报，1993(13):69-72.
[7]赵凯，熊红云. 模糊车辆配送问题的改进算法[J]. 物流科技，2008(2):24-27.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。