硅谷杂志：基于TSP的改进差分进化算法 |
| 2012-11-11 11:34 作者：朱宇航 伏 楠 来源：硅谷网 HV： 编辑： 【搜索试试】
|
|
[硅谷网11月11日文] 据《硅谷》杂志2012年第17期刊文称，针对TSP问题，提出一种改进的差分进化算法：利用贪心算法产生初始种群,定义特有的编码匹配函数进行变异操作，排序法修复变异个体，并采用顺序交叉，在变异操作之后，加入新的选择机制，防止交叉操作破坏变异出的优良个体，实验结果表明改进后的差分进化算法能够高效地解决TSP问题，体现良好的优化性能。
0引言
差分进化算法（DE：DifferentialEvolution）是一种模拟自然进化法则的仿生智能计算方法，在解决复杂的全局优化问题方面，DE的性能更加优秀，过程也更为简单，受控参数少[1]，但由于DE特有的差分操作的限制，DE被成功应用的领域多集中在连续优化领域，在离散优化领域的应用还相对较少[2]。
TSP（旅行商问题）作为典型的离散优化问题，是解决很多实际问题的最终转化形式，同时也是著名的NP难题，在短时间内求出其最优解非常困难，现有解法[3-4]在求解中都各有缺点.因此，研究将DE经过必要的改进后应用于TSP的求解具有重要意义。
1改进DE算法
1.1编码及匹配函数
编码方式采用简单直观的顺序编码，由于TSP行走路径为回路，同一路径可有多种编码。如（1234）和（2341）为相同回路，影响变异操作的进行。为此，提出了一种匹配函数P（x，y）。
设某k个城市的TSP问题任意两个解为：x=（x1x2…xk）和y=（y1y2…yk）。
定义1：同一路径的所有的编码组成的集合称为ALL集合，记为ALL（x）。当x=（123）时，ALL（x）={（123），（231），（312）}。
定义2：为了消除同一路径多种编码带来的问题，找出两个路径编码之间真正的不同之处，以编码y为参照，在编码x的集合ALL（x）中，求匹配于编码y的编码P（x，y）=xTemp，满足条件：
当x=（23451），y=（12345）时，对x求P（x，y）=（12345）=y，即：消除了同一路径存在的多编码。
当x=（32451），y=（12345）时，P（x，y）=（13245），进行差分操作（x-y）时，相比于直接按位相减所得的（2011-4），P（x，y）-y=（01-100）才能真正反映出编码x与y的不同。
适应度定义为：负的路径长度，使得路径长度越短，适应度值越大。
1.2贪婪初始化
为提高初始种群的质量，采用贪婪的初始化方法.对于初始种群的每个个体，产生方法如下：
step1：初始化待走城市列表List为包含所有城市的列表；
step2：随机选择一个城市A作为起点，并将此点作为当前城市T，从List中移除；
step3：从List中选择距离城市T最近的城市作为新的当前城市T，并将T从List中移除；
step4：判断List是否为空，若是，则结束；若否，则转step3。
1.3变异及合法化
新的变异操作定义如下：
其中，i=1，2，…，NP，，是在父代种群中随机选择的三个不同个体，并且；F是一个[0，2]的常量因子，称为放缩因子。
当采用公式（1）时，xr1=（12345），xr2=（23514），xr3=（52431），设F=1时，按新变异操作得：vi=（02265），此时vi存在相同位和超值位等非法编码位，需要合法化处理。
合法化处理方法：将编码vi从小到大排序，然后使用其序号代替原编码值，比如：vi=（02265），排序后为：（02256），即：位值0的序号为1，依次类推，进行合法化处理后的编码为（12354）。
1.4贪婪顺序交叉
设交叉概率为cross，产生的随机数为rand.当rand＜cross时，不发生交叉，直接进入选择操作；当rand≥cross时，进行顺序交叉。
由于每次顺序交叉会产生两个交叉个体，而DE交叉操作中只需要一个交叉个体，因此，为了提高收敛速度，在原顺序交叉基础上，改进算法贪婪选择适应度优的个体作为返回的交叉个体。
1.5选择操作及流程的改进
为了防止交叉操作消除或者影响变异操作产生的寻优效果，改进算法在保留原有交叉操作之后的贪婪选择机制之外，增加了变异操作之后的选择机制：若变异个体的适应度优于原个体，则直接跳过交叉操作，选择变异个体进入下一代种群；否则，在变异的基础上进一步进行交叉操作。
2实验
为了证明改进算法的有效性，选用国际TSP标准测试库TSPLIB[5]的实例：eil51.tsp进行改进算法的测试实验，并与遗传算法[4]进行了对比。
设置遗传算法和差分进化算法共有的参数：种群规模为200，最大迭代次数为1000，差分进化算法的交叉概率为0.5，放缩因子为1。
将改进DE算法和遗传算法同时运行10次：改进DE算法最优解的平均值为439.3，明显优于遗传算法的最优解的平均值464.8。
图1改进DE求解结果示意图
图2最短路径长度进化过程对比
图1为改进DE算法的一次求解结果，其最短路径长度为431.1705，图2为改进DE算法与遗传算法求解最短路径长度的进化过程对比：改进算法与遗传算法在求解过程的初期相差不大，均能通过迭代使最短路径长度不断缩短。在进化的中后期，遗传算法的进化基本陷入停滞，而改进算法能够不断寻优，找到更加优秀的解，证明了改进算法相比遗传算法，优化性能更加优异。
3结束语
提出了一种将差分进化算法应用于TSP问题的新的改进方法，实验证明了改进算法针对TSP问题能够迅速得到最优解或近似最优解。
参考文献：
[1]段海滨、张祥银、徐春芳，仿生智能计算Bio-inspiredComputing[M].北京：科学出版社，2011：107-127.
[2]刘波、王凌、金以慧，差分进化算法研究进展[J].控制与决策，2007，22（7）：721-729.
[3]黄岚等，粒子群优化算法求解旅行商问题[J].吉林大学学报：理学版，2003，41（4）：477-480.
[4]李明海、邢桂华，用MATLAB实现中国旅行商问题的求解[J].微计算机应用，2004，25（2）：208-222.
[5]TSPLIB.http://www2.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.2011.12.
作者简介：
朱宇航（1986-），男，陕西武功人，硕士研究生，研究方向：智能优化算法、云计算。
|
|
|
|
【对“硅谷杂志：基于TSP的改进差分进化算法”发布评论】 |
版权及免责声明：
① 本网站部分投稿来源于“网友”，涉及投资、理财、消费等内容，请亲们反复甄别，切勿轻信。本网站部分由赞助商提供的内容属于【广告】性质，仅供阅读，不构成具体实施建议，请谨慎对待。据此操作，风险自担。
② 内容来源注明“硅谷网”及其相关称谓的文字、图片和音视频，版权均属本网站所有，任何媒体、网站或个人需经本网站许可方可复制或转载，并在使用时必须注明来源【硅谷网】或对应来源，违者本网站将依法追究责任。
③ 注明来源为各大报纸、杂志、网站及其他媒体的文章，文章原作者享有著作权，本网站转载其他媒体稿件是为传播更多的信息，并不代表赞同其观点和对其真实性负责，本网站不承担此类稿件侵权行为的连带责任。
④ 本网站不对非自身发布内容的真实性、合法性、准确性作担保。若硅谷网因为自身和转载内容，涉及到侵权、违法等问题，请有关单位或个人速与本网站取得联系（联系电话：01057255600），我们将第一时间核实处理。
|
|
|
|
