基于Matlab的遗传算法研究分析信息管理与信息系统专业.docx

《基于Matlab的遗传算法研究分析信息管理与信息系统专业.docx》由会员分享，可在线阅读，更多相关《基于Matlab的遗传算法研究分析信息管理与信息系统专业.docx（52页珍藏版）》请在课桌文档上搜索。

1、基于Matlab的遗传算法研究第3章遗传算法研究遗传算法的求解思路是首先进行编码操作，然后随机产生一个种群，进而选择适应函数也就是目标函数，进行三种不同的遗传操作，然后进行迭代，如果迭代满足收敛的条件，那么得到最优结果，迭代结束，否则继续进行迭代，继续看是不是满足收敛的条件，如果不满足，则继续迭代，直到满足为止，进而求得最优解。具体就是对于求出来多个Xi,计算出对应的fi,求出其中最小的/(小n)对应的Xmin就是最优解。3.1目标函数的选取及其处理遗传算法在初始阶段具有很快的下降速度，但是在算法迭代后期，由于梯度变化值很小，导致函数收敛速度很慢，迭代次数很多。假设性能函数Rx)是误差平方和，

2、即/(X)=Iy(X)=V(XyV(X)(3-1)/=1式中，X是参数向量，V是误差向量。要使性能函数最小，根据遗传算法可以得知，参数向量迭代更新至最优值，参数向量更新公式：XM=x-jr(XJJ(XJ+丁JT(XJV(XJ(3-2)式中，表示第4+1次迭代更新后的参数向量；XA表示第2次迭代的参数向量；4表示第2次迭代的学习率；I是单位矩阵；J(X)是JaCobian矩阵:如（X）SH(X)如（X）dxx2西加2（X）加()MX)J(X)=xlx2dn(3-3):M(X)M(X)v()xlSx2算法特点：当从增加时，它接近于有小的学习速度的最速下降法:xu =x-jf(x0v(x0(3-4)

3、当从下降到0的时候，算法变成了高斯牛顿方法。该算法具有梯度法和高斯牛顿法共同的优点，在算法初始阶段具有梯度法的下降速度，在接近误差极小值时,具有高斯牛顿法的优点，收敛速度快。3. 2遗传算法的基本步骤在求函数最大值问题或者是求最小值问题的时候，一般情况之下都是可以表达为以下的数学规划模型：max f(x)XERRSU(3-5)mi11/(x)XeR或者ReU其中，f（x）为遗传算法的目标函数，X,R,U的相关性条件为约束条件，其中具体的满足约束条件的解为可行解。具体的遗传算法的步骤如下所示：1、具体的遗传算法的先随机产生种群。2、确定具体的个体的适应度也就是目标函数，判断个体的适应度是否符合优

4、化准则，如果符合优化准则，那么就可以直接输出最佳个体还有输出其最优解,结束，如果不符合优化准则，进行下一步。3、依据具体的个体适应度进行选择再生个体，根据算法的适者生存的原则可以有适应度高的个体毫无疑问被选中的概率就相应的高一些，适应度低的个体就相应的被淘汰。4、根据遗传学之中交叉的规则，按照一定的交叉概率以及具体的交叉方法，进一步的生成新的个体。5、根据遗传学之中变异的规则，可以按照一定的变异概率以及具体的变异方法，同样可以进一步的生成新的个体。6、根据前面产生的交叉和变异，可以确定的得到产生新一代种群，然后返回步骤2。基于Matlab的遗传算法研究摘要本文首先从遗传算法问题的研究背景以及研

5、究意义出发,然后对于遗传算法问题的国内外研究现状进行了探讨，接着对于研究方法进行了总结，最后对于本文要用到的一些理论知识进行了总结，比如：遗传算法的一些基本概念，以及染色体，适应度，遗传操作，图的概念，有向图以及无向图的说明，最短路径的一些概述，以及一般求解最短路径的步骤，还有一些求解最短路径的基本方法做了一些说明。接着对于遗传算法问题进行了详细的分析推到计算，最后本文将遗传算法问题到了最短路径规划问题上，并且对于遗传算法的最短路径规划问题进行了matlab仿真分析，对仿真的结果进行了分析，得到了相关的结论。证明了遗传算法运用在最短路径问题上的正确性与科学性。关键词：遗传算法；matlab；最

6、短路径ResearchonGeneticAlgorithmsBasedonMATLABAbstractThispaperstartswiththeresearchbackgroundandsignificanceofgeneticalgorithm,thendiscussestheresearchstatusofgeneticalgorithmathomeandabroad,thensummarizestheresearchmethods,andfinallysummarizessometheoreticalknowledgetobeusedinthispaper,suchas:somebas

7、icconceptsofgeneticalgorithm,aswellaschromosomes,fitness,geneticoperations,graphs.Theconcepts,directedgraphsandundirectedgraphs,someoverviewsoftheshortestpath,andgeneralstepstosolvetheshortestpath,aswellassomebasicmethodstosolvetheshortestpatharedescribed.Thenthegeneticalgorithmproblemisanalyzedandc

8、alculatedindetail.Finally,thegeneticalgorithmproblemisputintotheshortestpathplanningproblem,andtheshortestpathplanningproblemofgeneticalgorithmissimulatedandanalyzedbymatlab.Thesimulationresultsareanalyzedandtherelevantconclusionsareobtained.ThevalidityandScientificityofgeneticalgorithminshortestpat

9、hproblemareproved.Keywords:geneticalgorithm,matlab,shortestpath目录第一章绪论11.1 研究背景及研究意义11. 1.1研究背景1LL2研究意义21.2 国内外研究现状21国外研究现状21.2.2国内研究现状31.3研究内容以及研究方法31.3. 1研究内容31.3.2研究方法4第二章理论知识52.1 遗传算法简介52.1.1 染色体52.1.2 群体52.1.4 遗传操作52.2 图的概念62. 2.1图的定义63. 2.2有向图或无向图62. 3最短路径问题72. 3.1最短路径的定义73. 3.2最短路径的一般步骤7第三章遗传

10、算法研究103.1 目标函数的选取及其处理103. 2遗传算法的基本步骤113. 3遗传算法求解最短路径问题123. 3.1最短路径问题的图论描述124. 3.2染色体编码135. 3.3适应函数136. 3.4选择操作137. 3.5交叉与变异操作13第四章遗传算法的仿真研究167.1 仿真实验环境设计164. 2仿真实验结果展示191 .3实验结果分析204 .4最短路径几种算法比较20第五章总结22致谢23参考文献：24附录：25第1章绪论1.1 研究背景及研究意义1.1.1 研究背景伴随着工业化时代的到来，人们的生产生活有了更多更高的要求，很多工业过程的实际问题得不到解决，以及随后达尔

11、文的适者生存，优胜劣汰的自然科学规律的提出，人们借助达尔文的发现，提出了遗传算法这样一种新的算法来解决很多工业过程的实际的问题。遗传算法英文全称是GeneticAlgorithm,是在1975年的时候，由美国科学家JHoIIand从生物界的进化规律之中发现并且提出来的，借助适者生存，优胜劣汰的自然科学规律运用到科学的训练方法之中，对于对象直接进行操作的一种算法。这种算法不用跟其他算法一样，需要对于模型进行求导和连续性的限制，遗传算法本身就可以借助概率化的求算工具进行全局寻优，并且可以自动的获取并且指导需要优化的搜索区域，如果搜索区域产生偏差，会自动的进行调整。因此，遗传算法本质上不需要跟其他算

12、法一样，不必须有一种明确的规则进行指导进行。并且可以说与传统的优化相比，在求取符合运行要求的全局最优解时，遗传算法作为一种搜索的方法，已经成为成熟的具有良好收敛性、极高鲁棒性和广泛适用性的优化方法，很好的解决了电力系统的多变量、非线性、不连续、多约束的优化控制问题。现在遗传算法的这些优良的性质被逐渐的开发出来，已经被运用的越来越广泛，不仅可以应用在化工过程的各种生产过程的求解之中，更是可以用在现在最火热的机器学习的领域之中，对于信号处理这一块还有自适应控制这一块的应用也得到了推广，就连比较冷门的人工生命等学科也可以说是有比较广的涉及，可以说遗传算法已经发展成为现当今时代有关智能计算中的一种不容

13、忽视的算法技术。作为当今最火热的一种算法，有必要对于遗传算法进行一些更深入的了解。本文就是基于遗传算法的研究，并且将遗传算法运用在路径规划的问题上进行具体的研究。1.L2研究意义遗传算法作为一种搜索的方法，己经成为成熟的具有良好收敛性、极高鲁棒性和广泛适用性的优化方法,很好的解决了电力系统的多变量、非线性、不连续、多约束的优化控制问题。由于遗传算法的优良性能的存在，因此，对于遗传算法的进一步研究们可以促进我国其他众多学科的发展，不仅可以为我国的文化理论知识领域进行扩充，更是对于众多生产领域提供了实际操作的切实可行的理论基础。就比如本文研究的关于遗传算法控制的路径规划的问题就是一个非常火热的话题

14、，可以具体应用在非常多的领域，比如：外卖小哥送外卖，怎么送才能在最短时间内准时送达多份外卖；一件快递，如何以最快的速度从北京送到广州；在策划一次旅行中，如何设计最优路线等这些可大可小的问题都出现了最短路径问题，深入了解最短路径算法，能够大大提高生产效率，提升生活质量；这些都是遗传算法可以成功应用的领域。1.2国内外研究现状1.2.1国外研究现状遗传算法问题在生活与生产中的具体应用随处可见，可以说遗传算法问题从发现以来就一直就是一个炙手可热的研究问题，国外很早就开始了遗传算法问题的研究。在20世纪90年代末期的时候，当时任然身为学生D.Whitey就基于遗传算法问题提出了交叉算子的概念，利用交叉

15、算子的概念，D.Whitey成功的将遗传算法问题运用到了旅行推销员问题、货郎担问题（TSP）的问题上，并且D.Whitey具体的用实验证明了应用的正确性。在D.Whitey之后，著名学者D.H.Ackley基于遗传算法问题提出了随机迭代遗传爬山法的问题（SIGH）,随机迭代遗传爬山法的最大优势就是在求解速度上，大大改善了一般的遗传算法得求解速度问题。著名学者HBersini独特的看到了单一方法的优势可以运用到遗传算法之中，H.Bersini将二种方法结合形成了多亲交叉算子，该算子的发现，使得遗传算法有了更好的性能。随后，在20世纪初期的时候，YUnLi和他的学生对于二进制基因进一步拓展研究，将

16、其扩展到了七进制的基因还有十进制的基因设置时还有整数基因和浮点基因,利于遗传算法模糊参量的进一步改善。在2000年的时候，GeneticProgramming的创造者美国科学家JohnKoza等一大批遗传算法研究学者参加了EvoNet研讨会，进行探讨遗传算法与遗传编程集合起来的结构寻优,从而使得遗传算法打破了固定结构的局限性。，并且从这时候开始遗传算法也不再仅仅拘泥于数值优化。1.2.2国内研究现状遗传算法问题一直就是一个炙手可热的研究问题，相比较于国外的研究，国内对于遗传算法问题的研究就相对少一点，并且大量的研究都是从21世纪以后才开始的，但是我国对于遗传算法问题的研究的发展还是比较快的，目

17、前，对于遗传算法问题的研究，国内主要有以下内容：对于遗传算法问题的研究，国内首先的关注点在于交叉算子的改进，在2002年的时候，中国著名科学家戴晓明基于多种群遗传并行的基本法则，提出了对于不同种群来说可以利用不同的遗传策略来搜索变量空间，进而进一步解决局部最优值问题。在2004年的时候，中国著名科学家赵宏立，考虑到现阶段对于较大规模的拼接组合整体优化的一些情况的时候，可能会出现搜索效率低下的不利情况，进而在这个基础上发明了基于基因块进行编码的并行遗传算法来解决搜索效率低下的不利情况。在2004年的时候，中国著名科学家江雷等基于科学家赵宏立提出的并行遗传算法，来求解TSP相关的问题，这种算法，解

18、决了局部收敛的难题，使得并行遗传算法进一步的向着全局最优解方向前进。接着2016年，黄玲等科学家改进粒子群算法，用遗传算法求解最短路径问题。1.3研究内容以及研究方法1.3.1 研究内容本文首先从遗传算法问题的研究背景以及研究意义出发，然后对于遗传算法问题的国内外研究现状进行了探讨，接着对于研究方法进行了总结，最后对于本文要用到的一些理论知识进行了总结，比如：遗传算法的一些基本概念，以及染色体，适应度，遗传操作，图的概念，有向图以及无向图的说明，最短路径的一些概述，以及一般求解最短路径的步骤，还有一些求解最短路径的基本方法做了一些说明。接着对于遗传算法问题进行了详细的分析推到计算，最后本文将遗

19、传算法问题到了最短路径规划问题上，并且对于遗传算法的最短路径规划问题进行了matlab仿真分析，对仿真的结果进行了分析，得到了相关的结论。证明了遗传算法运用在最短路径问题上的正确性与科学性。1.3.2 研究方法1 .文献法一一搜集和分析研究各种现存的有关遗传算法方面的文献资料，从中选取适合本文的信息，帮助完成调查研究目的。2 .资料收集法一一通过查看有关遗传算法的书籍或网站，学习相关知识，运用到论文中。3 .分析推算法一一通过上面二种方法收集到的资料，将遗传算法运用到最佳路径的问题之上，进一步的进行分析推算，得到一些关于遗传算法的结论。4 .实验法一一通过上面对于遗传算法运用到最佳路径的问题的

20、分析研究，进行matlab仿真分析，验证遗传算法的科学性。第2章理论知识2.1 遗传算法简介遗传算法英文全称是GenetiCAIgOIithm,是在1975年的时候，由美国科学家J.H。IIand从生物界的进化规律之中发现并且提出来的，借助适者生存，优胜劣汰的自然科学规律运用到科学的训练方法之中，对于对象直接进行操作的一种算法。并且，遗传算法作为一种搜索的方法，已经成为成熟的具有良好收敛性、极高鲁棒性和广泛适用性的优化方法,很好的解决了电力系统的多变量、非线性、不连续、多约束的优化控制问题。非常多的运用到了生产的方方面面。可以说遗传算法的研究已经取得了巨大的成功。2.1.1 染色体在具体的使用

21、遗传算法的时候，一般是需要把实际之中的问题进行编码，使之成为一些具有实际意义的码子。这些码子构成的固定不变的结构字符串通常被叫做染色体。跟生物学之中一样的，具体的染色体中的每一个字符符号就是一个基因。总的固定不变的结构字符串的长度称之为染色体长度，每个具体的染色体求解出来就是具体问题之中的一个实际问题的解。2.1.2 群体具体的实际之中的问题的染色体的总数我们称之为群体，群体的具体的解就是实际之中的问题的解的集合。2.1.3 适应度在对于所有的染色体进行具体的编码之后，具体的一条染色体对应着一个实际的数值解，而每个实际的数值解对应着一个相对应的函数，这个函数就是适应度指标，也就是我们数学模型之

22、中常说的目标函数。2.1.4 遗传操作说到遗传算法，不得不提的是遗传算法之中的遗传问题，具体进行遗传的时候有如下操作：1、选择：从上一次迭代过程之中的M个染色体，选择二个染色体作为双亲，按照一定的概率直接遗传到下一代。2、交叉：从上一次迭代过程之中的M个染色体，选择二个染色体A、B作为双亲，用A、B作为双亲进行生物学之中的交叉操作，遗传到下一代。3、变异从上一次迭代过程之中的M个染色体，选择一个染色体进行去某一个字符进行反转。2.2 图的概念2.3 2.1图的定义有序三元组G=（匕瓦中）称为一个图,G=（匕ET）必须满足以下条件：（1） V=Vl,V2,.,Vn是一个有限的非空集合，这里我们把

23、V称之为顶点集合。（2）这里我们把E称之为边集，其中的元素叫做图G的边。（3）犷是从边集E到顶点集合V的有序或者无序的元素偶对构成集合的映射，我么这里称之为关联函数。这里本文用图示一下，假设：G=（匕及中）满足以下条件：V=Vl,V2,.,Vn,E=el,e2,.,en,那么G的图解如下图2-1所示:图2-1G的图解2. 2.2有向图或无向图在G=（匕瓦）中，与V中的有序偶（Vi,Vj）对应的边e,称为图的有向边，同时与V中的顶点的无序偶Vi*Vj相对应的边e,称为图的无向边，并且如果在G=（匕瓦+）中，与V中的顶点的无序偶Vi*Vj相对应的边e,全部都是无向边的话，这个图就叫做无向图，与V中

24、的有序偶（Vi,Vj）对应的边e,都是有向边的话，这个图就叫做有向图。为了方便实验，与进行仿真分析，本文所有实验的算法都选用的是无向图。2.3最短路径问题2. 3.1最短路径的定义最短路径问题是运动规划的一个主要的课题。运动规划问题由二部分组成，分别是最短路径和轨迹规划，其中路径问题归结起来就是连接起点和终点的一条曲线，而与之相匹配的路径规划问题就是形成这样一种路径的策略。最短路径问题在生活生产的方方面面都会遇到，已经在很多领域都有着充分的运用。比如现在中国最前端的领域就有涉及，比如：机器人在行动的时候必须做到自主无碰；无人机在飞行的时候必须做到避障突防；巡航导弹在飞行的时候必须做到躲避雷达的

25、范围性探知；在我们的现实生活之中有:全球定位系统导航;各个城市内部不同的道路网规划等。3. 3.2最短路径的一般步骤最短路径问题总结起来一般有下面三个步骤:(1)环境建模。其中，环境建模可以说是最短路径的一个不容忽视的一步，环境建模的目的是建立在实际上可以让计算机来操作进一步来最短路径的环境模型，也就是把现实之中的物理空间转化成算法从而可以形成抽象空间，实现相互间的映射。(2)路径搜索。路径搜索就是在环境模型已经完成了之后，运用之前已经建立好的算法，进而去寻找一条最优的的路径，使得我们所建立目标函数能够获得我们所期望的最优值。(3)路径平滑。通过之前已经建立好的算法，找到的最优的的路径在实际情

26、况之中，并不一定实际上可行路径，需要后期继续作进一步处理，并且进行平滑的操作，才能使之前找到的最优的的路径成为一条在现实之中可以行走的路径。第3章遗传算法研究遗传算法的求解思路是首先进行编码操作，然后随机产生一个种群，进而选择适应函数也就是目标函数，进行三种不同的遗传操作，然后进行迭代，如果迭代满足收敛的条件，那么得到最优结果，迭代结束，否则继续进行迭代，继续看是不是满足收敛的条件，如果不满足，则继续迭代，直到满足为止，进而求得最优解。具体就是对于求出来多个Xi,计算出对应的fi,求出其中最小的n)对应的Xmin就是最优解。3.1 目标函数的选取及其处理遗传算法在初始阶段具有很快的下降速度，但

27、是在算法迭代后期，由于梯度变化值很小，导致函数收敛速度很慢，迭代次数很多。假设性能函数爪)是误差平方和，即NTF(X)=如(X)=V(X)V(X)(3-1)=1式中，X是参数向量，V是误差向量。要使性能函数最小，根据遗传算法可以得知，参数向量迭代更新至最优值，参数向量更新公式：XN=X/+J7(XJV(XJ(3-2)式中，Xz表示第4+1次迭代更新后的参数向量；X*表示第k次迭代的参数向量；外表示第2次迭代的学习率；I是单位矩阵；J(X)是JaCobian矩阵：加(X)()的(x)xx2亚(X)阳()现(X)J(X)=xix2(3-3)纵()弧()v(x)dxyx2算法特点：当从增加时，它接近

28、于有小的学习速度的最速下降法:xu三x-j(x0v(xa)(3-4)jk当从下降到O的时候，算法变成了高斯-牛顿方法。该算法具有梯度法和高斯牛顿法共同的优点，在算法初始阶段具有梯度法的下降速度,在接近误差极小值时，具有高斯牛顿法的优点，收敛速度快。4. 2遗传算法的基本步骤在求函数最大值问题或者是求最小值问题的时候，一般情况之下都是可以表达为以下的数学规划模型：minf(x)maxf(x)XeR或者(XR(3-5)RWUIRGU其中，f(x)为遗传算法的目标函数，X,R,U的相关性条件为约束条件，其中具体的满足约束条件的解为可行解。具体的遗传算法的步骤如下所示：2、具体的遗传算法的先随机产生种

29、群。2、确定具体的个体的适应度也就是目标函数，判断个体的适应度是否符合优化准则，如果符合优化准则，那么就可以直接输出最佳个体还有输出其最优解，结束，如果不符合优化准则，进行下一步。3、依据具体的个体适应度进行选择再生个体，根据算法的适者生存的原则可以有适应度高的个体毫无疑问被选中的概率就相应的高一些，适应度低的个体就相应的被淘汰。4、根据遗传学之中交叉的规则，按照一定的交叉概率以及具体的交叉方法，进一步的生成新的个体。5、根据遗传学之中变异的规则，可以按照一定的变异概率以及具体的变异方法，同样可以进一步的生成新的个体。6、根据前面产生的交叉和变异，可以确定的得到产生新一代种群，然后返回步骤2。

30、7、直到求得上面所描述的目标函数的最优解，迭代结束。3.3遗传算法求解最短路径问题3.3.1最短路径问题的图论描述在G=（V，及+）中，与V中的有序偶（Vi,Vj）对应的边e,称为图的有向边，同时与V中的顶点的无序偶Vi*Vj相对应的边e,称为图的无向边，并且如果在G=（V，及+）中，与V中的顶点的无序偶Vi*Vj相对应的边e,全部都是无向边的话，这个图就叫做无向图，与V中的有序偶（Vi,Vj）对应的边e,都是有向边的话，这个图就叫做有向图。为了方便实验，与进行仿真分析，本文所有实验的算法都选用的是无向图。3.3.2染色体编码具体在进行染色体编码的时候，我么对于各顶点号是进行按自然编排的，然后

31、按照编排的顺序将每个待选的顶点作为一个染色体的基因，基因编排的顺序也就是一条路径之中出现的先后顺序，所以可以看出来，具体的染色体的总长度应该和顶点的个数保持持平。3.3.3适应函数对于前面假设的性能函数在此处可以进行一些稍微的改进，因为是求距离，所以此处我们将前面误差的平方和，看成是各个顶点之间距离的平方和，具体如下面公式（3-6）以及公式（3-7）所示：X）=如（X）=V（X）V（X）（3-6）(3-7)U(X)=(匕，匕+J具体就是对于求出来多个Xi,计算出对应的fi,求出其中最小的/(4Vn)对应的Xmin就是最优解。3. 3.4选择操作从上一次迭代过程之中的染色体，选择二个染色体作为双

32、亲，而这里具体的染色体选择的是交叉的节点，这个是根据前面的适应函数选取的，原理就是选择操作更容易选择距离较短的二个顶点。4. 3.5交叉与变异操作1、交叉操作：将被选中要进行操作的染色体在进行交叉操作的具体步骤是，先在染色体上产生一个随机数，然后弄清楚这个随机基因的具体位置，从而确定与这个随机基因交叉点的位置，一般来说是同一个位置，然后将与这个随机基因在交叉点交叉的基因进行互换。具体交叉操作的示意图如图3-1所示：图3-1交叉操作2、变异操作将被选中要进行操作的染色体在进行变异操作的具体步骤是，先在染色体上产生一个随机数，然后弄清楚这个随机基因的具体位置，然后将这个位置之上的基因从O变成1,或

33、者从1变成0。变异操作虽然可以改变基因，但是有可能减缓遗传算法的计算速度。具体变异操作的示意图如图3-2所示：图3-2变异操作然后具体的设置的条件，也就是上面步骤1设置的目标函数的最优解，即达到距离最短，也就是我们所设置的条件。第4章遗传算法的仿真研究遗传算法问题在生活与生产中的具体应用随处可见，可以说遗传算法问题从发现以来就一直就是一个炙手可热的研究问题，而相应的最短路径问题在生活生产的方方面面都会遇到，已经在很多领域都有着充分的运用。比如现在中国最前端的领域就有涉及，比如：机器人在行动的时候必须做到自主无碰；无人机在飞行的时候必须做到避障突防；巡航导弹在飞行的时候必须做到躲避雷达的范围性探

34、知；在我们的现实生活之中有：全球定位系统导航；各个城市内部不同的道路网规划等。因此，本文将遗传算法应用在了路径规划的问题上，并且进行了相应的Mllab仿真研究。具体的求解可以用下面的算法流程图表示：图4-1遗传算法流程图4.1仿真实验环境设计这里我们研究的是遗传算法应用在了路径规划的问题的matlab仿真。并且这里我们设置了二种情况的最短路径研究，第一种是设置了10个点进行最短路径的遗传算法的研究，第二种是设置了30个点进行最短路径的遗传算法的研究。具体情况如下所示：情况一：10个点进行最短路径的遗传算法的研究具体的代码为：卜functiontest(lchrom,popsize,Pc,Pm,

35、gen)functiontest(xy,Ichrom,popsize,Pc,Pm,gen)tic%xy三rand(Ichrom,2)*100其中：主函数functiontest(xy,Ichrom,popsize,Pc,Pm,gen)参数意义：Xy为点的坐标(IChrom行2列的矩阵，可以随机生成也可以自己定)IChrOm为点的个数(点数)(10-30)；popsize初始种群规模数(100-200)；PC交叉概率，一般较大接近于1(0。81)；Pm变异概率，小，接近与0(（三）O10)；gen叠代的代数(500-2000)；functionelim=eliminate(x,y)；消去相同的f

36、unctionpop=inigroup(lchrom,popsize)；产生初试种群functionm=crossover(oldpl,oldp2)；交叉操作functiont=pathlenfit(p,(Jistmatrix)；计算适应值functiondraw(p,xy)；连线functiondistmatrix=site(lchrom,xy)；计算距离矩阵设置的点的matIab仿真图如下图4-110个点的设置所示:图4-110个点的设置从图4-110个点的设置可以看出来设置的需要遍历的10个点的坐标的依次如附录所示：（见附录4T）。情况二：30个点进行最短路径的遗传算法的研究具体的代码跟

37、上面设置的情况一样，只是情况一的IChrOm为10；情况一的Ichrom为30o代码为：Ichrom=30；xy-rand（Ichrom,2）*100;设置的点的matIab仿真图如下图4-230个点的设置所示:图4-230个点的设置从上图4-230个点的设置，利用MATLAB计算出的30个点的（从1号到30号）的左边依次如附录所示：（见附录4-2）。5. 2仿真实验结果展示针对上面设置的情况一以及情况，我们使用遗传算法，借助IIIatIab分别对于10个点以及30个点的情况进行了仿真得到了他们的具体的路径，具体的情况如下图4-310个点的仿真结果图以及图4-430个点的仿真结果图所示：情况一

38、：10个点进行最短路径的遗传算法的研究10个点进行最短路径的遗传算法进行matIab具体运行的最短路径的图示:图4-310个点的仿真结果图情况二：30个点进行最短路径的遗传算法的研究30个点进行最短路径的遗传算法进行matIab具体运行的最短路径的图示:图4-430个点的仿真结果图4.3实验结果分析对于最短路径的遗传算法研究，这里我们设置了二种情况，第一种是设置了10个点进行最短路径的遗传算法的研究，第二种是设置了30个点进行最短路径的遗传算法的研究。并且从MATLAB的结果来看运行结果都非常完好，完美的遍历了每一种情况的各个点，下面我们来对二种情况进行具体的分析。情况一：10个点进行最短路径

39、的遗传算法的研究从图4-310个点的仿真结果图可以看出来，运行结果都非常完好，完美的遍历了随机设定的10个点，并且通过遗传算法的的设计，制定并且在matlab上画出了路径最短的一条路径，通过ITIatlab强大的计算能力可以看出来，运行的路径分别是ShortPath=：3-1-2-10-9-7-5-4-6-8,比且可以计算得出最后最短的距离为shortpathlength=262.272。将遗传算法运用在最短路径问题上运行结果非常完好，不仅距离达到最短，而且完美的遍历了随机设定的10个点，符合了我们设定的要求，证明了将遗传算法运用在最短路径问题上的正确性与科学性。情况二：30个点进行最短路径的

40、遗传算法的研究从图4-430个点的仿真结果图可以看出来，运行结果都非常完好，完美的遍历了随机设定30个点，并且通过遗传算法的的设计，制定并且在matlab上画出了路径最短的一条路径，通过IIlatIab强大的计算能力可以看出来，运行的路径分别是shortpath=：11-20-28-1-4-30-19-2-6-21-18-13-16-9-5-25-14-15-27-7-3-24-23-29-17-IO-8-26-22-l2,并且可以计算得出最后最短的距离为ShortpathIength=518.4869。将遗传算法运用在最短路径问题上运行结果非常完好，不仅距离达到最短，而且完美的遍历了随机设定

41、的30个点，符合了我们设定的要求，证明了将遗传算法运用在最短路径问题上的正确性与科学性。上面二种情况都完美的通过了我们的要求，运行结果非常完好，不仅距离达到最短，而且完美的遍历了每一种情况的各个点，符合了我们设定的要求，证明了将遗传算法运用在最短路径问题上的正确性与科学性。并且，本文为了进一步验证遗传算法运用在最短路径问题上的正确性与科学性，本文同时设置了固定点为20个点、固定点为40个点、固定点为50个点的3种情况来进一步验证。1、固定点为20个点最短路径问题首先，本文先进行了固定点为20个点最短路径问题，二十个点依次为以下所示，固定点为20个点的示意图如右图4-5所示，并且在仿真之后的结果

42、路径如图4-6固定点为20个点最短路径问题仿真结果所示：图4-5固定点为20个点最短路径问题图4-6固定点为20个点最短路径问题仿真结果求得的固定点为20个点的最短路径问题为ShOrtPathlength=361.6357。通过固定点为20个点的最短路径问题，进一步验证遗传算法运用在最短路径问题上的正确性与科学性。2、固定点为40个点最短路径问题接着，本文先进行了固定点为40个点最短路径问题，四十个点依次为以下所示，固定点为40个点的示意图如右图4-7所示，并且在仿真之后的结果路径如图4-8固定点为40个点最短路径问题仿真结果所示：图4-7固定点为40个点最短路径问题,二三三-mF)编辑(E)

43、查看(V)SA(I)IMm桌面(D)窗口(W)帮助（三）0MldT%-、踮。乂石T目I国图4-8固定点为40个点最短路径问题仿真结果图求得的固定点为40个点的最短路径问题为shortpathlength=776.3215o通过固定点为40个点的最短路径问题，进一步验证遗传算法运用在最短路径问题上的正确性与科学性。3、固定点为50个点最短路径问题最后，本文先进行了固定点为50个点最短路径问题，五十个点依次为以下所示，固定点为50个点的示意图如右图4-9所示，并且在仿真之后的结果路径如图4-10固定点为50个点最短路径问题仿真结果所示：图4-9固定点为50个点最短路径问题文件(F)例(E)查看(V

44、)插入工具(T)桌面(D)窗口(W)帮助（三）日GI站IQl久久电要/三B图4-10固定点为50个点最短路径问题仿真结果图求得的固定点为50个点的最短路径问题为shortpathlength=999.2455o通过固定点为50个点的最短路径问题，进一步验证遗传算法运用在最短路径问题上的正确性与科学性。上面的设置固定点的三种情况都完美的通过了我们的要求，运行结果非常完好，不仅距离达到最短，而且完美的遍历了每一种情况的各个点，符合了我们设定的要求，证明了将遗传算法运用在最短路径问题上的正确性与科学性。4.4最短路径几种算法比较最短路径常用的算法可以说有非常之多，下面简单介绍几种算法，并且对于他们的

45、算法复杂度，以及算法准确性进行了描述：(1)穷举法顾名思义穷举法，就是将所有目标点的的所有可以遍历的情况全部列出来,全部走一遍，全部二二进行比较，从而得到最短路径。毫无疑问对于最短路径常用的算法来说，穷举法可以说是准确性是最高的一种算法，因为它将所有的可能性都列出来了，所以准确性肯定最高，而且能得到最优解，但是随之而来的问题是穷举法的效率过于低，算法的复杂度经过理论分析为O(1?)。(2)爬山算法爬上算法是在穷举法基础上发展起来的一种算法，意思就是也要将目标点的的所有可以遍历的情况全部列出来，但是不必要二二进行比较，只需要把前一种结果后一种进行比较，取最小的，从而依次比较下去就可以了。对于爬上

46、算法与穷举法比较起来看，毫无疑问算法的效率得到了很大提升，算法的复杂度经过理论分析从。(n2)提升到了。(n)0但是爬上算法只是把前一种结果与后一种进行了比较，准确性不是那么高，容易陷入局部最优的窘境。(3)模拟退火算法：模拟退火算法又是在爬山算法基础上发展起来的，算法的目的在于以下三个方面分别是：解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。模拟退火算法我们不用想象的太复杂，它的思想搞清楚就好了，他首先是个算法，这个算法的目的是求解，精髓是求最优解，它能使解在迭代过程中跳出局部最优的陷阱，怎么跳出的，是通过接受不好的解，继续迭代，这样就可以从整体上考虑，求出最优解。物理退火过程具体的可以划分为三个过程：1、加温过程一一指可以先把固体加热，一直加热到足够高的温度，然后可以使分子排列出来这里只要随机排列状态；2、等温过程一一对于一个系统状态而言，总是有着朝自由能不断减小的方向进行交替的这样一种趋势，当其达到最小的状态的时候，就可以说达到平衡态了；3、冷却过程一一使加热到足够高的温度的固体逐步降温，慢慢冷却，最后分子以一定的状态排列出来,这个状态必须是低