新颖的基于遗传算法的数字电路的多目标优化设计

(河南财经政法大学计算机与信息工程学院，河南郑州，450046)

新颖的基于遗传算法的数字电路的多目标优化设计

鲍治国,卢照敢

(河南财经政法大学计算机与信息工程学院，河南郑州，450046)

针对基于遗传算法的数字电路的多目标优化设计问题，采用了带有均匀交叉的遗传算法,并且考虑到了多种制约条件,如：电路的复杂度,功耗,信号延迟等。结果电路的正确性，构成的复杂度，功耗和信号延迟等指标，可以采用适应度函数来评价。通过自动生出2位全加器的实验,验证了这种方法的有效性。实验结果证明,新提出的方法,在最优适应度函数值和平均适应度函数值方面,优于传统的遗传算法。

进化算法；遗传算法；均匀交叉；进化硬件；电路设计；多目标优化

0 引言

在人工智能领域，进化算法（Evolutionary Algorithm,EA）是一种常用的以种群为基础的启发式算法。遗传算法(Genetic Algorithm,GA)是一种典型的进化算法。

进化硬件(Evolvable Hardware,EHW)是进化算法的应用之一。进化硬件可以作为硬件设计的一种选择。通过进化算法可以自动的生成电路，进化硬件看上去很成功，也很有前景。然而，进化硬件用于设计实际的电路时，还存在着一些问题，如：可扩展性，可维护性和通用性等。一些研究者对进化速度进行了探讨，一些研究者对编码方法进行了探讨。电路的多目标优化设计，也是一个尚待解决的问题。

本文提出的电路优化设计方法，考虑到了电路的复杂度，功耗和信号延迟等，实现了电路的多目标优化设计。不同的逻辑门，有不同的复杂度，功耗和信号延迟。在新的半导体技术中，连线的功耗和信号延迟，也不能被忽略，也要考虑进来。遗传算法通过交叉变异等操作，可以改变电路中一些逻辑门的功能和连线方式；通过适应度函数，可以评价结果电路的正确性和优化度。因此，遗传算法通过进化可以找到构造简单，连线较短，功能正确的目标电路。用这种方法，自动生成了2位全加器的设计电路，对提出算法的有效性进行了验证。

1 带有均匀交叉的遗传算法

遗传算法是一种广泛使用的搜索技术，对于搜索问题和优化问题，常用于寻找最优解或者次优解。遗传算法从一些个体组成的种群中开始搜索。在种群的初始状态,每个个体都是随机产生的。在进化阶段,用适应度函数来评价每个个体符合要求的程度。每代的最优个体被保留下来；此外,通过选择,交叉和变异等操作,产生一些新的个体。因此,将使种群像自然进化一样,后生代种群比前代更加适应于环境的要求。

遗传算法中起重要作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以提高。

参数化均匀交叉是用比赛选择法选出两个父代个体，以某个概率选出一些基因进行替换重组，重组后新的个体作为下一代的个体。参数化均匀交叉可以在较大的空间内,以比较公平的方式发挥作用,可以增强个体的多样性，会有更强的全局搜索能力，因而，更有可能找到较好的方案。

2 基于遗传算法的电路优化设计

2.1 目标

在电路的优化设计中，通过应用新颖的遗传算法，找到较优化的解决方案。目标电路提供符合要求的功能行为，并且需要较少的复杂度，更低的功耗和更少的信号延迟。实验中，用2位全加器作为实例，介绍了遗传算法如何自动生成目标电路。

2.2 遗传编码

为了方便的处理遗传编码，目标电路被看作是一个两维的逻辑门阵列，如图1所示。每个逻辑门，有两个输入，一个输出。第一列逻辑门的输入，来自基本输入；以后各列逻辑门的输入，来自前面各列逻辑门的输出。可以用一串数字作为一个染色体表示一个电路。每三个数字表示一个逻辑门，如：

(输入1， 输入2，函数功能)。

一个染色体可以是一串数字,如:

这里，xi是((now_columns)*(number_of_rows) - 1)，now_columns是逻辑门所在的当前列，取值范围是[1,5]；number_of_rows是逻辑门阵列的行数，值为5。当xi＜=4时，输入是基本输入；当xi＞=5时，输入是逻辑门xi的输出。函数的功能编码如表1所示。

2.3 适应度函数

适应度函数的目标是得到功能正确的电路，并且在电路构成的复杂度，功耗和信号延迟方面尽量优化。函数F1被用作评价结果电路输出的正确性，函数F2被用作结果电路在构成的复杂度，功耗和信号延迟方面的评价。

如表1所示，在电路构成的复杂度，功耗和信号延迟方面，不同的逻辑门被指定不同的评价值。复杂度的设定，考虑了逻辑门用到的晶体管的数量，也可以理解为晶体管的数目，或者逻辑门的面积。如图1所示，每个逻辑门的输入和输出被指定不同的坐标，便于计算电路中连线的长度。

num_testdata 是测试数据的数量，num_rightout是结果电路的正确输出结果的数量。

Ev: 电路的复杂度，功耗，信号延迟的综合评价值。Tmax:固定的大于Ev的数，实验中被设定为1.5*1010。

Cg: 结果电路中所有逻辑门的复杂度的评价值。αcg: 逻辑门复杂度的权重。cgi:逻辑门i的复杂度。

Pg: 结果电路中所有逻辑门的功耗评价值。αpg: 逻辑门功耗的权重。pgi: 逻辑门i的功耗的评价值。

