《最优化理论与方法遗传算法.doc》由会员分享，可在线阅读，更多相关《最优化理论与方法遗传算法.doc（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流最优化理论与方法遗传算法.精品文档.遗传算法研究综述罗九晖 统计学 132111059 优化是科学研究、工程技术以及经济管理等等领域的重要研究对象。优化问题广泛存在于各个领域中，学者对该问题的求解研究从未停止。一、优化算法概述优化问题是个古老的课题，目前，对优化问题的求解研究主要有三个方向： （1）经典精确优化算法（数值最优化） 该算法主要用来处理目标函数以及约束条件有具体的解析表达式且存在导数的情况。它是先利用求导或者变分法得到极值点存在的必要条件（通常是一组方程或不等式），然后再求解细方程或不等式。（2）经典近似优化算法（解析最优化） 通
2、过最优解的性质建立迭代公式求最优解。（3）智能算法（仿生算法、演化算法、进化算法） 数值优化算法和解析优化算法必须建立在目标函数存在导数的性质条件下进行，而在实际中碰到的很多优化问题的目标函数并不存在导数。因此，近年来，学者们以模拟物质变化过程或模拟生命体而设计的搜索方式为基础，提出各种算法，这类算法就是智能算法。二、智能算法概述智能是在任意给定的环境和目标条件下，正确制定决策和实现目标的能力。智能优化算法则是将生物行为与计算机科学相结合，解决优化问题，制定最优化决策。目前，智能算法有以下几类：（1）模拟退火算法 模拟退火算法是基于蒙特卡洛迭代求解策略的一种随机寻优算法,其出发点是基于物理中固
3、体物质的退火过程与一般组合优化问题之间的相似性(即:退火过程中,固体最终达到能量最小的状态,对应于优化算法最终找到了最优解)而设计的一种智能优化算法,该算法将固体的退火过程与优化问题的求解过程有机的结合起来,因此该算法被称为模拟退火算法。（2）禁忌搜索算法 所谓禁忌就是禁止重复前面的工作。为了回避局部邻域搜索陷入局部最优的主要不足,禁忌搜索算法用一个禁忌表来记录已经达到过的局部最优点,在下一次的搜索中,利用禁忌表中的信息不再或有选择地搜索这些点,以此来跳出局部最优点。 （3）蚁群算法蚂蚁在运动过程中,能够在它所经过的路径上留下该种物质,而且能够感知这种物质的存在及其强度, 并以此指导自己的运动
4、方向。蚂蚁倾向于朝着该物质强度高的方向移动。因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多, 则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。蚁群算法就是基于这样启发而设计出来的一种智能优化算法。（4）粒子群优化算法 群体搜寻最优目标时,每个个体将参照当前群体中曾有的最优个体,和自身曾经达到的最优位置调整下一步的搜寻方向,这就是粒子群优化算法。（5）人工神经网络 人工神经网络是对人脑的模拟。（6）遗传算法 遗传算法是一种通过模拟生物界自然选择和遗传机制的随机搜索算法。三、遗传算法概述遗传算法是模拟自然界生物进化过程
5、与机制，求解极值问题的一类自组织、自适应的人工智能技术，其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法。1.遗传算法执行过程遗传算法是一种自适应全局优化搜索算法，使用二进制遗传编码，繁殖分为交叉和变异两个独立的步骤进行。其基本执行过程如下：（1）初始化。确定种群规模 N、交叉概率 Pc、变异概率 Pm和置终止进化准则; 随机生成 N 个个体作为初始种群 X ( 0);置进化代数计数器 t0。（2）个体评价。计算或估价 X(t)中各个体的适应度。（3）种群进化。选择 (母体 )。从X(t)中运用选择算子选择出 M /2对母体 (MN )。交叉。对所选择的 M /2对母
6、体, 依概率Pc执行交叉形成M个中间个体。变异。对M个中间个体分别独立依概率Pm执行变异, 形成M个候选个体。选择 (子代 )。从上述所形成的M 个候选个体中依适应度选择出N 个个体组成新一代种群X(t+ 1)。（4）终止检验。如已满足终止准则, 则输出X(t+ 1)中具有最大适应度的个体作为最优解, 终止计算; 否则转（3）。2.遗传算法理论研究遗传算法追求的是当前群体产生比现有个体更好个体的能力，即遗传算法的可进化性，因此，遗传算法的理论和方法研究主要是围绕这一目标展开：编码二进制编码用于多维、高精度数值优化问题时，不能很好地克服连续函数离散化时的映射误差，不能直接反映问题的固有结构，精度
7、不高，并且个体长度大、占用内存多，学者们提出的改进方法主要有：a.格雷码编码；b.实数编码；c.十进制编码；d.非数值编码。适应度函数在遗传算法中, 适应度是描述个体性能的主要指标, 根据适应度的大小对个体进行优胜劣汰。将目标函数转换成适应度函数一般应遵循两个原则: 适应度必须非负; 优化过程中目标函数的变化方向应与群体进化过程中适应度函数变化方向一致。在使用遗传算法求解具体问题时，适应度函数的选择对算法的收敛性以及收敛速度的影响较大，针对不同的问题需要根据经验或算法来确定相应的参数。遗传算子遗传算子主要包括三个方面：选择算子、交叉算子以及变异算子。常见的选择算子有：轮盘赌选择、排序选择、最有
8、个体保存、随机联赛选择。交叉算子主要有：单点交叉、两点交叉、均匀交叉、算术交叉。变异操作主要有：基本位变异、均匀变异、二元变异以及高斯变异。参数选择遗传遗传算法的参数选择一般包括群体规模、收敛判据、杂交概率和变异概率等。参数选择关系到遗传算法的精度、可靠性和计算时间等诸多因素, 并且影响到结果的质量和系统性能。因此, 在遗传算法中参数选择的研究非常重要。收敛性分析遗传算法的收敛性通常是指遗传算法所生成的迭代种群收敛到某一稳定状态或其适应值函数的最大或平均值随迭代趋于优化问题的最优值。依不同的研究方法及所应用的数学工具, 收敛性分析可分为Vose-Liepins模型、Markov链模型和公理化模
9、型等。欺骗问题欺骗问题是遗传算法研究中的一个热点。根据模式定理可知, 低阶、短距的优模式在遗传子代中将以指数级增长, 最终, 不同的最优模式相互组合, 从而得到最优解。但是, 对于欺骗问题, 复制算子受欺骗条件的迷惑,使最优低阶模式在组合后形成非最优高阶模式, 从而使遗传算法偏离最优解。由于欺骗问题的存在, 许多问题被归结为遗传算法难题, 使遗传算法的应用受到一定的局限。目前遗传算法的欺骗问题研究主要集中在三个方面: a.设计欺骗函数；b. 修改遗传算法以解决欺骗函数的影响；c. 理解欺骗函数对遗传算法的影响。并行遗传算法并行算法的基本思想是将一个复杂的任务分解为多个较简单的子任务, 然后将各
10、子任务分别分配给多个处理器并行执行求解。并行遗传算法可以分为四大类, 即全局并行遗传算法、粗粒度并行遗传算法、细粒度并行遗传算法和混合并行遗传算法。3.遗传算法的应用遗传遗传算法提供了一种求解复杂系统优化问题的通用框架,它不依赖于问题的具体领域, 广泛应用于多种学科领域。其主要领域有：函数优化、组合优化、生产调度、自动控制、机器人学、图像处理、人工生命、遗传编程、机器学习以及数据挖掘等。4.总结遗传算法作为一种非确定性的拟自然算法，为复杂系统的优化提供了一种新的方法，在许多学科领域具有广泛的应用价值。但有关算法的研究对已经研究较为深入的热点关注度较高，而对潜在研究热点和迅速发展起来的研究热点关注度不足。综观遗传算法在算法改进及应用方面的研究现状，它已经成为目前计算智能领域的热点之一。但是还有一些不足，总体而言，以下几方面的工作尤其值得进一步探讨:a.遗传算法与优化技术的融合。b.算法的改进以及新型算法的提出。c.混合遗传算法。d.算法的并行化研究。e.加强遗传算法与应用的结合。f.面向多目标优化约束优化问题的算法及理论研究。