论文部分内容阅读
[摘 要] 针对遗传算法收敛速度过慢的问题，将蚁群算法与遗传算法相结合，应用于求解旅行商问题，同时对两种算法求解旅行商问题的结果进行模拟与对比分析，实验结果表明结合算法可以有效地解决旅行商问题，在求解效率和求解质量上都取得了很好的效果。
[关键词] 遗传算法；蚁群遗传结合算法；旅行商问题
doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2016. 17. 103
[中图分类号] TP312 [文献标识码] A [文章编号] 1673 - 0194（2016）17- 0184- 02
1 前 言
20世纪70年代以来，人工智能的应用研究得到了迅速的发展，其中关于智能优化算法的研究与应用越来越多，遗传和蚁群作为两种比较流行的算法，都具有各自的优势，本文主要研究在对比两种算法性能优势与不足的基础上，采用两种算法相结合来解决旅行商问题，从而避免单一算法的缺点。通过实验数据仿真表明，将蚁群与遗传算法相结合可以更有效地解决旅行商问题。
2 旅行商问题（TSP）模型
“旅行商问题”也被称为“旅行推销员问题”，指一名推销员要拜访多个地点时，如何找到拜访多个地点的最短路径。求其最短路径可以用数学模型表示：
假设路径R=（c0，c1，…，cn-1），满足f（R）的值最小，则路径R就是所求的路径。
其中ci为城市号，i=（0，1，2，…，n-1）。d（ci，cj）表示城市ci到城市cj的距离。
2.1 遗传算法求解TSP
遗传算法（GA）是由美国Michignan大学的Holland于20世纪60年代提出的，其主要原理是以自然选择和遗传进化论为基础，模拟生物界的遗传规律，对种群中的个体不断进化，达到产生更优秀种群的目的。
该算法主要特点是：具有自组织、自适应和自学习性，良好的全局优化性和稳健性，较强的鲁棒性，易于和其他算法结合，计算过程简单，操作性强。但存在早熟、收敛速度过慢等缺点。
2.2 蚁群遗传结合算法求解TSP
通过将遗传算法与蚁群算法结合，形成一种全局优化算法，使得遗传算法和其他算法取长补短，有效提高了算法的收敛速度，并且还能防止早熟收敛，改进的结合算法的具体实现是，利用蚁群算法经过一次蚂蚁全局循环，得到一个较优解集，再将所获得的优解集作为遗传算法的初始种群，加快遗传算法的收敛速度，减少遗传算法的寻优次数，提高算法的执行效率。其解决TSP问题的流程说明：
（1）初始化蚁群算法的信息启发式因子α=1，期望值启发式因子β=2，信息素挥发系数ρ=0.1，信息素强度Q=100，其中路径初始信息量为1，初始时刻为0。
（2）初始化蚂蚁的位置，将m只蚂蚁随机分配到n个城市中。
（3）根据式（2）计算蚂蚁k的状态转移概率，即选择下一个城市概率。
（4）将新加入的城市移动到蚂蚁k的禁忌表中，更新禁忌表。
（5）重复步骤（3）、（4），分别求出每只蚂蚁遍历一次的路径。
（6）将步骤（1）至（5）得到的m只蚂蚁的遍历的路径作为遗传算法的初始种群。
（7）初始化遗传算法的交叉概率pc，变异概率pm以及最大迭代次数的值。
（8）若i大于最大迭代次数，则结束循环，比较每次循环最短路径，得到算法的最优解。
下面通过实例来验证比较两种算法求解TSP问题的实验结果。
通过以上实例数据的仿真对比分析，可以看出结合算法具有更好的优化性能。
3 结 语
本文采用的改进的蚁群遗传结合算法，通过蚁群算法迭代获得一个较优解集，作为遗传算法的初始种群，然后采用遗传算法寻求最优解。实验仿真表明，结合算法在解决TSP问题上具有较快的收敛速度和较强的全局寻优能力。
主要参考文献
[1]王超学，孔月萍，董丽丽.智能优化算法与应用[M].西安：西北大学出版社，2012，9（1）.
[2]于莹莹，陈燕，李桃迎.改进的蚁群遗传算法求解旅行商问题[J].计算机仿真，2013（11）： 30-11.
[关键词] 遗传算法；蚁群遗传结合算法；旅行商问题
doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2016. 17. 103
[中图分类号] TP312 [文献标识码] A [文章编号] 1673 - 0194（2016）17- 0184- 02
1 前 言
20世纪70年代以来，人工智能的应用研究得到了迅速的发展，其中关于智能优化算法的研究与应用越来越多，遗传和蚁群作为两种比较流行的算法，都具有各自的优势，本文主要研究在对比两种算法性能优势与不足的基础上，采用两种算法相结合来解决旅行商问题，从而避免单一算法的缺点。通过实验数据仿真表明，将蚁群与遗传算法相结合可以更有效地解决旅行商问题。
2 旅行商问题（TSP）模型
“旅行商问题”也被称为“旅行推销员问题”，指一名推销员要拜访多个地点时，如何找到拜访多个地点的最短路径。求其最短路径可以用数学模型表示：
假设路径R=（c0，c1，…，cn-1），满足f（R）的值最小，则路径R就是所求的路径。
其中ci为城市号，i=（0，1，2，…，n-1）。d（ci，cj）表示城市ci到城市cj的距离。
2.1 遗传算法求解TSP
遗传算法（GA）是由美国Michignan大学的Holland于20世纪60年代提出的，其主要原理是以自然选择和遗传进化论为基础，模拟生物界的遗传规律，对种群中的个体不断进化，达到产生更优秀种群的目的。
该算法主要特点是：具有自组织、自适应和自学习性，良好的全局优化性和稳健性，较强的鲁棒性，易于和其他算法结合，计算过程简单，操作性强。但存在早熟、收敛速度过慢等缺点。
2.2 蚁群遗传结合算法求解TSP
通过将遗传算法与蚁群算法结合，形成一种全局优化算法，使得遗传算法和其他算法取长补短，有效提高了算法的收敛速度，并且还能防止早熟收敛，改进的结合算法的具体实现是，利用蚁群算法经过一次蚂蚁全局循环，得到一个较优解集，再将所获得的优解集作为遗传算法的初始种群，加快遗传算法的收敛速度，减少遗传算法的寻优次数，提高算法的执行效率。其解决TSP问题的流程说明：
（1）初始化蚁群算法的信息启发式因子α=1，期望值启发式因子β=2，信息素挥发系数ρ=0.1，信息素强度Q=100，其中路径初始信息量为1，初始时刻为0。
（2）初始化蚂蚁的位置，将m只蚂蚁随机分配到n个城市中。
（3）根据式（2）计算蚂蚁k的状态转移概率，即选择下一个城市概率。
（4）将新加入的城市移动到蚂蚁k的禁忌表中，更新禁忌表。
（5）重复步骤（3）、（4），分别求出每只蚂蚁遍历一次的路径。
（6）将步骤（1）至（5）得到的m只蚂蚁的遍历的路径作为遗传算法的初始种群。
（7）初始化遗传算法的交叉概率pc，变异概率pm以及最大迭代次数的值。
（8）若i大于最大迭代次数，则结束循环，比较每次循环最短路径，得到算法的最优解。
下面通过实例来验证比较两种算法求解TSP问题的实验结果。
通过以上实例数据的仿真对比分析，可以看出结合算法具有更好的优化性能。
3 结 语
本文采用的改进的蚁群遗传结合算法，通过蚁群算法迭代获得一个较优解集，作为遗传算法的初始种群，然后采用遗传算法寻求最优解。实验仿真表明，结合算法在解决TSP问题上具有较快的收敛速度和较强的全局寻优能力。
主要参考文献
[1]王超学，孔月萍，董丽丽.智能优化算法与应用[M].西安：西北大学出版社，2012，9（1）.
[2]于莹莹，陈燕，李桃迎.改进的蚁群遗传算法求解旅行商问题[J].计算机仿真，2013（11）： 30-11.