（信号与信息处理专业论文）改进gp在电路建模中的应用研究.pdf

改进g p 在电路建模中的应用研究 摘要 在电子线路与电子系统计算机辅助设计分析中，自动构造各种电路元件和 系统的模型是进行仿真分析的基础。根据电路元件和系统的输入输出数据，借助 于电路建模方法建立高精度的等效模型，对于复杂电路器件和系统的仿真分析具 有重要的现实意义。g p 算法相对于传统的电路建模方法具有更为灵活的描述能 力，且可以不需要先验知识以较优的精度获得多个模型，因此本文采用g p 算法 进行电路建模。 本文主要研究内容有： 1 改进标准g p 算法，用并行变异代替基本的变异操作。并行变异将多种变 异操作其相互结合，并行运作产生子代。这种方式能够综合发挥各种算子的优势 显著改变进化个体的结构，增加群体的不同模式并维持其多样性，促进进化过程 收敛到全局最优解，达到提高收敛速度的目的。对改进g p 算法的收敛性进行分 析，证明了采用保优策略的改进的g p 算法以概率1 收敛到全局最优解，为解决 电路建模问题提供了理论依据。 2 将改进g p 算法应用于电路建模。采用模拟和数字两种不同电路的建模试 验例子测试改进算法。对比结果显示改进算法在无先验知识的条件下，与实验统 计法相比可以获得多个电路模型，同时精度上质量更优。与标准g p 算法相比具 具有更快的收敛速度。 关键词：等效模型，遗传编程，并行变异 t h ea p piic a tio ns t u d yo f im pr o v e dg pincir c uit m o d eiin g a b s t r a c t w h e nt h ec i r c u i ts y s t e mi sc o m p l i c a t e da n di t sf u n c t i o ni sh a r dt ou n d e r s t a n d ，t h e e s t a b l i s h m e n to fc i r c u i te q u i v a l e n tm o d e li st h ek e yt os i m u l a t i o na n a l y s i s 。c o m p a r e d w i t hs t a n d a r da l g o r i t h m s ，t h eg pi sm o r ef l e x i b l ea n di tc a ng e tav a r i e t yo fm o d e l s t r u c t u r ew i t h o u tp r i o rk n o w l e d g e i nt h ep a p e r , t h em e t h o db a s e do ng pi su s e di n c i r c u i tm o d e l i n g m a i nw o r k si nt h i sp a p e ra r ei l l u s t r a t e da sf o l l o w s 1t h ei m p r o v e dg pa l g o r i t h m si sp r o p o s e da n di ts u b s t i t u t es t a n d a r d sm u t a t ef o r p a r a h dm u t a t e t h ei m p r o v e dg pc o m b i n ek i n d so fm u t a t i o no p e r a t i o nt og e n e r a t e o f f s p r i n g t h i sa l g o r i t h m sc o m p r e h e n s i v eb r i n ga l lt h ea d v a n t a g e so fo p e r a t o r sa n d c h a n g et h es t r u c t u r eo b v i o u s l y i ta l s oi n c r e a s e sd i f f e r e n tm o d e l sa n dm a i n t a i n i n d i v i d u a l sd i v e r s i t ya n dm a k et h ea l g o r i t h m sa c h i e v et h ep u r p o s eo fi m p r o v i n g t h ec o n v e r g e n c er a t e b ya n a l y z i n gt h ec o n v e r g e n c eo ft h ei m p r o v e dg p ，i t p r o v i d e sat h e o r e t i c a lb a s i sf o rc i r c u i tm o d e l i n g 2t h ei m p r o v e dg pi su s e di nc i r c u i tm o d e l i n g t w oi n s t a n c e sa r eg i v e nt ot e s tt h e i m p r o v e dg p c o m p a r e dw i t ht h ee x p e r i m e n t a ls t a t i s t i c a lm e t h o d s ，t h er e s u l t s s h o wt h a tt h ei m p r o v e dg po b t a i nm a n ym o d e l sw i t h o u tp r i o rk n o w l e d g ea n dt h e p r e c i s i o ni sb e t t e r c o m p a r e dw i t ht h es t a n d a r dg p ，t h ei m p r o v e dg p i sf a s t e ri n c o n v e r g e n c er a t e k e y w o r d s ：c i r c u i tm o d e l i n g g e n e t i cp r o g r a m m i n gp a r a l l e lm u t a t i o n n 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含其他教育机构的学位或证书使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名：雍乏 签字日期：加莎年斗月p 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信息 研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公 众提供信息服务。 学位论文作者签名：霭乞 签字日期：加万年彳月e l 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签字：1 龙j 彦炎 签字日期：年月 电话： 邮编： 杂坞照 日 改进g p 在电路建模中的应用研究 1 绪论 随着集成电路制造技术的不断进步，电路的规模和复杂程度日益增加。近 几年迅速发展起来的电子设计自动化技术( e d a ) ，使得电子线路的设计人员能在 计算机上完成电路的功能设计、逻辑设计、性能分析、时序测试直至印刷电路板 的自动设计。这就需要对电路器件进行仿真分析。为了进行电路仿真，必须先建 立元器件的模型，也就是用数学模型代替物理上存在的具体的器件。这种数学模 型应该能够正确的反应器件的物理特性和电学特性，并且便于在计算机上进行数 值计算。因此，数学模型的建立便成为电子线路与电子系统计算机辅助设计分析 的关键。本文利用遗传编程( g e n e r i cp r o g r a m m i n g 简称g p ) n m l 方法来建立电路 的数学模型。 1 1 电路建模现状 通常把电路建模方法分为两大类。即机理分析法与实验统计法嘲。机理分析 法又叫直接分析法或解析法，是一种应用的最为广泛的建模方法。这类方法适用 于那些内部结构和特性清楚的系统。该方法由以下几个步骤组成：分析器件或 电路系统的功能和原理。找出系统的输入变量和输出变量。按照系统遵循的 物理规律写出各个部分的微分方程。消除中间变量，从而得到近似的数学模型。 文献 4 采用机理分析的方法建立电路的方程，用数值逼近和最小二乘的方法识 别方程中的等效参数。但是这种方法需要事先知道电路的结构，而大多数的电路 其结构非常复杂或者根本无法得知其结构。因此，这类方法具有较大的局限性。 试验统计方法不考虑器件或电路的具体结构，通过对器件或电路不同工作状 态下的测量得到输入输出数据，根据这些数据构造数学模型。目前由于电路的功 能与性能的不断提高，因此机理分析建模方法遇到许多困难，而试验统计方法由 于不受内部结构的影响因而成为重要的建模工具。目前，此类方法广泛应用于电 路系统建模的数学建模。文献 5 采用数学伴随方程的方法构造电路的等效模型。 该法采用黑盒技术，用分段高次线性代数伴随方程取代宏电路和数据的传统模式 来构成各种电路元件和电路系统的外特性方程模型。该模型在保证精度的前提下 改进g p 在电路建模中的应用研究 大大地减少了计算量和内存量，而且容易实现构模的自动化。文献 6 采用向量拟 合法有理逼近网络函数。向量拟合在进行逼近时求解的不是关于分子分母系数的 一组方程，而直接是有理函数的极点与留数。这原是一个非线性问题，但向量拟合 法通过一个辅助函数的引入，将问题转换为线性方程的求解，就可以解决矩阵病 态的问题。由于这一特点，使这种方法可实现几乎任意高阶的逼近。文献 7 利用 代数节点方程确定系统结构，利用小波配置方法建立系统模型。使系统行为级建 模具有更高的精度。 近年来人工神经网络在众多领域得到广泛应用阳钔，这一技术也被用于器件 与电路的建模。神经网络系统是由大量的同时也是很简单的处理单元( 神经元) ， 通过广泛的互联形成的复杂网络系统：神经网络具有学习功能，可模拟复杂的非 线性函数关系，许多类型的神经网络是通用逼近器，能以适合的精度逼近任意输 入输出映射。文献 i o 采用b p 神经网络对系统进行预测建模，取得了良好的效 果。文献 1 1 采用r b f 神经网络作为建模工具对微波电路进行建模、优化。r b f 网络具有良好的局部性，能提供平滑、性能优秀的离散数据内插特性，由该网络构 成的系统是有界、稳定的。该网络可以提供完备的、最优逼近功能。但是，其在 针对具体的建模问题时，需要人为地假定和修改网络结构，凭借经验选取隐含层 的结点个数，隐含层的层数和神经元的激励函数等。由于数据集变量间的函数关 系隐含于网络内部，不能够直接得到输入输出变量的显式变化规律，不利于对系 统的机理分析，在解决实际建模问题存在着一定的局限性。 以上方法各具特点并在不同程度上取得了成功。但所研究的问题如缺乏先 验知识或者模型具有强非线性时，采用机理分析法与实验统计法所建的模型精度 可能较差，虽然神经网络有较好的拟合精度，但是它的模型表达形式是隐性的，不 直观 g p 算法用于建模时具有较为灵活的描述能力，可以不需要先验知识以较优 的精度获得多个模型，便于对模型进行分析。因此使用g p 算法建模是具有优势 的。 2 改进g p 在电路建模中的应用研究 1 2 g p 概述 1 2 1g p 基本思想 g p n 2 1 是一种在遗传算法基础上发展起来的模拟生物进化过程的非线性系统 结构优化搜索算法。其搜索过程从本质上属于随机搜索，但其空间遍历性比传统 的启发式搜索要好，遗传操作使得路径可随机跳跃到不同的子空间，从而在全局 空间中以若干搜索集的并集方式从时序过程方面逼近全集。g p 的基本进化思想 是：随机产生一个适合于给定环境的初始群体，即问题的搜索空间，该初始群体 由某种遗传结构形式表示，例如树型结构、线性结构等；与遗传算法类似，构成 群体的个体都有一个适应度值表示该个体的性能优劣，依据达尔文适者生存原 则，用遗传操作算子处理得到的高适应度的个体，产生下一代的群体，如此进化 下去，给定问题的解或近似解在某一代上出现。g p 的一次运行并不能保证能够 得到问题的解，如何确定控制参数使遗传程序设计达到最佳效果，这与所给问题 环境有关，通常需经多次反复实验而定，所以说g p 算法是一种与实验相关的算 法。 g p 具有自组织、自适应和自学习等智能特征及其本质并行性，可以根据建 模数据集自动地生成高精度的函数模型，而且模型的结构复杂多样。文献 1 3 利 用遗传程序设计的方法来自动生成统计预测模型，生成的模型具有很高的精度且 模型的形式不唯一。 从大量的建模实例以及工程应用中可以看到，基于g p 的数据建模技术能够 根据系统的数据集自动地生成非线性系统的高精度函数模型，实现了从输入到输 出的映射。这就需要进一步分析数据进化建模技术的函数逼近性问题，对于数据 进化建模算法的应用具有重要的指导性意义。文献 1 4 将g p 建立的模型与神经 网络进行类比，表明g p 具有很强的函数逼近能力。 1 2 2 遗传编程的研究现状 g p 是由k o z a 于上世纪8 0 年代末9 0 年代初提出的一种自动程序设计方案。 随后，一些相关的具有代表性的技术和研究成果也相继出现n 蚴1 ，这些著作对理 论的深化、应用的扩展起了重要作用，使程序设计自动化展现了新的局面。 3 改进g p 在电路建模中的应用研究 9 0 年代以来，g p 算法在机器学习乜引、自动控制瞳羽、图像处理瞳钔、信号处 理汹1 和模式识别乜目等领域取得了广泛成功，世界上许多国家将g p 算法作为计 算智能的一个重要研究方向并成为研究的热点。目前已经出现了许多用不通的语 言编写的g p 系统( 女i l i s p ，c ，c + + ，j a v a 等) 取得了令人满意的效果。具体如下旺 ： ( 1 ) 系统建模和模式识别：g p 算法是一种先进的数据挖掘方法，可以使 用g p 进行特征分析和数据分类，特别是对于特征提取的数据量非常大或者特 征变量间关系不明确的情况。 ( 2 ) 过程控制和机器人控制：在这类系统中，大多数控制对象是复杂的，难以 建立输入与输出变量间明确的解析表示。g p 算法起源于对人工自适应系统的研 究，它可以解决这些现有方法很难解决或不能解决的控制问题 ( 3 ) 人工生命：用计算机模拟生物的自然进化或发现规律。 ( 4 ) 图像和信号处理：图像识别、图像恢复、图像和声音的压缩等。 ( 5 ) 演化硬件：利用可编程器件以结构可重配置的特点，通过演化算法实现 硬件的功能。 ( 6 ) 游戏策略及艺术。 ( 7 ) 软件复用和自动程序设计。 国内外有关g p 建模方面的文献有：文献 2 8 】将g p 算法应用于混沌时间序 列的研究中。采用g p 算法寻找合适的模型结构，用粒子群优化算法进行参数估 计。曹宏庆康立山等在其混合演化建模方法啪1 中，以g p 优化模型结构，用遗传 算法啪埘1 优化模型参数，保证算法在得到好的结构的同时，也获得好的系数，显 著地提高了求解的质量。g r o s m a n 等在n m p c 中使用g p 算法预测过程的模型结 构和参数值嘲。查志琴和上海交通大学的高波等人针对g p 的特点，提出了一个 通用的模型，以虚拟机来提高算法的效率嘲。西安交通大学的李良敏等提出了一 种基于g p 和支持向量机的故障诊断模型，该模型利用g p 对传统的时域指标进 行特征选择和提取，得到更能反映信号本质的特征，与其他特征组合后作为识别 特征输入多类支持向量机，实现了对机器不同类型故障的识别嘲。北京化工大学 的白焰采用g p 解决非单调非线性系统的辨识问题，在对象的结构和参数未知的 情况下，先进行参数恒定下的辨识，再进行在运行期间非线性环节参数发生变化 的系统辨识汹1 。利用g p 在表示硬件电路方面的优势，文献啪1 将其用于演化硬件 4 改进g p 在电路建模中的应用研究 的研究之中，实现数字电路的自动设计。演化硬件将演化算法与可编程逻辑器件 相结合的技术，它通过演化算法中的遗传操作，根据硬件所要实现的功能来寻找 全局最优的个体，经过译码得到相应的配置文件下载到可编程逻辑器件中去。本 文所研究的电路建模问题是纯软件的，利用g p 算法得到电路模型，便于对电路 进行仿真分析。 目前有许多文献提出了对g p 算法的改进。文献 3 7 将局部搜索、模拟退火、 g p 和遗传算法相互结合设计出1 4 种不同的进化建模策略。y e u n 提出辅助进化 树的g p 算法嘲，利用辅助树进化群体，将基本树与动态的辅助树之和作为输出， 提高进化建模的质量。文献 3 9 采用随进化代数动态调整的非线性适应度函数 以改进算法性能。文献 4 0 1 采用d i f f e r e n t i a le v o l u t i o n ( d e ) 获得简单、有效的模型。 文献 4 1 】采用个体树快速生成、初始群体性能的提高、一致性交叉、编辑算子和 权值逐步适应法等5 种g p 算法的改进技术提高g p 的收敛性和搜索结果的精度。 文献 4 2 针对g p 算法中标准交叉操作由于完全随机的选择交叉点而无法有效的 生成优秀子代个体的问题，提出一种新的交叉操作方法。 由于g p 是一种随机性很强的算法，面对复杂问题容易造成收敛速度慢的问 题。本文针对遗传操作中的变异做了改进，将多个变异算子并行运作，综合发挥 各种算子的优势，进一步提高了群体结构的多样性，促进进化过程收敛到全局最 优解，达到提高收敛速度的目的。 1 3 本文的研究内容 本文对电路的建模问题进行深入的研究。将遗传编程技术应用于电路的建 模问题。遗传编程是一种类似于遗传算法的进化计算方法。能较好的解决无先验 知识的电路建模问题。并且其给出的模型具有显式，多样化和精度高等优点。本 文采用并行变异对基本的g p 进行改进。 工作主要集中在以下几个方面： ( 1 ) 采用并行变异对传统的遗传编程进行改进，将多种操作形式的变异算子 并行运作，得到模型结构变化多样的进化群体，并且提高了算法的收敛性。 ( 2 ) 对并行变异进行了收敛性分析，为解决电路建模问题提供理论依据。 ( 3 ) 将改进的g p 遗传编程算法应用于模拟和数字电路建模，并与其他算法 5 改进g p 在电路建模中的应用研究 得到的结果进行对比分析。 本文组织结构如下： 第一章绪论。本章主要介绍了常用的电路建模方法及其不足。提出用遗传 编程的方法进行电路建模。 第二章g p 算法。主要介绍遗传编程的基本原理和方法。 第三章改进的g p 算法及收敛性分析。改进基本g p 算法，用并行变异代替 基本变异操作。对改进算法进行收敛性分析，为解决建模问题提供理论依据。 第四章基于改进g p 的电路建模。利用改进的基于并行变异的遗传编程方 法进行试验。选取模拟和数字两种电路进行建模，验证算法的有效性。 第五章总结与展望 6 改进g p 在电路建模中的应用研究 2g p 算法 g p 的基本思想是基于达尔文进化论和孟德尔的遗传变异理论的。d a r w i n 进 化论最重要的是“物竞天择，适者生存 原理。它认为自然界总是延续适应性强 的物种，淘汰不适应的物种，每一物种在发展中越来越适应环境。m e n d e l 遗传 变异理论最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基 因形式包含在染色体内，经过存优去劣的自然淘汰，适应性高的基因结构得以保 存下来。g p 算法就是通过对生物遗传和进化过程中的选择、交叉、变异等机理 的模仿，来完成对问题最优解的自适应搜索过程。 2 1g p 组成 g p 从随机产生一个适用于所给问题环境的初始群体出发，构成群体的个体 都有一个评价其解决问题能力好坏的适应度，基于适应度选择个体进行交叉、变 异、复制等遗传操作形成新的个体，最终产生下一代群体，经过一代代繁演，最 终产生一个适应度高的个体，即所给问题的解或近似解产生。总结以上过程，g p 主要由初始群体生成，适应度函数，遗传操作，终止准则几部分组成。 一般而言，g p 算法的设计分为以下5 个步骤： 第一步：确定模型操作符集和数据集。 第二步：初始化树表达式的种群。采用随机的方法产生n 个初始化树表达 式种群。 第三步：评估种群中的每个个体。 第四步：根据适应度值对种群中的个体进行复制，交叉和变异，产生新一 代的种群。 第五步：判断是否满足终止准则。如果当前群体不满足终止准则转到第二 步，否则算法结束，选择当前种群中适应度最好的个体作为计算的结果。图2 - 1 为流程图 7 改进g p 在电路建模中的应用研究 图2 1 流程图 2 2 g p 个体表示方法与初始群体生成 在g p 中，首先要解决的问题是如何用可行的函数对个体进行描述。g p 的个 体表示法可根据其基本结构大致分为三种：树形的，线性的和基于图形的结构。 其中最常见的是树形结构。在这种c a p 系统中，每个个体都是一个以树形结构表 示的程序( 或表达式) 。 树中的结点可分为两类，其中位于内部的结点称为“函数 而位于端点的叶 结点称为“终止符”。 函数可以是： 8 改进g p 在电路建模中的应用研究 ( 1 ) 算术运算符，如+ ，一，奉，等； ( 2 ) 标准数学函数，如s i n ，c o s ，e x p ，i n 等； ( 3 ) 布尔运算符，如a n d ，o r ，n o t 等： ( 4 ) 条件表达式，如i f t h e n e l s e 等； ( 5 ) 可迭代函数，如d o u n t i lf o r ，w h i l e 等； ( 6 ) 可递归函数： ( 7 ) 其它与问题有关的函数。 终止符可以是变量( 如描述系统的输入、传感器、识别器、状态变量等) 或 常量( 如整型、实型或布尔型常数) 。 图2 2 是一个用树形结构表示的个体( 表达式) 。写成表达式形式为 s i n x + ( 2 8 ) 。其中基本运算符“+ ，“一，“s i n 为函数，变量“x 和常数“2 ， “8 为终止符。该树即为数据结构理论中著名的算法树数据结构，这种算法树 数据结构非常便于表达式求值。 图2 - 2 遗传编程树形表示法 函数集与终止符集应满足封闭性和充分性。所谓封闭性是指函数集中的任一 函数的返回值及数据类型以及终止符集中任一端点的可能取值及数据类型，都可 以作为函数集中函数的参数。也就是说，函数集中的函数应对其所有可能的参数 组合都是有定义的。而充分性是指通过对函数和终止符的组合，可以生成解决问 题的程序。 初始群体是众多初始个体组成的集合，初始个体是由给定的函数集和终止符 集随机生成的。生成初始个体时，首先从函数集中随机选取一个函数作为根结点， 如图2 1 中的“+ ”。然后根据该函数处理的自变量的个数，从函数集和终止符集 中随机的选出同样数量的元素作为子结点。“+ 为二元操作符，因此有两个子结 9 改进g f 在电路建模中的应用研究 点“一”和“s i n 。重复上述操作，直到所有的分支都选择终止符作为子结点。 初始随机树的生成方法有多种。初始群体中的树应有不同的大小和形状。 k o z a 将初始群体的生成方法按其大小和形式分为以下4 种【l 】： ( 1 ) 完全法：用完全法产生的初始个体，每一叶子的深度都等于给定的最大 深度。其实现方法是：若待定结点的深度小于给定的最大深度，则该结点的选择 将限制在函数集内：若待定结点的深度等于给定的最大深度，则该结点仅从终止 符集内选取。 ( 2 ) 生长法：生长法也是从根结点到终结点顺序生成个体树，但每个分支长 度可以不相等，即用生长法产生的初始个体具有不同的形态，每个分支的深度不 一定等于给定的最大深度。在决定中间结点的类型时，可以随机地决定选择终结 点型还是函数结点型。若选择终结点型，则在终结点集中随机选择其一；若选择 函数结点型，则在函数结点集中随机选择其一，这样虽然存在最大生成深度的限 制，但没有一定的必要达到最大。 ( 3 ) 倾斜生成法：倾斜生成法将最大生成深度作为种群的一种参数处理。种 群中的个体结构大小呈均匀分布，倾斜生成法在实际生成个体树时，可一致地选 择完全生成法和生长法。 ( 4 ) 倾斜对半生成法：倾斜对半生成法与倾斜生成法不同的是，在生成每个 遗传程序时可以随机地选择采用完全生成法和生长法。本文采用这种方式生成初 始群体，使得个体满足一定的分散性，保证个体具有多样性。 随机产生的初始群体遍布整个解空间，但整体素质一般是很差。有许多甚至 是不可行的，要经过几代甚至更多代后整体素质才有提高。因此出现了改进的初 始群体生成方法踟： ( 1 ) 排序生成法 如果群体规模为m ，在生成初始群体时首先随机生成a m 个个体，然后将这 a m 个个体进行排序，取其前m 个组成初始群体。a 是表示问题复杂程度的系数， a l ，一般情况下，取a 2 比较好；当问题比较复杂，收敛性能相对下降，a 应取 较大值，以提高初始群体的质量，使收敛性能有所改善。当a 太小时，近似于随 机生成初始群体，对算法起不到改进作用。该方法生成初始群体的运算量随a 增 大而增加。 1 0 改进g p 在电路建模中的应用研究 ( 2 ) 最优生成法 最优生成法是循环m 次，每次生成m 个个体，取其最好者，直至得到m 个 最好者，形成初始群体。这种方法生成的初始群体质量较高，但运算量很大。当 问题较复杂时，群体规模m 一般较大，计算量就更大。采用此方法生成的具有 较高质量的初始群体可以大大改善g p 的收敛性能，该方法生成初始群体时相当 于要从m 2 个个体中选出m 个个体，所以初始群体生成时的运算量很大。但是， 一旦初始群体生成后，迭代过程因为具有较高质量的个体而收敛得比较快。 ( 3 ) 平均值法 平均值法是首先生成m 个个体，求其平均适应度，当个体的适应度大于平 均值者将被保留下来，重复此过程，直到保留下来的个体数达到m 为止。该方 法生成初始群体时的运算量不大，一般情况下，重复2 3 次就可以满足要求。 2 3 适应度函数、选择策略及终止准则 适应度评价在达尔文自然选择定律，遗传算法和g p 中都充当了驱动力的角 色，是遗传算法和g p 得以实现的关键因素。可用“适应度函数值 表达个体对 环境的适应程度及繁衍到下一代的可能性。在设计数学算法的时候“适应度函数 可以表述为个体的一个属性，表示其竞争能力。g p 算法根据相应的适应度函数 得到不同个体的适应度，通过控制参数调节求解过程的搜索范围和进化操作。它 的值直接影响g p 算法的收敛速度以及能否找到最优解。 在g p 算法设计中，根据不同的需要，适应度的评价可以选用标准化适应 度、原始化适应度、调整适应度和正规化适应度等4 种形式： ( 1 ) 标准化适应度 标准化适应度与遗传算法中适应度的最大化要求取得一致，采用如式( 2 1 ) 的简单形式： s ( f ) 一，傩- r ( i ) ( 2 1 ) 式( 2 1 ) 中sc i ) 为个体i 适应度计算的输出值，眦为为最大的原始适应度，( f ) 为 个体i 的原始适应度。 ( 2 ) 原始化适应度 改进g p 在电路建模中的应用研究 原始化适应度是问题适应性的自然描述的一种度量，通常通过直接计算个 体的输出与期望输出之间的绝对误差获得，如式( 2 2 ) 所示： r ( f ) 一驴( 训一c ( j ) l ( 2 2 ) 式( 2 2 ) 中：s ( i ，j f ) 为个体i 在第j f 个输入值时的计算输出；c ( j ) 为第- 个输入 值对应的目标期望值；m 为训练样本个数 ( 3 ) 调整适应度 将标准化适应度( 如式2 1 所示) 进行调整，个体f 的调整适应度a ( f ) 如 式( 2 3 ) 所示： 口( f ) 。南 ( 2 3 ) 一般情况下，s ( i ) t 0 ，贝l ja ( i ) 【o ，1 】。因此调整后适应度的值越大，个体就越 优良。调整适应度比标准适应度形式对最佳个体具有更好的鉴别力，特别是当标 准适应度趋近o 时，调整适应度可以放大标准适应度的微小差别。 ( 4 ) 正规化适应度 正规化适应度用于基于适应度比例的选择方法，它由调整适应度计算得到， 如式( 2 4 ) 所示： 疗( z ) 。善生 荟口( 七)筋。 ( 2 4 ) 式( 2 4 ) 中，m 为种群的大小。 正规化适应度具有以下三种理想的特征： 万( f ) 【o ，1 】：适应度值越大，个 f 体越优良：，l ( 七) = 1 。正规化适应度可以直接用作个体的选择概率。 i = l 上述四种形式的适应度函数具有如下特征：定义形式规范；函数数单值、 连续；适应度与解的优劣比例；计算简单；具有一定的通用性。可以说，满 足了个体优劣的度量要求。适应度通常用一组适应度计算实例进行估值，对于自 变量空间有限的问题来说，适应度计算实例可取自变量的所有可能组合，此时， 该组适应度计算实例就是整个值域空间的代表。 1 2 改进g p 在电路建模中的应用研究 当个体由适应度函数计算得到适应度值后，g p 算法需要根据适应度的评价 驱动进化过程，选择个体是否保留在群体中或被新的个体替代。在g p 算法中， 选择策略影响个体进化的速度和趋势，不同的选择策略决定个体生存方式的差 异。因此，选择策略对于g p 算法中个体的优胜劣汰很重要，通常是个体过早 收敛中阻碍进化算法成功的主要因素。目前，个体选择概率的常用分配方式有如 下两种： ( 1 ) 适应度比例选择法 适应度比例选择法是自h o l l a n d 以来的一种最常用的选择策略。该方法按 个体适应度占群体的比例分配决定个体被选择的可能性，即个体的适应度越高， 它被选中的概率就越大，其子孙遗留的可能性就越高。 设厂( f ) 是某个体i 的适应度，则该个体被选择的概率只为 霉盟 ( 2 5 ) ， 式( 2 5 ) 中，m 为群体中个体的数目。当p i 给定后，产生区间 0 ，1 n 的随机数来 确定参与遗传操作的个体，个体的只值越大，它被选中的概率就越大。 ( 2 ) 适应度排序选择法 此方法由w h i f l e y 等提出，具体方法是把各个体按适应度从大到小排序， 然后按事先设计好的概率表按序指定各个体的选择概率。该概率与适应度大小不 直接成比例，而仅与个体的适应度排位有关。适应度排序选择法避免了适应度计 算尺度的问题，并且当最好个体的选择概率和平均选择概率之间的比值过小的情 况下，克服了进化过程早熟的现象。此方法的缺点是：基于适应度排位的选择 概率表要事先确定，这种方法也是一种基于概率的选择，所以仍有统计误差。 在g p 算法中，常用的个体选择策略有如下两种： ( 1 ) 轮盘赌选择法 该方法是最简单的一种选择方法，它根据给定个体的适应度、选择概率和累 积概率，对个体进行多轮选择，确定选择交配个体。在每一轮选择中j 产生一个 【0 ，1 】之间的均匀随机数，将该随机数作为选择指针，从而确定被选择个体。 ( 2 ) 锦标赛选择法 改进g p 在电路建模中的应用研究 该方法随机地从群体中选择一定数目的个体，将它们的适应度值进行比较， 选择适应度值最好的个体作为生成下一代的父体，该过程重复进行，直至完成一 定数量个体的选择。锦标赛选择法使得适应度值较好的个体具有较高的选中机 率，另外，它通过衡量竞赛规模和选择强度之间的关系，以个体适应度的相对值 为选择标准，避免了群体中个别或极少数超级个体的影响，能有效避免进化过程 的早熟现象。 常用的终止准则是检查当前进化代数，如果代数超过预定的最大进化代数 时则进化停止。还可以根据进化搜索的特征值，检查进化群体适应度的改进程度， 作出中断的决定。当进化代数还没达到最大进化代数时，群体中的最好个体的适 应度连续保持代无显著变化，即解的质量没有明显提高，则终止进化。另外 的终止条件是生成模型的质量，当代数还没达到最大进化代数时，群体中最优个 体所表示的函数在给定的建模精度范围内，即获得满足精度要求的模型个体，终 止进化进程。 2 4 基本遗传操作 遗传编程的基本操作包括复制，交叉，变异，自动定义函数f ) 等。 ( 1 ) 复制 当复制操作发生时，一个父代个体繁殖一个后代个体。复制操作从当前的群 体中，跟据适应度的大小按照不通的选择方法选出一个父代个体，然后将父代个 体不经任何变化的复制到下一代中去。在复制的过程中，适应度较好的个体有更 大的概率获得复制操作。 ( 2 ) 交叉操作 交叉操作是生成新个体的活动，它扩大了搜索空间，提高了群体收敛性。交 叉后的新个体通过父代个体提供不同的组成部分而产生。如图2 3 ，交叉操作从 当前群体中跟据适应度随机的选取两个父代个体，选出的父代个体的结构大小都 不相同。然后从每个父代个体算法树中随机的选取一个结点作为交叉点，交换这 两个父代中以交叉点为根结点的子树，得到两棵新树即为下一代群体中的两个子 代个体。 交叉操作需要满足终点集封闭性原则，才能生成合理的下一代个体。由于父 1 4 改进g p 在电路建模中的应用研究 个体是基于适应度值挑选出来的，它在解决给定问题时有一定的效果，它们部件 的重新组合产新一代个体，可能更适合于所给问题。 父代 子 叉点 图2 3 交叉示恿图 ( 3 ) 变异操作 变异操作使群体中个体的结构发生局部变化，增加了算法的局部搜索能力， 一定比例的变异操作可以避免群体的同化倾向。变异操作随机选择个体树上的一 个结点( 称为变异点) ，该变异点既可以是树的内部结点，也可以是终结点；然 后，删掉变异点以下的子树，以随机方式将变异点变变异为另外一个具有相同参 数的结点或变异为终结点，也可以随机产生一个适度大小的新子树取代该结点以 下的子树而形成一个新的个体树。图2 4 给出一个变异的例子。 其他变异操作有： 在父代个体中随机地选择某个结点，用相同属性的元素代替。 交换变异子树的左子树和右子树。 删除以变异点为根结点的相应子树，用终止符代替它。 改进g p 在电路建模中的应用研究 若变异点元素是常数，则用随机数扰动，适应度函数将决定临时随机常 数的调整方向和大小。 变异景变异 一 c o p y 0 ； f o r ( i = 1 ；i p a r a m s p m u t e n o d e w t + p a r a m s - p a r a m s p m u t e a l l n o d e t w t 】+ p a r a m s - p a r a m s p m u t e s h r i n k w t + p a r a m s - p a r a m s p m u t e s w a p w t + p a r a m s - p a r a m s p m u t e t r u n c w t + p a r a m s - p a r a m s p m u t e s u b t r e e w t + p a r a m s p a r a m s 【p m u t e g r o w w t + p a r a m s 一 p a r a m s p m u t e s h i f t w t ) ； w h e e l = p a r a m s 一 p a r a m s p m u t e n o d e w t ； i f ( p r o b m u t a t e n o d e 0 ；单点变异 e l s ei f ( p r o b p a r a m s p m u t e a l l n o d e w t ) ) t r i a l 一 m u t a t e a u n o d e 0 ； 多点变异 e l s ei f ( p r o b p a r a m s p m u t e s h r i n k w t ) ) t r i a l 一 m u t a t e s h r i n k 0 ； 压缩变异 e l s ei f ( p r o b p a r a m s p m u t e s w a p w t ) ) t r i a l 一 m u t a t e s w a p 0 ；置换变异 e l s ei f ( p r o b p a r a m s p m u t e t r u n e w t ) ) t r i a l - m u t a t e t r t m c 0 ；截断变异 e l s ei f ( p r o b p a r a m s p m u t e s u b t r e e w t ) ) t r i a l - m u t a t e s u b t r e e 0 ；子树变异 e l s ei f ( p r o b p a r a m s p m u t e g r o w w t ) t r i a l 一 m u t a t e g r o w 0 ； 生长变异 e l s e t r i a l 一 m u t a t e s h i f t 0 ；) 移位变异 n e w c h r o m e = t r u e ； 3 3 改进g p 的收敛性分析 g p 算法能够根据系统的数据集自动地生成非线性系统的高精度函数模型， 改进g p 在电路建模中的应用研究 实现了从输入到输出的映射。这就需要进一步分析g p 算法的函数逼近性问题。 在函数逼近问题中，由于形成建模数据的真实模型往往是存在的，真实模型就可 以作为问题的全局最优解。这样算法的函数逼近性分析转换为算法的收敛性分 析，即g p 算法能否以概率1 收敛到最优解。 标准遗传算法不能够收敛到全局最优，其原因在于算法中最优解的概率 遗失。如果在算法中每代保留当前进化群体中的适应度最优的个体，无论是在选 择操作前还是在选择之后，遗传算法将最终收敛到全局最优幻。 引理采用保留最优解的遗传算法以概率1 收敛到全局最优解。 遗传算法可以看作为一个有限状态的齐次m a r k o v 链，每一代群体空间的变 化依赖于遗传操作的循环往复执行，按照交叉一变异一选择的迭代顺序进行状态 的转移，并且为了保证算法的收敛性还引入保优操作，则进化过程的状态转移矩 阵p = c m s u ，要求交叉转移矩阵c 是随机矩阵，变异转移矩阵m 为严格正的随 机矩阵，选择转移矩阵s 是随机且列容的，保优操作的转移矩阵u 的每一行只 有一个元素为1 ，其他元素为o 。 g p 算法从随机生成的初始群体开始，通过选择、交叉和变异操作产生新的 进化群体，并且在进化的每一代中保留上一代的最优个体。可以看作为采用动态 编码串结构的遗传算法，但是交叉和变异操作在很大程度上与遗传算法不同。分 析g p 算法遗传操作的转移矩阵，如果它的状态描述及选择、交叉、变异和保优 操作的状态转移矩阵的基本性质与二进制编码的遗传算法相同，那么遗传算法在 收敛性分析方面的结论对于g p 算法也可以适用。因此在分析g p 算法的收敛性 时，证明其遗传操作能够满足遗传算法的收敛条件即可。进一步地分析遗传操作 转移矩阵的概率描述，进而得到数据进化建模算法的收敛性质。 结论1 ：g p 算法是一个有限状态的m a r k o v 链。 在g p 算法中，令所有个体形成的空间为d ，所有群体对应的整个状态空间 为g = d 1 ，0 2 , ，o a ，其中每一个状态d f 表示一个群体的可能，么为状态空间 的状态数。当限定个体编码串的最大长度z 和进化群体规模p s 时，由于个体编 码串是动态可调的，从根结点开始依次添加编码，d 的维数为， 改进g p 在电路建模中的应用研究 iqi 一( 陌+ n f ) + ( r + f ) 2 + + ( n t + n f ) 7 。( n t + 胛0 塑塑! 二! ( 3 2 ) 。i n t + n f 、一1 式中胛和胛分别为端点集和函数集中编码的个数。 考虑到会组成一些编码串无效的个体，总是要小于i d l 。从而得到状态空间 的状态数： a 。 ( 3 1 8 ) 结论4 ：并行变异操作的转移矩阵是严格正的随机矩阵。 一种状态0 i 经过并行变异操作后可能转移到另一种状态q 。记变异转移矩 阵m = ( m i j ) n a 则 = 垂仁p ( 气呻如) ) 一( 己) 芦n p ( 厶一) ) 。 ( 3 1 9 ) 改进g p 在电路建模中的应用研究 式中砌为并行变异的操作概率，臌表示状态优中第k 个个体；拓表示状 态仍中的第k 个个体。对于任意二个状态，至少在一个非零概率下可实现从傀 到口的转移。于是变异操作的转移矩阵是正的随机矩阵。 结论5 ：经过选择操作的状态转移矩阵是随机且列容的。 在g p 算法中，交叉和变异操作后得到的子代经选择操作后转移到下一代群 体，设其状态转移矩阵为踞g ) 。算法采用的选择机制与二进制遗传算法的比 例选择策略( 轮盘赌) 的机制类似，只是g p 算法的适应度函数为个体所表示的函 数的建模精度，其值越小，个体的适应能力越好，更有可能被选入到下一代群体 中。因此群体中第f 个个体五被选中的概率为： 掣坠墅业 0 ( 3 2 0 ) 厢 、。， 1 ( 1 + f i t n e s s ( i k ) ) 则状态q 经选择操作后保持不变的概率为： 驴i=ies一1(1+fitness(i,)。 选择转移矩阵s 每一列中至少存在一个正数，因此矩阵s 是随机且列容。 结论6 ：最优保存操作的转移矩阵的每一行均有且只有一个元素为1 ，而其 它元素为0 。 最优保存操作是将本代的最优个体直接复制到下一代的操作，其作用是使 下一代的最优个体不劣