单位文秘网 2022-02-25 08:42:44 点击: 次
摘 要: 针对制约演化硬件技术发展所面临的可扩展性问题,提出了一种GD⁃BIE分解演化方法,它将待演化电路按照先输出分解后输入分解的顺序,逐步分解为多个子电路,最后将演化成功的子电路有规律的综合完成目标电路的演化设计。实验证明,该分解方法能有效解决大规模电路演化中存在的染色体编码长、最大适应度高、演化代数多、输入输出真值表组合复杂的问题,为较大规模电路演化提供了一种有效途径。
关键词: 演化硬件; 扩展性问题; 分解演化; 大规模电路
中图分类号: TN710⁃34; TP316 文献标识码: A 文章编号: 1004⁃373X(2013)23⁃0151⁃03
Research on the decomposition evolution for complex digital circuit
LOU Jian⁃an, LI Yang, YU Jian⁃hua
(Department of Vehicle and Electrical Engineering, Ordnance Engineering College, Shijiazhuang 050003, China)
Abstract: In view of the scalability problem faced by evolvable hardware technology development, a GD⁃BIE decomposition evolution method is proposed, which decomposes the circuit for evolves into multiple sub circuits with the order of the output decomposition before input decomposition. Finally, it achieves the evolving goals by regularly combining all sub circuits. The experiments shows that the proposed decomposition method can effectively solve the scalability problem in large scale circuit evolution, such as long chromosome coding, high maximum adaptation degree, large evolution algebras and complex truth table combination of input and output. The GD⁃BIE method provides an effective way for large⁃scale circuit evolution.
Keywords: evolvable hardware; scalability problem; decomposition evolution; large⁃scale circuit
1 演化硬件的可扩展性问题
演化硬件技术是一种面向行为级描述的电路综合设计技术[1],其不依赖于设计者的先验知识和丰富经验,只需给出电路的高层次描述(如波形图、相位图、真值表等),演化算法根据设定条件搜索满足条件的电路结构,有利于提高电路设计的自动化程度。尽管演化硬件在设计小规模电路(比如乘法器、译码器、简单逻辑电路等)上取得了成功,但在大规模电路设计上仍然面临着可扩展性问题(scalability)[2]。所谓可扩展性问题是指当目标电路演化规模较大时,演化设计方法的效率十分低下,甚至不能演化出目标电路。文献[3]分析了演化硬件技术相比于传统方法的技术优势和自提出以来取得的重大成果,也指出了可扩展性问题是制约演化硬件技术发展和面向现实世界应用的一个重要因素。
造成演化硬件可扩展性问题的因素主要有三个:
(1)染色体编码长度过长,演化计算效率很低。染色体基因由逻辑门编码和连接关系编码组成,而且演化过程中还存在大量的冗余逻辑单元,因此目标电路的演化规模越大,需要的冗余单元越多,演化一个100个逻辑单元的电路,染色体长度通常达到上千位,而演化扩展计算带来极大的困难。
(2)输入输出组合过多,算法搜索空间极大。随着演化规模的增大,输入输出数量也越来越多。真值表的长度与输入个数呈指数级关系,真值表的扩大给电路个体适应度评价带来巨大的困难。
(3)真值表的复杂度增加,使算法的搜索空间增大,直接引起个体适应度的评估时间增加,进一步导致演化速度的降低。
2 分而治之的演化思想
针对以上三个造成演化硬件可扩展性问题主要因素,国外一些研究者首先提出了“分而治之”(Divide⁃and⁃Conquer)的演化分解方法[4],以期降低单次演化的规模,减短染色体编码程度,缩小算法搜索空间,从而解决电路演化的可扩展性问题。
最典型的“分而治之”的分解演化方法是Tatiana Kalganova提出的双向增量演化(Bi⁃direction Incremental Evolution,BIE)[5]和E.Stomeo等提出的通用分解演化算法(Generalized Disjunction Decomposition,GDD)[6]。BIE的主要思想是首先将电路分解成若干个子电路,分别进行演化,当所有的子电路都演化完成后,再把它们组合成整个电路,并在不影响电路功能的前提下进行必要的优化,但是该方法对电路输入组合多的情况显得无能为力。GDD的基本思想是在演化过程开始之前根据经验对整个系统进行输入分解,将整个待演化系统分解成可演化部分(G)和固定部分(H):可演化部分的输入是待演化系统输入的一部分,其个数必须足够小到利用 BIE 分解算法能够进行充分演化;而固定部分则是由事先设计好的选择器组成,原系统余下输入是其选择信号端,G 的输出是其输入信号。GDD方法有效解决了电路输入组合多的难题,但对于电路输出多的情形下,仍然存在适应度评价困难的问题。
文献[7⁃8]介绍了通用分解演化结合双向增量演化(GD⁃BIE)的演化方法,该方法综合的GDD方法的输入分解优势和BIE方法输出分解的特点可演化出较大规模的电路,但分解过程需依赖于设计者的经验。本文提出一种改进的GD⁃BIE分解演化方法,该方法只需设定好固定部分的参数,对于不同的目标电路需从细微处调整分解算法就能演化出同等规模范围的数字电路,基本实现电路的设计自动化。
3 改进GD⁃BIE分解演化实现
3.1 分解原理
本文提出的改进GD⁃BIE方法,是结合GDD方法的真值表分解和BIE方法的全自动分解及组合优势而提出的一种分解演化方法,其主要的思想仍然是“分而治之”的分解演化策略。分解演化的方法称作分而治之的方法,也可以作为是自生长的演化方法[9],其通过多个子系统演化来降低演化算法的搜索空间,降低每次的演化难度,每次先演化简单的模块,最后通过简单模块的组合生成复电路。
如图1所示为GD⁃BIE方法的分解设计描述,图1(a)是一个待演化的普通[m]输入[n]输出的目标电路,如果该电路中[m]和[n]过大,直接对其演化将导致演化过程出现可扩展性问题,从而导致演化设计效率低下,甚至是设计失败。图1(b)是对输出进行分解的演化模型,借鉴BIE分解特点,对其输出分解为两个及其以上的子电路,从而以多次演化的方式减少单次电路演化的输出个数。图1(c)是将输入和输出都进行分解的演化模型,该步骤选取电路的[m]个输出中的[(m-t)]个作为待演化子电路的输出,剩下的输入不再参与演化,而是进入固定部分H作为演化输出的选择信号。图1(d)是对分解后的子电路进行组合的模型,最后完成整个目标电路的演化。
图1 GD⁃BIE分解
3.2 分解描述
实验以四位全加器为例,直观说明电路的分解、演化和组合过程。四位全加器电路为一个8输入5输出组合逻辑电路,其分解过程如图2所示。
由图2(a)可见,电路的原始真值表输入规模达100×8,输出真值表达100×5,对于这种规模下的目标电路演化最大适应度将达到500,如果对其直接演化将导致染色体编码过长、演化算法搜索效率低下以及适应度评价及其困难等大规模电路演化过程中常见的可扩展性问题。因此,要想完成如此规模的电路演化设计,分解演化的方法就具有了应用意义。图2(b)所示为对原始真值表进行输出分解,将目标电路真值表分解为一个8输入4输出子电路和一个8输入1输出子电路系统,该步骤将降低待演化大量的最大适应度值。图2(c)与图2(d)分别演示了对图2(b)中的两个子电路系统的进一步分解,其分解原理是把电路的8个输入中的4个作为分解后子电路的演化部分输入,另外剩下4个输入作为子电路的选择信号,该步骤完成后,目标电路被分解为2×16=32个子电路。
3.3 演化实验
实验时,电路采取笛卡尔遗传程序编码(Cartesian Genetic Programming,CGP),分解后的子电路规模分别为4×4和4×1,最大适应度值为64和16,基本逻辑门包括:与门、或门、与非门和或非门。最终电路需要用到64输入8输出的多路选择器,但其不参与演化。演化算法采用遗传算法,种群规模为20,交叉率为0.75,变异率为0.01,最大演化代数为200 000。分解演化算法重复运行10次,32个子电路均达到100%演化设计成功,其演化代数分布如图3所示。
由图3中可见4×4子电路的最大演化代数在16 000代以下,有些子电路甚至只需几百代就能演化成功,4×1子电路由于最大适应度值为16,故所需演化代数更少。虽然GD⁃BIE分解演化方法进行了32次电路演化,但是却成功演化出来了目标电路的所有功能,这在不采用分解方法演化时是不可能完成的任务。正是如此,证明了分解演化方法在大规模电路演化设计上的作用和意义。
图3 子电路演化代数分布
4 结 论
可扩展性问题是制约演化硬件面向复杂数字电路演化设计的一项技术难题。针对这一难题,本文提出一种GD⁃BIE分解演化方法,该方法综合利用BIE和GDD分解方法的特点和各自优势,对复杂数字电路能够实现较大规模的演化设计。实验证明,该分解演化方法对电路真值表的输入输出进行分解,然后对子电路分别演化以达到降低目标电路复杂度目的,有效地解决了复杂数字电路演化设计的可扩展性问题。
参考文献
[1] THOMPSON A. Hardware evolution: automatic design of electronic circuits in reconfigurable hardware [M]. London: Springer⁃Verlag, 2012.
[2] VASSILEV V K. Scalability problems of digital circuit evolution[C]// Proceedings of the 2nd NASA/DoD Workshop on Evolvable Hardware. Palo Alto, CA: NASA/DoD, 2000: 55⁃64.
[3] YAO X, HIGUCHI T. Promise and challenges of evolvable hardware [J]. IEEE Transactions on Systems, Man, and Cybernetics⁃Part C: Applications and Reviews, 1999, 29(1): 87⁃97.
[4] TORRESEN J. Evolving multiplier circuits by training set and training vector partitioning [C]// Proceedings of 5th International Conference on Evolvable Hardware. Trondheim, Norway: ICES, 2003: 228⁃237.
[5] KALGANOVA T. Bidirectional incremental evolution in evolva⁃ ble hardware[C]// Proceedings of 2nd NASA/DoD Workshop on Evolvable Hardware. Palo Alto, CA: 2000, NASA/DoD: 65⁃74.
[6] STOMEO E, KALGANOVA T. Improving EHW performance introducing a new decomposition strategy[C]// Proceedings of the 2004 IEEE Conference on Cybernetics and Intelligent Systems. Singapore: IEEE, 2004: 439⁃444.
[7] STOMEO E, KALGANOVA T, LAMBERT C, et al. On evolution of relatively large combinational logic circuits[C]// Proceedings of NASA/DoD Conference Evolvable Hardware. Washington DC, USA: NASA/DoD, 2005: 59⁃66.
[8] STOMEO E, KALGANOVA T, LAMBERT C. Generalized disjunction decomposition for evolvable hardware [J]. IEEE Transactions on Systems, Man and Cybernetics, Part B: Cybernetics, 2006, 36(5): 1024⁃1043.
[9] TORRESEN J. Increased complexity evolution applied to evolva⁃ ble hardware[C]// Proceedings of ANNIE on Smart Engineering System Design: Neural Networks, Fuzzy Logic, Evolutionary Programming, Data Mining, and Complex Systems. St. Louis, USA: ANNIE, 1999: 429⁃436.
(责任编辑:单位文秘网) )地址:https://www.kgf8887.com/show-231-101770-1.html
下一篇:基于单片机的电源切换控制设计研究
版权声明:
本站由单位文秘网原创策划制作,欢迎订阅或转载,但请注明出处。违者必究。单位文秘网独家运营 版权所有 未经许可不得转载使用