基于自适应HereBoy算法的电路进化设计实验研究

吴会丛，王金泽，刘春草，高金金

(河北科技大学信息科学与工程学院，河北石家庄 050018)

基于自适应HereBoy算法的电路进化设计实验研究

吴会丛，王金泽，刘春草，高金金

(河北科技大学信息科学与工程学院，河北石家庄 050018)

针对电路进化设计演化后期种群收敛速度放慢等问题，采用自适应HereBoy算法，融入遗传算法的群体概念，研究自适应因子在进化算法中对演化收敛速度的影响。运用类神经网络的电路模型和矩阵编码方法对组合电路进行编码，建立了电路编码到电路功能的映射关系，采用外部进化方式进行电路适应度值评估，引入自适应遗传算子提高算法收敛速度和种群多样性。二位二进制乘法器电路的进化结果表明，该方法较传统HereBoy算法在电路进化设计进程中电路平均演化代数及演化时间明显减小，在进化后期，随着种群演化代数增加适应度值平均涨幅提高。

电子电路;演化硬件;电路进化;神经网络;HereBoy算法;自适应算子

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

WU Huicong，WANG Jinze，LIU Chuncao，etal.Research of circuitevolution design based on adaptive HereBoy algorithm［J］.Journal of HebeiUniversity of Science and Technology，2015，36(3):293-299.

计算机技术的迅速发展及芯片技术的不断提高，尤其是可编程逻辑器件的出现，使电路控制系统的规模不断扩大、电路结构和功能更加复杂化，特别是空间探测和军备武器设备，其设备的可靠性和有效性面临着更加严峻的挑战［1-3］。硬件演化技术为电路设计开辟了一条新道路，其自修复和自适应特点将大大提高系统的可靠性和可用性［4-6］。演化硬件是把演化算法与可重构硬件相结合，根据环境变化而动态调整自身结构的硬件电路系统。演化硬件是当前国际上的一个热点研究领域，电路进化设计是演化硬件的一个分支，它使得电路设计过程不再依赖于先验知识和设计规则，通过初始种群编码和运用演化计算对最优解的搜索实现复杂和大规模电路的自动设计，并为以在线自适应与容错为特征的进化硬件的研制奠定基础。

本文借鉴人工神经网络中的多层前反馈网络建立了电路进化设计网络模型，根据该电路模型特点采用了矩阵编码方法;引入遗传算法中种群的概念，对HereBoy算法进行改进，同时对种群中多个个体进行演化操作，提升算法并行性;针对进化算法中普遍存在的收敛问题引入了精英保留策略和自适应进化算子，使乘法器电路尽快收敛到最优解。

1 电路进化设计

电路进化就是将电路的结构和参数等作为染色体进行编码参与演化过程;依靠演化算法的搜索能力寻找满足预期功能的电路结构的过程。

1.1 电路进化设计流程

作为一种高性能的适应性搜索工具，演化算法借鉴生物体的进化过程，通过模拟自然选择和遗传机制，不断生成和效验备选解。使用演化算法求解问题，算法的执行直接作用在解的某种编码串上，而不直接作用在问题的解空间上，使这些编码串参与一系列遗传操作来完成学习过程和确定搜索方向，最终达到寻优目的［4-5］。电路进化的基本流程见图1。

1.2 电路进化的适应度评估

适应度值是驱动整个进化进程的关键，也是衡量是否满足预期目标的标准。根据适应度评估方式的不同，可以将电路进化分为内部进化型和外部进化型两种［2-3，7］。内部进化是将进化算法中每一代产生的染色体作为电路相应的配置位串下载到可重构器件中，根据目标响应对每一种电路结构的输出直接进行评判，演化过程是直接在硬件上动态调整电路结构和参数，依赖硬件的快速性、并行性快速评估每个染色体的适应度［8-10］;外部进化是通过建立电子器件的模型，将由进化算法产生的染色体作为电路的配置位串，将配置位串在模型上进行评判，当达到预期的目标时，配置位串被下载到硬件中去。与内部演化相比，速度较低，但其灵活性强，当进化电路改变时，只需修改一些参数或增减一些函数模块即可［11-12］。电路进化适应度评估方式见图2。

