一种新的基于真值表分解技术的电路加速演化策略(自动化)
孟亚峰, 张峻宾,蔡金燕
(军械工程学院电子与光学工程系,石家庄050003)
摘要:硬件演化技术在电路演化过程中具有自组织、自适应、自修复性能,具有重要的工程应用价值,硬件演化技术能够实现的核心就是演化算法。目前中等规模及大规模电路演化的时候存在演化速度慢等缺陷,直接影响电路演化的时效性。提出了一种新颖的电路加速演化策略,即基于真值表分解的电路演化策略,从不同的角度对电路演化算法进行了改进,有别于常规的改进演化算法。通过对典型电路进行仿真分析,证明了所提出的加速演化策略的有效性,并且具有重要的应用价值。
关键词:硬件演化;电路演化;演化算法;真值表分解技术;加速演化
中图分类号:TP301.6 文章编号:1671-637X(2016)04 -0062 -04
0 引言
随着电子技术的不断发展,为提高电子电路在各种复杂、恶劣环境的自适应性,近年来兴起了一种新颖技术——硬件演化( Evolvable Hardware,EHW)技术。
硬件演化公式可表示为硬件演化=可编程逻辑器件+演化算法。硬件演化是以演化算法为组合优化和全局搜索的工具,通过模拟进化来获得预期的电路或系统结构。
正因如此,采用EHW技术,能够使电路具有自适应、自组织、自修复的能力。可编程逻辑器件( Program-mable Logic Device,PLD)是EHW的硬件基础,而演化算法( Evolutionary Algorithm,EA)是EHW技术能否实现的关键。
目前,EA存在演化速度慢、容易陷入局部最优等缺陷,因而对EA进行改进是现在的一个研究热点。改进的目标都是为了加速EA的收敛、减少迭代次数,而较多采用遗传算法及其改进算法和粒子群算法及其改进算法,或者是采用动态变异率演化算法副。在针对大规模电路进行演化的时候,目前主流演化算法的策略为分而治之。
本文针对组合逻辑电路演化过程中真值表所表现出来的特点,提出了一种基于真值表分解技术加速电路演化的策略,并进行了仿真分析。1 真值表分解技术加速演化电路基本策略。
在实现演化算法的过程中,当面临大规模的真值表的口寸候,演化电路的规模将随真值表输入端个数的增加呈指数增加。但是,演化收敛的速度将随真值表规模的增加呈指数降低,因此提高具有大规模真值表的电路演化速度将显得格外重要。对真值表进行必要的拆分,能够在很大程度上提高演化算法的收敛速度。
为了解决复杂电路快速演化问题,TORRESEN J将“分而治之”思想引入到EHW技术之中,而拆分真值表技术是分而治之( divide-and-conquer)的深化,在演化过程中,结合二元判决图( Binary Decision Diagram,BDD),将真值表实行一层一层的剥离。
在对真值表进行拆分的时候,不能拆分得太细,因为实现同样功能的电路拓扑结构可能不一样,拆分得太细就不能表现出电路结构的多样性。例如有如下的电路布尔函数:Y1=AB+AC,Y2 =A(B+C),如图1所示。
从Y1和Y2可以看出,虽然它们有相同的具体功能,但是电路结构完全不一样,所消耗的硬件资源也不一样,各有各的特点。不能直接判定哪一种电路结构好,哪一种电路结构差,需要根据具体的问题环境,找出所需要的电路结构。如果采用真值表分解技术将真值表全部进行分解,将只能得到一种固定不变的电路结构;如果采用真值表分解技术同EHW技术相结合,不仅可以演化出相同功能的不同结构的电路,还能加速电路的演化。
为了有利于演化算法的展开,使演化算法的自适应、自组织特点得到有效的发挥,本文采用的方法是将真值表拆分到只剩4个输入组合为止,剩余的4个输入端再采用演化算法进行演化,得到最终的目标电路。拆分至4个输入端的另一个参考依据是目前主流FP-GA的查找表(Look-up Table,LUT)具有4个输入端,且目前FPGA被作为硬件演化的硬件平台。
虽然FPGA的LUT相当于一个ROM,能够直接存储任意4输入1输出的真值表,本文为了更好地在电路设计过程中对演化算法的自适应自组织特性进行展示,对剩余未拆分电路采用演化算法进行设计。
在基于真值表分解技术的电路演化过程中,根据BDD原理,将大规模电路拆解成了关联度较小的小规模电路,将纯粹的电路演化过程变成了电路演化和BDD的有效结合过程。而小规模电路在电路演化的时候,约束条件较少,相对于大规模电路的电路演化搜索到目标电路编码将比较容易,演化算法迭代次数将大幅度缩减,同时收敛速度也将加快。
本文中演化算法采用遗传离散粒子群算法( Ge-netic Algorithm Discrete Particle Swarm Optimization,GADPSO)。CADPSO演化算法是将遗传算法(GeneticAlgorithm,GA)的交叉、变异融合于离散粒子群算法( Discrete Particle Swarm Optimization, DPSO)之中,(GA算法在优化问题方面限制很小,对目标函数及约束要求很低,具有较强的鲁棒性和适应性,虽然收敛速度比较慢,但是能够较好地克服寻优过程中易陷入局部最优的缺点。然而DPSO搜索速度较快,因此将GA算法和DPSO算法相结合能克服相互的缺陷,将GADPSO演化算法引入电路演化,能够极大地减少演化目标电路编码所需要消耗的时间。能明显提高粒子群的多样性,有助于改善DPSO算法的收敛速度和收敛精度。
2 加速演化策略的步骤
任何一个真值表均能表示成一个布尔函数。首先
完成真值表拆分之后,紧接着施加GADPSO演化算法,如图2所示。
GADPSO演化算法实现的步骤如下所述。
选择、交叉、变异操作。
4)更新各个粒子的位置和速度。
5)计算每一个粒子的适应度值,并和全局最优值进行比较,对全局最优值进行更新。
6)根据计算出的适应度值判断算法是否满足收敛标准,如果满足,则输出最终粒子编码;如果不满足,则转入步骤3)。
7) GADPSO算法结束。
3 仿真验证与分析
为了验证所提出的基于真值表分解技术在电路演化过程中的有效性,选取带进位的两位加法器作为典型电路进行仿真研究,其真值表如表1所示。由于篇幅的关系,表1中只列出了真值表的部分输入输出关系。其输入从00000 -直到11111,一共32个组合。
在进行真值表分解的时候,由演化算法进行输入端的分离。根据约束条件,演化算法将A1输入端选出,A1有“0”,“1”两种取值,取“0”的时候为A1,取“1”的时候为A1,以此为标准将真值表划分为两部分。对于剩下的输入端仍然采用划分A1的标准进行分解,直至未分解的输入端剩余4个即可。由于表1本身只有5个输入端,因而只需要拆分一次真值表即可。
在演化过程中设置适应度函数为
采用GADPSO算法进行20次仿真分析,同时设置GADPSO算法的相关参数。令初始化样本数,N=40,变异率pd=0. 05,交叉率pc=0.95,交叉算子采用2点交叉,变异算子采用2点变异。
最后得到仿真数据如图3所示。
从图3中可以清晰地看出,在20次仿真分析中,采用真值表分解技术实现电路演化的平均演化迭代次数都远远小于直接对真值表进行电路演化。
并且数据统计表明:基于真值表部分分解平均演化迭代次数是3407次,然而,没有采用真值表部分分解技术的平均演化迭代次数是16 915次。
前者只对真值表进行了一次分解,即待演化的目标电路分解成了两个子电路,并结合式(1),演化出目标电路的布尔函数。通过仿真对比分析,可以看出真值表分解技术能够极大地加速演化算法的收敛速度,在仿真中,基于真值表分解技术在加速电路演化方面的有效性也得到了证明。
4结论
本文从不同的视角,提出了一种基于真值表分解的加速电路演化策略,有别于常规的改进演化算法。通过仿真分析,证明了所提出的策略在电路加速演化方面的有效性,同时保证了电路的多样性,此技术的优势在组合电路的演化方面得到了很好的体现。