《基于不动点理论的改进遗传算法研究》由会员分享，可在线阅读，更多相关《基于不动点理论的改进遗传算法研究（59页珍藏版）》请在金锄头文库上搜索。
1、河北工程大学 硕士学位论文 基于不动点理论的改进遗传算法研究 姓名：王红霞 申请学位级别：硕士 专业：计算机应用技术 指导教师：张京军 2011-04 摘 要 I 摘 要 遗传算法是一种随机搜索方法，是应用最广泛的优化方法之一。但遗传算法 存在“未成熟”收敛以及收敛精度不高等方面的不足， 针对这些问题把不动点理论引 入遗传算法，借助不动点算法中的“剖分标号”思想，提出了三种求解优化 问题的改进遗传算法。 第一，基于三角剖分的改进遗传算法，将三角剖分理论引入遗传算法，首先 将优化问题转化为不动点的问题。借助相对坐标的概念设计遗传编码、交叉算子、 变异算子，提出一种改进遗传算法。通过本算法克服了用
2、三角剖分求不动点时采 用人为标号的缺点。同时将渐细剖分的思想引入遗传算法，使搜索范围逐渐减小， 提高算法的搜索的效率。第二，基于 1 J 剖分的改进遗传算法，将 1 J 剖分与整数标 号引入遗传算法，设计个体编码，利用编码将个体进行分类，进行交叉操作的个 体根据类别被进行了限定，如果两个体不满足交叉限定，则将其中个体进行变异 操作，这样使得遗传操作更据实效性。第三，基于 1 hJ 剖分的改进遗传算法，将 1 hJ 剖分引入遗传算法，算法增加了增维算子，以找到所有全标单纯形作为比较客观 的收敛准则。 这三种算法将不动点算法和遗传算法相结合，保证种群多样性，解决了遗传 算法的收敛性问题，并通过测试
3、函数进行仿真实验，结果表明本文提出的改进遗 传算法比其他遗传算法具有更高的全局性和有效性。 关键词：关键词：遗传算法；不动点；三角剖分； 1 J 剖分； 1 hJ 剖分；整数标号 Abstract II Abstract Genetic algorithm is a random search method and it is the most widely method of optimization. But the genetic algorithm existing some deficiency. For example, the “immature convergence” and
4、 the convergence precision are not higher. Aiming at these problems, the fixed point theories introduced into genetic algorithm using fixed point algorithm of “Simplicial triangulation - Integer label”. Propsing three kinds of improved genetic algorithms to solve optimization problem. Firstly, an im
5、proved genetic algorithm is based on triangulation, which will introduce the triangulations theory into the genetic algorithm. Firstly, it introduces the optimization problem into fixed point problem. With the relative coordinates of concept design the genetic coding, crossover operator and mutation
6、 operator, in order to improve genetic algorithm. Through this method overcomes the faults that with triangulations solving fixed point when using artificial label. We introduced gradually accurate triangulation thoughts into genetic algorithm, making the search range gradually decreased, improved t
7、he efficiency of the algorithm of search. Secondly, the improved genetic algorithm will introduce 1 J triangulation and integer label into the genetic algorithm, the design of individual coding; using coding classify classifies individuals. The individual which carries on crossover operation accordi
8、ng to the individual category is limited. If two individuals do not satisfy then the crossover limited, and one individual carries on mutation operation, this makes genetic operation more actual effect. Thirdly，an improved genetic algorithm based on 1 hJ triangulation which the 1 hJ triangulation is
9、 introduced into genetic algorithm, the algorithm increased increasing dimension operator, which find all the whole standard simplex as objective convergence criteria. In this paper, the fixed point algorithms were combined with genetic algorithm, guarantee the population diversity. It is solved the
10、 genetic algorithm convergence problem, and then through the test function to simulation experiments, the results show that the proposed improved genetic algorithm compared with other genetic algorithm has higher global and effectiveness. Keywords: Genetic Algorithm; Fixed Point; Triangulation; 1 J
11、Triangulation; 1 hJ Triangulation; Integer Label 独创性声明 本人郑重声明： 所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或 集体已经发表或撰写过的研究成果，也不包含为获得河北工程大学河北工程大学或其他教育 机构的学位或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体， 均已在论文中作了明确的说明并表示了谢意。本人完全意识到本声明的法律结果 由本人承担。 学位论文作者签名： 签字日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解 河北工程大学河北
12、工程大学 有关保留、使用学位论文的规 定。特授权 河北工程大学河北工程大学 可以将学位论文的全部或部分内容编入有关数据库 进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同 意学校向国家有关部门或机构送交论文的复印件和电子文档。 （保密的学位论文在解密后适用本授权说明） 学位论文作者签名： 签字日期： 年 月 日 导师签名： 签字日期： 年 月 日 第 1 章 绪论 1 第 1 章 绪论 1.1 遗传算法的发展与现状 1.1.1 遗传算法的发展 遗传算法是一种随机化全局搜索算法，以生物界进化中优胜劣汰、自然选择、 适者生存为基础。遗传算法的基本过程是首先利用随机方式产生一个
13、初始群体， 然后将通过选择、交叉、变异等过程改善待优化群体整体的性能，然后经过循环 过程直至达到某一限值或满足收敛要求，循环过程结束找出最佳个体。 遗传算法对优化模型的要求很低，基本上不利用外部信息，仅以适应度为依 据，对函数的连续性、可微性、梯度信息、设计空间的连通性和非凹性不做要求, 只要求能进行大小比较的非负结果即可，遗传算法在整个解空间遍及搜索，易得 到全局最优解，其适者生存的自然遗传机制与广义的优化内涵恰好相吻合。这些 优点使遗传算法在优化领域不断壮大，尤在工程结构优化及难以解决的复杂非线 性优化问题中得以广泛应用。 遗传算法早期的研究工作始于本世纪 60 年代。下面按年代的顺序，以
14、重要的 人物及其研究成果为线索，简要地介绍遗传算法研究的发展过程： （1）Holland 和自适应系统 50 年代末 60 年代初，一些生物学家开始利用计算机对遗传系统进行模拟。 Holland 在此期间正在从事自适应系统的研究。受生物学家们模拟结果的启发， Holland 和他的学生们首次应用模拟遗传算子来研究人工问题. 适应性的研究涉及到自适应系统和其环境，一般地，它是研究系统如何生成 过程，以使系统有效地适应它们的环境.如果适应性在开始时不是任意限制的，那 么自适应系统必须能生成一个具有有效定义能力的方法或过程1。. 60 年代中期，Holland 开发了一种编程技术遗传算法，其基本思想
15、是利用类 似于自然选择的方式来设计计算机程序6。在软件设计中，适应性是基于监督程序 的不同选择，通过不断剔除效果不佳的程序，让那些求解问题好的程序越来越占 据优势，从而使系统最终能适应任意的环境。Holland 除了认识到选择的必要性之 外，还赞同群体搜索的方法优于当时文献中普遍的单个结构到单个结构的方法。 在随后的 10 年中，Holland 致力于创建一种能表示任意计算机程序结构的遗传码， 以拓广遗传算法的应用领域2-5。 河北工程大学硕士学位论文 2 （2）Bagley 和自适应下棋程序 1967 年，Bagley 发表了关于遗传算法应用的第一篇论文并且首次提到了“遗 传算法”这个名称。
16、Bagley 设计了一个可控制的试验棋盘，模拟六个棋子的下棋 游戏。 Bagley 构造的遗传算法是用来搜索下棋游戏评价函数中的参数集，它与我们 现在应用的遗传算法很相似，Bagley 还敏锐地意识到在遗传算法的开始和结束阶 段需要有适当的选择率，为此，他引人了适应值比例机制，在算法执行的起始阶 殴减小选择的强制性，在算法执行的后阶段增加选择的强制性，因而，当接近群 体收敛时，在类似的高适应值的串之间保持了适当的竞争.今天的遗传算法研究人 员也采取了与之相似的步骤。 （3）Cavicchio 和模式识别 1970 年，Cavicchio 应用遗传算法解决了人工搜索中的两个问题：子程序选择 问题和模式识别问题7。 在 Cavicchio 的遗传算法中，他采用了一个预选择策略，即一个好的子代替换 它的一个父代，以便保持群体的多样性.当群体规模比较小时，群体多样性的保持 尤其显得重要，预选择策略有助于此，后来 De Jong 采用类似的方法成功地运用于 函数优化研究中
