下载文档原格式
用于求解TSP问题的遗传算法改进一、TSP问题简介TSP问题，全称Traveling Salesman Problem，即旅行商问题。
所谓TSP问题是指，给定一些点和每一对点之间的距离，求出一条遍历每个点恰好一次的最短路径，该问题的解决方法对实际问题中的路径规划和优化有着很大的参考价值。
二、遗传算法的基本思想遗传算法，是模拟自然界中生物遗传进化过程的一种演化计算方法。
它通过模拟生物的繁殖、变异、适应性等生命过程来寻找问题的最优解。
其基本的过程如下：1. 初始化：随机生成一个初始群体，每个个体表示一种可能的解决方案。
2. 选择：根据适应度函数，选择一定数量的优秀个体作为繁殖的父亲。
3. 交叉：将所选父亲进行交叉操作，生成新的子代个体。
4. 变异：对于一部分子代个体，进行变异操作。
5. 替换：用新的子代个体替换掉一部分原有的个体，形成新一代群体。
6. 结束条件：当某种条件达到时结束算法，否则返回步骤二。
在TSP问题中，遗传算法的基本实现方法如下：1.初始化：随机生成一个初始群体，每个个体表示一个解决方案，其中每个基因表示一个城市的编号。
例如，假设有10个城市，则每个个体就是由这10个城市编号随机排列组成的，例如：1-2-5-8-4-3-7-9-6-10等。
2.适应度函数：对于每个个体，计算其总路程，将总路程作为适应度函数的值。
4.交叉：将所选父亲进行交叉操作，生成新的子代个体，交叉方式一般有：顺序交叉法、部分映射交叉法、环形交叉法、边交叉法等。
5.变异：对于一部分子代个体，进行变异操作，变异的方式一般是：交换变异、倒位变异、随机抽样变异等。
7.结束条件：当达到一定条件时结束算法，比如迭代次数达到上限或者群体的适应度达到一定的水平。
传统的遗传算法在求解TSP问题时，存在一些问题：1.收敛速度慢：由于集合了交叉、变异等算子，每一代都要进行大量的计算，所以收敛速度慢。
2.易受陷入局部最优解：由于遗传算法采用的是局部搜索策略，所以可能会陷入到局部最优解中。
利⽤遗传算法求解TSP问题⼀、摘要TSP问题是指给定平⾯上N个点及每点的坐标，求⼀条路径，遍历所有的点并回到起点，使这条路径长度最⼩。
TSP问题是⼀个组合优化问题。
该问题可以被证明具有NPC计算复杂性。
因此，任何能使该问题的求解得以简化的⽅法，都将受到⾼度的评价和关注。
遗传算法是⼈⼯智能⽅法的⼀种，⽤于求解各种传统⽅法不⽅便求解或耗时很长的问题。
下⾯给出遗传算法求解TSP问题的步骤。
在传统遗传算法求解TSP的基础上，提出了⼀种新的编码⽅式，并且讨论了⼀种优化⽅法的可⾏性。
本次实验的程序⾸先在matlab上验证了基本的算法，然⽽由于matlab运⾏较慢，故⼜移植到C++平台上，经过测试，实验结果良好。
⼆、算法实现遗传算法的实现主要包括编码、选择、交叉、编译、将个体放⼊新种群这么⼏个步骤，经过很多代的编译求解，以逼近最优解。
下⾯讨论每⼀个步骤的实现，其中编码⽅式是我在考虑了传统编码⽅式不利于计算的缺点下，重新设计的⼀种全新的编码⽅式。
编码在传统TSP问题中，编码可以直接采⽤⼆进制编码或⾃然编码的形式，⽐如直接把城市转化成（2,5,4,1,3,6）的形式，表⽰从2到5到4到1到3到6最后回到起点。
但是在求解TSP问题时，如果直接采⽤此种编码⽅式，会导致在交叉或变异时出现冲突的情况。
如（2,5,4,1,3,6）和（3,5,6,1,2,4）交换后变成了（2,5,6,1,2,6）和（3,5,4,1,3,4），显然路径出现了冲突的现象，传统的解决⽅式是通过逐步调整的⽅法来消除冲突，但是这种⽅法增加了编码的复杂度，不利于问题的求解，根据问题的特点，提出了采⽤⼀种插⼊序号的编码⽅式。
假设6个城市（1,2,3,4,5,6）现在有编码（1,1,2,2,1,3），让第n个编码表⽰n放在第⼏个空格处。
那么⽣成路径的规则是⾸先取1放在第⼀个（1），然后取2放在第⼀个空格处（2，1），然后取3放在第⼆个空格处（2,3,1），然后取4放在第⼆个空格处（2,4,3,1）然后取5放在第⼀个空格处（5,2,4,3,1）最后取6放在第3个空格处（5,2,6，4,3,1）。
目录摘要 (I)Abstract (II)第1章绪论............................................................... - 1 -1.1旅行商问题......................................................... - 1 -1.2研究意义........................................................... - 1 -1.3 论文的组织结构..................................................... - 1 - 第2章遗传算法理论概述................................................... - 2 -2.1遗传算法的起源和发展............................................... - 2 -2.2遗传算法基本原理................................................... - 3 -2.3遗传算法的基本步骤................................................. - 4 -2.4 遗传算法的流程图................................................... - 4 -2.5遗传算法的特点..................................................... - 5 -2.6遗传算法的应用..................................................... - 6 - 第3章 TSP问题及研究的基本方法............................................ - 8 -3.1 TSP问题概述....................................................... - 8 -3.2 TSP的应用与价值................................................... - 8 -3.3 TSP问题的数学模型................................................. - 9 -3.4 TSP 问题的分类..................................................... - 9 -3.5 现有的求解TSP问题的几种算法...................................... - 10 - 第4章遗传算法在TSP的应用.............................................. - 12 -4.1遗传算法在TSP上的应用............................................ - 12 -4.2算法的实现........................................................ - 12 -4.3编码.............................................................. - 12 -4.4初始化种群........................................................ - 13 -4.5适应度函数........................................................ - 13 -4.6选择操作.......................................................... - 13 -4.7交叉操作.......................................................... - 15 -4.8变异操作.......................................................... - 17 -4.9实验结果.......................................................... - 18 - 结论................................................................... - 20 - 展望..................................................................... - 20 - 参考文献.............................................................. - 21 - 致谢................................................................... - 22 - 附录程序................................................................. - 23 -摘要TSP问题(Traveling Salesman Problem)是已知有n个城市，现有一推销员必须遍访这n个城市，且每个城市只能访问一次，最后又必须返回出发城市。
基于遗传算法的TSP问题研究旅行商问题（TSP）是一类NP-hard（非确定性的可能时间指数）问题，涉及到寻找一条最短的路径，以便走遍一系列的城市。
这个问题的例子就像是一个推销员想要在多个城市中寻找到一条能够使他成本最小化并且每个城市只访问一次的路径。
由于旅行商问题的困难度，许多学者和研究者致力于寻找最优解决方案。
在过去的几十年中，各种各样的算法被提出来，其中之一就是遗传算法。
遗传算法的基本原理是模仿自然界中的进化过程。
在这个算法中，候选解决方案根据它们与当前已知最优解的接近情况来进行繁殖和变异。
这种方法通过不断迭代，逐步优化了解决方案。
在TSP领域中，遗传算法已经得到了广泛的应用。
这是因为算法简单易懂，且计算速度快。
但是，它也存在一些缺点。
首先，它对最初种群的设定敏感，因为遗传算法的结果取决于初始的种群。
此外，算法可能会在局部最优解中陷入困境，而无法到达全局最优解。
虽然这些问题存在，但仍有许多研究者尝试改进遗传算法，以提高其效率和准确性。
例如，有些人将变异率设为自适应的变量，以在迭代初期增加变异率，并在迭代后期逐渐减少变异率，以便更好地优化解决方案。
同时，其他一些研究者正在尝试将遗传算法与其他的优化算法相结合，以便更好地解决TSP问题。
特别是，一些研究者使用了禁忌搜索方法，将其与遗传算法结合使用，以避免算法在局部最优解中停滞不前。
总的来说，基于遗传算法的TSP问题研究取得了一些非常有意义的成果。
尽管仍有许多问题需要解决，但这种方法在解决TSP问题中仍然是一种非常有前途的方法。
我们期待在日后的研究中看到更多有关这种算法的创新，以期能够找到真正有效的解决方法。
报告题目：基于Matlab的遗传算法解决TSP问题说明：该文包括了基于Matlab的遗传算法解决TSP问题的基本说明，并在文后附录了实现该算法的所有源代码。
此代码经过本人的运行，没有发现错误，结果比较接近理论最优值，虽然最优路径图有点交叉。
因为本人才疏学浅，本报告及源代码的编译耗费了本人较多的时间与精力，特收取下载积分，还请见谅。
若有什么问题，可以私信，我们共同探讨这一问题。
希望能对需要这方面的知识的人有所帮助！1.问题介绍旅行商问题(Traveling Salesman Problem，简称TSP)是一个经典的组合优化问题。
它可以描述为：一个商品推销员要去若干个城市推销商品，从一个城市出发，需要经过所有城市后，回到出发地，应如何选择行进路线，以使总行程最短。
从图论的角度看，该问题实质是在一个带权完全无向图中。
找一个权值最小的Hemilton回路。
其数学描述为：设有一个城市集合其中每对城市之间的距离(),i j d c c R +∈，求一对经过C中每个城市一次的路线()12,,n c c c ΠΠΠ⋯使()()()1111min ,,n i n i i d c c d c c −ΠΠΠΠ+=+∑其中()12,,12n n ΠΠΠ⋯⋯是，的一个置换。
2.遗传算法2.1遗传算法基本原理遗传算法是由美国J.Holland 教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。
遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。
遗传算法，在本质上是一种不依赖具体问题的直接搜索方法，是一种求解问题的高效并行全局搜索方法。
遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、负载平衡、电磁系统设计、生物科学、社会科学等方面都得到了应用。
用遗传算法求解TSP问题遗传算法（Genetic Algorithm——GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J。
Holland教授于1975年首先提出的。
J.Holland 教授和它的研究小组围绕遗传算法进行研究的宗旨有两个：抽取和解释自然系统的自适应过程以及设计具有自然系统机理的人工系统。
遗传算法的大致过程是这样的:将每个可能的解看作是群体中的一个个体或染色体，并将每个个体编码成字符串的形式，根据预定的目标函数对每个个体进行评价,即给出一个适应度值。
开始时,总是随机的产生一些个体，根据这些个体的适应度，利用遗传算子-—选择（Selection）、交叉（Crossover)、变异（Mutation)对它们重新组合，得到一群新的个体.这一群新的个体由于继承了上一代的一些优良特性，明显优于上一代，以逐步向着更优解的方向进化.遗传算法主要的特点在于：简单、通用、鲁棒性强。
经过二十多年的发展，遗传算法已经在旅行商问题、生产调度、函数优化、机器学习等领域得到成功的应用。
遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比,主要有以下特点：1、遗传算法以决策变量的编码作为运算对象.传统的优化算法往往直接决策变量的实际植本身,而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子.2、遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。
3、遗传算法使用多个点的搜索信息,具有隐含并行性。
4、遗传算法使用概率搜索技术，而非确定性规则。
遗传算法是基于生物学的,理解或编程都不太难。
下面是遗传算法的一般算法步骤:1、创建一个随机的初始状态初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样;在那里,问题的初始状态已经给定了。
基于遗传算法的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之间的距离为ijd，如何选择一条道路使得商人每个城市正好走一遍后回到起点且所走路线最短。
这是一个经典的优化组合问题，它可以扩展到很多问题，如电路布线、输油管路铺设等，但是，由于TSP问题的可行解数目与城市数目N是成指数型增长的，是一个NP-hard问题，即不存在多项式时间算法。
因而一般只能近似求解，遗传算法（Genetic Algorithm,GA）是求解该问题的较有效的方法之一，当然还有如粒子群算法，蚁群算法，神经网络算法等优化算法也可以进行求解。
遗传算法是美国学者Holland根据自然界“物竞天择，适者生存”现象而提出的一种随机搜索算法，本文采用MATLAB来实现遗传算法解决TSP问题。
2 旅行商问题旅行商问题可以具体描述为：已知n个城市之间的相互距离，现有一个推销员从某一个城市出发，必须遍访这n 个城市，并且每个城市只能访问一次，最后又必须返回到出发城市，如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短。
图论模型如图1所示，构造一个图G=(V,e),顶点V表示城市，边e表示连接两城市的路，边上的权()eW表示距离（或时间或费用）。
于是旅行推销员问题就成为在加权图中寻找一条经过每个顶点正好一次的最短圈的问题，即求最佳Hamilton 圈的问题。
ABCDEF452638396859926265738338938794图1 TSP问题的图论模型TSP问题是NP-hard问题，。
也就是说,对于大型网络(赋权图),目前还没有一个精确求解TSP问题的有效算法，因此只能找能求出相当好（不一定最优）的解的算法。
TSP 问题的数学规划模型：设ij d 是i 与j 之间的距离，10或=ij x ，其中1表示连线，0表示不连线，那么整个TSP 问题的数学模型表示如下：v j i v k k x V i x t s x d Z sj i ji j i ij ji ijij ∈⎪⎩⎪⎨⎧⊂-≤∈==∑∑∑∈≠≠,,,1||,1..*min , 式中，k 为v 的全部非空子集；|k|为集合k 中包含图G 的全部顶点个数。
3 遗传算法遗传算法(genetic algorithm ，GA)起源于对生物系统所进行的计算机模拟研究，是一种借鉴生物界自然选择(Nature Selection)和自然遗传机制的随机搜索算法(Random Searching Algorithms)。
其基本流程图如图2所示。
该算法适宜于多峰值空间中的优化求解，能从任一初始化的群体出发，通过随机选择、交叉和变异等遗传操作，使群体逐渐进化到搜索空间越来越好的区域。
遗传算法的应用已从最初的组合优化领域扩展到生产调度、自动控制、机器人学、图像处理、机器学习、数据挖掘等多个领域。
遗传算法应用的关键在于如何结合应用模型构造出染色体以及交叉、变异操作。
3.1 遗传算法的运行过程遗传算法的运算流程如图2所示。
由图2可以看出，使用上述三种遗传算子的遗传算法的主要运算过程如下：（1）编码：解空间中的解数据x ，作为遗传算法的表现型形式。
从表现型到基因型的映射成为编码。
遗传算法在进行搜索之前先将解空间数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合就构成了不同的点。
（2）初始群体的生成：随机产生N 个初始串结构数据，每个串结构数据成为一个个体，N 个个体构成了一个群体。
遗传算法以这N 个串结构作为初始点开始迭代。
设置进化代数器0←t ；设置最大进化代数T ；随机生成M 个个体作为初始群体()0P 。
（3）适应度值评价检测：适应度函数表明个体或解得优劣性。
对于不同的问题，适应度函数的定义方法不同。
根据具体问题，计算群体()t P 中个体的适应度。
（4）进行遗传操作：群体()t P 通过选择、交叉、变异运算后得到下一代群体()1+t P 。
（5）终止条件判断：若T t ≤，则1+←t t ，转到步骤（2）；若T t >，则以进化过程中所得到的最大适应度的个体作为最有解输出，终止运算。
3.2遗传算法的基本操作遗传算法有三个基本操作：选择（Selection ）、交叉（Crossover ）和变异（Mutation ）。
从群体中选择优胜的个体，淘汰劣质的个体的操作叫做选择。
选择算子有时又称为再生算子（reproduction operator ）选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有以下集中：适应度比例方法、随机遍历抽样法、局部选择法。
其中，轮盘赌选择法（roulette wheel selection ）是最简单也是最常用的选择方法。
在该方法中，各个个体的选择概率和其适应值成比例。
设群体大小为n ，其中个体i 的适应值为i f ，则i 被选择的概率为∑==nj i i i f f p 1/显然，概率反映了个体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 ）。
最常用的交叉算子为单点交叉。
具体操作是：在个体串中随机设定一个交叉点，实现交叉时，该点前或后的两个个体的部分结构进行互换，并产生两个新个体。
下面给出了单点交叉的一个例子：新个体个体新个体个体00111110000011:B 10010001111001:A →↑→↑变异算子的基本容是对群体中的个体串的某些基因座上的基因值做变动。
依据个体编码表示方法的不同，可以有以下的算法：实值变异、二进制变异。
一般来说，变异算子操作的基本步骤如下：（1）对群体中所有个体以实事先设定的变异概率判断是否进行变异。
（2）对进行变异的个体随机选择变异位进行变异。
3.3 基本遗传算法的数学模型基本遗传算法（simple genetic algorithm ，SGA ）是一种群体型操作，该操作以群体中的所有个体为对象，只使用基本遗传算子（genetic operator ）：选择算子、交叉算子和变异算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。
基本遗传算法可表示为：),,,,,,,(0T M P E C SGA ψΓΦ=式中，C ：个体的编码方法；E:个体适应度评价函数；0P ：初始种群；M:种群大小；Φ：选择算子；Γ：交叉算子；ψ：变异算子；T:遗传运算终止条件。
图3为基本遗传算法的流程图。
编码和初始种群的生成种群中个体适应度的检测评估选择变异交叉图3 基本遗传算法的流程图4 遗传算法求解TSP 问题实例遗传算法求解TSP 的基本步骤如下： （1）种群初始化。
在解决TSP 问题过程中个体编码方法为实数编码，实数编码为1~n 的实数的随机排列，初始化的参数有种群个数M 、染色体基因个数（即城市的个数）、迭代次数C 、交叉概率c P 、变异概率m P 。
（2）适应度函数。
在TSP 问题中，对于任意两个城市之间的距离),(j i D 已知，每个染色体（即n 个城市的随机排列）可计算出总距离，因此可将一个随机全排列的总距离的倒数作为适应度函数，即距离越短，适应度函数越好，满足TSP 要求。
（3）选择操作。
本文采用轮盘赌法。
（4）交叉操作。
对于个体，随机的选择两个个体，在对应位置交换若干个基因片段，同时保证每个个体依然是1~n 的随机排列，防止进入局部收敛。
（5）变异操作。
对于变异操作，随机选取个体，同时随机选取个体的两个基因进行交换以实现变异操作。
图4 搜索过程图图5 优化后的城市路径如图4所示是用遗传算法进行TSP问题求解的搜索过程图，由图可以看出经过110次左右的搜索，种群已经接近最优解了，在第419代获得最优解。
图5是一个动态显示每次搜索的路径及其所需要的时间，最后输出最优解。
5 结论本文采用MATLAB实现遗传算法求解TSP问题，并根据实验结果进行了分析，遗传算法是一种智能优化算法，它的实现有些关键点，一是串的编码方式，本质就是问题编码，串长度及编码形式对算法收敛影响极大；二是适应函数的确定，这是选择的基础；三是自身参数的设定，其中重要的是群体大小，最大迭代次数，交叉概率和变异概率，通过实验我们可以看到最大迭代次数对问题求解的精度有影响，交叉概率和变异概率的设定对问题的收敛速度和求解精度都有极大的影响，目前很多研究都是根据具体的领域问题，改进交叉算子，变异算子，寻找最优的参数设定来提高算法收敛速度和保证最优解的得到，对算子的改进和参数值的设定这是将来的研究工作。