图1 电路进化设计流程图Fig.1 Flow chart of circuits evolutionary design

2 电路模型与编码方式

2.1 类神经网络电路模型

多层前反馈神经网络模型本质上是基于人工神经网络的一种数学模型，其结构由输入层、输出层和中间层组成，中间层不与输入输出相连接，但其状态影响输入输出之间的关系。借鉴该模型，将数字电路中的基本逻辑单元作为神经元，限定其输入输出端个数，神经元的连接关系类比为电路中基本逻辑单元的连接关系，建立类神经网络电路模型，见图3。

图2 电路进化适应度评估方式Fig.2 Fitness evaluation of circuits evolution

图3 类神经网络电路模型Fig.3 Circuits imitation model based on neural network

电路模型中网络节点对应电路基本元件的逻辑功能，能够实现与或非等多种逻辑处理，各层节点之间的连接权值反映电路基本元件的连接关系。通过改变进化区域的大小，即网络的层数和每层节点的个数，该电路模型就可以用来描述任意的数字组合逻辑电路。在描述电路模型中各网络节点连接关系时，引入连接度，即在m行n列的矩阵单元中，第i行j列单元Cij的输入能与前p列单元的输出相连接，则称单元Cij的连接度等于P。本文电路模型中可重构功能节点接收该节点所在层的前一层节点的输入，进行相应逻辑处理，将处理结果依次传递到下一层节点，电路输入经过一系列的选择和不同的逻辑处理得到电路输出。

2.2 矩阵组编码方法

针对电路模型的结构特点，进化过程中构建了二进制矩阵编码的方法对电路结构进行编码［13］。编码矩阵由连接矩阵Wp和单元功能矩阵F组成，两者形成的编码阵列共同决定了电路的功能。连接矩阵Wp表示各层节点之间的连接关系，表达式形式如式(1)所示。

式中fi，j表示第i层第j个逻辑单元的功能。

使用矩阵组编码方法对电路进行编码时，当各层单元数目改变或进行遗传操作时不会产生非法个体，并且可根据电路编码形式判定电路网络的冗余信息，这对实现电路的快速重构修复有重要作用。

2.3 适应度函数设计

电路进化过程中个体的适应度值代表进化所得电路输出与目标电路输出的接近程度，进化所得电路与目标电路越接近，其适应度越高。其原理为通过模拟评价电路的逻辑功能，计算每个备选个体的适应度，将演化目标电路的真值表作为适应度评价标准。即判断真值表的每一行输入是否得到与真值表一致的预期输出值。其计算过程是:对每一个个体电路，都输入p=2i(i为输入端子个数)种组合中的输入信号来验证电路的输出值评价进化个体的优劣，p种不同的输入信号遍历了输入所有可能的组合。分别将p种输入信号对应的实际输出与真值表的期望输出进行对比，以对应正确位数的个数作为适应度的值。适应度计算公式如式(3)所示:

式中:yij表示电路在第i个输入组合时实际输出的第j位的值，对于数字电路，此值要么为1，要么为0;dij表示与该输入相对应的期望输出的第j位;q为进化电路的输出总位数。当fit达到最大适应度值就意味着进化出了一个功能正确的电路。

3 电路进化自适应HereBoy算法

3.1 HereBoy 算法

HereBoy算法是遗传算法和模拟退火算法相结合的一种算法［10］。进化过程中，染色体在许多随机选定的基因位发生变异，如果发生变异后个体适应度值增加，则将变异后个体保留下来，相反如果变异后个体适应度值减小，则保留父体。该算法鲁棒性好，在许多经典问题中被证明能够较快地收敛到最优解［12］。但是，由于HereBoy算法在遗传操作过程中是对单个染色体个体实施变异操作来进行搜索，搜索空间的变化不大，缺乏群体的多样性，因此可能出现早熟的现象。本文在原有HereBoy算法基础上加入了种群思想，使多条染色体独立通过HereBoy算法进行演化，从而保持种群的多样性，避免早熟现象。

3.2 自适应策略设计

