基于基因表达式编程的装备测试需求建立方法❋

王俊亚,陈棣湘,潘孟春

(国防科技大学机电工程与自动化学院,湖南长沙 410073）

自动测试系统(Automatic Test System,ATS)是对那些能自动完成激励、测量、数据处理并显示或输出测试结果的一类系统的统称[1].自从20世纪60年代第一代ATS出现以来,在各国军方和各航空公司的强烈需求牵引下,自动测试技术已经在系统集成[2]、测试总线[3]、测试资源模块化和虚拟化[4]、软件体系结构[5]、测试数据形式化[6]等方面取得了极大成就.但是,在被测对象(Unit Under Test,UUT)测试需求分析与测试程序集(Test Program Set,TPS)之间的界限比较模糊,不利于ATS的模块化和标准化.这个问题自20世纪末在西方军用ATS设计过程中得到了重视,但在我军ATS的设计过程中还很少有相关的报告和研究文献.边泽强、孟晓风等人在实现柔性测试系统的快速组建和按需生成方面,利用IEEE STD 1641标准建立了UUT测试需求的标准化描述[7];王学奇、肖明清等人利用可扩展标记语言(Extensib le Markup Language,XM L)实现了UUT测试需求数据的跨平台交换方法[8];根据 Jackson等提出的面向问题域的系统分析方法,刘金宁等提出了面向UUT问题域的测试需求分析方法[9].美国TYX公司开发的ATS软件开发平台PAWS(ProfessionalATLASWork Station)不管是在军方还是各民用航空电子领域都有广泛的用途,其设计遵循IEEE 1226广域测试网(A Broad Based Environment for Test,ABBET)的分层规范和VPP-2(VX IPlug&Play)接口协议,提供多种工具支持 TPS各个阶段的开发.其中包括三大组成部分:测试需求文档,TPS开发平台,测试执行系统.其测试文档的建立包括信号需求定义、测试策略定义和 TPS框架的生成.本文结合某型装备的测试需求特征,提出了一种基于基因表达式编程的测试模型和测试需求的建立方法.在UUT结构和工作原理未知的情况下,根据 UUT的观测数据建立其测试模型,分析其测试信号需求.

1 某型装备制导电子箱测试需求分析

某型装备由若干个功能电子箱组成,其中制导电子箱是一个专用的遥控型制导装置.图1(a)所示的制导电子箱结构原理图中,共包括6块功能电路:采集校正电路、微机电路、接口电路、激活起动电路、点火电路、电源电路.从图1(b)制导电子箱的功能模型可以看出,制导电子箱主要提供控制算法,其输入为一系列的误差信号和控制信号,输出为经过算法处理之后的控制信号.

图1 制导电子箱的结构原理与功能模型Fig.1 The schematic and functionalm odel of the con trol and guide box

表1 测试信号需求分析Tab.1 The requirem en t analyze of the testsignal

从表1可以看出,制导电子箱激励和响应信号的种类和数量很多,涉及数字电平信号、模拟信号、时序信号、能量信号、编码信号等;信号的变化范围较大,尤以时序信号为甚.

2 基因表达式编程算法

2.1 基因表达式编程算法原理

Ferreira博士融合了遗传编程(GP)和遗传算法(GA)的优点,于2001年提出了基因表达式编程算法(Gene Expression Programming,GEP)[10].GEP在形式表达上继承了GA的定长线性编码简单快捷的特点,在基因表达上继承了GP的树形结构灵活多变的特点,用简单编码解决复杂问题,比传统进化计算快 2～4个数量级[11].由于GEP具有极强的全局搜索能力和计算能力,在关联规则挖掘,符号回归等领域用途广泛.

利用GEP进行进化操作的基本流程如图2所示,首先随机生成初始的种群,包含若干个代表不同问题解答的“染色体”或“个体”.然后将种群中的个体表达成对应的表达式或程序,并计算每个表达式的适应度,进而根据适应度和某种选择规则进行选择、复制操作,让适应度比较高的个体有更高的机会保留到下一代中.接着对这些个体进行各种遗传操作,以引入新的个体.最后形成新一代种群.此过程重复进行,直到找到符合要求的问题解答.

在GEP中,除了和GA中类似的单点重组(交叉),两点重组(交叉),单点变异等遗传操作以外,还包括插串(Insert Sequence,IS)和根插串(Root Insert Sequence,RIS)等具有独特动作和含义的遗传算子.这些是GEP所特有的遗传算子,能够为GEP引入更多的新个体.

2.2 基因表达式编程算法设计

图2 基因表达式编程算法流程图Fig.2 The flow char t of the GEP

通过对制导电子箱原理和功能模型的分析,可以发现其本质是一个以处理器为核心的控制单元.其测试信号需求是一定数量的激励信号,要求控制单元的输出满足特定的控制要求.基于此,设计了基因表达式编程算法的构造方法,标准基因表达式编程算法包括定义函数符集合和终结符集合确定、初始种群的生成、适应度函数设计、选择策略、遗传算子确定等几个方面.下面给出基因表达式编程算法的构造原理.

2.2.1 函数符集合和终结符集合确定

基因表达式编程算法的函数符集合与终结符集合应该满足封闭性[12],即要求终结符集合中每一个函数的定义域和值域都是相同的,因此在终结集合中不能同时出现模拟信号和数字信号.并且终结符集合中的函数一般不带参数.在不满足封闭性的时候,遗传操作就会产生大量的死基因,从而影响算法的效率,但是装备实际需求的信号又是形式各异的:模拟信号,数字信号,协议信号(例如RS-232信号,各种编码信号等等),但是对其操作肯定是不满足封闭性的.这就需要一个通用的信号定义和模型.如图3所示的 IEEE 1641标准[13]对信号模型的定义.

图3 IEEE 1641标准定义的信号模型Fig.3 The signalm odel defined in the IEEE 1641

根据测试模型的用途,利用IEEE标准委员会在2010年9月17日最新发布的IEEE 1641标准设计了面向信号的函数符集合F={a,b,c,d,e,f,g,h,i}.其中a代表Average运算,用来求信号的平均值;b代表Counter运算,用来给编码信号计数;c代表Decode运算,用来解码已编码的信号;d代表Interval运算,用来求信号的持续时间;e代表Peak运算,用来求信号的峰值;f代表PeakNeg运算,用来求信号的谷值;g代表 Instantaneous运算,用来求信号的瞬时值;h代表 MaxInstantaneous运算,作为最大值运算;i代表MinInstantaneous运算,作为最小值运算.利用信号源类定义设计了终结符集合P={A,B,C,D,E,0,1,2,3,4,5,6,7,8,9},其中 A代表正弦信号,B代表阶跃信号,C代表常值信号,D代表噪声信号,E代表串行数字信号,数字代表各个信号模型的数字参数.

2.2.2 初始种群生成

考虑到测试模型的精确性,根据制导电子箱本身装备的特点,在求解该优化问题过程中,为了避免进化算法过早地收敛到局部最优解,采用基于小生境理论[14]的初始种群生成方法.

生物学上,小生境(Niche)[15]是指在特定环境中一种组织(Organism)的功能,而把有共同特性的组织称作物种(Species).自然界的小生境为新物种的形成提供了可能性,是生物界保持近乎无限多样性的根本原因之一.在基于小生境的算法中[16],把种群划分为不同的子群,各子群就是具有相同特性的个体集合.子群间通过优胜劣汰、适者生存这一机制进行相互竞争.子群平均适应值高,则其群体规模就大;反之群体规模就小.这样,不但保持了种群中个体的多样性,还保证种群向着预定的目标发展.

2.2.3 适应度函数确定

除了制导电子箱的观测数据和用途之外,对制导电子箱的内部工作原理了解较少,因此在适应度函数的选择上,采用 R-square作为制导电子箱测试模型辨识的适应度计算函数.其计算方法如下

式中:Ri表示第i个个体所对应的函数模型的复相关系数,-1≤Ri≤1;fi表示第i个个体的适应度函数值.Ri的计算方法如下

式中:Pi,j是指第j个样本中第i个个体事先指定的匹配精度;Tj表示训练数据中第j个样本的数据输入;n表示样本个数.

2.2.4 选择操作

选择操作就是从群体中按个体的适应度函数值选择出较适应环境的个体.考虑到测试模型的生成必须能够正确地反映被测装备的测试需求,其正确性必须首先满足.同时为了简化算法的复杂度,采用轮盘赌算法和精英主义算法的结合.

在精英主义算法中,每一代适应度值最大的个体都会被无条件复制到下一代,从而保证了算法能够快速收敛到全局最优值.另外还对适应度最高的个体的基因进行备份,以免在其交叉或变异中被破坏掉.若发现比当前保存的基因适应度更高的基因,则用其替换当前保存的基因.

在保存当前最优解之后,采用轮盘赌算法对剩余个体进行选择,个体的适应度越高,被复制到下一代的概率就越大.各个体在下一代群体中的期望生存数目为

式中:N为种群中个体总数;fi为第i个个体的适应度值.

2.2.5 其它遗传操作

在基因表达式编程算法中,遗传算子一共有8种,主要包括:变异算子、倒串算子、IS插串算子、RIS插串算子、基因变换算子、单点重组算子、两点重组算子和基因重组算子.其中单点重组算子和两点重组算子是最重要的两个算子,是算法进化的主要动力来源;变异算子主要用于维持种群的多样性,避免算法过早地陷入局部最优解;插串算子是基因表达式编程算法独有的遗传算子,为算法提供更强的鲁棒性和适应性;而基因重组主要是对多基因进行操作的.

3 系统实现与电子箱生成测试需求分析

在完成基因表达式编程算法中各部分的设计构造后,还要完整给出对应的算法实现,只需在此基础上给出具体的算法流程及主要参数即可.

算法主要由运算符集合和变量集合确定、初始种群生成、适应度计算、选择策略和遗传操作等步骤.在MATLAB中采用面向对象的编程思想,因此算法实现的核心就是两个类的编写,一个是种群的类,入口参数包括:种群对应的染色体类型,种群大小,种群头部长度,基因组数,基因链接方式等,类中定义了best属性用以表示当前的最好染色体,generate()函数生成初始种群;另一个是染色体的类,构造染色体主要针对应用的对象即测试模型的构造,其入口参数与种群的类相似,类中定义了fitness()、solved()和cycle()三个函数,分别表示适应度函数、终止条件满足函数和改造染色体函数.

算法流程如下:

1)定义p roblem类,包含一个获取数据的函数和一个获取变量名称的方法;

