基于遗传算法的TSP问题研究.doc

基于遗传算法的TSP问题研究摘要：旅行商问题是一个经典的优化组合问题，本文采用遗传算法来求解旅行商问题，深入讨论了遗传算法解决TSP问题的求解过程，并通过MATLAB对算法进行了实现，最后对实验结果进行分析。关键字： 旅行商问题； 遗传算法Abstract:The traveling salesman problem is a classic optimal combination problem. In this paper, we use genetic algorithm to solve the TSP problem.We discusse the solving process, and the algorithm is realized by MATLAB. Finally, the experimental results are analyzed.Key words: Traveling Salesman Problem; Genetic Algorithm1 引言旅行商问题（Traveling Salesman Problem,TSP）的原始问题为：一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为，如何选择一条道路使得商人每个城市正好走一遍后回到起点且所走路线最短。这是一个经典的优化组合问题，它可以扩展到很多问题，如电路布线、输油管路铺设等，但是，由于TSP问题的可行解数目与城市数目N是成指数型增长的，是一个NP-hard问题，即不存在多项式时间算法。因而一般只能近似求解，遗传算法（Genetic Algorithm,GA）是求解该问题的较有效的方法之一，当然还有如粒子群算法，蚁群算法，神经网络算法等优化算法也可以进行求解。遗传算法是美国学者Holland根据自然界“物竞天择，适者生存”现象而提出的一种随机搜索算法，本文采用MATLAB来实现遗传算法解决TSP问题。2 旅行商问题旅行商问题可以具体描述为：已知n个城市之间的相互距离，现有一个推销员从某一个城市出发，必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回到出发城市，如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短。图论模型如图1所示，构造一个图G=(V,e),顶点V表示城市，边e表示连接两城市的路，边上的权表示距离（或时间或费用）。于是旅行推销员问题就成为在加权图中寻找一条经过每个顶点正好一次的最短圈的问题，即求最佳Hamilton 圈的问题。图1 TSP问题的图论模型TSP问题是NP-hard问题，。也就是说,对于大型网络(赋权图),目前还没有一个精确求解TSP问题的有效算法，因此只能找能求出相当好（不一定最优）的解的算法。TSP问题的数学规划模型：设是i与j之间的距离，其中1表示连线，0表示不连线，那么整个TSP问题的数学模型表示如下：式中，k为v的全部非空子集；|k|为集合k中包含图G的全部顶点个数。3 遗传算法遗传算法(genetic algorithm，GA)起源于对生物系统所进行的计算机模拟研究，是一种借鉴生物界自然选择(Nature Selection)和自然遗传机制的随机搜索算法(Random Searching Algorithms)。其基本流程图如图2所示。该算法适宜于多峰值空间中的优化求解，能从任一初始化的群体出发，通过随机选择、交叉和变异等遗传操作，使群体逐渐进化到搜索空间越来越好的区域。遗传算法的应用已从最初的组合优化领域扩展到生产调度、自动控制、机器人学、图像处理、机器学习、数据挖掘等多个领域。遗传算法应用的关键在于如何结合应用模型构造出染色体以及交叉、变异操作。3.1 遗传算法的运行过程遗传算法的运算流程如图2所示。图2 遗传算法的运算流程由图2可以看出，使用上述三种遗传算子的遗传算法的主要运算过程如下：（1） 编码：解空间中的解数据x，作为遗传算法的表现型形式。从表现型到基因型的映射成为编码。遗传算法在进行搜索之前先将解空间数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合就构成了不同的点。（2） 初始群体的生成：随机产生N个初始串结构数据，每个串结构数据成为一个个体，N个个体构成了一个群体。遗传算法以这N个串结构作为初始点开始迭代。设置进化代数器；设置最大进化代数T；随机生成M个个体作为初始群体。（3） 适应度值评价检测：适应度函数表明个体或解得优劣性。对于不同的问题，适应度函数的定义方法不同。根据具体问题，计算群体中个体的适应度。（4） 进行遗传操作：群体通过选择、交叉、变异运算后得到下一代群体。（5） 终止条件判断：若，则，转到步骤（2）；若，则以进化过程中所得到的最大适应度的个体作为最有解输出，终止运算。3.2遗传算法的基本操作遗传算法有三个基本操作：选择（Selection）、交叉（Crossover）和变异（Mutation）。从群体中选择优胜的个体，淘汰劣质的个体的操作叫做选择。选择算子有时又称为再生算子（reproduction operator）选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有以下集中：适应度比例方法、随机遍历抽样法、局部选择法。其中，轮盘赌选择法（roulette wheel selection）是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应值成比例。设群体大小为n，其中个体i的适应值为，则i被选择的概率为显然，概率反映了个体i的适应值在整个群体的个体适应值总和中所占的比例。个体适应度越大，其被选择的概率就越高，反之亦然。交叉是把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。交叉算子根据交叉概率将群体中的两个个体随机的交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。根据编码表示的方法不同，可以有以下算法：（1） 实值重组（real valued recombination）：离散重组（discrete recombination）、中间重组（intermediate recombination）、线性重组（linear recombination）、扩展线性重组（extended linear recombination）。（2） 二进制交叉（binary valued crossover）：单点交叉（single-point crossover）、多点交叉（multiple-point crossover）、均匀交叉（uniform crossover）、洗牌交叉（shuffle crossover）。最常用的交叉算子为单点交叉。具体操作是：在个体串中随机设定一个交叉点，实现交叉时，该点前或后的两个个体的部分结构进行互换，并产生两个新个体。下面给出了单点交叉的一个例子：变异算子的基本内容是对群体中的个体串的某些基因座上的基因值做变动。依据个体编码表示方法的不同，可以有以下的算法：实值变异、二进制变异。一般来说，变异算子操作的基本步骤如下：（1） 对群体中所有个体以实事先设定的变异概率判断是否进行变异。（2） 对进行变异的个体随机选择变异位进行变异。3.3 基本遗传算法的数学模型基本遗传算法（simple genetic algorithm，SGA）是一种群体型操作，该操作以群体中的所有个体为对象，只使用基本遗传算子（genetic operator）：选择算子、交叉算子和变异算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。基本遗传算法可表示为：式中，C：个体的编码方法；E:个体适应度评价函数；：初始种群；M:种群大小；：选择算子；：交叉算子；：变异算子；T:遗传运算终止条件。图3为基本遗传算法的流程图。图3 基本遗传算法的流程图4 遗传算法求解TSP问题实例遗传算法求解TSP的基本步骤如下：（1）种群初始化。在解决TSP问题过程中个体编码方法为实数编码，实数编码为1n的实数的随机排列，初始化的参数有种群个数M、染色体基因个数（即城市的个数）、迭代次数C、交叉概率、变异概率。（2） 适应度函数。在TSP问题中，对于任意两个城市之间的距离已知，每个染色体（即n个城市的随机排列）可计算出总距离，因此可将一个随机全排列的总距离的倒数作为适应度函数，即距离越短，适应度函数越好，满足TSP要求。（3） 选择操作。本文采用轮盘赌法。（4） 交叉操作。对于个体，随机的选择两个个体，在对应位置交换若干个基因片段，同时保证每个个体依然是1n的随机排列，防止进入局部收敛。（5） 变异操作。对于变异操作，随机选取个体，同时随机选取个体的两个基因进行交换以实现变异操作。图4 搜索过程图图5 优化后的城市路径如图4所示是用遗传算法进行TSP问题求解的搜索过程图，由图可以看出经过110次左右的搜索，种群已经接近最优解了，在第419代获得最优解。图5是一个动态显示每次搜索的路径及其所需要的时间，最后输出最优解。5 结论本文采用MATLAB实现遗传算法求解TSP问题，并根据实验结果进行了分析，遗传算法是一种智能优化算法，它的实现有些关键点，一是串的编码方式，本质就是问题编码，串长度及编码形式对算法收敛影响极大；二是适应函数的确定，这是选择的基础；三是自身参数的设定，其中重要的是群体大小，最大迭代次数，交叉概率和变异概率，通过实验我们可以看到最大迭代次数对问题求解的精度有影响，交叉概率和变异概率的设定对问题的收敛速度和求解精度都有极大的影响，目前很多研究都是根据具体的领域问题，改进交叉算子，变异算子，寻找最优的参数设定来提高算法收敛速度和保证最优解的得到，对算子的改进和参数值的设定这是将来的研究工作。参考文献：1傅颖勋.遗传算法的研究与改进D.北京:北京邮电大学,2010:5-72武斌.遗传算法求解TSP问题的研究J.中国石油大学胜利学院学报, 2014 (3):23-253周敏.遗传算法求解TSP的研究J.无线互联科技,2015(3):128-1294张雁翔,祁育仙.改进遗传算法求解TSPJ.山西电子技术,2016(1):28-305高玮.现代智能仿生算法及其应用M,科学出版社,20116Coomi,Dorigo,Maniezzo.Distributed optimization by ant colonies. In Proc of the First European Con# On Artificial LifeR.Paris Franee:Elsevier Publishing, 2011:134-1427Dorigo M.,Maniezzo D.,Colormi.Ant System:Optimization by a Colony of Cooperation AgentsJ.IEEE Trans.On systems Man,and Cybernetics, 2010 (1): 29-418Holland J.Adaptation in Natural and ArtificialSystemsJ.Cambridge,MA:MIT press,20129Holland H. J.Concerning Efficient Adaptive SystemsJ.In Yovits, M.C, Ed Self-Organizing Systems, 2008: 215-23010Bremermann.Optimization Through Evolution a