进化算法作为一种类随机搜索的寻优算法存在着一定的缺陷，就是有很大可能会过早地收敛于局部最优解。此问题也是算法研究与改进工作中的重要研究方向［14-15］。选择算子、交叉算子和变异算子对算法的收敛速度有很大的影响，对算法执行中的不同阶段也有不同的作用效果［16-19］。根据电路进化的实际过程，在电路进化初期由于染色体适应度值普遍较小，其代表的电路与期望电路的差距较大，此时，算法任务除了保护优秀个体外，还应该给予较差个体一定的生存空间，保证种群的多样性和算法的并行性，实现算法能从全局中搜索最优解;然而在电路进化后期，随着染色体适应度的不断提升，电路结构逐渐趋向收敛于期望功能电路结构，算法的重点应该着重保护优秀个体基因块不被破坏，从而加速算法后期收敛速度。本文根据适应度值和算法执行阶段等情况进行各种遗传参数的自适应调节。

1)选择算子的自适应策略

选择操作的作用是实现种群中个体的“优胜劣汰”，选择概率是指当前种群中个体被选中遗传到下一代种群的概率。个体的演化过程是不确定的，可能会使算法陷入过早收敛至局部最优，其根本原因是群体中个体差异缩小，种群多样性锐减。为了降低局部收敛的概率，本文增加了自适应选择策略。按照个体适应度的大小决定个体被选中的概率:适应度越高的个体被选中的概率越大;同理适应度越低的个体选择概率越小。另外还需同时考虑根据进化过程中的不同阶段使用不同的选择压力:进化过程早期以降低选择压力，保存种群多样性为主，使较差的个体也有一定的生存空间;进化后期，主要针对最优个体的局部区域进行搜索，为改善寻优速度，增大选择压力。具体如式(4)所示:

式中:fit(i)表示当前群体中的个体适应度值;f′max表示群体的最大适应度值;f′ave表示群体的平均适应度值;Ps0表示初始选择概率;T为最大进化代数;T1为0到T间的一个常数，表示分割2个过程的节点。

2)交叉算子选择

交叉算子模拟自然界基因重组过程，通过互换部分基因将原有的优良基因遗传给下一代个体，生成的新个体包含了更复杂基因结构。EIBEN提出仅仅以选择算子和变异算子为基础，就可以解决各种任务［10，20-21］。也有研究表明交叉和变异在处理位流文件时对模式的影响作用相同，且HereBoy算法认为交叉是变异的子集。本文延续HereBoy算法的思想，在进行遗传操作中，取消交叉算子转而用变异算子来代替。

3)变异算子自适应调节

变异操作是指染色体中某些等位基因的替换，即某些位置的基因值使用其他值进行替换，从而产生新个体。变异算子的使用对算法性能的影响主要是:实现个体中基因值替换，扩充种群中模式的数量，提高种群多样性;变异操作通过调整个体编码的局部基因，提高算法的局部搜索能力。因此，变异率的选择对算法性能的影响非常重要，变异位数过多促使优良模式丢失，使进化算法性能趋近随机搜索;变异位数过小则会抑制新个体的产生。

本文采用种群中的不同个体变异位数自适应策略，其基本思想是:对于适应度值低于当前群体平均适应度值的个体，使其继续在编码空间上探索，取较大的变异位数;而对于适应度值高于当前群体平均适应度值的个体，使其在当前最优解邻域附近搜索，变异位数取较小值。由于进化后期群体多样性不断下降，个体适应度值容易集中在局部最优的附近，本文将变异位数结合进化代数进行自适应变化，并且优先考虑适应度值的影响，自适应策略模型如式(5)所示:

式中:fave为当前种群平均适应度值;fmax为最佳个体适应度值;fit(i)为当前个体适应度值;L为染色体长度;k依据具体问题选择;T为最大进化代数;T1，T2是介于0到T的2个正整数，为分割进化过程的2个节点。

4 实验结果及分析

以二位乘法器的进化设计为例，按前述矩阵编码方式对可进化区域采用二进制进行编码，适应度值评估种群中不同个体输出正确位的数量，演化过程中采用HereBoy算法并且遗传算子和变异算子跟随进化进程作自适应调整。对比观察了3种算法的适应度值曲线和平均演化时间曲线。为进一步研究自适应遗传算子在演化后期对算法收敛效率的影响，设计实验对比观察采用不同遗传算子情况下，适应度值随遗传代数的增加平均涨幅的变化曲线。

