求解旅行商问题的几种育种算法

求解旅行商问题的几种育种算法

tsp的求解旅行商问题（tsp：旅游采购和服务）是一个非营利问题。tsp问题是组合优化领域的典型问题。这个问题有很大的现实意义。例如，印刷板的空转方案和商店物流方案可以简化为tsp问题。并且此问题也可作为测试新的算法的标准问题,因此该问题一直是研究的热点。目前求解TSP问题的主要方法有模拟退火算法,遗传算法,启发式搜索法,Hopfield神经网络算法,蚁群算法等,各种算法各有千秋。育种算法是许必熙于2005年提出的,可解决一般优化问题,该算法以简单快速著称,本文提出用改进的育种算法来求解旅行商问题。1繁殖算法的原理1.1育种算法与模拟退火算法的比较育种算法是从遗传算法演变而来的,遗传算法容易陷入局部最优,搜索时间较长,需要经过复制、交叉和变异三个操作。遗传算法依靠大量复制优秀个体,以优秀个体数量来保证优秀特性遗传到下一代,但会出现近亲繁殖、内耗等问题,使新生优秀个体被压制甚至埋没等可能。育种算法将从工作机理上对遗传算法进行改进,取消遗传算法的复制和交叉操作,只进行变异操作,类似于生物的转基因育种的方法和过程,从群体当中挑选出品质最优秀的个体作为种子,并在该种子的基础上进行随机变异,变异出若干个,再从中挑选出品质最优秀的个体作为种子,再进行变异,以此类推,直至种子适应值满足要求或达到最大迭代次数。换句话说,育种算法与培养优良品种的方法类似,即选种→繁殖→再选种→再繁殖→……。由于算法具有随机性,不能保证最好解在最后一代中出现,因此迭代中需要记录最好的路径。以求解旅行商问题来说明育种算法,其算法如下:1)随机产生个路径以及计算各路径长度;While(小于最大迭代次数N)do2)从m个路径中找最短的路径长度的为种子路径C0;3)记录目前最好的路径C*;4)在C0的邻域内随机变异m个路径,并计算各路径长度;End5)输出最好的路径C*。从算法的流程看,与遗传算法比较,育种算法简单,只进行变异操作,计算时间明显减少。育种算法依靠随机变异操作的概率分布特性使得大多数新生个体能够继承种子的特性,又有少数个体产生巨大变化,这样既保留了前面搜索的成果,又保证了个体的多样性,避免陷入局部最优。育种算法与模拟退火算法也明显区别,模拟退火算法是基于物理中固体物质的退火过程与一般优化问题的相似性。模拟退火算法的基本思想是从一给定解开始的,从邻域中随机产生另一个解(此操作可以看作局部变异操作),接受准则允许目标函数在有限范围内变坏,它由一控制参数决定,其作用类似于物理过程中的温度,对于控制参数的每一取值,算法持续进行“产生新解-判断-接受或舍弃”的迭代过程,对应着固体在某一恒定温度下趋于热平衡的过程。解TSP问题的模拟退火算法的框架:1)给定起、止“温度”T、T0和退火速度α,初始一条路径C0;While(T>T0)do2)在C0的邻域内产生另一条路径C1;3)计算两条路径所引起的目标函数(能量)值的变化ΔE;4)若ΔE≤0,接受新值,否则若exp(-ΔE/T)>rand(0,1)(rand(0,1)表示0～1之间的随机数),也接受新值,否则就拒绝;5)确定新的参数值,若扰动被接受,则C0←C1,否则C0不变;6)若接受新值,降温T←αT,否则不降温;End从模拟退火算法可以看出,模拟退火算法计算过程始终由一个解变异一个在迭代,而育种算法由一个种子变异若干个解,从中挑最好作为种子再进行变异,很明显,育种算法比模拟退火算法简单。1.2城市2.4.2回归系统的b3:k93第7次访问的城市育种算法中由路径C0变异产生另一条路径C1,常用的有以下4种策略,这里假设有n个城市。策略A在第1～n个访问的城市中随机地选取第j1次和第j2次访问的城市,在路径C0中交换第j1次和第j2次访问的城市,其余不变,此时的路径为C1。比如C0=234157986,j1=2(第2次访问的城市是城市3),j2=7(第7次访问的城市是城市9),则C1=294157386。策略B在第1～n个访问的城市中随机地选取第j1次访问的城市,在路径C0中交换第j1次和第j1+1次访问的城市,其余不变,此时的路径为C1。比如C0=234157986,j1=2,则C1=243157986。策略C在第1～n个访问的城市中随机地选取第j1次和第j2次访问的城市,假设j1<j2,在路径C0中将第j1次访问的城市安排到第j2次访问的城市之后,其余不变,此时的路径为C1。比如C0=234157986,j1=2,j2=7,则C1=241579386。策略D也称逆转策略,在第1～n个访问的城市中随机地选取第j1次和第j2次访问的城市,在路径C0中第j1次到第j2次访问的城市之间的子路径以反方向插入,其余不变,此时的路径为C1。比如C0=234157986,j1=2,j2=7,则C1=297514386。2基本地下空间遗传参数和策略以解决中国31个直辖市和省会城市的CTSP问题与基本蚁群算法、基本遗传算法、模拟退火算法进行比较,数据来源于文献。育种算法的参数如下:m=3,N=1000;模拟退火算法的起始温度T=100000,终止温度T0=1,退火速度α=0.99,在C0的邻域内产生另一条路径C1,也采取A、B、C和D四个策略。遗传算法程序采用MATLAB的遗传算法工具箱,参数如下:染色体个数N=30率,交叉概率Pc=0.2,变异概率Pm=0.5,迭代次数100;各种策略各随机测试50次,结果如表1所示。从表1看出,育种算法比基本蚁群算法、基本遗传算法和模拟退火算法性能好,特别策略D效果最好,并且速度比较快。育种算法策略D的最好的结果如图1所示,总路程为15383km,横坐标x和纵坐标y表示各城市的相对坐标,其路径为:北京—沈阳—长春—哈尔滨—呼和浩特—银川—兰州—西宁—乌鲁木齐—拉萨—成都—昆明—贵阳—南宁—海口—广州—长沙—武汉—南昌—福州—台北—杭州—上海—南京—合肥—郑州—西安—太原—石家庄—济南—天津。图2显示了迭代过程,纵坐标表示每次迭代种子的路径长度之和S,横坐标表示迭代次数N。从图2可以看出,前100次左右的迭代,目标函数值迅速下降,以后的迭代种子的目标值趋于稳定。3种子变异、繁殖基本育种算法是从种群中选择最好的一个个体作为种子,然后进行变异,因此变异的多样性稍差点。改进的思路,选择若干个比较好的个体作为种子,而非一个种子,比如选择βm(βm不为整数时取整)个比较好的个体作为种子,这里β(1/m≤β≤1)为选择系数,然后对每个种子变异1/β个,这样变异后的总数仍为m,接着再选种、繁殖等操作。求解旅行商问题的改进育种算法如下。1)随机产生m个路径以及各计算路径长度;While(小于最大迭代次数N)do2)从m个路径中选择路径长度较短βm的个个体为种子群;3)记录目前最好的路径C*;4)在各个种子的邻域内随机变异1/β个路径,并计算各路径长度;End5)输出最好的路径C*。从算法可以看出,基本育种算法实际是β=1/m时的特例。同样对于CTSP问题,β分别取0.1,0.2和0.25时,运行50次结果如表2所示。与表1比较,可以看出改进的育种算法比基本育种算法效果好。β取不同时效果也不一样,β=0.2时效果比较好,β太小多样性偏少,β太大多样性太大,没有达到优选种子的目的,因此β应取适中。4混合智能算法本文讨论了求解TSP问题育种算法的4种策略,推荐采用策略D,并提出了改进的育种算