（模式识别与智能系统专业论文）遗传算法的若干理论分析.pdf

浙江大学硕士学位论文 摘要 | l 遗传算法是借助生物界自然选择和遗传学机理而建立的一种迭代全局优化随 机搜索算法，是一种求解复杂系统优化问题的通用框架。它不依赖于问题的具体 领域，具有简单、通用、较强的自适应性和鲁棒性，以及适于并行处理等显著特 点，因此被广泛应用于众多领域。 作为一种仿生算法，遗传算法的应用研究远远领先于算法的基础理论研究。 现有的遗传算法的相关理论：修正的模式定理、马氏链收敛分析等在一定程度上 奠定了遗传算法的理论基石，促进了理论研究和应用研究的进一步发展。但是， 遗传算法的全局收敛性、计算复杂性、算子的运行机理等方面还缺乏严格意义上 的数学分析，这已经成为遗传算法发展的瓶颈。f r 本文对遗传算法的一些基本问题，如算法的编码方式、收敛性、算法参数设 置和算子设计等方面，进行了深入的研究分析，提出了一些有效的分析方法。具 体包括以下几部分内容： l _ 针对各种遗传算法的收敛性，提出了一个统一的收敛准则。眭利用马氏链 。一- - 。一 、 分析了三种典型的遗传算法的收敛性的基础上，通过对比几个证明过程的异同点， 提出了一个统一的收敛性判断准则。可以对不同的遗传算法分析其收敛性，而无 需考虑g a 模型差异，无需烦杂推理和大规模计算，有利于在实际应用中判断遗 传算法的敛散性和设计新的遗传算子。， 2 遗传算法以选2 匿垄选的编码作为运算对象，三种基本的遗传算子的选择和 设计都依赖于编码的方式。l 编码策略是设计遗传算法的一个重要步骤，编码也成 t 为遗传算法应用中的首要问题，因而建立完善的编码方面的理论指导是必要的。 通过研究二进制码和格雷码的编码、解码公式，分析了编码差异、个体差异和适 应度差异之间的联系，指出了部分文献中的漏误之处，并进一步通过理论分析说 明了两种不同编码对遗传算子搜索能力的影响。y 3 实践和理论都已经证明，遗传算子所采用的参数会影响算法的搜索效率和 收敛速度。本文针对遗传参数缺乏理论指导的问题，采用简单的概率分析方法， 从遗传算予的搜索能力的角度出发，分析了变异算予作用机理，得出部分算法参 新试入学碗i 学位论文 数数关联约乘。基于褥至的关联约来，提如了设饕算法参数豹应该遴循静部分规 则。然螽遵过对应用实铡的分析谎裙了规鄹静合瑗桎。 最螽，在慈结全文的慕穑上，指出了遗传算法基础理论上有待深入研究的若 干问题。 浙江人+ 1 i + 硕十学何论文 a b s t r a c t g e n e t i ca l g o r i t h mi sak i n do fs t o c h a s t i c w h o l e - s e a r c h i n gr e g r e s s i o n a l g o r i t h m ，w h i c hi sb u i l to nn a t u r a ls e l e c t i o na n dm o l e c u l eg e n e t i cm e c h a n i s m ， a sak i n do fu n i v e r s a l a l g o r i t h m t o o p t i m i z et h ep r o b l e m so fc o m p l i c a t e d s y s t e m ，i ti sw i d e l yu s e di nm a n y f i e l d sd u et oi t ss u p p l e n e s s ，u n i v e r s a l i t y ，w e l l s e l f - f i t n e s s ，r o b u s t n e s sa n df i t n e s sf o rc o l l a t e r a lp r o c e s s ， a sak i n do fb i o n i ca l g o r i t h m s ，t h er e s e a r c ho ng a sa p p l i c a t i o nk e e p sf a r a h e a do fi t st h e o r e t i cr e s e a r c h t h e r ea r em a n yt h e o r i e so fg a s u c ha st h e m o d i f i e dm o d e lt h e o r e ma n d c o n v e r g e n c et h e o r y ，w h i c hh a v e a c c e l e r a t e dt h e r e s e a r c ho fi t s a p p l i c a t i o n b u tt h el a c ko fs t r i c t a n a l y s i sb l o c k st h ef a r t h e r d e v e l o p m e n t o fg a t h i sp a p e rc o n c e n t r a t e ss o m eb a s i cp r o b l e m so fg a a n dp u t sf o r w a r d s e v e r a lm e t h o d st oa n a l y z eak i n do fg a s ，t h em a i n w o r k s a r el i s t e db e l o w ： p u tf o r w a r dau n i v e r s a lr u l et oj u d g et h ec o n v e r g e n c eo fa l lk i n d so f g a s 2 a n a l y z et w ok i n d so fc o d i n gs t r a t e g ya n dg i v es o m ef e a t h e r so ft h e c o d i n gm e t h o d w h i c hc a nb e u s e dt oa n a l y z et h es e a r c ha b i l i t yo fg a o p e r a t o r s 3 i no r d e rt os o l v et h e p r o b l e mt h a tt h e r ei sn ot h e o r e t i cf o u n d a t i o no nh o w t os e t p a r a m e t e r s i ng a ，t h i s p a p e rp r e s e n t sp a r a m e t e r r u l e sb a s e do n a n a l y z i n gt h es e a r c ha b i l i t yo fg ao p e r a t o r s t h e n u s et h e s er u l e sl oa n a l y z e a nl n s t a n c eo fm o d e | i d e n t i f i c a t i o nw h i c hi sb a s e do ng a 。f r o mt h i sw ec a ns e e t h a tt h er u l e sa r er e a s o n a b l e f i n a l l y w ec o n c l u d ea l l t h em a i np o i n t so ft h i sp a p e ra n dp o i n to u tt h e p r o b l e m sn e e ds t u d yf u r t h e r 浙江人学硕十学位论文 致谢 值此论文付梓之际，首先谨向我的导师荣冈教授表示崇高的敬意和衷心 的感谢! 本文的完成离不丌荣教授的悉心指导和热情鼓励。在我攻读硕士学位期 制，导师在学习、工作和生活上都给予了无微不至的关怀和帮助。荣老师严灌而 丌放的治学态度、渊博而深邃的学识、敏捷深刻的洞察力、幽默风趣的谈吐和睿 智达观的人生态度，是我今后学习和工作上的榜样。 王树青教授、王宁教授、金晓明副教授都给过我热情的指导和帮助，在此谨 向他们表示衷心的感谢。 感谢王寅、张溥明、赵向海、宋洁蔚、e 达、朱炜、洪一帆、章鹏、王晓例、 裘绍翔、赵小强、张惠良、李荣雨、张奇然、吴剑强、张建明、裴瑞凌、吕品晶 等人对我的帮助和支持。在学习过程中与他们所进行的诸多有益的探讨和交流， 使我获益匪浅。 感谢许峰、毛秀伟、苏宁军和李林欢，和他们之间的讨论给了我很多启发和 帮助。 对所有关心和帮助过我的同学和朋友们表示感谢。 谨以此文献给多年来一直理解、关怀、支持我的家人。 高峰 2 0 0 3 年4 月于求是园 第一章遗传算法研究概述 摘要 本章首先简述遗传算法的生物学基础，然后阐明遗传算法的发展过程和特点，并综述了 遗传算法的理论和麻用研究概况最后就本文的主要r 作给出说明。 关键词：生物学基础遗传算法研究综述 1 1 引言 长久以来，人们一谈到人工智能( a i ，a r t i f i c i a li r i t e l l i g e n t ) 就马上想 到逻辑、规则、推理，而一谈到计算就联想到矩阵运算、解微分方程，似乎智能 和计算是两条没有交点的线。人工智能在走过几十年的曲折道路之后，人们经过 认真反思，不断探索新的研究途径，于是一个新的研究方向智能计算应运而 生。 研究思维模拟主要的道路有四条”“：基于心理学的符号处理方法，基于社会 学层次型的智能体( a g e n t ) 方法，基于生物进化的进化计算( g c ，e v o l u t i o n a r y c o m p u t a t i o r ) 与自适应( s e l f - a d a p t i v e ) 方法，以及基于生理学的人工神经网 络( a n n ，a r t i f i c i a ln e u r a ln e t w o r k s ) 方法。目前聚集在智能计算大旗下的主要 是后两个学派的学者( 加上从事模糊计算和混沌计算等方面的学者) 。实际上，只 要在计算机上，模拟人类思想，不管用什么方法，其本质的基础还是二进制数字 计算，在当前符号处理主宰人工智能的情况下，更应强调遗传算法等以数字计算 为基础的方法对推动人工智能发展有着特殊的作用。 计算技术的飞速发展使大规模的现实模拟成为可能，而针对社会和生物现象 的模拟，对人类认识自身及其环境具有重大意义，进化是其中最为诱人的领域之 。人的智能是从哪里来的? 归根结底是从生物进化中得来的，反映在遗传基因 中，脑的结构变化也是通过基因的变化一代代遗传下来的。每一种基因产生的生 物个体( 看成一种结构) 对环境有一定的适应性，或叫适应度( f i t n e s s ) ，杂交和 基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选择( n a t u r a l s e l e c t i o n ) ，适应度高的结构被保存下来。因此从进化的观点看，结构优化是适 应度选择的结果。在这种观点启发下，6 0 年代f o g e 等提出了进化规划( e p ， e v o l u t i o n a r yp r o g r a n m i n g ) 思想，7 0 年代h o l l a n d 提出了遗传算法( o a ，g e n e t i c a 1g o r i t h m s ) ，如同神经网络研究一样，经过2 0 年的沉寂，到8 0 年代后期，由于 浙江人学硕十学位论文 花经济预测等应用领域获得成功，遗传算法成为十分热门的研究课题。 遗传算法是一类借鉴生物界自然选择和自然遗传机制的自适应全局优化概率 搜索算法，它起源于6 0 年代对自然和人工自适应系统的研究。遗传算法的主要特 j ! i 是群体搜索策略和群体中个体之问的信息交换和搜索不依赖于梯度信息，它尤 其适用于处理传统搜索方法难于解决的复杂和非线性问题。作为一种全局优化搜 索算法，以其简单、通用、较强的自适应性和鲁棒性，以及适于并行处理等特点， 被f l 泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域， 足2 1 世纪有关智能计算中的关键技术之一。它将和混沌理论、分形几何一起成为 研究非线性现象和复杂系统的三个主要新方法，并与神经网络一起成为人类研究 认知过程的重要工具。“。 1 2 遗传算法的生物学基础 生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。受 廷启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应 系统的设计和丌发提供了广阔的前景。遗传算法就是这种生物行为的计算机模拟 中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使 得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基 础就是生物的遗传( g e n e t i c s ) 和进化( e v o l u t i o n ) 。 i 。2 1 遗传与进化的特点 虽然人们还未完全揭开遗传与进化的奥秘，既没有完全掌握其机制、也不完 全清楚染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传与进化 的以下几个特点却为人们所共识“。”： 1 生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状。 2 染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色 体上。 3 生物的繁殖过程是由其基因的复制过程来完成的。 4 通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现 新的性状。 j 对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多 的机会遗传到下一代。 第一章遗传算法研究概述 1 2 2 遗传学与遗传算法基本用语的对应关系 g a 的仿生特性，决定了遗传科学与遗传算法之阳j 具有先天的对应关系，下面 以表格的形式来描述这种对应关系，有助于我们更好的理解算法。 表1 一l 生物遗传概念在遗传算法中的对应关系“1 生物遗传概念遗传算法中的作用 适者生存 个体( i n d i v i d u a l ) 染色体( c h r o m o s o m e ) 基因( g e n e ) 适应性( f i t n e s s ) 群体( p o p u f a t i o n ) 交配( c r o s s o v e r ) 变异( m u t a t i o n ) 等位基因( a i l e l e ) 基因座( l o c u s ) 基因型 ( g e n o t y p e ) 表现型( p h e n o t y p e ) 目标值越高的解被留住的可能性越大 解 解的编码( 如字符串、向量等) 解中每一分量的特征( 如各分量的值) 适应函数值 选定的一组解( 解的个数为群体规模) 通过交配原则产生一组新解的过程 编码的某一分量发生变化的过程 特性值 编码串中的位置 结构 参数集、解码结构、候选解 l - 3 遗传算法的发展与特点 1 3 1 遗传算法的发展历程 遗传算法起源于对生物系统所进行的计算机模拟研究。早在本世纪4 0 年代， 就有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进 行了生物的进化过程模拟、遗传过程模拟等研究工作。进入6 0 年代后，美国密歇 根大学的h o l l a n d 教授及其学生们受到这种生物模拟技术的启发，创造出了一种 基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术 遗传算法。下面是在遗传算法的发展进程中一些关键人物所做出的一些主要贡献。 i h h o l l a n d 6 0 年代，h o ll a n d 认识到了生物的遗传和自然进化现象与人工自适应系统的 相似关系，运用生物遗传和进化的思想来研究自然和人工自适应系统的生成以及 浙江人学硕十学付论文 它们与环境的关系提出在研究和设计人工自适应系统时，可以借鉴生物遗传的 机制，以群体的方法进行自适应搜索，并且充分认识到了交叉、变异等运算策略 在自适应系统中的重要性。 7 0 年代初，h o l l a n d 教授提出了遗传算法的基本定理模式定理( s c h e m a i h e o r e m ) ，从而奠定了遗传算法的理论基础。模式定理揭示出了群体中的优良个 体( 较好的模式) 的样本数将以指数级规律增长，因而从理论上保证了遗传算法是 一个可以用来寻求最优可行解的优化过程。1 9 7 5 年，h o l l a n d 出版了第一本系统 论述遗传算法和人工自适应系统的专著自然系统和人工系统的自适应性 ( a d a p t a t j o n i nn a t u r a la n da r t i f i c i a ls y s t e m s ) ”1 。 8 0 年代，h o l l a n d 教授实现了第个基于遗传算法的机器学习系统分类 器系统( c s ，c 1 a s s i f i e rs y s t e m ) ，丌创了基于遗传算法的机器学习的新概念， 为分类器系统构造出了一个完整的框架”1 。 2 j d b a g l e y 1 9 6 7 年，h o l l a n d 的学生b a g l e y 在其博士论文中首次提出了“遗传算法”一 1r ，并发表了遗传算法应用方面的第一篇论文。他发展了复制、交叉、变异、 钽性、倒位等遗传算子，在个体编码上使用了双倍体的编码方法。这些都与目前 遗传算法中所使用的算子和方法相类似。他还敏锐地意识到了在遗传算法执行的 f 周阶段可以便用不同的选择率，这将有利于防止遗传算法的早熟现象，从而创 立了自适应遗传算法的概念。 3 k a d ej o n g 19 7 5 年，d ej o n g 在其博士论文中结合模式定理进行了大量的纯数值函数优 化计算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结 论。】。例如，对于规模在5 0 1 0 0 的群体，经过1 0 2 0 代的进化，遗传算法都能 以很高的概率找到最优或近似最优解。他推荐了在大多数优化问题中都较适用的 遗传算法的参数，还建立了著名的d ej o n g 五函数测试平台，定义了评价遗传算 法性能的在线和离线指标。 4 d j g o l d b e r g 1 9 8 9 年，g o l d b e r g 出版了专著搜索、优化和机器学习中的遗传算法( g e n e t i c a 1 9 0 r i t h m si ns e a r c h ，o p t i m i z a t i o na n dm a c h i n el e a r n i n g ) “。该书系统 总结了遗传算法的主要研究成果，全面而完整地论述了遗传算法的基本原理及其 应用。可以说这本书奠定了现代遗传算法的科学基础，为众多研究和发展遗传算 法的学者所瞩目。 第一章遗传算法研究概述 1 9 9 1 年，d a y is 出版了遗传算法手册( h a n d b o o ko fg e n e t i ca i g o t i t h m s ) 书，书中包括了遗传算法在科学计算、工程技术和社会经济中的大量应用实例 “】。这本书为推广和普及遗传算法的应用起到了重要的指导作用。 6 j r k o z a 1 9 9 2 年，k o z a 将遗传算法应用于计算机程序的优化设计及自动生成，提出了 遗传编程( g e n e ti cp r o g r a m m in g ，简称g p ) 的概念“3 。他将一段l i s p 语言程序 作为个体的基因型，把问题的解编码为一棵树，基于遗传和进化的概念，对由树 组成的群体进行遗传运算，最终自动生成性能较好的计算机程序。k o z a 成功地把 他提出的遗传编程的方法应用于人工智能、机器学习、符号处理等方面。 i 3 2 遗传算法的特点 为了解决各种优化计算问题，人们提出了各种各样的优化算法，如单纯形法、 梯度法、动念规划法、分枝定界法等。这些优化算法各有各的长处和限制，有各 自不同的适用范围。与普通的搜索算法( 如梯度算法) 一样，遗传算法也是一种 迭代算法。但是与其他一些优化搜索算法相比，遗传搜索要求两个存在明显冲突 的方向之阳j 的平衡：挖掘( e x p l o i t a t i o n ) 最优解和探测( e x p l o r a t i o n ) 搜索空 间“。爬山法( h i l lc l i m b i n g ) 是尽可能地改进挖掘最优解策略的例子，但它忽 视了对搜索空间的探测。随机搜索( r a n d o ms e a r c h ) 是一个注重探测搜索空间而 忽视挖掘最优解的典型例子。遗传算法则是在总体上寻求挖掘和空间探测之间平 衡的一类算法。 遗传算法是一类可用于复杂系统优化计算的鲁棒搜索算法。与其他一些优化 算法相比，它主要有下述几个特点，： ( 1 ) 遗传算法以决策变量的编码作为运算对象( 函数优化中有时也采用决策 变量本身作为运算对象，可以视为简单的代数编码) 。传统的优化算法往往直接利 用决策变量的实际值本身来进行优化计算，但遗传算法不是直接以决策变量的值， 而是以决策变量的某种形式的编码为运算对象。这种对决策变量的编码处理方式， 使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念，可以模仿自 然界中生物的遗传和进化等机理，也使得我们可以方便地应用遗传操作算子。特 别是对一些无数值概念或很难有数值概念，而只有代码概念的优化问题，编码处 理方式更显示出了其独特的优越性。 ( 2 ) 遗传算法直接以目标函数值作为搜索信息，并不利用梯度信息，无需求 导运算。传统的优化算法不仅需要利用目标函数值，而且往往需要目标函数的导 数值等其他一些辅助信息爿能确定搜索方向。而遗传算法仅使用由目标函数值变 浙江人学硕七学位论文 换来的适应度函数值，就可确定进一步的搜索方向和搜索范围，无需目标函数的 导数值等其他一些辅助信息。这个特性对很多目标函数是无法或很难求导数的函 数，或导数不存在的函数的优化问题，以及组合优化问题等，应用遗传算法时就 显得比较方便。因为它避开了函数求导这个障碍。再者，直接利用目标函数值或 个体适应度，也可使得我们可以把搜索范围集中到适应度较高的部分搜索空间中， 从而提高了搜索效率。 ( 3 ) 遗传算法同时使用多个搜索点的搜索信息，是一种群体优化过程。传统 的优化算法往往是从解空间中的一个初始点丌始最优解的迭代搜索过程。单个搜 索点所提供的搜索信息毕竟不多，虽然搜索效率较高，但容易使搜索过程陷于局 部最优解而停滞不的。遗传算法从由很多个体所组成的一个初始群体开始最优解 的搜索过程，而不是从个单一的个体开始搜索。对这个群体所进行盼选择、交 叉、变异等运算，产生出的乃是新一代的群体，在这之中包括了很多群体信息。 这是遗传算法所特有的种并行性。 ( 4 ) 遗传算法使用概率搜索技术。很多传统的优化算法往往使用的是确定 性的搜索方法，一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系， 这种确定性往往也有可能使得搜索永远达不到最优点，因而也限制了算法的应用 范围。而遗传算法属于种自适应概率搜索技术，其选择、交叉、变异等运算都 足以一种概率的方式束进行的，从而增加了其搜索过程的灵活性。虽然这种概率 特性也会使群体中产生一些适应度不高的个体，但随着进化过程的进行，新的群 体中总会更多地产生出许多优良的个体，实践和理论都已证明了在一定条件下遗 传算法总是以概率1 收敛于问题的最优解。当然，交叉概率和变异概率等参数也 会影响算法的搜索效果和搜索效率，所以如何选择遗传算法的参数在其应用中是 一个比较重要的问题。而另一方面，与其它一些算法相比，遗传算法的鲁棒性又 会使得参数对其搜索效果的影响会尽可能地低。 1 4 遗传算法理论研究综述 遗传算法理论研究内容主要有以下几个方面“”1 ：分析遗传算法的编码策略； 全局收敛性和搜索效率的数学基础；遗传算法的新结构研究；基因操作策略及其 性能研究；遗传算法参数的选择；与其它算法的综合的比较研究等。 i 4 1 模式分析 h o l l a n d 首先用模式定理”h 解释”了遗传算法的搜索行为，该研究成果奠定 第一章遗传算法坝究概述 了遗传算法的数学理论基础“。根据隐并行性得出每一代处理有效模式的f 限值 ”2 0 1 是n 2i ( c ，_ ”) ，其中为群体大小，是符号串编码长度，g 是小整数，一 些研究”把结果简化为o ( n 3 ) ，这是遗传算法能够有效搜索的根本原因之所在。 b e r t o n i 和d o r i g o ”“推广了此项研究，并获得了n = 2 斟，给出p 为任意值时处理 多少有效模式的表达式。每代遗传会产生多少新模式也是说明g a 效率的重要特 性。怦为民和席裕庚“。7 给出了每代至少产生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 ”首先察觉到了一 种常使g a 从全局最优解发散出去的问题，称为g a 一欺骗( g a d e c e d t i r e ) 问题。 o o l d b e r g ”首先运用w a l s h 模式转换法设计出了最小g a 一欺骗问题并进行了详细 分析。目前，g a 一欺骗问题的研究主要集中在3 个方面：设计欺骗函数；理解欺 骗函数对g a 的影响；修改g a 以解决欺骗函数的影响。 1 9 9 0 年代中后期，一些学者对模式定理的正确性提出了质疑。马丰宁”73 通过 测试黎曼函数和相应的理论分析，指出模式定理推导中的错误，并提出了新模式 定理：张铃等”也得出类似的结论，并对模式定理进行了修正；g r e f e n s t e t t e ”3 指出模式定理不能保证适应度变换的唯一眭：m u m e n b e ir l m 指出了模式定理中计 算模式适应度中存在的问题：r a d c l i f f e 。“3 ”通过对模式定理的分析，指出遗传算 法并不总e e 随机搜索算法好；v o s e 。等也论述了模式定理中存在的一些问题。 尽管大量的成功实际应用支持了模式定理所依赖的积木块假设，但至今还没 有一种方法用束判别“对于一个给定的问题，积木块假设是否成立”。 1 4 2m a r k o v 链分析 生物进化的“趋势向上”性似乎蕴含着遗传算法的最终收敛性，但还须从理 论上对这一事实给予证明。“遗传算法是全局收敛的”这一结论主要是根据 h o l l a n d 的模式定理得出的，事实上这一结论普遍受到怀疑并引起争论，修正后 的模式定理已经不能说明这一观点。 近几年，遗传算法全局收敛性分析取得了突破性进展“”。o o l d b e r g 和 s e g r e s t 首先使用m a r k o v 链分析了一个极为简单的遗传算法的性能；e i b e n 等用 m a r k o v 链证明了一类基于保留最优个体的抽象g a 的全局收敛性：f o g e l 等分析了 没有变异算子的g a 的渐近收敛性；s u z u k i 用m a r k o v 链状态转移矩阵的特征根分 浙江人学硕十学位论文 f j i 了，g a 的收敛行为；q i 和p a l m i e r i 基于m a r k o v 链对浮点数编码的遗传算法进 ir 严密的数学分析，但其分析基于群体无穷大这一假设：p d u o p h 用齐次m a r k o v 链证明了标准遗传算法收敛不到全局最优解，若采用保留最优个体的选择机制， 则改进的g a 全局收敛：王丽薇等用类分析方法分析了g a 的收敛性；李书全等用 随机泛函分析证明了保留最优个体g a 的全局收敛性：田军用m a r k o v 链和随机撮 动理论证明了g a 进入最小能量集的条件；粱艳春等用m a r k o v 链研究了基于扩展 串的等价遗传算法的收敛性；张讲社等o ”1 提出了一类非齐次、保证收敛且容易判 断是否收敛的新型g a ，证明了算法收敛的充要条件。该算法收敛速度快，有较强 的避免早熟的全局优化能力，具有合理的停机标准。 以上这些研究成果，要么基于群体无穷大这一假设( 破坏了g a 实现的可能 性) ，要么基于分析简单化的或特殊的g a ，要么实际应用中的可操作性太差，但 文献 3 5 的研究成果是值得借鉴的。尽管如此，一般遗传算法的收敛性分析以及 如何构造一个收敛的遗传算法，仍是这一领域亟待解决的重要理论问题。 上述的收敛性分析都是建立在计算时间趋于无穷这一条件上。事实上遗传 算法的计算复杂性问题是实际应用中更为关心的问题。b a e c k ，m u m a n b e i n 和a s o h 等对简化的遗传算法进行了计算复杂性研究；恽为民等基于m a r k o v 链对此做了粗 略的分析：n i w a 等基于群体遗传学中的w r i g h t f is h e r 模型，使用扩散方程对此 进行了分析。最近，a y t u g 和k o e h l e r 等基于有限群体下的m a r k o v 模型，通过引 入置信水平得出了遗传算法达到置信水平时算法迭代次数的上下限。尽管研究 成果在实际应用中存在概率转移矩阵过大，以致难以计算等缺点，但他们的分析 思路是值得借鉴的。 1 4 3 其他应用于g a 的理论分析工具及方法 i 4 3 1 维数分析 因为使用m a r k o v 链无法判断遗传算法中控制参数的重要性，所以一些学者。”1 采用了维数分析的方法。维数分析来源于工程科学，它试图辨识一个复杂系统中 的重要因素( 维数) ，并在它们之间建立函数关系。当使用维数分析来分析遗传算 法时，选择、交叉和变异算子等因素被放到各自的函数关系中。可以说，这些函 数关系是一种“猜测”的结果，并且必须通过模拟来判断这些函数关系的有效性。 这种分析思路有助于遗传算法的研究。 第一章遗传算法研究概述 1 4 3 2b g a 理论 m u h l e n b e i n 和s c h l i e r k a m p ”根据数量遗传学，构造出一种特殊的遗传算法 复制遗传算法( b r e e d e rg e n e t i ca 1 9 0 r i t h m ，简称b g a ) ，并受到广泛的关 注。因为它提供了一套完整的理论框架，证明了b g a 在求解多峰函数时的计算复 杂性为o ( n i n n ) ，分析过程是基于球形对称和群体无穷大这两个假设。事实上， 当变异概率较小时，b g a 理论所依赖的旋转不变性并不成立，从而使得球形对称 假设也不成立。这时所有变量相互依赖，算法仅沿着坐标轴方向搜索，从而导致 算法的计算复杂性变为o ( n “) ，比随机搜索算法的计算复杂性o ( e “) 高得多。 1 4 3 3 可分离函数 文献 1 1 分析了当变异概率l a 。= 1 时( n 为群体大小) ，遗传算法求解所 有可分离函数的计算复杂性为o ( n i n n ) 。所谓函数可分离，即函数满足就： ，( x ) = f ( x ) ( 11 ) 根据这一定义，目| i 的测试函数大部是可分离函数。试验表明，如果变量x 相互 独立，遗传算法将有较好的性能。文献 3 8 将这种方法推广到浮点数编码的遗传 算法中，分析表明，在连续函数的优化过程中，采用浮点数编码i ；k - - 进制编码的 遗传算法性能更好，因为二进制编码增加了算法的复杂性。 1 4 3 4w a l s h 函数分析 傅立叶，w a l s h 和h a r t 函数都是正交函数，被应用于构造g a 难易问题和欺 骗问题，其中w a l s h 变换在遗传算法的分析中扮演着重要的角色。b e t h k e ”“运用 w a l s h 函数和模式转换发展了这种有效的分析方法。b a r i o s 通过w a l s h 级数分析， 证明了对于欺骗问题g a 收敛的充分条件，给出了欺骗问题的严格定义。另有一些 学者针对欺骗问题，从应用的角度构造出一些有效的算法“”。尽管如此，“欺骗性” 仍然遭到严厉的批评。g r e f e r s t e t t e 认为欺骗性定义是以静态超平面分析这一错 误的假设为基础的，它不是引起g a 一难的根本原因；l i e p i i 2 s 和v o s e 指出，可以 0浙江人学硕十学何论文 通过一个简单的变换将所谓的完全欺骗问题转化为个c a 一易问题。 研究欺骗问题是为了预测遗传算法求解给定问题时的难易程度。如果一个问 题满足积木块假设，用遗传算法求解效率就高；否则，效率就低。目前尚无法判 定一个问题包含欺骗的多少与问题相对于遗传算法的难易程度，因为影响遗传算 法效率的因素尚不十分清楚。 【4 3 5 傅立叶分析 k o s t e f s 等”使用傅立叶函数来分析遗传算法，建立了一套完整的分析框架。 他们将遗传群体看作一个概率分析，其实质是认为群体无穷大，通过跟踪群体分 布在遗传算子作用下的变化情况来研究遗传算法的进化过程。k o s t e r s 重新定义 了，遗传算子，分析了基函数的期望值和目标函数期望值在遗传算子作用下的变化 悄况，推导出对任意可测函数下的w a l s h 模式变换，并通过模拟试验进行了验证。 k o e h l e r 等将上述结论推广到非二进制编码的遗传算法分析中。受上述研究成果 的启发，我们自然想到可否采用小波分析理论来研究遗传算法? 这是一个值得深入 研究的问题。 1 4 3 6 二次动力系统 二次动力系统( q u a d r i cd y n a m i cs y s t e m ，简称q d s ) 模型常被用于刻画生 物界和物理界中的自然现象。如果假设群体无穷大，那么可将遗传算法看作一个 q t ) s ”。1 。由于q d s 的模拟是一个p a p a c e c o m p l e t e ，所以它不是一种有效的分析 与法“。目前，基于q d s 的研究主要分析了系统的待征根和稳定性。一般说，只 有当群体规模很大时，基于q d s 的预测才会有较好的精度。 1 4 4n of r e el u n c h 定理 遗传算法的基础理论研究至今还没有取得突破性进展，理论与应用之间还存 在着很大的差距。最近，s t a n f o r d 大学w o l p e r t 和m a c r e a d y 教授提出了n of r e e l u n c h ( 简称n f l ) 定理“，它是优化领域中的一个重要理论研究成果，其意义极 为深远。现将其结论概括如下。 第一章遗传算法研究概述 1 4 4 1 定理描述 定理1 1 ( n of r e el u n c ht h e o r e m ) 假定有a 、b 两种任意( 确定或随机) 算法，对于所有问题集，它们的平均性能是相同的( 性能可采用多种方法度量， 如最优解、收敛速率等) 。即： p ( 6i 厂，n ，爿) = p ( 6l 厂，n ，b ) ( 1 2 ) 了了 其中，为个体适应度的概率曲线，厂为适应度函数，为群体大小。n f l 定理 的证明可参见文献 3 4 。对于上述结论，r a d c l i f f 和s u r r y 也有相同的结论。例 如，如果g a 求解问题集a 时的性能比模拟退火的性能好，那么必然会有模拟退火 求解问题集b 时的性能比g a 的性能好。平均所有的情况，两种算法的性能是相同 的。因此说没有哪种算法比随机搜索算法更好。 根据n f l 定理，算法性能“好”与“坏”不仅与一定的问题有关，而且与个 体适应度的概率曲线c 有关。显然，只要知道c ，就可评价算法性能的好坏。由 此可见，不应盲目地将遗传算法应用到任何问题的求解中。 1 4 4 2n f l 定理在g a 方面的推论 在g a 的应用研究方面，研究者在开始总是尝试设计出一种改进的新型g a 以 期在各个方面的取得较好的应用效果。不仅在应用上，还有人试图从理论上给出 这种可以在应用于各种问题的g a 存在的依据。 通过对n f l 定理的分析可以得出如下有益的推论： 推论1 1 不存在一种g a ，可以使其对于任意问题的算法性能优于一种给定 的g a 算法。 推论1 2 对于任意给定的一类问题p ( 们，存在一种g a ，使得这种g a 的 算法性能优于随机搜索算法的性能。 上述推论都是以算法性能为比较对象的，我们可以把算法性能具体到计算复 杂性方面，同样可以得到类似的结论。 以上推论说明：只有针对某一类或者某几类问题来设计一种算法性能优异的 g a ，才是可行的，而且在理论上也是存在。因而，g a 的以后的一个研究方向就是 针对具体问题设计有针对性的遗传算法。 浙江人学硕十学位论文 1 5 遗传算法应用研究综述 遗传算法提供了种求解复杂系统优化问题的通用框架，它不依赖于问题的 h 体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科“”1 。下面 是遗传算法的一些主要应用领域： ( 【) 函数优化。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性 能评价的常用算例。很多人构造出了各种各样的复杂形式的测试函数，有连续函 数也有离散函数，有凸函数也有凹函数，有低维函数也有高维函数，有确定函数 也肓随机函数，有单峰值函数也有多峰值函数等。用这些几何特性各具特色的函 数求评价遗传算法的性能，更能反映算法的本质效果。而对于一些非线性、多模 型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法都可以方便 地得到较好的结果。 ( 2 ) 组合优化。随着问题规模的增大，组合优化问题的搜索空间也急剧扩大， 仃时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复 杂问题，人们己意识到应把主要精力放在寻求其满意解上，而遗传算法是寻求这 种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的n p 完全问题非 常有效。例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划 分问题等方面得到成功的应用。 ( 3 ) 生产调度问题。生产调度问题在很多情况下所建立起来的数学模型难以精 确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结 果与实际相差甚远。而目前在现实生产中也主要是靠经验进行调度。现在遗传算 法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间 调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。 ( 4 ) 自动控制。在自动控制领域中，很多与优化相关的问题需要求解，遗传算 法已在其中得到了初步的应用，并显示出了良好的效果。例如用遗传算法进行航 空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控 制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学 习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等，都显示出了 遵传算法在这些领域中应用的可能性。 ( 5 ) 机器人学。机器人是类复杂的难以精确建模的人工系统，而遗传算法的 起源就来自于对人工自适应系统的研究，所以机器入学理所当然地成为遗传算法 的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人 运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面 第一章遗传算法研究概述 得到研究和应用。 ( 6 ) 图像处理。图像处理是计算机视觉中的个重要研究领域。在图像处理过 程中，如扫描、特征提取、图像分割等不可避免地会存在一些误差，这些误差会 影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要 求。遗传算法在这些图像处理中的优化计算方面找到了用武之地，目前已在模式 识别、图像恢复、图像边缘特征提取等方面得到了应用。 ( 7 ) 人工生命。人工生命是用计算机、机械等人工媒体模拟或构造出的具有自 然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大主 要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究 人工生命现象的重要基础理论。虽然人工生命的研究尚处于启蒙阶段但遗传算 法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应 用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成， 遗传算法为人工生命的研究提供了个有效的工具，人工生命的研究也必将促进 遗传算法的进一步发展。 ( 8 ) 遗传编程。k o z a 发展了遗传编程的概念，他使用了以l i s p 语言所表示的 编码方法，基于对一种树型结构所进行的遗传操作来自动生成计算机程序。虽然 遗传编程的理论尚未成熟，应用也有一些限制但它已成功地应用于人工智能、 机器学习等领域。 ( 9 ) 机器学习。学习能力是高级自适应系统所应具备的能力之一。基于遗传算 法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算 法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进 了模糊系统的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权， 也可用于人工神经网络的网络结构优化设计：分类器系统也在学习式多机器人路 径规划系统中得到了成功的应用。 1 6 本文主要内容 本文由以下六章组成： 第一章为遗传算法研究概述，简单介绍了g a 的生物学基础、发展历程和特点， 并对当前g a 的理论和应用研究现状作了综述。 第二章主要写g a 的基础知识，包括一般遗传算法的数学描述、算法流程、g a 模式定理和m a r k o v 链的特性。这些是后续各章在理论方面证明的的基础。 第三章就算法的收敛性作出分析，在回顾了已有的几个典型的收敛性定理之 后，提出一个统一的收敛标准，易于在设计新的遗传算法时，判断其收敛性。而 4 浙江人学硕十学位论文 小不需要大规模计算。 第四章就二进制、格雷码、两种编码方式作出对比分析，从数学的角度分析 r 不同编码方式对算法寻优搜索过程的影响。并给出了不同编码方式下，个体差 异和编码差异问的关系。 第五章首先给出变异算子的机理