应用数学报告

深圳大学课程论文题目多旅行商问题的遗传算法研究成绩专业机械工程课程名称、代码《应用数学》152016040006年级姓名学号时间任课教师1.摘要旅行商问题（TravelingSalesmanProblem，简称TSP）是一个著名的组合优化问题：给定n个城市，有一个旅行商从某一城市出发，访问每个城市各一次后再回到原出发城市，要求找出的巡回路径最短。多旅行商回路（MTSP）是旅行商问题（TSP）扩展。MTSP是指给出N个城市的集合，M个推销商从目标城市出发，分别走一条旅行路线，使得每个城市有且仅有一个推销商走过，最后回到原来的出发城市，且总路程最短。相对于传统的变异方法，此次我们通过增加种群中个体的变异数量，来提高变异程度，从而实现了在更少的迭代次数中使最优解趋于稳定。2.引言遗传算法是一种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与同一群染色体的随机信息变换机制相结合的搜索算法。它通过给解向量编码、形成初始种群，然后用变异、交叉重组、自然选择等算子，进行并行迭代，求的优化解。由于它采用随机运算，对搜索空间无特殊要求，无需求导，具有运算简单、收敛速度快等优点。3.论文内容多旅行商问题根据起点和终点城市的不同，又可以分为四种不同情况，而此次论文中主要研究的是所有旅行商起点和终点城市都相同的这种情况。此次，论文中提出了一种新的GA染色体编码方式及相关的变异操作方法(Two-partchromosometechnique)，并且将此方法与以前的方法在理论性能和计算性能上做比较，通过计算测试发现该方法具有更小的搜索空间，同时具有更好的适值解，相对于另外两种传统编码方式。3.1编码方式论文主要提出了3种了编码方法，可以通过下面3个图形来表示它们各自不同的编码方式。第一种编码方式：Onechromosome（上图中正数代表城市排列，负数代表分隔符，将城市划分M块）12-1578-2364第二种编码方式：Twochromosome（上图中第一个排列代表城市排列，第二个代表每个城市所对应的旅行商）第三中编码方式：Two-partchromosome（图中上面的代表城市排列，下面的代表城市分割位置）3.2、从两个方面论证该种编码方式具有更好的求解优势A.从搜索空间上看优势体现三种编码方式下的解空间大小如下表所示：以上是在三种不同的编码方式下解空间大小通过图形表示如下：12578364223133211265784343可见Two-partchromosometechnique方式具有更小的解空间。B.从最终的适值解上分析论文中通过给定不同的城市数，分别在三种不同编码方式下，进行多旅行商最优值的求解，并在图形上显示出来，具体结果如下图：1、城市数固定为51最小的总旅程距离最长的那个旅行商的最小距离2、城市数固定为1003、城市数固定为150上图中绿线是本论文所提出的一种方法，另外两条线是传统方法，从图中可以看出，绿线在不同的情况下都表现出了良好适值解。同时，由于在现实世界中的问题可能会更感兴趣的减少最长的单个旅行商的旅行距离，所以右侧的三个图分别分析了单个旅行商的旅行距离，通过观察发现，其同样具有很好的适值解。4.实现过程由于前面论文中已经给出了一种最优的编码方式，所以此次我们采用的也是前面论文中所提出的一种编码方式来实现程序的编写。4.1实现流程大致过程可以分为以下几步：1、初始化种群：通过randperm(n)+1产生随机2-n的随机序列号，根据min_tour求插入点位置位置序列，用二者来充当初始化的个体，以此组成种群。2、根据n个城市的位置信息，求一个n*n的距离矩阵，用来充当后续的个体序列求距离时的元素间距离索引。3、通过双重循环来求出种群序列所对应的旅行长度，并将索引值，序列号，旅行长度三者关联起来，用于后续的变异操作时的索引。同时求出本次种群中的最优个体（旅行长度最小），并通过序列号画出线路图。4、通过一个循环，以步长为10，每次进入循环之后从种群中选取10个个体，然后找到10个个体中的最优个体，并内嵌一个循环次数为10的循环结构，用来对每次的最优个体进行9次变异，和1次不变异，因而用新的10个个体代替以前的10个个体，来形成下一个种群。其中，由于形成的10个变异个体中都会有1个个体不变异，也就是说下一代种群中都会存在一部分上一代种群中的最优的部分个体，所以最优解永远会趋于收敛。5、通过迭代次数来控制变异是否结束。流程图如下：4.2变异方法从种群中每10个个体中取出一个最优个体，进行遗传变异操作，从前面我们知道我们实质上是从一个最优个体变异产生9个不同的变异个体，以下是最优个体对应的9中不同变异方法。A、元素序列变异1、元素互换x、y元素互换2、元素倒置m、n、k倒序排列3、元素插入X元素插入到y后4、整体互换将abefg排列改为efgabB、插入点变异根据最小旅行要求随机产生插入点序列。C、插入点和序列号同时变异（4种）插入点重复前面的序列变异方法，但同时加入插入点变异。所有加一起总共可以产生9种不同的变异，还有一个最优个体不变异，因此，通过一个个体产生了10个不同的下一代个体，用于形成下一代种群。5.结果分析此次程序设计中还是延续了前人的一些设计经验，但在变异部分增加了变异的程度，对应增加了两种变异方式，以前通常会选择7种变异，此次我们增加到9种。也就是以前是从1个个体中产生8个变异个体，而我们是从1个个体产生10个变异个体，通过仿真发现增大变异程度，最优解会在较少的迭代次数中趋于稳定。现分别做了一个仿真比较，如下图：此次采用30个城市，5个旅行商，最少旅行5个城市来做比较。前人的结果：改变之后的结果：可以发现，在增大变异程度之后，种群最优路径值会在短时间内将路径值降低到很小然后再慢慢平稳降低，最后趋于稳定。因此，如果想要在短时间内找近似最优值，可以采用增大变异程度来实现；如果想要不计较迭代时间，只是想要实现平稳趋近最优值，可以采用减小变异程度，来实现最优路径求解。6.参考文献1、ArthurE.Carter,CliffT.Ragsdale.Anewapproachtosolvingthemultipletravelingsalespersonproblemusinggeneticalgorithms.EuropeanJournalofOperationalResearch175(2006)246-2572、陶然，吕红霞，陈广秀．基于MTSP的机车周转图编制模型与算法[J]．西南交通大学学报，2006，41(5)：653-657．3、王海龙.周辉仁.郑丕谔.唐万生.WANGHai-long.ZHOUHui-ren.ZHENGPie.TANGWan-sheng基于遗传算法的多旅行商问题研究[期刊论文]-计算机应用研究2009,26(5)4、周辉仁.唐万生.魏颖辉.ZHOUHui-ren.TANGWan-sheng.WEIYing-hui基于GA的最小旅行时间的多旅行商问题研究[期刊论文]-计算机应用研究2009,26(7)