4.1 测试数据集设计

检验算法性能需要进行大量统计实验，选用的实验对象要具有一定的逻辑复杂性，但又要能够通过直接演化得到。本文所选用的验证电路为二位乘法器电路，演化目标是功能正确的数字电路，所以二位二进制乘法电路正确的输入输出组合作为测试数据集。二位二进制乘法器电路有4位输入端和4位输出端，共24=16种输入输出组合，由前述适应度值计算方法，最大适应度值fmax为64。

二位乘法器进化电路模型的规模设定为除去不具备逻辑处理功能的输入层外，输出层节点数目为电路输出端个数4，其隐含层节点为10行8列的矩阵式排列，即(10，10，10，10，10，10，10，10，4)，共84个可重构节点作为电路进化的资源，每个节点包括表1中所列的8种逻辑状态。

表1 电路进化中可重构节点逻辑处理功能类型Tab.1 Reconfiguration nodes logic function type in circuits evolution

4.2 实验条件设定与实验结果

首先，为了验证本文自适应HereBoy算法进化方案的整体性能，将自适应HereBoy算法与标准遗传算法、HereBoy算法在同样的环境中运行，并记录了运行过程中适应度值及平均演化时间的变化。实验中设定种群规模N=8，变异概率Pm=0.5，选择概率Ps=0.2，终止条件设定为最大遗传代数T=3 000，分割节点T1=1 000，T2=2 500。由测试数据集设计中已知共84个2输入1输出的可重构节点，8种逻辑功能用3位基因编码，因此染色体总长度L=87。图4是3种算法在20次独立实验中适应度及演化时间平均值的曲线。

图4 自适应HereBoy算法适应度值曲线对比Fig.4 Comparison of fitness value about adaptive HereBoy algorithm

由图4 a)可知，本文算法和HereBoy算法先后在600代左右和700代左右达到最大适应度的90%，之后，HereBoy算法在4 300代左右达到适应度最大，自适应HereBoy算法由于进化初期遗传算子的调整以加快收敛速度为主，在2 700代左右达到适应度最大值，标准遗传算法在算法终止时仍没有达到适应度的最大值;从图4 b)中可以发现，完成整个进化过程时，自适应HereBoy算法耗时明显少于其他2种算法。

为进一步研究自适应遗传算子在演化后期对算法收敛效率的影响，继续实验对比观察，采用自适应遗传算子与固定遗传算子情况下，适应度值随遗传代数的增加平均涨幅的变化曲线。其中，演化区域大小为7×5，设定种群规模N=8，终止条件设定为最大遗传代数T=5 000。自适应算法中初始变异概率和初始选择概率设为Ps0=0.5，固定变异算子的变异概率Pm=0.2，选择概率Ps=0.5。图5记录了20次独立实验中在适应度值增长幅度随演化进行的变化曲线。

从图5中可以看出使用固定遗传算子的算法在进化前期适应度涨幅与自适应HereBoy算法基本相同，但在电路进化后期，当适应度值增长到一定程度后，传统算法搜索空间减小，适应度值增长缓慢;而使用自适应策略的算法在进化后期由于增大变异算子以提高种群的多样性，适应度值增长仍较快，确保电路进化快速收敛到最优解。

4.3 结果分析

综合以上实验设定与结果，自适应策略的引入改善了进化前期算法的早熟现象和进化后期收敛速度急剧下降的情况，提升了算法的收敛性。实验中将自适应HereBoy算法的适应度值变化与简单遗传算法和HereBoy算法随进化过程的进行做了对比。从对比结果发现，使用本文算法进行电路进化时，算法达到最大适应度值的演化代数明显减少，运算时间有所下降，其收敛性明显优于标准遗传算法和HereBoy算法。另外，在进化后期自适应算子的应用增加了种群的多样性，避免陷入局部最优解，对进化后期收敛速度急剧下降的情况有明显改善，适应度平均涨幅仍在增加，因此，自适应Here-Boy算法对电路进化过程中适应度在进化前期的“早熟”现象和在进化后期存在的适应度增长缓慢的问题提供了一种解决方案。