2)定义继承染色体类的sp类,定义了终止符集合和函数符集合的两个函数,并且重新定义了fitness和solved方法;

3)利用种群类的generate函数生成初始种群;执行以下循环:

4)定义最大循环次数;

5)如果sp类的best属性通过方法solved(),退出循环;

6)否则调用方法cycle();

7)算法结束.

分析上述算法可以看出,终止循环的两个条件是:①完成预先设定的最大进化代数;②种群中的最优个体经受solved()的考验.算法中有几个可调参数,循环最大次数为1 000;种群大小一般设置在10～100;变异算子的概率一般在0.001～0.1之间;倒串算子、IS插串算子和 RIS插串算子的概率一般在0.01～0.2之间;单点重组和两点重组算子的概率一般在0.2～0.7之间;基因变换和基因变换算子的概率一般也在0.01～0.2之间.

根据以上测试模型自动生成系统算法设计,可以根据制导电子箱的输入输出数据生成其测试需求.测试需求分两部分内容:测试信号和测试方法.

假设测试资源不受限制的情况下得到如下测试模型:

对该模型可作以下解读:各个染色体的第一个终结符集合中元素代表系统所需要的测试信号,后半部分的数字代表信号模型的各个参数,根据上述结果可以得知:制导电子箱所需信号集合为{正弦信号,常值信号,串行数字信号,噪声信号};测试方法就是分别利用求峰谷值得到正弦信号的最大最小值,对常值信号求平均值得到信号的平均值,对数字信号进行计数来得到时间量,对编码信号进行解码得到原信号.

