毕业设计（论文）-基于改进遗传算法的板料切割轮廓路径优化设计.doc

毕业设计（论文）任务书毕业设计（论文）任务书 专业 机械设计制造及其自动化 班级 机械 117 姓名 廖波 下发日期 2015-3-8 题目题目基于改进遗传算法的板料切割轮廓路径优化设计 专题专题 主主 要要 内内 容容 及及 要要 求求 要求：在教师指导下，独立完成设计任务，培养较强的创新意识和学习能力，获 得机械工程师的基本训练。针对目标函数及应考虑的约束条件建立起完善的数学模型， 设计的算法正确，能够实现对板料切割轮廓路径进行优化设计。使用计算机设计、计 算；编制的计算机程序条理清楚，计算结果正确；说明书要求内容全面、文字通顺、 语言简练、图示清晰。 主要内容： （1）分析优化问题，建立完善、正确的优化数学模型。 （2）针对优化参数，设计相应的遗传算法优化方法。 （3）编制相应的计算机程序。 （4）撰写毕业论文说明书。 成果形式：设计说明书不少于 2 万字，查阅文献 15 篇以上，翻译与课题有关的英 文资料，译文字数不少于 5 千字。 主要技主要技 术参数术参数 10 个轮廓的路径优化，每个轮廓的顶点数是 38 个，时间距离最短，优化各个轮 廓的顶点扫描顺序。 进进 度度 及及 完完 成成 日日 期期 3 月 9 日3 月 27 日：布置、讲解设计题目，熟悉理解设计内容，借阅图书资料，毕业 实习/调研，收集、整理、消化、翻译有关资料。 3 月 30 日4 月 17 日：建立完善、正确的优化数学模型。 4 月 20 日5 月 8 日：针对要优化的参数，设计相应的改进遗传算法。 5 月 11 日6 月 5 日：编制相应的计算机优化程序。 6 月 8 日6 月 12 日：编写毕业论文说明书。 6 月 15 日6 月 26 日：毕业论文审阅、修改及答辩。 教学院长签字日 期教研室主任签字日 期指导教师签字日 期 指 导 教 师 评 语 指导教师: 年 月 日 指 定 论 文 评 阅 人 评 语 评阅人: 年 月 日 答 辩 委 员 会 评 语 指导教师给定 成绩（30%） 评阅人给定 成绩（30%） 答辩成绩 （40%） 总 评 答辩委员会主席 签字 评 定 成 绩 青岛理工大学本科毕业设计（论文）说明书 i 摘摘 要要 激光加工路径优化设计问题是激光加工中的所涉及到的重要课题之一，一条好的 路径可以减少激光头空行程运行时间并且可以降低生产成本和提高生产效率，从而提 升企业在市场的竞争力和生存能力。而激光加工路径优化问题属于典型的 np-hard 问 题，然而传统的优化算法和一些比较单一的算法很难求得起最优解，所以本文在当前 研究的基础上，采用遗传算法对该问题进行研究。 首先本文设计了对遗传蚁群算法的改进，该算法前期采用了遗传算法为蚁群遗传 算法产生初始信息素，后期采用蚁群遗传算法，从而实现蚁群与遗传算法的结合。在 蚁群遗传算法中建立新的状态转移规则，并使用动态挥发系数进行信息素更新，采用 适应度动态调整交叉和信息素以及变异概率。基于信息素和启发信息选择交叉，变异 位置，设计了两种不同的终止条件。 对激光切割进行路径规划设计时，为了使规划更贴切实际，这里我们建立了包含 时间距离的目标优化设计数学模型。针对激光切割路径优化设计的特点，因而将其归 纳为广义旅行商问题，采用双重编码分别对轮廓加工顺序和各个轮廓对应的起始顶点 进行表达，在设计算法时，除了考虑轮廓图形为多边形以外，还考虑了椭圆以及圆的 情况。通过建立适应函数从而实现多目标向单一目标的转化，同时动态控制适应函数， 并改进了相应的轮廓和顶点的交叉与变异方法。 在相应的理论研究基础上，采用 c 语言编程并通过 vc 编制完成了激光加工路径 规划设计软件。 关键词关键词：激光加工；时间距离；轮廓路径优化设计；遗传算法；实数编码； 青岛理工大学本科毕业设计（论文）说明书 ii abstract laser machining path optimization design problem is one of the important topics involved in laser processing, a good path can reduce the laser head empty running time and can reduce production cost and improve production efficiency, so as to improve enterprise competitiveness and ability to survive in the market. and laser machining path optimization problem belongs to the typical np - hard problem, but the traditional optimization algorithm and some single algorithm to obtain the optimal solution, so in this paper, on the basis of the present study, genetic and ant colony algorithm is used to study on the issue. first in this paper, the design of genetic ant colony algorithm is improved, the algorithm early adopted the genetic algorithm for generating the initial pheromone ant colony genetic algorithm (ga), the late using ant colony genetic algorithm, so as to realize the combination of ant colony algorithm and genetic algorithm. in ant colony genetic algorithm (ga) to establish a new state transition rules, and use dynamic to update pheromone volatilization coefficient, using fitness dynamic adjusting crossover and pheromone and mutation probability. based on the pheromone and the heuristic information choice crossover, mutation, two different termination condition is designed. for laser cutting path planning and design, in order to make the planning more relevant practice, here we set up containing time distance mathematical model for optimal design of target. according to the characteristics of the laser cutting path optimization design, and thus to be summed up as the generalized traveling salesman problem, adopt dual coding sequence of contour machining respectively and the contour to express the corresponding initial vertex, when designing algorithm, besides considering contour graphics for polygon, considered the ellipse and the situation of the circle. through the establishment of adaptive function so as to realize the transformation of multiple target to a single goal, dynamic control to adapt to function at the same time, and improve the corresponding contour and vertex method of crossover and mutation. on the basis of relevant theoretical research, using c language programming and through vc prepared by the contour path based on genetic algorithm optimization design software, 青岛理工大学本科毕业设计（论文）说明书 iii optimization of the final result shows the validity and practicability of the algorithm. keywords: laser processing; time distance; outline of the path optimization design; improved genetic ant colony algorithm; dual coding; 青岛理工大学本科毕业设计（论文）说明书 iv 目录目录 摘摘 要要.i abstract ii 目录目录iv 第第 1 章章 绪论绪论 1 1.1 课题研究的意义及现状.1 1.2 论文主要研究内容.4 第第 2 章章 遗传算法基本原理遗传算法基本原理 5 2.1 遗传算法基本概念.5 2.2 遗传算法的起源及其发展.6 2.3 遗传算法的特点及其实现方法 .7 2.4 遗传算法的实现方式.10 第第 3 章章 基于遗传算法的轮廓路径优化设计基于遗传算法的轮廓路径优化设计 16 3.1 轮廓加工路径优化设计题目的要求 .16 3.2 建立轮廓加工路径优化的数学模型 .17 3.3 轮廓加工路径优化的约束条件 .19 第第 4 章章 遗传算法的求解遗传算法的求解 20 4.1 算法设计 .20 4.2 产生初始解 .21 4.3 适应度值与最优解的产生 .22 4.4 交叉操作 .22 4.5 变异操作的实现 .24 4.6 选择复制操作的实现 .24 第第 5 章章 优化实例优化实例 26 5.1 遗传算法路径优化问题实例 .26 5.2 轮廓加工路径优化 c 语言源程序代码.32 结结 论论 41 青岛理工大学本科毕业设计（论文）说明书 v 参考文献参考文献 42 致致 谢谢 44 附件附件 1 .45 附件附件 2 .53 青岛理工大学本科毕业设计（论文）说明书 1 第第 1 章章 绪论绪论 1.1 课题研究的意义及现状课题研究的意义及现状 一、课题的研究意义 制造业是国民经济发展的核心与支柱产业，制造业的发展水平是衡量一个国家综 合国力的重要标志。在经济全球化的今天，目前国内制造业面临国外先进技术水平的 挑战，因此，有必要学习国外的先进制造理念与思想、优化算法、优化理论，从而提 高国内制造业水平，提升企业的竞争力。 随着全球经济的逐步复苏，市场环境的也在不断的朝着有利于经济发展的方向变 化，面对这种变化，我们不仅要能设计出满足消费者需求的产品，更重要的是要能提 高生产效率，占领市场。为此，20 世纪 90 年代以来，世界各国都在大力发展现代制造 技术以及现代加工技术，而在现代加工技术中，激光加工技术具有重要地位1。 激光加工技术是一种比较先进的加工材料的技术，因其应用范围广，素有“万能 加工工具” 、 “未来制造系统的共同加工手段”之称。激光加工具有切割范围广、速度 快、切缝窄、热影响区域小、加工柔性大等优点，这使得激光加工技术在现代工业当 中的应用越来越广泛，随着科学技术的发展，激光加工技术将在制造业中发挥着举足 轻重的作用。 在激光加工中，其加工时间主要由加工速度和加工路径决定。当速度一定时，一 条好的路径将直接决定加工时间，影响加工效率，而如何进行路径优化是激光加工技 术的难点之一。 在激光加工技术中，当加工的图形比较多而且复杂，采用传统的优化方法很难同 时保证加工质量和加工效率，一个好的路径规划方案不仅可以提高生产效率，降低生 产成本，而且可以提高企业产品的准时交货能力，从而增强企业竞争力，因此在这个 时候激光加工路径规划问题的研究就有很重要的现实意义。 激光加工技术兴起于欧洲、美国、日本等工业发达的国家并很快形成了一个新兴 的高技术产业，为了更深入的研究激光加工技术，各个国家都采取了一系列措施来支 持激光加工技术的发展，譬如美国的“战略防御倡议” ，德国的“激光技术及其研究重 点” ，英国的“阿维尔计划” ，日本的“激光研究 5 年计划”等等。这些国家为了执行 青岛理工大学本科毕业设计（论文）说明书 2 发展计划还专门设立了研究机构与激光加工应用中心。由此可见激光加工技术的重要 性。 在 20 世纪 7080 年代，美国、德国、日本等国就在大量激光切割工艺实验的基 础上总结激光切割工艺，建立工艺数据库，并着手研究高性能的激光切割系统，90 年 代初期国外就已经推出一些具有加工参数自动化设定功能的激光切割系统并建立了比 较完善的激光加工技术理论，与这些国家相比，我国的激光加工技术研究不够成熟， 起步较晚，基础工业相对落后，工业生产自动化程度不高，市场竞争意识薄弱，但是 由于国家对科学技术的重视，经过几代人的努力，我国的激光加工技术到目前为止已 经取得了可观的成绩，尤其在激光切割方面，激光加工技术在我国的发展主要分为三 个阶段：1）在 20 世纪 70 年代中期，我国就开始激光切割实验，到了 70 年代末期， 中科院长春光机所为成都飞机制造厂安装了中功率（500w 左右）激光器，用于切割 飞机零件；2）从 20 世纪 80 年代中期开始，在上海、株洲和天津等地先后全套引进 高功率（1500w 左右）激光切割系统，较广泛地把激光切割新工艺引入到我国的工业 制造领域；3）20 世纪 90 年代以后是激光切割发展的第三阶段，开始发展中、高功 率的，具有适合切割光束模式的快流激光系统为工业世界服务。2co 二、课题的研究现状以及现有研究存在的问题 目前我国正在发展中、高功率的激光加工技术。为了推动激光加工技术的发展， 我国专门建立了三个国家级激光加工中心2，此外激光加工技术还被列入了国家重点攻 关项目， “863”计划，国家“火炬”计划等。随着激光加工技术的发展，激光加工中 路径规划的研究得到学术界越来越广泛的关注，并提出了一系列的求解方法。目前比 较常用的有：传统方法和人工智能方法4,6。传统方法主要包括：可视图法4,5、自由空 间法6、栅格法7,8、人工势场法9,10、拓扑法11,12、梯度法、枚举法、随机搜索法等。 其中由于激光加工路径规划问题可归纳为旅行商问题，属于 np-hard 问题，难以找到 多项式算法，并且随着神经网络、遗传算法及蚁群算法等智能算法的提出及发展，越 来越多的学者将智能算法应用于路径规划问题。 文献13应用改进的遗传算法对路径规划问题进行研究，将不可行路径进行优劣评 价后加入到适应度函数中，并在子种群与父种群的置换中采用了置换比例；文献14针 对用遗传算法求解路径规划问题时，容易出现收敛速度慢、陷入局部最优的问题，对 适应度函数及变异算子进行改进，并采用自适应的方法调节交叉、变异概率。 文献 15,16对叠层实体制造工艺进行路径规划，采用轮廓的原始起点，将轮廓简化为点单 青岛理工大学本科毕业设计（论文）说明书 3 元，应用便宜算法等对路径进行排序优化。 文献17把路径规划问题进行了分级规划，采用两步算法进行求解，首先用最近邻 算法确定轮廓的起点，然后把路径优化问题归结为旅行商问题。 文献18把激光加工路径规划问题归结为广义旅行商问题，指出先按各轮廓路径 内原始节点次序确定各轮廓加工顺序，再指派轮廓起点的两步优化近似算法；文献19 将此问题看成广义旅行商问题进行研究，运用路径及起点的二级编码方式的遗传算法 对轮廓路径进行排序。 由上述介绍可以看出：激光加工技术日臻完善，但对激光加工路径规划的研 究还处于起步阶段，有许多地方值得我们研究探索。 （1）到目前为止单纯的遗传算法日渐成熟，但在处理激光加工路径规划问题时，算法 存在一些固有缺陷。学者们为了能有效地避开单一算法的不足，对算法进行融合，但 是现阶段对各种算法的融合仅仅是算法的简单混合或叠加，不能实现算法的真正融合。 对算法进行融合还处在试探阶段，没有完善的算法融合理论。 （2）在用智能算法规划路径时，有很多具体的加工细节没有考虑到，需进一步研究探 索。比如，建立目标函数时，直接建立距离最短的目标函数，而没有建立时间最短的 目标函数。 （3）用智能算法规划激光加工路径，把被加工轮廓当作一个点处理，并将路径规划问 题归结为经典旅行商问题。在用哪一点代表轮廓的问题上，学者们提出了很多解决方 法如用轮廓起点表示轮廓、轮廓终点表示轮廓、轮廓上任意一个特征点表示轮廓等， 并在处理路径规划时取得了一些成就，但这些处理方式都存在一些缺陷。因此，用哪 一点代表轮廓的问题是激光加工路径规划的一个“瓶颈” 。 （4）激光切割路径规划时，一般只考虑空行程时间最短，没有考虑工艺处理方面对工 件质量的影响。我们应该努力寻找一条优化的路径，即满足空行程时间最短又满足工 件质量的要求。 青岛理工大学本科毕业设计（论文）说明书 4 1.2 论文主要研究内容论文主要研究内容 本文主要是针对激光加工路径规划问题的研究，采用遗传算法的思想进行编程， 并给出总循环代数、最优解（目标函数最小值）及最优解出现在的代数。 （1）研究遗传算法及蚁群遗传算法的基本原理，并对各自的不足之处进行改进之 后融合得出改进的遗传算法。 （2）分析总结已有的路径规划方法并进一步探讨加工路径的方法。 （3）提出了时间距离的概念，进一步完善数学模型。建立了激光头空行程运行时 间最短和距离和最短的优化数学模型。 （4）考虑加工工艺的实际情况，解决了不同轮廓起始点不同的编码问题，运用时 间距离的概念，在原有路径规划问题上进行了改进，使其更加符合实际而且高效率， 为了提高遗传算法的优化性能，本文设计了多种交叉变异方法。 （5）利用 c 语言并通过 vc 编写了相应的优化程序，对设计的算法进行了模拟仿 真，根据所得优化结果反过来对遗传算法进行了改进。 青岛理工大学本科毕业设计（论文）说明书 5 第第 2 章章 遗传算法基本原理遗传算法基本原理 2.1 遗传算法遗传算法基本概念基本概念 遗传算法（genetic algorithm）是基于自然遗传机制自适应寻优和自然选择原理 的一种模拟进化算法。ga 启迪于生物学的新达尔文主义（达尔文的进化论、魏茨曼的 物种选择学说和孟德尔的基因学说） ，模仿物竟天演、优胜劣汰、适者生存的生物遗传 和进化的规律性。 由于遗传算法是由自然遗传学产生的直接搜索优化设计方法，因此在论文中引用 了许多遗传学的概念，这些概念如下： （1）基因（gene）：在生物中指的是生物遗传信息的载体，是控制着生物的各种 性状的内在因素。而在遗传算法中则指的是所列问题解的各种参数。 （2）染色体（chromosome）：在生物上指的是生物体细胞内具有遗传性能的物质， 它是基因的载体。在遗传算法中染色体指的是求解问题的解参数排列（编码） 。 （3）个体（individual）：指的是问题的解。 （4）种群（population）：个体的集合称为种群，该集合内个体的总数叫做种群的 大小。 （5）适应度（fitness）：指的是生物个体对生存环境的适应程度。在遗传学算法 中指的是某一个体被选择到下一代的可能性的大小。 （6）进化（evolution）：指的是生物在生存过程中，对生存环境的适应能力越来 越强，这种现象称之为进化。在遗传算法中则指的是种群适应度函数值逐渐变大的过 程。 （7）编码：把一个问题的可行解从其解空间转换到遗传算法能处理的搜索空间的 转换，也就是把一个问题的参数用遗传算法中的基因与染色体表达出来。 青岛理工大学本科毕业设计（论文）说明书 6 2.2 遗传算法的起源及其发展遗传算法的起源及其发展 20 世纪 4050 年代，数名计算机领域里的科学家开始研究进化算法，首次将自然 界中的生物进化引入工程领域。在用进化思想解决优化问题时，沿用了进化过程中的 选择、遗传等概念，并把它们当作算子参与优化。 到了 20 世纪 60 年代，rechenberg 提出了进化策略方法，并应用于优化实值函数。 美国密执根大学的 j.holland 教授用生物体遗传和进化的思想对自然和人工自适应系统 以及两者与环境的关系进行了研究，并提出了遗传算法的基本定律模式定理，并 于 1975 年出版了第一本自然系统和人工系统的自适应性著作，他在书中首次提出 并建立了遗传算法的基本框架，标志着遗传算法的诞生。 到了 80 年代，遗传算法进入了最为重要的发展时期，在理论研究以及实际研究方 面均取得了进步，尤其是遗传算法的应用研究显得更加吸引人。holland 教授首创了遗 传算法在机器学习上的新概念，并实现了第一个基于遗传算法原理的机器学习系统。 而 holland 的学生 bagley 在其博士论文中则首次使用了“遗传算法”一词，并发展了 复制、倒位、显性、交叉、变异等基本概念，在对个体进行编码时使用了双倍体的编 码方式。1989 年，goldberg 在genetic algorithm in search optimization and machine leaning一书中，完整的阐述了遗传算法的基本原理及其应用，并总结了遗传算法的 主要研究成果。1991 年，davis 在handbook of genetic algorithms一书中介绍了遗 传算法在工程技术、科学计算和社会经济中的许多应用实例。1992 年，koza 首次提出 了遗传编程(genetic programming,简称 gp)的概念并将其运用于计算机程序的优化设计 与自动生成。 纵观遗传算法的发展过程，在 6070 年代是起始阶段，80 年代是发展阶段，90 年代是高潮阶段。而遗传算法本身作为一种实用、高效、鲁棒性较强的现代优化技术， 发展非常快，已成为国内外学者研究的热门课题。 青岛理工大学本科毕业设计（论文）说明书 7 2.3 遗传算法的特点及其实现方法遗传算法的特点及其实现方法 利用传统优化算法可以找到小规模问题的最优解，但是随着问题规模的扩大，传 统优化算法的缺陷逐步显露出来，譬如求解效率低、稳定性差等，而遗传算法能很很 好的协调求解效率和稳定性，与传统优化算法比较，遗传算法还有如下优点： 多数传统优化算法是单点搜索法也就是每次只处理一个个体，而遗传算法在一定范围 内能同时处理多个个体，这样就大大提高了解决的效率，从而很好的防止了在搜索过 程中陷入局部最优解，增加了求得全局最优解的概率。 遗传算法对目标函数没有要求，它不要求目标函数连续，更不要求其可微，既可以是 数学解析所表达的显函数，亦可是隐函数、映射矩阵或者神经网络，而仅用适应度来 评价个体，即适应度值大的个体被选择的概率大。而适应度的唯一要求就是输入可以 计算出并且可以比较多的输出，这样就可以利用适应度指引搜索向不断改进的方向进 化，也就是不断的向最优目标函数值靠近。 在优化算例中，遗传算法是对起决定作用的变量进行编码，以编码为运算对象， 不直接处理决定变量本身的实际值，通过这种编码处理方式，可以使优化过程借鉴生 物学当中的基因和染色体等概念，模拟遗传学的机理，可以很方便的运用选择、交叉 和变异等遗传学算子，特别是对一些没有数值概念只有代码概念的优化问题，这种编 码处理方式凸显了其独特的优越性，这就使得遗传算法越来越受欢迎。 由于许多传统优化算法采用的是确定性搜素方法，即从一个搜个体到另一个个体有着 确定的转移方式和方法，这种确定性往往难以获得最优解。而遗传算法采用的是概率 搜索方法，也就是依据概率大小这种非确定性规则来指导算法的前进方向，但是有时 也会产生适应度值不高的个体，但总的来说会产生更多的优良个体即适应度值大的个 体，从表面看遗传算法是一种盲目的搜索方法，但是它始终是沿着最优解的方向不断 变化的。 遗传算法在本质上是并行的。遗传算法采用的不是单点搜索而是按并行方式搜索 整个解空间。其并行性主要表现在两个方面，一是遗传算法本身存在并行性，比较适 合大规模并行，最简单的并行方式可以让几百甚至几千台计算机在运行过程中不进行 联系，各自进行独立的种群进化计算，直到计算结束才进行比较，选出最佳个体。采 青岛理工大学本科毕业设计（论文）说明书 8 用这种并行方式对并行系统结构没有限制和要求，可以这样说，遗传算法可以在目前 所有的并行机或分布式系统上进行并行处理且对并行效率没有大的影响。二是遗传算 法的的内含并行性。由于遗传算法的搜索方式是种群，因此可以同时搜索解空间的多 个区域，同时相互交流信息。通过这种查询方式，虽然每次只是进行与总群规模成 zq n 比例的计算，但是实际上已经进行了大约 o（）次查询，通过这种方式可以获得事 3 zq n 半功倍的效果。 但是遗传算法也存在不足之处，其缺点如下： 1、遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需 要对问题进行解码。 2、另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严 重影响解的品质,而目前这些参数的选择大部分是依靠经验。 3、没有能够及时利用网络的反馈信息,故算法的搜索速度比较慢，要得要较精确 的解需要较多的训练时间。 4、算法对初始种群的选择有一定的依赖性，能够结合一些启发算法进行改进。 5、算法的并行机制的潜在能力没有得到充分的利用，这也是当前遗传算法的一个 研究热点方向。 在现在的工作中，遗传算法（1972 年提出）已经不能很好的解决大规模计算量问 题，它很容易陷入“早熟”。常用混合遗传算法，合作型协同进化算法等来替代，这些 算法都是 ga 的衍生算法。 遗传算法具有良好的全局搜索能力，可以快速地将解空间中的全体解搜索出，而 不会陷入局部最优解的快速下降陷阱；并且利用它的内在并行性，可以方便地进行分 布式计算，加快求解速度。但是遗传算法的局部搜索能力较差，导致单纯的遗传算法 比较费时，在进化后期搜索效率较低。在实际应用中，遗传算法容易产生早熟收敛的 问题。采用何种选择方法既要使优良个体得以保留，又要维持群体的多样性，一直是 遗传算法中较难解决的问题。 总结来说，遗传算法是一种新型的算法，具有解决复杂问题的能力。可以应用在 工业优化的很多问题上。 遗传算法的基本流程可以表示如下： 第一步 准备工作 青岛理工大学本科毕业设计（论文）说明书 9 （1）选择合适的编码方式。 （2）选择合适的参数，其中包括种群大小、交叉概率pc和变异概率pm。 （3）确定合适的目标函数和适应度函数。 第二步 建立目标函数并计算每个染色体目标函数值和适应度函数数值。 第三步 产生初始种群，随机产生一组初始个体构成初始解，针对本文指的是随机 产生一组 1 到 10 的不重复的数作为轮廓编码，即产生初始解。 第四步 交叉，确定交叉概率，根据交叉概率的大小选择进行交叉的个体数目，通 过交叉得到了大部分新个体，新个体组合了其父辈个体的特性。 第五步 变异操作，确定变异概率，根据其大小选择进行变异的个体数目，变异可 以增加种群的多样性，防止种群陷入局部最优。 第六步 选择复制 遗传算法的操作流程如图 2-1 所示： 图 2-1 遗传算法的操作流程图 青岛理工大学本科毕业设计（论文）说明书 10 2.4 遗传算法的实现方式遗传算法的实现方式 一 、编码方式 用遗传算法解决优化问题时，首先要做的就是编码。遗传算法不能直接对所需 要解决的问题完全参数化，因此所求得的解也必须符合遗传算法的的规律，也就是把 所需要解决的问题用遗传算法中的基因、染色体等概念表达出来，这样的操作就叫做 遗传算法的编码。为了高效的解决问题，在编码时应选择合适的编码方式，因此在设 计编码方式时，应注意编码的非冗余性、完备性和健全性，然而在实际问题中很难找 到上述要求的完美结合点，尽管如此，完备性是必须满足的。为了提高算法的查询效 率，在进行编码设计时应当满足有意义基因块编码规则以及最小字符集编码原则。 常见的编码方法有如下几种：实数编码、格雷编码、多参数映射编码和可变长编 码。 二、适应度函数 遗传算法中用于评价个体或者单个解的优劣程度即适应度值，适应度值大的个体 属于优良个体，被选到下一代的概率也较大，相反，适应度值小的个体属于劣质个体， 被选择到下一代的概率较小，而用于产生适应度值的函数便是适应度函数。因此合理 的适应度函数不但能够准确的反映个体的优劣程度而且能使最大限度的发挥遗传算法 的功能。 在遗传算法的优化过程需要建立优化函数，这个函数就是目标函数。其中，我们 可以通过目标函数与适应度函数的关系来确定适应度函数，即：适应度函数是目标函 数的倒数。在绝大多数优化过程中，目标函数求得的是极值，通常为最小值。我们可 以直接将目标函数转化为适应度函数。因为适应度函数值的大小可以决定概率，而概 率又可以决定那些个体留下，哪些个体被淘汰掉，也就是生物学上的“物竞天择，适 者生存” ，生存下来的个体组成形成可以繁殖下一代的种群。但是由于遗传算法中要对 个体的适应度进行比较并排序，并在此基础上选择概率，所以适应度函数值必须取正 数，如果有适应度函数值为负的情况需要对其做适当的变换，以保证其为正。 采用适应函数值度量个体差异与采用目标函数值度量个体差异有所不同，所以应 合理的设计适应度函数，使其与采用目标函数度量差别减到最小。如果适应度函数设 计不当，将难以体现个体之间的优劣，体现不出选择操作的作用，从而容易造成早熟、 收敛等缺点。所以一般都对适应度函数进行调节，如线性变换、幂变换和指数变换等， 青岛理工大学本科毕业设计（论文）说明书 11 即通过某种变换改变适应度函数间的比例关系。 适应度函数的构造可为： （2-3） k j j xgmf if 1 )(, 0max 1 min 式中:原适应函数值； xf 考虑了罚函数之后的新适应函数值；满足约束条件时 xf x 罚函数。 xp 五、遗传算子 遗传算子包括选择算子、交叉算子和变异算子。选择算子，顾名思义，就是选择 一些父代个体进入交配池，也就是过渡代，通俗的说就是建立一个临时数组用于存放 父代个体的编码（染色体或者基因）。最常见的选择方式就是通过轮盘赌进行选择， 这种选择方式类似于一种赌博方式，在遗传算法中我们依据各自的概率建立了一个大 的虚拟圆盘并把该圆盘不等分的分为几个部分，就好比切蛋糕一样，每一个板块代表 一定的选择概率，然后旋转该圆盘，当圆盘中概率大的部分指向某一个体时我们就认 为这个个体比较优秀。交叉算子是在遗传算法中运用公式进行交叉，任何交叉都有公 式或者逻辑算法。变异算子是交叉完成后的另一个遗传操作手段，变异的目的在于增 强寻求问题最优解的能力。选择、交叉、变异算子，他们构成了遗传算法的搜索能力 的核心。下面对各个操作做详细介绍： 1、交叉 遗传算法中的交叉跟生物上的交叉有很大的不同，生物上的交叉是指两个个体结 合产生一个个体，而在遗传算法中指的是两个个体通过一定的方式重组生成另外的两 个新个体，也就是基因片段的部分替换。由于研究要解决的问题是 tsp（旅行商）问题， 采用的编码方式是对路径编码。根据这种编码方式，有三种合适的交叉方式：部分匹 配交叉、顺序交叉和循环交叉。 一般的交叉方式则有：单点交叉、多点交叉和均匀交叉。 青岛理工大学本科毕业设计（论文）说明书 12 （1） 单点交叉。 单点交叉中，假定某一交叉点 a 的取值范围为1，m，m 为个体的变量数目， 我们把该点作为位分界点相互交换变量，并生成两个新个体。下面举例说明。假设个 体的编码是 x 1101101 一一 1101011 新个体 x个体的编码是 b 0010011 一一 0010101 新个体 x的交叉点又是随机设定的，当染色体长度为 n 时，可能有 n-1 个交叉点位置， 所以，单点的交叉可以实现 n-1 个不同的交叉结果。 （2） 多点交叉 对于多点交叉来说，m 个交叉位置 k。可以无重复的随机选择，可以在交叉点之 间进行变量间续地相互交换，产生两个新的后代，但在第一个变量与第一个交叉点之 间的一段不作交换。多点交叉的破坏性可以促进解空间的搜索，而不是促进过早地收 敛。因此搜索更加健壮。 （3） 均匀交叉 均匀交叉是将每个点都作为潜在的交叉点，随机的产生与个体等长的 01 的掩码，掩码中的片断表明了哪个父个体向子个体提供变量值。均匀交叉的操作过程 表示如下：当掩码中的位为 0 时，新个体 a继承旧个体 a 中对应的基因，当掩码中 的位为 1 时，新个体 a继承旧个体 b 中对应的基因，由此生成一个完整的新个体 a。 同样，可生成新个体 b。比如在旧个体 a 中，从左边第一个编码开始，如果是 1 就 保留，否则就将个体 a 中的 0 与个体 b 中的对应位编码进行交换。一个均匀交叉的 例子表示如下： 旧个体 a 101001 旧个体 b 110101 新个体 a 111101 新个体 b 100001 交叉算子是在遗传算法中运用公式进行交叉。在进行交叉时一般进行普通算数交 叉。假设父代个体 1 为 x，父代个体 2 为 y, x1=x+y （2-4）1 y1=y+x （2-5）1 青岛理工大学本科毕业设计（论文）说明书 13 式中，为交叉参数，是一个随机数，=rand%(101)/100.0 。 1 , 0 2、变异 变异算子的基本内容是对群体中某一个体的某些基因值作变动。子个体变量已很小 的概率或步长产生转变，变量转变的概率或步长与维数(变量的个数)成反比，与种群 大小无关。例如对于二迸制码串而言，变异操作就是把某些基因值取反，即 l 变为 0，0 变为 l。一般来说，变异算子的基本操作是：在群体中所有个体的码串的取值范围 内随机确定基因，再以事先设定的变异概率来对这些基因值进行变异。遗传算法导 入变异的目的有两个： 一、使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉己接近最优解的 范围时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛靠近。显然， 此种情况下的变异率应取较小值。 二、使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时，收敛概 率应取较大值。变异算子与选择交叉算子结合在一起，保证了遗传算法的有效性。在 变异操作中，变异概率不能取得太大，如果变异概率大于 05，遗传算法就退化为随 机搜索，而遗传算法的一些重要的数学特性和搜索能力也就不复存在了。 设变异操作时选择某染色体的第 1 位基因 d 进行变异，则新的基因值为： （2-6） dpop dpop dnewpop _ _ _ 式中：=rand()%101/100.0 。只是产生了之间的一个小数;10 a=rand()%2，是一个产生随机数0或1的整型变量，若a=0，则式中为加。此时 max；若a=1，则式中为减。此时min。dpop_dpop_ 3.选择复制 选择复制操作就是从父代种群中，把那些经过交叉变异的个体通过一定的概率选 择到下一代种群中。个体选择的方法包括：轮盘赌选择、随机便利抽样、锦标赛抽样 等。常用的选择方式为轮盘赌操作和按照比例的适应度计算。 选择过程总可以写成如下形式： 1、对每个染色体，计算累积概率ipopi i p 青岛理工大学本科毕业设计（论文）说明书 14 ， （2-7） popsize 1j i i i f f ppopsize, 2 , 1i 2、随机产生 01 之间的小数，在轮盘赌上选择相应的个体。 为了保证遗传算法的全局收敛性，这里实施了最优保留策略。 六、终止规则 遗传算法是通过不断地迭代循环来寻找最优解的一种方法，所以必须给其加上一 个终止条件，否则便会一直循环下去，形成死循环。最常见的处理方式就是规定一个 最大的遗传代数，当算法迭代次数达到最大遗传代数时便会停止。 遗传算法的收敛定理说明遗传算法可以收敛于 1，因此我们要追寻算法的求解效 率，不能让算法无限制的运行下去，而且问题的最优解一般是未知的，因此需要一个 条件来终止算法的运行，这个条件就是终止条件。 七、遗传参数 遗传算法的参数通常包括：种群规模 m、交叉概率 pc、变异概率 pm、进化代数。 （1)种群规模m 种群规模的大小对于遗传算法有着巨大的影响，如果种群的规模群体规模太小， 虽然可以提高遗传算法的运算速度，但是却降低了算法的多样性。优化的性能和优化 的结果不会很理想；如果群体规模太大，虽然算法的多样性提高，但是却也增加了算 法的计算量，降低了效率。 如果没有具体的理论确定种群大小，一般建议的取值范围是 10100。 （2）交叉概率pc 交叉概率用于控制交叉操作的频率。交叉操作是遗传算法中产生新个体最主要的 步骤，所以 pc一般取值较大。但 pc过大时，虽然可以增强开辟搜索新区域的能力， 但会破坏群体中的优良模式，不利于优良基因的遗传，不利于算法性能的发挥；pc过 小时，交叉操作产生的新个体过少，从而会使搜索停滞不前。一般建议的取值范围是 0.40.99。 （3）变异概率pm 变异是增加种群多样性的一个重要措施。变异概率直接影响到算法的收敛性和算 法最终解的性能。若 pm过大，使算法不断的搜索新的解空间，增加算法的多样性， 青岛理工大学本科毕业设计（论文）说明书 15 但影响到算法的收敛性；若 pm过小，则变异产生新个体的能力降低且算法容易出现 “早熟”现象。一般建议的取值范围是 0.00010.1。 （4）代沟 g 代沟控制着每代中被替换的个体占整个种群的比例。即每代有 mg 个个体被替 换。g=100%意味着整个种群全部更新；g=60%意味着 60%个体将被替换。标准 ga 中 g=100%，而有些替换策略中 g 值跟新旧个体的适应度好坏有关，而且是变化的，如 将父代种群的临时种群择优构成下一代种群。一般取 g=0.301.000。 青岛理工大学本科毕业设计（论文）说明书 16 第第 3 章章 基于遗传算法的轮廓路径优化设计基于遗传算法的轮廓路径优化设计 3.1 轮廓加工路径优化设计题目的要求轮廓加工路径优化设计题目的要求 本论文研究的主要是采用激光切割出在同一平面内的 10 个不同的轮廓图形，激光 头在已加工轮廓和下一个待加工轮廓之间的行走距离称为空行程。我们优化的目标就 是找出一条最佳轮廓加工顺序和顶点加工顺序，也就是一条合理的路径使总的空行程 距离和最短。而寻找最短路径主要分为两步，第一步确定各个图形的加工顺序，对应 于染色体编码中的第一行数，第二步确定各个轮廓图形对应的的起始点，对应于染色 体编码中的第二行数，但是不论先切割哪一个图形，不论以某一个图形的哪一个点作 为起始点，这些图形的总长度都不会变。但是切割顺序不同，空行程的距离也会发生 变化，路径总长度是可变的，所以可以通过优化激光切割路径来减少空行程距离，而 切割路径的优化过程就是一个如何确定各个轮廓的起始点以及轮廓切割顺序的问题。 青岛理工大学本科毕业设计（论文）说明书 17 3.2 建立轮廓加工路径优化的数学模型建立轮廓加工路径优化的数学模型 下面以激光加工为例结合图 3-1 说明激光加工过程，一个完整的切割过程是激光头 从加工原点出发按照一定的顺序依次切割图形，直到把所有的图形切割完，对于 3-1 所示的图形假设为原点，每个图形的第一个顶点为该图形的起点，则一条完整的切o 割径路径为： o11v12v13v14v11v21v22v23v24v21v31v32v33v34v35v31v 。41v42v43v44v45v41vo 然而在实际切割过程中，穿孔点的直径要比割缝宽，会对切割质量产生影响，此 时需要做一些工艺上的处理，例如可以在待加工材料旁边放置一块废料，让激光头先 切割废料，然后通过引弧把激光引到待切割轮廓上，这样就可以保证在加工材料时割 缝的均匀性，但是如果考虑上述问题无疑会加大问题的难度，且对路径影响不是很大， 因而暂不考虑穿孔点对路径规划的影响。 图 3-1 轮廓加工路径示意图 由激光头的运行时间等于距离和速度的比值知，当速度发生变化时，时间上的最 青岛理工大学本科毕业设计（论文）说明书 18 短并不一定是距离上的最短。例如在图 3-2 中，刀具从原点出发，终点是 d 点，由于 xy 轴均能以最大速度运行，由速度合成理论知对角线的速度比 x 轴、y 轴速度均大， 在相同时间内（假设这个时间即为最短时间） ，刀具可以走 bad 路径也可以走 bd 路径到达 d 点，在 x、y 方向各走过了一段距离 ba、ad 最终到达 d 点，由公 式知，当 xy 轴均以最大速度运行时，相同时间内 ba、ad 段距离之和大于 bd v s t 段，所以时间最短并不一定是距离最短，因此在此采用时间距离最短概念，即时间最 短的距离。空行程的时间就是从一个已加工轮廓的起始点到下一个待切割轮廓),(11yxp 的起始点的时间。而空行程时间取决于，即 x),(22yxq)(),(2211yyfabsxxfabsmax 或 y 方向上的最大距离值，此距离即是时间距离。 图 3-2 时间距离最短加工路径 轮廓加工分为两种情况，一种是从加工原点出发，加工到最后一个图形终止。另 外一种是，从加工原点出发，加工到最后一个图形，然后返回对刀点，形成回路。 设加工起始点的坐标为。）（000, yxp 第一种情况不形成回路，时间距离最短的目标函数为： （3-1） yy xx ii ii n i fabsfabsf 1 1 1 1 ,ma