图5 自适应HereBoy算子与固定遗传算子适应度涨幅曲线Fig.5 Fitness value increasing curve of adaptive HereBoy operator

5结论

本文借鉴多层前反馈神经网络的架构与描述方式，提出一个类神经网络的电路模型。该模型采用矩阵对组合电路进行编码并建立了电路编码到电路功能的映射。借鉴HereBoy算法，融入遗传算法中群体的概念，通过分析自适应因子在进化算法中对演化收敛速率的影响，引入自适应遗传算子提高算法收敛速度和种群多样性，提出了具有自适应能力的电路进化算法。该算法通过染色体的适应度来控制遗传算法的部分参数，在进化后期随着种群演化代数增加适应度值平均涨幅提高。在演化相同规模的数字逻辑电路中，具有自适应能力的进化算法与传统的进化策略相比较，明显地提高了演化效率，增加了大规模复杂电路的进化设计与工程应用的可能性。

［1］ YAO X，HIGUICHIT.Promisesand challengesofevolvable hardware［J］.IEEE Transactionson Systems，Man and Cybernetics，Part C:Applications and Reviews，1999，29(1):87-97.

［2］ TERRILE R J，AGHAZARIAN H，FERGUSON M I.Evolutionary computation technologies for the automated design of space systems［C］//Processdings of the 2005 NASA/DoD Conference of Evolution Hardware.Washington:IEEE Computer Society，2005:131-138.

［3］ KIM J，SONG B.Automated synthesis ofmultiple anolog circuits using evolutionary computation for redundancy-based fault-tolerance［J］.Applied Soft Computing，2012，12:1309-1321.

［4］ ZHANG Yang，SMITH SL，TYRRELL A M.Digital circuit design using intrinsic evolvable hardware［C］//Proceedings of the 2004 NASA/DoD Conference on Evolvable Haraware.Seattle:IEEE Computer Society，2004:55-62.

［5］ 康立山，何巍，陈毓屏.用函数型可编程器件实现演化硬件［J］.计算机学报，1997，22(7):781-784.

KANG Lishan，HEWei，CHEN Yuping.Evolvable hardware realized with function type programmable device［J］.Chinese Journal of Computers，1997，22(7):781-784.

［6］ 刘昌庆，张曦煌.硬件进化中演化算法的研究及应用［J］.计算机工程与设计，2008，29(24);6390-6392.

LIU Changqing，ZHANG Xihuang.Research and application of evolutionary algorithms in evolvable hardware［J］.Computer Engineering and Design，2008，29(24):6390-6392.

［7］ LIANG Houjun，LUOWenjian，WANG Xufa.Designing polymorphic circuits with evolutionary algorithm based on weighted sum method［J］.Evolvable Systems:From Biology to Hardware，2007，4684:331-342.

［8］ ANDERSON E F.Off-line evolution of behaviour for autonomous agents in real-time computer games［J］.Parallel Problem Solving from Nature，2002，2439:689-699.

［9］ LIU Mingguo，WEIYuzhu，HE Jingsong.Evolving diversified redundancies for robust analog circuits under uncertain component-drifts［C］//The 2011 IEEE International Conference on Intelligent Computing and Integrated Systems.Guilin:［s.n.］，2011:349-354.

［10］ EIBEN A，STIVER E.Parameter control in evolutionary algorithms［J］.IEEE Transactions on Evolutionary Computation，2009，3(2):124-141.

［11］ STOICA A，HENDREIR.Adaptive and evolvable hardware-a multifaceted analysis［C］//Second NAsA/EsA Conference on Adaptive Hardware and Systems.Edinburgh:IEEE，2007:486-498.

［12］朱继祥，李元香，夏学文，等.基于演化硬件的在线自适应系统［J］.计算机科学，2009，36(7):267-269.

ZHU Jixiang，LIYuanxiang，XIA Xuewen，et al.On-line self-adaptive systems based on evolvable hardware［J］.Computer Science，2009，36(7):267-269.

［13］刘春草.基于改进遗传算法的电路进化容错修复技术研究［D］.石家庄:河北科技大学，2014.

