演化计算技术

第 l8卷 第 1期 2D00年3月 海 南 大 学 学 报 自 然 科 学 版 NA'I3LIRAL SCIENCE JOURNALOFHAINAN UNI3．qERSITY V 18 No 1 M盯． 20∞ 77， D。fo孑 演化计算技术 姚 敏 王卫红 (浙江太学信息学院计算机系，杭州 310028)(浙江省气象局，抗州 310007) (=)2 ， ]P s 擒 要 演化计算是一类借鉴生物界自然选择和自然遗传机蹦而发展起来的通用问题求解方 法 ．本文简要讨论演化计算的基本原理 ，包括演化计算的基本概念、基本结构 和基本特征 以及 演化计算的主要范倒等． 关键词 苎些 蔓!鎏莲蔓墨!． 中国图书资料分类号 TP 301．6 演化规划；演化策略 ；遗传程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 达尔文进化论是一种稳健的搜索和优化机制 ．大多数生物体是通过 自然选择和有性生殖 进行进化，自然选择决定 了群体哪些个体能够生存和繁殖，有性生殖保证了后代基因中的混合 和重组 ．自然选择的原则是适应者生存，不适应者被淘汰． 演化计算正是一类借鉴生物界 自然选择和 自然遗传机制而发展起来的通用问题求解方 法 ．它采用简单的编码技术来表示各种复杂的结构，进而进行简单的遗传操作和优胜劣汰的自 然选择来指导学习和确定搜索方向，由于它采用种群的方式组织搜索，使得它可以同时搜索解 空间的多个区域 ，从而特别适合太规模并行 ，在赋予演化计算 自组织 、自适应、自学习等特征的 同时，优胜劣汰的 自然选择和简单的遗传操作使演化计算具有不受其搜索空间限制性条件(如 可微、连续等)的约束及不需要其它辅助信息(如导数)的特点，这些崭新的特点使得演化计算 不仅能获得较高的效率，而且具有简单、易于操作和通用性．目前，演化算法已经在计算机科 学 、 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 技术、管理科学和社会科学等众多领域得到了越来越广泛的应用_I J． 下面就关于演化计算的基本原理以及演化计算的主要范例等方面进行论述 1 演化计算的基本原理 ¨ 1，1 演化计算的基本概念 经近3O多年的不断研究和应用，已经清楚地表明了模拟自然进 化的搜索过程可以产生非常鲁棒的计算机算法，演化算法正是基于这种思想发展起来的一类 随机搜索技术 ，它们是模拟由个体组成的群体的集体学习过程 ．其 中每个个体表示给定问题搜 索空间中的一点 ．演化算法从任一初始的群体出发，通过随机选择 、变异和重组过程，使群体演 化到搜索空间中越来越好的区域．选择过程使群体中适应性好的个体比适应性差的个体有更 多的复制机会，重组算子将父辈信息结合在一起并将它们传到子代个体 ，变异在群体中引入了 新的变种． 1．2 演化计算的基本结构 不同的编码 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 、选择策略和遗传算子相结合构成了不同的演化 算法，但演化算法的基本结构可描述为： 收精 日期 ：1999—04—12 作者简介 ：姚敏 。男，1954年生，础教授 ，博士 武汉大学软件工程国家重点实验室基金资助项 日(编号：sⅡ3—03) 维普资讯 http://www.cqvip.com 海 南 大 学 学 报 自 然 科 学 版 2000妊 算法 l(演化算法的基本结构) 随机初始化种群 P(O)=1 Xt, 2 ． ⋯ ， }，t：0； 计算 P(0)中个体的适应值 ； while(不满足终止准则)d0 由 P(￡)通过遗传操作形成新的种群 P(t+1)； 计算 P( +1)中个体的适应值 ，t=f+1； 上述的基本结构是一个 比较粗略的框架 ，在具体实现时 ，可使用较为详细 的结构，如按照 种群的组织方式可分为非重叠和重叠种群的演化算法以及单种群和多种群的演化算法；按照 遗传算子的执行方式可分为非重叠和重叠遗传操作的演化算法等 ． 1．3 演化计算的基本特征 智能性 演化计算的智能性包括 自组织、自适应和 自学 习等．应用演化计算求解问题时， 一 旦确定了编码方案、适应值函数以及遗传算子以后 ，算法将利用演化过程中获取的信息进行 组织搜索．由于基于 自然选择的策略为：适者生存、劣者淘汰，故适应度大的个体有较高生存概 率．通常适应值大的个体具有与环境更适应的基因结构 ，再通过杂交和基因突变等遗传操作可 能产生与环境更适应的后代 ．演化算法这种 白组织、白适应特征同时也赋予了它具有能根据环 境的变化 自动发现环境的特性和规律的能力 ．同时，自然选择消除了算法设计过程中的一个最 大障碍 ：即需要事先描述问题的全部特点，并说明其相应的措施 ．于是，利用演化计算的方法， 我们可以解决那些结构 尚无人理解的复杂问题． 本质并行性 演化计算的本质并行性表现在 2个方面：一是它的内在并行性；二是它的内 含并行性 ．前者是指演化算法本身非常适台大规模并行 ．若干个各 自独立种群的演化计算过程 中可以不进行任何通信 ，等到运算结束才通信比较，选择最佳个体，这种并行处理方式对并行 系统结构也投有什么限制和要求 ．后者说明由于演化计算采用种群的方式组织搜索 ，使得它可 以同时搜索解空闻的多个区域，并相互交流信息，这种搜索方式使得它虽然每次只执行与种群 规模 Ⅳ成 比例 的计算，而实质上已经进行了大约 0(N )次有效搜索．这使得演化计算能较少 的计算获得较大的效益 ． 过程性 演化计算通过自然选择和遗传操作等组织行为来增强群体的适应性，算法模拟 的是一个过程 ，算法的实施也是一个过程 ． 多解性 演化计算采用群体的方式组织搜索，即从多个点出发，通过这些点的内部结构的 调整和重组来形成新的点集，因而每次都将提供多个近似解． 不确定性 由于演化计算的主要步骤都古有随机因素，因而在算法的演化过程中，事件的 发生与否有很大的不确定性． 非定向性 自然选择和生殖这种非定 向机制是演化计算的关键．它没有确定的迭代方程 ， 也不依靠梯度下降法似的爬 山策略，而是用调整群体的内部结构的方法来增强其对环境的适 应度 ． 内在学习性 学习是演化过程自身所具有的不可与其分割的行为方式 ．与 自然演化过程 I 维普资讯 http://www.cqvip.com 第 1期 姚敏 王卫红：演化计算技术 类似，它也有3种不同的学习方式：宗亲学习(祖先的良好特征通过遗传传递给后代，后代通过 家族成员“血缘”继承方式来学习先辈的 自适应行为)、社团学 习(独立群体 内部知识和结构的 共享)和个体学 习(通过改变个体的基因结构来提高自己的适应度)．而这些学习方式又内在地 体现在演化计算的整个过程 中． 统计性 演化计算的种群方式决定它是一个统计过程．在每一演化代都要进行统计，以确 定个体的优劣并推动演化的进行． 稳健性 演化计算利用个体的适应值来推动群体的演化，而不管求解问题本身的结构特 征，因而只需要设计相应的适应性 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 函数，而无需修改算法的其它部分，就可用来求解不同 的问题．同时，因为演化计算具有自然系统的自适应特征，算法在效益的效率之问的权衡使得 它能适用不同的环境并取得较好的效果． 整体优化 传统的优化方法一般采用梯度下降的搜索策略，往往容易陷入局部最优．而演 化计算能同时在解空间的多个区域内进行搜索，并且能以较大的概率跳出局部最优 ，以找出整 体最优解 ． 2 演化计算的主要范例 演化计算目前有4大分支：遗传算法(senede a d山m，简称 cA)、演化规划(evoludon pro— granmfing，简称 EP)、演化策略(evolution strategy，简称 ES)和遗传程序设计(genetic progt~ ， 简称 GP)．虽然这几个分支在算法实现方面具有一些细微的差别．但它们的共同特点都是借助 生物演化的思想和原理来解决实际问题的 ． 2．1 遗传算法 遗传算法可以形式化描述如下： C．d=(P(0)，N，f， ，g，p，f， )， 其中 P(0)=( I(0)．a2(0)，⋯， (0))∈ ，表示初始种群； J= ={0．1} 表示长度为z的二进串全体，称为位串空间； 』v表示种群中含有个体的个数 ； 表示二进制串的长度； ：／N一 表示选择策略； g表示遗传算子，通常包括繁殖算子、杂交算子和变异算子； P表示遗传算子的操作概率 ，包括繁殖概率、杂交概率和变异概率； r．，_， 是适应函数； t： 一{0．1}是终止规则． 2．2 演化规划L8,9j F％,el L J等在人工智能的研究中发现，智能行为就是要具有能预测其所 处环境的状态 ，并按照给定的 目标作出适当响盛的能力 ．他们在研究中将模拟环境描述成是由 有限字符其中的符号组成的序列．于是问题便转化为：怎样根据当前观察到的符号序列作出响 应以获得最大的收益．这里收益的计算是根据环境 中将要出现的下一个符号及预先定义好的 效益目标来确定的．演化规划中常用有限态 自动机(简称 rSM)来表示这样的策略．问题是如何 设计出一个有效的 FSM．vogel L J等借用演化的思想对一群FSM进行演化以获得较好的FSM． 他们将此方法应用到数据论断、模式识别和分类以及控制系统的设计等问题之中，取得了较好 的结果． 2．3 演化策略_l0J 演化策略模仿自然进化原理作为一种求解参数优化问题的方法．早期演 维普资讯 http://www.cqvip.com 簿 南 大 学 学 报 自 然 科 学 舨 2OOO矩 化策略的种群中只包含一个个体，而且只使用基于正态分布的变异操作．在每一演化代，变异 后的个体与父体进行比较再选择两者之优．这种演化策略称为(1+1)演化策略． (1+1)演化策略存在诸如有时不能收敛到全局最优解、效率较低等缺陷．它的改进是增加 种群内个体的数目，从而演变为( +1)、( + )以及( ， )等演化策略．演化策略与遗传算法的 不同之处在于：遗传算法要把原问题的解空间映射到位串空间之中，然后再施行遗传操作．它 强调个体基因结构的变化对其适应度的影响．而演化策略则是直接在解空问上进行操作 ．它强 调演化过程中从父体到后代行为的自适应性和多样性 ．从搜索空间的角度来说 ，演化策略强调 的策略是直接在解空间上进行操作，强调演化过程中搜索方向和步长的 自适应调节． 2．4 遗传程序设计【l1】 遗传程序设计的过程实际上就是从所有可能的计算机程序形成的空 间中，搜索有高的适应值的计算机程序个体，在这个过程中，几百或几千个计算机程序参与遗 传演化． 遗传程序设计强调物种行为的变化．演化程序设计系统的表示自然地面向任务级 ．一旦选 定一种适应性表示，就可以定义依赖于表示的变异操作，在具体的双亲行为上创建子孙． 遗传程序设计最初由一随机产生的计算机程序群体开始，这些计算机程序由适合于问题 空间领域的函数所组成，这样的函数可以是 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的算术运算函数，标准的编程操作，逻辑函数 或由领域指定的函数．群体中每个计算机程序个体是用适应值测试来评价的，该适应值与特定 的问题领域无关． 遗传程序设计可繁殖出新的计算机程序以解决问题 ，它分 3个步骤 ： 1)产生出初始群体，它由关于问题(计算机程序)的函数随机组台而成； 2)迭代执行下述步骤，直到满足选种标准为止； ◆ 执行群体 中每个程序 ，根据它解决问题的能力，给它指定一个适应值 ． ◆ 应用变异等操作刨造新的计算机程序群体 ．基于适应值根据概率从群体中选出一个计 算机程序个体，然后用台适的操作作用于该计算机程序个体．把现有的计算机程序复制到新的 群体中．通过遗传随机重组两个现有的程序 ，创造出新的计算机程序个体 ． 3)在后代中适应值最高的计算机程序个体被指定为遗传程序设计的结果．这一结果可能 是问题的解或近似解． 3 结 语 演化计算是多学科结合与渗透的产物．它已发展成一种自组织、自适应的综合技术．演化 计算的研究工作主要集中在以下几个方面 ： 1)基础理论研究；2)基于知识的新的计算模型；3)并行和分布式 演化计算 ；4)演化机器 学习；5)演化神经网络；6)演化模糊系统；7)演化计算应用系统；8)演化硬件；9)演化软件． 目前，演化计算与神经网络、模糊系统一起形成了一个新的研究方向——计 算智能(Coin． putational Intelligence)．与传统的符号智能相比，计算智能是一种全新的智能模拟技术．符号智 能以物理符号系统为基础，研究知识表示、获取、推理过程等，而计算智能则是以数据为基础， 通过训练建立联系，进行问题求解．可以说，计算智能的出现已经使人工智能从传统的符号主 义向多元化方向发展，并且已经在许多领域取得了可喜的成果．同时，计算智能的发展必将引 起更加深刻的“智能革命”，从而使人的自然智能得到更有效的模仿和扩展，实际社会生产的自 动化和智能化，促进知识密集型经济的发展 ． (下转第 108页) 维普资讯 http://www.cqvip.com 108 海 南 大 学 学 报 自 然 科 学 版 2000年 两边积分。得 ． ． T2 2，I 4-{，I 8in2口+{ +mgl cos ： (常数)． (1o) 比较(8)、(9)式与(4)、(6)式，显然完全一样．而对于(10)式只须把欧拉运．t学方程代人(5)式 便可得(1o)式一样的结果．由上述推导可见，用拉格朗日方程求对称刚体的运动微分方程的第 l积分式比用牛顿力学方法简便得多 ，特别是车问题中拉氏函数 L不含 和 ，即 和 都是 循环坐标，使问题变得更为简便． 参 考 文 献 1 周衍柏编 ．理论力学教程．第2版．北京：高等教育出版杜，1986 2 朱照宣，周起盒，殷盒生编．理论力学(下册)．北京：北京大学出版杜，1982 3 肖尚彬．董秋泉编 ．蛇螺力学．北京 ：人民教育 出版杜，1981 (上接第8o页) 参 考 文 献 1 谱正君，康立山，陈毓屏．演化计算．北京：清华大学出版社，1998．203页 2 姚新，陈国良，徐惠敏．进化算法研究进展．计算机学报，1995，18(9)：694—706 3 贺前华，韦岗，砧以勤．基因算法研究进展．电子学报，1998，26(10)：118—122 4 Miehale,aiez Z，~chalevfiez M．Evolul~onary c0n 曲由n teehnlquea their印Pli∞ ．Proceedings 0f the IEEE 1CII~，1997．14—25 5 cl面 枷 1aTlaklI1 S，m 晒en P，Avate~ V．Genetic algohthras in fon~atstmg commercial banks detx~it．Pro- ( 蜘 the IEEE 1CIPS，1997．116—121 6 Olmlofi K， T．t,~ic syntIle幽 l商Ilg gene a d恤 ．Proceedlngs 0ftheIEEEICII~，1997．137—142 7 Tmn JM，H叫唱 JW，Zhao C J．Hybrid syste~m oiXfir,lzationI商Ilg genetic dⅡ帅 ．Proceedings 0ftheIEEE1CIPS， 1997．579—583 8 WangH G，脑 JC．1lIe hybrid genetle幽 tIⅡnh solv／ngm 印ⅡIlirIg．Proceedings 0ftheIEEEICIPS， 1997．5舳 一591 9 宋爱国。陆估人．基于进化规划的 Koh~en网络用于被动声纳目标聚类研究．电子学报，1998，26(7)：124— 132 10 yG，TurgotA．Evolufi0~ary PⅡm forthe o rr ol1 a genetic el~ssitier． of theIEEE 1CIF~，1997．574—578 11 MengxW，ChengH．Using e II 唧 Fa'Oga'mnn~ng to co h。p6eld n哪al networks．胁 伊0ftheIEEE 1C ．1997．571—573 维普资讯 http://www.cqvip.com