应用数学报告.docx

《应用数学报告.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、深圳大学课程论文题目多旅行商问题的遗传算法研究成绩专业机械工程课程名称、代码《应用数学》6年级姓名学号时间任课教师1.摘要旅行商问题（TravelingSalesmanProblem，简称TSP）是一个著名的组合优化问题：给定n个城市，有一个旅行商从某一城市出发，访问每个城市各一次后再回到原出发城市，要求找出的巡回路径最短。多旅行商回路（MTSP）是旅行商问题（TSP）扩展。MTSP是指给出N个城市的集合，M个推销商从目标城市出发，分别走一条旅行路线，使得每个城市有且仅有一个推销商走过，最后回到原来的出发城市，且总路程最短。相对于传统的变异方

2、法，此次我们通过增加种群中个体的变异数量，来提高变异程度，从而实现了在更少的迭代次数中使最优解趋于稳定。2.引言遗传算法是一种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与同一群染色体的随机信息变换机制相结合的搜索算法。它通过给解向量编码、形成初始种群，然后用变异、交叉重组、自然选择等算子，进行并行迭代，求的优化解。由于它采用随机运算，对搜索空间无特殊要求，无需求导，具有运算简单、收敛速度快等优点。3.论文内容多旅行商问题根据起点和终点城市的不同，又可以分为四种不同情况，而此次论文中主要研究的是所有旅行商起点和终点城市都相同的这种

3、情况。此次，论文中提出了一种新的GA染色体编码方式及相关的变异操作方法(Two-partchromosometechnique)，并且将此方法与以前的方法在理论性能和计算性能上做比较，通过计算测试发现该方法具有更小的搜索空间，同时具有更好的适值解，相对于另外两种传统编码方式。3.1编码方式论文主要提出了3种了编码方法，可以通过下面3个图形来表示它们各自不同的编码方式。第一种编码方式：Onechromosome12-1578-2364（上图中正数代表城市排列，负数代表分隔符，将城市划分M块）第二种编码方式：Twochromosome125783

4、6422313321（上图中第一个排列代表城市排列，第二个代表每个城市所对应的旅行商）第三中编码方式：Two-partchromosome1265784343（图中上面的代表城市排列，下面的代表城市分割位置）3.2、从两个方面论证该种编码方式具有更好的求解优势A.从搜索空间上看优势体现三种编码方式下的解空间大小如下表所示：以上是在三种不同的编码方式下解空间大小通过图形表示如下：可见Two-partchromosometechnique方式具有更小的解空间。A.从最终的适值解上分析论文中通过给定不同的城市数，分别在三种不同编码方式下，进行多旅行

5、商最优值的求解，并在图形上显示出来，具体结果如下图：1、城市数固定为51最小的总旅程距离最长的那个旅行商的最小距离2、城市数固定为1003、城市数固定为150上图中绿线是本论文所提出的一种方法，另外两条线是传统方法，从图中可以看出，绿线在不同的情况下都表现出了良好适值解。同时，由于在现实世界中的问题可能会更感兴趣的减少最长的单个旅行商的旅行距离，所以右侧的三个图分别分析了单个旅行商的旅行距离，通过观察发现，其同样具有很好的适值解。1.实现过程由于前面论文中已经给出了一种最优的编码方式，所以此次我们采用的也是前面论文中所提出的一种编码方式来实现

6、程序的编写。4.1实现流程大致过程可以分为以下几步：1、初始化种群：通过randperm(n)+1产生随机2-n的随机序列号，根据min_tour求插入点位置位置序列，用二者来充当初始化的个体，以此组成种群。2、根据n个城市的位置信息，求一个n*n的距离矩阵，用来充当后续的个体序列求距离时的元素间距离索引。3、通过双重循环来求出种群序列所对应的旅行长度，并将索引值，序列号，旅行长度三者关联起来，用于后续的变异操作时的索引。同时求出本次种群中的最优个体（旅行长度最小），并通过序列号画出线路图。4、通过一个循环，以步长为10，每次进入循环之后从种

7、群中选取10个个体，然后找到10个个体中的最优个体，并内嵌一个循环次数为10的循环结构，用来对每次的最优个体进行9次变异，和1次不变异，因而用新的10个个体代替以前的10个个体，来形成下一个种群。其中，由于形成的10个变异个体中都会有1个个体不变异，也就是说下一代种群中都会存在一部分上一代种群中的最优的部分个体，所以最优解永远会趋于收敛。5、通过迭代次数来控制变异是否结束。流程图如下：4.2变异方法从种群中每10个个体中取出一个最优个体，进行遗传变异操作，从前面我们知道我们实质上是从一个最优个体变异产生9个不同的变异个体，以下是最优个体对应的

8、9中不同变异方法。A、元素序列变异1、元素互换x、y元素互换2、元素倒置m、n、k倒序排列3、元素插入X元素插入到y后4、整体互换将abefg排列改为efgabB、