引入演化效率因子的演化算法设计

吴会丛 于洁

摘 要：随着电子芯片技术的发展，电路系统不断向高集成度和智能化发展。在复杂电磁场环境的各种干扰下，对信息化电子系统的稳定性和可靠性要求越来越高，电子系统的可靠性及自主容错能力成为电路设计所面临的新挑战。为提高恶劣情况下电路的抗干扰能力，提出将分析得到的演化效率因素作为算法的影响因子，引入到演化算法的适应度函数中，对算法进行提高和改进。研究结果表明，在单点短路和断路故障仿真实验中，引入演化效率因子的演化算法的平均无故障概率分别为0.754和0.853。与传统的演化算法相比，两者分别提高了16.4%和14%；与自适应算法相比，两者分别提高了6.7%和5%，证明在受扰或局部损伤的情况下，引入演化效率因子能够有效提升电路系统的鲁棒性及容错抗扰能力。研究结果对改进电路设计的强化及完善有一定的参考价值。

关键词：电子电路；演化效率；演化算法；电路设计；容错能力

中图分类号：TP275 文献标志码：A

文章编号：1008-1542（2018）03-0275-07

随着电子应用技术的高速发展和系统设计的复杂化，电磁防护等设备的可靠性和有效性面临着严峻考验，电子电路设计技术已经越来越受到相关企业和研究人员的重视[1-4]。但是传统的电路设计方法出现了设计过程繁琐、抗干扰能力差等诸多问题。演化硬件（evolvable hardware，EHW）技术从硬件的进化、适应和修复方面给电路设计带来了崭新的解决方案，主要通过演化算法（evolutionary algorithms，EAS）和目标模型来设计所需要的电子电路系统以及电路模块[5-9]。

电路演化是电路设计的重要部分，许多研究者从演化方法上对电路的容错能力进行分析研究[10-14]。与传统容错方法相比，进化方法依赖于人们的先验知识，能提高电路设计的效率并为实现电路自动化设计提供保障[15]。为了提高演化过程的搜索效率和速度，很多研究者对传统的演化算法进行了改进。文献[7]介绍了遗传算法的启发式搜索方法，该方法利用合成电路提高了电路的容错能力；文献[10]将自适应HereBoy算法运用于遗传算法群体，利用两位二进制乘法器，为电路进化过程中前期出现的局部最优和后期的适应度变化缓慢问题提供了解决方法，证明了较传统方法电路进化的收敛速度和种群多样性获得提高；文献[12]采用近似Pareto分布熵及其变化评估种群的进化状态，以此为反馈信息来设计进化策略，算法表现出较好的收敛性和多样性。

本文基于搜索空间和寻优过程进行研究，利用演化效率的变化影响电路的演化进程，将电路演化效率作为一个因子，引入到适应度函数中，指导电路高效准确地向异构方向演化，缩短了电路演化的周期，提高了异构电路个体的寻优概率。

1 电路演化设计

电路演化设计是在可进化硬件研究的基础上，将电路进行编码，利用演化算法对其进行搜索，寻找出符合要求的电路结构的过程。

1.1 演化设计流程

演化算法是借鉴于生物体的进化过程，模拟自然界生物的世代生存规律，通过子代个体之间基因的遗传（选择、交叉和变异）规则，满足“优胜劣汰”“适者生存”的丛林法则。利用演化算法，将其应用于编码空间，通过对其编码的遗传操作达到寻找最优解的目的[16-18]。电路演化过程流程图如图1所示。

通过遗传算子对个体电路不断演化，按照编码方式进行解码转换为电路，对元件简化组合，采用仿真软件对其进行模拟，通过适应度的计算寻找出适应能力最优的电路。从父代和子代个体中，对个体适应度进行排序，选择优异的个体；两两实现单点交叉，产生新的个体；对这些存在的个体进行一定概率的单点突变，计入总个体，并对其进行适应度评价。如果演化后的适应值趋于稳定且在规定演化次数之内，此时演化成功，停止迭代；否则，当演化次数超过规定次数的上限，此时演化失败，停止迭代。从这些最优的电路结构中寻找结构差异大但功能相同的电路，进行故障仿真测试。

1.2 编码方式

在电路优化的设计过程中，通常会利用不同的编码方式（常见电路演化设计编码方式如表1所示）对电路的可变部分进行编码和解码。本文利用网表编码（如图2所示）的连接方式对演化电路进行编码，[KG*3]电路的拓扑结构以及参数值的变化在一定范围内随机波动。由于网表编码元件连接的多样性，以及简单的编码方式，使电路具有丰富的结构，从而可以在编码空间中产生结构多样性的电路，形成初始种群。然后通过遗传算子（选择算子、交叉算子、变异算子）对种群进行操作，从而产生新的个体。

