遗传算法在求解最短路径问题中的研究应用.doc

遗传算法在求解最短路径问题中的研究应用摘 要TSP 问题是典型的NP完全问题,遗传算法是求解NP完全问题的一种常用方法。本文针对解决TSP 问题,在MATLAB中用遗传算法施行对TSP问题进展了求解，进展了选择、穿插与变异算子进展了算法设计，最后在JAVA软件上进展编程实现。最后探讨了遗传算法解决旅行商问题自身具备的特点1。关键词：遗传算法；TSP问题；JAVA软件SOLVING TSP (Travelling Salesman Problem ) BASED ON GENETIC ALGORITHMAuthor : Zong Man-yi Tutor : Qiao Li-hongAbstractTSP( Traveling Salesman Problem) is a typical NP complete problem ,genetic algorithm is the perfect method for solving NP complete problem. This paper use genetic algorithm in the MATLAB software to solve the a typical TSP problem . It probes into the realization of genetic operator program through TSP solving by genetic algorithm , design the each function of each genetic operator(select, intercross, mutate). Finally ,We programm in Matlab language and discuss the characteristic of genetic algorithm in solving TSP Key words : genetic algorithm; TSP JAVA ;目录引言41 GA概述42旅行商问题(TSP)43 用遗传算法解决旅行商问题54 论文的主要构成5遗传算法的设计61问题分析62 总体设计73 详细设计8 编码与随机和初始群体生成83.2 城市位置及距离矩阵和适应度函数83.4 选择93.4 穿插93.5 变异103.6 群体的跟新和终止条件10MATLAB编程验证111MATLAB计算112算法分析优化13结论15参考文献16引言1 GA概述遗传算法(Genetic Algorithm , GA ) 是由美国J. Holland 教授提出的一类借鉴生物界自然选择与自然遗传机制的随机化搜索算法。它起源于达尔文的进化论, 是模拟达尔文的遗传选择与自然淘汰的生物进化过程的计算模型。其主要特点是群体搜索策略与群体中个体之间的信息交换, 搜索不以梯度信息为根底。它尤其适用于处理传统搜索方法难于解决的复杂与非线性问题, 可广泛应用于组合优化、机器学习、自适应控制、规划设计与人工生命等领域。作为一种全局优化搜索算法, 遗传算法以其简单通用、鲁棒性强、适于并行处理以及应用范围广等特点, 使其成为21 世纪智能计算核心技术之一。进入80 年代, 遗传算法迎来了兴盛开展时期, 无论是理论研究还是应用研究都成了十分热门的话题2。2旅行商问题(TSP)一个有名的组合优化问题就是旅行商问题(Travelling Salesman Problem , TSP)。TSP问题是典型的、易于描述却难以处理的组合优化问题。由于遗传算法方法的本质是处理复杂问题的一种鲁棒性强的启发性随机搜索算法, 故而利用遗传算法求解这类问题是有效的。假设平面上有n个点代表n个城市的位置, 寻找一条最短的闭合路径, 使得可以遍历每一个城市恰好一次。这就是旅行商问题。旅行商的路线可以看作是对n个城市所设计的一个环形, 或者是对一列n个城市的排列。由于对n个城市所有可能的遍历数目可达(n- 1)!个, 因此解决这个问题需要0(n!)的计算时间。假设每个城市与其他任一城市之间都以欧氏距离直接相连。也就是说, 城市间距可以满足三角不等式, 也就意味着任何两座城市之间的直接距离都小于两城市之间的间接距离。是一个典型的优化组合问题3。3 用遗传算法解决旅行商问题目前针对TSP问题有许多种解法，较为常用的算法有神经网络法、列表寻优法、二叉树描述法、模拟退火法与遗传算法等等。遗传算法是近几年开展起来的一种崭新的全局优化算法，它借用了生物遗传学的观点，通过选择、遗传、变异与免疫等作用机制，使每个个体的适应性提高。由于其全局搜索的特性，遗传算法在解决TSP问题中有着其他算法所没有的优势。提出的TSP问题包括31个城市的编号与各自的位置。本文针对这个TSP问题进展了遗传算法的编程与求解。4 论文的主要构成本论文在MATLAB中用遗传算法施行对TSP问题进展了求解，进展了选择、穿插与变异、免疫等算子进展了算法设计，最后在MATLAB软件上进展编程实现。遗传算法的设计1问题分析TSP 问题的描述十分简单, 简言之, 就是寻找一条最短的遍历n 个城市的最短路径, 或者说搜索自然数子集X = 1 ,2 , , n ( X 的元素表示对n 个城市的编号) 的一个排列( X) = V1 , V2 , , Vn , 使len = d ( Vi , Vi+1) + d ( V1 , Vn)取最小值, 式中的d ( Vi , Vi+1) 表示城市Vi 到城市Vi + 1的距离.图 13本实例中设定了我国31个省会城市，当一个旅行商彼遍历了所有城市后回到出发城市，求其最短路径的走法。一个最容易想到的方法是利用排列组合的方法把所有的路径都计算出来，并逐一比拟，选出最小的路径。虽然该方法在理论上是可行的，但路径的个数与城市的个数成指数增长，当城市个数较大时，该方法的求解时间是难以忍受的，甚至是不可能完成的，31个城市所有路径个数是30！个。由于其全局搜索的特性，遗传算法在解决TSP问题中有着其他算法所没有的优势。本文针对这个TSP问题进展了遗传算法的编程与求解。2 总体设计图 2标准遗传算法的流程图标准的遗传算法包括群体的初始化，选择，穿插，变异操作。其主要步骤可描述如下1：1随机产生一组初始个体构成的初始种群，并评价每一个个体的适配值。2判断算法的收敛准那么是否满足。假设满足输出搜索结果；否那么执行以下步骤。3根据适配值大小以一定方式执行选择操作。4按穿插概率Pc执行穿插操作.5按变异概率Pm执行变异操作。6返回步骤2。 本TSP问题的遗传算法总体设计图3总体设计说明：1本算法的判断完毕准那么是固定指定了迭代的次数当算法到达迭代次数时，算法完毕，输出当前的最优解2在根据适配值计算并选择的时候，记录下来的当前最优值，在变异后参加跟新的群体，保证新的迭代循环中TSP解越来越好不会变差。3在选择的一种操作是拿最优的K个替换最差的K个个体，本例是按适配值选择，并使群体数目变少，当每次变异操作后，产生随机路径补充群体是群体数目不变，再次循环，一定程度上防止因初始群体的选择问题而陷入局部最优。3 详细设计-个体数 10 编码与随机与初始群体生成 给所有城市编码，以城市的遍历次序作为遗传算法的编码。在MATLAB中使用 randperm(N)产生一个1×N 的矩阵N为所有城市的个数，本例中为31为一个随机路径。利用n×N矩阵存储n个随机群体产生初始群体。3.2 城市位置及距离矩阵与适应度函数 距离d(i-1,j-1)= sqrt(Xi-Xj.2+(Yi-Yj).2)城市的位置为编译前指定，也可以使用随机生成的坐标参数。距离矩阵使用一个N×N矩阵D存储，Di，j代表城市 i与城市j之间的距离。Di，j=sqrt(Xi-Xj.2+(Yi-Yj).2)在该问题的求解中，用距离的总与来衡量适应度，距离的总与越大，适应度越小，进而探讨求解结果是否最优。每个个体每条路径距离总合计算公式为：len=d(1,9);len=D(1,N);for i=1:(N-1) for(i=0,i<8;i+) len+=d(I,i+1); len=len+D(i,i+);endlen纪录总路径格式n×1 len(i)代表第i个个体路径距离总合。3.4 选择选择 choice()选择操作是为了防止有效基因的损失，使高性能的个体得以更大的几率生存，从而得到全局收敛性与计算效率。本例中使用的适配值函数为 fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.0001).m;% maxlen ，minlen为最大与最短路径利用fitnessrand选择个体，将个体，将较小路径(适应度较大)个体选择下来。但这种算法的群体的个体数目变小并且较优的个体个数较少， 可能收敛的数目变慢，在算法调试的过程中证明了这一点4。 穿插穿插 mutual()穿插操作用于组合出新的个体，再借空间中进展有效的搜索，同时降低有效模式的破坏概率1。本实例中穿插采用局部匹配穿插策略,其根本实现的步骤是：步骤1： 随机选取两个穿插点步骤2： 将两穿插点中间的基因段互换步骤3： 将互换的基因段以外的局部中与互换后基因段中元素冲突的用另一父代的相应位置代替，直到没有冲突。本例中路径实例如图穿插点为2，7，交换匹配段后A中冲突的有7 、6、5，在B的匹配段中找出与A匹配段中对应位置的值7-3，6-0，5-4，继续检测冲突直到没有冲突。对B 做同样操作，得到最后结果。图 4 变异 变异类 swap()变异操作通过随机改变个体中某些个体的某些基因而产生新个体，有助于增加种群的多样性，防止早熟收敛非全局最优。本例中变异操作使用互换操作算子SWAP，即随机交换染色体中两个不同基因编码的位置，SWAP相对于INV逆序操作与INS插入操作更有利于算法的大范围搜索。对于一个31路径的染色体的变异操作，依变异概率确定是否变异，随机选择路径上的两个城市进展交换。例如 变异交换位置为2与83.6 群体的跟新与终止条件为保证计算随迭代次数的增加，最优解越来越好，本例种每次变异后将每次的上次迭代最优解参加群体，防止因穿插或变异而是最优解失去，出现退化现象。为保持群体数目不变，变异后产生随机解参加群体本算法群体数目仔选择中可能发生减少。终止条件最常用的有事先给定一个最大进化步数，或者是判断最优化值是否连续假设干步没有明显变化两种。本实例中只选择了第一种方法6。MATLAB编程验证1JAVA计算1初始值图 5种群个数n=100;迭代次数C=1000; 穿插概率Pc=0.9;变异概率Pm=0.2;初始种群中的一个随机值:R = 29 13 15 16 4 17 22 12 2 18 31 5 25 26 11 6 28 3 14 30 20 1 9 21 10 24 8 7 23 19 27Rlength = 4.4308e+004迭代1000次后路径如图Rlength = 3.0902e+004发现算法收敛很慢2初始值图 6种群个数n=100;迭代次数C=2000; 穿插概率Pc=0.9;变异概率Pm=0.2;初始种群中的一个随机值:Rlength = 4.3506e+004迭代2500次后路径如图Rlength =1.9497e+004趋向于收敛3初始值图 7种群个数n=100;迭代次数C=2500; 穿插概率Pc=0.9;变异概率Pm=0.2;初始种群中的一个随机值:Rlength = 4.3506e+004迭代2500次后路径如图Rlength = Rlength = 1.8754e+004 趋向于收敛4初始值：图 8种群个数n=100;迭代次数C=3000; 穿插概率Pc=0.9;变异概率Pm=0.2;Rlength = 4.4721e+004迭代3000次路径如图Rlength = 1.6957e+004次序为R =29 13 7 10 9 8 3 18 22 21 26 28 27 31 1 15 14 12 11 23 6 5 2 4 16 17 19 24 20 25 30路径较小可能已经为最优解 5初始值：图9种群个数n=100;迭代次数C=3500; 穿插概率Pc=0.9;变异概率Pm=0.2;Rlength = 4.4721e+004迭代3500次路径如图Rlength = 1.7093e+004次序为R =25 20 21 22 18 3 17 16 5 6 7 2 4 8 9 10 13 12 11 23 19 24 29 14 15 1 31 30 27 28 26路径较小可能已经为最优解 城市 坐标矩阵为a=1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556; 3238 1229;4196 1044;4312 790;4386 570;3007 970;2562 1756; 2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376; 3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826; 2370 2975;可以认为该算法在迭代3000左右时，已经发生了收敛，对于本例给出一个解为R =29 13 7 10 9 8 3 18 22 21 26 28 27 31 1 15 14 12 11 23 6 5 2 4 16 17 19 24 20 25 302算法分析优化1. 选择操作。本例中算法收敛较慢，改良选择操作如下，选定K个最大适应度的个体，用来代替适应度最小的K个个体，保持群体的数目不变。此方法可以使群体的平均适应度大幅提高，可能使其收敛速度加快。试验中使用该种选择操作，发现速度有加快迹象6初始值：图 10种群个数n=100;迭代次数C=1000; 穿插概率Pc=0.9;变异概率Pm=0.2; Rlength= 1.9575e+004与图6相比收敛速度又加快迹象本次迭代次数为1000次7初始值：图 11种群个数n=100;迭代次数C=4000; 穿插概率Pc=0.9;变异概率Pm=0.2; Rlength= 1.8588e+004与图8，9相比收敛结果根本正确。证明优化方式正确。2. 每次穿插或变异操作以后，检验子代的适应度。如果子代发生退化，取消操作，用父代代替子代。这种方法可能带来的问题有虽然收敛迭代次数可能减少，但每次运算的计算量增加，增加了运算的时间不利于种群的多样化，可能收敛解非最优解。解决方法根据某一较小概率0.1-0.2有选择的进展检验与替换。本例中算法已经进展了设计3. 免疫遗传算法。免疫遗传算法在变异以后参加免疫算子，可以大幅减少迭代次数。针对TSP问题，免疫遗传算子设计为先用一个n×2的矩阵存储每一个顶点城市与其相应的最近城市的编号。如阿ai,1的最近城市ai,2。根据TSP问题而言，在最终的解决方案中，即在最正确路径中必然包括或载很大程度上包括了相邻城市间距离的最短路径。将城市ai,2移到ai,1之后，进展免疫检测，如果个体发生退化，取消免疫。免疫遗传算法可以大幅加快迭代的收敛速度减少迭代次数。本实例中没有进展免疫设计4。4. 终止条件。终止条件最常用的有事先给定一个最大进化步数，或者是判断最优化值是否连续假设干步没有明显变化两种。本实例中只选择了第一种方法。可以设定一百次记录一次最优解，当连续三次的解不变或相差不大输出迭代结果。本实例中没有设计。结论论文用遗传算法对TSP问题进展了求解，熟悉遗传算法地算法流程，证明了遗传算法在求解TSP问题时，具有可行性，MATLAB在进展算法优化编程时具有一定的优势。遗传算法在设计过程中要照顾好两个原那么子代要具有父代优良的基因信息即继承性子代要保持群体的多样性，即变异。虽然这两个原那么在设计过程中经常会出现冲突，我们必须统筹的把握。既要实现算法的快速运算，又要实现解的最优。本论文认为对标准遗传算法有进展改经的必要，以提高其求解能力。参考文献1 王凌著，智能优化算法及其应用，清华大学出版社，20012陈国良，王煦法，庄镇圈等.遗传算法及其应用，北京：人民邮电出版社，19963 谢胜利等,基于遗传算法的旅游商问题求解,温州师范学院学报;4阮怀忠,张建中, 基于改良遗传算法的TSP 问题求解,5刘克胜, 邵华, 曹先彬等. 基于免疫算法的TSP 问题求解A . 1999 中国智能自动化学术会议论文6 高经纬，张煦等，求解TSP 问题的遗传算法实现，计算机时代， 2004年第2 期第 16 页