（计算数学专业论文）遗传算法的一些改进及其应用.pdf

摘要 摘要 科学理论研究与实践中，往往存在着这样一类问题，就是需要在众多的方案 中确定最优方案的标准，并且给出寻找最优方案的方法，此类问题就称为优化问 题。目前对于一些简单的情况，科学工作者已经研究出了比较成熟的算法和方法。 但是，对于一些复杂的系统，他们往往感到力不从心，努力寻求更加有效的方法。 2 0 世纪4 0 年代以来，学者注意到生物在自然演化过程中表现出强大的适应 能力，生物不断复制优势遗传基因，改善群体的适应性，得到具有很强适应性的 优良物种。遗传算法正是建立在自然演化系统理论研究基础之上的一类优化方 法。作为一类有效的全局优化搜索算法，遗传算法具有以下特点：( 1 ) 使用群体 搜索技术，具有隐含并行性，提高了算法的运行效率；( 2 ) 使用基于目标函数值 的评价信息，不需要目标函数的代数表达式；( 3 ) 具有很强的稳定性，提高了结 果的可信度；( 4 ) 简单通用，便于与其他方法结合成混合算法。 但是，遗传算法的局部搜索能力不强。即便依靠强的全局收敛性可以很快地 达到最优解附近，搜索到最优解也要花很长时间。造成上述现象的主要原因在于 子代不断继承父代的基因，降低了群体的多样性程度，使得算法易于陷入局部收 敛。为充分利用遗传算法的优势、避开其缺陷、加快收敛速度，除了设计科学合 理的基本操作算子、选取适合的参数之外，一个有效的方法就是采用混合策略。 也就是在遗传进化的过程中引入快速收敛的局部寻优算法，构成混合遗传算法。 国外研究人员在提高遗传算法的局部搜索能力、加快寻优速度方面取得了显 著的成果( a l l e ng a r d n e rb ，m i c h a e lss ，2 0 0 3 ) ，( k u r t ah ，j o h ne d d y ，k e m p e r el ，2 0 0 2 ) ，( g h a s e m imr ，h i n t o ne ，w o o drd ，1 9 9 9 ) 。国内研究人员对遗 传算法与可变容差法、模拟退火法等的混合算法进行了研究，也在许多不同领域 的应用获得了重要的成果。m j b o x 于1 9 6 5 年提出了复合形方法( 刘战合， 2 0 0 4 ) ，通过对设计个体进行反射、扩张、压缩等基本操作实现全局寻优，具有 较强的局部寻优能力，易于收敛。本文将研究遗传算法与复合形法的结合，并通 过实例结果分析该混合算法的性能。 本文共六章，第一章介绍遗传算法的特征、发展与应用，并说明本文的选题 依据，研究内容和基本方法。第二章介绍遗传算法的基础知识。第三章探讨遗传 算法的实现技术，介绍相关的基本遗传操作算子。第四章给出遗传算法的一些改 进策略，包括对基本操作算子设计与算法参数选取的改进，以及对遗传算法早熟 收敛现象的改进方案。改进方案从两个角度来研究遗传算法与复合形方法的结 摘要 合，分别称为改进遗传算法i 与改进遗传算法2 。第五章将第四章的改进策略应 用于配电网设备检修计划优化模型的求解。结果显示，与基本遗传算法相比，改 进算法在性能上有较大的优越性，能够在很大程度上降低成本，具有很好的经济 应用价值。第六章给出了本文的总结以及可以进一步研究的方向。 关键词：遗传算法复合形法改进遗传算法配电网设备检修计划 a b s t r a c t a bs t r a c t d u r i n gt h er e s e a r c ha n dp r a c t i c eo ft h es c i e n t i f i ct h e o r y , t h e r eo f t e ne x i s t ss u c h k i n do fp r o b l e mt h a tt od e t e r m i n et h ec r k e r i o no fa l lo p t i m a ls c h e m e ，a n dt h ew a yo f s e e k i n gt h eo p t i m a ls c h e m e t h i sk i n do fp r o b l e mi sc a l l e da no p t i m i z a t i o np r o b l e m s c i e n t i f i cr e s e a r c h e r sh a v es t u d i e do u tr a t h e rm a t u r ea l g o r i t h m sa n dm e t h o d sf o r s o m es i m p l ec i r c u m s t a n c e h o w e v e r , f o rt h ec o m p l i c a t e ds y s t e m ，t h e yu s u a l l yf e e l i n c o m p e t e n ta n dt r yt of i n dm o r ee f f e c t i v em e t h o d s s i n c e19 4 0 s ，r e s e a r c h e r sh a v en o t i c e dt h ep o w e r f u la d a p t a t i o na b i l i t yo ft h e l i v i n gb e i n g sd u r i n gt h ee v o l u t i o no ft h en a t u r e s u p e r i o rg e n e sa r ec o n s i s t e n t l y d u p l i c a t e d ，t h ea d a p t a t i o n so fc o m m u n i t y a r ei m p r o v e d ，a n dt h ee x c e l l e n ts p e c i e sw i t h p o w e r f u la d a p t a t i o ne m e r g e s t h eg e n e t i ca l g o r i t h mi ss u c ho p t i m a la l g o r i t h mt h a ti s b a s e do nt h er e s e a r c ho fn a t u r ea d a p t a t i o nt h e o r y a sag l o b a lo p t i m i z a t i o na l g o r i t h m ， t h eg e n e t i ca l g o r i t h mh a st h ef o l l o w i n gp r o p e r t i e s ：( 1 ) b yt h eg r o u ps e a r c ht e c h n i q u e a n di m p l i c i tp a r a l l e l i n gp r o p e r t y , t h ee f f i c i e n c yo ft h ea l g o r i t h mi sa c c e l e r a t e d ；( 2 ) i t r e l i e so n l yo nt h ev a l u e si n s t e a do ft h ea l g e b r a i ce x p r e s s i o no ft h eo b j e c t i v ef u n c t i o n ； ( 3 ) t h er e l i a b i l i t yo ft h es ol u t i o ni si m p r o v e db e c a u s eo ft h er o b u s t n e s so ft h e a l g o r i t h m ( 4 ) i ti ss i m p l ea n dg e n e r a ka n de a s yt ob ec o m b i n e dw i t ho t h e ra l g o r i t h m s t of o r mh y b r i da l g o r i t h m s b u tt h eg e n e t i ca l g o r i t h mi sn o te f f i c i e n ta tl o c a ls e a r c h a r h o u g hi tc a nr e a c h t h en e a r b yo ft h eo p t i m a ls ol u t i o nq u i c k l yb yt h ep o w e r f u lg l o b a lc o n v e r g e n c e p r o p e r t y , i tt a k e sv e r yl o n gt i m et of m dt h eo p t i m a ls ol u t i o n t h em a i nr e a s o no f t h e a b o v ep h e n o m e n ai st h a tt h eo f f s p r i n gc o n s t a n t l yi n h e r i t st h eg e n e so ft h ep a r e n t ， w h i c hr e d u c e dt h ed i v e r s i t yo f t h ec o m m u n i t y , s ot h a tt h ea l g o r i t h mi st r a pi n t oal o c a l c o n v e r g e n c e i no r d e rt om a k ef u l lu s eo ft h ea d v a n t a g eo ft h ea l g o r i t h m ，t oa v o i di t s w e a k n e s s ，a n dt os p e e du pt h ec o n v e r g e n c e ，o n ee f f e c t i v em e t h o di st oa d o p tt h e h y b r i ds t r a t e g yb e s i d e sw e l ld e s i g n e db a s i cg e n e t i co p e r a t o r sa n dp r o p e r l yc h o s e n p a r a m e t e r so ft h ea l g o r i t h m t h a ti s ，t ob r i n gf a s tc o n v e r g e n tl o c a lo p t i m i z a t i o n a l g o r “h mi n t ot h eg e n e t i ca l g o r i t h md u r i n gt i 汗g e n e t i ce v o l u t i o np r o c e s s 。j n dt of o r m ah y b r i dg e n e t i ca l g o r i t h m f o r e i g nr e s e a r c h e r sh a v eg a i n e dp r o m i n e n tr e s u l t si ne n h a n c i n gt h el o c a ls e a r c h m a b s l r a c t a b i l i t ya n ds p e e d i n gt h eo p t i m i z a t i o np r o c e s so fg e n e t i ca l g o r i t h m ( a l l e ng a r d n e rb e t a l ，2 0 0 3 ) ，( k u r t ahe t a l , 2 0 0 2 ) ，( g h a s e m im re t a l ，19 9 9 ) d o m e s t i cr e s e a r c h e r s a l s oh a v e g a i n e dm a n yi m p o r ta c h i e v e m e n t si n v a r i o u sf i e l d sb ys t u d y i n gt h e c o m b i n a t i o no ft h eg e n e t i ca l g o r i t h mw i t ht h ef l e x i b l et o l e r a n c em e t h o do rt h e s i m u l a t e da n n e a l i n gm e t h o d t h ec o m p l e xm e t h o d ( z h a nh el i u ，2 0 0 4 ) w a sf i r s t l y p r o p o s e db yj b o xi n 19 6 5 ，i to p t i m i z e st h eo p t i m i z a t i o ni n d i v i d u a l sb yt h er e f l e c t i o n ， e x p a n s i o n ，a n dc o m p r e s s i o no p e r a t o r i tp o s s e sp o w e r f u ll o c a lo p t i m i z a t i o nc a p a c i t y , i s e a s yt oc o n v e r g e t h i sp a p e rw i l ls t u d yt h ec o m b i n a t i o no ft h eg e n e t i ca l g o r i t h m a n dt h ec o m p l e xm e t h o d ，a n da n a l y z et h ep e r f o r m a n c eo ft h eh y b r i da l g o r i t h m t h r o u g ht h ec a s er e s u l t s t h ep a p e rc o n t a i n ss i xc h a p t e r s t h ef i r s tc h a p t e ri n t r o d u c e st h ec h a r a c t e r , e v ol u t i o n ，a n da p p l i c a t i o no ft h eg e n e t i ca l g o r i t h m ，a n di l l u s t r a t e st h ep a p e r ss e l e c t e d t o p i cb a s e ，r e s e a r c hc o n t e n t sa n db a s i ca p p r o a c h t h es e c o n dc h a p t e rp r e s e n t st h e b a s i ck n o w l e d g eo ft h eg e n e t i ca l g o r i t h m t h et h i r d c h a p t e rp r o b e s i n t ot h e i m p l e m e n t a t i o nt e c h n i q u eo ft h eg e n e t i ca l g o r i t h m ，i n t r o d u c e sr e l a t e db a s i cg e n e t i c o p e r a t o r s t h ef o u r t hc h a p t e rp r o v i d e ss o m ei m p r o v e ds t r a t e g i e so ft h eg e n e t i c a l g o r i t h m i tn o to n l yi m p r o v e st h ed e s i g no ft h eb a s i co p e r a t o ra n dt h es e l e c t i o no f t h ea l g o r i t h m i cp a r a m e t e r s ，b u ta l s o g i v e st h ei m p r o v e ds c h e m et o s o l v et h e p r e m a t u r ec o n v e r g e n c ep h e n o m e n o no ft h eg e n e t i ca l g o r i t h m t h ei m p r o v e ds c h e m e s t u d i e st h eh y b r i do ft h eg e n e t i ca l g o r i t h mw i t ht h ec o m p l e xm e t h o df r o mt w op o i n t s o ft h ev i e w , a n di sn a m e dt h ei m p r o v e da l g o r i t h m1a n dt h ei m p r o v e da l g o r i t h m2 t h ef i r hc h a p t e ra p p l i e st h ei m p r o v e ds t r a t e g i e so ft h el a s tc h a p t e rt ot h ed i s t r i b u t i o n d e v i c e sm a i n t e n a n c es c h e d u l i n go p t i m a lm o d e l t h r o u g ht h ep e r f o r m a n c eo ft h e o p t i m a lr e s u l t s ，t h es u p e r i o r i t yo ft h ei m p r o v e dg e n e t i ca l g o r i t h mt o t h eg e n e t i c a l g o r i t h mi sv e r i f i e d t h eo p t i m a lr e s u l t sc a nr e d u c et h el o s st ot h el a r g ee x t e n t ，a n d h a sp o w e r f u le c o n o m i ca p p l i e dv a l u e t h es i x t hc h a p t e rg i v e st h es u m m a r yo ft h e p a p e ra n dt h ef u r t h e rr e s e a r c ho nt h es u b j e c t k e yw o r d s ：g e n e t i ca l g o r i t h m ，c o m p l e xm e t h o d ，i m p r o v e dg e n e t i ca l g o r i t h m ， d i s t r i b u t i o nn e t w o r kd e v i c em a i n t e n a n c es c h e d u l e w 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：塑鲥 签字日期 如z 臼) 5 - 刁 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中国学 位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 卤鑫开口保密( 年) 作者签名：捏之士虹 导师签名： 签字日期： 知f q 主12 3 签字日期： 第一章绪论 第1 章绪论 本章将阐述遗传算法的特征、发展与应用，据此提出本文的选题依据，研究 目的，研究内容和方法。 1 1遗传算法的特征、发展与应用 遗传算法作为一种应用比较广泛、影响比较大的优化算法，与其他优化算法 相比，它主要具有下述若干独特的性能。 ( 1 ) 遗传算法以参数的编码集作为运算对象，并且在执行搜索过程中，不受优 化函数连续性及其导数求解的限制，因而具有很强的通用性。 ( 2 ) 遗传算法直接使用由目标函数确定的适应度函数信息，以群体为单位执行 搜索过程，加快搜索到适应度较好的搜索空间，因而具有较强的全局搜索能 力。 ( 3 ) 遗传算法简单通用，普适性强，易于与其他算法结合构成混合智能算法， 并且该算法具有很强的鲁棒性，因而在众多领域得到了广泛的应用。 鉴于以上特征，遗传算法受到了越来越广泛的重视。其具体发展过程如下所 述： ( 1 ) 1 9 6 2 年，j o h nh o l l a n d 提出了利用群体进化模拟适应性系统的思想( h o l l a n d ， j h 。1 9 6 2 ) ，引进了群体、适应值、选择、变异、交叉等基本概念。 ( 2 ) 1 9 6 7 年，h o l l a n d 的学生j d b a g l e y 在其博士论文中首次提出“遗传算法” 一词( b a g l e y , j d ，1 9 6 7 ) 。 ( 3 ) 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 ) ( h o l l a n d ，j h ，19 9 2 ) 提出了对遗传算法的 理论发展极为重要的模式理论。同年，d ej o n g 在其博士论文研究中首次把 遗传算法用于函数优化问题( d ej o n g ，k a ，1 9 7 5 ) ，并给出了适用于大多数 优化问题的遗传算法的参数，建立了著名的d ej o n g 五函数测试平台。 ( 4 ) 8 0 年代，h o l l a n d 教授开g , j t 基于遗传算法的机器学习的新概念，为分类 器系统构造出了一个完整的框架( h o l i a ：, djh ，r e i t m a n ! s ，1 9 7 0 ) ( 5 ) 1 9 8 9 年，d a v i dg o l d b e r g 出版了专著搜索、优化和机器学习中的遗传算 法( 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 na n dm a c h i n el e a r n i n g ) 第一章绪论 ( g o l d b e r gd e ，19 8 9 ) 这是第一本遗传算法教科书，总结了当时关于遗传算 法领域的研究工作，为推广和普及遗传算法的应用起到了重要的指导作用。 ( 6 ) 1 9 9 2 年，k o z a 将遗传算法应用于计算机程序的优化设计及自动生成，提 出了遗传编程的概念( k o z ajr 1 9 9 4 ) ，( k o z ajr ，1 9 9 2 ) ，并且为基于符号 表示的函数学习问题提供了一个有力的工具。 当前因特网的出现，加速了遗传算法的推广。g e c c o ( g e n e t i ca n d e v o l u t i o n a r yc o m p u t a t i o nc o n f e r e n c e ) 国际会议，p p s n ( p a r a l l e lp r o b l e ms o l v i n g f r o mn a t u r e ) 会议，f o g a ( f o u n d a t i o no fg e n e t i ca l g o r i t h m ) 会议，c e c ( c o n g r e s so n e v o l u t i o n a r yc o m p u t a t i o n ) l 垂l 际会议，以及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 杂志等，更进一步加速了遗传算法理论的研究，拓展了遗传算法的应用 领域，使得其成为一个多学科、多领域的重要研究方向。 遗传算法具有很强的全局搜索能力，通用性强，鲁棒性高，因而被广泛应用 于很多领域，下面简要介绍一些主要的应用领域： ( 1 ) 函数优化。函数优化不仅是遗传算法的经典应用领域，而且各类复杂的测 试函数也是对遗传算法进行性能评价的依据。另外，对于一些使用其他优化 方法很难求解的非线性、多目标函数优化问题，应用遗传算法一般可以得到 满意的优化结果。 ( 2 ) 调度问题。遗传算法在生产调度中得到了广泛的应用，不仅避免了只依据 靠经验调度的不可靠性，而且避免了在传统求解过程中由于对模型的大幅度 简化，而导致求得结果与实际结果之间的巨大差异。 ( 3 ) 图像处理。遗传算法在模式识别、图像恢复、图像边缘特征提取等方面得 到了广泛的应用。 ( 4 ) 自动控制领域。遗传算法在参数辨识、模糊控制器的优化设计、模糊控制 规则的学习中的应用取得了很显著的成果。另外，遗传算法在航空控制系统 的优化、空间交会控制器的设计、故障诊断( z h o n gb i n g l i nc ta l , 1 9 9 2 ) ， ( z h a n g ，j ，a n dr o b e r t , p d 19 9 2 ) 和机器人行走路径规划( g i l l ，m a c ，a n d z o m a y a ，a y ，1 9 9 8 ) ，( d o r i g o ，m ，a n ds c h n e p h ，u ，e ta 1 ，1 9 9 3 ) ，( d a v i d o r , y ， 1 9 9 1 ) d 尸的应用也取得了成功。 ( 5 ) 机器学习。基于遗传算法的机器学习，在很多领域中都得到了广泛的应用。 其中比较典型的是h o l l a n d 设计的分类器系统( g o l d b e r g ，d e ，1 9 8 9 ) ，以及 机器人规划、模式识别、概念学习等m c a u l a y , a d ，a n do h ，j c 1 9 9 4 ) ， ( d o r i g o ，me ta l , 19 9 3 ) ，( ( k a d a b a ，n ，n y g a r d ，k e ，a n dj u e l l ，p j ，19 91 ) ( l i e p i n s ，qe ，a n dw a n g ，l a ，1 9 9 1 ) 。 ( 6 ) 社会与经济领域。基于遗传算法的思想，软件开发人员设计了很多的软件 第一章绪论 包，服务于各类社会和经济行业，比如金融系统和股票投资分析行业。 ( 7 ) 人工智能与科学计算。因为很多求解问题的复杂性，往往得不到问题的解 析解，人们尝试运用各种算法求出最优解的近似解来逼近最优解。遗传算法 是这类算法中一种典型的方法，被广泛应用在很多问题求解中。例如本文给 出了遗传算法在配电网设备检修优化模型中的应用实例，如果将优化结果应 用在配电网设备检修计划中，能从很大程度上降低因检修而带来的损耗，具 有很好的经济应用价值。 至此，我们可以看出遗传算法具有很高的应用价值。但是，遗传算法并不是 一种完美的算法，其存在着不足之处，导致有时优化结果并不理想。因而，为了 充分利用遗传算法的优势，克服其缺陷，还需要开展进一步相关的研究工作。 1 2 本文的选题依据，研究内容和基本方法 ( 1 ) 选题依据 由前面所述，遗传算法具有显著的性能优势，被广泛地应用于各种领域。但 遗传算法自身存在一些不足，如搜索时间过长、易发生早熟收敛、局部寻优能力 差等。而今，随着“改革开放”的深入，各种理论、思想的交流不断得到加强， 产生了越来越多的新发明、新创造。因而，为了克服遗传算法自身的不足，尝试 在遗传算法基本操作的设计过程中，融入能克服遗传算法缺陷的新方法、新思想。 于是，我们希望能够找到一个有效的具有快速收敛能力的局部寻优算法，将其引 入到遗传进化的过程中，最终获得一类新的混合智能算法，其不仅保持了遗传算 法全局搜索能力强的特点，而且其局部寻优能力得到了极大的改善和提高。而复 合形方法具有这方面的特征，因而本文重点在研究遗传算法与复合形法融合的角 度。 ( 2 ) 研究内容和基本方法 本文重点研究遗传算法的改进策略，使得其在保留强的全局收敛能力的同 时，能极大地改善其容易限于局部收敛的缺陷。为了读者能更好的理解本文的研 究内容，本文采用如下方式展开。 第二章中简要的介绍了遗传算法的相关理论，包括该算法描述的一般模型、 基本操作算子的确定、参数的选取、收敛性的充要条件等。 第三章中详细的介绍了遗传算法实现的相关操作，包括编码方法、群体规模、 初始群体、适应值、复制算子、交叉算子、变异算子、收敛准则等。在描述相关 操作时，不仅介绍了操作实现的具体步骤，而且给出了操作中需要注意和改进的 地方。 第四章中具体的给出了遗传算法实现中相关操作的一些改进策略，包括改进 第一章绪论 初始群体构造方法、改进罚函数方法、改进复制算子、改进交叉算子、改进变异 算子、改进收敛准则，并且针对遗传算法容易早熟的现象，本文也探索了针对该 问题的改进方法。在遗传算法基础上，引入一个易收敛、局部寻优能力强的复合 形法。我们从两个角度来融合遗传算法与复合形法，称为改进遗传算法1 与改进 遗传算法2 。为便于读者有个形象的理解，本文给出了改进遗传算法1 和改进遗 传算法2 的流程图。 改进遗传算法l 中，首先，由遗传算法对搜索空间进行一次优化，搜寻到最 优解的附近时停止，转而通过复合形法对当前寻优结果进行二次优化，最终获得 全局最优解。改进遗传算法2 中，遗传算法在每次进化过程中，通过复合形法不 断排序、继承、更新的操作过程，不断改善种群，把整个种群向最优解的方向收 缩，同时也维持了种群的多样性。在该改进遗传算法2 中，复合形法实质上成为 了遗传算法的一个算子。 第五章中主要是检验两种改进遗传算法的实用性与有效性。本文将改进遗传 算法与遗传算法分别应用到配电网设备检修计划优化模型中。通过算例结果分 析，改进遗传算法不仅寻优速度快、效率高，而且其优化结果在很大程度上降低 了因检修而带来的损耗，验证了改进遗传算法相比遗传算法的优越性。 4 第二章遗传算法 第2 章遗传算法 2 1 遗传算法概述 遗传算法主要借鉴了生物进化的一些特征，模拟生物的自然选择和遗传机制 而形成的一种自适应全局优化概率搜索算法。依据达尔文“适者生存”的理论， 在不断变化的自然环境中，只有那些适应性好的个体才能存活下来，并通过遗传 机制将好的特性传递给其后代。与此同时，在遗传过程或适应环境过程中，个体 发生了变异，具有了适应环境的能力。这样，在进化过程中，生物群体将逐渐地 产生优良的群体，适应生态环境的变化。其在形式上是一种迭代方法，从选定的 初始解出发，通过不断迭代计算过程，逐步改善当前解，直至最后搜到最优解或 满意解。 为便于读者更好的理解算法，本文对文中将要出现的相关术语做了简要的说 明。在后文实例分析中，本文又将相关一些术语放到实例中再次解释，以便给读 者留下形象的理解。目前，遗传算法的相关术语还没有得到统一，本文中采用的 术语及其含义解释如下： 个体：遗传算法要优化的基本对象，也就是说个体中包含了各个参数属性的 对象。 群体：个体的集合。 群体规模：群体中个体的个数。 染色体：个体的编码。其用来表征个体，并且反映了个体的特征。 基因：组成染色体的元素，表示不同的特征。 基因长度：组成染色体基因的个数。 等位基因：同一基因位的基因取值。 适应值：反映个体对于环境的适应能力。 复制：实质上就是保留那些在选择机制下存活的个体。 交叉：染色体相应基因的交换。 变异：染色体上某个基因的变化。 进化：复制、交叉、变异是遗传算法的基本操作算子，这些算子执行一次就 相当于进化一次，它们反映了物种的进化、淘汰过程。 第二章遗传算法 2 2 遗传算法描述的一般模型 学者注意到，生物在其进化过程中，显示出强大的适应环境的能力。于是， 很多基于生物该生存特性的新思想和方法被研制出来，并且取得了很多重要的成 果。遗传算法正是基于模拟生物遗传和进化的一种自适应算法。为研究需要，本 文参照h o l l a n d 关于复杂适应系统的建模理论，给出遗传算法描述的一般数学模 型。 遗传算法本质上采用“进化论”思想，在问题处理过程中，往往采用离散化 过程，假定其进化次数为f = 1 ? ；假定长度为 的染色体表示为符号串 x = 五j c 2 ，其中：记号薯o = l ，2 ，m ) 代表一个遗传基因，它的所有可能取值称 为等位基因；所有等位基因的组合构成了解的基本空间： a = j c l 艺= 兀：l 薯 ( 2 1 ) 处于f 进化次数的群体记为a ( t ) ；与此进化次数对应的环境记为b ( t ) ，并假定各 进化次数对应的环境召( r ) 是相互独立的：群体对环境的适应能力记为c ( t ) ；自 然选择和遗传机制d ，作用下生成新的解集群体彳( f + 1 ) ： a ( t + 1 ) = z ( 4 ( f ) ，c ( f ) ) ( 2 2 ) 依据达尔文的自然进化理论，适应环境的物种生存下来，而不适应环境的物 种则被淘汰。由此看出，环境在生物群体的进化过程中起着至关重要的作用，因 此，我们不能简单的考察群体对某一特定环境的适应情况，而应该将群体融入到 一个动态的环境之中，来研究群体的进化过程，因此上一模型中仅考虑到群体对 当前进化次数对应的环境的适应能力是不合理的。为此，我们引入一个新的变量 岛( f ) = ，它反映了此进化次数之前群体与环境的动态适应 历史信息，更贴切的再现了群体的自然进化过程。故上述模型修改为： a ( t + 1 ) = 4 ( 彳( f ) ，c ( r ) ，( f ) ) ( 2 3 ) 其中：e s ( f + 1 ) 的生成反映了在群体自然进化过程中，自然选择和遗传机制的处 理方式： ( f + 1 ) = a , ( e b ( ，) ，c ( f ) ) ( 2 4 ) 新的解集群体的生成可以理解为一个随机过程。对于有限的解集空间， x = 【薯，而，再，而】，刀= i 卅，当么窖) 硝识) 刀 ，在自然选择和遗传机制 d ，作用下生成新的解集群体彳o + 1 ) = lq = 1 , 2 ，疗) 的概率为 6 第二章遗传算法 则上述改进模型可以改写为： p ( f ) = 仍。( f ) i a ，。o ) - - 1 ( 2 5 ) 碍= l 尸( f + 1 ) = d t ( a ( t ) ，c o ) ，岛( ，) ) ( 2 6 ) 群体彳( f ) 对环境b ( f ) 的适应性测度一般采用大于等于0 的实数表示，表示为： l x s ( a ( t ) ) = 卢口，( 4 ( f ) ，b ( f ) ) ( 2 7 ) 其中：盯表示处于f 进化次数的群体4 u ) 对环境b ( f ) 的适应性。一旦群体或环 境发生变化，那么群体适应环境的能力也随之发生变化，适应性测度函数也会做 相应的调整： 鳓，川= 4 ( ，i 耵，4 p ) ，c ( f ) ) ( 2 8 ) 在t 进化次数，群体对环境的适应能力c ( t 1 可以表示为： c ( f ) = 口，( 彳p ) )( 2 9 ) 当环境和群体变化时，自然选择和遗传机制d ，也需要进行适应性调整，使得 群体具有更好的适应性。自然选择和遗传机制的调整应该考虑当前机制作用的群 体，当前群体对环境的适应能力c ( t ) ，群体与环境的动态适应历史信息e b ( f ) ， 历史自然选择和遗传机制e d ( t ) - 等，表述如下： d ( t + 1 ) = g ( 彳( f ) ，c ( f ) ，e b ( f ) ，易( f ) ) ( 2 1 0 ) 群体适应环境的整个进化阶段中，群体的适应性测度为 r f ( r ) = ， ( 2 1 1 ) t = l 群体对环境的适应过程与自然选择和遗传机制日( d 紧密相关。在自然选择和遗 传机制毛( d = 下，整个进化阶段，群体的适应性测度为： r f ( t ，( 丁) ) = 心，( 4 ( f ) ) f ；i ( 2 1 2 ) 对于全局最小值优化模型，假设进化阶段获得最小累计支付的适应计划是最佳 的： ，( 丁) = m ! n f ( e 4 ( r ) ) ) ( 2 1 3 ) w 参考控制理论的相关信息，一个复杂系统的适应计划 第二章遗传算法 f ( 吃( n ) = ( 2 1 4 ) 称为满意适应计划，如果满足： 娶m 【f ( 毛( 功，( 乃】_ l ( 2 1 5 ) - - + a o 称f ( e ( r ) ) 是一个满意的适应计划，如果对于某一给定的环境变化 马= 口0 ，口是一个很小的实数，则称f ( 日( r ) ) 是一个满意的适应计划。 综合以上内容，我们给出描述复杂系统适应过程的数学模型如下： a ( t + 1 ) = 吐( 4 ( ，) ，c ( f ) ，e b ( r ) ) e 8 ( f + 1 ) = 4 ( o ) ，c ( f ) ) ，如( 彳o ) ) = ，( 彳( r ) ，占( f ) ) c ( ) 2 r ( ) ( 2 1 8 ) ”l = 4 ( 心，彳( ，) ，c ( f ) ) 。 d ( t + 1 ) = g ( 彳( f ) ，c ( o ，e b ( r ) ，历( f ) ) 7 ，( 丁) = 心， 其中：o ) = ；髟o ) = ；彳o ) 表示r 进化次数的群体；聊) 表示与此进化次数对应的环境：c ( f ) 表示群体对环 境的适应能力；吐表示自然选择和遗传机制；耵表示处于f 进化次数的群体么( f ) 对环境b ( f ) 的适应性。 基于上述模型，我们懂得在进行遗传算法的研究中时，有关键的几点必须明 确： ( 1 ) 要明确算法研究的对象，优化的对象，以便确定算法中的个体、群体。 ( 2 ) 要明确群体的生存环境，也就是优化变量需要满足的约束条件。 ( 3 ) 要明确环境对群体的选择机制，也就是优化变量满足哪些条件时才能被保 留下来。 ( 4 ) 要明确群体的适应机制是什么，也就是优化变量如何向优化问题最优解的 方向靠近、进化。 第二章遗传算法 ( 5 ) 要明确算法的一些改进策略，以便保证算法的收敛，提高算法的运行效率 与精确度。 2 3 遗传算法的基本操作算子和参数选取 群体多样性的性质的好坏关系着遗传算法的搜索能力、收敛性质。环境对群 体的选择机制下，群体不断向着更好适应环境的方向进化，导致群体的多样性程 度降低，群体搜索的领域越来越小。如若没有其他操作算子，那么在选择机制下， 群体最终将趋向稳定，并将一直保持稳定，此时算法也就达到了收敛。但是该收 敛点未必是最优解，甚至与最优解相差很多，无法逼近最优解。因而，从某种程 度上讲，仿照生物自然进化过程，遗传算法加入交叉、变异基本操作，就是为了 改善群体的多样性而设计的。第4 章中的一些改进策略，也是在保证群体多样性 性质的基础上，为了提高算法运行效率，加速收敛而做的一些改进。 文献( 李敏强等，2 0 0 2 ) 1 6 6 中的相关结论为基本遗传操作设计提供了理论 上的支持。该文献中提及：如果遗传算法设计中只包含环境对群体的选择机制， 那么搜寻的结果停留在初始群体中适应值最好的个体而不再改变。如果算法只包 含环境对群体的选择机制，以及群体中个体间的交叉操作，那么当群体多样性测 度降到0 时，搜寻操作停止，算法只能收敛到最优解的邻近点。只有算法包含环 境对群体的选择机制，个体间的交叉操作，以及个体的变异操作时，算法才能够 收敛到最优解。 遗传算法基本操作确定后，我们就要考虑相应参数的设计。参数设计的合理 与否关系到算法的执行效率和优化结果。文献( 李敏强等，2 0 0 2 ) 1 6 3 2 1 5 同样为 参数设计提供了选择依据。相关结论为：算法运行初始阶段，选取较大的群体规 模、较松的选择机制、较大的交叉率，以便加大算法搜索的空间。算法运行中期 阶段，选取较小的群体规模、较严的选择机制、较大的变异概率，以便突破局部 最优解的控制。算法运行后期阶段，选取较小的群体规模，较严格的选择机制、 较小的交叉、变异概率，加快算法的收敛。 2 4 遗传算法收敛性的相关理论 评价算法优越性与否的关键指标是其运行效率和收敛性。高的运行效率可通 过选用合理的操作算子和参数来保证，那么其收敛性如何来保证呢? 文献( 邢文 训，谢金星，1 9 9 9 ) 1 6 4 中得到的与收敛性相关的结论如下： 定理如果遗传算法按交配、变异、种群选取之后更新当前最优染色体的进 化循环过程，则收敛于全局最优。 9 第二章遗传算法 由此可知，文献( 邢文训，谢金星，1 9 9 9 ) 嘲给出了保证遗传算法收敛的充分 条件，