（信号与信息处理专业论文）遗传算法和电子线路参数优化及中心化设计技术的研究.pdf

摘要 近年来，随着信息产业的蓬勃发展和电子产品竞争的日益激烈，电子线路的 优化设计技术越来越受到人们的关注。所谓电子线路优化设计是指利用数学优化 算法，以计算机作为分析工具，通过不断改变电子线路的拓扑结构和元件参数， 使其逐步满足某一特定设计指标的过程。通过电路优化设计可达到缩短设计周期、 降低成本、提高质量的目的。其分为电路拓扑结构优化和固定拓扑结构的电路参 数优化两部分，本文集中研究后者电子线路参数优化技术。其又可以分为两 大类：( 1 ) 基于性能的电子线路参数优化技术( 通常称为电路参数优化) ：( 2 ) 基 于成品率的电子线路参数优化技术( 通常称为电路中心化设计) 。另一方面，遗传 算法近年来以具有全局搜索能力，并行运算能力，鲁棒性强以及优化不需要目标 函数导数信息等众多优点而得到广泛应用。但是，其也存在诸如局部搜索能力差， 未熟收敛以及收敛速度慢等不足之处。因此，本文开展对遗传算法基础理论方面 研究，旨在提高遗传算法的收敛速度，改善其综合性能。百本文的详细内容如下： 首先，本文系统全面地研究和分析了遗传算法的基本概念、基本原理及其有 关方法。同时，提出并证明了基于二进制编码、一点交叉、位变异的加速遗传算 法收敛的有关通用定理最小分辨率定理、权值定理、交叉算子搜索步长定理 和变异算子搜索步长定理，在这些定理的基础上，提出了变染色体串长、变交叉 和变异概率的遗传算法，测试结果表明本算法能大大提高遗传算法的收敛速度， 与理论推导是一致的，并且其综合性能优于单纯保留最优个体的遗传算法。 其次，本文在分析了几种典型常用数学优化算法以及分析讨论了使用 o r c a d 9 1 优化电子线路参数的基础上，提出并实现了种实用的基于性能的电 子线路参数优化方法均匀设计多项式拟合遗传优化算法。( 其主要思想是采用 拟合的多元多项式代替电路仿真以指导遗传算法进行搜索，以便减少电路的仿真 次数。并在数据采集过程中运用均匀设计方法，不仅能减少数据采样的数目，而 且能使初始群体包含丰富的信息，更利于其收敛。从优化实例可知，其对设计目 标复杂以及参数较多复杂电路的优化是行之有效的。4 最后，本文在分析了基于成品率的电子线路参数优化技术电子线路参数 中心化设计的基本概念、有关术语以及研究现状等问题的基础上提出并实现了一 种基丁均匀设计的改进重心游移法。 路实例研究表明其在，v 元级 乜路们l h 心化 设计中是可行有效的，且大大优十传统的重心游移法。最后，探时”y - 基1 ：偏最小 二j 乘回归建模的方法。j 关键词：遗传算法i 电路参数优化_ 】u 路巾心化设计 a b s t r a c t r e c e n t l nw i t ht h er a p i d l yd e v e l o p m e n to fi n f o r m a t i o ni n d u s t r ya n dt h ec o m p e t i t i o n a m o n g e l e c t r o n i cp r o d u c t sb e c o m i n gi n c r e a s i n g l yi n t e n s e ，c i r c u i to p t i m i z a t i o nh a sb e e n p a i dc l o s ea t t e n t i o n c i r c u i to p t i m i z a t i o ni st h a tc h a n g i n gc i r c u i tt o p o l o g yo rp a r a m e t e r s o fc i r c u i tm a k e si t s a r i s f y i n gag i v e ns p e c i f i c a t i o nb yu s i n gm a t h e m a t i c a lo p t i m i z a t i o n a l g o r i t h m sa n dc o m p u t e rt e c h n o l o g y ，w h i c hc a ns h o r t e ni t sd e s i g n i n gp e r i o d ，l o w e ri t s c o s ta n d i m p r o v e i t s q u a l i t y ，c i r c u i to p t i m i z a t i o n c a nb ed i v i d e di n t ot w o p h a s e s c i r c u i tt o p o l o g yo p t i m i z a t i o na n dp a r a m e t e ro p t i m i z a t i o n i nt h i sp a p e r , w e f o c u so nt h el a t t e r c i r c u i tp a r a m e t e ro p t i m i z a t i o n c i r c u i tp a r a m e t e ro p t i m i z a t i o ni s b a s e do np e r f o r m a n c ea n d y i e l d ( u s u a l l y t h ef o r m e ri sc a l l e dc i r c u i t p a r a m e t e r o p t i m i z a t i o n ；a n dt h el a t t e ri sc a l l e dc i r c u i td e s i g nc e n t e r i n g ) i no p t i m i z a t i o nm e t h o d s ， i ti sw e l lk n o w nt h a tg e n e t i ca l g o l i t h m ( g a ) h a st h ea d v a n t a g e so fg l o b a ls e a r c h i n g ， p a r a l l e lc o m p u t i n g ，b e t t e rr o b u s t n e s s ，a n dn o tn e e d i n gd i f f e r e n t i a li n f o r m a t i o nd u r i n g e v o l u t i o n ，h o w e v e r , i ta l s oh a ss o m ed e m e r i t s ，s u c ha sp o o rl o c a ls e a r c h i n g ，p r e m a t u r e c o n v e r g i n ga sw e l la ss l o wc o n v e r g e n c es p e e d i nt h i sp a p e r , t h ef u n d a m e n t a lt h e o r yo f g e n e t i ca l g o r i t h mi s s t u d i e d ，w h i c ha i m sa ti m p r o v i n gg a sc o n v e r g e n c es p e e da n d c o m p r e h e n s i v ep e r f o r m a n c e f i r s t l y , b a s i cc o n c e p t i o na n dp r i n c i p l e ，a n ds o m em e t h o d so fg aa r es t u d i e da n d a n a l y z e di n t e g r a l l y m e a n w h i l e ，s o m eg e n e r a lt h e o r e m s m i n i m a lr e s o l u t i o n ，w e i g h t v a l u e ，a n ds e a r c h i n gs t e po fc r o s s o v e ra n dm u t a t i o na b o u tc h r o m o s o m es e a r c h i n gs t e p i ng ab a s e do nb i n a r y c o d i n g ，o n e p o i n tc r o s s o v e r ，b i tm u t a t i o na r ep r o p o s e da n d p r o v e d b a s e do nt h e s et h e o r e m s ，a ni m p r o v e dg a u s i n gv a r i a n tc h r o m o s o m el e n g t h a n dp r o b a b i l i t yo fc r o s s o v e ra n dm u t a t i o ni s p r e s e n t e d l h et e s t i n gw i t hs o m ec r i t i c a l f u n c t i o n ss h o w st h a ti tc a ni m p r o v et i mc o n v e r g e n c e s p e e do fg as i g n i f i c a n t l ya n di ti s i na c c o r d a n c ew i t ht h e o r e t i cd e d u c t i o n ，a n di t s c o m p r e h e n s i v ep e r f o r m a n c ei sb e t t e r t h a nt h a to f t h eg a w h i c ho n l yr e s e r v e st h eb e s ti n d i v i d u a l s e c o n d l y ，s o m ec r i t i c a lm a t h e m a t i c a lo p t i m i z a t i o na l g o r i t h m sa r ea n a l y z e d ，a n dc i r c u i t p a r a m e t e ro p t i m i z a t i o nw i t ho r c a d9 1i sd i s c u s s e di nt h i sp a p e r m o r e o v e r , a p r a c t i c a l m e t h o do fc i r c u i t p a r a m e t e ro p t i m i z a t i o n b a s e do np e r f o r m a n c e - - u n i f o r m d e s i g n f i u i n gg e n e t i ca l g o r i t h mi sg i v e na n dr e a l i z e d t h em a i ni d e ai st h a tc i r c u i ts i m u l a t i o n i s r e p l a c e db yf i t t i n g o fm u l t i v a r i a t ep o l y n o m i a lt o g u i d et h eg e n e t i ca l g o r i t h mt o s e a r c h ，w h i c hd e c r e a s e st h en u m b e ro fc i r c u i t s i m u l a t i o n d u r i n gd a t u ms a m p l i n g ， u n i f o r md e s i g ni su t i l i z e d ，w h i c hc a l ln o to n l yr e d u c et h en u m b e ro f s a m p l i n g ，b u ta l s o m a k ei n i t i a lp o p u l a t i o nh a v ec o m p r e h e n s i v ei n f o r m a t i o n ，a n dw h i c hi sm o r e p r o p i t i o u s f o r a l g o r i t h mc o n v e r g i n g c i r c u i to p t i m i z a t i o ne x a m p l e ss h o wt h a tt h i s a p p r o a c hi s v a l i d a t ef o rt h o s ec i r c u i t sw i t hc o m p l i c a t e d d e s i g no b j e c t sa n dh a v i n gm a n yp a r a m e t e r s f i n a l l y ，b a s i cc o n c e p t i o n ，r e l a t i v e t e r m i n o l o g i e s a n dr e v i e wo fc i r c u i t d a r a m e t e r c e n t e r i n ga r ea n a l y z e d f u r t h e r m o r e ，a ni m p r o v e dc e n t e r so fg r a v i t y ( c o g ) b a s e do n u n i f o r m d e s i g ni sp r e s e n t e da n dr e a l i z e d c i r c u i te x a m p l e ss h o wt h ep r o p o s e dm e t h o di s v a l i d a t e df o rc e l ll e v e l c i r c u i t s ，a n di t s p e r f o r m a n c e i sm u c hb e t t e rt h a nt h a to f t r a d i t i o n a lc o g i nt h e e n d ，m o d e l i n g m e t h o db a s e do np a r t i a l l e a s t s q u a r e s r e g r e s s i o n i sd i s c u s s e d k e y w o r d s ：g e n e t i c a l g o r i t h m ，c i r c u i tp a r a m e t e ro p t i m i z a t i o n ，c i r c u i t d e s i g nc e n t e r i n g i v 天津大学博【：学位论艾 销一章绪论 1 1 前言 第一章绪论 近年来，随着信息产业的蓬勃发展和电子产品竞争的日益激烈，电子线路的 优化设计技术越来越受到人们的关注。所谓电子线路优化设计是指利用数学优化 算法，以计算机作为分析工具，通过不断改变电子线路的拓扑结构和元件参数， 使其逐步满足某一特定设计指标的过程。它利用计算机运算速度快、存储容量大 以及数据处理技术好的特点，以达到缩短设计周期、降低成本、提高质量的目的。 电子线路优化包括电路拓扑结构优化和固定拓扑结构的电路参数值优化两部分 ”。“。前者是通过符号运算不断改变电路拓扑结构以使其获得具有潜在好的性能； 后者是在固定拓扑结构上，通过不断调整电路参数值以使其性能达到最优。对于 前者，一方面可以通过优化获得性能潜在好的电路；另一方面，通过优化可以删 除冗余器件，使得在批量生产中降低成本。对于后者，一方面其是拓扑结构优化 后的第二道工序，即调整参数值以使达到电路性能最优；另方面在电子线路 的批量生产中通过调烂电路参数值，使其获得潜在高的成品率，以保证生产过程 中获得较高成品率进而降低成本，提高产品可靠性。本文集中研究电子线路参数 优化技术。 对电子线路参数优化又可以分为两大类： ( 1 ) 基于性能的电子线路参数优化技术( 通常称为电路参数优化) ( 2 ) 基于成品率的电子线路参数优化技术( 通常称为电路中心化设计) 对于第一类其是通过优化设计，调整电路参数值使其满足给定的设计指标或 优化其性能。通过其优化设计，可以自动解决传统手工方法无法解决的复杂问题， 以实现设计自动化。对于第二类，其在电路满足设计指标的基础上，通过进一步 的优化设计赋予其潜在高的成品率，以防止电路参数值在制造过程中不可以避免 的随机波动而导致成品率下降。应该指出的是，对于不进行批量生产的电子线路， 通过中心化设计可以降低其对参数值变化的敏感程度，使其能在使用环境( 温度， 湿度等) 发生变化以及电路老化导致元件值发生轻微变化的情况下，以较大的概 墨堡查兰竖主堂垡笙奎一生兰曼! ! 鱼 率保持性能的稳定，即提高其可靠性。因此，从某种意义上讲，后者是更高意义 上的电路参数优化设计。 由上可知，不论是基于性能的还是基于成品率的电子线路参数优化技术，其 都能达到缩短产品的设计周期、降低成本、提高质量的目的。因此，在将集成电 路设计与制造等作为重点发展信息技术的国情背景下，开展这方面研究具有深远 的现实意义。 同时，随着电子线路变得越来越复杂，参数越来越多，传统优化算法解决此 类问变得无能为力，因此，需要引入某些新型的优化算法。因此，本文将遗传算 法引入( g e n e t i ca l g o r i t h m s ) 并加以研究。其就是一种适合处理传统搜索方法 难于解决的复杂和非线性问题的优化算法。其以具有全局搜索能力，并行运算能 力，鲁棒性强以及优化不需要吲标函数导数信息等众多优点丽得到广泛应用。【列 此遗传算法成为2 l 世纪智能计算中的关键技术之一。然而，遗传算法也存在诸如 局部搜索能力差，未熟收敛以及收敛速度慢等不足之处，限制其更广泛地应用。 因此，开展对遗传算法基础理论方面研究旨在解决其应用中存在的问题在智能计 算、并行运算、人工智能等信息技术高度发展的当代同样具有很高的现实意义【。 1 2 本文任务及其结构 首先，系统全面地研究和分析遗传算法的基本概念、基本原理及其有关方法， 提出并证明几个有关加速遗传算法收敛的通用定理，在此基础上，提出一种旨在 提高遗传算法收敛速度的算法，为第二篇应用遗传算法进行电子线路参数优化作 准备。其次，在分析几种典型常用的数学优化算法，以及分析讨论使用o r c a d 9 i 优化电子线路参数技术的基础上，提出并实现一种实用的基于性能的能对设计目 标复杂以及参数较多复杂电路进行优化的电子线路参数优化算法。最后，在分析 基于成品率的电子线路参数优化技术电子线路参数中心化设计基本概念以及 研究现状等问题的基础上提出并实现了一种大大优于传统重心游移法的改进算 法。最后，探讨基于偏最小二乘回归建模的方法。 本文共三篇，其结构如下： 第一篇遗传算法的研究，其包括： 第二章遗传算法的基本概念 天津大学博士学位论文 第一章绪论 第三章遗传算法的基本原理和方法 第四章变串长与变概率遗传算法的研究 第五章本篇小结 第二篇基于电子线路性能的参数优化技术的研究 第六章基于电子线路性能的参数优化技术的研究进展 第七章均匀设计多项式拟合遗传优化算法的研究与实现 第八章本篇小结 第三篇电子线路中心化设计技术的研究 第九章电子线路中心化设计技术的研究进展 第十章基于均匀设计的重心游移法的研究与实现 第十一章基于偏最小二乘回归建模的探讨 第十二章本篇小结 第十三章全文总结和展望 第一篇遗传算法的研究 第二章遗传算法的基本概念 第三章遗传算法的基本啄理和方法 第疆章变串长与变概率遗传算法的研究 第五章本鹪小结 墨堡查堂苎主堂垡堡苎 堡二笪望堡兰生! ! ! ! 塑 2 1 引言 第二章遗传算法的基本概念 遗传算法( g e n e t i ca l g o r i t h m s ) ，又称为基因算法，它是由美国m i c h i g a n 大 学的j o h nh o l l a n d 教授在7 0 年代提出的。它是一类借鉴生物界自然选择和自然 遗传机制的随机化搜索算法，该算法源于d a r w i n 的自然选择学说。“。其以具有全 局搜索能力，并行运算能力，鲁棒性强以及优化不需要目标函数导数信息等众多 优点而得到广泛应用，尤其适用于处理传统搜索方法难于解决的复杂和非线性问 题，可用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域”1 “， 是2 l 世纪智能计算中的关键技术之一。 2 2 生物背景 生命自从在地球上诞生以来，就开始了漫长的生物进化历程。低级、简单的 生物类型逐渐发展成为高级、复杂的生物类型。这一过程已经得到古生物学、胚 胎学和比较解剖学等方面研究工作的证实。生物进化的原因有着各种不同的解释， 但被人们广泛接受的是d a r w i n 的自然选择学说。 自然选择学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括 科，内斗争、种问斗争以及生物跟无枧环境之问的q 争这三方面。在生存斗争中， 具有有利变异( m ur a t i o n ) 的个体容易存活下来，并具有更多的机会将有利变异遗 传给后代；具有不利变异的个体容易被淘汰，产生后代的机会也少得多。因此， 凡是在生存斗争中获胜的个体都是对环境适应性比较强的。d a r w i n 把这种在生存 斗争中适者生存，不适者淘汰的过程叫做自然选择。从d a r w i n 的自然选择可知， 遗传和变异是决定生物进化的内在因素。遗传是指父代与子代之间，在性状上存 在相似的现象。变异是指父代与子代之间，以及子代的个体之间在性状上或多或 少地存在差异的现象。在生物体内，遗传和变异的关系十分密切。一个生物体的 遗传性状往往会发生变异，而变异的性状有的可以遗传。遗传能使生物的性状不 断地传送给后代，从而保持了物种的特性。变异能够使生物的性状发生改变，从 凡津入学博士学位论文 第一篇遗传算法的研究 而适应新的环境而不断地向前发展。 生物的各项生命活动都有它的物质基础，生物的遗传与变异也是这样。根据 现代细胞学和遗传学的研究得知，遗传物质的主要载体是染色体( c h r o m o s o m e ) ， 染色体主要是由d n a ( 脱氧核糖核酸) 和蛋白质组成，其中d n a 又是最主要的遗传物 质。现代分子水平遗传学的研究又进一步证明，基因( g e n e ) 是有遗传效应的片段， 它储存着遗传信息，可以准确地复制，也能够发生突变，并且可通过控制蛋白质 的合成而控制生物的性状。生物体自身通过对基因的复制( r e p r o d u c t i o n ) 和交叉 ( c r o s s o v e r ，即基因分离、基因自由组合和基因连锁互换) 的操作使其性状的遗传 得到选择和控制。同时，通过基因重组、基因变异以及染色体在结构和数目上的 变异产生丰富多采的变异现象。需要指出的是，根据d a r w i n 的进化论，多种多样 的生物之所以能够适应环境而得以生存进化，是和上述的遗传和变异生命现象分 不丌的。生物的遗传特性，使生物界的物种能够保持相对的稳定；生物的变异特 性，使生物个体产生新的性状，以至于形成新的物种，推动生物的进化和发展。 2 3 标准的遗传算法 遗传算法是模拟上述生物进化过程的计算模型。由于遗传算法是自然遗传学 和计算机科学相互结合渗透而形成的新计算方法，所以遗传算法中经常使用一些 有关自然进化中的基本术语。为了更好地理解遗传算法，现介绍有关基本术语。 2 3 1 基本术语 如上所述，生物遗传物质的主要载体是染色体，d n a 是其中最主要的遗传物 质，而基因又是控制生物性状的遗传物质的功能和结构单位。多个基因组成染色 体，染色体中基因的位置称作基因座或位：( 1 0 c u s ) ，而基因所取的值又叫做等位基因 ( a l i e l e s ) 。基因和基因座决定了染色体的特征，也就决定了生物个体的性状。此外， 染色体有两种相应的表示形式，即基因型( g e n o t y p e ) 和表现型( p h e n o t y p e ) 。所谓的 表现型是指生物个体所表现出来的性状，而基因型指与表现型密切相关的基因组 成。同一科基因型的生物个体在不同的环境条件下可能有不同的表现型，因此表 现型是基因型与环境条件相互作用的结果。在遗传算法中，染色体对应的是数据 或数组，在标准的遗传算法中，这通常是由维的串结构数据来表现的。串上各 天津大学博士学位论文 第一篇遗传算法的研究 个位鬣对应上述的基因座( 或位) ，而各位置上所取的值对应上述的等位基因。遗 传算法处理的是染色体，或者叫基因型个体( i n d i v i d u a l s ) ，简称个体。一定数量的 个体组成群体( p o p u l a t i o n ) ，也叫集团。群体个体的数目称为群体的大d 、( p o p u l a t i o n s i z e ) ，也叫群体规模。而各个体对环境的适应程度叫做适应度( f i t n e s s ) 。此外，执 行遗传算法时包含两个必需的数据转换操作，一个是表现型到基因型的转换，另 一个是基因型到表现型的转换。前者是把搜索空间中的参数或解转换成遗传空间 中的染色体或个体，此过程叫做编码( e n c o d i n g ) 操作；后者是前者的一个相反操作， 叫做译码( d e c o d i n g ) 操作。表2 1 给出了自然遗传学和人工遗传算法之间有关术语 的对应关系： 表1 - l 遗传学与遗传算法之间有关术语对照表 自然遗传学人l 遗传算法 染色体( c h r o m o s o m e )数据、数组、位串 基因( g e n e )特质、个性、探测器、位 等位基因( a l l e l e s )特性值 基因座位( 1 0 c u s )串中位置 基因型( g e n o t y p e ) 结构 表现型( p h e n o t y p e )参数集、解码结构、候选鳃 遗传隐匿( e p i s t a s i s ) 非线形 2 3 2 标准的遗传算法 遗传算法是具有“生成十检测”( g e n e r a t e a n d t e s t ) 迭代过程的搜索算法，其基 本思想为：通过对初始群体进行选择( s e l e c t i o n ) ，然后进行交叉( c r o s s o v e r ) 和变异( m u r a t j0 1 q ) 产生新群体直到满足进化结束条件，其基本流程如下所示： s t e pl ：初始化根据参数编码方法，生成初始群体： s t e p2 ：计算适应度函数值计算群体中各个体( i n d i v i d u a l ) 的适应度值； s t e p3 ：选择根据个体的适应度函数值从父代中选择两染色体( 适应度函 s t e p4 s t e p5 s t e p6 s t e p7 数值越大，被选中的概率就越大) ； 交叉将选择出的两个体进行交叉操作形成两个新个体； 变异对新个体按位进行变异； 再生接受新个体并判断是否完成新群体的生成。如果没有，则返 回到s t e p3 ： 测试如果满足进化结束条件，则停止；否则返回到s t e d2 。 丕! ! _ 丈堂竖主堂焦堡塞 塑二签鲨垡簦垄笙! 世塑 由上可知，遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。 选择( s e l e c t i o n ) 、交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 是遗传算法的三个主要操 作算子。它们构成了遗传操作( g e n e t i co p e r a t i o n ) ，使遗传算法具有了其它传统方 浊所不具有的特性。遗传算法包含如下五个基本要素： 1 ) 参数编码；2 ) 初始群体设定：3 ) 适应度函数设计：4 ) 遗传操作算子设计； 5 ) 控制参数设定( 群体规模、遗传操作算子的概率等) 。这五个要素构成了遗传算法 的核。t 2 、内容。 2 4 遗传算法的主要特点口5 遗传算法具有众多的优点，这是因为它采用了许多独特的方法和技术： ( 1 ) 遗传算法的处理对象不是参数本身，而是对参数集进行编码的个体。此 编码操作，使得遗传算法可直接对结构对象进行操作。所谓结构对象泛指集合、 序列、矩阵、树、图、链和表等各种一维或二维甚至三维结构形式的对象。这一 特点使得遗传算法具有广泛的应用领域，比如： 通过对连接矩阵的操作，遗传算法可以对神经网络、自动机的结构或参数 加以优化； 通过对集合的操作，遗传算法可以对规则集合或知识库的操作而实现高质 量机器学习； 通过对树结构的操作，用遗传算法可得到用于分类的最佳决策树； 通过对任务序列的操作，遗传算法可用于任务规划，而通过对操作序列的 处理，遗传算法可自动构造顺序控制系统。 ( 2 ) 许多传统搜索方法都是单点搜索算法，即通过一些变动规则，问题的解 从j 型索空间中的当前解( 点) 移到另一解( 点) 。这种点对点的搜索方法，对于多 峰分布的搜索空间常常会陷于局部的某个单峰最优解。相反，遗传算法是采用同 时处理群体中多个个体的方法，即同时对搜索空间中的多个解进行评估。更形象 地| 兑、遗传算法是并行地爬多个峰。这一特点使遗传算法具有较好的全局搜索性 能，减少了陷于局部优解的风险。同时，这使遗传算法能进行并行计算和处理。 ( 3 ) 在标准的遗传算法中，基本上不用搜索空间的知识或其它辅助信息，而 仪用适应度函数值来评估个体，并在此基础上进行遗传操作。需要指出的是，遗 天津大学博士学位论文第一篇遗传算法的研究 传算法的适应度函数不仅不受连续可微的约束，而且其定义域也可以任意设定， 对适应度函数的唯一要求是，对于输入能计算出可以比较的非负输出。这一特点 使其应用范围大大扩展。 ( 4 ) 遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导其搜索 方向。遗传算法采用概率仅仅是作为一种工具来引导其搜索过程向着空间更优解 的区域移动。 天津大学博士学位论文 第一篇遮传算法的研究 第三章遗传算法的基本原理和方法 由第二章可知，群体个体的适应度越商，其生存的机会就越多，而通过遗传 算子操作，在下一代中产生适应度更高或者说性能更好的个体。但其为什么是这 样呢? 本章将对其运行机理作详细分析。 3 1 模式定理( s c h e m a t at h e o r e m ) 口，1 轧1 5 1 为了更好地理解模式定理，先给出有关定义： 首先，引入模式的定义。所谓模式( s c h e m a ) 是一个描述字符串集的模扳，该 字符串集中串的某些位置上存在相似性。不失一般性，考虑二值字符集 0 ，1 ) ，由 此可以产生通常的0 ，1 字符串，并且增加一个符号“，称作“无关符”( d o n tc a r e ) 或通配符，即“叫既可以被当作“0 ”，也可以被! 刍作“l ”。这样二值字符集f 0 ，1 ， 就扩展为三值字符集( 0 ，1 ，+ ，由此可以产生诸如0 1 1 1 0 、1 1 1 + * 0 1 等字符串。 定义3 1 ：基于三值字符集 0 ，l ，+ ) 所产生的能描述具有某些结构相似性的0 ，1 字符串集的字符串称作模式。 在引入模式概念前，遗传算法给人的感觉是：在某一代中，个互不相同的 串在选择、交叉和变异算子的作用下产生下一代的个新的互不相同的串。然而， 在进化过程中两代间究竟保留了什么性质，破坏了什么性质呢? 无从得知。这是 因为串都是相互独立的，互不联系的。而引入模式概念后得知一个串实际上隐含 着多个模式( 长度为，的串隐含着2 7 个模式) ，一个模式可以隐含在多个串中，不同 的串之阳j 通过模式相互联系。遗传算法中串的运算实质上是模式运算。因此，通 过分析模式在遗传算子操作下的变化，就可以知道什么性质被延续，什么性质破 丢弃，从而把握遗传算法的实质，这正是模式定理所要揭示的内容。 定义3 2 ： 模式中确定位置的个数称作该模式的阶，记作o ( h 1 。 比如模式0 1 1 + + 1 的阶数为4 ，而模式1 + + + + + 为l 。显然，一个模式的阶数越 高，其样本个数就越少，确定性就越高。 天津大学博士学位论文第篇遗传算法的研究 定义3 3 ：模式h 中第一个确定位置和最后一个确定位置之i 自j 的距离称作该 仪式的定义距，记作d ( h ) 。 比如，模式+ l + + + 0 的定义距为4 ，而模式1 + + + + 为0 。 模式的阶和定义距描述了模式的基本性质。令p o p ( t ) 表示第，代中串的群体， 以c h r o m ，i = 1 , 2 ，表示一代中第i 个个体，个体的长度为f o 、选择算子对模式的作用 假设在第，代，群体p o p ( t ) 中的模式h 所能匹配的样本数为m ，汜为m ( h ，r ) 。 在选择中，一个串( 个体) 是根据其适应度进行复制的。更确切地说，个串( 个 体) 是以概率只= 厂，进行选择的，其中，是个体c r o m ，的适应度。假设一代 中群体大小( 个体的总数) 为，且个体两两互不相同，则模式h 在第，+ 1 代中的样 本数m ( h ，r + 1 ) 为： m ( h ，h 1 ) = n m ( h ，f ) f ( h ) ，( 3 - 1 ) 其中f ( h ) 是模式日所有样本的平均适应度a 记厂2 专蕃，则有 m ( h ，t + 1 ) = m ( t t ，) f ( h ) l s( 3 - 2 ) 式( 3 - 2 ) 可知，模式的增长( 减少) ，即样本数的增加( 减少) ，依赖于模式的平 均适应度与群体平均适应度之比；平均适应度高于群体平均适应度的模式将在下 代中得以增长，而平均适应度低于群体平均适应度的模式则在下一代中减少。 又假定模式日的平均适应度h h ) 始终高于群体平均适应度7 ，并且设 商出部分为c f ，c 为常数，则有 ，”( ，+ 1 ) = m ( h ，) ( 厂+ c f ) f = m ( h ，) ( 1 + c )( 3 3 ) 不失一般性，假定从t = 0 开始，c 保持常数，那么可以得到 m ( h ，t + 1 ) = m ( t to ) ( 1 + c ) ”i ( 3 - 4 ) l | l 式( 3 - 4 ) 可知，在选择算子作用f 平均适应度高于群体平均适应度的模式将呈 天津大学博士学位论文 第一篇遗传算法的研究 指数级增长；而平均适应度低于群体平均适应度的模式将呈指数级减少。 二、交叉算子对模式的作用 由上述定义距的定义可知，模式只有当交叉点落在定义距之外才能生存。 在简单交叉( 一点交叉) 的作用下，模式h 的生存概率只= 1 一d ( h ) ( i 一1 ) ，而交叉 操作也是以一定的概率丘发生的，这样模式h 的生存概率为： p 、= l 只d ( h ) ( 1 1 ) 由于考虑到如果与个体进行交叉的配偶在某些基因位上与其本身相同 h 将被保留，因此式( 3 5 ) 给出的生存概率只是一个下界，即 只l 一只d ( h ) i ( i 一1 ) 三、变异算子对模式的作用 ( 3 5 ) 那么模式 ( 3 - 6 ) 假定个体某一位置发生改变的概率为p 卅，则该位置不变的概率为1 一p m 。而模 式h 在变异算子作用下若要不被破坏，则其中所有的确定位置( 为“0 ”或“1 ” 的位) 必须保持不变。因此，模式h 保持不变的概率为( 1 一只) o 。当巴l 时， 模式在变异算子作用下的生存概率为 只= ( 1 一只) o “m 1 一d ( h ) 只， ( 3 7 ) 结合式( 3 - 2 ) 、( 3 - 6 ) 和( 3 - 7 ) ，模式h 在遗传算子选择、交叉和变异的共同作 用下，其子代的样本数为： m ( h ，f + 1 ) m ( h ，) f ( h ) f o 1 一只d ( h ) ( 1 1 ) 】 1 一o ( h ) 只】 = m ( h ，) f ( h ) i f , 1 一只d ( h ) “，一1 ) 一o ( h ) p 卅+ f i ( h ) 】 ( 3 - 8 ) 其中，8 ( h ) = 只d ( h ) ( 1 1 ) o ( h ) e ，。忽略极小项j ( h ) ，则有 m ( h ，t + 1 ) m ( h ，f ) f ( h ) ，【1 一只d ( h ) ( i 一1 ) 一o ( h ) 匕】 ( 3 9 ) 根据式( 3 - 9 ) 并结合式( 3 - 4 ) ，可以得到模式定理： 模式定理：在遗传算予选择、交叉和变异的作用下，具有低阶、短定义距以及 平均适应度高于群体平均适应度的模式在子代中将以指数级增长。 虽然模式定理是在某些假定条件下得出来，但其是遗传算法的理论基础，给 出遗传算法的内在机理，其意义是深远的。 、，j - 人学博士学位论文笫一篇遗传算法的研究 3 2 积木块假设h 1 5 1 出上节的模式定理可知，具有低阶、短定义距以及平均适应度高于群体平均 适应度的模式在下一代中将以指数级增长。这类模式在遗传算法巾非常重要，称 么为积木块( b u i l d i n gb l o c k ) 。 定义3 4 ：具有低阶、短定义距以及高适应度的模式称作积木块。 厄如搭积木一样，这些“好”的模式在遗传操作下相互拼搭、结合下，产生 适应度更高的的个体，从而搜索到更优的可行解。 积木块假设( b u i l d i n gb l o c kh y p o t h e s i s ) ：低阶、短距、高平均适应度的模式( 积 小块) 在遗传算子的作用下，相互结合，能生成高阶、长距、高平均适应度的模式， 可最终生成全局最优解。 模式定理保证了较优的模式( 遗传算法的较优解) 的样本数呈指数级增长，从而 满足了搜索最优解的必要条件，即遗传算法存在搜索到全局最优解的可能性。而 积木块假设则指出，遗传算法具备搜索到全局最优解的能力，即积木块在遗传算 予的作用下，能生成高阶、长距、高平均适应度的模式，最终生成全局最优解。 虽然上述结论没有得到证明( 称之为假设的原因) ，但是目前已经有大量的应 h 实例支持这一假设。尽管大量的实例证据并不等于理论证明，但至少可以肯定， 对大多数经常碰到的问题遗传算法都是适用的。 3 3 编码 般来讲，遗传算法很强的鲁棒性使得其对编码的要求并不苛刻。因此，大 多数实际问题都可以采用基因呈一维的编码方式，尤其是基于 o ，1 ) 符号集的二值 编j f 冯形式。然而，编码的策略或方法对遗传操作，尤其是对于交叉算予功能有着 讯犬的影n 向。因此，不同的编码形式对实际问题的解决有着不同的效果。 天津大学博士学位论文 第一篇遗传算法的研究 3 3 。1 编码问题 图3 1 给出了问题空间和g a 空间的对应关系。问题空间是指由g a 表现型 个体( 有效的候选解) 集所组成的空间；而g a 空间是指由基因型个体所组成的空间。 在g a 空间中，个体的迁移是由交叉和变异所决定的。个体因一次变异所能迁移 的局部空间叫做变异近邻( m u t a t i o nn e i g h b o r h o o d ) ：由两个体进行一次交叉所能迁 移的局部空间叫交叉近邻( c r o s s o v e rn e i g h b o r h o o d ) 。在g a 空问中，由于交叉近邻 是由两个体决定的，因此其比变异近邻迁移要大。这正是交叉算子是遗传算法核 心操作的原因所在，使交叉算予成为遗传算法区别于其它优化搜索方法的关键。 定义3 5 ：由问题空间向g a 空间的映射称作编码( c o d i n g ) ，而由g a 空间向 倒3 1 ：空i 司映射 问题空问的映射称作译f i 6 ( d e c o d i n g ) 。 如图3 - 1 所示，从问题空间指向g a 空间的虚线表示表现型向基因型的映射或 转换，而由g a 空间指向问题空间的虚线表示基因型向表现型的逆映射或逆转换。 在g a 空间中，对父代个体鼻和e 实行交叉生成个体阳历。对f c h r o t t t 。进行逆 映射，则在问题空间中生成解个体c 加d 脚。显然，此个体己部分继承了父代只和 只的性状。 3 。3 2 编码( 译码) 评估规范和编码原理 评估编码常采用以下三个规范1 2 2 1 人学博十学位论文 讹一篇j i ! l 0 钾浊的 j | 究 , 完备性( e o m p l e t e n e s s ) ：问题空间中的所有点( 候选解) 都能作为g a 空间 t i ，的点( 染色体) 表现。 健全性( s o u n d n e s s ) ：g a 空间中的染色体能对应所有问题空间中的候选解。 非冗余性! ( n o n r e d u n d a n c y ) ：染色体和候选解一一对应。 应该指出的是，严格满足上述规范的编码方法和提高遗传算法的效率并无关 系。在某些场合，允许生成致死基因( 映射到问题空间生成无用解) 的编码，虽 然这样会导致冗余的搜索，但总的计算量可能反而会减少，从而可以更有效地找 最优解。 上述的编码评估规范虽然带有普遍的意义，但是缺乏具体的指导思想，尤其 址满足这些规范的编码设计不定能有效地提高遗传算法的搜索效率。而d e j o n g 提出的编码评估准则( 称之为编码原理) 更客观明确、可操作性更强，其规则如 下日1 ： 有意义积木块编码规则：所定编码应当易于生