改进的TSP算法（精选7篇）
改进的TSP算法 篇1
TSP(旅行商问题)是一类被广泛研究的组合优化问题。对于一个M城市的TSP，问题归结为求一条穿过所有M个城市且每个城市只能通过一次的最短闭合路径。对M个城市，一共存在(M-1)!/2条可能的路径，因此，TSP是一个NP完备问题[1,2,3]。由于(M-1)!/2随M增长极快，检查所有路径的枚举法是不切实际的。解决TSP的有效方法是使用遗传算法等近似算法。相对传统解法，遗传算法不考虑得到路径的过程，而是直接将目标指向距离最短，因此能很快得到结果。但遗传算法搜索空间大，搜索时间较长;对初值敏感，对大型TSP收敛速度较慢[4]。局部优化算法对于寻找TSP的局部最优解非常有效，通常在很短时间内计算出上百个城市TSP问题的高质量的解，但易陷入局部最优点[5,6,7]。
本文采用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
[8]乔彦平，张骏．基于一种改进遗传模拟退火算法的TSP求解.计算机仿真，2009;26(5):205-208
改进遗传算法求解TSP 篇2
目前, 人工智能发展迅速, 出现了许多独立于问题的智能优化算法。文献[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.
改进遗传算法解决TSP问题 篇3
遗传算法(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问题中收敛速度和早熟的问题,且具有较强的鲁棒性,通用于类似的组合优化问题。
摘要：针对基本遗传算法收敛速度慢,易早熟等问题,提出一种改进的遗传算法。新算法利用贪婪思想产生初始种群来加快寻优速度,用贪婪思想来引导交叉操作,在交叉操作之前,把当前较差的一半种群替换成随机种群,最后用改进的变异算子和进化逆转操作进行寻优,利用新的遗传算法求解基本的旅行商问题。仿真结果表明,改进的遗传算法具有全局搜索能力强、收敛速度快的特点,优化质量和寻优效率都较好。
改进的TSP算法 篇4
本文在分析遗传算法的基础之上求解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中的应用 篇5
蚁群算法,是一种用来在图中寻找优化路径的机率型技术,由Marco Dorigo于1992年在他的博士论文中引入,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,经过各种数值仿真结果表明该算法具有许多优良的性质,具有一种新的模拟进化优化方法的有效性和应用价值,是一种求解组合最优化问题的新型通用启发式方法,具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点,通过建立适当的数学模型,可以解决一维静态优化问题甚至多维动态组合优化问题。
本文采用蚁群算法对TSP问题进行研究,设计一个基本的蚁群算法解决最短路径问题的模型,并提出一种最大———最小蚂蚁系统(MMAS)模型,通过引入“三步走”法确定模型参数的最优组合,使所选参数让性能达到最优;改进信息素更新规律及动态调整参数;并且引进去交叉局部优化相关的求凸壳顶点的算法,改进算法的局部搜索能力,对MMAS模型加以改进,最终使收敛速度和收敛效果达到令人满意的结果。
1 基本蚁群算法及MMAS在TSP中的应用
1.1 问题描述
旅行商问题(traveling salesman problem,TSP)是著名NP完全问题之一,常被用于测试和评价算法的性能。该问题可以简单描述如下:有一个商人需要选择一条最短的哈密顿回路拜访各城市,即所有城市必须经过且只经过一次,而最后要回到原来出发的城市。如果用穷举的办法解决该问题,时间复杂度显然是很大。当比较大的时候,现有的计算机是无法在可接受的时间内求解该问题的。因此很多高效的算法被用于尝试求解TSP。本文采用蚁群算法对TSP问题进行研究,并通过基本蚁群算法、MMAS、改进的MMAS三者直接的比较得出最优解。
1.2 算法设计
(1)蚁群算法构造TSP问题的基本数学模型
设bit表示t时刻位于元素i城市的蚂蚁数目,m表示蚂蚁的总数目,n表示城市的规模:
蚂蚁k k=≤1,2,…,m≤在运动过程中,根据各路径上的信息量决定其转移方向。这里用禁忌表tabuk(k=1,2,3,…,m)来记录蚂蚁k当前所走过的城市,集合随着tabuk进化过程做动态调整。在搜索过程中,蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率:pkijt≤≤表示在t时刻蚂蚁k由城市i转移到城市j的状态转移概率:
上式中,allowedk=,C-tabuk,表示蚂蚁下一步允许选择的城市,C表示所有城市的集合;ηij表示路径i,≤j≤距离dij的倒数即ηij=1/dij;α、β分别表示信息素和路径信息对转移概率的影响程度。随着时间的推移,以前留下来的信息素会逐渐挥发,用参数p表示信息素的挥发程度。经过n个时刻,每个蚂蚁都完成一次循环,各条路径上的信息素须做调整:
system调整信息素的方法:
其中,Q为常数,表示蚂蚁循环一周所释放的总信息量,Lk表示antk在这次循环中所走的路径的长度。
(2)最大最小信息素算法(MMAS)
(3)去交叉局部优化
在这里引进去交叉局部优化相关的求凸壳顶点的算法对MMAS算法进行改进,凸壳问题(convex hull problem)是几何学中的基本问题之一,在TSP中主要是对各点进行预处理。设S是平面上的非空点集,z1和z2是S中的任意两点,t是0与1之间的任意实数。如果满足公式8的点Z属于S,则S为凸集。
凸集S中的凸壳是包含S的周长最小的凸多边形,凸壳必包含凸集,在TSP的预处理算法中,从某一凸壳的顶点开始,需要判断与其不相邻的下一个凸壳顶点是否在同一条直线上,若不是,则消去此线,然后以此类推对其余的凸壳顶点进行同样处理。
2 实例仿真
实例:中国的31个省会城市的坐标C=[1 304 2 312;3 639 1 315;4 177 2 244;3 712 1 399;3 488 1 535;3 326 1 556;3 238 1 229;4 196 1 004;4 312 790;4 386 570;3 007 1 970;2 562 1 756;2 788 1 491;2 381 1 676;1 332 695;3 7151 678;3 918 2 179;4 061 2 370;3 780 2 212;3 676 2 578;4 029 2 838;4 263 2 931;3 429 1 908;3 507 2 367;3 3942 643;3 439 3 201;2 935 3 240;3 140 3 550;2 545 2 357;2 778 2 826;2 370 2 975],下面以31个城市的坐标为参考模型,分别建模仿真。
首先采用“三步走”方法选择蚁群算法的最优参数组合:
(1)确定蚂蚁的数目,当城市规模大致是蚂蚁数目的1.5倍时,蚁群算法的全局收敛性和收敛速度都比较好。显然这里蚂蚁数目m选20比较适宜,城市n选31。
(2)参数粗调,调整取值范围较大的信息启发因子α,期望启发式因子β以及信息素强度Q等参数以得到较理想的解。经过调整取α=1.0,β=5.0,Q=100。
(3)参数微调,在较小范围内调整信息素挥发因子ρ。信息挥发素ρ取值为0.04。
实践证明运用此方法后在减少计算量、快速搜索、收敛性、收敛速度等方面都有较好的效果。在MMAS模型中σ取5,τmin!0"=2。进行仿真后得到以下数据:图1为运行10次基本蚁群算法模型得到的最优路径;图2为运行10次改进的MMAS模型得到的最优路径;图3为运行10次未改进的MMAS模型得到的最优路径;表1中为两种方法中的最短路径的距离、平均距离、得到最优最小迭代数及平均迭代数。
上述数据表明改进型的MMAS对于基本蚁群算法及MMAS有一定的优越性,所得的结果在收敛性、稳定性、收敛速度等方面都有很大的改进,并且改进型MMAS不会出现图3中的那种交叉路径,能够起到避免出现过早呆滞和及时纠正交叉的作用。图4列出改进的MMAS在实验过程中得到实时路径数据。
3小结
本文主要是分析了蚁群算法及两种类型蚁群算法在旅行商问题中的应用,通过MATLAB编程仿真了所建立模型,并把获得的结果进行了比较分析,由实时路径图也可以看到此算法的稳定性能较强,能够较好的应用来解决旅行商问题。
参考文献
[1]段海滨.蚁群算法原理及其应用[M].北京:科学技术出版社,2005.
[2]赵霞.MAX-MIN蚂蚁系统算法及其收敛性证明[J].计算机工程与应用,2006(8):70-72.
[3]陈宝文,宋申民.应用于车辆路径问题的多蚁群算法[C]//第25届中国控制会议论文集(下册),2006:1723-1726.
[4]Yang Haiqing,Yang Haihong.An self-organizing neural network with convex-hull expanding property for TSP[C]//Neural Net-works and Brain,ICNN&B'05,International Conference on Volume1,2005:379-383.
[5]蔡之华,彭锦国,高伟,等.一种改进的求解TSP问题的演化算法[J].计算机学报,2005(28):823-828.
[6]周培德.求凸包定点的一种算法[J].北京理工大学学报,1993(13):69-72.
改进的TSP算法 篇6
遗传算法 (Genetic Algorithm, 简称GA) [1]是一种常用的大规模并行搜索优化算法, 它模拟了达了达尔文“适者生存”的规律和随机信息交换思想, 仿效生物的遗传方式。从随机生成的初始解群出发, 采用选择、交叉、变异等算子进行操作, 产生优于父代的子代, 如此循环执行, 使优化过程以大概率趋于全局最优。但其本身还存在许多不足, 尤其在解群分布不均匀时易出现末成熟收敛, 陷入局部极优, 其原因在于G A中基于适应度的多样性保持策略没能保持群体的多样性。
为了解决上述问题, 文献[2,3,4,5]提出了使遗传算法具有免疫功能的免疫遗传算法。其算法一般包括六大块组成:抗原的识别, 初始抗体的产生, 适应度计算, 向记忆细胞分化, 抗体的促进和抑制, 抗体产生 (选择, 交叉, 变异) 。
免疫遗传算法既保留了遗传算法的搜索待性, 克服了遗传算法在局部搜索解空间上效率较差的缺点, 又在很大程度上避免末成熟收敛。但由于其每一代种群的产生仍只通过简单的遗传算子 (选择, 交叉, 变异) 产生, 收敛效果不是很理想, 因此, 本文提出了一种针对上述情况的用于T S P (Traveling Salesman Problem, 旅行商问题) 的改进免疫算法。文中首先描述用于TSP寻优问题的改进免疫算法的实现过程, 然后通过对TSP问题测试数据进行仿真。仿真结果说明该算法收敛速度快, 较易实现。
2 旅行商问题 (TSP)
Traveling salesman prolem (TSP) 问题是经典的N P难问题, 是典型的组合优化问题, 具有很强的应用背景, 例如, VISI芯片设计, 路径优化, 网络路由, 机器人控制等许多问题都可以建模为T S P问题。TSP问题其核心思想就是要寻找一条遍历L个城市的最短路径, 在数学上可以描述为以下优化问题
其中, C为城市集合, 为城市编号, i=1, 2, 3, ……, l, d (c i, c j) 为编号i和j的两城市之间的距离。
3 用于TSP的改进免疫算法描述
3.1 基本概念
抗原:算法中的抗原一般是指城市之间的距离距阵, 及其约束条件 (距离最小)
抗体:算法中的抗体一般是指生成的各个路径
抗体与抗体之间的亲合度:用于表明抗体之间的相似度, 本文采用基于信息熵的亲合度计算[5], 即:Au, v=1/ (1+H (2) ) .
式中Au, v为抗体之间亲合度, H (2) 为抗体u与v的平均信息量
抗体与抗原之间的亲合度:用于表明抗体对抗原的识别程度, 本算法中抗体与抗原的亲合度定义为:最长路径值和抗体的路径长度值之差及其与所有差值和之比
式中M为城市个数, dmax为城市距离中最大两城市之间的距离, Dmax为存在的可能最大路径值
式中iB表示抗体i与抗原之间的亲合度, len (i) 表示路径i的长度值。
3.2 算法描述与算法步骤
如果把实际求解问题的城市距离视为外来入侵的抗原, 那么, 免疫响应中产生的抗体视为问题的解, 则不同亲和度抗体的进化与成熟机制就是寻找最优路径 (路径值最短) 。本文的改进算法主要是针对传统的遗传算法以及文献[5]所使用的基于信息熵的免疫遗算法的收敛效率问题所提出来的。算法采用实数编码, 减少二进制编码的计算量, 提高了搜索的效率;引入抗体群优化策略, 可以在初始或经遗传算子进化生成的种群中提高抗体与搞原的亲合度, 从而提高算法的搜索效率。
本文算法的主要步骤如下:
步骤1:算法初始化:抗原输入及参数的设定:输入城市坐标值 (或随机生成坐标值) , 并通过欧几里得距离计算公式:
D= ( (xi+1-xi) ^2+ (yi+1-yi) ^2) ^0.5计算抗原值;
同时设定种群规模N, 相似度阈值γ, 交叉率Pm, 变异率Pc;
步骤2:抗体的编码:抗体的编码采用实数编码, 抗体的长度为N (城市的个数)
步骤3:产生初始抗体群, 记忆库:先检查记忆库, 如果为空则在可可行解空间随机产生初始抗体群, 否则, 从记忆库中选择和随机产生的其余抗体共同组成初始抗体群。
步骤4:抗体种群的优化:由于TSP问题的任何一条路径都是闭合路径, 则从任一城市出发, 要到达的下一个城市选择为未到过的城市中距离该城市最近的一个, 这样更能使种群朝着有利方向收敛。
步骤5:对上述抗体群体进行评估:计算抗体与抗原适应度值及各抗体的浓度值,
以个体选择率ie为标准进行评估。定义选择率为, , 式中, fi表示抗体与抗原的亲合度, ic表示抗体的浓度。抗体的浓度是指抗体群体中相似抗体所占的比重, 即:ic=与抗体i相似度大于γ的抗体数/N;
步骤6:将抗体种群基于选择率进行选择操作, 再对选择出的抗体实施交叉、变异操作。
步骤7:记忆优良个体:计算变异后的抗体群体的亲和度, 选择高亲和度的抗体, 加入记忆细胞库。
步骤8:终止条件判断:判断是否满足终止条件;是则算法结束;否则返回步骤4.
步骤9:输出最优路径。
4 仿真实验及分析
为了测试本文算法的性能并和相关算法进行比较, 本文分别选用国际上通用的TSP测试库中的Eil 51-cities和Berlin 52-cities数据为例进行测试[6]。
相关参数:种群数目N:100, 交叉率P c=0.7变异率P m=0.1, 相似度阈值γ=0.02
方法一:遗传算法;
方法二:文 (5) 中所提的基于信息熵的免疫遗传算法;
方法三:本文方法;
其运行的结果如图1, 图2:
在相同参数设置下, 从图1中我们看到在100次迭代次数以内, 本文算法算法具有较快的收敛性, 从图2中我们看到虽然最终三种算法都能求得最优解, 但采用不同的算法, 收敛速度不同, 而本文的算法明显优于GA与IGA, 其在170代左右就能求得最优解, 而GA与IGA由分别需650代与340代左右。综合上述仿真实验结果可知:本文提出的用于TSP优化路径与相关算法比较, 它能够在较少的迭代代数下, 求出最优解, 加快点收敛的效率。
5 结语
本文是基于生物免疫系统机制, 在文[5] (基于信息熵的免疫算法) 的基础上, 提出了一种改进的用于TSP路径优化的免疫遗传算法。文中详细的讨论了该算法的步骤和过程, 最后对两测试数据包进行了实验仿真, 并和相关算法进行了比较, 初步仿真实验结果表明:本文提出的算法应该有效的, 值得进一步研究和应用于实际复杂问题的优化计算中。
摘要：受生物免疫原理启发而产生的人工免疫算法, 是一种新型的随机启发式搜索算法。基于生物免疫系统机制, 本文提出了一种改进的用于TSP优化的免疫算法。算法包括初种群优化, 免疫选择, 交叉, 变异, 同时采取免疫记忆, 免疫网络促进与抑制操作。文中详细讨论了算法的相关概念及算法步骤, 通过对TSP测试数据[6]进行仿真实验, 实验结果表明了本文的改进算法的有效性。
关键词：免疫遗传算法,TSP,初始种群优化
参考文献
[1]云庆夏编著.进化算法[M].北京:冶金工业出版社, 2000-05.
[2]高岩, 位耀光, 付冬梅, 张蔚.免疫遗传算法的研究及其在函数优化中的应用.《微计算机信息》, 2007, 23 (6) :183～184.
[3]杨孔雨, 王秀峰.免疫记忆遗传算法信其完全收敛性研究.计算机工程与应用, 2005, 12:47～50.
[4]Jiao L C, Wang L.A novel ge-netic algorithm based immunity.IEEETransactions on System Man, andCybernetics, 2000, 30 (5) :552～561
[5]杨四海, TSP的等价解及其对免疫遗传算法的干扰.华侨大学学报 (自然科学版) 1期, 2007年1月.
改进的TSP算法 篇7
关键词：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