SD: 结果电路的信号延迟的评价值。αsd: 信号延迟的权重。sdouti: 逻辑门i输出处的信号延迟。sdgi: 逻辑门i自身的信号延迟。sdw(i,inx): 连接到逻辑门i的输入inx的连线的信号延迟。sdout(i,inx): 连接到逻辑门i的输入端inx的逻辑门的输出端的信号延迟。sdwj: 连线j的信号延迟。xbwj:连线j的开始端点的X坐标。ybwj: 连线j的开始端点的Y坐标。xewj: 连线j的结束端点的X坐标。yewj: 连线j的结束端点的Y坐标。βsdw: 连线的信号延迟的系数，实验中被设定为1。

Pw: 结果电路中所有连线的功耗。αpw: 连线功耗的权重。pwj: 连线j的功耗。βpw: 连线的功耗的系数，实验中被设定为1。

N: 结果电路中逻辑门的数量。

在计算式2中，评价项目的优先顺序是:Cg＞Pg＞S D＞Pw。在这个实验中，αcg被指定为 1*108,αpg 被指定为1*106, αsd被指定为 1*103, αpw 被指定为 1.

函数F1被用作评价结果电路输出的正确性，函数F2被用作结果电路在构成的复杂度，功耗和信号延迟方面的评价。当结果电路不完全正确时(F1＜100)，主要关注电路的正确性；当结果电路正确时(F1=100)，主要关注电路的优化度。

表2 进化参数的设置Table 2 Conditions for evolution

3 实验和分析

实验是为了验证新颖的遗传算法在电路优化设计方面的有效性。遗传算法用到的遗传参数的设置如表2所示。为了确定适合这个实验的参数,做了一些前期的实验。

实验是在Eclipse SDK 3.5.1环境下用Java Runtime Environment 1.6.0实现的；测试是在个人电脑上完成的，Inter(R) Core(TM)2 的内核，主频 2.67G 赫兹，2G 的内存。

实验中对于遗传算法采用不同的交叉方法进行了对比，实验结果如表3所示。对于每种方法，都是独立运行了30次。“best”: 30次结果中最好的适应度值。“quality”: 最优的结果中相对于一点交叉的优化度。“average”: 最优的5次结果中平均的适应度值。“var”:正确的结果中适应度值的样本方差。“quantity”: 30次运行结果中最终结果正确的运行次数。“time”: 30次运行的平均运行时间。

从实验结果可以看出，在最优适应度值，最优的5次适应度值的平均值方面，均匀交叉优于一点交叉。

适应度函数值为162.44的结果电路如图2所示。图2对应的结果电路，输出结果正确，使用的逻辑门较少，功耗和信号延迟较少，因此，对应的评价值较高。

4 结束语

本文提出了一种基于遗传算法的新型电路优化设计的方法，除了考虑到结果电路的输出正确性外，还考虑到电路构成的复杂度，功耗和信号延迟等。在适应度函数中，首先考虑到了输出结果的正确性，其次考虑到了优化度。通过遗传算法的进化，可以找到较优化的结果电路。从实验结果可以证明，采用均匀交叉的算法可以找到较优化的电路。

这种方法也可以被用到规模较大的电路上。另外，在评价值的设定上，可以更加接近实际值。

[1] T.Schnier and Xin Yao.Using multiple representations in evolutionary algorithms [C].Proc.of the 2000 Congress on EvolutionaryComputation,La Jolla,CA,2000: 479–486.

[2] J.H.Holland.Adaptation in Natural and Artificial systems[M].The University of Michigan Press, 1975.

[3] 柏磊.数字电路进化设计算法研究（D）.博士，南京理工大学，2012.

[4] 杨华秋.可进化硬件平台研究(D).硕士，复旦大学，2011.

[5] 姜庆辉.演化硬件技术研究(D).硕士，中国科学院研究生院(西安光学精密机械研究所)，2011.

[6] X.Yao and T.Higuchi.Promises and Challenges of Evolvable Hardware[J].IEEE Trans.on Systems, Man,and Cybernetics,Part C:Applications and Reviews,1999, 29(1): 87-97.

[7] Z.Bao and T.Watanabe.A Novel Genetic Algorithm with Cell Crossover for Circuit Design Optimization [C].Proc.of the IEEE International Symposium on Circuits and Systems(ISCAS 2009),Taipei,Taiwan, 2009:2982-2985.

[8] 柏磊，顾陈，严璐，等.基于适应度评价扩展自适应遗传算法的门级电路进化设计[J].南京理工大学学报，2011，35(2):240-244.

[9] 梁腾腾，邓平科，林宝军.可用于演化硬件的改进自适应遗传算法研究[J].计算机工程与设计,2012,33(2):711-717.

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

Multi objective optimization design of digital circuit based on genetic algorithm

Bao Zhiguo,Lu Zhaogan
(College of computer and information engineering,Henan University of Economics and Law,Zhengzhou, Henan,450046)

Aiming at the multi-objective optimization design of digital circuit based on genetic algorithm, a genetic algorithm with uniform crossover is adopted, and a variety of constraints are considered,such as the complexity of the circuit, power consumption, signal delay, etc.. Results the correctness of the circuit, the complexity, power consumption and signal delay and so on, can be used to evaluate the fitness function. The validity of this method is verified by the experiment of 2 full adder. Experimental results show that the new method is better than the traditional genetic algorithm in terms of optimal fitness function value and average fitness function value.

evolutionary algorithm;genetic algorithm;uniform crossover;evolutionary hardware;circuit design;multi objective optimization

教育部留学回国人员科研启动基金资助项目(教外司留[2013]1792号)；河南省基础与前沿技术研究计划项目（132300410240,132102210140）；河南省教育厅科学技术研究重点项目（13B520903,12A510001）资助.

鲍治国,男,1977年生,博士,讲师, CCF会员,主要研究方向:进化计算,进化硬件,多目标优化;卢照敢,男,1977年生,博士,讲师,主要研究方向:电路设计,无线通信.