2 模型构建

模拟电路演化的最终目的是寻找出容错能力强的电路系统，如何寻找出最佳的冗余电路系统成为解决问题的关键。当系统的每个支路电路结构相同时，称其为同构冗余组合电路。在这种情况下，由于其结构完全相同，即使故障概率随机发生，但是在极端环境下，时时对电路系统进行影响，发生故障的概率较大。当系统的每个支路电路结构不同时，称其为异构冗余组合电路。这种情况下，因其结构不同，对于同一错误同时发生故障的概率下降，整个系统更加稳定，容错能力和抗干扰能力较强[19-21]。

组合最佳的异构冗余电路系统采用传统的三模冗余系统[22]（如图 3所示）。即由3个相同的功能模块电路和1个表决器组成，每个功能模块都有相同的输入，针对3个模块对于输入的处理得到3个输出，由表决器进行表决，对结果进行输出。因此，在三模冗余系统中，异构冗余组合电路发生故障的概率低于同构冗余电路发生故障的概率。

为了进一步提高电路的稳定性，改进电路系统的自容错能力，采用扩大模块间的异构度来提高电路系统在不同错误发生时模块间的异构容错效率，即在特定故障模式干扰下，使模块之间输出的错误位具有交错性，只要不同时出现2个相同的错误，就能够屏蔽掉故障模块的错误，以期进行冗余表决后仍能保持系统正确。当错误出现在不同位置时进行非相关性纠正，提高了系统的可靠性、安全性以及容错能力。本文異构冗余系统通过最大化故障状况下错误模式的差别来实现容错性能，保障故障发生后能够及时处理，并不影响系统的正常运行，如表2所示。

表2中，a组为3个电路模块每位输出均为正确值00…001；b组为第3个模块在第1位输出为错误，而由于前2个模块的相同位输出正确，所以表决器选择0输出正确；c组发生2个位的错误输出，但是不在同一个位置上，即分别位于第1位和第2位，所以经过表决器表决，系统输出仍为正确值；d组中2个位的错误发生在同1位，即同时发生在第1位上，表决器无法输出正确值，因此d组是错误输出。通过这样设计可以使系统在小故障下依然正常工作，对于处在复杂环境中的电路系统保持稳定运行有很大的作用。

3 算法改进设计

电路演化过程中，适应度评估起着至关重要的作用。在生物学中，适应度是判断生物体或者生物种群所具有的各项特征对环境的适应性，只有在达到一定适应能力的条件下，其后代才能得以生存。本文通过控制进化的收敛速度，增加种群选择的多样性，使其达到在保留优异个体的同时，给予相对较差个体一定的生存空间，从而满足多样化结构种群和算法并行，能够在全局中寻找最优解。根据对电路演化适应度曲线的分析，发现电路演化过程存在一定的趋势，将该方向作为因子引入适应度函数，控制电路演化。根据对电路解码后染色体适应度的计算，判别所得电路与目标电路的相似程度。相似程度越高，说明所得电路越接近目标电路，愈满足设计要求。

3.1 演化效率因子的引入

寻找全局最优解成为研究的一个方向。为了得到最佳的电路组合异构模块，根据传统的电路演化方法进行研究，通过分析电路演化进程以及电路适应度效率的变化趋势，得到演化效率，反映了电路演化的一种方向趋势，将其反作用于适应度函数，作为影响因子来指导电路向电路异构的方向进行演化，从而得到最佳的异构同功能电路模块，进而组合成最佳的异构冗余电路系统。电路演化的适应度曲线如图4所示。根据演化的适应度对其演化效率进行分析，寻找出电路演化的方向，得到演化的效率曲线如图5所示。

