（计算机软件与理论专业论文）gep评估及个体多样性对策.pdf

摘要 遗传算法和遗传编程作为进化计算模型中的两个最典型的分支，已 成为人工智能的研究热点。遗传算法采用线性编码解决简单问题，而遗 传编程采用树结构编码来解决复杂问题。2 0 0 1 年，葡萄牙学者c a n d i d a f e r r e i r a 在遗传算法和遗传编程的基础上扬长避短，提出了基因表达式编 程算法( g e n ee x p r e s s i o np r o g r a m m i n g ，简称6 e p ) 。g e p 克服了遗传算法 和遗传编程各自的缺点，综合了它们的优点，通过简单紧凑的编码解决 复杂的应用问题，易于进行遗传操作，其性能比遗传编程高出2 4 个数量 级。作为进化计算中的一个新分支，g e p 的研究才开始，它需要更加坚 实的理论基础来完善自己。本文在前人工作的基础上对g e p 的研究现状、 原理、不足、改进及应用进行了研究。 本文的主要研究工作包括以下几个方面： ( 1 ) 分析了传统g e p 算法的局限性。 ( 2 ) 提出了一种新的g e p 解码方法( s t a c kd e c o d i n g ，s d ) ，该方法利 用堆栈直接对染色体进行解码和适应度评价，无需将染色体转换为表达 式树，从而提高了算法的运行速度，并且通过符号回归实验进行了验证。 ( 3 ) 为了保持g e p 进化过程中的种群多样性，在s d 方法的基础上， 以元胞自动机模型为框架，提出了基于堆栈解码的元胞基因表达式编程 算法( s t a c kd e c o d i n gb a s e dc e l l u l a rg e n ee x p r e s s i o n p r o g r a m m i n g ， s d c g e p ) ，符号回归和预测分析实验表明该算法在运行速度和预精确度 上均超过传统g p 、g e p 算法。 ( 4 ) 将g e p 运用到组合优化领域，分析了g e p 求解t s p 问题的技术。 针对传统g e p 算法多样性不足的缺点，在g e p 的基础上引入基因均匀分 布策略和基于全局收敛策略的变重组、变异概率算子，提出了改进的g e p 算法( i m p r o v e dg e n ee x p r e s s i o np r o g r a m m i n g ，i g e p ) ，并将其应用于求解 t s p 问题，实验表明i g e p 在求解t s p 问题上具有更优的性能。 关键词：基因表达式编程；解码；元胞自动机；符号回归；t s p 问题 a bs t r a c t g e n e t i ca l g o r i t h m ( g a ) a n dg e n e t i cp r o g r a m m i n g ( g p ) a r et h em o s t i m p o r t a n tc o m p u t a t i o n m o d e l si ne v o l u t i o n a r yc o m p u t a t i o n t h e yh a v a b e c o m eah o tp o i n ti nt h er e s e a r c ho fa r t i f i c i a li n t e l l i g e n c e g au s e sl i n e a r s t r i n g a sc h r o m o s o m ec o d e ，a n ds o l v e ss i m p l ep r o b l e m s g pu s e s t r e e s t r u c t u r ea sc h r o m o s o m ec o d e ， a n ds o l v e s c o m p l e xp r o b l e m s i n 2 0 0 1 ，f c a n d i d ap r o p o s e san e we v o l u t i o n a r yc o m p u t a t i o nm e t h o dn a m e d g e n e e x p r e s s i o np r o g r a m m i n g ( g e p ) ，b a s i n g o ng aa n dg p g e ph a s o v e r c o m et h es h o r t c o m i n go fg aa n dg p ，i n t e g r a t e i n gt h e i ra d v a n t a g e s i t c a nb eu s i n gs i m p l ec o d ee x p r e s s i o nt os o l v ec o m p l e xa p p l i c a t i o np r o b l e m s i th a se a s i e rg e n e t i co p e r a t i o na n dm o r ep o w e r f u lg e n e t i co p e r a t o r a sa n e wb r a n c ho fe v o l u t i o n a r yc o m p u t a t i o n ，g e pn e e d sm o r es o l i dt h e o r e t i c a l f o u n d a t i o nt op e r f e c ti t s e l f , a n dm o r ef i e l d s t op r o v ei t s e l f t h i sp a p e r m a i n l y d e v e l o p s w o r ko n p r e s e n t r e s e a r c hc o n d i t i o n ，p r i n c i p l e ， i n s u f f i c i e n c y ，i m p r o v e m e n ta n da p p l i c a t i o no fg e p t h em a i nc o n t e n to ft h i sa r t i c l ei sa sf o l l o w s ： ( i ) d i s c u s st h eb a dp o i n to fs t a n d a r dg e p ( 2 ) an o v e lg e pd e c o d i n gm e t h o dn a m e ds t a c kd e c o d i n gw a sp r o p o s e d i td i dn o tn e e dt ot r a n s f o r mt h ec h r o m o s o m ei n t oe x p r e s s i o n t r e e ，b u t d i r e c t l yu s e ds t a c kf o rd e c o d i n ga n de v a l u a t i n gc h r o m o s o m et oa c c l e r a t et h e e v o l u t i o nr a t e t h er e s u l ts h o w st h a ti to u t p e r f o r m st h ec o n v e n t i o n a lg e p i n e v o l u t i o n a r ye f f i c i e n c y ( 3 ) i n o r d e rt ok e e pd i v e r s i t yo ft h ep o p u l a t i o n ，i ti m p r o t e dc e l l u l a r a u t o m a t at oa v o i dt h ep r o b l e mo fp r e m a t u r ec o n v e r g e n c e t h er e s u l ts h o w s t h a ti to u t p e r f o r m st h ec o n v e n t i o n a lg e pi np r e d i c t i o na c c u r a c y ( 4 ) i nt h ef i e l d o fc o m b i n a t o r i a lo p t i m i z a t i o n ，d e s c r i b e dt h ek e y t e c h n o l o g yo fs o l v i n gt s pp r o b l e m sb yg e p a ni m p r o v e dg e n ee x p r e s s i o n p r o g r a m m i n ( i g e p ) w a sp r o p o s e d i ti m p o r t e dg e n es p a c eb a l a n c es t r a t e g y a n dt h eg l o b a lc o n v e r g e n c es t r a t e g yb a s e do nt h ep r o b a b i l i t yo fm u t a t i o n o p e r a t o r s t h er e s u l t ss h o w st h a ti g e ph a sb e t t e rp e r f o r m a n c e k e yw o r d s ：g e p ；d e c o d i n g ；c e l l u l a ra u t o m a t a ；s y m b o l i c ；t s p 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本 声明的法律后果由本人承担。 作者签名： 杨棚 日期：纠c ) 年箩月弓日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密囝。 ( 请在以上相应方框内打“ ) 作者签名： 导师签名： 杨柳 乍弘 日期：为，7 d 年岁月刃e 1 日期：训。年0 月日 第一章绪论 1 1 研究的背景和意义 自动程序设计是计算机科学和人工智能的一个长期奋斗目标。19 5 9 年，a r t h u rs a m u e 将自动程序设计定义为：使计算机去做所需要做的事， 而不需告诉它如何去做。典型的例子就是：给定多组数据，期望发现所 有数据之间的关系，也就是找到一个程序，即函数表达式，使得对指定 的输入，输出相应的数据。2 0 世纪9 0 年代初，s t a n f o r d 大学学者k o z a j r 提出了遗传程序设计( 简称g p ) ，它模仿自然界生物的选择和遗传机制， 运用遗传算法的思想，采用非线性的、可变分层树结构来表示计算机程 序，自动生成解决问题的程序。遗传程序设计采用遗传算法实现程序自 动化设计，具有强大的问题解决能力，为自动程序设计提供了一个重要 的方法。 目前，遗传程序设计在预测、分类、符号回归和图像处理等领域已 经得到广泛的应用，其基本思想是：随机生成一个适用于所给问题的初 始群体，即问题的搜索空间；而构成群体的所有个体都有一个适应度值； 按照达尔文适者生存的原则，利用遗传算子处理高适应度的个体，来产 生下一代群体；如此循环下去，所给问题的解或进似解将会出现在某一 代种群中。遗传程序设计是在遗传算法基础上发展起来的一种新型的全 局搜索优化算法，因此它与遗传算法有一些相同点。第一，二者都是属 于进化计算的范畴，基于达尔文的进化论，借助生物进化“优胜劣汰 的原则解决实际问题。第二，适应度的评价是算法进化的自然驱动力， 它们均利用适应性来控制群体中结构改变的过程。最后，遗传程序设计 和遗传算法都具有本质的并行性。 但是，它们在具体实现方面却存在着较大的差异。在编码上，遗传 算法通常采用具有确定长度的线性符号串，而遗传程序设计以分层的树 结构作为个体染色体。树的叶节点为终止符，组合终止符的函数以及运 算符只能作为树的根节点或中间节点。每个树结构都对应问题的一个可 能解，也可以理解为求解该问题的一个计算机程序。这种复杂的编码结 构使得遗传程序设计的个体染色体具有功能多样性优点，同时也带来了 一些缺点。首先，由于树形结构需求空间庞大，复制操作比较麻烦。其 次，分层树在自身作变异操作时，为保证语法树在句法上的正确性，一 般都是随机选择一个节点，并用随机产生的新的子树进行替换。总的来 说，遗传编程的遗传操作复杂，最总导致演化时间过长。 2 0 0 1 年，葡萄牙学者c a n d i d af e r r e i r a 在遗传算法和遗传程序设计的 基础上扬长避短，提出了基因表达式编程算法【1 1 ( g e n ee x p r e s s i o n p r o g r a m m i n ，简称g e p ) 。g e p 是一种新型的基于基因型和表现型的自适 应演化算法，它克服了遗传算法和遗传程序设计各自的缺点，综合了它 们的优点，能够通过简单紧凑的编码解决复杂的应用问题，并且易于进 行遗传操作，其性能比遗传程序设计高2 4 个数量级。在缺乏先验知识和 不了解事物内部机制的前提下，g e p 可以通过实验数据来挖掘较为准确 的公式，以较高的精确度和较强的适应性在许多应用领域都取得了非常 好的效果。此外，g e p 为自动程序设计提供了另外一种可行的方法，目 前已成为前沿研究热点。然而，作为进化计算中的一个新分支，g e p 的 研究才刚刚开始，它需要更加坚实的理论基础来完善自己，需要更多领 域的应用来证实自己。因此，对g e p 的改进及其应用研究意义深远。 1 2 国内外研究现状 c a n d i d af e r r e i r a 于2 0 0 1 年l2 月在c o m p l e xs y s t e m s 上首次公开发 表了她的关于g e p 的第一篇文章。2 0 0 3 年，她出版了第一本关于g e p 的专著g e n ee x p r e s s i o np r o g r a m m i n gi ：m a t h e m a t i c a lm o d e l i n gb ya n a r t i f i c i a li n t e l l i g e n c e ) ) ，该书中通过实验的方法讨论了符号回归、问题求 解、参数优化、函数发现、时间序列预测、逻辑综合、分类规则、细胞 自动机、组合优化、以及g e p 在神经网络中的应用等问题，为g e p 的研 究奠定了良好的基础。2 0 0 6 年，她又出版了第二本专著g e n ee x p r e s s i o n p r o g r a m m i n gi i ：m a t h e m a t i c a lm o d e l i n gb ya na r t i f i c a li n t e l l i g e n c e ) ) 。近年 来，国内外许多学者对g e p 展开了广泛而深入的研究。 目前，国内对g e p 的研究也有了一定的成果，最为突出的要数四川 大学，他们在公式发现、关联规则发现、函数挖掘、太阳黑子预测、因 子分解取得了较好的进展，对g e p 理论进一步完善的成果也发表。 1 理论研究 针对g e p 理论分析的空白与不足，文献 2 】对g e p 的基本概念进行 了一系列形式化描述，利用马尔可夫链理论，对离散型群体的g e p 进行 了收敛性分析。而对于群体为一般型的g e p ，分析了适应度函数的收敛 性，并证明了依概率收敛定理和最小残差平方。从而在理论上保证了g e p 算法的可靠性和可行性。由于g e p 从提出迄今尚无完整的理论体系，文 献 3 】通过分析g e p 的基因结构，提出了g e p 模式的概念，并从理论角度 2 解释g e p 的进化机理及其强大的最优解发现能力。最后，通过一系列推 理得到了公式化g e p 模式定理，对比分析验证了理论的正确性。 2g e p 基本技术的改进 初始种群的多样性是否丰富对进化效率和进化结果至关重要，文献【4 提出了基因空间均匀分布策略，证明了描述编码空间量化性质的g e p 编 码空间定理。文献 5 】提出了一种基于均匀设计的基因表达式程序设计算 法，该算法对经典的g e p 做了如下改进：利用混合水平均匀表生成初始 种群，保证了分布的均匀性；同时引入自适应多亲杂交算子，利用均匀 优化代替随机进化。最后，从理论上分析并证明了该算法具有全局收敛 性，且收敛速度优于传统g e p 算法。文献【6 】提出了优势种群产生策略， 该策略可以产生具有基因多样性且适应度较高的个体，更加有效地提高 了g e p 的搜索效率。 由于传统的g e p 算法进化过程中多样性表现不足，文献【7 】提出了 一种基于动态变异算子的改进g e p 算法，实验表明新算法建立的复杂函 数反问题拟合模型更加优秀。文献 8 】提出了g e p 进化阶段和基因组多样 性评估模式的定义，以及描述进化阶段的进化因子概念和分阶段进化策 略；采用动态遗传算子设计以及群体规模控制方法，使进化能够更快跳 出局部最优。文献【9 】用变种群策略的快速跳出局部最优，通过在进化过 程中增加g e p 群体的基因多样性，提高g e p 的并行搜索能力，从而可以 使g e p 算法在进化过程中较快地跳出早熟和局部最优状态。文献 10 】提 出了远缘繁殖策略和动态适应度函数策略，远亲繁殖并及时变换评估个 体的标准，增加了进化过程中种群的多样性并有利于选择优质个体。 另外，文献【l l 】对g e p 的遗传操作进行改进提出了残差制导进化算 法，该算法对几种有可能产生比当前最佳染色体更好的个体的遗传操作 分配指标任务，即要求该遗传操作在每一代操作中生成的残差平方和小 于上一代最小残差平方的染色体个数至少达到规定的阈值，若没有完成， 则在本代遗传操作中调整其遗传率，重新进行遗传操作使下一代群体中 残差平方和小于上一代最小残差平方的染色体个数尽可能多。文献【12 】 提出了一种基于动态变异算子的改进g e p 算法，该算法用于求解复杂函 数的反问题十分有效。文献 13 】提出了五种常数产生方法：基于最好个体 的随机变异法、基于最好个体的爬山变异法、基于种群前a 的爬山变异 法基于种群a 的随机变异法、以及间隔一定代数的整个种群的随机变异 法。 3 与其他理论的结合 借鉴生物界的“返祖现象 ，提出了基于回溯的基因表达式编程方法， 3 提高知识发现效率i t4 。引入多层染色体思想，利用染色体构建的层次调 用模型对个体进行表达，在解决电路进化，函数发现等实际问题中取得 了良好效果【1 5 】。为了有效干预进化质量、过程和速度，把生物工程转基 因思想移植到基于g e p 的函数挖掘中，获得了一系列成果1 1 6 1 。受生物基 因片段重叠表达现象的启发，提出了一种新的基于重叠表达进化算法， 同时该方法还融合了免疫算法关于浓度的计算技术【t ，l 。实验表明，新算 法在高次函数发现问题上具有很大的优势。提出了原子基因片断的概念， 以保护进化良好的基因片断；引入了基因嫁接思想，实现了n g e p 原型i is l 。 文献【19 】将克隆选择算法与g e p 算法相结合用于数据挖掘的分类问题求 解中。文献 2 0 l 借鉴g p 中的模块化结构思想，提出了基于g e p 的松散模 块结构，从而实现g e p 中的模块重用。 文献 2l 】通过模拟退火算法调整变异概率构造了自适应变异算子，该 算子能根据解的质量自适应地调整搜索区域，实验结果表明自适应变异 算子能有效地提高多种群的搜索能力。将模拟退火机制与遗传机制相结 合，以提高算法跳出局部最优的能力，文献 2 2 提出了基于模拟退火的并 行基因表达式编程算法。将模拟退火思想引入到标准g e p 算法的选择算 子中，提出了基于模拟退火的基因改进型基因表达式编程算法 r g g e p s a ，该算法具有更高的稳定性1 2 3 1 。另外，还有g e p 算法与遗传 算法，免疫算法结合的相关研究1 1 4 1 1 2 5 1 。 4 适应值计算方法 传统g e p 算法在计算个体适应度值时，需要将染色体转换为表达式 树，造成算法空间和时间效率较低。为了解决这一问题，相继出现了基 因阅读运算器方法 2 6 1 ，具有线性复杂度的g e p 适应度评价l d e e o d e 方法 1 2 7 1 ，基于s c a l e 的基因评估方法【2 。j 。以上这些方法均不用动态生成释放大 量表达式树，而是直接对染色体进行操作得到该染色体的适应值。 5 应用 近几年来，基因表达式编程的应用在以下几个方面表现比较突出。 ( 1 ) 符号回归 符号回归问题就是对给定的一组数据进行函数建模，也就是找出一 个符号形式的函数，以指定的精确度拟合一组相关变量的有限样本的数 据点集。g e p 不需要对模型的形式作事先假定，在没有先验知识的前提 下，自动实现建模过程。文献【2 9 】最早成功地将g e p 算法应用的符号回 归领域。 ( 2 ) 时间序列预测 时间序列预测就是通过编制和分析时间序列，预测下一段时间或以 4 后若干年内可能达到的水平，已被广泛的应用在金融经济一一如股票价格 预测1 3 0 、气象水文、灾害预警、信号处理等领域。基因表达式编程的出 现打破了传统统计学预测方法的先验知识需求约束，以其较快地速度和 较高的预测精度而成为近年来时间预测方法中的个研究热点。已有研 究者提出了基于g e p 的时间序列模型构造 3 t l 方法：滑动窗口预测法和微分 方程预测法。前者直接发现时间序列中历史数据到未来数据的函数关系， 并以此进行预测；而后者则利用训练数据建立关于时间的高阶常微分方 程，并根据给定的初值进行预测。文献【3 2 】提出了基于g e p 的数据流预 测模型，根据过去时间窗口上的数据来预测未来窗口的值，并且预测函 数被数据流所驱动而不断演化。在全局的空间内搜索最优的预测函数， 从而保证预测模型能广泛适用于各种复杂的数据流。 ( 3 ) 分类 分类属于数据挖掘领域的内容，指的是找出一个类的概念描述，它 代表了这类数据的整体信息，即该类的内涵描述。一般用规则或决策树 模式表示，该模式能把数据库中的元组映射到给定的类别中。常用方法 有建立分类决策树的方法和建立分类规则的方法。目前已有研究者利用 g e p 构造决策树来解决分类问题，其性能可与i d 3 算法相比，并且能解 决n c l a s s 问题【3 3 l 。文献 3 4 】利用g e p 提取分类规则并通过实验证明新方 法的分类精度优于c 4 5 算法。文献【35 提出了关于g e p 应用于分类问题 的新方法，其研究结果表明g e p 算法应用于分类的有效性。 ( 4 ) 关联规则挖掘 关联规则挖掘问题就是在事务数据库中找出具有用户给定义的最小 支持度和最小置信度的关联规则。关联规则的研究始于事务型数据库， 已成为数据库知识发现领域的一个热点课题，被广泛地应用于贱卖分析、 商品目录设计、生物序列检测、网络入侵检测等。在g e p 方面，已有研 究者设计了基于基因表达式程序设计的关联规则挖掘系统【3 】。 ( 5 ) 其他领域 文献【3 7 】利用g e p 进行电路设计，设计了染色体编码、适应值函数， 实验证明新方法具有更好的效果。在传感器校正方面，已有研究者提出 了基于基因表达式程序设计的用于解决传感器系统非线性校正问题的 s g e p 算法，该方法比传统的硬件校正更灵活【3 s 】。文献【39 提出了基于基 因表达式程序设计的网格调度域计算节点的选取算法，并通过实验证明 该算法的优越性和实用性。另外，g e p 已被应用到数字图像分割【4 0 l 、磁 盘负载均衡方面【1 。文献【4 2 】运用g e p 求解第一类f r e d h o l m 积分方程并 取得了较好的效果。另外，g e p 还应用到了高能量物理数据分析，i p 路 5 由优化以及一维混沌映射等领域【m 4 s 。 1 3 研究的主要内容和思想 本文分析了传统g e p 算法的适应度评估和种群多样性的局限性。传 统g e p 算法在进行适应度评价时，需要反复构造和遍历表达式树，本文 利用堆栈直接对染色体进行解码和适应度评价，提出一种新的g e p 解码 方法f s t a c kd e c o d i n g ，s d ) ，该方法大大提高了算法的效率。在此基础上， 针对传统g e p 算法进化过程中多样性不足，以元胞自动机模型为框架， 提出基于堆栈解码的元胞基因表达式编程算法( s t a c kd e c o d i n gb a s e d c e l l u l a rg e n ee x p r e s s i o np r o g r a m m i n g ，s d c g e p ) 。通过符号回归和预测 分析实验对比，结果表明s d g e p 算法在演化效率和预测精度上均超过 传统g p 、g e p 算法。将g e p 应用于组合优化问题领域，阐述了g e p 求 解t s p 问题的基本方法。另外，针对传统g e p 算法初始种群多样性不足 以及进化过程中多样性不足的缺点，通过引入一系列多样性对策提出了 改进的g e p 算法( i m p r o v e dg e n ee x p r e s s i o np r o g r a m m i n g ，i g e p ) 。将i g e p 算法应用于求解t s p 问题，实验对比结果表明i g e p 算法性能更优。 第一章绪论。阐述课题研究背景、国内外研究的现状和发展趋势、 本文的研究内容以及本文的组织。 第二章介绍了进化计算的几个主要分支，对基因表达式编程算法的 两个起源算法一一遗传算法( g a ) 和遗传编程( g p ) 着重进行了介绍，详细 阐述了二者的基本思想及技术，对比了两者的不同点，指明了各自的优 缺点。 第三章介绍了基因表达式编程的基本思想和各项关键技术。 第四章分析了传统g e p 算法适应度评价和种群多样性的局限性， 为了改进g e p 的性能，提出了基于堆栈解码的元胞基因表达式编程算法 ( s t a c kd e c o d i n g b a s e dc e l l u l a rg e n e e x p r e s s i o n gp r o g r a m m i n g ， s d c g e p ) 。符号回归和预测分析实验结果表明，s d c g e p 算法在演化效 率和预测精度上均超过传统g p 、g e p 算法。 第五章将g e p 运用到组合优化领域，阐述了g e p 求解t s p 问题的 关键技术。针对传统g e p 算法多样性不足的缺点，在g e p 的基础上，引 入基因均匀分布策略和基于全局收敛策略的变重组、变异概率算子，从 而提出了改进的g e p 算法( i m p r o v e dg e n ee x p r e s s i o np r o g r a m m i n g ， i g e p ) ，并将i g e p 算法应用于求解t s p 问题，实验结果表明g e p 在求解 t s p 问题比传统g e p 算法具有更优的性能。 第六章对研究工作进行了总结，提出了下一步研究工作的设想。 6 第二章进化计算 进化计算是对自然界中生物进化机制的模拟，近年来已成为人工智 能和计算机科学的热点研究领域。本文研究的基因表达式编程是进化计 算的一个新的分支，由遗传算法和遗传编程融合而成。 2 1 进化计算概要 进化计算，又称演化计算，是一种基于群体导向随机搜索的技术和 方法。它的基本原理是进化机制和自然选择法则。进化计算采用简单的 编码技术来表示各种复杂的结构，并通过对一组编码进行简单的遗传操 作：复制、重组、变异以及优胜劣汰的自然选择来确定搜索方向。简而 言之，进化计算不需要了解问题的全部特征，就可以通过进化过程来完成 问题的求解。 总的来说，基于对生物进化机制的模仿，共有三种典型的进化计算 模型，它们分别是：遗传算法、进化策略和进化规划。这些方法各自有 不同的生物进化背景，强调了生物进化过程中的不同特性，通过不同的 生物进化机制开发出来的。但是它们都能产生一种鲁棒性较强的计算机 算法，适应面较广。 进化计算的三个分支虽起源于生物进化的不同背景，由不同的研究 人员独立开发出来的，但它们还是有很多共同点。第一，算法的操作对 象是由多个个体组成的群体，对每个个体优劣程度都有一个评价尺度一 一适应度。第二，算法都要通过选择复制操作来产生下一代，并由个体 交叉、变异等遗传操作来增加群体的多样性。第三，算法都是一个反复 迭代的过程，受随机因素的影响，均能够以较大的概率找到全局最优点。 最后，算法都具有一种天然的并行结构，均适合于在并行机中进行大规 模复杂问题的求解。由于进化算法具备以上这些特点，使得它们都能够 用于解决复杂系统的优化问题，并且不依赖于具体问题的种类，广泛地 应用于各种不同的领域中。 2 2 遗传算法 2 2 1 遗传算法简介 遗传算法是模拟生物进化原理提出的一种自适应全局优化概率搜索 7 算法【4 7 】。它最早由美国密执安大学的h o l l a n d t 提出，起源于6 0 年代初 对自然和人工自适应系统的研究。h o l l a n d 在自然和人工系统中的适应 性一书中系统阐述了遗传算法的基本原理。7 0 年代，d ej o n g 基于遗传 算法的思想在计算机上进行了大量的纯数值函数优化实验。8 0 年代， g o l d b e r g 在前人的研究基础上对遗传算法进行总结归纳，从而形成了遗 传算法的基本框架。他还出版了搜索、优化和机器学习中的遗传算法 一书，全面系统地论述了遗传算法的基本原理及应用，为这一领域奠定 了坚实的科学基础。9 0 年代，d a v i s 编辑出版了遗传算法手册一书， 书中包括了遗传算法在工程技术、科学计算和社会经济中的大量应用实 例。 遗传算法类似于生物体的进化过程，模拟自然选择和遗传机制，通 过染色体寻找待解决问题的最优解。遗传算法用线性编码空间表示问题 的参数空间，将适应度函数作为评价依据，以个体种群为进化基础，通 过对群体中个体位串的遗传操作实现遗传机制，建立起一个迭代过程。 在这一过程中，群体中的所有个体不断地进行遗传和进化操作，并且每 次都按照优胜劣汰的规则将适应度较高的个体以更高的机率地遗传给下 一代，最终在群体中将会得到优良的个体，从而解决问题。 遗传算法对于在求解复杂的优化问题时无需建模和进行复杂运算， 而是通过遗传算子寻找问题的最优解或近似最优解。遗传算法提供了求 解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，具有很 强的鲁棒性，已被广泛的应用于很多学科。例如：组合优化、函数优化、 自动控制、机器人学、生产调度问题、人工生命、图像处理、遗传编程 以及机器学习，1 等。 2 2 2 遗传算法的运算过程及基本要素 遗传算法在解决实际问题时需要进行数据转换操作：编码和解码。 将问题解空间中参数转换为线性编码( 染色体) 称为编码操作；而相反将编 码转换为原问题结构的过程叫解码。 遗传算法先将问题的可能解进行编码得到遗传空间的染色体，选取 若干个个染色体构成初始种群p ( t ) 。再根据预定的适应度函数来计算个体 的适应值，并且随机选择高适应值的个体作为父代染色体，通过交叉和 变异来产生下一代的群体p ( t + 1 ) 。其中，在计算个体适应度值时须先对 染色体进行解码操作。然后再判断是否达到最大进化代数，如果没有达 到最大进化代数，则对新群体继续进行遗传操作，直到达到最大进化代 数，此时输出具有最大适应度的个体作为最优解。图2 1 为遗传算法运算 过程示意图。 图2 1 遗传算法的运算过程示意 遗传算法主要构成要素如下。 ( 1 ) 编码。传统遗传算法使用固定长度的二进制符号串来表示种群的 个体，其等位基因由二值符号集 l ，0 ) 组成。其实质即是解空间到遗传空间 的映射。例如：x = 1 0 0 111 0 0 1 0 0 0 1 0 11 0 1 就是一个个体，该个体的染色体长 度为18 。其他编码方法还有：浮点数编码、多参数级联编码、格雷码编 码和多参数交叉编码。编码原则一般为应使用能易于产生与所求问题相 关的且具有低阶、短定义长度最小字符集。此外，编码要求具有完备性、 健全性和非冗余性。 ( 2 ) 适应值评价函数。遗传算法按与个体适应度成正比的概率决定当 前个体复制到下一代群体的机率。适应值评价函数由目标函数确定，而 且所有个体的适应度值必须为正数。对于不同的问题，必须预先确定目 标函数到适应值评价函数的转换规则。在使用适应度函数进行个体评价 之前，遗传算法必须先对个体进行解码操作。 ( 3 ) 选择算子。遗传算法使用选择算子对群体进行优胜劣汰，将具有 高适应值的个体以更高的机率的复制到下一代群体中。常用选择方法有： 比例选择、排序选择、最优保存策略、无放回随机选择、确定式采样选 择以及随机联赛选择。 ( 4 ) 重组算子。重组运算是指通过两个相互配对的染色体按某种方式 相互交换其部分基因，从而形成两个新个体染色体。常用的重组算子有： 单点重组均匀重组、两点重组、以及算术重组。图2 2 为遗传算法的重组 算子的具体执行过程。 9 父代1 父代2 子代l 子代2 ( a ) 交叉前 ( b ) 交叉后 图2 2 遗传算法的重组算子 ( 5 ) 变异算子。变异运算是指将个体染色体编码串中的某些基因座上 的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体染 色体。常用的变异算子有：均匀变异、基本位变异、非均匀变异、边界 变异以及高斯变异。以上三种遗传算子均用来产生下一代群体。图2 3 为遗传算法的变异算子的具体执行过程。 父代子代 i lll lll唧踽lolllolll 固il ll,i,掣国!：1 olllol 1 t 赤b *t 变异位 i 变异位 l ”4 ( a ) 变异前 ( b ) 变异后 图2 3 遗传算法的变异算子 ( 6 ) 遗传算法的运行参数。遗传算法有如下运行参数需要提前设定： 群体大小、交叉概率、遗传运算的终止进化代数以及变异概率。 2 3 遗传编程 2 3 1 遗传编程简介 k o z a j r 认为，各领域中许多看起来不同的问题都可以看成为寻找 一个确定计算机程序的问题：即当给定程序的某个输入则产生所需的输 出。19 9 2 年，他将遗传算法应用于计算机程序的自动生成和优化设计， 提出了遗传编程的概念。与之相关的研究成果有g e n e ticp r o g r a m m in g i ：o nt h ep r o g r a m m n i go fc o m p u t e r sb ym e a n s0 fn a t u r a ls e l e c t i o n 、 - - 1 ) 中， 并作为一个新的操作数进行如上的操作，直到表达式处理完毕。对于图 3 1 所示的表达式树的求值过程如表3 1 所示。 表3 1 表达式求值过程 操作顺序表达式 互卜b c -a b c - d + q 互卜t t d a t l d + q 互卜a t 2 +a t 2 + q 正卜五q t 3 q 1 6 3 3 适应度函数 适应度函数设计的合理性对取得求解问题的成功起了至关重要的作 用，在g e p 中也不例外。 符号回归的目的是寻找一个对在一定误差范围内的所有适应问题都 能运行良好的符号表达式。然而，如果误差范围选择过小，群体的进化 速度会减慢甚至找不到一个满意解。反之，选择范围过大，将会出现许 多具有最大适应度的解，而这些解可能与最优解相差甚远。 针对上述的两难问题，c a n d i d af e r r e i r a 在求解符号回归问题时提出 了两种新的适应度评价函数，该适应度函数使得系统在某个误差范围之 内就能找到满意解。其基本思想是：给出一个很广的选择范围，例如大 小为2 0 或1 0 0 的相对误差，不仅能够使其运行进化过程启动，而且能 够在想要的最小误差附近进行细微的调整。公式( 3 2a ) 表示基于绝度误差 的适应度评价函数，公式( 3 2b ) 表达基于相对误差的适应度评价函数。 z = ( m l c ( f ，j ) - 7 ( 州 ( 3 2a ) ，、1 z = 善叫等铲叫 2b ， 上面两个公式中：肘是一个常数，表示种群的选择范围；q 表示第i 个 染色体利用函数关系式在第_ ，个样本中的变量数据所求得的函数值；互n 表示第，个样本包含的实际测量值；c 表示样本的数目。 而对于更加复杂的布尔问题，c a n d i d af e r r e i r a 设计了以下适应度函 数： 1 i f n 寺c , ，t h e n f = n ；e l s e f = l ， 其中，n 是正确求得适应度样本的个数，而c 是所有的适应度样本的数目。 3 4 常数处理 数值常量的处理是数值公式发现的一个重要特征。在g e p 中， c a n d i d af e r r e i r a 提出了一种随机产生和变化数值常量方法。该方法的基 本思想是：采用一种附加终点n ? 和用来表示随机常数的符号构成的附加 域n 。附加域在基因尾部的后面与基因的尾部长度相等。在生成初始种 群的时，随机常数被保存到一个数组中，仅在基因表达的过程中赋值。 通过特殊的变异、转座、重组等遗传算子可以用来保证随机常数的多样 性。 1 7 记： 如下为一个含有随机常数的染色体，其头部长度为5 ，d c 用黑体字标 ol23456 789 0l23 456 q7 + ? aa?aa6 3 0 2 5 8 该染色体对应的表达式树如图3 2 所示。 图3 2 含随机常数的表达式树 对表达式中的”? ”用d c 中的符号按从左到右，从上到下的顺序进行替 换，得到如图3 3 所示的表达式树。 图3 3 添加附加域的表达式树 这些符号对应的值被保存在一个数组中。其对应的规则为：数值所 代表的为其在数组中的顺序。a _ - o 8 5l ，1 2 6 8 ，o 9 6 3 ，2 3 15 ，1 0 3 5 ， o 9 6 1 ，2 135 ，o 8 7 9 ，1 2 6 4 ，2 0 0 2 ) 。于是，通过随机常数的处理得到 如图3 4 所示的表达式树。 图3 4 替换随机常数的表达式树 以上完整描述了g e p 中常数处理的全过程。 3 5 遗传算子 l 选择 在传统g e p 算法中，采用轮盘赌选择算子。轮盘赌选择是指从群体 中随机选择一些个体的方法，个体被选中的机率和它们的适应性分数成 比例，染色体的适应性分数愈高，其被选中的概率也愈大。这并不保证 适应性分数最高的成员一定能选入下一代，仅仅说明它有最大的被选中 概率。也就是说，个体的适应度越高，它被遗传给后代的可能性就越大。 如果采用赌盘轮选择算子，那么赌盘按照群体中染色体个数的值进行相 应次数的旋转，从而始终保持群体的大小不变。 2 变异 在g e p 中，变异可以发生在染色体中的任何基因位。但为了保证染 色体的结构组织的完整性，在基因的头部中，任何符号都可以变成函数 符或终止符。函数符可以被其它的任意函数符替换，无需考虑每个函数 符所需要的参数个数；函数符也可以被其它的终止符取代。但是，在基 因的尾部，终止符只能够变异威终止符。染色体执行变异操作时，没有 对变异的种类和数量进行限制。通过这种方法，染色体的结构组织得以 保持，由变异产生的新个体都是结构上正确的程序。 012 3456789 卜、0 123456 789 q 4 - a 一dbcbal “ q 4 - a adbcba 口变异位口变异位 ( a ) 变异前 ( b ) 变异后 图3 5 变异算子 1 9 3 转座 在g e p 中，有三种转座元素。( 1 ) i s 元素：起始位置上是函数符或 终止符的短片段转座到基因的头中除根节点以外的位置；( 2 ) r i s 元素： 起始位置上是函数的短片段转座到基因的根节点；( 3 ) 整个基因转座到染 色体的起始位置。 ( 1 ) i s 元素转座 考虑如下由2 个基因组成的染色体，基因头长为4 ： 0l 234 5 678 90l23456 7 q + a adbcb + a adbcb 假设基因2 中的序列“a ”为i s 元素，目标位置为基因l 的第2 个基 因位。那么从第1 位开始截断，块“a ”被复制到插入位置，从而得到： 012345 6 7 8 9 0l2 3 4 5 6 7 q ，a + 8dbcb + a adbcb 观察上述染色体可以发现，在基因1 的头部末端部分之后与i s 元素 长度相等的序列丢失了。进行替换操作后，新产生的个体仍然是结构正 确的程序。 ( 2 ) r i s 元素转座 所有的r i s 元素都是从一个函数符开始的。在基因的头部任选一点， 沿基因向后查找，直到发现一个函数符为止，该函数符成为r i s 元素的 起始位置。如果找不到函数符，则不作任何操作。 考虑如下由2 个基因组成的染色体，基因头长为4 ： 0l2345 6 7 8 90l2 345 67 q + a adbcb + a adbcb 假设基因2 中的序列“a ”为r i s 元素，将其替换基因l 的根部得到： 0l2 3 4 5 6 7 8 90l2 345 6 7