遗传算法求解TSP（通用8篇）
遗传算法求解TSP 篇1
旅行商问题 ( traveling salesman problem, TSP) 又称为旅行推销员问题、货郎担问题, 是最著名的NP完全问题。TSP并不仅仅是旅行商问题, 且涉足众多领域, 应用十分广泛, 如邮路问题、基因组图谱绘制问题和产品的生产安排问题等, 因此TSP的有效求解具有重要的意义。
目前, 人工智能发展迅速, 出现了许多独立于问题的智能优化算法。文献[1]讨论了蚁群算法、遗传算法、模拟退火算法、禁忌搜索算法、粒子群优化算法等求解TSP的优缺点及研究进程; 文献[2]利用贪心策略指导遗传操作, 提出了贪心遗传算法, 保证算法的有效性; 文献[3]将单亲遗传算法与模拟退火算法相结合, 提高全局寻优能力。
本文对基本遗传算法 ( Simple Genetic Algorithm, SGA) 求解TSP问题进行改进, 实验结果表明, 改进后的遗传算法具有较高的精确性且收敛速度快。
1 基本问题描述
1. 1 TSP问题描述
TSP可描述为: 已知n个城市以及他们相互之间的距离, 求出某一旅行商经过所有城市并回到出发点的最短路线[4]。简言之, 就是搜索自然子集X = { 1, 2, …, n} ( X的元素对n个城市的编号) 的一个排列 π ( X) = { V1, V2, …, Vn} , 使
取最小值, 其中d ( Vi, Vi + 1) 表示城市Vi到城市Vi + 1的距离。
1. 2 遗传算法描述
遗传算法 ( genetic algorithm, GA) 灵感来源于John Holland《自然系统与人工系统中的适应性》, 其实质是模拟自然界的进化过程, 将自然界适者生存规则与种群内部染色体的随机信息交换机制相结合, 是高度并行、随机、自适应的全局寻优搜索算法[5], 具有很强的鲁棒性和全局搜索能力, 易于其他算法相结合。目前, 遗传算法已被广泛应用于组合优化、机器学习、自适应控制等领域, 并取得了良好的成果。
1. 3 基本遗传算法求解TSP步骤
SGA是把问题参数编码为染色体, 利用迭代方式进行选择、交叉、变异等操作逐步交换染色体信息, 不断得到更优的群体, 同时以全局并行搜索方式搜索优化群体中的最优个体, 求得满足要求的最优解。其求解TSP基本步骤为:
1) 确定编码机制, 初始化种群, 解决TSP问题时通常采用整数编码, 及使用城市序号编码, 例如, 1 |3 |5 |4 |2 代表对于5 个城市TSP问题的一个合法染色体。初始化种群采用随机法生成目标种群。
2) 计算适应度值, 设n个城市的一个合法染色体为k1|k2| … | ki| kn, 则该个体的适应度值为:
其中Dkikj为城市ki到kj的距离。
即此适应度函数为旅行者按照规定的路线走完所有路程的距离的倒数。优化的目标是所走路程距离最短, 即该适应度函数越大, 所选染色体越优质, 反之越劣质。
3) 选择操作, 使用比例选择算子, 利用比例于各个个体适应度的概率决定子代是否被选择。即, 其中, fi为个体i的适应度值, Pi为个体i被选择的概率。选择概率给定后, 产生[0, 1]之间的均匀随机数决定哪个个体被选择。
4) 交叉操作, 使用单点交叉算子, 任选两个体作为交叉对象, 随机产生一个交叉点, 两个体在交叉点互换交叉对象, 采用部分映射消除冲突数字, 交叉概率为Pc。
5) 变异操作, 变异策略为随机选取两个点, 互换位置。变异概率Pm同生物界一样, 一般取值较小。
6) 迭代终止, 循环进行选择、交叉、变异操作, 若满足最大遗传代数则遗传终止, 得出最优解。
SGA在进化前期收敛速度快, 但当达到最优解的90%时, 进化停滞, 无法跳出局部最优, 容易出现早熟收敛现象。为了提高搜索能力, 克服早熟收敛, 加快收敛速度, 需要对算法进行改进。
2 改进遗传算法
2. 1 最近插入法产生初始种群
GA涉及的染色体大都来源于初始种群, 种群个体的质量影响全局性能, SGA随机生成初始种群, 适应度值普遍偏低, 算法效率低。本文采用最近插入法产生初始种群, 使种群个体在初始时保持较高的适应度值, 提高收敛速度。最近插入法过程如下:
1) 随机选择一个城市为当前城市, 在剩余城市中选择距离当前城市最近的一个城市与之构成子路线。
2) 比较所有剩余城市到当前子路线上每一座城市的距离, 选择距离子路线某一城市相距最近的一个城市插入子路线。
3) 反复操作步骤2) , 最终将所有城市均插入子路线构成一个完整的路线, 表示此路线的一个染色体就是种群中的一个个体。
2. 2 选择操作精英保留策略
在选择操作中加入精英保留策略, 即在使用变异、交叉算子之前先选出适应度值最大的个体保存在最优解集中, 替换子代中适应度最差的个体。目的是保留最好的个体, 避免交叉、变异算子破坏其优良性, 这样使得亲代的好的个体不至于由于交叉或者变异操作而丢失, 子代种群中的最优个体永远不会比亲代最优的个体差。保证了种群的全局最优性。
2. 3 交叉、变异策略的自适应
SGA中交叉概率Pc和变异概率Pm是不变的, 导致后期搜索迟钝, 进化停滞, 自适应控制可以有效地改善后期收敛速度, 在进化过程中自适应的改变Pc、Pm的大小, 将进化过程分为渐进和突变两个不同的阶段: 渐进阶段强交叉、弱变异, 扩大整体搜索范围, 突变阶段弱交叉、强变异, 使优良基因结构得以保存, 且防止陷入局部最优, 自适应调节公式为:
式中, fi为个体i的适应度值, favg和fmax分别为当前种群所有个体的平均适应度值和最大适应度值, pc1= 0. 9, pm1= 0. 001。
2. 4 进化逆转操作
TSP的关键是码串的顺序, 交叉算子和变异算子会使子代维持种群的多样性, 但是难以继承亲代较多的优良基因, 在选择、交叉、变异之后引进进化逆转操作可以改善GA的局部搜索能力。本文的逆转算子是单方向性 ( 朝着好的进化方向) 的, 只有经逆转后, 适应度值有提高的才会保留下来, 否则逆转无效。
例如: 随机选取两个[1, 9]区间内的整数r1和r2, 确定两个断裂点, 将两断裂点内数据进行逆转, 如, r1= 3, r2= 7
5 3∣6 7 2 4∣1 9 8
逆转后为:
5 3∣4 2 7 6∣1 9 8
2. 5 遗传迭代终止规则
在SGA中, 当迭代至最大遗传代数时迭代终止, 由此得出的进化过程会由于最大遗传代数选择的不合适使进化后期进行不必要的循环迭代, 出现进化停滞。为了避免此现象, 本文提出一种新的终止规则。
本文规定, 若连续Q代内都满足条件, 其中 ε 为适当小的正数, fgmax为第g代种群内个体的最大适应度值, 为第g - 1 代种群内个体的最大适应度值。
2. 6 改进遗传算法基本流程
改进后遗传算法求解TSP流程图如图1 所示。基本流程为:
Step1: 种群初始化;
Step2: 对种群各个体进行适应度值计算, 循环进行选择、交叉、变异和进化逆转操作, 直至达到终止条件。
选择算子: 采用随机遍历抽样选择, 选择时采用随机等距的方式选择个体。
交叉算子: 采用部分映射杂交, 根据当前进化情况自适应调整交叉概率。
变异算子: 随机选取两个点, 将其对换位置。根据当前进化情况自适应调整变异概率。
3 实验结果及分析
本文采用MATLAB语言对改进遗传算法设计实现。并用TSP样本案例库TSPLIB中的部分数据进行仿真分析。实验环境为: windows 7 系统, 2G内存, Matlab R2010b平台。
分别使用改进GA和SGA对国际公认的TSPLIB实验数据仿真验证后, 得出实验结果对比如表1, 可以得出, 改进后的遗传算法相对于SGA不仅可以搜索到最优解, 而且收敛到最优解的速度也较快, 有效性高, SGA容易陷入局部最优, 如pr136。
改进的GA可以产生高性能的初始种群, 且可以在较短的代数内收敛至全局最优, 当进化停滞时, 新的终止条件可以避免算法进行无效的进化, 提高有效性, 如图2 所示。
采用改进GA对TSPLIB中部分数据进行仿真得出各数据最优路线图如图3 至图5。
4 结束语
本文对传统的遗传算法进行了改进, 使用最近插入法生成部分初始种群; 加入精英保留策略, 自适应调整交叉、变异概率, 加入了进化逆转算子; 提出了一种新的遗传终止条件。通过实验仿真显示, 改进遗传算法在搜索最优能力、有效性和收敛速度方面都有明显的提高。
摘要：针对遗传算法收敛速度慢、易陷入早熟的问题提出一种改进的遗传算法。在传统遗传算法基础上, 引入最近插入法产生高性能的初始种群;选择操作中加入精英保留策略, 保证收敛到全局最优;根据种群进化状况自适应调整交叉概率、变异概率, 克服过早收敛并加快收敛速度;在选择、交叉、变异之后加入进化逆转操作, 保留亲代较多信息, 增强搜索能力;提出一种新的遗传终止规则, 提高遗传算法的有效性。经过国际公认的TSPLIB实验数据仿真验证, 改进后的遗传算法精确性、有效性和收敛速度均有明显提高。
关键词：旅行商问题,遗传算法,最近插入法
参考文献
[1]高海昌, 冯博琴, 朱利.智能优化算法求解TSP问题[J].控制与决策, 2006, 21 (3) :241-247.
[2]魏英姿, 赵明扬, 黄雪梅, 等.求解TS问题的贪心遗传算法[J].计算机工程, 2004, 30 (19) :19-20.
[3]曹恒智, 余先川.单亲遗传模拟退火及在组合优化问题中的应用[J].北京邮电大学学报, 2008, 31 (3) :38-41.
[4]William J, Cook.Traveling Salesman:Mathematics at the Limits of Computation[M].隋春宁, 译.北京:人民邮电出版社, 2013:10.
[5]刘荷花, 崔超, 陈晶.一种改进的遗传算法求解旅行商问题[D].北京理工大学学报, 2013, 33 (4) :390-393.
遗传算法求解TSP 篇2
求解作业排序问题的通用混合遗传算法研究
车间作业排序理论是生产管理与组合优化领域的重要研究方向,由于其固有的计算复杂性(NP-Hard),一般无法利用经典方法求出最优解.本文针对一般作业排序问题,将遗传算法与启发式方法相结合,建立了一种混合算法框架,利用遗传算法改进启发式方法的求解性能,同时利用启发式方法引导遗传搜索过程,以提高其搜索效率.通过对完工时间与平均延误时间等不同优化目标的计算分析与比较表明,该方法对不同类型的.排序问题均具有相当满意的求解效果.
作 者：周泓 姬彬 作者单位：北京航空航天大学经济管理学院,刊 名：系统工程理论与实践 ISTIC EI PKU英文刊名：SYSTEMS ENGINEERING――THEORY & PRACTICE年，卷(期)：200121(12)分类号：O223 C931.1关键词：作业排序 遗传算法 启发式
改进的遗传算法求解TSP 篇3
本文采用2-Opt局部搜索算法对标准遗传算法进行了改进。另外，在运算过程中利用不同程度的精英复制有效保留了优秀基因，同时也维持后代种群的个体数量不变。为了保证交叉后产生新个体编码的有效性，引入了改进的OX交叉算法。还提出了一种新的变异算法，随机产生变异基因的位置，算法简单，运算量小，可通过改变变异次数调整运算结果。通过调整变异率、变异次数和交叉率、交叉节点等参数，得到了较好的试验结果。
1 改进的遗传算法
1.1 2-Opt算法
2-Opt算法是一种局部启发式搜索算法，其原理示意图如图1所示。算法的实质是将节点a2与a3之间的城市码逆序排列，得到新的路径。
考虑路径p1:
其中1 2 3 4 5 6 7 8为城市编码，p1表示这些编码按顺序联接形成的路径。
可见，2-Opt算法与节点a1与a2的选择无关，改变a2与a3的位置，会得到不同精度和收敛速度的结果。
2-Opt操作后，得到的路径:
1.2 选择和复制
采用式(1)求个体的期待值:
由于个体被选择(复制)的次数ni将由期待值vi四舍五入得到。种群进行选择操作之后个体的数量将会由所变化。常会发现进行选择后的种群个体数量远远小于初始种群。在选择后进行合理的精英复制可以解决这个问题。将最优个体进行一定数量的复制，加入经选择后个体数目减少的种群中，一方面可以保留最优个体，另一方面可以保证种群数量的稳定。
1.3 变异
随机产生两个整数，作为变异城市码的位置。将这两个位置的城市码交换，即得到变异后的新个体。传统的变异方法容易产生重复路径，或不能保证每个城市只经过一次，导致算法得出不符合要求的结果。改进后的算法可以避免这个问题。同时适当调整种群变异率和个体的变异次数会有效地改善结果。
1.4 交叉
改进的OX顺序交叉。这种交叉操作能避免重复路径的产生，保留排列并融合不同排列的有序结构单元。两个父个体交叉时，通过选择父个体1的一部分，保存父个体2中城市码的相对顺序生成子个体。为了减小问题的复杂程度，利用最常见的一点交叉方法。
以下面两个个体为例说明交叉方法(|表示交叉点的位置):
将父体2的第一段复制到父体1之前，得到
父体1的第一段复制到父体2之前，得到
此时两个体中o1、o2中都有重复城市码，从第二段开始扫描，去掉与第一段城市码重复的编码即得到子个体。以o1为例，从第二段第一个编码1开始扫描，第二段第二个编码2与第一段第三个编码重复，去掉;第三段第一个编码4与第一段第一个编码重复，去掉;直至扫描到第三段最后一个编码。这样子个体生成为:
o1:(4 5 2 1 3 6 7 8 9);o2:(1 2 3 4 5 8 7 6 9)。
2 算法步骤
随机产生初始种群，对所有个体应用2-Opt局部搜索算法，然后进行选择、复制、交叉和变异，得到的子代种群应与父代种群个体数目相等，判断是否符合终止条件，若不符合按同样的方法继续计算，直至符合条件为止。设定终止条件为:(1)达到最大迭代次数C;(2)迭代得到结果与最优解之差小于δ。当满足条件2时算法结束;若条件2一直不能满足，达到最大迭代次数之后算法结束。
算法步骤具体如下:
(1)随机产生初始种群E，个体数为N。
(2)对所有个体应用2-Opt。
(3)求取种群E中个体的适应度，用期待值法将最优个体复制到TempE中，现在TempE中有k1个个体。
(4)取种群中E适应度最大的个体M复制(N-k1)e次，进行变异操作。并将变异后的个体复制到TempE中，现在TempE中有k2=k1+(N-k1)e个个体。
(5)将M复制N-k2次放到TempE中，现在TempE中有N个个体。对所有个体应用2-opt。
(6)对新种群TempE进行变异率为a的变异操作，保留最优个体。
(7)对种群TempE进行交叉操作，交叉点为n，交叉率为x，将TempE中个体复制到E中。
(8)求种群的目标函数值，若符合终止条件，输出最短路径;否则转(2)。
3 试验结果
以求30个城市的最短路径为例进行试验，这些城市在平面内的坐标参照文献[8]。以下各图和表展示了标准遗传算法(SGA)和改进遗传算法(IGA)求解该问题时的其中一次试验结果。
图2绘制了其中一次试验得出的贯穿所有城市的最短路径示意图，可以很明显的看出改进遗传算法的优势;图3和图4分别给出了算法开始到终止的过程中最短总路径长度和最优个体适应度的变化情况。表1给出了初始值由接近最优到逐渐趋于随机的5种情况下的实验结果比较。
由表中数据对比可知:尽管改进遗传算法较标准遗传算法复杂，单次循环时间长，但由于进化代数小，所以运行时间仍小于普通遗传算法。随着初值趋于随机的变化，两种算法的运行时间都变长，但可以看出改进遗传算法受影响程度较小。在最后一组初值下标准遗传算法已经不能在500步之内找到全局最优解，但改进遗传算法仍然取得了较好的结果。
4 结论
本文提出了一种新的变异算法，这种算法有效避免了路径重复，减小了运算量，提高了运算速度。加入了改进的OX交叉算法，在交叉中合理保留了优秀个体基因的排列顺序。把局部启发式搜索算法和标准遗传算法结合了起来，加快了算法的收敛速度，减轻了初值对结果的影响。仿真结果表明，改进的遗传算法收敛性好，受初值影响小，运算时间缩短。
参考文献
[1] Samanliogolu F,Ferrell Jr W G,Kurz M.A memetic random-key genetic algorithm for a symmetric multi-objective traveling salesman problem.Computer and Industrial Engineering,2008;55:439-449
[2]杨行峻，郑君里.人工神经网络与盲信号处理.北京，清华大学出版社，2003:162
[3] Rosen K H.离散数学及其应用.北京，机械工业出版社，2002:480
[4]高海昌，冯博琴，朱利.智能优化算法求解TSP问题．控制与决策，2006;21(3):242-247
[5]莫海芳，康力山.求解TSP的混合遗传算法.计算机工程与应用，2007;43(18):40-44
[6] Baraglia R,Hidalgo J I,Perego R.A hybrid heuristic for the traveling salesman problem.IEEE Trans on Evolutionary Computation,2001;5(5):613-622
[7]尹传忠，卜雷，蒲云，等.带回送和时间窗的车辆路径问题的模型及算法.西南交通大学学报，2006;41(3):290-295
遗传算法求解TSP 篇4
TSP问题又称为货郎担问题, 要求一个货郎要走遍n个城市, 每个城市经且只能经过一次, 最后回到始发的城市, 这条路径又称为哈密尔顿圈或哈密尔顿回路, 问题要求找到一条最短的路径。 其数学描述如下:设城市集合V={v1, v2, … , vn}, 每对城市vi, vj∈V间的距离为d (vi, vj) ∈Z+。 求经过V中任一城市正好一次的路径 (vπ (1) , vπ (2) , …, vπ (n) ) 使得
其中 (π (1) , π (2) , …, π (n) ) 是 (1, 2, …, n) 的一个置换。
TSP问题是组合优化问题中典型的NP难问题, 是许多领域内复杂工程优化问题的抽象形式, 具有较为广泛的工程应用和现实生活背景, 如飞机航线的安排、公路网络的建设、网络通信节点的设置、物流货物配送、 超市物品上架等, 所有这些实际应用问题均可以转变为TSP问题来解决。 因此, 如何有效、快速地解决TSP问题具有很高的实际应用价值。
若穷举搜索全部可能的路径, 一定能够找到最短的那条路径。 亦即, 使用穷举法能够找到最优解。 但是, TSP问题的搜索空间会随着城市数量n的增加而急剧增加, 所有可能的旅行路径的组合数是 (n-1) !/2。 当城市个数达到50 时, 就有1.5207×1064个旅行方案。 使用常规的穷举法在如此庞大的搜索空间中寻求最优解, 对于现有的计算机而言, 是不可行的。当城市个数更多时, 更加难以求得最优解, 因此, 寻找最优解变得非常困难。 自然而然地, 各种求近似解的优化算法就成了比较现实可行的解决方法。 近几十年来, 出现了很多近似算法[1], 如贪婪算法、近邻法、双最小生成树法、最近插入法、最远插入法等等。近年来, 随着人工智能的发展, 许多更为有效的智能启发式算法应用于TSP问题, 高海昌等[2]对用于求解该问题的蚁群算法、遗传算法、模拟退火算法、禁忌搜索、神经网络、粒子群优化算法、免疫算法等进行了描述。随着研究的深入, 许多改进的优化算法不断涌现, 文献[3]提出了一种快速求解旅行商问题的蚁群算法。文献[4]将蚁群算法与免疫算法相结合应用于TSP问题求解。 Marinakis等对基于概率的旅行商问题进行研究, 提出了一种混合多粒子群优化算法[5]。 文献[6]的混合遗传算法将局部寻优与广义分割交叉算子结合, 提高了算法的执行效率。 文献[7]对传统遗传算法的交叉操作进行研究, 设计了一种顺序构造交叉算子以提高解的质量。 为了提高遗传算法解决TSP问题的效率, 文献[8]将贪婪搜索算法引入遗传变异操作中, 设计出新的贪婪子路变异算子。 大量研究表明, 融入一些其它信息如近似算法、特殊组合算子、局部搜索技术等, 能够极大地改善进化算法的搜索性能[9,10], 尤其是, 将进化算法与局部搜索相结合的方法, 已经证明是很有效的策略[11,12]。这种融有局部搜索的进化算法被称为文化基因算法[13], 从文献[11-12]可以看出, 文化基因算法具有高效的搜索性能。
为更好地求解TSP问题, 本文提出了一种基于遗传算法的文化基因算法, 将2-opt作为局部搜索算子嵌入到遗传算法中, 以加快遗传算法的收敛速度、提高解的精度。遗传算法具有很好的全局搜索能力, 2-opt针对TSP问题具有较强的局部搜索特点, 所提出的文化基因算法力图在全局和局部搜索中达到平衡和融合, 使之更有效地求解TSP问题。
1 文化基因算法
文化基因算法 (Memetic Algorithm, 简称MA) , 由Moscato在1989年首先提出[13]。 Memetic一词源于道金斯 (Dawkins) 在1976 年所著《自私的基因》 (The Selfish Gene) 中提出的一个概念——Meme。 Meme也译为“拟子”、“觅母”或“文化基因”等[14], 指的是文化领域的一个信息单位, 就如遗传学中的基因单位一样。 生物的进化一般指生物通过基因的繁殖、变异, 加上自然选择, 使生物不断适应环境的变化。 类似于生物的进化, 文化的进化是通过各种Meme被复制、被模仿稍加改变, 在人与人之间传播、变化。 有利于人类的Meme通常能得到不断的传承和发展。但是, 文化进化与生物进化不同的是, 生物基因的变异一般是随机的, 只有个别适应环境的变异能促进生物的发展, 除此以外, 或者大部分的变异对于生物的进化不起作用。而文化进化总是朝着改进的方向进化, 而不是混乱无序或无进展, 如更动听的音乐、科学的发展等等。
Moscato在1989 年首先提出文化基因算法 (MA) 正是受上述文化进化思想的启发。 本质上来说, MA就是将基于群体的全局搜索进化方法与局部搜索方法相结合的一种新技术[13]。 文献[13]中将局部搜索或优化策略比喻为Meme, 把局部搜索策略与传统的进化优化方法结合起来就形成了MA。 MA开始提出时, 特指的是遗传算法 (GA) 和局部搜索策略的结合, 随着进化优化方法研究的不断发展, 基于群体的其它智能算法如粒子群、蚁群等的MA也相继被提出。
MA比遗传算法 (GA) 、蚁群 (ACO) 、 粒子群 (PSO) 等算法有更广的范畴, 代表着一类算法。 它是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体[13], 这样的结合机制使其搜索效率在某些问题领域比传统遗传算法快几个数量级, 可应用于广泛的问题领域并得到满意的结果。 很多人将文化基因算法看作混合遗传算法、遗传局部搜索或是拉马克式进化算法, 实际上, 文化基因算法提出的是一种框架、是一个概念, 在这个框架下, 采用不同的搜索策略可以构成不同的文化基因算法, 如全局搜索策略可以采用遗传算法、进化策略、进化规划等, 局部搜索策略可以采用爬山搜索、模拟退火、贪婪算法、禁忌搜索、导引式局部搜索等。目前, 为了求解各种不同类型的优化问题已经有大量的MA被提出。 2005 年文献[15]中作者对MA进行了综述, 用框架的形式描述了文化基因这一类算法。图1 描述了传统的文化基因算法的流程图。
2 求解TSP问题的文化基因算法描述
为更好地求解TSP问题, 本文提出了一种基于遗传算法的文化基因算法, 将2-opt作为局部搜索算子嵌入到遗传算法中, 以加快遗传算法的收敛速度和提高解的质量。 遗传算法具有较强的全局搜索能力, 2-opt针对TSP问题具有很好的局部搜索效果, 所提出的文化基因算法试图在全局搜索和局部探索中达到均衡和融合, 使之能更有效率地解决TSP问题。
2.1 2-opt局部搜索
2-opt局部搜索是一种有效的局部搜索技术, 被广泛应用于旅行商 (TSP) 及其它的一些组合优化问题, 而且有研究表明2-opt局部搜索对求解旅行商问题十分有效。 2-opt局部搜索的主要意图是消除回路中所有相交的边, 因为相交的边基本上不是最优的。 主要计算过程是, 依次在哈密尔顿回路中选两条不相邻的边, 进行判断, 若这两条边相交, 则将这两条边从路径中移除, 再用另外两条新的边, 把移除边后得到的两条路径重新连接成为新的哈密尔顿圈, 如下图2 形象描述了这一过程。
2-opt的优化过程主要包含两步: (1) 先移除回路中一对相邻点之间的边, 得到两条互不相连的路径, (2) 将其中一条分支路径进行反转, 重新与另一条分支路径连接, 形成新的哈密尔顿圈 (回路) 。 反转操作可记为Turn, 对路径V中第i个点到第j个点之间的路径的反转操作记为Turn (V, i, j) 。
假设V= (v1, …, vi, vi+1, … , vj, vj+1, vn, v1) , 则Turn (V, i, j) = (v1, … , vi, vj, vj-1, … , vi+1, vj+1, vn, v1) , 当满足条件d (vi, vi+1) +d (vj, vj+1) >d (vi, vj) +d (vi+1, vj+1) , j≥i+2 时, 才会进行上述反转优化操作, 如图3 所示。
2-opt局部搜索算法的伪代码如下图所示:
2.2 算法主体设计
遗传算法是一种基于自然选择和基因遗传学原理的一种寻求全局最优解而不需要任何初始化信息的高效优化方法。它将问题的解集看作一个种群, 通过不断地选择、交叉、变异等遗传操作, 使解的质量越来越好。该算法具有全局寻优能力、适应性强、解决非线性问题具有较强的鲁棒性、对问题没有特定限制、计算过程简单、易于与其他算法结合等特点, 在函数优化、图像处理、自动控制、经济预测和工程优化等领域得到了广泛的应用, 在求解NP完全问题方面也是一种较为有效的全局方法。
针对TSP问题, 本文提出的文化基因算法, 在算法主体上采用遗传算法进行全局搜索, 在进化的过程中, 采用2-opt技术进行局部调整以加快算法的收敛速度和提高解的精度。 算法求解TSP问题的主要计算过程如下:
Step 1: 确定编码机制, 生成初始种群Vi (i=1, … , popsize) , popsize为种群的规模。 解决TSP问题通常采用城市序号对路径进行编码, 按照访问城市的顺序排列组成编码。
Step 2: 计算种群中每个个体的适应度值。 TSP求解是要寻找使目标函数最小的个体, 因此选择适应度函数。可以看出, 巡游路径越小, 适应度值越大。
Step 3: 选择算子。 算法采用最常用的轮盘赌选择策略, 适应度较高的个体具有较大被选择的机会。 计算每个个体被选择的概率为。 在轮盘赌选择的基础上, 算法也考虑到了精英个体的保留。 在对种群进行轮盘赌选择结束后, 算法会检查新生成的种群中是否包含有父代的精英个体, 若不包含, 则将新生成的子代种群中最差的个体替换为父代的精英个体。
Step 4: 交叉算子。 由交叉概率pc选择父体并进行配对, 按照交叉算法的规则生成新个体。 算法中采用单点顺序交叉法 (OSPX) 。 设两父代个体为V1, V2。随机选择一个交叉点, 定义交叉点后面的元素为拟匹配区域。 设V1, V2及交叉点表示为:
采用单点顺序交叉, 首先将V1和V2的拟匹配区域进行复制, 分别加到V2和V1的前面, 可得到
然后分别从复制的匹配区域后依次删除与前面匹配的相同的码, 最后可得到:
Step 5: 变异算子。 为了保持种群个体的多样性, 防止陷入局部最优, 本算法采用基本位变异, 以pm的变异概率对每个个体执行变异操作。随机选择个体的两个基因位, 将两个位上的码进行反转操作。设个体及随机选择的两个基因位为, 执行基本位变异操作, 执行完成后个体转换为:V1=[10 1 9 2 8 5 6 7 4 3]。
Step 6: 对新生成的子代个体执行2-opt局部搜索。 局部搜索的伪代码如图4 所示。
Step 7: 迭代终止判断. 若满足预定的终止条件 (如达到最大迭代次数) , 则算法停止迭代, 所得的路径认为是满意的路径; 否则, 转Step2, 计算新一代种群中每个个体的适应度值, 将新一代种群替换为当代种群。
3 实验测试
为了测试基于遗传算法的文化基因算法在解决TSP问题方面的表现, 本文从TSP标准问题测试库中提取了10 个测试问题, 将本文提出的算法用于求解这10 个问题, 并将算法的执行结果与当前其它一些优秀的智能算法的运行结果进行了比较。
在测试过程中, 算法采用轮盘赌选择和精英个体保留机制, 单点顺序交叉, 基本位变异, 终止代数为500, 群体大小为200, 交叉概率为0.9, 变异概率为0.09。 在Matlab环境下, 算法对每个测试问题独立进行10 次。 在相同的终止迭代条件下, 表1 给出了几种算法所求得的最短路径的平均值。 以eil51、bier127、rat195、kro B200 为例, 图5 形象展示了算法在这些测试问题上独立运行10 次的结果。
从表1 和图5 可以看出, 相较于遗传算法, 本文提出的基于遗传算法的文化基因算法所求得的路径更短, 可见融入2-opt局部搜索技术对于提高算法的性能是非常有效的。 与当前其它一些优秀的算法, 包括模拟退火、粒子群算法、蚁群算法相比, 在这些测试问题上, 基于遗传算法的文化基因算法均表现了较好的性能, 所求得的结果都优于其它算法。如图5 所示, 与其它算法相比, 本文提出的算法还具有较好的稳定性, 鲁棒性较强, 对问题的敏感性较弱, 比较适合解决此类TSP问题。
4 总结
遗传算法在求解TSP问题时往往存在着求解质量不是很高、容易陷入局部最优等一系列问题。 为了克服这些缺陷, 本文提出了一种基于遗传算法的文化基因算法。 算法在求解过程中, 将2-opt作为局部搜索算子, 嵌入到遗传算法中, 以加快遗传算法的收敛速度和提高局部搜索能力。遗传算法具有全局搜索的能力, 2-opt具有局部搜索的特点, 嵌入2-opt局部搜索的遗传算法力图在全局和局部搜索中达到平衡和融合, 使之更有效地解决TSP问题。
为检测算法的性能, 将该算法在10 个标准TSP测试问题上进行了测试, 并将测试结果与标准的遗传算法及蚁群、粒子群等其它一些优秀的算法的实验结果进行了对比, 数值实验结果表明, 本文提出的算法在求解的质量、稳定性上均表现了较好的性能, 算法的整体表现要优于其它算法。 可见融入局部搜索技术的全局搜索算法对于解决TSP问题是一条有效的途径。 探索其它更高效的局部搜索算法, 将这些局部搜索技术有效地融合到遗传算法、蚁群算法中, 以更好地解决TSP问题将是作者今后进一步的研究工作。
摘要：为更好地求解旅行商问题, 本文提出了一种基于遗传算法的文化基因算法。将2-opt作为局部搜索算子, 融入到遗传算法中, 以加快遗传算法的收敛速度和提高解的局部搜索能力。遗传算法具有全局搜索的能力, 2-opt具有局部搜索的特点, 嵌入2-opt局部搜索的遗传算法力图在全局和局部搜索中达到平衡和融合, 使之更有效地解决TSP问题。为检测算法的性能, 将该算法用于解决标准的TSP测试问题, 并将测试结果与标准的遗传算法及蚁群、粒子群等其它一些优秀的算法的实验结果做了比较, 数值实验结果证明了算法的有效性。
遗传算法求解TSP 篇5
本文在分析遗传算法的基础之上求解TSP问题, 并与穷举法所得结果进行比较。表明了遗传算法在求解此问题上的优越性。针对遗传算法的不足, 结合模拟退火思想对遗传算法进行改进, 取得了理想的试验结果。
1 算法设计
TSP问题的模型是简单而易于描述的。实际应用中, 像印刷电路板工艺这样的应用可能是和模型比较接近的。但是模型中的城市之间的距离代表的是某个解的耗费, 实际中不一定是欧氏距离, 有可能点与点之间的耗费需要另外用权值给出。而且在实际中, 两个城市之间的消耗不一定是对称的, 例如乘船到另一城市和返回的费用可能是不同的。
这里对TSP问题模型进行简化, 在500×500的平面内随机生成了一些点, 用它们来代表城市。假设每个城市和其它任意一个城市之间都以欧氏距离直接相连。
1.1 遗传算法的总体框架
遗传算法的简单通用的特点, 主要是指其主要框架简单通用, 可以说是万变不离其中。其基本结构可以概括为:①初始化种群;②对种群每个个体进行评估;③选择 (竞争生存机会) ;④变化 (重组、杂交与变异) ;⑤如不满足终止条件, 转②;否则结束。
其中变化算子的设计是最重要的, 既要考虑保留种群在演化中产生的好的基因, 又不能使种群过早地局限于某个局部。其次是选择算子, 选择策略意味着什么样的个体能够存活并参与繁殖下一代。如果参与繁殖的父体都很“好”, 意味着种群里面的差异小, 则很有可能会陷入局部最优。
1.2 算法的详细设计
1.2.1 解空间的表示方式
遗传算法对解空间的表示大多采用二进制编码形式, 但是二进制编码方式不适合TSP问题的解的表示, 因为它要求特殊的修补算子来修复变化算子所产生的非法路径 (即不可行路径) 。给出城市编号, 用十进制数编码来表示解更合适, 例如:近邻表示、次序表示和路径表示等等。
这里采用了最简单的路径表示法。它是最自然、最接近人类思维的表示法。例如, 有6个城市的TSP问题, 可将6个城市从1～6编号, 下面的路径 (闭合的) :
5→1→2→4→3→6→5
表示从城市5出发, 经过1, 2, 4, 3, 6最后回到城市5的一条路径, 可以自然地用一维数组来表示:
(5, 1, 2, 4, 3, 6)
相应地, 50个城市的TSP问题, 如果种群规模为500, 解空间就用二维数组来表示:path[500][50]。
1.2.2 种群初始化
种群的规模选择应适当, 盲目的增大种群规模不能使算法得到改进, 反而大大增加了计算的开销。例如, 20个城市TSP与50个城市的TSP问题, 20个城市的TSP问题可以选择小规模的种群 (例如500) , 而50个城市则要选大一些的种群 (例如3 000) 。
以20个城市为例, 说明初始化种群的方法:种群初始化时, 先产生1, 2, …, 20的一条规则路径, 然后在这条路径中随机选两个数, 将它们交换位置, 这样做若干次 (本文采用500次) , 保证这条路径变成了一条随机的路径。
以这条随机路径为基础, 对一些随机的位, 做两两交换 (做100次两两交换) , 这样产生了一个个体;同样地产生种群里其它的个体。
1.2.3 适应度函数与最优解的保存
用个体 (一条闭合路径) 的周长 (平面欧氏距离) 作为该个体的适应值。求得种群中所有个体的适应值后, 将适应值最大的个体保存起来, 到演化完毕时, 这个个体就是最后要求的解。
1.2.4 选择 (竞争) 策略
这里采用了轮盘选择策略。但是因为这是一个最小化问题, 必须对适应值做相应调整以适应这种选择策略。可以采用一个映射对适应值进行规范:
undefined
其中, F是适应度函数求出的适应值, Fmax为其中的最大值, F′是规范后的适应值。然后, 用F′来构造轮盘, 概率为:
undefined
表示了某一个体被选入下一代的概率。对P做逐级累加存入数组P[i]:
undefined
这个P[i]正是构造好的轮盘。最后产生一个 (0, 1) 之间的随机数r模拟轮盘转动, 检查这个值落在P[i]的哪个区段, 如P[k]
1.2.5 杂交算子
杂交是希望不同的个体在产生下一代时, 能够结合各自的优势基因, 产生更好质量的下一代。在遗传算法里面, 可以用单体杂交, 双体杂交和多体杂交。但要保证种群的规模不变, 须保证n个个体杂交产生n个后代, 后代产生之后要代替其父体的位置。
常用的杂交算子有PMX、OX、CX等, 这几个算子细节见文献[1]。本试验实现了OX算子, 采用了双体杂交, 每次选两个个体杂交, 产生两个后代。
1.2.6 变异算子
变异可以看作是外界对种群的影响。变异是为了引入新的因素, 希望个体在外界的作用下, 能够自我优化, 产生好的基因。
变异算子采用了简单的倒序变换, 以8个城市为例, 随机的产生两个小于8的整数, 对某个个体进行分割, 将分割段倒序并放回原来的位置即可。
(1, 3, |4, 6, 5, 2, 8, |7)
(1, 3, |8, 2, 5, 6, 4, |7)
由于这种变异算子仍能保持个体中的路径片段, 即倒序前后这个切割段的路径是一样的, 只是两端点与整个路径的连接颠倒了, 这使得变异不是漫无边际, 而是有所取舍的。这种简单反序可以保证后代仍然是一条合法途径。
1.2.7 模拟退火的基本思想
模拟退火算法来源于固体退火原理, 将固体加温至充分高, 再让其徐徐冷却。加温时, 固体内部粒子随温升变为无序状, 内能增大, 而徐徐冷却时粒子渐趋有序, 在每个温度都达到平衡态, 最后在常温时达到基态, 内能减为最小。在遗传算法中, 引入模拟退火的思想, 在变异算子中, 让变异的父体和变异产生的后代之间竞争生存机会。在演化的前期, 种群的质量较差, 因此给变异产生的后代较多的生存机会 (从1向1/2递减) , 而随着演化向末期推进, 将他们的生存机会减到平衡状态 (各占1/2) 。
变异产生的后代的生存概率表示为:
undefined
其中, Gt是遗传算法要演化的总代数, Gc是当前演化到第几代。这样, 在初始时, Gc为0, 后代获得的生存机会为1, 类似于温度高、能量大;向后推进时, 父辈与子女的生存机会差距逐渐减小;最后趋于平衡。
1.2.8 算法的流程
引入模拟退火思想对遗传算法进行改进, 算法的流程如图1所示。
2 试验分析
所有的试验在一台奔腾4 (主频为2.4G) 的WINDOWS平台的PC机上进行, 这个算法计算量大 (耗CPU) , 但只占用较少的内存。
对于解的质量, 首先使用15个城市的TSP问题进行分析。由于20个以上城市的TSP问题用穷举法在短时间内无法求得, 因此这里选择了15个城市来做了穷举搜索的尝试。
使用穷举搜索法 (Exhaustive Search Algorithm, 简称ESA) , 15个城市的TSP问题用4m15s求得了最优解。如图2所示, 长度是875.689 149, 解路径是:0, 9, 12, 6, 1, 10, 11, 5, 3, 14, 8, 4, 13, 2, 7。
使用遗传算法来求15个城市的TSP, 在几秒钟内就可以求得结果, 而且得到最优解的概率也很大。图3为使用OX算子, 种群规模500, 演化600代, 在1s内求得和穷举法同样的最优解的情形。解的路径长度为875.689 149, 由于路径是闭合的环路, 出发点在哪里不影响解的质量, 所以这条路径和穷举搜索法求出的解是一样的。通过大量的试验观察还发现, 最优解和较好的次优解在图形上均没有交叉的情形出现。
当然, 遗传算法并不能保证在1秒钟内总能求得最优解。但是通过增加演化代数 (1 000代) 和增加种群规模 (1 000个) , 试验40次, 每次耗时6s, 40次均求得了最优解, 而且演化到300代时已经取得了最优解的情形超过90%。可见遗传算法收敛速度快, 而且能够一直向最优解逼近。
采用OX杂交算子对50个城市的TSP问题的进行测试。种群规模选择4 000, 演化代数选择了10 000。测试进行了5次, 每次耗时约10m30s, 得到的结果分别为1 709.7、1 812.9、1 744.1、1 749.3、1 766.0。从图形上看也还不是很理想, 路径中会出现一个或二个交叉, 图4所示是5次试验中最好的结果, 长度为1 709.7, 路径中有一个交叉。
使用模拟退火的思想对算法进行改进后, 在同样的条件下进行了3次试验。每次耗时仍为10m30s左右, 得到的结果分别为1 680.3、1 660.2、1 672.3。从数值上看, 得到了更优的解, 从图形表现上看, 3次试验所得路径都没有出现交叉, 质量更好。图5所示是3个结果之一。
3 结语
遗传算法的效率与变化算子和选择策略的设计有很大关系。好的杂交算子能够使后代尽可能保留父辈中的优秀的基因。而如果变异算子设计得不好, 又很容易使问题求解陷入解空间的某一局部。因此, 必须仔细考虑各个算子的设计。
只要设计出合适的算法, 对于一些常规搜索算法无法或很难求解的问题, 例如, 像TSP这样的组合优化问题, 遗传算法能够给出令人满意的次优解。遗传算法还可以和其它的智能搜索策略结合起来使用, 可以加快求解过程或优化解的质量, 本文使用模拟退火算法的思想对变异算子进行了改进, 也是这方面的一个尝试。
参考文献
[1]ZBIGNIEW MICHALEWICZ, DAVID B.FOGEL.如何求解问题——现代启发式方法[M].北京:中国水利水电出版社, 2003.
[2]朱福喜, 汤怡群, 傅建明.人工智能原理[M].武汉:武汉大学出版社, 2002.
[3]FISCHETTI M., SALAZAR J.J., TOTH P.Branch-and-cut al-gorithm for the symmetric generalized traveling salesman problem[J].Operations Research, 1997 (3) .
[4]MERZ P.A comparison of mimetic recombination operators for thetraveling salesman problem[C].Proceedings of the Genetic andEvolutionary Computation Conference (GECCO) , 2002.
[5]JUNG S, MOON BR.The nature crossover for the 2DEuclideanTSP[C].Proceedings of the Genetic and Evolutionary Computa-tion Conference (GECCO) , 2000.
[6]吴斌, 史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报, 2001 (12) .
[7]朱亨荣, 刘伟铭, 宋丹.改进遗传算法求解TSP问题[J].株洲工学院学报, 2004 (2) .
[8]王斌, 李元香, 王治.一种求解TSP问题的单亲遗传算法[J].计算机科学, 2003 (5) .
遗传算法求解TSP 篇6
关键词：Elitism策略,遗传算法,免疫遗传算法,旅行商问题,优化
旅行商问题(Traveling Salesman Problem,简称TSP)就是从n个城市中的某一城市出发，不重复地走完其余n-1个城市并回到原出发点，在所有可能的回路中求出回路长度最短的一条[1]。或者说搜寻整数子集X={1,2,…,n}(X的元素表示对n个城市的编号)的一个排列X={x1,x2,…,xn}，使得闭合路径取最小值。式中的d(xx,xj)表示城市xi到城市xj的距离。TSP问题是组合优化问题的代表，属于NP完全问题。[2]
遗传算法(Genetic Algorithm,GA)作为一种生物进化计算模型，是在1975年由Michigan大学Holland教授提出的一种启发式优化算法，具有全局并行搜索的特点，但这种算法的主要问题在于容易陷入局部最优解、早熟收敛、局部搜索能力较差及收敛速度慢等。人工免疫算法模拟了自然免疫系统的抗体繁殖策略，引入了抗体浓度调节机制，从而有效的调节了选择压力，保持了解群体的多样性，克服了遗传算法容易出现早熟收敛和陷入局部最优的缺点。但AIA存在运行速度和收敛速度都较慢的不足[3]。
针对这些问题，本文利用精英选择策略(elitism strategy)提出了一种新的改进免疫遗传算法，简称为IGAE(Immune Genetic Algorithm with Elitism)，用来求解TSP问题。IGAE有两个重要特点，其一是抗体的亲和力和期望繁殖率在进化时可以动态调整，以达到平衡群体的多样性和算法的收敛速度的目的，使算法能快速求出优质解;其二是采用了Elitism策略，可以确保算法收敛到全局最优解。与遗传算法和免疫算法进行对比，结果表明，在相同条件下，IGAE具有收敛速度快及动态收敛性好等优点。
1 改进的免疫遗传算法的设计思想
免疫遗传算法与遗传算法一样，包含选择、交叉和变异三种操作。两者不同的是，在遗传算法中，个体的品质只用适应度一个指标评价;但在免疫遗传算法中，个体(即抗体)的品质同时采用了适应度和浓度两个指标共同来评价。抗体的浓度的概念是由Fukuda首先提出来的[4]。引入浓度概念之后，和遗传算法对比，免疫遗传算法的群体更新策略有了较大改变。并且，在克隆操作时，在遗传算法中，个体的选择概率只与适应度有关;而在免疫遗传算法中，个体的选择概率则既与适应度有关，也与浓度有关。同遗传算法相比，免疫遗传算法具有更好的群体多样性保持能力，其收敛性也更好[5]。
1.1 本算法涉及的几个定义
假定有一个规模为Sp的抗体群，其中每一个抗体都可表示成一个具有n个元素的一维向量。以下给出涉及的几个定义，包括抗体的亲和力、浓度、期望繁殖率、选择概率以及抗体群多样性的指标等。
定义1.1在特定的、规模为Sp的抗体群中，任取两个抗体v和w，设抗体v和w的适应度分别为fv和fw，抗体v和w的欧氏距离记为d(v,w)，亲和力指标记为J(v,w)。假定ε是一个适当小的正常数，若有：
成立，则称抗体v与抗体w相似。式中，α>0是反映欧氏距离d(v,w)和适应度差值|fv-fw|各自在J(v,w)中相对重要性的一个参数;ε称为抗体亲和力阀值。
在这个定义中，欧氏距离用来反映两个抗体在结构上的相似性，而适应度的差值用来反映两个抗体在品质上的相似性。其中，抗体v与抗体w之间的欧氏距离定义为：
将式2代入式1，可得：
式(3)是本文给出的一种新的抗体亲和力定义方法。这样定义有两个优点：第一，将抗体相似的两个重要特征，即欧氏距离和适应度值，统一在一个公式中，使抗体亲和力的定义变得更为简洁、规范;第二，通过引入可调参数α，可对欧氏距离和适应度值两者在亲和力指标中的相对重要性进行调整，这种调整对免疫遗传算法在进化过程中同时兼顾群体的多样性和收敛速度以保证快速获得高质量的解是非常重要的。
通常情况下，在免疫遗传算法进化过程的初期和中期，为了使群体保持良好的多样性，避免算法陷入局部最优，我们希望α取较大的值;而在进化过程的后期，由于群体中各个体的品质己被大大改进，所以希望α取较小的值，以加速算法的收敛速度。基于这一考虑，我们将参数α随算法迭代指针t的变化关系定义为如下的公式：
式中，α0是参数的初始值，0.5<α0<2;1
定义1.2在特定的、规模为Sp的抗体群中，与抗体v相似的抗体的个数称为抗体v的浓度，记为Cv。
定义1.3对于特定的、规模为Sp的抗体群，抗体v的期望繁殖率ev定义为：
式中，β是反映抗体的适应度和浓度各自在期望繁殖率中非常重要的一个参数。
式(5)是本文给出的一种新的抗体期望繁殖率的定义方法。已往的人工免疫算法中，抗体的期望繁殖率与其适应度和浓度的关系是完全固定的(相当于在式5中取β=1)，无法调整适应度和浓度各自在期望繁殖率中的相对重要性，本文给出的这个定义很好地解决了这个问题。
定义1.4对于特定的、规模为Sp的抗体群，设抗体v的期望繁殖率为ev，则抗体v被选择进行复制的概率Qsv为：
从该式可以看出，人工免疫算法的选择概率不仅与个体的适应度有关，而且与个体的浓度有关。这是人工免疫算法与遗传算法最大的差别之处。
定义1.5对于特定的、规模为Sp的抗体群，其多样性指标Idiv定义为：
式中，ci为第i个抗体的浓度。
1.2 Elitism策略
遗传算法的最大缺陷就是容易陷入局部最优，为了防止当前群体的最优个体在下一代发生丢失，导致遗传算法陷入局部最优而不能收敛到全局最优解，De Jong在其博士论文中提出了“精英选择”(elitist selection or elitism)策略[6]，也称为“精英保留”(elitis preservation)策略。其主要思想是，将群体在进化过程中迄今出现的最好的个体直接复制到下一代中，而不进行配对交叉。这种选择操作即复制。De Jong在其论文中对精英选择策略作了如下定义：
定义1.6设到第m代时，群体中a*(m)为最优个体。又设A(m+1)为新一代群体，若A(m+1)中不存在a*(m)，则把a*(m)加入到A(m+1)中作为A(m+1)的第Sp+1个个体，这里Sp为群体的大小。
将精英个体加入到新一代群体中后，为了保持群体的大小规模和原先一致，则可以将新一代群体中适应度值最小的个体淘汰掉。精英保留策略对改进标准遗传算法的全局收敛能力产生了重大作用[7]。
2 IGAE求解TSP的算法及步骤
2.1 使用IGAE求解TSP的算法
以上面定义的抗体亲和力、浓度、期望繁殖率、选择概率等概念和计算公式以及精英保留策略为基础，给出如下求解TSP的改进免遗传疫算法：
在TSP问题中，走遍n个城市的最短距离就是算法的抗原，而从其中的一个城市出发，走遍其余(n-1)个城市只去一次的路径有(n!/2n)条[8]。对这n个城市编号，其号码分别为1,2,…,n，并且把商人所在城市即出发城市编为第1号，其它城市可随意编号。把这n个城市的编号任意排列成一个长度为n的字符串就形成一个抗体，因此抗体空间包含n!个抗体，而解空间包含(n!/2n)个可行解。为了缩小抗体空间，提高搜索效率，本文采用对于TSP问题较直观的抗体编码方式，即将每个抗体的第一个基因位(即字符串的第一个字符)固定为出发的城市编号1。这样每个抗体只有(n-1)个基因位可任意排列，抗体空间包含(n-1)!个抗体。而这种编码方式也更加符合TSP问题的实际情况，只是从固定的第一个城市出发，最终又返回到第一个城市。
在仿真实验中，针对TSP问题的特殊性，在选择算法中，采用比例选择法;在交叉算法中，采用顺序交叉算子;在变异时，采用单点基因位换位算子和多对基因位换位算子。
2.2 使用IGAE求解TSP的步骤
Step1:初始化参数。设置群体规模为100,迭代次数为20,抗体亲和力阀值ε=0.1,α0=1.2,β0=1.6;
Step2:初始化抗体群。在目标函数的解空间中随机产生n个初始抗体,组成抗体群;
Step3：确定每个抗体的适应度，并将适应度最大的抗体作为精英抗体赋予变量x;如果是第一代抗体群，则转到Step6，否则继续;
Step4：如果这一代抗体群中找不到与精英抗体适应度相同的抗体，则将保存在变量x中的精英抗体复制一个到抗体群中，同时将该抗体群中适应度最小的那个抗体删除，否则继续;
Step5：如果这一代抗体群中适应度最大的抗体其适应度的值大于精英抗体的适应度值，则将抗体群中适应度最大的抗体复制一个，并以它作为新的精英抗体替代保存在专用变量中的精英抗体，否则继续;
Step6：根据抗体的亲和力定义，即公式(3)，计算出每个抗体的浓度;
Step7：根据公式(5)计算出每个抗体的期望繁殖率;根据公式(6)计算出每个抗体的选择概率;根据选择概率对抗体群执行选择和复制操作;
Step8:对抗体群执行交叉操作,设置交叉概率Pc∈[0,l],本实验取值为0.6;
Step9:对抗体群执行变异操作,设置变异概率Pm∈(0,l),本实验取值为0.01;
Step10：判断设置的终止条件是否满足。若终止条件满足，则输出结果，算法停止;若终止条件不满足，则返回Step5，继续循环操作。
3 仿真实验
利用MATLAB7.0编程实现遗传算法GA、免疫算法IA和加入精英选择策略的改进免疫遗传算法IGAE求解TSP问题。分别取顶点数为10,15,20,30,50，在边长为20的正方形区域内随机选择顶点。每种算法重复进行10次计算。表1～表3分别给出了三种算法求解TSP问题的实验结果。
从表1～表3来看，在同种条件下，遗传算法收敛速度快但容易陷入局部最优;人工免疫算法求出的最优解较之遗传算法好，但运行速度和收敛速度都较慢;引入Elitism策略的改进免疫遗传算法无论是求出的最优解还是所用时间较之前两种算法都大大提高了。
4 结束语
该文将Elitism策略运用到免疫遗传算法中，提出了一种新的基于Elitism策略的改进免疫遗传算法。该算法可以动态调节抗体的亲和力和期望繁殖率，使算法具有更快的运行速度和更强的求解能力。通过仿真实验，在求解TSP问题时，基于Elitism策略的改进免疫遗传算法具有更快的收敛速度及动态收敛性好等优点。由于本仿真实验中采用的城市数属小规模TSP，对于大中型规模的TSP求解，笔者将作进一步的探讨。
参考文献
[1]王曙霞,葛东媛.一种TSP求解的人工免疫遗传算法[J].孝感学院学报,2005,25(3):69-71.
[2]Johnson D S,McGeoch L A.The Traveling Salesman Rob-lem:A Case Study in Local Optimization[M].Aarts E H L,Lenstra J K,eds.Local Search in Optimization,1997:215-310.
[3]Yuji Watanabe,Akio Ishiguro,Yoshiki Uehikawa.Decentralized Behavior Arbitration Meehanism for Autonomous Mobile Robot Using Irnrnune Network In Artificial Immune Systems and their Applications,Dasgupta D.(ed.),Springer Verlag,1998:187-209.
[4]Toyoo Fukuda,Kazuyuki Mori and Makoto Tsukiyama.Parallel Search for Multi-Modal Function Optimization with Diversity and Learning of Immune Algorithm.In Artificial Immune Systems and Their Applications,Dipankar Dasgupta(Ed.),Springer,1998:210-220.
[5]Dipankar Dasgupta and Hal Brian.Mobile Security Agents for Network Traffic Analysis,0-7695-1212-7/01,2001IEEE:332-340.
[6]何琳,王科俊.最优保留遗传算法及其收敛性分析[J].控制与决策,2000,15(1):63-66.
[7]危明,李元香,姜大志,等.基于精英策略的反序—杂交算法[J].武汉理工大学学报(信息与管理工程版),2008,30(4):514-518
遗传算法求解TSP 篇7
TSP的求解算法包括两大类:精确解法和启发式算法[2]。由于精确解法受到求解规模的限制, 而近年来问题规模越来越大, 因此国内外学者的研究主要倾向于启发式算法:遗传算法 (genetic algorithm, GA) 、蚁群算法 (ant colony algorithm, ACO) 、模拟退火 (simulated annealing, SA) 算法、禁忌搜索 (tabu search, TS) 算法等[3—7]。
针对TSP的改进SA算法研究, 国内外学者已经做了很多工作[8—10];提出了许多改进算法, 其中有一部分改进效果比较明显, 但以往学者提出的改进大多都是基于自己的经验, 缺乏细致科学的性能筛选分析实验, 所以主观性太强。本文则针对传统SA算法的不足, 从三个方面提出了改进的SA算法的想法, 然后以TSP标准测试库TSPLIB[11]中的数据对每一种改进想法进行仿真实验, 对其改进性能进行对比分析, 最终筛选出相对理想的改进SA算法。最后的数据验证也表明改进SA算法在性能上比GA和传统SA算法都有较大提高。
1 传统模拟退火算法
1.1 模拟退火算法基本原理
模拟退火算法原理来源于固体退火:将固体加温至充分高, 再让其徐徐冷却, 加温时, 固体内部粒子随温升变为无序状, 内能增大, 而徐徐冷却时粒子渐趋有序, 在每个温度都达到平衡态, 最后在常温时达到基态, 内能减为最小。根据Metropolis准则, 粒子在温度T时趋于平衡的概率为e-ΔE/ (k T) , 其中E为温度T时的内能, ΔE为其改变量, k为Boltzmann常数。
用固体退火模拟组合优化问题, 将内能E模拟为目标函数值f, 温度T演化成控制参数t, 即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始, 对当前解重复“产生新解—计算目标函数差—接受或舍弃”的迭代, 并逐步衰减t值 (由冷却进度表 (cooling schedule) 控制) , 算法终止时的当前解即为所得近似最优解, 这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。
1.2 模拟退火算法模型流程
模拟退火算法模型包括编码方式、目标函数、冷却进度表、扰动机制、内循环机制、外循环机制等, 其中最基础的是编码方式、目标函数和冷却进度表。
1.2.1 编码方式
求解TSP问题的各种编码中, 多数以遍历城市的次序排列进行编码, 即整数编码。这种方法简单、自然、容易理解。如城市编号为[3, 2, 5, 4, 7, 1, 6, 9, 8]表示从3号城市出发, 经过2、5、4、7、1、6、9、8后, 最终又回到了城市3。
1.2.2 目标函数
TSP问题的一个个体为C={C (1) , C (2) , …, C (N) }, 其目标函数定义为个体所代表路径确切距离的长度, 即
式中C (i) 为路径C的第i个城市, d[C (i) , C (j) ]为两城市间的距离, 而且d[C (i) , C (j) ]=d[C (j) , C (i) ]。在后面的运行过程中, 算法试图使适应度函数f (C) 最小化并认为使得该函数取得较小值的解为较优解。
1.2.3 冷却进度表
传统冷却进度表包括初始温度T0、衰减函数g (T0) , 以及当前温度T下内循环迭代次数L。
初始温度T0针对不同的问题可以有不同的取值方法, 一般TSP常用的方法为:随机产生N个个体, 分别计算其目标函数值f (Ck) , k=1, 2…N, T0有如下两种取值方式:
温度衰减函数g (T0) 根据不同问题的需要, 可以设置不同的衰减速度, 常见的有三种:
当前温度T下内循环迭代次数L通常取常数定值。
1.2.4 模型流程
模拟退火算法可以分解为解空间、目标函数和初始解三部分。其模型的具体流程如下:
(1) 初始化:初始温度T0 (充分大) , 初始解C (C表示城市序列, 是算法迭代的起点) , 每个t值的迭代次数L。
(2) 对k=1, …, L做第 (3) 至第 (5) 步。
(3) 随机产生扰动, 得到新解C'。
(4) 计算增量Δf=f (C') -f (C) , 其中f (C) 为目标函数。
(5) 若Δf≤0, 则接受新解, 否则以概率p (Δf) =exp (-Δf/T) 接受新解, 以概率1-p (Δf) 接受原解, 并以接受的解作为下一次模拟的初始解。
(6) 温度T按一定的规律逐渐减少。
(7) 如果满足终止条件则输出当前解作为最优解, 结束程序;如果不满足则转第 (2) 步。
2 改进模拟退火算法
分析SA退火算法可以发现, 虽然SA算法存在有限度地接受劣解、可以跳出局部最优解原理简单、使用灵活、适合求解出优化问题的全局最优或近似全局最优解等优点;但它存在以下三点主要问题: (1) 退火速度问题。同一温度下的充分搜索是相当必要的, 在变量多、目标函数复杂时, 为了得到一个好的近似解, 温度T需要从一个较大的值开始, 并在每一个温度值T执行多次Metropolis算法, 迭代运算速度慢。 (2) 扰动机制种类繁多, 灵活性大, 每一种的收敛速度和寻优能力不易估计, 选择时难以抉择。 (3) 搜索过程中由于执行概率接受环节而遗失当前遇到的最优解。针对以上三个问题, 提出以下三点改进。
2.1 内循环改进
虽然传统的SA方法设置了内循环, 在同一温度值T执行多次Metropolis算法, 保证全局搜索能力。但是实践表明, 将温度T下执行Metropolis算法的次数设置为定值往往不够灵活, 次数过多造成时间的浪费, 次数过少则损失解的质量。改进之处即设置采样稳定条件, 使得采样次数可以根据当前所得解的情况灵活处理, 在保证解质量的前提下, 尽量避免时间的浪费。
采样稳定条件定义为:同一温度T下局部解未被提高的次数L。具体操作是在每个温度T开始时设置一个局部解未被提高次数计数器num=0, 然后每执行一次Metropolis算法之后进行判断, 如果局部解被提高了就将num重新置于0, 否则就将num加1;这样直到num达到上限L时跳出当前温度T的内循环。
2.2 扰动机制改进
传统的SA算法选用单一的扰动机制, 而且没有证明这种单一的扰动机制就是最优的, 因此造成解被改进的可能性不大。改进之处在于提供了6种扰动机制, 给它们以同等机会被采用, 这样就增大了解被改进的可能性。扰动机制如图1所示。
其中M5还有一个变种, 即城市子排列双向反序, 如图2所示:
2.3 记忆功能改进
传统SA算法“依概率接受”思想, 使得当前状态可能要比搜索过程中某些中间状态差, 在仿真实验中已经发现最终得到的近似最优解有时候比中间经历的最好解差, 这样就浪费了搜索时间, 影响了搜索效果。为了不损失搜索过程中遇到的当前最优解, 并提高搜索效果, 加快搜索速度, 文章的改进之处在于增加了记忆功能。
记忆功能是指在搜索过程中记住当前最优解, 并及时更新使之能记住搜索过程中遇到的最好解, 避免了由于执行概率接受环节而遗失当前遇到的最优解, 增加了这种记忆能力的模拟退火算法已成为一种智能化的算法。
2.4 改进后的模型流程
在传统SA算法的基础上, 加入以上三种改进, 实现后的模型流程为如下:
(1) 运用公式W1或W2产生初始温度T0, 随机产生初始解C, 定义记忆器best=C, 定义局部最大无更优解产生次数L、全局最大无更优解产生次数M、局部最优解未更新次数num=0、全局最优解未更新次数aim=0、退火代数k=0。
(2) k=k+1, 运用公式G1、G2或G3更新温度Tk。
(3) 对个体C以同等概率执行3.3中的6种扰动机制, 产生新解C'。
(4) 按公式O计算增量Δf=f (C') -f (C) , 如果Δf<0, 则C=C', num=0, 转第 (7) 步。
(5) 计算概率值p (Δf) =exp (-Δf/Tk) , 产生伪随机数r, 如果r
(6) num=num+1, 转第 (7) 步。
(7) 如果num≤L, 则转第 (3) 步, 否则转第 (8) 步。
(8) 如果f (C)
(9) 如果aim≤M, 则转第 (2) 步, 否则以best为最终解输出, 算法结束。
3 仿真实验及结果分析
为了验证SA算法改进思想的效果, 分别选用att48、eil51、eil76进行实验。仿真硬件为普通PC机, 微处理器为Core2 Duo (2.00 Hz) , 内存1.00GB, 仿真软件为MATLAB (R2008a) 。以上3个问题的数据集均来自国际通用的TSP标准测试库:http://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/tsp/。
仿真实验分3次进行, 前两个实验均以eil51为数据集, 分别测试内循环改进和扰动机制改进的效果 (记忆功能改进比较直观, 无需测试) , 并从中选择最佳的参数配置, 组合成比较理想的改进SA算法。第三个实验是综合运用att48、eil51、eil76三个测试集, 将改进SA算法与标准GA以及传统SA算法进行对比实验, 进一步验证改进效果。
3.1 内循环改进仿真实验
为了仿真检测内循环改进的效果, 设计了一组对比SA算法实验:
确定量:有记忆功能;以公式W2确定初始温度T0;温度衰减函数选择公式G1;扰动机制以同概率采用M5 (城市子排列反序) 和M5’ (城市子排列双向反序) ;全局最大无更优解产生次数M=300。
变量:温度T下局部最大无更优解产生次数L, 分别取0、50、100、200、500、1 000次。
每个不同的参数L运算10次, 然后取平均值, 得到结果如表1所示。
由表1的结果可知, 采取内循环比不采取内循环效果要好很多, 而且内循环迭代次数越多, 结果越好, 但是运算时间也就越高。综合分析认为局部最大无更优解产生次数L设为500比较合适。
3.2 扰动机制改进仿真实验
为了仿真检测扰动机制改进的效果, 文章设计了一组对比SA算法实验:
确定量:有记忆功能;以公式W2确定初始温度T0;温度衰减函数选择公式G1;全局最大无更优解产生次数M=300;局部最大无更优解产生次数L=500。
变量:单一扰动机制M1、M2、M3、M4、M5、M6和同等概率采用6种扰动机制M7。每种扰动机制运算10次, 然后取平均值, 得到结果见表2。
由表2的结果可知, 扰动机制M1、M2和M3单独使用的效果不是很好, 应该避免单独使用这样一种扰动机制;单独使用时, M5效果最好;总体来说, 综合使用时M7结果好、方差小, 效果最佳。
3.3 综合对比仿真实验
由以上两个仿真实验, 可得一种比较理想的改进SA算法:采用记忆功能;以公式W2确定初始温度T0;温度衰减函数选择公式G1;全局最大无更优解产生次数M=300;局部最大无更优解产生次数L=500;扰动机制为M7。
为了仿真检测改进SA算法的效果, 文章设计了一组改进SA算法与标准GA以及传统SA算法进行对比实验:
每种算法的终止条件都设为相同, 即全局最优解没有被改进的次数达到300次时终止程序。每种算法针对各个问题均运算10次, 然后取平均值。具体结果见表3。
由表可以看出改进的SA算法与标准GA和传统SA算法相比, 运算结果不仅平均值有很大改进, 而且每10次计算都能够算到最优解, 同时结果的方差也相对较小, 结果比较稳定, 可以说明改进是成功的。图3给出了三种算法计算eil51问题, 均迭代1 000次之后的收敛曲线图。
TSP标准测试库给出三个问题att48、eil51和eil76的最优解为33 522、426和538, 本文的改进SA算法均能够达到, 图4、图5和图6分别展示了三个最优解。
4 结束语
通过分析传统SA算法原理和存在的不足, 提出了三种改进SA算法的思想。运用TSP标准测试集对三种改进思想进行仿真对比实验, 最终找到合理的改进参数配置, 得到一种较优的改进SA算法。将改进算法与GA和传统的SA算法进行对比实验, 结果表明该算法在性能上有较大提高。文中改进SA算法计算时间仍然相对偏长, 这将是下一步继续改进的目标。
参考文献
[1] 韩丽霞, 王宇平.解旅行商问题的一个新的遗传算法.系统工程理论与实践, 2007;12:145—150
[2] Steinbrunn M, Moerkotte G, Kemper A.Heuristic and randomized optimization for the join ordering problem.The VLDB Journal, 1997;6 (3) :8—17
[3] 林志毅.改进的遗传算法求解TSP问题.湖北:武汉理工大学, 2006
[4] Kirkpatrick S, Gelartt C D, Vecchi M P.Optimization by simulated annealing.Science, 1983;220 (11) :650—671
[5] 苏晋荣.基于智能优化算法的TSP问题研究及应用.山西:山西大学, 2007
[6] 于海平, 杨艳霞.基于信息素变异的蚁群算法的应用研究.计算机与数字工程, 2011;39 (9) :10—12
[7] 文永军.旅行商问题的两种智能算法.西安:西安电子科技大学, 2010
[8] 田澎, 王浣尘, 张冬茉.旅行商问题 (TSP) 的模拟退火求解.上海交通大学学报, 1995;30 (S1) :111—116
[9] 杨卫波, 赵燕伟.求解TSP问题的改进模拟退火算法.计算机工程与应用, 2010;46 (15) :34—36
[10] 杜宗宗, 刘国栋.基于混合遗传模拟退火算法求解TSP问题.计算机工程与应用, 2010;46 (29) :40—46
改进遗传算法解决TSP问题 篇8
遗传算法(GA)是一种进化算法,其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法则。最早是由美国密歇根大学Holland教授提出,在20世纪80年代左右得到了进一步发展。遗传算法是把问题参数编码为染色体,再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息,最终生成符合优化目标的染色体。目前遗传算法主要多用于优化问题[1]、图像处理[2]、通讯工程[3]等领域。
旅行商问题(TSP)是典型的组合优化问题,求解TSP问题传统的算法有:穷举法、分支限界法、动态规划法[4,5]等。高海昌等[6]对蚁群算法、遗传算法、模拟退火算法、禁忌搜索、神经网络、粒子群优化算法、免疫算法等进行了论述。随着研究的深入,许多改进的算法不断涌现,李玮[7]采用矩阵编码、交叉、变异的遗传算法来解决TSP问题,雷玉梅[8]提出了一种分而治之的遗传算法思想,姚明海[9]采用遗传算法与其他智能算法结合的思想来解决问题。遗传算法因其高效的搜索能力成为了解决TSP问题的有效方法之一。虽然遗传算法能够较为成功地求解TSP问题,但也存在搜索较慢的问题,特别是遗传算法在解决TSP问题时容易出现早熟的问题。因此本文在交叉操作之前,将一半的当前种群替换成随机种群来防止早熟,再融合贪婪思想产生的初始群体[10]和贪婪思想引导的交叉算子[11]来加快收敛速度,用改进的变异算子[12]进行操作,由此而得到最优解。
1 TSP问题描述
TSP问题最初的描述是1759年欧拉研究的骑士周游问题,这是著名的NP-hard难题,TSP问题数学描述为:给定n个城市及各个城市之间的距离,要求从起点出发,走访每个城市仅一次的Hamilton回路,最终返回起点并使得Hamilton回路最短。简言之,就是一条最短的遍历n个城市的路径,或者说搜索自然子集X={1,2,…,n}(X的元素表示对n个城市的编号)的一个排列,m(X)={V1,V2,…,Vn},使
取最小值。其中,d(V1,Vi+1)表示城市Vi到Vi+1的距离。
TSP问题并不仅仅是旅行商问题,其他许多的NP完全问题也可以归结为TSP问题,如邮路问题、装配线上的螺母问题和产品的生产安排问题等,使得TSP问题的有效求解具有重要的意义[13]。
2 基本遗传算法
遗传算法是建立在自然选择和群体遗传学原理基础上的随机迭代、进化、具有广泛适应性的搜索算法。具体是从一组随机产生的初始群体开始搜索操作,群体中的每一独立个体代表问题的一个解,这些个体利用选择、交叉、变异算子经过反复迭代,最终得到优良个体。
基本遗传算法的主要步骤如下:
Step1编码;
Step2初始化种群;
Step3计算种群中每个个体的适应度值;
Step4选择操作;
Step5交叉操作;
Step6变异操作;
Step7终止条件判断.若满足终止条件,则转至下一步,否则,转至Step3;
Step8输出结果。
3 改进的遗传算法求解TSP问题
3.1 编码和种群初始化
编码采用城市序号(序号是自然数1~N,N为城市个数)的十进制编码方法。这种表示方法是直接产生N个1~N间的互不重复的自然数的排列,该排列就构成一个N段的染色体,其中每一段即为对应的城市编号,每个染色体表征一种行走周游方案。设8个城市的TSP问题{1,2,3,4,5,6,7,8},染色体为|4|1|2|8|7|6|3|5就是一个合法的解(染色体)。基本的遗传算法是通过随机的方式产生初始种群,这样的染色体个体适应度比较低,从而在一定程度上制约收敛的速度。本文采用贪婪的思想产生初始种群,类似于蚁群算法的原理过程。在已知各个城市距离情况下,首先随机产生一个初始城市C1,并作为当前城市,在未走的城市集合中寻找一个城市作为下一次待走的城市,待走城市与当前城市C1的距离越小,将其选中的概率就越大。这里不直接选择最短距离城市作为待走城市,因为这种做法将容易陷入局部最优。在选择出待走城市后,可将其作为当前城市继续重复操作,直至N个城市巡游结束。由实验可知,这种贪婪思想产生的初始种群整体质量有所提高,而且其收敛速度也切实显优于随机产生种群的收敛速度。
3.2 适应度函数
和基本的遗传算法一样,适应度计算方法采用整条染色体的总路径长度的倒数为其个体的适应值,设个体的适应值为:
其中,zi为染色体个体的总路径长度。
3.3 选择操作
选择操作采用轮盘赌的方式,首先计算种群中每一个体在该种群中的相对适应值,个体选择概率由其适应度占种群个体适应度总和的比例所确定,即p(i)=fi/∑fi,其中,fi为第i个染色体的适应度,p(i)为个体选择的概率,个体适应度越大,获得选择的概率也就越大。选择操作从旧种群中选择90%的个体作为新种群,然后进行下面的交叉和变异等操作,剩下的10%个体将在重插入操作中进入种群。
3.4 交叉操作
对于TSP遗传算法的求解,常见的交叉操作有部分匹配交叉、顺序交叉和循环交叉操作,本文采用一种贪婪思想引导的交叉操作,在交叉操作开启之前,将适应值较低的一半种群替换成随机产生的种群,这样做的目的是防止到后期时候遗传算法的种群陷入局部最优。而随机种群的加入既能保持种群的多样性,又将有助于种群跳出局部最优。在替换后,开始进行贪婪交叉操作。设2父代个体为A,B,通过贪婪交叉操作产生子代A',具体执行过程如下:
Step1随机选择一个城市c作为起点,初始化子代个体A'的代码串,A'里面只含一个城市代码c。
Step2分别从A,B中找出c的右城市cRight1,cRight2,计算c的右边<c,cRight1>,<c,cRight2>的长度d1,d2。
Step3如果d1<=d2,则选择cRight1,将cRight1添加到A'中,从A,B中删除c,并修改c=cRight1,转至step5。
Step4若d1>d2,则选中cRight2,将cRight2添加到A'中,从A,B中删除c,并修改c=cRight2。
Step5若A,B中城市个数为1,则结束。否则转至Step2继续重复执行。
同理,将上述操作改为从A,B查找c的左城市c Left1,c Left2,比较<c,c Left1>,<c,c Left2>的大小,可以计算出B'。
例如父代A,B为:
以此为背景基础,研究可得规模为6的城市距离如表1所示。
从城市1开始,2父代通过贪婪交叉算子得到的子代个体为:
综上可知,A,B 2个体的距离分别为80,100。交叉操作之后A',B'的距离为70,70。可见贪婪思想引导的交叉算子加快了寻优速度。
3.5 变异操作
基本变异操作的设计弊端主要呈现在:变异元素比较接近,同时变异元素个数也较少,本文引用文献[12]的变异操作:定点置换法。随机选取一些位置,并对这些位置进行元素调换,从而实现序列更新。以8个城市的例子A:58 371 642,具体操作如下:
Step1随机生成变异序列长度6(变异长度必为偶数)。
Step2选择2组不同的序列作为置换位:
Step 3对换相应位上的各元素,从而获得一组新的序列。
3.6 进化逆转操作
为提升遗传算法的局部搜索能力,在选择交叉变异之后引进连续多次的进化逆转操作,这里的“进化”是指逆转算子的单方向性,即发生逆转之后,只有适应度值有所提高的才能接受下来,否则无效。仍旧以8个城市的TSP问题来给出演示说明。产生2个[1,8]区间内的随机整数r1和r2,确定2个位置,将其位置对换,如r1=3,r2=7
进化逆转后可得:
判断A的适应度值f(A)与A'的适应度值f(A'),如果f(A')>f(A),则逆转操作被接受,否则操作无效。
3.7 重插入操作
如前文提及在选择操作中,只有90%的种群获选进行交叉、变异和逆转操作。而若重复下一次选择操作则需要完整的种群,这就使得需要设定重插入10%的种群以支持实现下一次选择操作。如果选择插入10%的随机种群,在下一次选择算子中,这些随机种群的适应度值较低,会以较大概率被放弃掉,从而不能保持种群的多样性。因而,本文选用初始生成的贪婪种群,插入适应值较大的10%个体,在保持种群多样性的情况下也并不容易被选择放弃,实验结果表明,这些插入的种群在操作中能够起到良好的寻优作用。
4 实验与仿真
TSP问题已经成为测试许多新算法的标准问题,如果算法能够对TSP问题实施妥善解决,那么对算法进行稍微改动,也就能够为其他组合优化的问题提供优化满意方案,因此用改进的遗传算法在TSP上开展仿真测试。本文采用31个城市为例。按照枚举法,31个城市的巡回路径应有约1.326×1032种。实验参数设置如下。
种群大小:100,最大迭代次数:200,交叉概率:0.9,变异概率:0.1,代沟:0.9。在同样条件下,用MATLAB7.0软件分别对基本的遗传算法(SGA)、在基本遗传算法上只引入贪婪种群(GA1)、在基本的遗传算法上只引入贪婪交叉操作(GA2)和本文改进的遗传算法(IGA)测试20次,结果四舍五入后设计展现如表2所示。
由表2可知,对照基本的遗传算法(SGA)和本文改进的遗传算法(IGA)发现,不论是平均值、收敛代数还是最优值,改进的遗传算法均要呈现全面优效。比较GA1、GA2和IGA,改进的遗传算法寻优结果和收敛代数也优于GA1和GA2。图1展示了改进的遗传算法(IGA)测得的最优解为15 378(15 377.711 3)km。各自的最优解迭代过程如图2、图3所示。由图2可知,在迭代过程中,改进的遗传算法的收敛速度明显要快于基本的遗传算法,在迭代的后期,SGA出现早熟现象而IGA没有。由图3可知,GA1遗传算法在迭代过程中收敛速度较慢,而且容易出现早熟现象,GA2相对有所改善,但却并非最佳,IGA是收敛速度最快且最优解堪称理想的情况。通过多次实验测试,关于求解TSP问题,本文改进的遗传算法(IGA)在200代之前都能找到问题的最优解,并且在收敛速度、收敛代数和平均值上也要实优于SGA、GA1和GA2,结果令人满意。
5 结束语
文章在基本的遗传算法基础上提出一定改进,引用贪婪思想产生质量相对较好的初始种群,同时又在贪婪思想引导的交叉操作发生之前,把当前较差的一半种群替换成随机种群,二者结合来提升收敛速度又防止了陷入局部最优。实验证明,本文研发的改进遗传算法较好地解决了TSP问题中收敛速度和早熟的问题,且具有较强的鲁棒性,通用于类似的组合优化问题。
摘要：针对基本遗传算法收敛速度慢,易早熟等问题,提出一种改进的遗传算法。新算法利用贪婪思想产生初始种群来加快寻优速度,用贪婪思想来引导交叉操作,在交叉操作之前,把当前较差的一半种群替换成随机种群,最后用改进的变异算子和进化逆转操作进行寻优,利用新的遗传算法求解基本的旅行商问题。仿真结果表明,改进的遗传算法具有全局搜索能力强、收敛速度快的特点,优化质量和寻优效率都较好。