（电路与系统专业论文）模拟电路自动设计的进化方法研究.pdf

摘要 摘要 电路进化设计是演化硬件( e v o l v a b l eh a r d w a r e ：e h w ) 的一个重要分支，通过 模拟自然界生物进化过程可以在无需人为干涉的条件下通过进化操作束进行电 路设计，也是演化硬件近年来的一个研究热点。然而，电路进化设计问题的研究 目前还处于起步阶段，很多问题需要进行深入的研究。如何改进电路进化设计的 收敛速度、规模和实际应用等，仍是极具挑战性的问题。本文的研究工作主要关 于模拟电路的进化设计，分别从电路的协同进化设计、基于主动偏差的容差电路 进化设计以及模拟电路的多目标优化设计几个方面进行了研究。具体而言，主要 研究工作有： ( 1 ) 针对电路进化设计中的电路规模与收敛速度问题，本论文通过调研发 现协同进化在解决复杂问题上具有很大的优势，并将协同进化机制与遗传规划相 结合提出了c o g p 进行电路设计。在此基础上，将c o g p 算法与现有的分而治 之设计方法相结合。结合后的方法能够进化较大规模电路，解决可扩展性问题， 并且提高了电路进化设计的收敛速度。多组电路进化的实验结果验证了该算法的 有效性。 ( 2 ) 模拟电路中的分立器件的器件值非常容易受到制造公差、器件老化以 及环境变化等因素的影响而发生漂移，因此模拟电路的容差设计显得非常必要。 本文从进化的角度提出了一种新的电路容差设计方法。首先，给出了器件参数漂 移的进化模型主动偏差模型，用来模仿模拟电路中器件的标称值与实际值之 间产生漂移的现象。然后，运用主动偏差模型进行电路的容差设计，提出了基于 主动偏差的混合g p 算法。使用该算法在容差设计过程中电路对器件参数漂移的 容忍范围可以通过设定器件的主动偏差范围进行设定，具有很大的灵活性。通过 实验证明该方法可以有效提高所设计电路的容差范围，且容差范围可调，在模拟 电路容差设计方面具有很大潜能。 ( 3 ) 针对模拟电路的多目标设计问题，本文实现了一种基于快速p a r a t o 排 序的多目标优化方法- n s g p 。该方法充分利用了快速p a r a t o 排序与g p 的优 点，进化过程中可以同时兼顾电路的性能和电路的规模两个目标。通过实验证明 了n s g p 方法可以一次设计出十个以上的p a r a t o 最优解，每个p a r a t o 最优解即 表示一个目标电路，表明了n s g p 在电路多目标设计中的优越性能。 关键词：演化硬件电路进化遗传规划协同优化主动偏差多目标优化 模拟滤波器 a b s t r a c t a b s t r a c t e v o l u t i o n a r yc i r c u i td e s i g ni sa l li m p o r t a n tb r a n c ho ft h ee v o l v a b l eh a r d w a r e ： e h w , i th a sa l r e a d yb e c o m ear e s e a r c hh o t s p o to fe h wr e c e n ty e a r s e v o l u t i o n a r y c i r c u i t d e s i g na p p l i e se v o l u t i o n a r yt e c h n i q u e st od e s i g nc i r c u i t sw i t h o u th u m a n i n t e r v e n t i o n ，w h i c hs i m u l a t e st h ep r o c e s so fb i o l o g i c a le v o l u t i o n h o w e v e r , e v o l u t i o n a r yc i r c u i td e s i g ni ss t i l li nt h ei n i t i a ls t a g e ，m a n yi s s u e sn e e di n d e p t h r e s e a r c h f o re x a m p l e ，h o wt oi m p r o v et h ec o n v e r g e n c er a t eo f e v o l u t i o n a r yp r o c e s s ， t h es c a l eo ft h ec i r c u i t sw ed e s i g n e d ，a n dt h ea p p l i c a t i o n s ，e t c ，a l lo ft h e ma r e c h a l l e n g i n gp r o b l e m s t h ep u r p o s eo ft h i sd i s s e r t a t i o ni st os t u d ya n a l o gc i r c u i t s a u t o _ d e s i g nb a s e do ne v o l u t i o n a r ym e t h o d s t h er e s e a r c hi n c l u d e st h ec o e v o l u t i o n c i r c u i te v o l u t i o n ，t h ec i r c u i tt o l e r a n c ed e s i g nb a s e do na c t i v ed e v i a t i o na n d m u l t i - o b j e c t i v eo p t i m i z a t i o no fa n a l o gc i r c u i t t h em a i nr e s e a r c hw o r k so ft h i s d i s s e r t a t i o nc a nb es u m m a r i z e da sf o l l o w s ： ( 1 ) i no r d e rt od e s i g nc i r c u i t sw i t hm o r ec o m p o n e n t sa n dt oi m p r o v et h es p e e d o fc o n v e r g e n c e ，t h i sd i s s e r t a t i o nh a ss t u d i e dt h ec o e v o l u t i o n t h e o r y t h e c o _ e v o l u t i o nt h e o r yw a sc o m b i n e dw i t hg e n e t i cp r o g r a m m i n g ，a n dc o g pa l g o r i t h m w a sp r o p o s e d o nt h i sb a s i s ，t h i sd i s s e r t a t i o nh a sc o m b i n e dt h ec o g pa l g o r i t h mw i t h c u r r e n td e c o m p o s i t i o nm e t h o d ，w h i c hi sa ne v o l u t i o n a r yc i r c u i td e s i g nm e t h o df o r s o l v i n gt h es c a l a b i l i t yp r o b l e m ，a n di tc a na l s oi m p r o v et h ec o n v e r g e n c er a t eo f e v o l u t i o n a r y t h ee x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h ev a l i d i t yo ft h ep r o p o s e d m e t h o d ( 2 ) i na n a l o gc i r c u i t s ，t h ev a l u eo fd i s c r e t ed e v i c e si ss u s c e p t i b l et o m a n u f a c t u r i n gt o l e r a n c e s ，d e v i c ea g i n ga n de n v i r o n m e n t a lf a c t o r s ，s ot h et o l e r a n c e d e s i g no fa n a l o gc i r c u i t si sv e r yn e c e s s a r y i nt h i sd i s s e r t a t i o nan e wc i r c u i tt o l e r a n c e d e s i g nm e t h o d w a sp r o p o s e d f i r s t l y , t h ee v o l u t i o n a r ym o d e l ( a c t i v ed e v i a t i o nm o d e l ) o f t h ed e v i c ev a l u ed r i f tw a sg i v e n ，w h i c hw a su s e dt om i m i ct h ep h e n o m e n o no fd e v i c e v a l u ed r i f t t h e n ，t h i sp a p e rc o m b i n e dt h ea c t i v ed e v i a t i o na n dg p , a n dp r o p o s e dt h e a c t i v ed e v i a t i o nb a s e dh y b r i dg p ( a d b a s e dh g p ) w i t ha d b a s e dh g pt h e t o l e r a n c er a n g eo ft h et a r g e tc i r c u i tc a nb es e ti na c c o r d a n c ew i t ht h ea c t i v ed e v i a t i o n r a n g e ，t h i si sv e r yf l e x i b l et oc h a n g et h et o l e r a n c er a n g ei nt h ed e s i g np r o c e s s t h e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h em e t h o dc a ne f f e c t i v e l yi m p r o v et h et o l e r a n c er a n g e o ft h ec i r c u i tw ed e s i g n e d ，a n dt h et o l e r a n c er a n g ei sa d j u s t a b l e ，w h i c ha l s os h o w si t s g r e a tp o t e n t i a li na n a l o gc i r c u i tt o l e r a n c ed e s i g n ( 3 ) i nt h i sp a p e r ，w ei m p l e m e n tan o n d o m i n a t e ds o r t i n g b a s e dm u l t i o b j e c t i v e a b s t r a c t g e n e t i cp r o g r a m m i n g ，c a l l e dn o n d o m i n a t e ds o r t i n gg e n e t i cp r o g r a m m i n g ( n s g p ) ， w h i c hw a su s e dt om u l t i - o b j e c t i v ec i r c u i t sd e s i g n i nt h ed e s i g np r o c e s s ，t h i sm e t h o d c a nt a k ei n t oa c c o u n tt h ec i r c u i tp e r f o r m a n c ea n dc i r c u i ts i z e e x p e r i m e n t a lr e s u l t s d e m o n s t r a t et h a t ，d u r i n ga ne v o l u t i o np r o c e s s ，n s g pc a ng i v eo u tm o r et h a nt e n p a r e t o o p t i m a ls o l u t i o n s ，e a c hp a r e t o o p t i m a ls o l u t i o nr e p r e s e n tat a r g e tc i r c u i t ，i t a l s os h o w e dt h es u p e r i o rp e r f o r m a n c eo fn s g pi nm u l t i o b j e c t i v ec i r c u i t sd e s i g n k e yw o r d s ：e v o l v a b l eh a r d w a r e ，c i r c u i t s e v o l u t i o n ，g e n e t i cp r o g r a m m i n g ， c o o p e r a t i v eo p t i m i z a t i o n ， a c t i v e d e v i a t i o n ， m u l t i _ o b j e c t i v e o p t i m i z a t i o n ，a n a l o gf i l t e r s i v 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均己在论文中作 了明确的说明。 作者签名： 签字日期：型丝! 堕? ) 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中 国学位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内 容相致。 保密的学位论文在解密后也遵守此规定i 耐公开口保密(年) 作者签名： 耄幺缸 签字同期：w 丛弗 导师签名： 肇二一 签字同期：p ，p s - f 厂 第1 章绪论 1 1 引言 第1 章绪论 所谓电路进化设计就是采用模拟生物进化的方法来进行电路设计，是一种电 路设计自动化的方法，是演化硬件( e h w ) 1 的一个重要分支。演化硬件是研 究人员受大自然的启发将进化计算引入到硬件设计中而形成的一种硬件设计方 法。演化硬件具有自适应的特性，寻求在不需要人为干涉和先验知识的条件下通 过进化操作来完成目标电路和系统的设计，在电路设计中有很大的应用前景。此 外，演化硬件在太空及深海探索等要求系统具有自适应性的领域也有着广阔的应 用前景。近年来成为国内外学者们的研究热点之一。 演化硬件之所以得到研究人员的普遍关注和积极参与有以下几方面的原因： 第一，随着集成电路技术的不断进步和人类需求的不断提高，硬件的规模和复杂 程度同益增加，传统的设计方法由于对先验知识和人工干预的依赖而显得设计能 力的不足，需要一种新的效率更高电路设计方法。第二，伴随着研究的深入，人 类对自然进化机理的掌握加深，进化计算的应用也更为广泛。第三，对太空、深 海探测等人工难以实施控制的特殊环境中需要系统具有对环境自适应的能力，常 规方法在该领域取得突破难度很大，e h w 的自适应特性表明其在该领域最有可能 获得突破性进展。第四，计算机的计算能力的不断提高，使得演化硬件的实际应 用成为可能。 目前演化硬件的研究工作主要集中在“电路的进化设计”和“硬件系统对环 境的自适应结构调整”两个方面。本论文主要对电路的进化设计在模拟电路设计 中的应用进行一些探索和研究。 模拟电路是电子系统重要的组成模块之一，在系统与外界接口以及专门处理 模拟信号的电路中必不可少。传统的模拟电路设计是建立在设计者拥有丰富的先 验知识基础上的，其设计流程如图1 1 所示。传统的设计流程中无论是电路拓扑 结构设计和器件的选择，还是后期的样品电路测试都需要设计者有丰富的经验， 并且需要耗费很长的设计与测试时l b j 。因此，传统的设计方法必然会面临下列必 需解决的矛盾。首先是设计能力与制造能力之间的矛盾，随着集成电路技术和工 艺的不断进步，电路的规模和复杂程度r 益增加，传统的模拟电路设计方法的设 计能力已经显得明显不足。其次是系统的复杂性与更新换代之间的矛盾，随着社 会的不断进步人们对于系统的性能要求不断提高，这必将导致系统的复杂性的增 第1 章绪论 加，从而加大设计难度，然而激烈的市场竞争又要求能够以最快的速度设计出产 品，缩短设计周期。面对传统设计方法所存在的矛盾，一个可行的方法是将演化 硬件( e h w ) 引入模拟电路设计，即模拟电路的进化设计。 足 固 图1 1 传统电路设计流程 1 2 电路进化设计的原理与研究进展 1 2 1 电路进化设计的基本原理 目前电路进化设计方法的设计步骤比较固定，电路的进化设计具有明显的生 物学背景，是e h w 研究的两个主要分支之一，电路进化设计通过模仿自然界中生 物进化来实现电路的自动设计，是一种全新的电路设计方法，其设计一般流程如 图1 2 所示。目前，电路进化设计的进化方式主要有两种，即外部进化和内部进 化。所谓内部进化就是进化过程是在实际的可配置和可编程的电路中进行( 如使 用f p g a 、c p l d 等硬件平台) ，并采用基于硬件配置和实测的适应度评估方式。 而外部进化则是指采用基于电路模型和软件仿真的适应度评估方式，需要选择适 用的电路仿真软件( o l m a t l a bs i m u l i n k 、s m a s h 、p s p i c e 等) ，并按照进化算法的 要求精心对目标电路进行编码。 由于电路进化设计的本质是模拟生物进化中的优胜劣汰过程，所以我们可以 将它归纳为如下的步骤：首先，分析需求给出电路的预期行为；第二，对电路结 构和相关参数( 器件值等) 加以编码并施加进化操作；第三，根据所设计电路的 要求设定适应度评估标准，并对进化过程中的个体进行评估，以实际行为与评估 2 第1 章绪论 标准的符合程度作为适应度评估的依据；第四，根据适应度值实施进化操作，产 生新的候选解；第五，重复第三步和第四步直到搜索获得具备预期行为的电路为 止。 图1 2 电路进化设计流科 当前用于电路进化设计的主要算法是遗传规划( g e n e t i cp r o g r a m m i n g ) 【2 4 ，2 5 】 与遗传算法( g e n e t i c a l g o r i t h m ) 2 3 ，3 0 ，3 1 。运用遗传算法对电路进行编码时采 用二进制位串方式，这种二值位串染色体的结构与数字电路中的高低两种状态具 有一致性，并且使用起来比较直观和方便，这种编码方式叫做直接编码。运用遗 传规划对电路进行表示时采用的是树状结构染色体编码，这种编码称作i 甸接编 码，可用于对模拟和数字电路的编码表示。如何改进进化算法的性能，特别是进 化速度和收敛率，使之更加适用于电路进化设计，是非常值得研究的问题。 1 2 2 电路进化设计的的研究进展 毫无疑问，任何一种学科都是在实践中产生并且在实际应用中得到不断的改 进和发展，电路的进化设计也不例外。从上个世纪九十年代初期同本和瑞士科学 第1 章绪论 家正式提出演化硬件 2 的概念至今，学者们在电路进化研究领域耿得了很多方 面的研究成果，同时也促进了进化电子学的发展【1 ，5 】，下面对具有代表性的电路 进化设计方法进行描述与简单的概括。 在电路进化设计领域，应用最为广泛的两种算法是遗传规划( g p ) 和遗传 算法( g a ) 。 其中，在g p 电路进化设计方面的研究中，k o z a 等的研究最具代表性也是该 领域中取得成果最多的团体 3 ，4 ，6 ，3 4 ，3 5 。k o z a 最早提出遗传规划概念，他与 他的学生们以用于构建电路的树状结构为进化对象，初始化的个体中仅包含有输 入、输出、信号源、负载和可修改连线的最简单电路信息，通过不断地对电路的 “可修改连线”进行修改操作，使所进化的电路得以扩展和变化；进化过程中适 应度评估通过电路仿真软件s p i c e 来实现。使用该方法，k o z a 等成功设计出滤波 器、放大器、温度传感电路等实用电路，部分电路与人工设计的专利电路相比结 构与功能都很相似，但是其缺点是进化的计算较复杂度较大，用s p i c e 进行仿真 所需的时问过长。 通过对k o z a 等工作的进一步研究，h o u ，c h a n g 等将电路结构限制为串并 联r l c ( r 一电阻，l 一电感，c 一电容) 网络结构，采用二叉树编码和g p 求解技术 1 3 。相比之下，结构约束的自动设计方法缩小了搜索空问，可避免电路合法性 检查又能对电路直接进行快速的分析。但是该方法是以对结构进行约束为自玎提 的，其优点是不需进行s p i c e 仿真，使得每一代的进化时间大为减少，但是适应 度评估次数( 计算复杂度) 依然较大。除此之外，h o u 还对电路容差、阻抗匹配、 以及在高频条件下电路的寄生效应等方面进行了研究 3 6 ，3 7 。 在运用g a 算法进行电路进化设计的研究方面，g r i m b l e b y 提出基于网表编 码的混合g a 综合方法，通过限制遗传操作的过程来避免产生非法个体。混合 g a 是指运用g a 进行电路的拓扑结构的设计，用数值优化的方法来进行器件值 的确定，即把电路的拓扑结构设计和器件值选择分开进行 8 ，9 。l o h n 等提出了 基于线性表示的g a 综合方法 7 ，通过使用特定结构来构造电路从而避免产生 非法个体。特别值得肯定的是该文中给出了三端非线性器件( 三极管) 的编码方 案，三极管被作为5 0 余种组态的双端元件来使用，三极管的第三端固定地与电 源、地、输入、输出或前一节点相连接。因此，使用该方法进行电路设计可选用 的元器件包括电容、电阻、电感和三极管等。 在内部进化的研究方面，t h o m p s o n 等 5 在硬件平台上运用进化的方法设计 音调识别器，通过内部进化得到了能够区分1 k h z 和1 0 k h z 两种频率的电路，电 路性能符合设计要求，该设计中将现有的一些电路设计经验引入了电路的进化过 程。同时，该实验揭示出进化结果对器件、环境温度和工作电压等的依赖性，因 4 第1 章绪论 此研究者对e h w 对环境条件的适应性给予了更多的关注。此外，在内部进化的 研究中，s t o i c a 等 1 0 ，11 主要利用现场可编程晶体管阵列( f p t a ) ，通过实验对 模拟电路和数字电路的内部进化方法进行了研究。提出了“混合进化( m i x t r i n s i c e v o l u t i o n l ” 1 2 方法政方法在每一代都对部分个体实施内部进化而对其余的 个体实施外部进化，用以弥补外部进化( 电路仿真) 存在的不足。并且建议利用 “混合进化”束发现和奖励那些在实测和仿真时具有不同性能的个体，以便找出 仿真软件尚不支持的新奇电路特性。其中f p t a 的基本结构如图13 所示，阵列 中晶体管的连接通过开关实现，图中用s i 柬表示。g a 中电路染色体编码由二进 剖串s l ，s 2 ，s 3 ，s 组成。表示f 巳路中各丌关的扣开和闭合情况s 1 为0 表示第i 个丌关为断开，为“l ”时表示闭合。可见该设计方法采用的是直接编 码方式。 。i 丑f 气叫二 ，! 藩铲刊 图13f p t a 的基本单元 国内在电路进化设计方面起步较晚，与发达国家相比还有一定的差距，但是 进步较为明显，取得了较好的成果。目前已有的研究成果主要包括：中国科学技 术大学的王煦法教授等人在硬件进化算法模型 1 9 、基于e h w 的无损图像压缩 2 0 和硬件电路的冗余容错设计 2 i 等方面进行研究；武汉大学的李元香等 1 4 讨论了e h w 涉及的主要问题和有关研究方向i 深圳大学朱明程等 15 研究了 f p g a 动态可重构技术，以及基于该技术的数字电路系统容错方法；西安电子科 技大学的赵曙光研究了基于函数变换的最小项编码方案 1 6 武汉大学康立山等 1 7 ，1 8 提出了基于“树型结构函数”的函数型可编程器件概念，在g a l 型门缴、 函数级数字电路的函数型编码方案，并且进行了外部进化实验：清华大学钟国安 等 2 2 研究了基于硬件实现的基因算法。总体上说，现阶段国内电路进化设计研 究的发展势头良好。但是研究的深度和广度均与国际先进水平有较大差距，因此 在这一重要领域开展较为系统和深入的研究更为必要和迫切。 j 5 | o ，i ，一 毫i j 竺 第1 章绪论 1 3电路进化设计存在的问题 目前，电路进化设计的相关研究已经取得了很大进展，然而，运用进化的方 法所设计的电路在实际中却很少有应用。电路进化设计实际应用的主要障碍是进 化的计算复杂度过大、收敛速度慢，其直接结果是所设计的电路功能过于简单， 实际应用的空间较小。 以模拟电路的进化设计为例，至少存在如下一些问题需要做进一步研究和解 决： ( 1 ) 模拟电路进化设计的规模和计算复杂度之i 日j 的矛盾； ( 2 ) 现有的电路设计经验是否可以应用到模拟电路进化设计中去； ( 3 ) 染色体编码方式，找出更适合对电路进行编码的方法： ( 4 ) 运用进化方法进行电路稳定性设计的模型的建立，如容差、容错模型 的建立等； ( 5 ) 模拟电路设计是一种典型的多目标设计，应该对模拟电路的多目标设 计进行研究，给出可以实现的方法； ( 6 ) 模拟电路进化设计实际应用的基本流程以及其余现行电路设计方法之 间的联系和区别； ( 7 ) 计算机的训算速度的有限也是影响模拟电路进化设计发展和实际应用 的一个重要方面。 以上所提到的问题是电路进化设计研究中比较普遍且尚未得到很好解决的 问题，因此，当前我们应该更多地围绕上述问题展开有针对性的研究。在研究的 过程中要密切关注演化研究研究领域及相关领域的最新进展，注意借鉴有关的研 究成果，进而促进电路进化设计更好更快地发展。 1 4 本文的研究工作与组织安排 模拟电路进化设计是一个新的研究领域，可以为电路设计提供一个全新的设 计方法。由于其正处于起步阶段，所以有很多问题需要进一步研究，上一节在对 电路进化设计进行调研的基础上指出了一些存在的问题。针对存在的问题本文尝 试用遗传规划算法对模拟电路进化设计进行研究。论文的研究工作主要有以下几 个方面： ( 1 ) 由于模拟电路进化设计随着规模的增大，搜索解的范围呈指数增长， 所以规模问题一直是模拟电路进化设计的瓶颈；协同进化对于解决大规模复杂问 题具有很大的优势，所以我们将协同引入复杂电路进化的设计。 6 第1 章绪论 ( 2 ) 电路中的元器件的实际值与标称值难免存在公差，这一点在由分立器 件构成的模拟电路中显得尤为突出，这必将导致实际电路与设计电路的性能之间 存在差异，进而影响产品的稳定性；同时由于环境影响以及产品老化也将使得器 件值与标称值发生偏移，鉴于以上分析在设计电路时对电路的容差性能加以考虑 很有必要。 ( 3 ) 模拟电路设计是一个典型的多目标问题，因此对模拟电路多目标设计 进行研究很有必要。文中我们通过把g p 与非支配排序相结合来处理电路设计中 的多目标问题。 本文共分为六章，下面我们介绍个章节的内容安排。 第一章简要介绍了电路进化设计的研究背景、基本原理以及电路进化设计的 研究现状，指出目前电路进化设计存在的不足，并且给出本论文所要研究的主要 内容。 第二章简要介绍了遗传规划的基本原理，及其在模拟电路进化设计应用中的 一些基础知识，为本论文后面章节运用遗传规划进行模拟电路进化设计的相关研 究及改进提供基础。 第三章针对电路进化设计的规模与搜索空间( 电路进化的速度) 这一矛盾， 研究了电路进化的协同设计。通过采用基于分治的协同设计可有效改善电路进化 设计中规模效应问题。 第四章研究了电路容差设计问题。首先介绍了传统进化方法在进行电路容差 设计中存在的不足以及导致所设计电路容差性能不理想的关键所在。提出了一种 新的进化设计思路主动偏差思想，利用主动偏差思想可以有效解决进化容差 设计中参数漂移建模的问题。通过实验验证了方法的有效性。 第五章研究了电路进化设计中的多目标设计。论文将快速非支配排序算法引 入遗传规划算法，实现了一种可用于模拟电路设计的多目标进化算法。 第六章对全文进行总结，指出研究中存在的不足，并据此对下一步的研究工 作进行展望。 7 第2 章基丁遗传规划的模拟电路设计基础 第2 章基于遗传规划的模拟电路设计基础 2 1 遗传规划概述 遗传规划( g e n e t i cp r o g r a m m i n g ) ，又称之为遗传程序设计，是2 0 世纪九十 年代初，美国斯坦福大学的k o z a 教授基于自然选择的原理，所提出的一种用层 次化的计算机程序来表达问题的遗传程序设计方法。随后，k o z a 教授又发表了 多本关于遗传规划的专著 2 4 ，2 5 ，3 8 ，深化了遗传规划的研究，k o z a 和他的团 队运用所提出的g p 算法成功地解决了许多实际应用问题，其中最著名的是g p 在电路设计中的应用。同时，一些与之相关的代表性的研究成果也相继出现，使 程序设计自动化展现了新的局面。近年来，随着遗传规划研究的不断深入和发展， 学者们研究解决了很多实际问题，如电路自动设计、工业控制、图像处理、经济 学和数掘管理等e 3 ，2 6 - 2 9 ，这些问题往往很难用常规方法来解决。遗传规划 自首次提出至今，已经引起人工智能和计算机等相关领域越来越多的国内外学者 们的浓厚兴趣。 2 1 1 遗传规划的个体 初始种群所包含个体的数量，即种群规模，要视具体问题而定。种群中的个 体采用分层的树状结构，也称为程序树。种群由程序树组成，而程序树由节点构 成。图2 1 中根节点分别为和+ ，这种树状结构的层次一目了然。程 序树的节点可以分为两大类，功能节点和终端节点。图2 1 所示的树状结构中没 有子节点的节点为终端节点，如 x ，y ，z ；带有子节点的为功能结点，如 ，+ 。功能节点是各种函数或者功能单元( 完成程序相应功能的函数) ：根 据其子节点的数目，功能节点又可以分为一元节点、二元节点和多元节点。终端 节点则是变量或者常数( 从事先确定的终止符集t 中选取) 。 ；j z i j。“ ，八 图2 1 两个树状结构个体 9 ，、 ，_ 第2 章基t 遗传规划的模拟电路殴计基础 21 2 遗传操作 种群中每个个体的结构和内容都是动态变化的这是由遗传操作束实现的。 与遗传算法相同，遗传规划常用到的遗传操作有3 种，分别是：复制、交叉和变 异。 “) 复制。复制的作甩是保留父代种群的遗传信息。复韵l 过程出两部分组 成：第一部分根据适应度，从当自口种群中选出一个父代个体常用的选择力浩 有贪婪法、级差往、竞争法等：第二部分，将被选出的父代个体不傲任何变化直 接从当前代复制到下一代种群中去。 j ? 义 yx 图2 2 变义后的于代个体 ( 2 ) 交叉。交叉的作用是通过交换两个父代染色体中的部分信息获得新个 体的过程。交叉操作可以描述为：选择两个个体作为父辈个体，假定为图2 1 中的两个个体；确定两个父辈个体用于交叉的子树，分别为图21 中a 和b 方框 中部分：将圈21 中a 和b 两棵于树进行交叉即得到图22 所示的两个新的子代 个体。在电路设计中交叉的作用是改变电路的拓扑结构。 ( 3 ) 变异。变异的作用是在进化中通过完变的方式柬改变某个父代个体的 遗传信息。变异操作可分为以下3 步：第一步，选择一个树状结构个体，作为突 变操作的父代：第二步，从待变异的父代个体中选择的一个突变点，图23 中a 树状结构的方框部分；第三步，删除突变点及其以下的程序树分支，用随机产生 的程序树替代，得到一个新的子代如图23 中b 树状结构所示。突变操作过程 见图23 其中a 个体为突变前父代个体，其节点3 为突变点；b 个体为突变后 的子代个体。 第2 章墓r 遗传规划的模拟电路垃计基础 2 13 遗传规划的特点 图2 3 变异操作示意酗 遗传规划在遗传算法的基础上发展而来，继承了遗传算法的基本思想【3 2 ， 它与遗传算法的差别主要在于它以可变长度的树状结构束对种群中的个体进行 编码表示。遗传规划克服了遗传算法的一些不足，同时与遗传算法也具有一定的 区别，主要表现在以下几个方面： ( 1 ) 遗传规划的程序结构不再考虑等位基因的位置，这使得遗传规划能够动 念改变大小、形状。相比之下，采用定长的字符串描述方法的遗传算法不具备动 态可变性，每一种特定的字符串结构仅适用于某类问题的求解。 ( 2 ) 遗传规划在进行树状结构染色体编码时，构成树状结构的节点类型分为 两类：一类是终端节点( 在电路进化中表示电路元器件) ，另一类是功能结点( 在 电路进化中表示电路中的连接信息) 。 ( 3 ) 遗传规划的适应度评估也就是树状结构染色体所表示程序的运行结果。 ( 在电路进化设计中也就是相应电路的功能输出) 。 ( 4 ) 在遗传规划中用于改变个体性状的遗传操作算子主要是交叉和变异，并 且使用较多的是交叉算于。其中在电路进化设计中交叉葬于主要用于改变电路的 拓扑结构，而变异算子则主要用于改变电路元器件的器件值。 22 基于g p 的树状结构对电路进行表示 g p 的最大特点是采用动态变化树状染色体表达问题，运用g p 进行模拟电 路的自动设计其核心就是用树状染色体柬表示所要综合的目标电路，我们应用 g p 进行电路综台的模板咀及树状结构模型如图2 4 所示，图中的e v o l v e dt r e e 第2 章基丁遗传规划的模拟电路设计基础 即是所要进化得到的目标电路，图2 4 ( b ) 所示为目标电路的树状结构表示，其中 r s 和r l 分别表示源电阻和负载电阻，其值在文中均取lq 。 + v i n + v 叫 ( a ) 原理图( b ) 树状结构 图2 4g p 进化电路模板 玉6 ( a ) 传统方法 6 由6 由 ( b ) 基因单元法法 图2 5 两种不同的基冈表达 把目标电路用树状结构染色体进行表示，则每个树状结构中的节点表示相应 电路的元器件或电路的连接属性，因此我们把树的结点分成终止节点和功能节 点。其中每个节点表示一个基因，终止节点表示电路的元器件，功能节点表示电 路的连接特性，在此基础上我们给出由r l c 等基本元器件构成的滤波器电路的 树状结构表示。传统的r l c 滤波器设计所采用的终端结点仅仅包括r ，l ，c 三 种基因类型，其中r 固定作为源电阻或负载电阻，然而实际上滤波器电路中会 有l + c ( l 串c ) 和l c ( l 并c ) 作为基本电路单元经常出现，所以我们在终端 结点的表示上增加了u 和l c 两个基本单元作为新的基因类型我们称之 为基于单元的基因表示。即功能结点函数符包括f + ，) 分别代表串联和并联，终 端结点终止符包括f r ，l ，c ，l + c ，l c 分别表示电阻( 固定作为源电阻或负 载电阻) ，电容，电感，电容与电感串联，电容与电感并联，如图2 5 ( b ) 所示。 采用本章所提出的基于单元的基因表示可以有效减小解空间的大小。当图 2 6 ( a ) 所示滤波器电路需要一个l + c 电路单元时，采用传统g p 的树状结构表 1 2 第2 章基丁遗传规划的模拟电路设计基础 示至少需要三个结点，见图2 5 ( a ) ，且其中的3 个“? ”必须完全符合所需的结 点类型，每个“? ”均取自 “+ ，”，“l ，c ”) 中，所以用传统方法币确表示 一个l + c 的解空间为4 * 4 * 4 = 6 4 ，如果采用基因单元法表示则至少只需一个结点， 如图2 6 ( b ) 所示，每个结点均取自 “+ ，”，“l ，c ，l + c ，l c ”) ，则解空 问仅为6 。通过上述分析我们可以得出采用所提出的方法与传统的g p 相比产生 所需的基本单元的解空间明显减小，进化出同样规模的电路的搜索解空| 日j 也必然 会明显减小，因此与传统基因表示方法相比搜索出同样电路的效率得到提高。 ( a ) 树状结构 图2 6r l c 低通滤波器 2 3g p 树状结构的电路分析算法 ( b ) 电路原理图 在进化过程中我们需要对每个树状结构所表示的电路进行分析进而计算每 个个体的适应度值。在设计滤波器时我们采取分析电路的幅度频率响应，则当频 率为w 时对图2 6 所示的树状结构的幅度频率响应分析按如下步骤进行： 1 ) 计算各终端节点的阻抗值：对于给定频率，四种终端节点的阻抗值可按 ( 2 1 ) 式计算： | j w l ,抓d 乃= j 1 7 肥 狄c ) lj w l + 1 j w c , i f ( l + c ) ( 2 1 ) 【1 ( 1 j w l + j w c ) ，圹( l c ) 其中l 和c 分别表示终端节点器件值的大小，器件的值均取射0 2 ，5 】之间 对数分布的取值序列。 2 ) 计算各功能节点的阻抗值：除去终端节点，剩下的所有节点均为功能节 点，功能节点的阻抗值计算按照树状结构分布自底向上依次计算，两类功能节点 第2 章基丁遗传规划的模拟电路设计基础 的阻抗按公式( 2 2 ) 进行计算： z 夕= z 1 r ( 1 + z z 。r + 。，z ，爹苫z c 2 2 ， 其中z r 表示功能节点的右孩子节点的阻抗值，z j 表示功能节点的左右孩子 节点的阻抗值。 3 ) 计算各节点电压：根据电路分析理论阻抗的分压原理可以依次计算出各 个节点的电压值，进而最终得出输出负载的电压，计算出电路的电压幅频响应 2 4 适应度计算 种群中的每个树状染色体在按上述步骤完成分析计算后，接下来便要进行个 体的适应度评估，计算适应度值的步骤如下： 1 ) 在通带和阻带中按照对数分布分别取5 0 个频率抽样点； 2 ) 计算每个抽样点的电压增益a o u t ( i ) ，标准值为s ( i ) 与设计要求的增益相 减得出差e r r o r ( i ) ，并对所得的差乘以一个惩罚系数w i ； 3 ) 将所有抽样点的误差绝对值的相反数求和得出适应度函数 。n 一f f i t n e s s = 一：lw i * e r r o r ( i ) i ， ( 2 3 ) f = l 其中e r r o r ( i ) = a o u t ( i ) s ( i ) ，n 伪所有抽样点的个数。 2 5本章小结 本章简要介绍了遗传规划的基本原理，及其在模拟电路进化设计应用中的一 些基础知识。文中分析了遗传规划在进行电路树状结构编码过程中的方式和特 点，并分析了传统遗传规划染色体基因表示方法存在的不足。通过分析，本章给 出了一种新的基因表示方法基于单元的基因表示法，该方法可以降低模拟电 路进化设计的搜索解空间大小。随后本章第三节和第四节分别给出了模拟电路进 化设计的电路分析算法和适应度评估方法，为本论文后面章节运用遗传规划进行 模拟电路进化设计的相关研究提供基础。 第3 章基丁分而治之的协同电路设计方法研究 第3 章基于分而治之的协同电路设计方法研究 3 1引言 电路设计总的来说可以分为数字电路设计和模拟电路设计，模拟电路是电子 系统重要的组成模块之一，在系统与外界接口以及专门处理模拟信号的电路中必 不可少。模拟电路设计的自动化是电路设计自动化中必不可少的组成部分，然而， 与数字电路设计相比，模拟电路设计的自动化程度依然很低，其设计能力也显得 不足。模拟电路的进化设计是演化硬件的一个分支，具有自动化水平高、对人工 干预依赖少等优点，运用进化方法进行模拟电路设计是模拟电路设计自动化的一 条有效途径，也是演化硬件的热点研究领域之一。电路进化设计的主要思想可以 看作是一个优化搜索问题，其任务是从一个包括所有可能解的解空问中搜索出满 足要求的电路( 包括电路的拓扑结构和器件值) 。由于电路进化设计的搜索空间 随着电路的规模呈指数增加，因此，运用进化方法所设计出的电路普遍存在的一 个问题是所设计出电路的规模较小，且计算复杂度很高，规模问题成为电路进化 设计必须解决的一个问题。为了解决该问题学者们一直在不懈地研究 【3 , 7 ，9 ，1 3 ，4 1 ，研究取得了一定的进展，所设计电路的规模在不断的增大，然而计 算复杂度依然较大。 随着技术的进步和人类需求的不断增长，提高模拟电路的规模和性能是电路 设计领域的一个重要任务，因此模拟电路进化设计面临一个亟待解决的问题 电路规模与计算复杂度这一矛盾。协同进化( c o e v o l u t i o n ) 4