《遗传算法在求解最短路径问题中的研究应用.doc》由会员分享，可在线阅读，更多相关《遗传算法在求解最短路径问题中的研究应用.doc（15页珍藏版）》请在金锄头文库上搜索。
1、智能优化计算及应用课考核论文 第 16 页 遗传算法在求解最短路径问题中的研究应用 摘 要TSP 问题是典型的NP完全问题,遗传算法是求解NP完全问题的一种常用方法。本文针对解决TSP 问题,在MATLAB中用遗传算法施行对TSP问题进行了求解，进行了选择、交叉和变异算子进行了算法设计，最后在JAVA软件上进行编程实现。最后探讨了遗传算法解决旅行商问题自身具备的特点1。关键词：遗传算法；TSP问题；JAVA软件SOLVING TSP (Travelling Salesman Problem ) BASED ON GENETIC ALGORITHMAuthor : Zong Man-yi Tut
2、or : 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
3、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概述4
4、2旅行商问题(TSP)43 用遗传算法解决旅行商问题54 论文的主要构成5遗传算法的设计61问题分析62 总体设计73 详细设计83.1 编码与随机和初始群体生成83.2 城市位置及距离矩阵和适应度函数83.4 选择93.4 交叉93.5 变异103.6 群体的跟新和终止条件10MATLAB编程验证111MATLAB计算112算法分析优化13结论15参考文献16引言1 GA概述遗传算法(Genetic Algorithm , GA ) 是由美国J. Holland 教授提出的一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。它起源于达尔文的进化论, 是模拟达尔文的遗传选择和自然淘汰的生物进
5、化过程的计算模型。其主要特点是群体搜索策略和群体中个体之间的信息交换, 搜索不以梯度信息为基础。它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题, 可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。作为一种全局优化搜索算法, 遗传算法以其简单通用、鲁棒性强、适于并行处理以及应用范围广等特点, 使其成为21 世纪智能计算核心技术之一。进入80 年代, 遗传算法迎来了兴盛发展时期, 无论是理论研究还是应用研究都成了十分热门的话题2。2旅行商问题(TSP)一个有名的组合优化问题就是旅行商问题(Travelling Salesman Problem , TSP)。TSP问题是
6、典型的、易于描述却难以处理的组合优化问题。由于遗传算法方法的本质是处理复杂问题的一种鲁棒性强的启发性随机搜索算法, 故而利用遗传算法求解这类问题是有效的。假设平面上有n个点代表n个城市的位置, 寻找一条最短的闭合路径, 使得可以遍历每一个城市恰好一次。这就是旅行商问题。旅行商的路线可以看作是对n个城市所设计的一个环形, 或者是对一列n个城市的排列。由于对n个城市所有可能的遍历数目可达(n- 1)!个, 因此解决这个问题需要0(n!)的计算时间。假设每个城市和其他任一城市之间都以欧氏距离直接相连。也就是说, 城市间距可以满足三角不等式, 也就意味着任何两座城市之间的直接距离都小于两城市之间的间接
7、距离。是一个典型的优化组合问题3。3 用遗传算法解决旅行商问题目前针对TSP问题有许多种解法，较为常用的算法有神经网络法、列表寻优法、二叉树描述法、模拟退火法和遗传算法等等。遗传算法是近几年发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观点，通过选择、遗传、变异和免疫等作用机制，使每个个体的适应性提高。由于其全局搜索的特性，遗传算法在解决TSP问题中有着其他算法所没有的优势。提出的TSP问题包括31个城市的编号和各自的位置。本文针对这个TSP问题进行了遗传算法的编程和求解。4 论文的主要构成本论文在MATLAB中用遗传算法施行对TSP问题进行了求解，进行了选择、交叉和变异、免疫等算子进
8、行了算法设计，最后在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的距离.（图 1）3本实例中设定了我国31个省会城市，当一个旅行商彼遍历了所有城市后回到出发城市，求其最短路径的走法。一个最容易想到的方法
9、是利用排列组合的方法把所有的路径都计算出来，并逐一比较，选出最小的路径。虽然该方法在理论上是可行的，但路径的个数与城市的个数成指数增长，当城市个数较大时，该方法的求解时间是难以忍受的，甚至是不可能完成的，31个城市所有路径个数是30！个。由于其全局搜索的特性，遗传算法在解决TSP问题中有着其他算法所没有的优势。本文针对这个TSP问题进行了遗传算法的编程和求解。2 总体设计（图 2）标准遗传算法的流程图标准的遗传算法包括群体的初始化，选择，交叉，变异操作。其主要步骤可描述如下1：（1）随机产生一组初始个体构成的初始种群，并评价每一个个体的适配值。（2）判断算法的收敛准则是否满足。若满足输出搜索结
10、果；否则执行以下步骤。（3）根据适配值大小以一定方式执行选择操作。（4）按交叉概率Pc执行交叉操作.（5）按变异概率Pm执行变异操作。（6）返回步骤（2）。 本TSP问题的遗传算法总体设计（图3）总体设计说明：（1）本算法的判断结束准则是固定指定了迭代的次数当算法达到迭代次数时，算法结束，输出当前的最优解（2）在根据适配值计算并选择的时候，记录下来的当前最优值，在变异后加入跟新的群体，保证新的迭代循环中TSP解越来越好（不会变差）。（3）在选择的一种操作是拿最优的K个替换最差的K个个体，本例是按适配值选择，并使群体数目变少，当每次变异操作后，产生随机路径补充群体是群体数目不变，再次循环，一定程
11、度上防止因初始群体的选择问题而陷入局部最优。3 详细设计-个体数 103.1 编码与随机和初始群体生成 给所有城市编码，以城市的遍历次序作为遗传算法的编码。在MATLAB中使用 randperm(N)产生一个1N 的矩阵（N为所有城市的个数，本例中为31）为一个随机路径。利用nN矩阵存储n个随机群体产生初始群体。3.2 城市位置及距离矩阵和适应度函数 距离d(i-1,j-1)= sqrt(（Xi-Xj）.2+(Yi-Yj).2)城市的位置为编译前指定，也可以使用随机生成的坐标参数。距离矩阵使用一个NN矩阵D存储，D（i，j）代表城市 i和城市j之间的距离。D（i，j）=sqrt(（Xi-Xj）
12、.2+(Yi-Yj).2)在该问题的求解中，用距离的总和来衡量适应度，距离的总和越大，适应度越小，进而探讨求解结果是否最优。每个个体（每条路径距离）总合计算公式为：len=d(1,9);len=D(1,N);for i=1:(N-1) for(i=0,i8;i+) len+=d(I,i+1); len=len+D(i,i+);endlen纪录总路径格式n1 len(i)代表第i个个体（路径）距离总合。3.4 选择选择 choice()选择操作是为了避免有效基因的损失，使高性能的个体得以更大的几率生存，从而得到全局收敛性和计算效率。本例中使用的适配值函数为 fitness(i,1)=(1-(le
13、n(i,1)-minlen)/(maxlen-minlen+0.0001).m;% maxlen ，minlen为最大和最短路径利用fitnessrand选择个体，将个体，将较小路径(适应度较大)个体选择下来。但这种算法的群体的个体数目变小并且较优的个体个数较少， 可能收敛的数目变慢，在算法调试的过程中证明了这一点4。3.4 交叉交叉 mutual()交叉操作用于组合出新的个体，再借空间中进行有效的搜索，同时降低有效模式的破坏概率1。本实例中交叉采用部分匹配交叉策略,其基本实现的步骤是：步骤1： 随机选取两个交叉点步骤2： 将两交叉点中间的基因段互换步骤3： 将互换的基因段以外的部分中与互换后
14、基因段中元素冲突的用另一父代的相应位置代替，直到没有冲突。本例中路径实例如图交叉点为2，7，交换匹配段后A中冲突的有7 、6、5，在B的匹配段中找出与A匹配段中对应位置的值7-3，6-0，5-4，继续检测冲突直到没有冲突。对B 做同样操作，得到最后结果。（图 4）3.5 变异 变异类 swap()变异操作通过随机改变个体中某些个体的某些基因而产生新个体，有助于增加种群的多样性，避免早熟收敛（非全局最优）。本例中变异操作使用互换操作算子（SWAP），即随机交换染色体中两个不同基因编码的位置，SWAP相对于INV（逆序操作）和INS（插入操作）更有利于算法的大范围搜索。对于一个31路径的染色体的变异操作，依变异概率确定是否变异，随机选择路径上的两个城市进行交换。例如 变异交换位置为2和83.6 群体的跟新和终止条件为保证计算随迭代次数的增加，最优解越来越好，本例种每次变异后将每次的上次迭代最优解加入群体，防止因交叉或变异而是最优解失去，出现退化现象。为保持群体数目不变，变异后产生随机解加入群体（本算法群体数目仔选择中可能发生减少）。终止条件最常用的有事先给定一个最大进化步数，或者是判断最优化值是否连续若干步没有明显变化两种。本实例中只选择了第一种方法6。MATLAB编程验证1JAVA计算1初始值（图 5）种群个数n=100;迭代次
