文档介绍：《自动化技术概论》课程论文题目: 退火遗传算法班级: 动力工程学号: 201280812014 姓名: 戴志立完成时间: 退火遗传算法绪论遗传算法(icAlgorithm, GA) 是近年来迅速发展起来的一种全新的随机搜索与优化算法。它是由美国密执安大学 教授提出的一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。它起源于达尔文的进化论,是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。遗传算法的研究引起了国内外学者的关注。自1985 年以来,国际上已召开了多次遗传算法的学术会议和研讨会,国际遗传算法学会组织召开的ICGA 会议和FOGA 会议,为研究和应用遗传算法提供了国际交流的机会。遗传算法的主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不以梯度信息为基础。它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题,可广泛应用于组合优化、机器学****自适应控制、规划设计和人工生命等领域。作为一种全局优化搜索算法, 遗传算法以其简单通用、鲁棒性强、适于并行处理以及应用范围广等特点, 使其成为 21 世纪智能计算核心技术之一。进入 80年代,遗传算法迎来了兴盛发展时期,无论是理论研究还是应用研究都成了十分热门的话题近年来,遗传算法已被成功地应用于经济答理、交通运输、工业设计等不同领域. 解决了许多问题。例如,可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖掘等。模拟退火算法来源于固体退火的原理,其最初的思想由 Metropolis 在1953 年提出, Kirkpatrick 在 1983 年成功地将其应用于组合最优化问题中。出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。在对固体物质进行退火处理时,通常是先将它加温熔化,固体内部粒子随温升变为无序状,内能增大,使其中的粒子可以自由运动,然后降温,而徐徐冷却时粒子渐趋有序,在每个温度上都达到平衡态, 最后在常温时达到基态,内能减为最小,粒子就逐渐形成低能态的晶体。如果凝结点附近温度下降足够慢,那么固体物质一定能够形成最低能量的状态。目前已有一些将模拟退火算法与遗传算法相结合的方法-退火遗传算法。文共分三章。第一章简单介绍遗传算法,主要介绍了遗传算法的起源与发展、与生物进化的密切关系、进化计算、基本定理和应用情况。第二章介绍了模拟退火遗传算法,包括模拟退火相关的基本知识、基本遗传算法的步骤、每一步中常见的方法和问题、遗传算子以及模拟退火遗传算法目前的研究情况。第三章对遗传算法和模拟退火算法进行了算法分析并对其进行改进,提出了遗传退火算法。 1 遗传算法 遗产算法的产生和发展遗传算法是一类借鉴生物界的进化规律(适者生存,优胜劣汰遗传制)演化而来的自适应概率性随机化迭代搜索算法。1962 年霍兰德(Holland) 教授首次提出了 GA算法的思想,它的基本思想是基于 Darwin 进化论和Mendel 的遗传演说。Darwin 进化论最重要的是适者生存的原理,它认为每一代种群总是向着前进方向发展, 越来越适应环境。每一个个体都有继承前代的特性,但不是完全继承,会产生一些新特性。最终只有适应环境的特征才能被保留下来。经过存优去劣的自然淘汰,适应性高的基因结构得以保存下来。遗传算法正是借用了仿真生物遗传学和自然选择机理,通过自然选择、遗传、变异等作用机制,实现各个个体的适应性的提高。从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。这一点体现了自然界中"物竞天择、适者生存"进化过程。与自然界相似,遗传算法对求解问题的本身一无所知,从代表问题可能潜在解集的一个群开始,每一个种群则由经过基因编码的一定数目的个体构成。每个个体实际上是染色体带有特征的实体。把问题的解表示成染色体,并基于适应值来选择染色体,遗传算法所需要的仅是对算法所产生的每个染色体进行评价,使适应性好的染色体有更多的繁殖机会。在算法中也就是以二进制编码的串。并且,在执行遗传算法之前,给出一群染色体,也就是假设解。然后,把这些假设解置于问题的“环境”中,也即在一个适应度函数中来评价。并按适者生存的原则,从中选择出较适应环境的染色体进行复制,淘汰低适应度的个体,再通过交叉,变异过程产生更适应环境的新一代染色体群。对这个新种群进行下一轮进化,直到最适合环境的值。 遗传算法的基本概念(l) 编码:解空间的解数据 x,作为遗传算法的表现型形式,就相当于基因,通过这个编码进行后面的选择、交叉和变异等计算。(2) 初始群体的生成: 随机生成 N 个串结构数据, 每个串结构数据称为一个个体,N 个个体构成一个群体。遗传算法以这 N 个串结构作为初始点开始迭代,设置进化代数计数器 t; 设置最大进化代数 T; 随机