根据解码得到的结果可以看出,通过算法得到的测试信号,就测试信号而言比制导电子箱所需要的信号多出一个噪声信号,这是因为在算法处理过程中,把常值信号看作是带有噪声的信号,这样在测试需求信号中就有相应的体现.

4 结束语

本文借鉴美国TYX公司的自动测试系统软件产品PAWS中测试需求建立方法以及国内相关专家已取得的成果,提出了基于基因表达式编程算法的装备测试需求自动生成方法并进行了系统实现.实验结果表明了该方法的有效性,为下一步实现基于模型的自动测试系统提供了基础.但此方法目前还存在一些不足之处,比如在函数符集合和终止符的设计上不够全面,缺乏对测试模型的自动评价体系等,这些都是需要进一步研究的问题.

[1] 张宝珍.美国空军第一种通用自动测试系统VDATS[J].航空维修与工程,2010(1):31-32.

Zhang Baozhen.VDATS,the first versatile depot ATS of USAF[J].Aviation Maintenance&Engineering,2010(1):31-32.(in Chinese)

[2] 李行善.自动测试系统集成技术[M].北京:北京航空航天大学出版社,2004.

[3] Yuan Mei,W ang Dahai.LXIC class device design in LAN based ATE[J].IEEE International Conference on Industrial In formatics,2006:995-999.

