（管理科学与工程专业论文）遗传算法适应值曲面及遗传算法困难度分析.pdf

摘要 遗传算法作为- , e e 搜索寻优技术，已经在许多领域得到了成功的应用。然而 n f l 定理的提出，使遗传算法的应用受到了冲击，于是对遗传算法困难度的分 析便提上了日程。另外，起源于生物学中的概念“适应值曲面”已成功地应用到 了遗传算法中，成为描述适应值空间特征和分析遗传算法性能的重要工具。本文 就是在这种背景下，对遗传算法适应值曲面理论进行了探讨，并基于适应值曲面 对遗传算法的困难度进行了分析，提出了若干种测试遗传算法困难度及解决遗传 算法困难问题的方法。本文的主要研究内容如下： 1 回顾了遗传算法的发展历史，总结了遗传算法的特点，分析了遗传算法 理论与应用研究的现状，并指出了当前需要解决的系列问题：讨论了适应值曲面 概念的起源，并分析了适应值曲面的应用状况；阐述了遗传算法困难度研究的背 景、历程和现状。 2 阐述了遗传算法适应值曲面的概念，及其在遗传算法研究中所起的作用。 从图论的角度对遗传算法适应值曲面进行了分析，描述了适应值曲面上的随机游 走相关函数，详细推导了相关长度计算公式。对适应值曲面上的随机游走模型进 行了时间序列分析，以获得关于适应值曲面的更多的信息，并基于n k 一适应值曲 面进行了实证研究。提出了模式适应值曲面的概念，并对模式适应值曲面进行了 统计分析。对动态适应值曲面进行了初步分析。 3 论述了n f l 定理，并分析了遗传算法困难度研究的意义。详细阐述了遗 传算法欺骗问题中的各种定义及定理，描述了模式欺骗对遗传算法困难度的影 响。利用w a l s h 模式变换对遗传算法基因关联问题进行了分析，并对连续函数优 化问题的基因关联阶数进行了估计。同时对基因关联进行了统计分析，讨论了基 因关联方差及基因关联相关系数，归纳出两个定理并给予了严格的数学证明。阐 述了几个常见的基因关联问题。对影响遗传算法困难度的其它问题( 函数的多模 态、适应值曲面的崎岖度、遗传算子的选择、早熟问题、遗传参数的控制等) 进 行了系统研究。 4 对常见的几种遗传算法困难度测试方法( f d c 测试、相关长度测试与基 因关联测试法) 进行了分析比较。提出了一种排序统计分析方法，可以直接测试 适应值曲面的特征，从而进一步反映遗传算法对该问题优化的困难程度。提出利 用分形理论来分析遗传算法适应值曲面，并提出基于随机游走模型对适应值曲面 进行关联维数测试，以反映适应值曲面的复杂程度。针对传统的测试基因关联的 方法只能给出染色体中所有基因位的整体关联程度的情况，通过在模式适应值曲 面上分别进行相关长度测试和基因关联测试，以研究染色体中一些特定位之间的 基因关联程度。对实数编码遗传算法困难度的测试方法进行了分析，提出了一阶 函数逼近测试法。同时基于进化动力统计分析对遗传算子的性能进行了测试。 5 讨论了几种遗传算法困难问题构造方法。分析了几种常见的改进遗传算 法结构的方法，以提高遗传算法的性能。提出了一种动态排序编码方法，以提高 交叉算子的效率。然后对欺骗问题的检测方法进行了举例分析，并提出了一种有 效克服欺骗问题的遗传算法。最后，基于适应值曲面分析及困难度测试设计了遗 传算法的决策支持系统框架。 关键词：遗传算法，适应值曲面，困难度分析，模式欺骗，基因关联 a b s t r a c t g e n e t i c a l g o r i t h m s ( g a s ) ，a s ak i n do fh e u r i s t i cs e a r c ha n d o p t i m i z a t i o n t e c h n i q u e s ，h a v eb e e na p p l i e d t om a n yd o m a i n ss u c c e s s f u l l y h o w e v e r , a f t e r “n of r e e l u n c h ”( n f l ) t h e o r e m sw e r ep r o p o s e d ，a p p l i c a t i o n so fg a s w c r c i m p a c t e d t h e r e f o r e ， t 1 1 es t u d yo ng a h a r d n e s sh a sb e e np a i dm o r ea n dm o r ea t t e n t i o n i na d d i f i o n t h e c o n c e p t ，“f i t n e s sl a n d s c a p e s ”，w h i c hc a r l a ef r o mb i o l o g y , h a sb e e na p p l i e dt og a s ， a n db e c a m ea ni m p o r t a n tt o o l t od e s c r i b et h ec h a r a c t e r i s t i c so f t h ef i t n e s ss p a c ea n dt o a n n y z e t h e p e r f o r m a n c e o fg a s u n d e rt h i sc i r c u m s t a n c e s w ed i s c u s s e dt h e p r i n c i p l e s o ff i t n e s sl a n d s c a p e so fg a s a n da n a l y z e d 吐l eg a h a r d n e s sb a s e do n f i t n e s s l a n d s c a p e s f u r t h e r m o r e w e p r o p o s e d s e v e r a lm e t h o d st om e a s u r e g a h a r d n e s s o rt os o l v es o m ed i 佑c u l tp r o b l e m sf o rg a s t h em a i nc o n t e n t so f t h i sd i s s e r t a t i o na r ea sf o l l o w s ： 1 w er e v i e w e dt h eo r i g i na n d d e v e l o p m e n to fg a s s u m m a r i z e dc h a r a c t e r i s t i c s o f g a s a n a l y z e dt h er e s e a r c hs t a t u sa b o u tt h ep r i n c i p l e sa n da p p l i c a t i o n so f g a s a n d f u r t h e rp o i n t e do u ts o m e p r o b l e m s ，w h i c hn e e d e dt ob es o l v e dc u r r e n t l m e a n w h i l e ， w ep r o b e di n t ot h e o r i g i no ft h e n o t i o n “f i t n e s sl a n d s c a p e s ”a n dd i s c u s s e di t s a p p l i c a t i o n s t a t u s w ea l s o a n a l y z e dt h eb a c k g r o u n d d e v e l o p m e n t a n d c u r r e n t s i t u a t i o no f t h es t u d yo ng a - h a r d n e s s 2 w ei n v e s t i g a t e dt h ep r i n c i p l e so ft h ef i t n e s sl a n d s c a p ea n di t sa p p l i c a t i o nt o g a si n d e t a i l f i r s t l y , f r o m t h ev i e w p o i n to fg r a p ht h e o r y , w ea n a l y z e df i t n e s s l a n d s c a p e s ，a n dd e s c r i b e dt h er a n d o m w a l kc o r r e l a t i o nf u n c t i o n ，t h e nw ed e d u c e dt h e e q u a t i o nt oc o m p u t et h ec o r r e l a t i o nl e n g t h s e c o n d l y , w ep e r f o r m e dt h et i m es e r i e s a n a l y s i s f o rt h er a n d o mw a l km o d e lo nt h ef i t n e s s l a n d s c a p et o d i s c o v e rm o r e i n f o r m a t i o na b o u tt h ef i t n e s sl a n d s c a p e ，a n dd e m o n s t r a t e dt h e m o d e l i n gp r o c e s sb a s e d o nt h en k l a n d s c a p e s 1 1 1 i r d l y , w ep r o p o s e dt h ec o n e ( ：p to ft h ef i t n e s sl a n d s c a p eo f s c h e m a t a ，a n di m p l e m e n t e ds t a t i s t i c a la n a l y s i sf o rf i t n e s sl a n d s c a p e so fs c h e m a t a l a s t l y , t h ed y n a m i cf i t n e s sl a n d s c a p ew a sa n a l y z e di nb r i e f 3 w ji d e n t i f i e ds o m ef a c t o r sw h i c h m a y c a u s eg a - h a r d n e s s a tt h eb e g i n n i n g w ed i s c u s s e dt h en f lt h e o r e m sa n dt h e i rs i g n i f i c a n c eo f t h es t u d yo ng a - h a r d n e s s s u b s e q u e n t l y , w e c o n c l u d e ds o m e i m p o r t a n t d e f i n i t i o n sa n dt h e o r e m sf o rg a d e c e p t i v ep r o b l e m s ，a n da n a l y z e ds c h e m ad e c e p t i v e n e s s i n f l u e n c eo ng a h a r d n e s s t h e n ，w ei n v e s t i g a t e dt h ee p i s t a s i so fg a su s i n gw a i s h - s c h e m at r a n s f o r m a n d f u r t h e re v a l u a t e dt h e e p i s t a s i s o r d e rf o rt h ec o n t i n u o u sf u n c t i o n o p t i m i z a t i o n p r o b l e m s m e a n w h i l e f o rt h es t a t i s t i c a la n a l y s i sm o d e lo fe p i s t a s i si n t r o d u e e db y d a v i d o r , w ed i s c u s s e de p i s t a s i sv a r i a n c ea n de p i s t a s i sc o r r e l a t i o n ，a n df u r t h e ri n d u c e d t w ot h e o r e m s ，o fw h i c hw eg a v es t r i c tm a t h e m a t i cp r o o f a d d i t i o n a l l y , s e v e r a lt e s t p r o b l e m sw i t he p i s t a s i sf o rg a s w e r ed e s c r i b e d f i n a l l y , w es t u d i e ds y s t e m a t i c a l l y s o m eo t h e rr e a s o n sf o rg a h a r d n e s s ，s u c ha sm u l t i m o d a lf u n c t i o n s ，t h em g g e d n e s s o ff i t n e s sl a n d s c a p e s ，s e l e c t i o no f g e n e t i co p e r a t o r s ，p r e m a t u r ep r o b l e m s ，c o n t r o lo f g e n e t i cp a r a m e t e r s ，e t c 一 4 w ep r o b e di n t os o m em e t h o d st om e a s u r eg a h a r d n e s s f i r s to fa 1 1 w e c o m p a r e dt h r e ea p p r o a c h e s ：f d c ，c o r r e l a t i o nl e n g t h ，a n de p i s t a s i sm e a s u r e s n e x t ， w ep r o p o s e dt h em e t h o do ff i t n e s ss e q u e n c es t a t i s t i c sa n a l y s i s ，t od i r e c t l ye x p l o r e c h a r a c t e r i s t i c so ff i t n e s sl a n d s c a p e s ，a n dt of u r t h e rm e a s u r et h ee x t e n to fg a h a r d n e s s w ea l s oi n t r o d u c e dt h ef r a c t a lt h e o r yt os t u d yf i t n e s sl a n d s c a p e s ，a n da n a l y z e dt h e c o m p l e x i t yo f f i t n e s sl a n d s c a p e sb yc o m p u t i n gt h ec o r r e l a t i o nd i m e n s i o nb a s e do n r a n d o mw a l kf i t n e s st i m es e r i e s b e c a u s et r a d i t i o n a le p i s t a s i sm e a s u r em e t h o d sc a n o n l yr e f l e c tt h ee x t e n to fi n t e r a c t i o nb e t w e e na l lg e n e si nt l l ec h r o m o s o m e w eu s e d c o r r e l a t i o n l e n g t ha n a l y s i sa n de p i s t a s i sm e a s u r e so nt h ef i t n e s sl a n d s c a p e s o f s c h e m a t at ot e s tt h ee x t e n to fi n t e r d e p e n d e n c eb e t w e e ns o m ec e r t a i ng e n el o c ii n s t u d y i na d d i t i o n w ef o r m u l a t e dm e a s u r e so f g a h a r d n e s sf o rg a sw i t hr e a l v a l u e d e n c o d i n g a n da d v a n c e d t h em e t l l o do ft h ef i r s to r d e rf u n c t i o na p p r o x i m a t i o n a tl a s t ， b a s e do nt h er o o d a lo fg a d y n a m i c s ，t h ep e r f o r m a n c eo fg e n e t i co p e r a t o r sw a s a n a l y z e d 5 i nt h el a s ts e c t i o n s e v e r a lm e t h o d sf o rc o n s t r u c t i n gf u n c t i o n sw i t hd i f i e r e n t d e g r e e s o fg a h a r d n e s sw e r ec o n c l u d e d f i r s t l y t h e n w ed i s c u s s e dd i f i e ：r e n t a p p r o a c h e st oi m p r o v i n gt h e s t r u c t u r eo fg a sf o rd i f f e r e n to p t i m i z a t i o np r o b l e m s f u r t h e r m o r e ，w ep r o p o s e dd y n a m i cr a n k i n ge n c o d i n gt oe n h a n c e t h ep e r f o r m a n c eo f c r o s s o v e r w ea l s oi l l u s t r a t e dh o wt oe x a m i n eg a d e c e p t i v ep r o b l e m s ，a n dd e s i g n e d a g at oo v e r c o m ed e c e p t i o ne f f e c t i v e l y i nt h ee n d ，a c c o r d i n gt ot h es t u d yo nf i t n e s s l a n d s c a p e s a n dg a h a r d n e s s ，w ed e s i g n e dt h ee l e m e n t a r ys t r u c t u r eo fd e c i s i o n s u p p o r ts y s t e m so fg a s f o rs t a t i cf i 恤e s sl a n d s c a p e sa n dd y n a m i cf i t n e s sl a n d s c a p e s r e s p e c t i v e l y k e y w o r d s ：g e n e t i ca l g o r i t h m s ，f i t n e s sl a n d s c a p e s ，g a h a r d n e s s ， s c h e m a d e c e p t i v e n e s s ，e p i s t a s i s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得盘鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名- 爹二2 二多字日期：力。1 年猬日 学位论文版权使用授权书 本学位论文作者完全了解基壅盘鲎有关保留、使用学位论文的规定。 特授权墨洼盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名名互式 导师签名 签字日期：西，上年工月口e l 签字日期：歹哆年a 月l o 日 天津大学博士论文 第一章绪论 1 1 遗传算法研究概述 1 1 1 遗传算法的发展历史 遗传算法是生物学、计算机科学、人工智能以及系统科学等学科相结合而产 生的一种全局性概率搜索方法，它是人们认识自然、掌握自然规律并用于解决客 观世界实际问题的产物。遗传算法的主要思想来源于达尔文( c d a r w i n ) 的生 物进化论，其中的“自然选择，适者生存”是遗传算法的主要指导原则之一 1 “。 按照孟德尔和摩根( gm e n d e l ，t m o r g a n ) 的遗传学理论【lj ，遗传物质是 作为一种指令密码封装在每个细胞中，并以基因的形式排列在染色体上，每个基 因有特殊的位置并控制生物的某些特性，生物体所表现出来的外在特征是对其染 色体构成的一种体现。生物的进化本质体现在染色体的改变和改进上，生物体自 身形态的变化是染色体结构变化的表现形式，不同的基因组合产生的个体对环境 的适应性不一样，通过基因杂交和突变可以产生对环境适应性强的后代。经过优 胜劣汰的自然选择，适应值高的基因结构就得以保存下来，从而逐渐形成了经典 的遗传学染色体理论，揭示了遗传和变异的基本规律。在定的环境影响下，生 物物种通过自然选择、基因交换和变异等过程进行繁殖生长，构成了生物的整个 进化过程。 自然界的生物进化是一个不断循环的过程。在这一过程中，生物群体也就不 断完善和发展。可见，生物进化过程本质上是一种优化过程，在计算科学上具有 直接借鉴的意义t 2 a j 。在计算机技术迅猛发展的时代，生物进化过程不仅可以在 计算机上模拟实现 2 s l ，而且还可以模拟进化过程，创立新的优化计算方法，并 应用到复杂工程领域之中，这就是遗传算法等一类模拟自然进化的计算方法的思 想源泉【2 。以生物进化过程为基础，计算科学学者提出了各种模拟形式的计算 方法。 早在1 9 6 2 年，j o h nh o l l a n d 在发表的论文o u f l i n ef o ral o g i ct h e o r yo f a d a p t i v es y s t e m s ) ) 1 2 j 中提出了利用群体进化的思想。他指出新的群体应当基于当 前群体的有效性来产生。尽管他当时没有给出实现这些思想的具体技术，但确实 引进了群体、适应值、复制、变异、交叉等基本概念。1 9 6 6 年f o g e l 4 i 等人也提 出了类似的思想，但其重点是放在变异算子而不是采用交叉算子，该方法已证明 不如h o l l a n d 提出的使用交叉的方法有效【9 j ，但目前仍在使用。1 9 6 7 年j d b a g l e y 在其博士论文中首次提出“遗传算法”一词i l o j 。 在h o l l a n d 发表论文后的十余年中，从事遗传算法研究的论文开始慢慢出现。 大多数研究都集中在美国m i c h i g a n 大学的h o l l a n d 及其学生当中。因此，遗传算 法大多数著名学者都是m i c h i g a n 学生，如d a v i d g o l d b e r g 、k e n n e t h d ej o n g 、j o h n k o z a 、s t e p a n i ef o r r e s t 等等。d ej o n g 的博士论文【l l 】首次把遗传算法用于函数优 化，并对相关问题进行了较为系统的研究。1 9 7 5 年，h o l l a n d 出版了专著 ( ( a d a p t a t i 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 ) ) l j j ，该书系统地阐述了遗传算法的基 本理论和方法，提出了对遗传算法的理论发展极为重要的模式理论( s c h e m a t h e o r y ) ，其中首次确认了选择、交叉和变异等遗传算子，以及遗传算法的隐并行 性，并将遗传算法应用于适应性系统模拟、函数优化、机器学习、自动控制等领 域。 第一章绪论 1 9 7 5 年之后，遗传算法不但在各个领域得到了广泛应用，而且还丰富和发 展了遗传算法的基本理论。1 9 8 0 年b e t h k e 对函数优化的遗传算法进行了研列”j ， 包括应用研究和数学分析。s m i t h 在1 9 8 0 年首次提出使用变长串的概念【i ”，这 在某种程度上为以后的遗传规划奠定了基础。g o l d b e r g “、d a v i s 4 1 、 g r e f e n s t e t t e 【i ”、b a u e r 【i 、s r i n i v a s 和p a t n a i k 【l7 】等大批研究人员对遗传算法理论 的基本框架和遗传算子进行了构建和改进，并将遗传算法分别应用于工程设计、 自动控制、经济金融、博奕问题、机器学习等诸多领域之中。 1 9 8 5 年是遗传算法发展的重要里程碑，在美国召开了第一届遗传算法国际 会议，即i c g a ( i n t e r n a t i o n a lc o n f e r e n c eo ng e n e t i c a l g o r i t h m s ) 。 1 9 8 9 年，d a v i dg o l d b e r g 出版了( ( g e n e t i c a 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 e l e a r n i n g ) ) 一书【6 】，这是第一本遗传算法教科书，它是对当时关于遗 传算法领域研究工作的全面而系统的总结，因而也成为引用最多的参考书之一。 与h o l l a n d 的著作侧重于适应性系统的进化数学分析不同，本书将遗传算法的基 本原理与广泛的应用实例相结合，并给出了大量可以使用的应用程序。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 f i t h r n s 1 1 4 1 ，其中包括了g a 在工程 技术和社会生活中的大量应用实例。 j o l l i lr k o z a 将遗传算法用于处理不定长树形字符串或一组程序，提出了遗 传规划( g e n e t i cp r o g r a m m i n g ，简称g p ) 的概念 1 8 , 1 9 】。1 9 9 2 年k o z a 教授出版了 第一本遗传规划专著( g e n e t i cp r o g r a m m i n gi 【l8 j ，两年之后又出版了第二本关 于遗传规划的专著”。 从1 9 9 9 年起，i c g a 和g p ( g e n e t i c p r o g r a m m i n gs o c i e t y ) 的系列会议合并 为每年一次的遗传和进化国际会议( g e n e t i ca n de v o l u t i o n a r yc o m p u t a t i o n c o n f e r e n c e g e c c 0 ) 。 在欧洲，从1 9 9 0 年开始也每隔一年举办一次类似的会议，即p p s n ( p a r a l l d p r o b l e ms o l v i n gf r o mn a t u r e ) 会议。以遗传算法理论基础为核心的学术会议f o g a ( f o u n d a t i o n so f g e n e t i c a l g o r i t h m s ) 也从1 9 9 0 年起每隔一年举办一次。 1 9 9 4 年1 月，i e e e 神经网络委员会( i e e en e u r a ln e t w o r kc o u n c i l ) 出版了 第一本“进化计算”专集；1 9 9 4 年6 月，i e e e 神经网络委员会召开第一届“进 化计算”国际学术会议( i e e ei c e c ) ，以后每年召开一次。1 9 9 7 年，该委员会 创办了i e e e t r a n s a c t i o n so n e v o l u t i o n a r y c o m p u t a t i o n 杂志。从1 9 9 9 年开始，i e e e i c e c 与e p 的年会合并为进化计算国际会议( c o n g r e s so ne v o l u t i o n a r y c o m p u t a t i o n ，c e c ) ，每年召开一次。 美国m i t 出版社从1 9 9 3 年开始出版e v o l u t i o n a r yc o m p u t a t i o n 和a d a p t i v e b e h a v i o r 杂志。世界上第一本关于人工智能研究的杂志a it r e n d s 于1 9 9 3 年更名 为c r i t i c a lt e c h n o l o g yt r e n d s ，并在更名启示中讲到：“遗传算法、自适应系统、 细胞自动机、混沌理论和人工智能一样，都是对今后十年的计算机技术有重大影 响的关键技术”。 随着i n t e r a c t 技术的发展和普及应用，遗传算法的有关研究单位建立了大量 的专题g a 网站，其中最为著名的是由美国海军人工智能应用研究中心建立的 g a a r c h i v e s 检索网站( h t t p ：w w w a l c n r l n a v y m i l g a l i s t ) ，它包括了世界范围内 的开展遗传算法和进化计算研究的大学和机构，历年来的可公开发表的论文和报 告，有关国际会议消息，典型应用案例和程序( 源代码) ，等等。 这些众多的研究单位和频繁的国际学术活动集中反映了遗传算法的学术意 义和应用价值。目前，遗传算法己成为一个多学科、多领域的重要研究方向。 天津大学博士论文 1 1 2 遗传算法的特点 遗传算法作为一种启发式搜索寻优技术，之所以受到越来越多人的青睐，在 于它是一种弱方法，具有很强的鲁棒性，即它能适应不同的环境、不同的问题， 并在大多数情况下都能得到比较满意的解。与其它搜索技术( 如梯度搜索技术、 随机搜索技术、枚举技术和其它启发式随机搜索方法等) 相比，遗传算法具有以 下特点【5 7 ，2 0 2 2 1 ： ( 1 ) 遗传算法直接处理的对象是参数的编码集而不是参数本身。因此遗传搜 索过程既不受优化函数连续性的约束，也没有优化函数导数必须存在的要求。通 过搜索编码中的相似性，遗传算法可以有效地处理一类函数。在求解问题时，首 先要确定编码方式。 ( 2 ) 遗传算法的搜索过程是从一群初始点开始搜索，而不是从单一的初始点 开始搜索，这种机制意味着搜索过程可以有效地跳出局部极值点。特别是当采用 有效的保证群体多样性的措施时，遗传算法可以很好地将局部搜索和全局搜索协 调起来，既可以完成极值点领域内解的求精，也可以在整个问题空间实施探索， 从而提高了得到问题全局最优解的概率。 ( 3 ) 遗传算法在搜索过程中使用的是基于目标函数值的评价信息，而不是传 统方法主要采用的目标函数的导数信息或待求解问题领域内知识。遗传算法的这 一特点使其成为具有良好普适性和可规模化( s c a l a b i l i t y ) 的优化方法。 ( 4 ) 遗传算法具有显著的隐并行性i ”j ( i m p l i c i tp a r a l l e l i s m ) 。遗传算法虽然在 每一代只对有限解个体进行操作，但处理的信息量为群体规模的高次方。 ( 5 ) 遗传算法在形式上简单明了，不仅便于与其它方法相结合，而且非常适 合于大规模并行计算机运算，因此可以有效地用于解决复杂的适应性系统模拟和 优化问题。 ( 6 ) 遗传算法具有很强的鲁棒性( r o b u s t n e s s ) ，即在存在噪声的情况下，对 同一问题的遗传算法的多次求解中得到的结果是相似的。遗传算法的鲁棒性在大 量的应用实例中得到了充分的验证。 1 1 3 遗传算法研究的现状 我们把遗传算法研究的现状总结如下： ( 1 ) 收敛性研究 遗传算法的收敛性通常是指遗传算法所生成的迭代种群( 或其分布) 收敛到 某一稳定状态( 或分布) ，或其适应值函数的最大或平均值随迭代趋于优化问题 的最优值【2 4 i 。当前对于遗传算法收敛性的研究成果已经非常丰富。 由于遗传算法下一代种群的状态通常完全依赖当前种群信息。而不依赖于过 去的状态，故可自然地用m a r k o v 链描述，这种方法一直被用于研究不同形式 g a s 的渐近行为。1 9 8 7 年，o o l d b e r g 和s e g r e s t 2 5 首次运用有限m a r k o v 链理论 对遗传算法进行了收敛性分析，e i b e n 等人证明了一类抽象g a s 在e l i t i s t 选择情 况下的收敛情况【2 6 j ，r u d o l p h 用齐次有限m a r k o v 链证明了带有选择、交叉和变 异操作的标准遗传算法收敛不到全局最优解，但是如果让每一代群体中的最佳个 体不参加交叉和变异操作而直接保留到子代，那么遗传算法是收敛的1 2 7 1 。c e r f 等采用摄动理论和m a r k o v 链，对g a s 的渐近收敛特性进行了分析，得出了遗传 算法运行及全局收敛性的一般性结论【2 ”。用m a r k o v 链模型描述遗传算法虽然有 直接、精确的优点，但由于所采用有限状态m a r k o v 链理论本身的限制，该模型 第一章绪论 只能用于描述通常的二进制或特殊的非二进制g a s 。另外，这类方法所得收敛性 一般是指相应的m a r k o v 链趋于某一平稳分布，这与优化中通常所指的收敛性不 同，它并不保证g a s 将一定或以概率l 收敛到问题的全局最优解。再有，相应 m a r k o v 链的状态数( 从而转移矩阵的规模) 通常很大，这使得具体确定、分析 转移阵的性态十分困难( 更不用说具体描述其平稳分布) ，因而对于较大规模的 g a s ，m a r k o v 链分析只能基于遍历性考察而得出相应g a s 收敛性的某些“粗糙” 结论【2 4 1 。 o i 和p a l m i e f i 对浮点数编码的遗传算法，在基于连续空间中群体规模为无 群大这一假设下进行了严密的数学分析【2 9 j 。f o g e l 和s u z u k i 从进化计算的角度对 遗传算法收敛问题进行了研究p ”“。 李书全等采用泛函分析理论证明了遗传算法的收敛性【3 。徐宗本提出了一 个既可用于分析时齐又可用于分析非时齐的公理化模型【2 4 埘】，其核心思想是：通 过公理化描述g a s 的选择算子与重组算子，并利用所引进的参量分析g a s 的收 敛性。 v o s e ，n i x ，l i e p i n s 等采用统计动力学方法，分析了无穷群体下遗传算法的 搜索轨迹和不动点收敛性口5 3 7 】。其核心思想是：用两个矩阵算子分别刻画比例 选择与杂交算子和变异算子的组合算子，通过研究这两个算子不动点的存在性与 稳定性来刻画g a s 的渐近行为。 尽管有关遗传算法收敛性的研究成果非常多，但对于遗传算法的具体应用和 参数设计所能提供的指导信息却非常少。 ( 2 ) 收敛速度估计和时间复杂性分析 与收敛性分析紧密相关的另一基本问题是遗传算法的收敛速度问题。这方面 的研究不仅可从另一侧面来阐明g a s 的收敛性，而且对于建立合适的停止准则 及恰当的度量标准以全面、客观地评判g a s 的各种执行策略有重要意义。然而， 到目前为止，有关g a s 收敛速度与复杂性研究仅有少量特殊的结果。依照这些 结果的具体形式，该方面的工作可以归纳为三类 2 4 】：收敛速度估计、迭代次数 估计与时间复杂性估计。 估计g a s 的收敛速度，根据所采用的分析框架与分析方法，通常要采用不 同的准则。常见的准则有：以种群平均适应值收敛，以发现最优解的概率及趋于 稳态分布的速率等。r a b i n o v i c h 和w i g d e r s o n l 3 8 j 对于一类特殊的组合优化问题： o n e m a x 问题，分析了带比例选择与均匀杂交的二进制g a s ，在演化种群平均适 应值收敛的意义下的收敛速度。s u z u k i 【3 2 j 以包含最优解的种群出现的概率和趋于 1 为准则并假设杂交概率为l ，利用概率转移矩阵的特征值导出了带有修正杰出 选择g a s 的几何收敛速度。v o g e t l 3 9 1 对于种群规模无限的g a s ，分析了当孤立、 重复地应用单个遗传算子( 例如仅杂交算子) 情形演化种群的分布趋于极限分布 的速度。高勇【4 0 】基于简单g a s 的m a r k o v 链模型，通过考察当前迭代种群的概 率分布向量与相应稳态分布向量的全变差距离，研究了简单g a s 的收敛速度。 s a l o m o n 【4 i 】在一定假设的前提下，对可分函数分析了只使用变异算子的杰出选择 型连续g a s 的收敛速度。 迭代次数估计是通过估计在一定准则下g a s 达到收敛所需的迭代次数( 或 界) 来阐明g a s 的收敛速度。c h a k r a b o r t y 和d a s t i d a 一4 2 1 通过引进模式的可靠性 概念，并建立相应的随机可靠性模型，运用可靠性分析方法研究了简单g a s 收 敛的迭代次数。a y t u g 和k o e h l e n m j 在定义g a s 收敛性为在一定置信水平下访问 过所有可能种群状态( 当然包括最优解) 的条件下，利用m a r k o v 链中首次访问 4 天津大学博士论文 时间( f i r s tp a s s a g et i m e s ) 概念，导出了g a s 所需迭代次数的上下界。 时间复杂性估计则从另外一个角度考察收敛速度。a n k e n b r a n d t 4 4 l 进了适 应值比率( t h ef i t n e s sr a t i o ) 的概念并假设其不变，在导出了关于某一分量取特 定值的比率之递推公式之后，给出了g a s 达到收敛所需时间的表达式及相应的 平均、最坏情形时间复杂性估计。a s o h 和m u h l e n b e i n 4 5 1 在不考虑选择和变异的 作用的前提下，就简单抽样与均匀杂交这两个特殊情况，给出了计算g a s 平均 收敛时间的公式。l o u i s 和r a w l i n s l 4 6 j 以种群的平均h a m m i n g 距离为度量，仅考 虑选择算子的情况下，分析了g a s 收敛时间界的估计问题。s m o m o n 【4 l 】分析了只 带变异的杰出选择型连续g a s 对于可分适应值函数优化时的时间复杂性估计。 然而，目前已有的关于遗传算法收敛速度与复杂性的结果几乎全部局限于二 进制情形，而且或是对特殊的适应值函数、或是对仅使用某一个或某两个遗传算 子操作情形的g a s 。所使用的度量准则也各不相同，因此这些方法均存在一定的 局限性。 ( 3 ) 遗传策略研究与设计 为了提高遗传算法的效率，g a s 必须采用适宜的运算形式，这就是遗传策略 ( g e n e t i cs t r a t e g y ) 研究与设计的主要内容。h o l l a n d 在早期研究中将群体结构适 应性改变方法称为遗传计划( g e n e t i cp l a n ) 。遗传策略可以分为微观遗传策略 ( m i c r o g e n e t i cs t r a t e g y ) 和宏观遗传策略( m a c r 0g e n e t i cs t r a t e g y ) s l 。 遗传算法的微观遗传策略主要讨论编码方式、群体规模、遗传算子的形式和 参数设计，及其对g a s