对演化效率曲线进行多维函数拟合，得到演化效率因子E（x）近似函數表达式见式（1），其中G为最大演化代数，k，q，p为演化效率因子中参变量，k的取值是[0.5，1），q，p的取值是（0，0.5）。

式（1）表示，种群接近c代时，电路的演化效率有一个变化的极值点，在c代之前，电路演化效率逐渐升高，表示电路演化搜索的范围不断扩大，体现了很好的种群多样性；在c代之后，电路演化效率逐渐减小，表示电路演化搜索的范围扩大，速度有所减慢。所以演化效率更多地放在了局部细化选优上，为了防止陷入局部最优，这种演化效率的变化平滑而缓慢，尽力保持电路寻优的稳定性和准确性。

式（2）为演化电路适应度函数表达式，目标相应曲线为f（x），实际响应曲线为g（x），对两条曲线进行偏差积分，从而获得它们的面积值，该值越小，演化电路的适应能力越好，所得的曲线越接近演化目标。根据式（1）和式（2）对电路演化过程的电路适应度函数进行转化，表示如式（3）所示。将演化效率因子E（x）引入，更好地表示出电路演化过程的特点，从而指导电路演化向着异构方向进化。式（3）表示，Fit（x）是将演化效率反作用原适应度F（x）的结果，E（x）是其动态变化的收敛因子。利用E（x）的变化决定了选择的强制性，当收敛因子越大，原有适应度较高的个体的新适应度就与其他个体的新适应度相差越大，即增加了选择个体的多样性，加速了进化进程，避免陷入局部最优解。

3.2 异构选择

电路演化过程中同一个输入取得相同的输出结果，可以拥有多种具有相同功能但是结构差异较大的优异个体电路，在这些个体电路中寻找出最佳的个体电路进行异构冗余组合，使其能够保证在系统发生故障的情况下，子电路仍旧可以实现电路的功能，保障其正常运行。

基于电路编码可以得到不同类型的电路组集，这些拓扑结构不同的设计是电路组合的优化。相同组件的参与，不同的拓扑结构可能产生不同的电路特性。根据所产生的结构，从中选择出结构不同但功能相同的个体。对这些选择出来的电路进行异构评估从而选取最优个体，进行异构系统组合，从而提升电路容错效率。

4 实验结果及分析

按照前述的编码方式对可演化器件进行编码，适应度采用传统的演化算法、自适应算法和引入演化效率因子的改进算法，对译码器进行电路进化。根据编码方案初始化父代染色体电路，初始化种群为10个；对染色体按照一定的比率进行演化算子操作，本实验按照10%的变异率进行位变异操作，40%的交叉概率进行随机非对称单点交叉，50%的选择概率进行个体遗传选择操作。演化算法的演化参数设计如表3所示。

按照解码方法将染色体转换成电路并对电路进行仿真测试，根据适应度函数进行个体适应度值计算，并根据个体适应度值对电路个体进行排序，然后按照一定的保留比例，选择进入下一代继续进行遗传操作的个体。电路演化过程中，记录每代个体的适应度值，并求每代平均适应度值，根据3种演化算法对电路演化进程的适应度值记录计算并显示，如图6所示。从图中可以看出，本文改进算法的演化进程多样性表现更好，并且比传统的算法和自适应算法的收敛速度快，较传统算法收敛效率提高了7.4%，较自适应算法收敛效率提高了2.1%。从保持多样性和提高收敛角度分析，改进算法对于电路演化有良好的寻优效果，能够更好地找到同功能异构度大的电路模块。

分别在基于传统算法、自适应算法和改进算法的电路演化实验中，选择最后一代的最优种群中的3个电路，作为三模冗余电路系统的相关度模块，进行组合冗余系统。仿真复杂电磁环境下，针对电路系统可能遇到的故障模型，同时对3个冗余电路系统进行单点短路故障和断路故障模拟。

4.1 短路故障

在单点短路故障仿真中，随机在系统中短路同一个元件，并测试整个电路系统的译码器真值表，记录实际响应，并与真值表中的期望响应信号进行对比，计算无故障概率。重复实验20次，计算平均无故障概率，作为短路故障仿真，2个系统的无故障概率表示电路系统一定的容错能力，如图7所示。

从图7可以看出，基于传统算法的演化异构组合系统的20次平均无故障概率为64.8%，基于自适应算法的演化异构组合系统的20次平均无故障概率为70.7%，基于引入演化效率因子的改进算法的演化异构组合系统的20次平均无故障概率为75.4%，较传统算法异构系统提高了 16.4%，较自适应算法异构系统提高了6.7%。说明基于引入演化效率因子的改进算法的电路演化异构冗余电路系统对短路故障有较好的抗干扰能力，引入演化效率因子的改进算法有助于提高电路演化异构冗余系统的容错能力和稳定性。

4.2 断路故障

在断路故障仿真中，随机在系统中断路相同的2个元件，并测试整个电路系统的译码器真值表，记录实际响应，并与真值表中的期望响应信号进行对比，计算无故障概率。重复实验20次，计算平均无故障概率，作为断路故障仿真，2个系统的无故障概率表示电路系统具有一定的容错能力，如图8所示。

从图8可以看出，基于传统算法的演化异构组合系统的20次平均无故障概率为74.8%，基于自适应算法的演化异构组合系统的20次平均无故障概率为81.2%，引入演化效率因子的改进算法的演化异构组合系统的20次平均无故障概率为85.3%，较传统算法异构系统提高了14%，较自适应算法异构系统提高了5%。说明引入演化效率因子的改进算法的电路演化异构冗余电路系统对断路故障有较好的抗干扰能力，改进算法有助于提高电路演化异构冗余系统的容错能力和稳定性。

4.3 结果分析

利用电路演化的种群多样性特点，分析演化效率因素对算法进程的影响，将演化效率作为影响因子引入到演化算法的适应度函数中。通过演化得到多个满足条件且拓扑结构不同的优秀个体电路，进行电路的异构冗余组合，得到引入演化效率因子的改进异构冗余系统，并与传统冗余系统和自适应算法冗余系统进行故障模式的仿真测试。综合上述实验与结果，引入演化效率因子的改进算法的异构冗余电路系统与传统冗余电路系统相比，在短路故障下的平均無故障概率提高了16.4%，在断路故障下的平均无故障概率提高了14%；比自适应算法冗余电路系统在短路故障下的平均无故障概率提高了6.7%，在断路故障下的平均无故障概率提高了5%。实验结果证明，引入演化效率因子的改进算法对于电路异构组合的系统有更好的随机容错能力和鲁棒性，使电路系统在复杂的电磁环境中能够更稳定地发挥其功能。

5 结 语

基于传统演化算法和数值拟合方法，提出了一种引入演化效率因子的演化电路算法，将分析得到的演化效率因素作为算法的影响因子，引入到适应度函数中，在保持良好种群多样性的前提下，提高了算法的收敛速度和寻优效率。利用三模冗余系统，选择结构差异较大的异构电路进行冗余集成，通过模拟仿真实验验证得到，基于演化效率因子的改进算法演化得到的电路模块，经过异构组合生成的三模冗余电路系统，较传统的演化算法及自适应算法的异构组合电路系统有更好的容错能力和鲁棒性。本文所采用的方法虽然提高了电路系统的无故障概率，但还存在不足之处，将从数字电路和模拟电路2个方面改进电路的设计方法，把电路系统的容错性能及稳定性作为后续研究的重点。

参考文献/References：

[1] KIM K J， CHO S B. Automated synthesis of multiple analog circuits using evolutionary computation for redundancy-based fault-tolerance[J]. Applied Soft Computing， 2012， 12（4）：1309-1321.

[2] YAO X，HIGUICHI T. Promises and challenges of evolvable hardware[J]. IEEE Transactions on Systems， Man， and Cybernetics， Part C： Applications and Reviews， 1999， 29（1）：87-97.

[3] 张峻宾， 蔡金燕， 孟亚峰. 面向复杂电磁环境的容错电路系统设计技术[J]. 西安交通大学学报， 2017， 51（2）：53-59.

ZHANG Junbin， CAI Jinyan， MENG Yafeng. A design technology of fault tolerance circuit systems facing complex electromagnetic environments[J]. Journal of Xian Jiaotong University， 2017， 51（2）：53-59.

[4] ZHANG Meng， HE Jingsong. Vector analysis on the fault-tolerant abilities of combined analog circuit systems[C]// International Congress on Image and Signal Processing， Biomedical Engineering and Informatics.Datong： IEEE， 2017：2020-2025.

[5] 吴会丛， 王晓红， 宋学军， 等. 演化硬件（EHW）的研究进展[J]. 河北工业科技， 2007， 24（1）：49-53.

WU Huicong， WANG Xiaohong， SONG Xuejun， et al. Research progress of evolvable hardware（EHW）[J]. Hebei Journal of Industrial Science and Technology， 2007， 24（1）：49-53.

[6] 陈亚洲， 张冬晓， 田庆民， 等. 某型无人机数据链系统HEMP辐照效应[J]. 高电压技术， 2016， 42（3）：959-965.

CHEN Yazhou， ZHANG Dongxiao， TIAN Qingmin， et al. HEMP radiation effects on unmanned aerial vdehicle data link system[J]. High Voltage Engineering， 2016， 42（3）： 959-965.

[7] 张晓芳， 李智， 牛军浩. 基于演化硬件的多目标进化算法的研究[J]. 微电子学与计算机， 2016， 33（9）：119-123.

ZHANG Xiaofang， LI Zhi， NIU Junhao. Research of multi-objective optimization evolutionary algorithm based on evolvable hardware[J]. Microelectronics & Computer， 2016， 33（9）：119-123.

[8] HUANG Zaisheng， HE Jingsong. An evolutionary design model for reducing the ripple of analog filter[C]//2015 11th International Conference on Natural Computation. Zhangjiajie：IEEE， 2015：1103-1108.

[9] 甄然， 司超， 吳学礼， 等. 基于改进粒子群算法的飞行器冲突解脱方法研究[J]. 河北科技大学学报， 2016， 37（5）：491-496.

ZHEN Ran， SI Chao， WU Xueli， et al. Study of the aircraft conflict resolution method based on modified particle swarm optimization[J]. Journal of Hebei University of Science and Technology， 2016， 37（5）：491-496.

[10]吴会丛， 王金泽， 刘春草， 等. 基于自适应HereBoy算法的电路进化设计实验研究[J]. 河北科技大学学报， 2015， 36（3）：293-299.

WU Huicong， WANG Jinze， LIU Chuncao， et al. Research of circuit evolution design based on adaptive HereBoy algorithm[J]. Journal of Hebei University of Science and Technology， 2015， 36（3）：293-299.

[11]LIN Chao， HE Jingsong. A novel negative-correlation redundancy evolutionary framework based on stochastic ranking for fault-tolerant design of analog circuit[C]// International Conference in Swarm Intelligence. Berlin：[s.n.]， 2013：556-563.

[12]胡旺， YEN G G， 张鑫. 基于 Pareto 熵的多目标粒子群优化算法[J]. 软件学报， 2014，25 （5）：1025-1050.

HU Wang， YEN G G， ZHANG Xin. Multiobjective particle swarm optimization based on Pareto entropy[J]. Journal of Software， 2014，25（5）：1025-1050.

[13]JIANG Shouda， ZHAO Jiayu， WEI Changan. Design of multifunctional communication card based on reflective memory[C]// NASA/DoD Conference on Evolvable Hardware. [S.l.]：Springer International Publishing， 2016：139-146.

[14]SHLYAKOV A N， KAMENSKIH A N， MAZUNINA E S. Synthesis of fault-tolerance circuits by genetic algorithms[C]// 2017 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering. Petersburg：IEEE， 2017：339-341.

[15]LIU Mingguo， HE Jingsong. Negatively-correlated redundancy circuits evolution： A novel way of robust analog circuit synthesizing[C]// 2010 Third International Workshop on Advanced Computational Intelligence. Suzhou：IEEE， 2010：496-501.

[16]解双建， 原亮， 满梦华，等. 基于演化硬件的容错电路设计与实现[J]. 计算机测量与控制， 2011， 19（10）：2495-2497.

XIE Shuangjian， YUAN Liang， MAN Menghua， et al. Design and realization of fault-tolerant circuit based on evolvable hardware[J]. Computer Measurement & Control， 2011， 19（10）：2495-2497.

[17]康立山， 何巍， 陈毓屏. 用函数型可编程器件实现演化硬件[J]. 计算机学报， 1999， 22（7）：781-784.

KANG Lishan， HE Wei， CHEN Yuping. Evolvable hardware realized with function type programmable device[J]. Chinese Journal of Computers， 1999， 22（7）：781-784.

[18]ZHANG Yang， SMITH S L， TYRRELL A M. Digital circuit design using intrinsic evolvable hardware[C]// NASA/DoD Conference on Evolvable Hardware. Washington：[s.n.]， 2012：55-62.

[19]高桂军， 王友仁， 姚睿. 系统异构冗余容错设计研究[J]. 传感器与微系统， 2007， 26（10）：25-28.

GAO Guijun， WANG Youren， YAO Rui. Research on redundancy and tolerance of system with different structures[J]. Transducer and Microsystem Technologies， 2007， 26（10）：25-28.

[20]施威， 原亮， 解双建，等. 基于负相关思想的异构电路冗余技术研究[J]. 微电子学与计算机， 2013，30（6）：71-74.

SHI Wei， YUAN Liang， XIE Shuangjian， et al. Research on selective redundancy of evolved circuits using negative correlation[J]. Microelectronics & Computer， 2013，30（6）：71-74.

[21]李志. 模拟电路负相关演化方法及设计[D]. 合肥：中国科学技术大学， 2013.

LI Zhi. Negatively Correlated Evolutionary Method and Design for Analog Circuits[D]. Hefei：University of Science and Technology of China， 2013.

[22]陈州， 倪明. 三模冗余系统的可靠性与安全性分析[J]. 計算机工程， 2012， 38（14）：239-241.

CHEN Zhou， NI Ming. Reliability and security analysis of triple-module redundancy system[J]. Computer Engineering， 2012， 38（14）：239-241.