[4] 张玮.基于模型化思想的模拟电路ATE测试与诊断技术研究[D].北京:航空航天大学,2003.

[5] Kevin Coggins.VDATS and the DoD ATS Framework[J].IEEE Autotestcon,2008(9):8-11.

[6] IEEE Standards Coordinating Comm ittee 20(IEEE SCC20).IEEE Std 1671.IEEE Trial-Use Standard for Automatic Test Markup Language(ATM L)[EB/OL].[2006-11-26].http://standards.ieee.org.

[7] 边泽强,孟晓风.测试需求和资源的标准化描述模型[J].电子测量技术,2008,31(7):111-114.

Bian Zeqiang,Meng Xiaofeng.Standard test requestand resourcemodel in flexible test system[J].Electronic Measurement Technology,2008,31(7):111-114.(in Chinese)

[8] 王学奇,肖明清.基于XM L的测试需求描述及其实现[J].计算机工程与应用,2005,23(2):112-114,172.

Wang Xueqi,Xiao Mingqing.XML-based representation and realization for test requirement[J].Computer Engineering and App lication,2005,23(2):112-114,172.(in Chinese)

[9] 刘金宁,张大勇.面向UUT问题域的测试需求分析方法研究[J].工业自动化仪表,2008,29(1):12-14.

Liu Jinning,Zhang Dayong.Research on analysismethod for UUT prob lem domain-oriented test demand[J].Process Automation Instrumentation,2008,29(1):12-14.(in Chinese)

[10] Candida Ferreira.Gene expression programm ing:a new adaptive algorithm for solving problems[J].Comp lex Systems,2001,13(2):87-129.

[11] Candida Ferreira.Gene exp ression programm ing:a new adaptive algorithm for solving p roblems[J].Comp lex Systems,2001,13(2):87-129.

[12] 左 吉力.基因表达式编程核心技术研究[D].成都:四川大学,2004.

[13] IEEE Standards Coordinating Committee 20(IEEE SCC20).IEEE Std 1641.IEEEStandard for Signaland Test Definition(STD)[EB/OL].[2010-05-19].http://standards.ieee.org.

[14] 李太勇,唐常杰.基于小生境基因表达式编程的多模函数优化[J].四川大学学报(工程科学版),2009,4(2):162-166.

Li Taiyong,Tang Changjie.Mu ltimodal function op timization based on nichegeneexpression programm ing[J].Journal of Sichuan University(Engineering Science Edition),2009,4(2):162-166.

[15] De Jong K A.Ananalysis of the behavior of a class of genetic adap tive systems[D].Michigan:University of Michigan,1975.

[16] Goldberg D E,Richardson J.Genetic algorithms with sharing for multimodal function optimization[C].Genetic Algorithms and Their Applications:Proceedings of the Second International Con ference on Genetic Algorithm s,1987:41-49.