（计算机应用技术专业论文）基于模糊聚类与多生境排挤的小生境遗传算法研究.pdf

摘要 摘要 遗传算法中维持种群多样性多采用小生境技术。本文在分析传统求解多模态 函数优化问题的小生境算法的基础上，针对存在的不足，提出了两种改进的小生 境遗传算法：自适应模糊相似聚类小生境遗传算法和基于适应值共享的多生境排 挤遗传算法。本文的内容主要有以下几个方面： 1 简要介绍了遗传算法的起源、基本概念、研究概况和基本理论：模式定理、 积木块假设、隐并行性。 2 深入分析了传统求解多模态函数优化问题的两种小生境算法：排挤方法和 适应值共享方法，并指出在解决实际问题中存在的不足。 3 提出了自适应模糊聚类小生境遗传算法。在演化过程中，将峰半径作为决 策变量的一部分参与染色体的编码，在对问题进行优化的同时对个体的峰半径进 行自适应调整：在聚类过程中，通过对模糊相似度的调节来控制小生境的数目， 以避免找到无效的极值点。该算法将模糊相似聚类、峰半径自适应调整适应值共 享遗传算法有机地结合起来，可以有效地搜索多模函数空间的多个极值点，同时 可以通过调节模糊相似度f 的值来控制收敛到的小生境的数目，避免找到无效的 极值点，有利于多个峰的精确定位，在无需事先确定小生境数目和半径的情况下， 就能较准确地搜索到多峰函数的各个全局和局部最优解。 4 提出了基于适应值共享的多生境排挤遗传算法。按照共享的思想在对个体 的适应值进行共享调整的同时，将排挤选择和相似个体中适应度最差个体被替换 的策略分别应用于选择算子和群体的进化中。该算法结合了标准适应值共享遗传 算法与确定性排挤遗传算法在调整种群多样性方面的优点，因而其维持种群多样 性的稳定性、跳出局部最优解、收敛到全局最优解的能力有了较大的提高。 5 使用经典的测试函数对两种算法进行实验测试，数值实验表明，算法很好 地维持了种群多样性，对问题的依赖性较弱，对于各类多峰函数具有较强的搜索 能力。 图1 1 表8 参考文献6 7 关键词：遗传算法；多峰函数优化；多生境；模糊相似聚类；适应值共享 分类号：t p 3 0 1 6 摘要 a b s t r a c t n i c h et e c h n o l o g yi sw i d e l yu s e di ng e n e t i ca l g o r i t h mf o rm a i n t a i n i n gt h e p o p u l a t i o nd i v e r s i t y t w oi m p r o v e dn i c h eg e n e t i ca l g o r i t h m s ( n i c h eg e n e t i ca l g o r i t h m b a s e do nf u z z ys i m i l a r i t yc l u s t e r i n ga n ds e l f - a d a p t i v ec o n t r o l l i n go fp e a k sr a d i i ，a n d m u l t i n i c h ec r o w d i n gg e n e t i ca l g o r i t h mb a s e do nf i t n e s ss h a r i n g ) a l ep r o p o s e di nt h i s p a p e r , f o ro v e r c o m i n gt h el i m i t a t i o n so ft r a d i t i o n a lm u l t i p l eh u m ps e a r c h i n gn i c h e g e n e t i ca l g o r i t h m s s e v e r a la s p e c t sa r ed i s c u s s e di nt h i sp a p e r a sf o l l o w e d ： 1 g a so r i g i n s ，i t sb a s i cc o n c e p t i o n s ，g e n e r a lr e s e a r c hc i r c u m s t a n c e sa n ds o m e f o u n d a t i o nt h e o r i e so fg a ，s u c ha ss c h e m at h e o r e m ，b u i l d i n gb l o c kh y p o t h e s i s ，a n d i m p l i c i tp a r a l l e l i s ma r em a i n l yi n t r o d u c e d 2 c r o w d i n gm o d a la n df i t n e s ss h a r i n gm o d a l ，t r a d i t i o n a l l yu s e di nm u l t ih u m p s e a r c h i n ga r ea n a l y z e dt h o r o u g h l y , a n dt h e i rl i m i t a t i o n sa r ep r o p o s e d 3 n i c h eg e n e t i ca l g o r i t h mb a s e do nf u z z ys i m i l a r i t yc l u s t e r i n ga n ds e l f - a d a p t i v e c o n t r o l l i n go fp e a k sr a d i ii sp r o p o s e d t h eb a s i ci d e ao ft h em e t h o di st h a t ，i nt h e p r o c e s so fg e n e t i ce v o l v e m e n t ，i tt a k e st h er a d i io fp e a k sa s ap a r to fo p t i m i z a t i o n v a r i a b l e s ，t h er a d i io fp e a k sa r ec o d e d ，p u ti nt h ec h r o m o s o m e sa n do p t i m i z e dw i t ht h e v a r i a b l e so ft h ep r o b l e mb yf i t n e s ss h a r i n gg e n e t i ca l g o r i t h mw i t h o u tap r i o r k n o w l e d g eo ft h ea b o v ep a r a m e t e r s ，i nt h ep r o c e s so fc l u s t e r i n g , i tc o n t r o l st h en u m b e r o fc o n v e r g e dn i c h e st h r o u g ha d j u s t i n gt h ef u z z ys i m i l a r i t yd e g r e e ，a v o i d i n gf i n d i n gt h e i n v a l i de x t r e m ep o i n t sa sw e l l t h ea l g o r i t h mt a k e sn on e e dt ok n o wt h ec o n c r e t e n u m b e ro fn i c h e sa n dt h ev a l u eo ft h en i c h er a d i u mi na d v a n c e ，h a v i n gag o o d s e a r c h i n ga b i l i t yo nv a r i o u sm u l t i p l eh u m p f u n c t i o n s 4 m u l t i n i c h ec r o w d i n gg e n e t i ca l g o r i t h mb a s e do nf i t n e s ss h a r i n gi sp r o p o s e d d u r i n gt h es e l e c t i o ns t e p ，t h ea l g o r i t h mu s e st h ec r o w d i n gs e l e c t i o np o l i c y , a n dd u r i n g t h er e p l a c i n gs t e p ，i tu s e sar e p l a c e m e n tp o l i c yc a l l e dw o r s ta m o n gm o s ts i m i l a r , a f t e r f i t n e s ss h a r i n g f o rc o m b i n e st h ei d e ao fc r o w d i n ga n ds h a r i n g ，t h ea l g o r i t h mh a sa g o o da b i l i t yi ne s c a p i n gl o c a lo p t i m a ，m a i n t a i n i n gs t a b l es u b p o p u l a t i o n si nd i f f e r e n t n i c h e s ，a n dc o n v e r g i n gt ot h eg l o b a lo p t i m a 5 s e v e r a lc l a s s i c a lt e s tf u n c t i o n sa r ec a r r i e do nt h et w oi m p r o v e da l g o r i t h m s t h e o r e t i c a la n a l y s i sa n dn u m e r i c a le x p e r i m e n t si n d i c a t et h a tt h ea l g o r i t h m sk e e pa g o o dd i v e r s i t yt h r o u g h o u tt h es e a r c h ，h a v eag o o ds e a r c h i n ga b i l i t yi nv a r i o u sm u l t i p l e i i 摘要 h u m pf u n c t i o n s ，a n da r el e s sd e p e n d e n t a sw a l l f i g u r e11 t a b l e8r e f e r e n c e6 7 k e y w o r d s ：g e n e t i ca l g o r i t h m ，m u l t i p l eh u m pf u n c t i o no p t i m i z a t i o n , m u l t i n i c h e ，f u z z y s i m i l a r i t yc l u s t e r i n g ，f i t n e s ss h a r i n g c b c n ：t p 3 0 1 6 i i i 插图或附表清单 插图或附表清单 相关图： 图1 ：遗传算法的基本流程图 图2 ：遗传算法空间转换图 图3 ：5 0 次优化中石( x ) 一次随机实验测试结果 图4 ：5 0 次优化中应( x ) 一次随机实验测试结果 图5 ：最相似个体中适应度最差个体被替换策略示意图 图6 ：石( x ) 运行1 0 0 代峰搜索结果 图7 ：石( x ) 个体在各峰上的分布 图8 ：石( x ) 各峰的平均适应度 图9 ：f 2 ( x ) 运行1 0 0 代峰搜索结果 图1 0 ：疋( x ) 个体在各峰上的分布 图1 1 ：厶( x ) 各峰的平均适应度 相关表： 表1 ：自然遗传学和遗传算法中基本术语对照表 表2 ：5 0 次优化中石( z ) 峰个数测试结果 表3 ：石( x ) 一次随机抽样测试结果与理想值的比较 表4 ：5 0 次优化中以( z ) 峰个数测试结果 表5 ：f 2 ( x ) 一次随机抽样测试结果与理想值的比较 表6 ：s h u b c r t 函数测试结果( 前18 个全局最优值) 表7 ：多生境排挤遗传算法中的参数设置 表8 ：s h e k e l sf o x h o l e s 函数运行2 0 0 代后测试结果 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 以外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得塞徽堡王太堂或其他教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示谢意。 学位论文作者签名：竖丝丝 日期：- 竺4 年j 月j 日 学位论文版权使用授权书 本学位论文作者完全了解塞邀堡王盘堂有保留、使用学位论 文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位 属于塞邀堡王太堂。学校有权保留并向国家有关部门或机构送交 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权安徽 理工大学可以将学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：译艳抱签字日期：2 钾1 年月7 日 导师签名： 。露匀 签字日期：砷年月7 日 引言 引言 在信息技术与基因工程技术突飞猛进的今天，人们越来越多地向自身进化这 一浩瀚却又微妙的过程学习，来增强求解问题的能力。在函数优化方面，生活中 许多问题用传统的数学计算方法来求精确解是不可能的，而遗传算法g a ( g e n e t i c a l g o r i t h m ) 是由美国m i c h i g a n 大学的j o h nh o l l a n d 教授与其同事、学生们在2 0 世 纪6 0 年代末期提出的一种优化搜索、群体进化算法。自然界中各种生物为了生存 和发展必须要进行一系列的竞争，包括同一种群内部的竞争、不同种群之间的竞 争以及物种与自然环境之间的协调与适应。只有那些适应环境能力强的物种具有 较强的生存能力，它们繁衍后代的机会较大；而对环境适应能力差的物种则在竞 争中处于劣势，产生后代的机会较小，甚至可能会逐步灭绝。达尔文( c d a r w i n ) 把这一现象归纳为“优胜劣汰，适者生存”。生物界的适者生存现象给人们带来了 启示：我们能否模拟生物的适应与进化机理来研究人造系统，以提高人工系统的 自适应能力和学习能力? 不同领域的学者为此进行了大量的研究，提出了许多具 有价值的理论与方法，遗传算法就是其中的一个突出代表。目前，遗传算法已经 在自适应系统、函数优化、机器学习、自动控制等领域得到了应用，并取得了令 人瞩目的成就。尤其是人工生命( a r t i f i c i a ll i f e ) 学科的兴起对g a 的发展起了 重要的推动作用，遗传算法已经成为人工生命、人工智能等领域的研究热点。 而在函数优化问题中，遗传算法是利用某种编码技术作用于称为染色体的二 进制串，并通过个体评价、选择、交叉变异等过程来改变染色体上的基因，逐步 得到满足优化条件的好的染色体，即最优解。在整个优化过程中遗传算法不依赖 于求解问题，只对算法所产生的每个染色体进行评价，基于适应值来选择下一代， 使适应性好的染色体比适应性差的染色体有更多的繁殖机会。函数优化是遗传算 法的重要应用领域，也是对遗传算法进行性能评价的常用算例。 对于具有多模态性质的连续函数优化问题和组合优化问题，传统的基于导数 或其它启发式信息的搜索算法( 如梯度爬山法，模拟退火方法等) ，均存在着如何 避免陷入局部极值点而发现全局最优解的问题，而遗传算法的特点在于采用群体 搜索和遗传算子策略( 空间分布式信息继承与重组) ，其效果显著好于传统方法的单 点搜索和启发引导方式( 邻域局部性信息继承与逼近) ，另外遗传算法还具有良好的 信息处理的隐并行性、鲁棒性等优良特性，因此成为求解多模函数优化问题的有 力工具，近年来已成为一个持续研究的领域。传统求解多模态函数优化问题的小 生境算法，主要分为两类：排挤方法和适应值共享方法。但基于排挤的方法仍然 引言 存在着已搜索到的最优解丢失，而且c f 参数的选择与具体问题有关，很难事先确 定合适的取值等问题，而基于适应值共享的方法也存在着需要事先指定小生境的 数目及半径等问题，因此为进一步提高算法的性能，国内外学者在此基础上，提 出了多种各样的改进小生境算法，基于排挤方法的有：确定性排挤方法、限制锦 标选择算法、多生境排挤方法：基于共享的方法有：标准适应值共享方法、清除 算法、适应值共享k 均值聚类算法、动态小生境共享算法、自适应小生境算法等。 另外还有将两种基本思想相结合，提出了多种共享排挤方法；将遗传算法与传统 的梯度算法、各种启发式算法相结合，提出了各种混合遗传算法等。 这些算法在一定的程度上改善了多模函数的优化搜索性能，但综合考虑问题 独立性、维持群体的多样性、全局收敛性、收敛的速度、应用的广泛性等多种因 素，目前所提出的以上诸多算法在具体问题的求解中，均存有一定的缺陷，为此 在对各种搜索算法进行了大量深入研究的基础上，本文旨在改进算法的性能，提 出更加合理、优秀的算法，并对改进的算法从维持种群多样性的稳定性、跳出局 部最优解、收敛到全局最优解的能力、对实际问题的依赖性等性能方面进行理论 分析和数值实验测试，这也是本文的研究重点。 1 绪论 1 绪论 本章全面评述了优化和搜索技术研究中所使用的方法及存在的问题，总结了 遗传算法的特点及研究应用状况，最后阐述了本文的主要研究内容。 1 1 优化和搜索方法评述【l 4 】 最优化问题一般可描述为下述数学规划模型： m a x ( m i n ) 厂( x ) ( 1 1 ) s ，x r( 1 2 ) rc _ u( 1 3 ) 其中，x = 【，t ，t 】7 为决策变量，f ( x ) 为目标函数，式( 1 2 ) 、( 1 3 ) 为 约束条件。满足约束条件的解x 称为可行解，u 是搜索空间，尺是可行解集合， 是u 的一个子集。通常情况下，目标函数和约束条件种类繁多，有的是线性的， 有的是非线性的；有的是连续的，有的是离散的；有的是单峰的，有的是多峰的， 随着研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出最优解 既不可能，也不现实，因而得到近似最优解或满意解便成为研究人员的主要着眼 点之一。 目前关于优化理论的著作中求最优解或近似解的方法主要有三类：基于微分 的方法、枚举法和随机方法。 1 基于微分的方法 基于微分的优化方法，即解析方法，主要用于求解无约束极值问题，可分为 直接法和间接法两类。前者是通过求解目标函数的梯度并令其等于零，从而得到 一个非线性方程组，求解后得到极值点，如最小二乘法。后者则利用目标函数的 梯度信息，根据已经求得的目标函数值，确定前进的方向与局部梯度有关的方 向，从初始点进行迭代搜索，逐步改善目标函数值，从而趋于极值点，如求解无 约束极值问题的最速下降法( 梯度法) 、优化前向人工神经网络的b p 算法等。由 于其沿着当前最陡的允许方法攀登，故称为爬山法。求最大问题称为上山法，求 最小问题称为下山法。尽管此类方法已被进一步改进和拓展，但无论采取什么策 略上山或下山，其缺陷都十分明显。 首先，由于上述方法所求得的是当前邻域内最好点，即局部最优解，致使其 应用范围受到限制。对于多峰函数的最大优化问题，若从较低峰值处的邻域内开 始寻优，利用任何一种上山法，都无法得到正确的解，可见初始搜索位置的选择 1 绪论 对最终结果起着决定性的作用。因而，在使用这类方法时，人们不得不反复多次 随机地选取初始搜索点，或采用其它方法，才可避免收敛于局部极值处。 其次，基于微分的方法取决于导数信息，这是该方法的另一不足之处。许多 实际的参数空间很少考虑是否可导及是否光滑，而且事实上寻优问题常常是不连 续的，甚至是多峰的，有时为噪声优化空间，从而梯度的计算变得十分困难。 凡是依赖于连续、可导条件的方法，只适用于非常有限的范围。正因为如此， 二次规划具有理想约束条件且导数总是存在的特征，使得优化理论学家们对其研 究不感兴趣。也正因为上述两个主要缺陷，使得基于微分的方法运用范围较窄， 而不能适用于所有问题或大部分问题，缺乏通用性，亦即缺乏足够的鲁棒性。 2 枚举法 又称穷举法，其思想相当直观：在一定搜索空间，或一离散的无穷搜索空间 上，通常为可行域，从计算任一点的目标函数值大小开始，一次仅计算一个点， 采取某种策略移动至下一点，逐步寻优。如线性规划( l i n e a rp r o g r a m m i n g ) 中 的单纯形法，其求解过程是从可行域的一个顶点到另一顶点逐步计算，比较而得； 非线性规划的单纯形法，利用( n 维变量其单纯形有n + 1 个凸点) 凸多边体各顶点 的函数值的大小比较，求得最差点的反对称点，再重新构造新的单纯形，如此反 复迭代，逐渐靠近最佳点，直到精度满足要求或达到最大迭代次数为止。 文献 5 对线性规划问题的单纯形法及算法的复杂性进行了研究，单纯形法是 一类非多项式算法，对于求解大规模问题是很困难的。椭球法和内点法能被证明 是多项式算法，但对于一般规模的问题，其计算量都比较大。枚举法的另一不足 是寻优效率低，由于其寻优过程过于繁琐，常受到计算机容量的限制，不断反复 地迭代运算，只适合于求解单变量或变量数较少的问题。动态规划( d y n a m i c p r o g r a m m i n g ，简称d p ) 睁7 1 ，自1 9 5 7 年r b e l l m a n 创立以来，一直备受水电及各 界研究人员的重视，在水库优化调度的研究中取得了一批有影响的成果，但实际 计算中都遇到了“维数灾问题，状态空间的离散结点总数随问题规模( 模型维 数) 的增加而呈指数次增加，因而所需要的计算机内存和c p u 时间都呈指数次增 加，有时甚至目前最先进的计算工具都不堪重负，即使对中等规模复杂的问题也 常常束手无策。为此研究者们在使用d p 法之前，必须先对数学描述或模型结构及 其参数加以处理，再使用改进的d p 法。总之，枚举法的低效寻优，以及对处理变 量数目的限制等，致使其鲁棒性能大大减弱。 3 随机方法【4 8 t 9 】 由于微分法和枚举法的不足，随机搜索算法正被日益重视，但随机方法在寻 1 绪论 优效率上仍然较低。g o l d b e r g 等人的研究结果表明，简单的随机搜索方法并不能 取得比枚举法更好的效果。 模拟退火( s i m u l a t e da n n e a l i n g ，简称s a ) 算法是利用随机过程理论帮助取 得最小能量状态的一种寻优方法。最早的思想由m e t r o p o l i s 于1 9 5 3 年提出， k i r k p a t r i c k 于1 9 8 3 年成功地应用在组合优化问题中，它能以一定的概率接受邻域 中能量较高的新点，理论上来说是一个全局最优算法。算法的核心在于模仿热力 学中液体的冻结与结晶或金属溶液的冷却或退火过程。在高温状态下，液体的分 子是可以自由移动的，如果液体徐徐冷却，液体中的分子就会逐渐丧失其由于温 度而引起的流动能力，这时原子就会自己排列起来而形成一种纯晶体，它们依次 地朝各个方向排列成几十倍于单个原子大小的距离，这个纯晶体状态就是该系统 的最小能量状态。与之不同的是，如果待冷却的金属溶液是被快速冷却或泼水使 其冷却，则它不能达到纯晶体状态，而是变成一种多晶体或非晶体状态，系统处 在这种状态时仍具有较高的能量。模拟退火算法用于求解最优化问题时，分别将 问题的解和目标函数值当作物理系统的状态和能量，从而物理系统内粒子的摄动 等价于问题解的试探，首先在一个高温状态下有效的“熔化 解空间，然后慢慢 地降低温度直到系统结晶到一个稳定解，这里所说的温度就是算法的控制参数。 在给定领域结构后，寻优过程仍然很慢。而且，实际应用中的s a 算法是一个启发 式算法，有诸多参数需要调整，如起始温度、温度下降的方案、温度固定时的迭 代长度及终止规则等，这些都需要人为地调整，于是人为的因素，如对问题的了 解、参数和规划的搭配等，将会造成计算结果的差异。解决这个矛盾的方法主要 是通过大量的数值模拟计算，从中选择较好的参数搭配，使得s a 算法的通用性大 打折扣。 遗传算法是一种基于群体选择的随机搜索算法，它借鉴了自然界生物进化中 适者生存的竞争机制。在求解优化问题时，遗传算法将优化问题当作一个生存环 境，问题的一个解当作生存环境中的一个个体，以目标函数值或其变化形式来评 价个体对环境的适应能力，模拟由一定数量个体所组成的群体的进化过程，优胜 劣汰，最终获得最好的个体，即问题的最优解。它呈现出的是一种通用算法框架， 该框架不依赖于问题的种类，因而具有较强的鲁棒性，特别是对于一些大型复杂 非线性系统，表现出比其他传统优化方法更加独特和优越的性能。其隐含并行性 和全局搜索特性保证算法能够在较大区域中做快速搜索，有较大把握寻找到全局 最优解。 l 绪论 1 2 遗传算法的特点与研究进展 1 2 1 遗传算法的特点 1 0 1 3 生物是通过两个基本过程( 自然选择和有性生殖) 不断进化的，通过遗传、 突然变异、自然淘汰等规律进化，以适应环境的变化，正因为如此，人们开始把 进化这种奇异的本领看成一种值得仿效的东西。与传统优化算法相比，遗传算法 具有以下主要特点： 1 遗传算法处理的对象是参数集的代码，而不是参数本身。因此遗传算法的 搜索过程既不受函数连续性的约束，也不受函数可导的约束，所以遗传算法是一 种弱方法，与具体问题领域无关。 2 遗传算法的搜索过程是从一组初始点开始搜索的，而不是从一个初始点开 始搜索。这种机制使得遗传算法易于并行化且搜索不易限于局部极值点，因此遗 传算法具有较好的全局搜索能力。 3 遗传算法的搜索过程仅使用适应度函数进行启发，而不需要导数和其它辅 助信息，不受可导、可微等传统方法思路的限制，过程简单，易于实施，这使得 遗传算法成为普适性的优化方法。 4 遗传算法的搜索过程采用的是概率转换准则，而不是确定性准则。这种准 则仅仅作为一种工具来引导其搜索过程朝着搜索空间的更优的解区域移动。看起 来它似乎是一直盲目搜索，但实际上它有明确的搜索方向u 川。 以上这些特点使得遗传算法使用简单，鲁棒性强，易于并行化，从而应用范 围更加广泛。 1 2 2 遗传算法的研究进展 1 6 。1 8 i 1 历史回顾 遗传算法起源于对生物系统所进行的计算机模拟研究。早在本世纪4 0 年代， 一些生物学家( 例如f r a s e r 等) 开始研究如何利用计算机进行生物模拟的技术， 目的在于借助计算机来研究自然现象，从生物学的角度进行了生物的进化过程模 拟、遗传过程模拟等研究工作，他们的某些模拟方法和模拟结果却给后来的遗传 算法研究带来了启迪。f r a s e r ( 1 9 6 2 年) 在研究参数对表现型( p h e n o t y p e ) 的影 响时，对p h e n o t y p e = a + q 口a + c d 中的参数口、孙c 采用二进制进行编码，三 个参数各以5 位码表示，形成一个1 5 位的二进制码串，他按照p h e n o t y p e 值的大 小进行码串的选择，模拟进化，并计算了各种码串在后续代中所占的比例。这种 l 绪论 做法与现在用于函数优化的遗传算法有很大的相似性。受生物学家模拟方法和模 拟结果的启发，正在研究自适应系统的一些学者如h o l l a n d ( 1 9 6 2 年) 、b l e d s o e ( 1 9 6 1 年) 等人将模拟遗传算子引入了自己的研究领域。h o l l a n d 1 9 1 认为，适应性的研究包 括适应系统和系统所处环境两方面，一般地，它是研究系统的生成过程，以使系 统有效地适应环境。借鉴生物学概念，h o l l a n d 采用了类似自然选择的方式来设计 计算机程序。在程序设计中，h o l l a n d 以监督程序模拟自然选择，不断剔除效果不 佳的程序，让那些求解问题好的程序越来越多占据优势，从而使系统最终能适应 任意环境，除了认识到选择的必要性外，他还十分肯定地认为基于群体的搜索方 法要优于单个结构到单个结构的方法。1 9 6 5 年h o l l a n d 又阐述了杂交算子的重要 作用，在随后的十年中，他致力于探讨基因适应系统理论的数学基础，提出了以 二进制位串为基础的基因模式理论( t h e o r yo f s c h e m a t a , 1 9 6 8 年) ，1 9 7 5 年出版了 第一本系统论述遗传算法和人工自适应系统的专著a d a p t i v ei nn a t u r a la n d a r t i f i c i a ls y s t e m s ) ) ，为遗传算法的研究奠定了坚实的理论基础。 1 9 6 7 年，h o l l a n d 的学生b a 西e y 在其博士论文中首次提出了“遗传算法 一 词，并发表了遗传算法应用方面的第一篇应用论文。他发展了复制、交叉、变异、 显性、倒位等遗传算子，在个体编码上使用了双倍体的编码方法，这些都与现代 遗传算法中所使用的算子和方法相类似。他还敏锐地意识到了在算法执行的不同 阶段可以使用不同的选择率，这将有利于防止算法的“早熟 现象，从而创立了 自适应遗传算法的概念。 1 9 7 5 年，d ej o n g t 2 0 】在其博士论文中结合模式定理进行了大量的纯数值函数优 化设计实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结 论。例如，对于规模在5 0 - - - 1 0 0 的群体，经过1 0 2 0 代的进化，遗传算法都能以很 高的概率找到最优或近似最优解。他还推荐了在大多数优化问题中都较适用的遗 传算法参数，并建立了著名的d ej o n g 五函数测试平台，定义了评价遗传算法性能 的在线和离线指标，其研究方式己成为遗传算法研究和开发中的典范。 19 8 9 年，g o l d b e r g t 2 l 】出版了专著( ( g e n e t i ca l g o r i t h m si ns e a r c h ，o p t i m i z a t i o n a n dm a c h i n el e a m i n g ，该书总结了遗传算法的主要研究成果，全面而完整地论述 了遗传算法的基本原理及其应用，奠定了现代遗传算法的科学基础，从而为众多 研究和发展遗传算法的学者所瞩目。1 9 9 1 年，d a v i s 编辑出版了 h a n d b o o ko f g e n e t i c a l g o r i t h m s ) ) 一书，其中包括了遗传算法在科学计算、工程技术和社会经济 中的大量应用实例，对该领域的设计和应用人员有很大的帮助，为推广和普及遗 传算法的应用起到了重要的指导作用。1 9 9 2 年。k o z a t 2 2 1 将遗传算法应用于计算机 1 绪论 程序的优化设计及自动生成，提出了遗传编码的概念。他将段l i s p 语言程序作 为个体的基因型，把问题的解编码为一颗树，基于遗传和进化的概念，对由树组 成的群体进行遗传运算，最终自动生成性能较好的计算机程序。k o z a 还成功地把 他提出的遗传编程方法应用于人工智能、机器学习、符号处理等方面。 2 研究进展 目前，遗传算法( g a ) 的研究工作主要是在h o l l a n d 的基因模式理论基础上 进行的，主要内容包括： 1 ) 模式理论的进一步发展和完善。 h o l l a n d 的模式理论奠定了g a 的数学基础，根据隐含并行性得出每一代处理 有效模式的下限值是拧3 佃，“2 ) ，其中栉是群体大小，是串长，口是小整数，一些 研究把结果简化为刀。b c r t o n i 和d o r i g o 推广了此研究，获得 = 2 ，即p 为任意 值时处理多少有效模式的表达式。每一代遗传有多少新模式产生也是说明了g a 效率的重要性，恽为民、席裕庚获得了每次至少产生0 ( 2 “) 数量级的新模式结果。 模式定理中模式适合度难以计算和分析，b e t h k e 运用w a l s h 函数和模式转换 发展了有效的分析工具，h o l l a n d 扩展了这种计算。f r a n t z 在文献 2 3 】中率先察觉 了一种使用g a 从全局最优解发散出去的问题，被称为g a 欺骗问题( g a d e c e p t i v e p r o b l e m ) 。文献 2 4 ( g o l d b e r g ，1 9 8 7 年) 首先运用w a l s h 模式转换法设计了最小g a 一 欺骗问题，并进行了详细的分析和更为深入的讨论。各种研究结果表明，g a 欺骗 问题一般包含有孤立的最优点，即在这个最优点周围是一些较差的点，从而使得 g a 较难通过基因之间的相互拼接而达到此最优点的模式。目前尚无解决此类问题 较好的方法或策略，所幸的是，实际遇到的各种应用问题中，很少有这种奇怪的 性质。 2 ) 个体表达( 编码) 方式的多样化。 h o l l a n d 模式定理建议采用二进制编码，得到许多学者的支持。双倍体表达是 高等生物染色体的重要特征，有长期记忆性，早期g a 研究者较多考虑双倍体表 达。g o l d b e r g 和s m i t h 用动态k n a p s a c k 问题对单倍体和双倍体g a 进行了比较研 究，文献 2 5 对双倍体g a 作了详细的分析，结果表明，对于静态优化问题，与使 用单倍体的g a 相比，使用双倍体的g a 并不能改善多少求解性能；但对于动态系 统的优化问题，使用单倍体的g a 很难达到优化要求，因为它跟踪不了动态环境 的变化过程，此时，使用双倍体的g a 却能表现出较好的应用效果。 文献 2 6 1 论述了不同的编码方式对g a 的收敛性和收敛速度均有重大影响，而 且人们在应用实践中已经发现二进制编码方式的g a 存在h a m m i n g 悬崖，缺乏微 8 1 绪论 调功能，对于复杂或高维问题由于个体串过长使问题无法计算以及引起“早熟 等问题。为此，研究学者们采用不同的编码方式进一步改进g a 的性能，如为克 服h a m m i n g 悬崖而使用g r a y 编码，为使算法具有微调功能采用动态编码【2 7 1 ，为 使算法能用于解决复杂或高维问题采用实数编码等。q i 和p a l m i c r i f 2 8 2 9 1 对浮点编 码的g a 进行了严密的数学分析，用m a r k o v 链作了全局收敛性分析，但其结果是 基于群体数无穷大的假设。v o s e 、b a t t l e 和l i e p i n s 等扩展了h o l l a n d 的模式概念， 揭示了不同编码之间的同构性。由于编码是g a 应用中的首要问题，因此建立完 善的理论指导是必要的。二进制编码的进化层次是基因，而浮点数编码的进化层 次是个体，用前者理论来指导后者是不合适的。 3 1g a 控制参数的优化问题：群体规模、杂交概率和变异概率等控制参数的 选择问题。 g a 控制参数的选择直接影响着算法的运行效果口0 】，各控制参数是相互制约 的。增大杂交概率有利于基因块重组，但同时增大了破坏优良基因串的可能；增 大突变概率有利于群体信息的多样性，但相应增加了计算机的内存费用，同时影 响算法的收敛速度。控制参数的选择目前尚无完善的理论指导，人们通过大量的 试验数据推荐了两组控制参数：群体规模1 0 0 、杂交概率0 6 、变异概率0 0 0 1 ( g r e f e n s t e t t e ，1 9 8 6 年) ；群体规模3 0 、杂交概率0 9 、变异概率0 0 1 ( d ej o n g ，1 9 9 0 年) 。实际应用中，人们发现随着算法进化过程使当地调整控制参数有利于算法的 收敛。文献 3 1 ( 1 9 9 3 年) 的研究中，在进化初期采用小的变异概率，而后期加大 了变异概率。文献 1 8 ( 1 9 9 5 年) 在上述基础上，提出了多环节变化措施。文献 3 2 】 根据群体平均适应度的变化调整杂交和变异概率，取得了较好的效果。从这些研 究成果看，算法的控制参数随进化过程适当调整有利于改善算法的性能，但如何 调整仍处于试验阶段，尚无统一的理论指导。 4 ) 从理论上探讨g a 的全局收敛性问题。 近几年，在遗传算法全局收敛性的分析方面取得了突破，运用的数学工具是 m a r k o v 链：把每一代群体看作一种状态，将整个进化过程视为一个随机过程来加 以考察，利用m a r k o v 链对进化过程进行理论分析。g o l d b e r g 和s e g r e s t 首先使用 了m a r k o v 链分析g a ，r u d o l p h 用齐次有限m a r k o v 链证明了带有复制、交叉、突 变操作的标准g a 收敛不到全局最优解，不适合于静态函数优化问题，并建议改 变复制策略以达到全局收敛。e i l e e n 等用m a r k o v 链证明，在进化过程中，随着进 化代数趋向无穷，使用保留最佳个体策略的g a 总能够以概率1 搜索到全局最优 解，即收敛性定理。这一定理表明g a 能够对搜索空间进行持续的搜索，适合于 1 绪论 求解全局优化问题。 但是，作为一种基于概率搜索的算法，我们更关心在有限的进化过程中，算 法有多大把握获得问题的最优解，或者说是算法得到的解为问题最优解的置信度 有多大? 这一问题的理论研究有待进一步深入。 5 ) g a 的“早熟 问题：如何避免群体中的个体过早在一个非最优点上达到 完全相同或接近完全相同。 理论上，g a 随着演化代数趋向无穷，将以概率l 找到问题的全局最优解。但 实际应用中，由于群体规模不可能太大，在选择算子的作用下，群体中的基因多 样性将迅速衰减，从而算法在进化若干代后，群体中的个体便在一个非最优点上 达到完全相同或接近完全相同。特别是当初始群体中某一个体的适应值比整个群 体平均适应值大很多时，问题更为突出，这就是g a 的“早熟 问题。关于如何 避免g a “早熟 ，人们研究了许多方法，中心思想是如何保持群体基因的多样性。 g o l d b e r g ( 1 9 8 7 年) 3 3 1 应用h o l l a n d 的共享函数思想控制个体间的距离，避免群 体过早趋向一致。d ej o n g 定义了“代间隙 以控制个体的分布。文献 3 2 从初始 群体构成出发，提出了正交选种的方法，在可行域中按正交表寻优，把结果从优 到劣排列，取前若干个组成初始群体，以增加群体的代表性。文献 3 4 】在选择算子 设计中，为避免高适应值的个体被频繁选中，没有采用通常的赌盘技术，其做法 是：将个体适应值从大到小排序，首先选择具有奇数下标的个体，然后按一非线 性变换函数随机产生配对个体的下标。这种选择方法既偏向选择好的个体，又不 致破坏群体的多样性。 6 ) 在传统g a 基础上改进遗传算子或引入新的遗传算子，以便改善算法的执 行结果。 传统g a 采用基于赌盘选择的复制算子、一点杂交算子。复制算子的改进在 上面已作介绍。杂交算子的作用是利用群体中的基因信息构成更好的个体。文献 3 5 】 采用了“远亲杂交 方式，其出发点是根据两个个体相差的程度来确定个体配对 的概率，以提高算子的执行效率，尽量保证杂交后产生两个新的好个体。 s y s w e r d a ( 1 9 8 9 年) p 叫提出了一致杂交( u n i f o r mc r o s s o v e r ) 算子，其基本做法是： 选择两个个体置、墨，以随机产生的一个码串a 作参考，a 的某一位码为1 ，则墨 和墨相应位变换。实际上，一致杂交算子是多点杂交的一种实现形式，s y s w e r d a 证明了一致杂交算子的收敛速度快于一点杂交或两点杂交算子。m i l l e r 等( 1 9 9 3 年) 3 7 1 在研究g a 解决多故障诊断问题( m u l t if r u s t r a t i o nd i a g n o s i s ) 时，提出了 具有工程调节( e n g i n e e r i n gc o n d i t i o n i n g ) 算子的遗传算法( e c g a ) ，e c 算子的 1 0 1 绪论 思想类似于爬山法，在每一代中，对每一个个体进行测试，将个体中的一位或两 位取反，如果适应值优于原个体，则新个体取代原个体。e c 算子无疑加强了g a 对局部极值点的搜索能力，但相应计算工作量也增加了两倍。文献 2 1 1 0 0g o l d b e r g 总结了一种高级遗传算子显性机制( d o m i n a n c em e c h a n i s m ) ，算子是基于生物基 因有显性和隐性这一事实的。算子操作时，个体基因码每位取值有3 个，而不是 通常的二进制形式。此外，还有一些针对特殊优化问题的操作算子如倒位 ( i n v e r s i o n ) 、迁移( i m m i g r a t i o n ) 等。 7 ) g a 与其它优化方法向结合，以提高收敛速度，增强算法的收敛性，避免 “早熟。 由于g a 的结构是开放式的，与问题无关，所以容易和其它算法相结合。“n p 叫 等把g a 和s a 进行综合，构成模拟遗传算法，在解决几种n p c 问题中显示良好 的性能，时间复杂度为o ( n 2 ) 。1 9 9 3 年y i p 和p a o 提出了一种带区域指引的进化模 拟退火算法，他们将进化策略引入区域指引，经过选