LIU Chuncao.Circuits Evolution and Fault Tolerance Technology Based on Genetic Algorithm［D］.Shijiazhuang:Hebei University of Science and Technology，2014.

［14］李莉，张锡岭，李飞凡，等.一种非均匀动态子带划分OFDM自适应调制算法［J］.河北科技大学学报，2014，35(6):577-582.

LILi，ZHANG Xiling，LIFeifan，etal.A non-uniform dynamic subband division adaptivemodulation algorithm of OFDM［J］.Journal of HebeiU-niversity of Science and Technology，2014，35(6):577-582.

［15］黄莉静，于乃文，王敬涛.基于均值迁移的粒子滤波算法研究［J］.河北科技大学学报，2014，35(2):184-188.

HUANG Lijing，YU Naiwen，WANG Jingtao.Particle filter algorithm based on mean-shift［J］.Journal of Hebei University of Science and Technology，2014，35(2):184-188.

［16］王友仁，黄媛媛，冯冉，等.基于矩阵编码的量子可逆逻辑电路进化设计方法［J］.电子学报，2011，39(11):2576-2582.

WANG Youren，HUANG Yuanyuan，FENG Ran，et al.Evolutionary design technology of quantum reversible logic circuit based on matrix coding［J］.Acta Electronica Sinica，2011，39(11):2576-2582.

［17］王婷，兰巨龙，邬钧霆.基于演化硬件的硬件重构编码方案及演化算法研究［J］.通信学报，2012，33(8):35-41.

WANG Ting，LAN Julong，WU Yunting.Hardware reconfigurable coding and evolution algorithm based on evolvable hardware［J］.Journal of Communications，2012，33(8):35-41.

［18］梁后军.电路进化设计算法研究［D］.合肥:中国科学技术大学，2009.

LIANG Houjun.Study of Circuit Evolution Algorithms［D］.Hefei:University of Science and Technology of China，2009.

［19］ ZHANGWei，LIWanjian，ZHANGWanqing.Online circuitevolution system based on adjustable genetic algorithm and fast pre-evaluator［J］.Advanced Science Letters，2012，15(2):624-628.

［20］ KIM K J，CHO SB.Combiningmultiple evolved analog circuits for robust evolvable hardware［J］.Intelligent Data Engineering and Automated Learning(IDEAL)，2009，5788:359-367.

［21］ WANG S，YAO X.Multi-class imbalance problems:Analysis and potential solutions［J］.IEEE Transactions on Systems，Man and Cybernetics，2012，42(4):1119-1130.

Research of circuit evolution design based on adaptive HereBoy algorithm

WU Huicong，WANG Jinze，LIU Chuncao，GAO Jinjin
(School of Information Science and Engineering，Hebei University of Science and Technology，Shijiazhuang，Hebei050018，China)

Aiming at solving the convergence rate problem in the latter stage of circuit evolution design，adaptive HereBoy algorithm together with the population evolution idea ofGA is adapted to study the impactof adaptive-adjust factor on the evolution of convergence rate.One circuitmodel which is based on the similarities between combinatorial circuit and neural network is proposed，on which the matrix encoding scheme of combinatorial circuit is discussed.Besides of this，extrintevolution is adapted to evaluate the circuits fitness value，and adaptive-adjust factor in GA is introduced to improve the population diversity and convergence rate.The implementation of 2-bit binarymultiplier circuits evolution shows that the average evolution generations and the evolution time all reduce obviously than conventional HereBoy algorithm，and that the average increase rate raiseswith the increase of evolution generation in the latter stage of circuit evolution.

electronic circuit;EHW;evolutionary of circuits;neural network;HereBoy algorithm;adaptive algorithm

TP275+.5

A

1008-1542(2015)03-0293-07

10.7535/hbkd.2015yx03011

2014-11-19;

2015-01-15;责任编辑:陈书欣

国家重点实验室基金(9140C87040415JB34004);河北省自然科学基金(F2014208113);教育部留学回国人员科研启动基金

吴会丛(1972—)，女，河北深泽人，副教授，博士，主要从事智能计算、演化硬件、数据挖掘等方面的研究。

E-mail:whc@hebust.edu.cn