【作者】 梁后军；

【导师】 王煦法； 罗文坚；

【作者基本信息】 中国科学技术大学 ， 计算机应用技术， 2009， 博士

【摘要】 电路进化是一种基于群体搜索和可编程硬件的智能进化设计方法。它的出现是智能算法与可编程硬件共同促进的结果,正受到越来越多的关注。使用进化算法设计的电路,能发现新颖的人们难以想到的电路结构,能降低需要的门资源或晶体管数量从而提高芯片的利用率,能降低电路的连接级数提高信号的传输速度。若使用内部进化的方式设计电路,还能使所得电路具有自组织、自修复、自适应的特性。因此开展电路进化设计研究具有重要的应用价值。目前有关电路进化设计的研究还不是很成熟。不论是内部进化方式还是外部进化方式,所能设计的电路规模都比较小,很难付诸实际应用。本文旨在通过对组合逻辑电路进化设计、时序电路进化设计和多态电路进化设计等进行深入研究和探索,提出高效的进化设计算法与策略,从而提高电路进化设计算法的求解性能。论文的主要研究工作与创新点包括以下几个方面:(1)提出了基于修复技术的组合逻辑电路快速进化设计算法。该算法利用候选电路在进化的初始阶段适应度增加很快的现象,先进化出一个功能大致正确的电路;然后转入修复过程并对不正确的输出进行修正,最终设计出功能正确的电路。实验结果表明了该算法是有效的。为了能对进化出的有错误的电路进行修复,专门设计出了简单而规整的修复电路的构造方法。附加的修复电路与进化生成的对大部分输入都能输出正确结果的电路结合在一起,形成最终的功能完全正确的电路。该方法极大地减少了进化所需的时间。(2)提出了基于三步分解方法的同步时序电路进化设计算法3SD-ES。该方法结合低功耗技术中已有的时序电路分解方法、进化设计领域中的输入分解、输出分解方法及进化策略。实验结果表明该算法具有更好的可扩展性。对时序电路而言,状态分解的粒度参数、输出分解的粒度参数及输入分解的粒度参数三者之间互相关联,手工设置往往顾此失彼。针对这一问题,本文给出了自动设定分解参数的方法。(3)提出了基于加权方法的多态电路进化设计算法。该算法针对多态电路中各功能电路进化难度不同的特点,首先提出了基于加权和方法的进化算法,实验结果显示除了个别电路外,基于加权和方法的进化算法的性能好于传统进化算法。然而,加权和方法需要事先做很多实验来确定各电路的难易程度,以便设置合理的权重。针对此问题,本文又进一步提出了动态加权法。实验结果表明对大多数测试电路动态加权法的效果优于加权和方法。本论文以进化算法为基本手段,对组合电路、时序电路和多态电路的进化设计进行了较为深入的研究。这不仅对电路进化设计的研究有着重要的意义,也对促进智能计算的应用研究有重要的意义。更多还原

【Abstract】 Circuit evolution is a kind of intelligent design method based on population-based algorithms and programmable hardware.It is a result of the development of evolutionary algorithms and programmable hardware.Recently,it has received more and more attentions,and has become a hot research field in the EHW field.Evolutionary techniques can find novel topologies of circuits;reduce the resources that are needed to build a circuit,increase transmission speeds of signals, etc.When the circuits are designed intrinsically,they can also have the characteristics of self-organizing,self-repairing and self-adaption.Therefore,the research on circuit evolution has great applicational value.Currently,the research on circuit evolution is still at the initial stage.Both intrinsic evolution and extrinsic evolution can only evolve small-scale circuits and it is hard to apply them in real world applications.The aim of this dissertation is to design effective algorithms and strategies for the evolutionary design of circuits and to do the corresponding experimental analyses by further exploring combinational circuit design methods,sequential circuit design methods and polymorphic circuit design methods.The main research works in this dissertation consist of the following aspects.(1) Based on the mending method,an efficient evolutionary design algorithm for combinational logic circuits is proposed.The evolutionary designing of circuits is now facing the problem of "stalling effect",which means that during the evolutionary process,the fitness value increases rapidly at the initial stage,however,when it reaches a certain percentage of maximum fitness value,the fitness value will increase very slowly.Based on the phenomenon of "stalling effect",the proposed algorithm switches to the mending stage after the initial stage.If the output is incorrect,the algorithm will mcnd the circuit to get the correct result.The empirical results demonstrate the proposed algorithm is effective.In order to mend the circuit(with minor errors) obtained from evolutionary process,a simple regular method for designing the additional mending circuit is proposed.The mending circuit is combined with the circuit that has some errors to form a 100%functionaly correct circuit.It can reduce evolutionary generations and time greatly. (2) For the evolutionary design of sequential logic circuits,a three step decomposition method named 3SD-ES is proposed.The algorithm integrates the decomposition method used in low-power techniques,the input decomposition method in the evolutionary design,the output decomposition method and ES.The experimental results show that this algorithm has better characteristic of expansion. The parameters of state decomposition,output decomposition and input decomposition affect each other.It is hard to set these parameters manually.In order to overcome this problem,an algorithm is proposed which can set the values automatically.(3) Based on the weighted sum method,an efficient evolutionary design algorithm for polymorphic circuits is proposed.Because the different functional circuits in the polymorphic circuit have different degree of difficulty,the algorithm based on the weighted sum method is proposed and the empirical results demonstrate that the algorithm has better performance than traditional EAs except for a few circuits.However,the weighted sum method needs a lot of experiments to evaluate the degree of difficulty beforehand in order to set appropriate weights.To overcome this problem,a dynamic weight adjustment method is proposed.Experiments demonstrate that this method is better than the algorithm based on weighted sum method.In this dissertation,the evolutionary algorithm ES is adopted for further exploring automatic and intelligent design of combinational logic circuits,sequential logic circuits and polymorphic circuits.The works in this dissertation not only can improve the research of evolutionary designing of circuits but also can promote the appilications of intelligent computation.更多还原