遗传算法在tsp问题中的应用

《遗传算法在tsp问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、遗传算法在TSP问题中的应用周师专（南昌大学信息工程学院软件工程416116114082）摘要：旅行商问题是研究最为广泛的组合优化问题，在现实生活中，也有着广泛的应用。遗传算法是一种有效的解决优化问题的方法。遗传算法是求解NP完全问题的一种常用方法，它在解决排列组合问题方面占有很重要的地位。本文针对旅行商问题，分别对个体的基因编码、适应值，以及选择、交叉、变异算子进行了设计，将此程序应用到旅行商问题的研究中。关键词：遗传算法；旅行商问题；交叉；变异；组合优化引言旅行商问题（TravellingSalesmanProblem）是数学领域中著名问题之一

2、，可描述为:有一个旅行商人要拜访个城市，从〃个城市中的某一城市出发，不重复地走完其余n-1个城市并回到原山发点，在所有可能路径中求岀路径长度最短的一条。TSP问题是一个相当古老的优化问题，在过去的10年中，出现了一些逼近最优解的算法：最近邻居、贪婪算法、最近插入、最远插入、双最小生成树、带解法、空间充填曲线算法等。而后來发展起來的遗传算法，是一种求解M题的高效并行全局搜索方法，能够解决复杂的全局优化问题。一、遗传算法概述遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自

3、然进化过程（适者生存，优胜劣汰遗传机制）搜索最优解的方法，通常用来生成有用的解决方案来优化和搜索问题。从选定的初始解山发,通过不断地迭代，逐步优化当前解，直到最后搜索到最优解或满意解。其迭代过程是从一纽初始解（群体）出发，采用类似于自然选择和有性繁殖的方法，在继承原有优良基因的基础上生成具有更好性能的丁一代解的群体。遗传算法的基本运算过程如卜‘：a）初始化：设置进化代数计数器F0,设置最大进化代数7；随机生成个个体作力初始群体汽0）。b）个体评价：计算群体中各个个体的适应度。C)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一

4、代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算:将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。群体经过选择、交叉、变异运算之后得到下一代群体八01人e)变异运算:将变异算子作川于群体。即是对群体屮的个体串的某些基因座上的基因值作变动。f)终止条件判断:若则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。运算停止。算法流程图如图1所示。图1二、问题分析TSP问题就是寻找一条最短的遍历n个城市的最短路径，即搜索自然数子集W={1,2,…，n}(W的元素表示对n个城市的

5、编号)的一个排列it(W)={VI，V2,…，Vn},使len=Sd(Vi,Vi+1)+d(VI,Vn)取最小值，式中的d(Vi,Vi+1)表示城市Vi到城市Vi+1的距离。遗传算法是具有“生成+检测”的迭代过程的搜索算法。该操作以群体中的所有个体为对象。选择(Selection)、交叉(Crossover)和变异(Mutation)是遗传•算法的3个主要操作算子，它们构成了所谓的遗传操作(geneticoperation),使遗传算法具有了其它传统方法所没有的特性。遗传算子包含如下6个基本因素：(1)参数编码：由于遗传算法不能直接处理解空间的解数

6、据，因此必须通过编码将它们表示成遗传空间的基因型串结构数据。巾于旅行商问题的解是一个序列，且序列的内容相同顺序不同，所以二进制编码对TSP不是最适合的。这里以城市的遍历次序作为算法编码，即(il,i2,…，in)是{1,2,…,n}的全排列。(1)生成初始群体：由于遗传算法的群体型操作需要，所以必须为遗传操作准备一个由若干初始解组成的初始群体。初始群体的每个个体都是通过随机方法产生。(2)适应度评估检测：遗传算法在搜索进化过程屮仅用适应度(ntness)值来评估个体或解的优劣，并作为以后遗传操作的依据。巾于用个体r相对应的哈密顿圈长的倒数作力适应度

7、较大，容易早收敛而得到局部最优解，所以川exp(-evaluate(father[i]))作为适应度函数，其中father[i]为种群中的一个个体，evaluate()是一个序列中城市之间的距离总和。(3)选择(selection):选择或复制操作是为了从当前群体屮选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。个体适应度越高，其被选择的机会就越多。此处采用与适用度成比例的轮盘赌方法进行选择。(4)交叉操作：交叉操作是遗传算法屮最主要的遗传操作。可分两步进行：首先对种群屮个体进行随机配对;其次，在配对个体屮随机设定交叉处，配对个体彼此交换部分

8、信息。(5)变异：变异操作是按位(bit)进行的，即把某一位的内荇进行变异。由于TSP问题的解是一个序列，所以由一个解序列