论文部分内容阅读
【摘 要】论文提出了一种改进的遗传算法求解旅行商问题（TSP）。该算法结合TSP的特点，采用实数编码方式减少算法计算复杂度；等位交叉方式扩大算法的搜索空间，改善寻优能力；轮盘赌选择策略加快算法的收敛速度。通过30个城市的benchmark实例进行仿真试验，试验结果表明，改进的遗传算法改善了全局搜索能力，具有较快的收敛速度和较高的收敛精度。
【Abstract】In this paper， an improved genetic algorithm for traveling salesman problem （TSP） is proposed.The algorithm combines the characteristics of TSP， using real number encoding to reduce the computational complexity of the algorithm， a cross way to expand the search space and improve searching ability， roulette selection strategy to accelerate the convergence of the algorithm.In this paper， it has simulated benchmark examples in thirty cities.The simulation results show that the improved genetic algorithm can improve the global search ability， and its convergence speed and the convergence precision is higher.
【关键词】旅行商问题；遗传算法；收敛速度
【Keywords】traveler problem；genetic algorithm；convergence precision
【中图分类号】TP18 【文献标志码】A 【文章编号】1673-1069（2017）03-0096-03
1 引言
旅行商问题（TSP）也称货郎担问题，它旨在寻求旅行商在遍历诸多城市一次最后回到起点城市的最短路径，是数学图论中的经典问题。在实际生活中，像物流路径优化、车间调度和网络路由选址等都可归结为TSP，因此，TSP的研究具有重要的理论意义和实际价值。
Karp[1]证明了TSP是一个NP难问题，传统的优化算法在求解TSP问题时往往会陷入局部最优，尤其随着城市数量的增加，计算量也急剧增加，致使很多算法瘫痪。因此智能优化算法强的搜索效率、快速的收敛速度在求解TSP中得到了广泛应用。Aziz[2]提出了广义的蚁群算法，算法中融合了局部和全局两种信息素更新机制，提高全局迅游能力。何湘竹[3]将混沌搜索机制融入基于教与学的优化算法求解TSP，通过benchmark实例仿真试验显示，新算法性能更优越。段艳明[4]将果蝇优化算法的连续空间对应到离散规划，利用了遗传算法的交叉、变异操作进行路径的寻优，加快局部搜索能力和收敛速度。
遗传算法是一种模拟生物进化过程的随机搜索优化方法，与其他的局部搜索算法相比，遗传算法具有更强的鲁棒性，隐形的并行搜索机制增强了算法寻优能力，但遗传算法也存在缺陷，例如： 种群常常会出现早熟收敛、易陷入局部最优的问题，使算法的搜索性能大大降低[5]。针对这些问题，学者提出了许多解决方法，如参数控制、多种群的运用和交配限制[6-8]等。
2 求解TSP的改进遗传算法
鉴于目前遗传算法在优化领域的优越性能，论文以TSP为例，提出了改进的遗传算法。
2.1 实数编码
对包含n个城市的TSP问题，我们提出一种新的有效编码方法——实数编码。它是指整数1到的一个全排列所构成的实数序列a1，a2，…，an，其中a∈[1，n）之间的整数，编码中ai表示编号为的城市排在路径上的第ai个位置。
2.2 轮盘赌选择
轮盘赌选择法是遗传算法中常用的选择方式，首先计算每个个体的适应度值fi，i∈[1，ps），ps为种群规模。这里fi的值越大，说明这个个体越优秀；其次，计算每个个体的选择概率pi=fi/（∑fi）和累积概率Pi=∑■■pi；最后，随机产生一个实数num∈[0，1]，选取满足num 2.3 等位交叉
交叉算子是遗传算法中关键的操作，它涉及种群的多样性和算法的搜索效率等，论文基于等位交叉来改变两个交叉个体的局部基因片段，使每個个体都能遗传到对方的基因。具体操作如图1所示。
■
图1 等位交叉具体操作图
2.4 改进的遗传算法
基于以上操作算子，求解 TSP的改进遗传算法步骤如下：
步骤1 初始化遗传算法种群个数ps、最大迭代次数inmax、交叉概率pc和变异概率pm等；
步骤2 根据各城市的坐标计算各个城市之间的距离，记作Cij，i，j∈[1，n]，代表第i个城市到第j个城市的距离，初始生成ps个个体，即ps个城市路线；
步骤3 计算每条路线的距离Si，计算适应度值根据公式fi=1/Si，计算选择概率pi=fi/（∑fi）和累积概率Pi=∑■■pi；
步骤4 根据选择概率和累积概率采用轮盘赌选择法选择要交叉的两个个体；
步骤5 根据交叉概率判断是否交叉，交叉采用等位交叉法，产生两个等位基因互换的两个交叉个体；
步骤6 根据变异概率判断是否变异，选择变异基因位置，随机产生基因片段，替换要变异的基因片段，产生新个体； 步骤7 计算新个体的适应度值，依据适应度值判断保留新个体还是原个体。循环迭代，返回步骤3，当迭代次数达到最大结束算法；
步骤8 输出最优解，画出路线图。
3 仿真试验及分析
为了验证该算法的正确性和有效性，选用30个城市的benchmark实例进行仿真实验。
3.1 实验测试环境与参数设置
实验测试环境为：操作系统Windows 7，处理器为Intel（R） Core（TM）i3-2350，CPU@2.30GHz，内存6GB，编程軟件MATLAB R2010a。种群设置为100，对于算例Oliver30最大迭代次数设置为200，交叉概率pc=0.8，变异概率pm=0.4。
3.2 试验结果及分析
通过遗传算法对30个城市的benchmark实例进行20次测试得到其最优解，数据结果如表1所示。表1列举了该算法20次独立运行结果，最优值表示20次独立运行中最好结果，最差值表示20次独立运行中最差结果，平均值表示20次独立运行结果的平均值，已知最优值表示目前TSPLB标准库收录的最优结果。
表1 TSP测试结果
■
由表1试验结果可以看出，该算法在求解TSP中有较好的效果，20次独立运行结果中最好值423.949与标准数据库中最好值423.7406相差0.2084，误差结果在可以接受的范围，平均值424.4247与最优值423.949相差0.4757，表明该算法对求解TSP具有较高的稳定性。
图2中给出了算法迭代200次的部分路线图，分别是第50、第100和第200代结果，由图可以看出，算法在运行至第100次时，结果430.8781已经接近最优值，表明算法有较强的收敛能力，第200次结果423.949非常接近已知最优值，表明了算法具有较强的全局搜索能力。图3给出了该算法是以宁都值变化图，也可直观地看出该算法具有较强的收敛性能。
【参考文献】
【1】Karp R.M. Reducibility Among Combinatorial Problems. Plenum Press. 1972：85-103.
【2】Zalilah Abd Aziz. Ant Colony Hyper-heuristics for Travelling Salesman[J]. Procedia Computer Science.2015，76：534-538.
【3】何湘竹.一种改进的基于教与学的优化算法求解旅行商问题[J].中南民族大学学报（自然科学版）.2015，34（4）：89-93.
【4】段艳明，肖辉辉.求解TSP问题的改进果蝇优化算法[J].计算机工程与应用，2016，52（6）：144-149.
【5】Park T，Ryu K R. A dual population genetic algorithm with evolving diversity[C]. IEEE Congress on Evolutionary Computation. 2007： 3516-3522.
【6】黄江波，付志红.基于自适应遗传算法函数优化与仿真[J].计算机仿真，2011，28（5）：237-240.
【7】巩敦卫，孙晓燕.变搜索区域多种群遗传算法[J].控制理论与应.2006，23（2）：256-260.
【8】徐晓艳.基于聚类思想的改进混合遗传算法[D].北京：北京工业大学计算机学院，2013.
【Abstract】In this paper， an improved genetic algorithm for traveling salesman problem （TSP） is proposed.The algorithm combines the characteristics of TSP， using real number encoding to reduce the computational complexity of the algorithm， a cross way to expand the search space and improve searching ability， roulette selection strategy to accelerate the convergence of the algorithm.In this paper， it has simulated benchmark examples in thirty cities.The simulation results show that the improved genetic algorithm can improve the global search ability， and its convergence speed and the convergence precision is higher.
【关键词】旅行商问题；遗传算法；收敛速度
【Keywords】traveler problem；genetic algorithm；convergence precision
【中图分类号】TP18 【文献标志码】A 【文章编号】1673-1069（2017）03-0096-03
1 引言
旅行商问题（TSP）也称货郎担问题，它旨在寻求旅行商在遍历诸多城市一次最后回到起点城市的最短路径，是数学图论中的经典问题。在实际生活中，像物流路径优化、车间调度和网络路由选址等都可归结为TSP，因此，TSP的研究具有重要的理论意义和实际价值。
Karp[1]证明了TSP是一个NP难问题，传统的优化算法在求解TSP问题时往往会陷入局部最优，尤其随着城市数量的增加，计算量也急剧增加，致使很多算法瘫痪。因此智能优化算法强的搜索效率、快速的收敛速度在求解TSP中得到了广泛应用。Aziz[2]提出了广义的蚁群算法，算法中融合了局部和全局两种信息素更新机制，提高全局迅游能力。何湘竹[3]将混沌搜索机制融入基于教与学的优化算法求解TSP，通过benchmark实例仿真试验显示，新算法性能更优越。段艳明[4]将果蝇优化算法的连续空间对应到离散规划，利用了遗传算法的交叉、变异操作进行路径的寻优，加快局部搜索能力和收敛速度。
遗传算法是一种模拟生物进化过程的随机搜索优化方法，与其他的局部搜索算法相比，遗传算法具有更强的鲁棒性，隐形的并行搜索机制增强了算法寻优能力，但遗传算法也存在缺陷，例如： 种群常常会出现早熟收敛、易陷入局部最优的问题，使算法的搜索性能大大降低[5]。针对这些问题，学者提出了许多解决方法，如参数控制、多种群的运用和交配限制[6-8]等。
2 求解TSP的改进遗传算法
鉴于目前遗传算法在优化领域的优越性能，论文以TSP为例，提出了改进的遗传算法。
2.1 实数编码
对包含n个城市的TSP问题，我们提出一种新的有效编码方法——实数编码。它是指整数1到的一个全排列所构成的实数序列a1，a2，…，an，其中a∈[1，n）之间的整数，编码中ai表示编号为的城市排在路径上的第ai个位置。
2.2 轮盘赌选择
轮盘赌选择法是遗传算法中常用的选择方式，首先计算每个个体的适应度值fi，i∈[1，ps），ps为种群规模。这里fi的值越大，说明这个个体越优秀；其次，计算每个个体的选择概率pi=fi/（∑fi）和累积概率Pi=∑■■pi；最后，随机产生一个实数num∈[0，1]，选取满足num
交叉算子是遗传算法中关键的操作，它涉及种群的多样性和算法的搜索效率等，论文基于等位交叉来改变两个交叉个体的局部基因片段，使每個个体都能遗传到对方的基因。具体操作如图1所示。
■
图1 等位交叉具体操作图
2.4 改进的遗传算法
基于以上操作算子，求解 TSP的改进遗传算法步骤如下：
步骤1 初始化遗传算法种群个数ps、最大迭代次数inmax、交叉概率pc和变异概率pm等；
步骤2 根据各城市的坐标计算各个城市之间的距离，记作Cij，i，j∈[1，n]，代表第i个城市到第j个城市的距离，初始生成ps个个体，即ps个城市路线；
步骤3 计算每条路线的距离Si，计算适应度值根据公式fi=1/Si，计算选择概率pi=fi/（∑fi）和累积概率Pi=∑■■pi；
步骤4 根据选择概率和累积概率采用轮盘赌选择法选择要交叉的两个个体；
步骤5 根据交叉概率判断是否交叉，交叉采用等位交叉法，产生两个等位基因互换的两个交叉个体；
步骤6 根据变异概率判断是否变异，选择变异基因位置，随机产生基因片段，替换要变异的基因片段，产生新个体； 步骤7 计算新个体的适应度值，依据适应度值判断保留新个体还是原个体。循环迭代，返回步骤3，当迭代次数达到最大结束算法；
步骤8 输出最优解，画出路线图。
3 仿真试验及分析
为了验证该算法的正确性和有效性，选用30个城市的benchmark实例进行仿真实验。
3.1 实验测试环境与参数设置
实验测试环境为：操作系统Windows 7，处理器为Intel（R） Core（TM）i3-2350，CPU@2.30GHz，内存6GB，编程軟件MATLAB R2010a。种群设置为100，对于算例Oliver30最大迭代次数设置为200，交叉概率pc=0.8，变异概率pm=0.4。
3.2 试验结果及分析
通过遗传算法对30个城市的benchmark实例进行20次测试得到其最优解，数据结果如表1所示。表1列举了该算法20次独立运行结果，最优值表示20次独立运行中最好结果，最差值表示20次独立运行中最差结果，平均值表示20次独立运行结果的平均值，已知最优值表示目前TSPLB标准库收录的最优结果。
表1 TSP测试结果
■
由表1试验结果可以看出，该算法在求解TSP中有较好的效果，20次独立运行结果中最好值423.949与标准数据库中最好值423.7406相差0.2084，误差结果在可以接受的范围，平均值424.4247与最优值423.949相差0.4757，表明该算法对求解TSP具有较高的稳定性。
图2中给出了算法迭代200次的部分路线图，分别是第50、第100和第200代结果，由图可以看出，算法在运行至第100次时，结果430.8781已经接近最优值，表明算法有较强的收敛能力，第200次结果423.949非常接近已知最优值，表明了算法具有较强的全局搜索能力。图3给出了该算法是以宁都值变化图，也可直观地看出该算法具有较强的收敛性能。
【参考文献】
【1】Karp R.M. Reducibility Among Combinatorial Problems. Plenum Press. 1972：85-103.
【2】Zalilah Abd Aziz. Ant Colony Hyper-heuristics for Travelling Salesman[J]. Procedia Computer Science.2015，76：534-538.
【3】何湘竹.一种改进的基于教与学的优化算法求解旅行商问题[J].中南民族大学学报（自然科学版）.2015，34（4）：89-93.
【4】段艳明，肖辉辉.求解TSP问题的改进果蝇优化算法[J].计算机工程与应用，2016，52（6）：144-149.
【5】Park T，Ryu K R. A dual population genetic algorithm with evolving diversity[C]. IEEE Congress on Evolutionary Computation. 2007： 3516-3522.
【6】黄江波，付志红.基于自适应遗传算法函数优化与仿真[J].计算机仿真，2011，28（5）：237-240.
【7】巩敦卫，孙晓燕.变搜索区域多种群遗传算法[J].控制理论与应.2006，23（2）：256-260.
【8】徐晓艳.基于聚类思想的改进混合遗传算法[D].北京：北京工业大学计算机学院，2013.