（电工理论与新技术专业论文）遗传算法参数自适应控制及收敛性研究.pdf

a bs t r a c t t h ep e r f o r m a n c eo fg e n e t i ca l g o r i t h m ( g a ) i so b v i o u s l ye n s l a v e d t ot h ec r o s s o v e rp r o b a b i l i t yp ca n dm u t a t i o np r o b a b i l i t yp 朋f o rt h ev a l u e s o fp ca n dp 所a r ei n v a r i a b l e ，t h e r ea r ep r o b l e m sa st h el o wc o n v e r g e n c e r a t ea n dp r e m a t u r ep h e n o m e n o ni ns i m p l eg e n e t i ca l g o r i t h m t h o u g h a d a p t i v eg e n e t i ca l g o r i t h m ( a g a ) h a s b e e n p r o v e nt ob ea b l et oa d j u s t t h ec o n t r o lp a r a m e t e r sa c c o r d i n gt ot h ef i t n e s so ft h eo v e r a l lp o p u l a t i o n ，i t i sn o ts u i t a b l ef o rd i f f e r e n tp r o b l e m sf o rt h er u l e st oa d ju s t p ca n dp ，行m u s t b ev a r i e dw i t ho p t i m i z a t i o nq u e s t i o n ss oa st of i n dt h eo p t i m a ls o l u t i o n f a s t e ra n dm o r ep r e c i s e l y i ti so fg r e a ti m p o r t a n c et oa d j u s tt h e p a r a m e t e r sa d a p t i v e l y c o n v e r g e n c et h e o r yi sac o r et h e o r e t i c a li s s u eo n g e n e t i ca l g o r i t h m s t h es y s t e m a t i s ma n du n i v e r s a l i s mo ft h et h e o r i e sa r e n o te n o u g h s o ，s t u d y i n gt h ec o n v e r g e n c et h e o r yo fg e n e t i ca l g o r i t h m si s t h ei n e v i t a b l er e q u i r e m e n tf o rt h et h e o r ya n da p p l i c a t i o no fg a t h e r e f o r e ，p a r a m e t e ra d a p t i v ec o n t r o l l i n ga n dc o n v e r g e n c et h e o r y f o rg e n e t i ca l g o r i t h m sa r es t u d i e di nt h i sp a p e r ak i n do fn e s t e df u z z y a d a p t i v eg e n e t i ca l g o r i t h m ( n f a g a ) w h i c hi s s u i t a b l ef o rd i f f e r e n t o p t i m i z a t i o np r o b l e m s i sr e a l i z e d ，t h es i m u l a t i o np l a t f o r mo ft h en e w a l g o r i t h mi si m p l e m e n t e d ，a n dt h es i m u l a t i o ne x p e r i m e n t si nf u n c t i o n o p t i m i z a t i o np r o b l e m sw i t hs e v e r a lo t h e rg e n e t i ca l g o r i t h m sa r ec a r r i e d o u t f o rt h ec o n v e r g e n c et h e o r y , t h ec o n v e r g e n c ea n dc o n v e r g e n c er a t eo f e l i t i s t g e n e t i ca l g o r i t h m ( e g a )b a s e do nm a r t i n g a l ea p p r o a c hi s s t u d i e d t h ed e t a i l e dc o n t e n t sa n di n n o v a t i v ew o r ko ft h i sp a p e ra r ea s f o l l o w s ： 1 a c c o r d i n gt o t h ed e f e c t sf o rr e g u l a t i o nl a wo ff u z z ya d a p t i v e g e n e t i ca l g o r i t h mb a s e do ne x p e r t i s e( e f a g a ) ，t h es e l f - l e a m i n g m e c h a n i s mt ou p d a t ea n do p t i m i z et h ek n o w l e d g eb a s i so ft h ef u z z y c o n t r o l l e ri ss t u d i e d o nt h eo n eh a n d ，t h ev a l u e so f p ca n dp ，打a r ea d j u s t e d a c c o r d i n gt ot h ee v o l u t i o n a lp r o c e s sb yu s i n gt h ef u z z yc o n t r o lm e t h o d ； o nt h eo t h e rh a n d ，t h ef u z z yr u le sa n dt h ep a r a m e t e r so ft h em e m b e r s h i p f u n c t i o n sa r eo p t i m i z e db ya n o t h e rg a t h u s ，ak i n do fn e s t e df u z z y a d a p t i v eg e n e t i ca l g o r i t h mw h i c hc o u l do v e r c o m et h ed e f e c t so ft h e e x i s t i n ga d a p t i v eg e n e t i c ea l g o r i t h m si sr e a l i z e d 2 t h es i m u l a t i o np l a t f o r mo fn f a g ab a s e do nm a t l a bg u ii s i m p l e m e n t e d t h ee f f i c i e n c yo fn f a g ai ss t u d i e dv i ac o m p a r a t i v e s i m u l a t i o ne x p e r i m e n t so fo t h e ra l g o r i t h m si ns o l v i n gt h ef u n c t i o n o p t i m i z a t i o np r o b l e m s s i m u l a t i o nr e s u l t sd e m o n s t r a t et h a t t h e p e r f o r m a n c eo fn f a g a i sb e t t e rt h a nt h eo t h e ra l g o r i t h m so b v i o u s l y 3 t h e c o n v e r g e n c ea n dc o n v e r g e n c e r a t eo fe g ab a s e do n m a r t i n g a l ea p p r o a c hi s s t u d i e d t h ep r o c e s so ft h em a x i m u mf i t n e s s f u n c t i o nw h i c hc o u l db et r a n s f o r m e di n t o s u b m a r t i n g a l ei su s e dt o d e s c r i b et h ee v o l u t i o np r o c e s so fg a b a s e do nt h es u b m a r t i n g a l e c o n v e r g e n c et h e o r e m ，t h ec o n v e r g e n c eo fe g ai sa n a l y z e d ，t h em a t h e x p r e s s i o nb e t w e e ni t sc o n v e r g e n c er a t ew i t ht h eo p e r a t i n gp a r a m e t e r si s d e r i v e d ，a n dt h em a x i m u me v o l u t i o n a lg e n e r a t i o nt of i n dt h eg l o b a l o p t i m a ls o l u t i o no fe g a i sc a l c u l a t e d k e yw o r d sf u z z ya d a p t i v eg e n e t i ca l g o r i t h m , s i m u l a t i o np l a t f o r m , s u b m a r t i n g a l e ，c o n v e r g e n c e ，c o n v e r g e n c er a t e 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：j 攀日期：望颦一年l 月旦日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允 许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：j 陋生盘导师签名家驾乞日期：j ! 乒年上月百 中南大学硕士学位论文第一章绪论 第一章绪论 遗传是一种生物从父代继承特性和性状的现象。生物进化的动力和机制在于 自然选择，“物竞天择，适者生存”是生物进化的过程。生物通过向自身演化的 过程学习，来增强自身解决问题的能力，其表现在抽象的算法上就是遗传算法 ( g e n e t i ca l g o r i t h m ，简称g a ) 。遗传算法求解优化问题的性能很大程度上取决 于交叉概率( 胁) 、变异概率( p r o ) 等参数的选择，合理地选取p 。、p m 是提高g a 效率的重要因素之一。因此，在实际应用中要对g a 的参数进行自适应调整。本 文运用模糊控制的方法，对g a 的交叉概率和变异概率等运行参数进行自适应控 制；同时，利用另一个遗传算法优化模糊控制器的知识库，实现了一种嵌套式模 糊自适应遗传算法，进一步改善了g a 的性能。 g a 的收敛性分析和收敛速度的研究是g a 的核心理论问题。然而，目前关 于收敛性和收敛速度的研究结果还不够系统和深入，也不便于实际应用。本文研 究基于鞅理论的保留精英遗传算法的收敛性和收敛速度，研究结果以求用于实时 控制系统。 本章主要包括以下内容：简述遗传算法的发展及其应用、国内外研究现状， 介绍论文主要研究内容及结构安排。 1 1 遗传算法的发展及其应用 1 1 1 遗传算法的发展 遗传算法是生命科学与工程科学互相交叉、互相渗透的产物。遗传算法的产 生是受启发于自然界的生物从低级到高级，从简单到复杂的进化过程i l 】。其遵循 的原则就是达尔文的进化论，优胜劣汰、适者生存；其本质是一种求解问题的高 度并行性全局搜索算法。它能在搜索过程中自动获取和积累有关搜索空间的知 识，并自适应地控制搜索过程以求得最优解。遗传算法的兴起与发展有两个背景： 其一是工程领域，特别是人工智能与控制领域，不断涌现出超大规模的非线性系 统，在这些系统的研究中存在着大量的经典优化方法所不能有效求解的优化问 题；其二，遗传算法本身就是一种模拟自然演化的学习过程的求解问题方法，它 能以独立的形式或是与其他方法相结合的形式用于智能机器学习系统的设计中 【2 】。经过几十年的努力，遗传算法不论是在应用上、算法设计上，还是在基础理 论上，均取得了长足的发展，已成为信息科学、计算机科学、运筹学和应用数学 等诸多学科所共同关注的热点研究领域【3 】，其研究和发展过程可分为以下几个阶 段： 中南大学硕士学位论文第一章绪论 ( 1 ) 2 0 世纪6 0 7 0 年代的兴起阶段 美国密歇根大学的j o h nh o l l a n d 教授最早认识到自然遗传进化可以转化为 人工智能算法。1 9 6 5 年，他将遗传操作应用于自然和人工系统的自适应行为的 研究中。1 9 6 7 年，h o l l a n d 的学生j d b a g l e y 在他的博士论文中首次提出了“遗 传算法 一词，并发展了选择、交叉、变异、显性、倒位等遗传算子。1 9 6 8 年， h o l l a n d 提出了遗传算法的基本定理模式定理( s c h e m at h e o r e m ) ，奠定了遗 传算法的理论基础。1 9 7 5 年，h o l l a n d 出版了他的开创性著作，第一部系统论述 遗传算法和人工自适应系统的专著自然系统和人工系统的适配。同年，美国 密歇根大学的d ej o n g 在他的博士论文一类遗传自适应系统的行为分析中建 立了遗传算法的工作框架和著名的d ej o n g 五函数测试平台，用于研究简单遗传 算法基准参数。 ( 2 ) 2 0 世纪8 0 年代的发展阶段 2 0 世纪8 0 年代，h o l l a n d 教授实现了第一个基于遗传算法的机器学习系统 分类系统( c l a s s i f i e rs y s t e m s ) ，提出了遗传算法的机器学习的新概念，为分 类器在构造上提出了一个完整的框架。1 9 8 9 年，g o l d b e r g 出版了专著搜索、 优化和机器学习中的遗传算法，总结了遗传算法的主要研究成果，对遗传算法 的基本原理及应用做了比较详细、全面地论述，奠定了现代遗传算法的科学基础， 形成了遗传算法的基本框架。此后，许多学者对遗传算法进行了大量改进和发展， 提出了许多成功的遗传算法模型，从而使遗传算法应用于更广泛的领域。 ( 3 ) 2 0 世纪9 0 年代的高潮阶段 2 0 世纪9 0 年代，人们比较重视遗传算法的一些基本问题。遗传算法作为一 种高效实用、鲁棒性强的全局优化算法，它的发展极为迅速，在不同领域( 如机 器学习、模式识别、神经网络及工程优化等) 中得到广泛地应用，引起了众多学 者的关注。在最近兴起的人工生命、遗传编程、进化计算等领域中，研究人员将 遗传算法与计算机科学相结合，试图模拟自然界的自适应、自组织和再生能力， 设计出具有“生命 的人工系统【4 1 。 1 1 2 遗传算法的应用领域 近几十年来，遗传算法不论是在应用上，还是在各种问题的求解上都展现了 它的特点和魅力，在基础理论和算法设计上也取得了长足的进步，已成为信息科 学、计算机科学、运筹学和应用数学等诸多学科所共同关注的热点研究领域，其 主要应用领域有【5 j ： ( 1 ) 函数优化：函数优化是遗传算法的经典应用领域。对于一些非线性、 多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法却可以 方便地得到较好的结果。 2 中南人学硕十学位论文第一章绪论 ( 2 ) 组合优化：对较大规模的组合问题，目前在计算机上用枚举法很难甚 至不可能求出其精确最优解，而遗传算法则较为方便的求得其满意解。实践证明， 遗传算法对于组合优化中的n p 完全问题非常有效【6 】。 ( 3 ) 生产调度问题：遗传算法已成为解决复杂调度问题的有效工具，在单 件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面都有有效的 应用。 ( 4 ) 自动控制：在自动控制领域中有很多与优化相关的问题需要求解，遗 传算法已在其中得到了初步的应用，并显示出了良好的效果。 遗传算法是一种全局搜索算法，根据适应度函数来评价算法的效果，不要求 适应度函数可微，对问题的依赖性小，可以避免陷入局部最优，非常适合用于模 糊控制器的优化设计。金耀初等【| 7 8 】分别采用梯度算法和遗传算法优化模糊控制 规则，比较其优缺点，结果表明遗传算法有较大的优越性。 ( 5 ) 机器人学：机器人是一类复杂的难以精确建模的人工系统，而遗传算 法的起源就来自于对人工自适应系统的研究，所以机器人学理所当然地成为遗传 算法的一个重要应用领域。 ( 6 ) 图像处理：图像处理是计算机视觉中的一个重要研究领域。遗传算法 在图像处理的优化计算，如模式识别、图像恢复、图像边缘特征提取等方面都有 很好的应用。 ( 7 ) 人工生命：人工生命是用计算机、机械等人工媒体模拟或构造出的具 有自然生物系统特有行为的人造系统。遗传算法与人工生命有密切的关系，基于 遗传算法的进化模型是研究人工生命现象的重要基础理论。 1 2 遗传算法的研究现状 遗传算法自身的研究工作目前主要集中在以下几个方面： ( 1 ) 遗传算法设计与执行策略的改进：遗传算法自身还存在一些不足之处， 如容易陷入局部极值，导致算法过早收敛等，为此，需要对算法做进一步的改进。 这些改进主要集中在两个方面：一是对算法本身的各个要素，即编码方法、适应 度值评价方法、选择机制、交叉机制和变异机制等做迸一步修正，使算法能较快 的搜索到全局最优解；另一方面是在其执行策略上做一些改进，将遗传算法和其 它寻优方法，如模拟退火算法、启发式算法、并行算法和梯度法等相结合，提高 其收敛速度和寻优能力。实践证明，结合后的混合算法无论是在收敛速度上，还 是在搜索到最优解的可能性上都比单纯使用遗传算法要好得多【5 】。 ( 2 ) 遗传算法的基础理论研究：对于遗传算法的理论分析方法主要有两类： 一类是遗传算法的马氏链模型；一类是v o s e l i e p i n s 模型。它们都给出了遗传算 3 中南大学硕士学位论文 第一章绪论 法收敛的一般定理，为保证遗传算法收敛到全局最优解提供了一定的理论依据。 虽然遗传算法已有不少的理论研究，但仍然不能说是很完善的，譬如关于各种改 进的遗传算法的收敛速度估计仍然没有得到很好的解决。 至今，无论是对遗传算法的理论研究，还是应用研究都分外活跃，国内外有 关遗传算法的研究热潮方兴未艾。众多的研究单位和频繁的国际学术活动集中反 映了遗传算法的学术意义和应用价值。目前，还没有一种通用的方法能根据要解 决的问题自动地设置高效的控制参数，只能根据经验和多次运行遗传算法的结果 进行人工设置和修正。大部分研究机构主要集中于研究遗传算法和进化算法作为 优化问题通用求解算法的一系列问题。本文研究的内容涉及以上两个方面的内 容，包括遗传算法参数的自适应控制和收敛性研究。关于遗传算法的参数控制和 收敛性研究现状简述如下。 1 2 1g a 参数控制方法研究现状 遗传算法求解优化问题的性能很大程度上取决于解空间搜索广度和深度之 间的平衡，而交叉概率、变异概率等参数的大小都是决定搜索广度和深度之间关 系的重要因素【9 】。不同的参数配置对g a 的优化效果有显著的影响，通常交叉概 率越高，算法就可以越快地收敛到最优解区域，然而，交叉概率越大具有高适应 度遗传模式被破坏的可能性就越大，但是如果交叉概率过小，则会使搜索过程缓 慢，以致停滞不前，造成算法不收敛。变异概率与交叉概率有近似的作用，变异 概率过小，就不易产生新的个体结构，而如果变异概率取值过大，会使算法变成 纯粹的随机搜索算法【l m l 2 】。因此，合理地选取交叉概率与变异概率是提高遗传算 法效率的重要因素之一。至今为止，交叉和变异概率的选择还没有理论依据，只 是给出了一个选择的推荐范围，其中，交叉概率取0 4 0 9 9 ，变异概率取 0 0 0 0 1 0 1 。在这么大的范围内随机地选择交叉概率和变异概率显然带有很大的 盲目性。实践表明，如果交叉概率和变异概率选择不当，不仅会降低遗传算法的 收敛速率，而且会产生早熟收敛，导致寻优结果失败。现有的一些自适应生成交 叉概率与变异概率的方法仍容易产生进化速度较慢和早熟收敛的现象。 目前，遗传算法参数设置的方法可大致分为参数调节和参数控制两大类【1 3 】。 其中，参数调节是指在算法运行f i 用试验的方法寻找出合适的参数值，然后将其 代入算法中运算，这些参数值将在整个算法搜索过程中保持不变。这种方法最大 的缺点是由于各参数间并不是相互独立的，对所有参数的所有可能值的组合进行 试验，寻找最佳组合值，耗时相当大，甚至是无法实现的。参数控制则是指算法 参数丌始以初始值运行，而后在运行的过程中能够根据算法搜索情况进行自适应 地改变。这类方法又可以用两种形式来实现：一种是应用传统的启发式规则控制。 遗传算法的参数；而另一种是用人工智能技术自适应调整算法的参数1 1 4 】。 4 中南人学硕十学位论文 第一章绪论 基于启发式规则的遗传算法参数自适应控制方法是根据参数大小变化对算 法性能的影响建立确定性参数规则，通常这些参数规则是可以用清晰的数学公式 表示的条件语句，算法参数将在满足条件语句前件的情况下，取得预先设定好的 确定值或由确定公式计算的值。基于人工智能的遗传算法参数自适应控制方法最 常见的是将模糊逻辑应用于参数控制，可以使算法具有较好的优化环境的适应 性。这类方法的参数控制规则一般是用模仿人智能的模糊语言表示，无需预先给 出参数明确的设定值。 人们对遗传算法运行参数对算法性能的影响早已有了一定的认识，如 h y x u 和v u k o v i c h 在文献 1 5 中设计了一种模糊遗传算法，用于生成七自由度 机器人轨道，取得很好效果。该算法用两个模糊控制器分别在线调整交叉概率和 变异概率，控制器的输入是当前种群规模和进化代数，控制规则是基于类似“当 进化过程接近最优解时，很快减小变异概率，以免破坏包含最优解的基因模式” 的对遗传算法的认识而设计的。又如李欣等在文献 1 6 中提到：自然界中，保持 种群一定程度的多样性对生物进化过程非常重要，同样，遗传算法中种群多样性 太低，算法找不到最优解，种群多样性太高，则算法不收敛。交叉和变异使遗传 算法的搜索能力提高并维持种群的多样性，因此，种群规模越大，个体多样性增 加，只需要很小的变异概率，反之，则需增大变异概率；且在进化初期，需要较 大的变异概率，以增加种群多样性来扩大搜索空间，而在进化后期，应减小变异 概率，保护接近最优解的个体，以获得最优或准最优解。文献 1 7 根据遗传算法 参数自适应控制方法的不同分类，采用基于启发式规则的参数控制方法对遗传算 法的种群数进行了宏观调控和微观调控，并采用不同特点的模糊控制器分别控制 交叉率和变异率，使种群数、交叉概率和变异概率都能够随进化的实际情况发生 自动调整，形成了一种新的种群数变化的模糊自适应遗传算法。 研究表明，对遗传算法运行参数控制的进一步研究和探讨是很必要的。正是 基于这种思考，针对简单遗传算法及现有的一些自适应遗传算法的缺陷，本文结 合模糊逻辑控制，对遗传算法的交叉概率和变异概率进行自适应控制，并利用另 一个遗传算法优化模糊控制器的知识库，提出了一种嵌套式的模糊自适应遗传算 法。该算法不仅能加快遗传进化速度，而且能增强遗传算法的全局收敛性能，从 而得到满意的全局最优解。最后，基于m a t l a bg u i 开发了新算法的仿真平台， 通过仿真实验验证了提出的改进算法的有效性。 1 2 2g a 收敛性研究现状 一种理论是否成熟很大程度上取决于其数学描述的完善程度。收敛性理论作 为遗传算法的一个核心理论问题，是评价g a 的重要指标，它包含收敛性与收敛 速度的研究。收敛性是g a 研究中的一个基本理论问题，决定着算法的可行性， 中南大学硕士学位论文第一章绪论 影响着算法的发展。收敛速度也是衡量遗传算法性能的重要指标，即使具有收敛 性的遗传算法，在用于实际问题时是否有效，取决于其收敛的快慢程度，即收敛 速度。对于一个收敛很慢的遗传算法，若在解决问题时花费的时间代价是人们难 以忍受的，则这种算法可以认为是无效的。由此可见，对遗传算法收敛理论的研 究是算法理论与应用的必然要求。 收敛问题曾困扰了人4 r 1 , 1 曼长时间，令人欣慰的研究结果也层出不穷。r u d o l p h 证明了简单遗传算法在概率意义下不收敛，采用精英保留策略可保证算法在概率 意义下的收敛。f o g e l 证明了：当不使用变异算子时，所生成的m a r k o v 链将存 在吸收态。g o l d b e r g 采用m a r k o v 链分析方法对一种只有变异和复制的遗传算法 的收敛性进行了分析【1 8 1 。文献 1 9 1 基于简化的g a ( 采用最小种群规模，忽略交 叉算子) 和最简单的优化问题( 二进制l 的计数问题) ，应用顺序统计学对收敛 速度进行了分析，但其分析方法很难甚至不可能推广到标准g a 和一般的优化问 题。文献 2 0 将遗传算法的平均收敛速度定义为最佳个体转移至吸收态的平均吸 收时间的数学期望，提出了应用最佳个体的随机矩阵估计遗传算法平均收敛速度 的理论方法和计算步骤。文献 2 1 】研究了一类不使用精英保留策略的遗传算法的 收敛速度，利用m a r k o v 链一个特殊的m i n o r i z a t i o n 条件，讨论了该类遗传算法 的收敛速度。尽管g a 收敛性的研究已取得了较大进展，但是其理论的系统性和 通用性还远远不够，大致地说，遗传算法过早收敛现象发生在算法种群演化到一 种非全局最优状态，它使得算法的进一步迭代已不能产生更佳可行解。 时至今日，已经有相当多的国内外专家学者致力于此，提出了各自的认识及 相关研究成果。然而，遗传算法已有的收敛性分析大都是在概率收敛意义下考虑 的且基于算法的遍历性分析，这种收敛性分析不确保算法在有限步内收敛到问题 的全局最优解，由于转移概率的复杂性，这些证明都比较复杂。文献 2 2 首次尝 试运用鞅论研究遗传算法的几乎必然强收敛性，证明一大类不带“杰出者记录策 略”的遗传算法能以概率1 确保在有限步内达到全局最优解，所获结果为遗传算 法的实际应用奠定了理论基础，且所使用的鞅论分析方法为遗传算法研究提供了 全新的分析方法。随后，基于鞅理论的遗传算法的收敛性和收敛率研究有了进一 步发展。文献 2 3 1 通过鞅论分析给出了一定条件下杰出遗传算法和整体退火遗传 算法的收敛率，它只以概率形式给出遗传算法的收敛率，不依赖于染色体的编码 形式，也不依赖于转移矩阵及特征值的分析，在形式上更加简单明了，这是鞅分 析方法优于马尔科夫链分析方法的独特优势。文献 2 4 引入鞅方法分析了生物免 疫遗传算法所形成种群的鞅性质，并得出了算法本身的几乎处处强收敛性结论。 6 中南大学硕十学位论文第一章绪论 1 3 论文主要研究内容及结构安排 本文的主要研究内容包括两方面：其一，研究遗传算法参数的自适应控制， 论文针对交叉概率和变异概率的自适应控制问题，实现了嵌套式模糊自适应遗传 算法，并基于m a t l a b 开发了其仿真平台；其二，基于鞅理论研究保留精英遗 传算法的收敛性和收敛速度，并对理论研究结果进行了相关的仿真验证。根据论 文的研究内容，各章节内容安排如下： 第一章为绪论部分，介绍了遗传算法的产生背景、发展历程及应用，简述了 遗传算法参数控制方法和收敛性研究的国内外研究现状，说明了本文的主要内容 安排。 第二章作为理论基础，介绍了遗传算法的特点，简述了简单遗传算法的基本 框架及遗传算法收敛性分析的相关理论。 第三章首先介绍了自适应遗传算法和模糊自适应遗传算法，针对这些现有的 自适应遗传算法存在的问题，通过采用两级嵌套的遗传算法，随主遗传算法g a l 求解优化问题的进化进程用模糊控制的方法自适应地调整遗传算法的交叉概率 和变异概率；同时，利用另一个遗传算法g a 2 优化模糊控制器的知识库，实现 了一种嵌套式模糊自适应遗传算法。 第四章基于仿真软件m a t a l b 实现了嵌套式模糊自适应遗传算法的仿真平 台开发，选取典型的测试函数，通过与简单遗传算法( s g a ) 、一般的自适应遗 传算法( a g a ) 和基于专家经验知识的模糊自适应遗传算法( e f a g a ) 对比实 验，验证论文研究的算法的有效性。 第五章研究了保留精英遗传算法的收敛性和收敛速度。其思想是避开了传统 的基于m a r k o v 链的遍历性分析，基于下鞅收敛定理，通过把最大适应度函数过 程转换成下鞅进行理论研究，并给出了相关的实验验证。 第六章结束语，对论文的研究工作进行了总结，并对下一步研究工作进行了 简单展望。 7 中南大学硕士学位论文第二章遗传算法的基本理论 第二章遗传算法的基本理论 2 1 遗传算法的特点 遗传算法是一种基于自然选择和遗传变异等生物机制的全局性概率搜索算 法。与基于导数的解析方法和其他启发搜索方法一样，遗传算法在形式上也是一 种迭代方法，它使用种群搜索技术，通过对当前的种群采用类似于自然选择和有 性繁殖的方式，在继承原有优良基因的基础上，生成具有更好性能指标的下一代 解的群体。它不是简单的随机化搜索方法，而是通过对染色体的评价和对染色体 中基因的作用，利用已有的信息来指导搜索，逐渐使得种群进化到包含或接近最 优解的状态。遗传算法的主要本质特征在于群体搜索策略和简单的进化算子。群 体搜索使遗传算法得以突破邻域搜索的限制，可以实现整个解空间上的分布式信 息搜索、采集和继承，从而保证了解的全局性；进化算子仅仅利用适应值度量作 为运算指标进行染色体的随机操作，降低了一般启发式算法在搜索过程中对人机 交互的依赖，使遗传算法获得强大的全局最优解搜索能力。问题域独立性，信息 处理的隐并行性，应用的鲁棒性，操作的简明性，使得遗传算法成为一种具有良 好普适性和可规模化的优化方法，但遗传算法也有其自身的缺点，如容易产生早 熟收敛以及收敛速度慢等。遗传算法是一种仿生优化算法，它与传统的优化算法 有许多不同之处，其最主要的特点体现在以下几个方面【2 5 】： ( 1 ) 遗传算法直接以适应度作为搜索信息，无需导数或其他辅助信息。求 解问题时，搜索过程既不受优化函数连续性的约束，也没有优化函数导数必须存 在的要求。通过对优良染色体的基因重组，遗传算法可以有效地处理复杂的优化 函数求解问题。 ( 2 ) 遗传算法具有很高的并行性。它不直接作用在解集上，而是从优化问 题的解的编码开始搜索，可以同时搜索解空间的多个区域搜索信息，从而降低算 法陷入局部最优解的可能性。 ( 3 ) 遗传算法具很强的鲁棒性。在待求解问题为非连续、多峰以及有噪声 的情况下，它能够以很大的可能性收敛到最优解或近似最优解，因而遗传算法具 有很好的求解能力。 ( 4 ) 遗传算法具有较高的可扩充性。它易于与其它领域的知识或算法相结 合来求解特定问题。 ( 5 ) 遗传算法的基本思想简单，具有良好的可操作性和简单性。 ( 6 ) 遗传算法具有较强的智能性，可以用来解决复杂的非结构化问题。 中南大学硕士学位论文 第二章遗传算法的基本理论 2 2 遗传算法的基本框架 生物进化过程的发生一般需要四个基本条件：( 1 ) 存在由多个生物个体组成 的种群；( 2 ) 生物个体之间存在着差异，或种群具有多样性；( 3 ) 生物能够自我 繁殖；( 4 ) 不同个体具有不同的环境生存能力，具有优良基因结构的个体繁殖能 力强，反之则弱。生物种群的进化机制包括三种基本形式：( 1 ) 自然选择；( 2 ) 交叉；( 3 ) 变异。外界对生物的评价反映了生物的生存价值和机会。遗传算法是 以编码空间代替问题的参数空间，以适应度函数为评价依据，以编码群体为遗传 基础，以对群体中个体位串的遗传操作实现遗传机制，建立起一个迭代过程。从 代表问题可能潜在解集的一个种群开始( 该种群由一些经过基因编码的一定个数 的个体组成) ，根据问题的特点，制定特定的适应度函数，对每一代种群，根据 问题域中个体的适应度大小来选择个体，利用交叉算子和变异算子等遗传算子进 行作用，从而产生出代表新的解集的下一代种群。遗传算法在整个遗传过程中的 遗传操作是随机性的，但它呈现出的特征并不是完全随机搜索，它能有效的利用 历史信息来推测下一代期望性能有所提高的寻优点集。这样一代代的不断遗传， 最后收敛到一个最适应环境的个体上，求得问题的最优解。 h o l l a n d 通过模拟生物进化过程设计了最初的遗传算法，称之为简单遗传算 法( s g a ) 。s g a 给出了遗传算法的基本框架，以后对于遗传算法的改进，都是 基于此算法。s g a 的基本框架如图2 1 所示。 种群p o p ( o 上 选择运算 山 交叉运算个体评价 上 l 变异运算 上 种群p 似f + 1 ) 卜_ - 叫解码1 1 蜘往厶 7 i ，竹乘口 遗传空自j 解空间 一一一一- - 一- 一一- 一- 一一一 图2 1s g a 基本框架 遗传算法是从待优化问题的可能潜在解集的一个种群开始，由经过基因编码 的一定数目的个体组成一个初始种群，按照适者生存和优胜劣汰的生物进化原 理，逐代演化生成越来越好的近似解或最优解。在每一代种群中，根据个体的适 应度大d , g l ；选个体，适应度高的个体容易被选中，然后借助交叉算子和变异算子， 9 中南大学硕士学位论文 第二章遗传算法的基本理论 产生出新的种群。通过这一过程使后代种群比前代种群更加适应环境，末代种群 中的最优个体经过解码，作为问题的最优解或近似最优解【2 眈8 1 。其主要运算过程 如下： ( 1 ) 初始化：设置进化代数计数器f ，最大进化代数乃随机生成肘个个体 作为初始种群p o p ( o ) ； ( 2 ) 个体评价：计算种群p o p ( i ) 中各个个体的适应度； ( 3 ) 选择运算：将选择算子作用于种群； ( 4 ) 交叉运算：将交叉算子作用于种群； ( 5 ) 变异运算：将变异算子作用于种群，种群p o p ( i ) 经过选择、交叉、变 异运算后得到下一代种群p o p ( i + 1 ) ； ( 6 ) 终止条件判断：若k l 则i = i + l ，转到( 2 ) ；若乃则以进化过程 中所得到的具有最大适应度的个体作为最优解输出，终止运算。 遗传算法的设计主要有五大要素：参数编码、初始种群的设定、适应度函数 的设计、遗传算子的设计和控制参数的设定。 1 参数编码 遗传算法不能直接处理问题空间的参数，而只能处理以基因码串形式表示的 个体。因此，要使用遗传算法，就必须把优化问题的解的参数形式转换成基因码 串的表示形式，这一转换操作就叫做编码。一般来说，由于遗传算法计算过程的 鲁棒性，它对编码的要求并不苛刻，但编码的策略对于遗传算子，尤其是对交叉 和变异算子的功能和设计有很大的影响，设计时应斟酌确定。 问题的编码一般应满足以下三个规则： ( 1 ) 完备性：原问题空间中的所有点( 可行解) 都能成为编码后的点； ( 2 ) 健全性：编码后的空间中的点能对应原问题空间所有的点； ( 3 ) 非冗余性：编码前后空间的点一一对应。 在实际操作中，二进制编码是最基本的编码方式，它的应用非常广泛。除了 二进制编码以外，还有各种其他的编码形式，如：格雷码编码、序列编码、实数 编码、符号编码等【2 9 1 。 2 初始种群 初始种群的好坏对于遗传算法的计算结果的优劣和算法的效率有着重要影 响f 2 “。简单遗传算法通过随机的方法产生一定数目的初始种群，它覆盖的参数 空间具有很大的不确定性，如果初始种群中不包含全局最优解的基因，而经过有 限次进化后，算法又没有得到全局最优解，那么就一定会产生早熟收敛。产生初 1 0 中南大学硕士学位论文第二章遗传算法的基本理论 始种群通常有两种方法。一种是完全随机的产生方法，它适用于对待求解问题的 解无任何先验知识的情况；另一种是把某些先验知识转化为必须满足的一组要 求，然后在满足这些要求的解中随机地选取。这种选择初始种群的方法可以使遗 传算法较快地达到最优解。 3 适应度函数 遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数为依据，利用 种群中每个个体的适应度值来进行搜索。因此，适应度函数的选取至关重要，直 接影响到遗传算法的收敛速度以及能否找到最优解。适应度函数的设计一般要满 足三个条件：( 1 ) 解析性质：连续、非负；( 2 ) 合理性：要求适应度函数设计应 尽可能简单；( 3 ) 近似量小：适应度函数对某一类具体问题，应尽可能通用。 g a 常常将目标函数直接作为适应度函数，但由于在执行选择操作时，它要按与 个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的几 率，而要正确计算此概率，要求所有个体的适应度函数值必须非负。所以实际操 作时，常常将目标函数适当作一些处理，具体为： ( 1 ) 直接将待求解的目标函数转化为适应度函数，即： 若目标函数为最大化问题，则 f i t ( f ( x ) ) = 厂( 工) ( 2 - 1 ) 若目标函数为最小化问题，则 f i t ( f ( x ) ) = - f ( x ) ( 2 2 ) ( 2 ) 将待求解的目标函数做适当处理后再转化为适应度函数，即： 若目标函数为最大化问题，则 砌c 删= 1 0 0 卜盟晌 3 ， 式中c 晌为f ( x ) 的最小估计值。 若目标函数为最小化问题 刚砌_ “斑q 一 亿4 ， 式中c 一为f ( x ) 的最大估计值。 采用合理的适应度函数，不仅有利于保持种群的多样性，而且能够改善遗传 算法的性能。适应度函数的设计在保证不同个体能够利用其适应度进行优劣区分 的同时，还要考虑以下两点：首先是遗传算法的进化初期，种群中可能存在一些 适应度非常好的个体，最终这些适应度较高的个体可能会占据整个种群，此时用 来产生新个体的交叉操作就会失去原有的作用，从而导致遗传算法提前收敛到某 中南大学硕十学位论文 第二章遗传算法的基本理论 个局部最优解。其次是进化后期，种群越来越集中，个体之间的差异越来越小， 个体之间的竞争力也随之减小。这必然造成个体被复制到下一代中的概率比较接 近，使进化失去竞争力，算法退化为随机搜索过程。因此，适应度函数的选取应 该尽量避免进化初期容易产生的早熟现象，即使适应度较高的个体与其它个体适 应度之间的差异降低，限制适应度较高的个体的复制数量，保证种群的多样性适 应度函数的选取也应该克服进化后期容易产生的退化现象，使算法在进化后期能 够扩大最优个体适应度与其它个体适应度之间的差异，提高个体之间的竞争力。 4 遗传算子 优胜劣汰是设计g a 的基本思想，它应在选择、交叉和变异等遗传算子中得 以体现，并考虑到对算法效率与性能的影响。 ( 1 ) 选择算子 选择操作建立在对个体的适应度进行评价的基础之上，适应度较高的个体被 遗传到下一代群体中的概率较大；适应度较低的个体被遗传到下一代群体中的概 率较小，因而可以避免有效基因的损失，使高性能的个体得以较大的概率生存， 从而提高全局收敛性和计算效率。 目前常用的选择算子是赌盘选择( 也叫适应度比例选择) ，它是以正比于个 体适应度函数值的概率来选择相应的个体。设种群规模为m ，个体i 的适应度函 数值为f ，则个体i 被选中的概率p ，为： i = 1 , 2 ，m ( 2 5 ) 其他比较常用的选择算子还有：精英选择、排序选择、联赛选择等形式【3 0 】。 ( 2 ) 交叉算子 交叉算子是遗传算法区别于其他进化算法的独有特征。它是模仿自然界有性 繁殖的基因重组过程，其作用在于将原有的优良基因遗传到下一代种群中，生成 新个体。交叉算子不仅具有优化功能，而且是产生新个体的主要手段【3 1 1 ，保证 了种群的多样性。常用的交叉算子包括单点交叉、两点交叉、多点交叉、均匀交 叉等形式。单点交叉算子破坏个体性状较小，使得有效模式受的破坏的概率较小， 但它生成一些有效模式的概率也较小，故不利于抑制遗传算法的早熟现象：多点 交叉会随着交叉点数的增多，个体的结构被破坏的可能性也逐渐增大，这样很可 能会破坏掉一些好的模式，所以使用时要