基于Matlab的遗传算法研究计算机专业.docx

基于Matlab的遗传算法研究 第3章 遗传算法研究 遗传算法的求解思路是首先进行编码操作，然后随机产生一个种群，进而选择适应函数也就是目标函数，进行三种不同的遗传操作，然后进行迭代，如果迭代满足收敛的条件，那么得到最优结果，迭代结束，否则继续进行迭代，继续看是不是满足收敛的条件，如果不满足，则继续迭代，直到满足为止，进而求得最优解。具体就是对于求出来多个xi，计算出对应的fi,求出其中最小的对应的就是最优解。 3.1目标函数的选取及其处理 遗传算法在初始阶段具有很快的下降速度，但是在算法迭代后期，由于梯度变化值很小，导致函数收敛速度很慢，迭代次数很多。假设性能函数是误差平方和，即 (3-1) 式中，是参数向量，是误差向量。要使性能函数最小，根据遗传算法可以得知，参数向量迭代更新至最优值，参数向量更新公式： (3-2) 式中，表示第次迭代更新后的参数向量；表示第次迭代的参数向量；表示第次迭代的学习率；是单位矩阵；是Jacobian矩阵： (3-3) 算法特点：当增加时，它接近于有小的学习速度的最速下降法： (3-4) 当下降到0的时候，算法变成了高斯-牛顿方法。该算法具有梯度法和高斯牛顿法共同的优点，在算法初始阶段具有梯度法的下降速度，在接近误差极小值时，具有高斯牛顿法的优点，收敛速度快。 3.2遗传算法的基本步骤 在求函数最大值问题或者是求最小值问题的时候，一般情况之下都是可以表达为以下的数学规划模型： 或者 （3-5） 其中，f(x)为遗传算法的目标函数，X,R,U的相关性条件为约束条件，其中具体的满足约束条件的解为可行解。 具体的遗传算法的步骤如下所示： 1、 具体的遗传算法的先随机产生种群。 2、确定具体的个体的适应度也就是目标函数，判断个体的适应度是否符合优化准则，如果符合优化准则，那么就可以直接输出最佳个体还有输出其最优解，结束，如果不符合优化准则，进行下一步。 3、依据具体的个体适应度进行选择再生个体，，根据算法的适者生存的原则可以有适应度高的个体毫无疑问被选中的概率就相应的高一些，适应度低的个体就相应的被淘汰。 4、根据遗传学之中交叉的规则，按照一定的交叉概率以及具体的交叉方法，进一步的生成新的个体。 5、根据遗传学之中变异的规则，可以按照一定的变异概率以及具体的变异方法，同样可以进一步的生成新的个体。 6、根据前面产生的交叉和变异，可以确定的得到产生新一代种群，然后返回步骤2。 基于Matlab的遗传算法研究 摘要 本文首先从遗传算法问题的研究背景以及研究意义出发，然后对于遗传算法问题的国内外研究现状进行了探讨，接着对于研究方法进行了总结，最后对于本文要用到的一些理论知识进行了总结，比如：遗传算法的一些基本概念，以及染色体，适应度，遗传操作，图的概念，有向图以及无向图的说明，最短路径的一些概述，以及一般求解最短路径的步骤，还有一些求解最短路径的基本方法做了一些说明。接着对于遗传算法问题进行了详细的分析推到计算，最后本文将遗传算法问题到了最短路径规划问题上，并且对于遗传算法的最短路径规划问题进行了matlab仿真分析，对仿真的结果进行了分析，得到了相关的结论。证明了遗传算法运用在最短路径问题上的正确性与科学性。 关键词：遗传算法；matlab；最短路径 Research on Genetic Algorithms Based on MATLAB Abstract This paper starts with the research background and significance of genetic algorithm, then discusses the research status of genetic algorithm at home and abroad, then summarizes the research methods, and finally summarizes some theoretical knowledge to be used in this paper, such as: some basic concepts of genetic algorithm, as well as chromosomes, fitness, genetic operations, graphs. The concepts, directed graphs and undirected graphs, some overviews of the shortest path, and general steps to solve the shortest path, as well as some basic methods to solve the shortest path are described. Then the genetic algorithm problem is analyzed and calculated in detail. Finally, the genetic algorithm problem is put into the shortest path planning problem, and the shortest path planning problem of genetic algorithm is simulated and analyzed by matlab. The simulation results are analyzed and the relevant conclusions are obtained. The validity and scientificity of genetic algorithm in shortest path problem are proved. Key words: genetic algorithm, matlab, shortest path 目 录 第一章 绪论 1 1.1研究背景及研究意义 1 1.1.1研究背景 1 1.1.2研究意义 2 1.2国内外研究现状 2 1.2.1国外研究现状 2 1.2.2国内研究现状 3 1.3研究内容以及研究方法 3 1.3.1研究内容 3 1.3.2研究方法 4 第二章 理论知识 5 2.1遗传算法简介 5 2.1.1染色体 5 2.1.2群体 5 2.1.3适应度 5 2.1.4遗传操作 5 2.2图的概念 6 2.2.1图的定义 6 2.2.2有向图或无向图 6 2.3最短路径问题 7 2.3.1最短路径的定义 7 2.3.2最短路径的一般步骤 7 第三章 遗传算法研究 10 3.1目标函数的选取及其处理 10 3.2遗传算法的基本步骤 11 3.3遗传算法求解最短路径问题 12 3.3.1最短路径问题的图论描述 12 3.3.2染色体编码 13 3.3.3适应函数 13 3.3.4选择操作 13 3.3.5交叉与变异操作 13 第四章 遗传算法的仿真研究 16 4.1 仿真实验环境设计 16 4.2 仿真实验结果展示 19 4.3 实验结果分析 20 4.4最短路径几种算法比较 20 第五章 总结 22 致谢 23 参考文献： 24 附录： 25 VII 第1章 绪论 1.1研究背景及研究意义 1.1.1研究背景 伴随着工业化时代的到来，人们的生产生活有了更多更高的要求，很多工业过程的实际问题得不到解决，以及随后达尔文的适者生存，优胜劣汰的自然科学规律的提出，人们借助达尔文的发现，提出了遗传算法这样一种新的算法来解决很多工业过程的实际的问题。遗传算法英文全称是Genetic Algorithm，是在1975年的时候，由美国科学家J.Holland从生物界的进化规律之中发现并且提出来的，借助适者生存，优胜劣汰的自然科学规律运用到科学的训练方法之中，对于对象直接进行操作的一种算法。这种算法不用跟其他算法一样，需要对于模型进行求导和连续性的限制，遗传算法本身就可以借助概率化的求算工具进行全局寻优，并且可以自动的获取并且指导需要优化的搜索区域，如果搜索区域产生偏差，会自动的进行调整。因此，遗传算法本质上不需要跟其他算法一样，不必须有一种明确的规则进行指导进行。 并且可以说与传统的优化相比，在求取符合运行要求的全局最优解时，遗传算法作为一种搜索的方法，已经成为成熟的具有良好收敛性、极高鲁棒性和广泛适用性的优化方法，很好的解决了电力系统的多变量、非线性、不连续、多约束的优化控制问题。现在遗传算法的这些优良的性质被逐渐的开发出来，已经被运用的越来越广泛，不仅可以应用在化工过程的各种生产过程的求解之中，更是可以用在现在最火热的机器学习的领域之中，对于信号处理这一块还有自适应控制这一块的应用也得到了推广，就连比较冷门的人工生命等学科也可以说是有比较广的涉及，可以说遗传算法已经发展成为现当今时代有关智能计算中的一种不容忽视的算法技术。作为当今最火热的一种算法，有必要对于遗传算法进行一些更深入的了解。本文就是基于遗传算法的研究，并且将遗传算法运用在路径规划的问题上进行具体的研究。 1.1.2研究意义 遗传算法作为一种搜索的方法，已经成为成熟的具有良好收敛性、极高鲁棒性和广泛适用性的优化方法，很好的解决了电力系统的多变量、非线性、不连续、多约束的优化控制问题。由于遗传算法的优良性能的存在，因此，对于遗传算法的进一步研究们可以促进我国其他众多学科的发展，不仅可以为我国的文化理论知识领域进行扩充，更是对于众多生产领域提供了实际操作的切实可行的理论基础。就比如本文研究的关于遗传算法控制的路径规划的问题就是一个非常火热的话题，可以具体应用在非常多的领域，比如：外卖小哥送外卖，怎么送才能在最短时间内准时送达多份外卖；一件快递，如何以最快的速度从北京送到广州；在策划一次旅行中，如何设计最优路线等这些可大可小的问题都出现了最短路径问题，深入了解最短路径算法，能够大大提高生产效率，提升生活质量；这些都是遗传算法可以成功应用的领域。 1.2国内外研究现状 1.2.1国外研究现状 遗传算法问题在生活与生产中的具体应用随处可见，可以说遗传算法问题从发现以来就一直就是一个炙手可热的研究问题，国外很早就开始了遗传算法问题的研究。 在20世纪90年代末期的时候，当时任然身为学生D.Whitey就基于遗传算法问题提出了交叉算子的概念，利用交叉算子的概念，D.Whitey成功的将遗传算法问题运用到了旅行推销员问题、货郎担问题（TSP）的问题上，并且D.Whitey具体的用实验证明了应用的正确性。在D.Whitey之后，著名学者D.H.Ackley基于遗传算法问题提出了随机迭代遗传爬山法的问题（SIGH），随机迭代遗传爬山法的最大优势就是在求解速度上，大大改善了一般的遗传算法得求解速度问题。著名学者H.Bersini独特的看到了单一方法的优势可以运用到遗传算法之中，H.Bersini将二种方法结合形成了多亲交叉算子，该算子的发现，使得遗传算法有了更好的性能。随后，在20世纪初期的时候，Yun Li和他的学生对于二进制基因进一步拓展研究，将其扩展到了七进制的基因还有十进制的基因设置时还有整数基因和浮点基因，利于遗传算法模糊参量的进一步改