一位全加器优化设计算法的研究

罗文静 范进高 会 丹 王娜娜 颜雪松

（中国地质大学（武汉）计算机学院，湖北武汉 430074）

电路优化技术是电路设计领域不可忽略的一个部分，电路优化能提高效率、降低能耗从而节约现实成本。近年来也出现越来越多的电路优化方法被运用到电路硬件设计领域。尽管如此，传统电路优化技术仍然存在几个方面的挑战：（1）如何让电路优化自动化；（2）设计平台的可编程性（3）如何能在较短时间内达到理想优化结果；（4）如何减少电路器件门数。

一位加法器电路优化设计属于电路硬件设计范畴，用传统电路设计方法明显达不到理想的结果。为了优化一位加法器设计，引入演化硬件技术（Evolvable Hardware，EHW ）。演化硬件技术是一种能够被用来替代传统电路设计的方法，用自可编程门阵列（Field Programmable Gate Arrays，FPGA）作为硬件演化平台，能通过演化算法自动生成数字电路。

对于一位加法器硬件电路的算法设计与优化，我们采用改进遗传算法（Modified Genetic Alogrothm，MGA）来设计组合数字电路。简单的遗传算法效率较差，我们通过引入跨世代精英机制和其他策略对简单遗传算法进行改进，设计了一种改进遗传算法以提高演化效率。本文采用的编码方式为矩阵单元三元组整数编码，采用的个体评估策略为贪婪策略；设计各种不同的选择、交叉、变异策略等其他算子，运用到各种算法中去。本文采用的算法策略以及优化方法对于设计数字滤波器、乘法器、多态数字电路等同样适用。

1 算法编码

1.1 矩阵单元三元组整数编码

采用演化硬件技术自动设计数字电路，先要将电路表示成便于演化算法设计的编码方式。该编码方式依据硬件平台Virtex－II系列FPGA的逻辑单元结构（见图1）构建的。

图1 可编程逻辑门阵列结构

经过下面的建模过程，体现基于FPGA电路设计自动化问题的可演化性，只与逻辑单元功能和其互联关系相关。将已知的电路输入作为逻辑单元矩阵的输入资源，对于一个N输入的逻辑电路，就有N个输入资源，每一个单元都有自己的输出。这样矩阵单元可以成为其他单元的输入，或者整个电路的输出。对所有资源进行编号，以便表示整个电路单元的互连关系，作如下三元组模式的编码：（Ai，Bi，Ci）。Ai表示将资源编号 Ai的输出连接到逻辑单元的的第一个输入，Bi表示将资源编号Bi的输出连接到逻辑单元的第二个输入，Ci用于标识逻辑单元的功能，Ci具体数字与其对应逻辑功能关系，见表1。

表1 染色体中的负数对应的逻辑门功能

引入连接度的方法来动态控制所有逻辑单元的输入，实现动态的控制搜索空间。连接度是指：在矩阵单元Mmn（m表示矩阵的行数，n表示矩阵的列数）中，若某个单元Cij（表示该单元在矩阵的第i行、第j列）的输入信号能与前k列单元的输出信号相连，即在第j－k列——第j－1列位置上所有单元的输出信号都能为该单元的输入信号，则称该单元Cij的连接度D为K.假设n为矩阵单元的总列数，nr和nc分别是矩阵的单元行数和列数。ni代表目标电路系统输入数目，若第c列某单元的连接度为k；其中c∈［1，n］，定义 V（c）为整数v的集合，所以：

后面的列其连接度呈递增趋势，这样通过控制k的值能够缩小电路的搜索空间，提高演化效率。

扩展约束编码规则即可避免染色体在个体初始化或变异时单元间连接形成回路，同时可动态调整单元的连接度，使得算法在运行时能动态调节单元的搜索空间，从而在某种程度上提高演化效率。

2 选择策略

2.1 选择输出端逻辑单元

采用贪婪策略来确定电路的输出单元，即根据给定电路功能的真值表，对于每一种电路输入组合，将各矩阵单元输出值与真值表各输出值进行比较，若匹配则加1，这样可构造出各矩阵单元对应各输出端的匹配度；再针对每个输出，我们分别选取匹配度最大的单元，将该单元作为该电路对应的输出端。与盲目随机选取输出单元相比，贪婪策略能防止同一染色体因输出单元选取的不同，使得它们的适应度评估值存在很大差异的缺陷，同时能更好的将有效个体电路保留下来，从而提高了演化效率。

2.2 确定每个逻辑单元的变异概率

首先将每个逻辑单元赋一个初始值P＿MUTATION。对于输出端的变异概率，若某个输出端已经正确输出，则变异概率为0，否则输出端概率为0.5＊P＿MUTATION。若相关联逻辑单元的变异概率比该输出单元小，则不变；否则，将输出单元的变异概率赋给该逻辑单元。

3 遗传操作

3.1 交叉操作

采用子电路交叉法。子电路交叉法是基于多目标技术，若将数字电路的每个输出端信号单独作为一个目标，一个多输出数字电路的设计即为一个带约束的多个目标优化问题。由于一个多输出组合逻辑电路可分解为多个输出端信号子电路，因此，一个多输出组合逻辑电路可由所有单输出端信号子电路构成。该文基于多目标与局部优化技术，提出子电路杂交策略。新个体电路的每个输出端子电路产生规则为：根据两父体电路中同一输出端信号的功能评价值，选取较优的子电路作为新个体电路对应输出端信号子电路，然后将新产生的所有输出端信号子电路组合形成新个体电路。若某逻辑单元产生冲突，则直接用后续输出单元的相关逻辑单元赋值。

3.2 变异操作

采用自适应变异。在三元组的三个位置中随机产生一个变异位置和该位置的变异概率，若该变异概率小于该逻辑单元的初始变异概率，则变异。变异的原则是：随机产生该位置满足条件的值，直到不与原来的值相等。

3.3 个体保留策略

采用跨世代精英机制。上一代种群与通过交叉变异操作产生的新种群混合起来，从中按一定概率选择较优的个体。具体操作过程如下：

第一步：将规模为N的当前种群P1通过交叉变异操作产生下一代子种群P2。

第二步：将当前种群P1和下一代子种群P2混合形成临时种群。

第三步：对临时种群按适应度值降序排序后，保留最优的N个个体形成新一代种群P1。

跨世代精英机制在健壮性和遗传多样性保持以及排序方法上都有着一定的特质，即使当交叉变异操作产生较劣个体偏多时，由于原种群大多数个体残留，不会引起个体的评价值降低；由于大种群操作，可以更好地保持种群演化过程中的遗传多样性，最后它很好的克服了比列适应度计算的尺度问题。

4 实验与分析

采用改进的遗传算法进行一位加法器的优化设计，其实验运行参数见表2（使用“与”门、“或”门和“非”门）。

表2 算法运行参数

在以上算法参数设置下，独立运行算法5次，实验结果统计如表3。

表3 5次实验结果统计表

对表3实验结果统计表进行分析，得出如表4实验结果分析表。

表4 实验结果分析表

实验结果分析表明，进行5次实验，设计最优电路的逻辑门数为9，设计有效电路的频率达到100%，设计电路的平均逻辑门数为5。实验数据说明电路演化优化设计能较好地用于一位加法器的演化优化设计。

5 结 语

将演化算法引入到硬件设计技术中，已经成为一门新兴技术，引起许多学者的广泛关注与深入研究。本文首先在人工设计电路的基础上，引入基于硬件设计的演化算法。采用的是矩阵单元三元组整数编码，编码规则为扩展约束编码规则，采用贪婪策略来确定电路的输出单元，在产生新一代时，采用轮盘赌算法进行随机选择，交叉采用子电路交叉法，变异采用自适应变异，最后的最优个体保留机制采用跨世代精英机制。实验结果表明，演化算法在电路优化设计上有效实用，在采用适当的算法的基础上，能获得比较优化的电路，这些电路可作为基本模块用于设计更复杂的硬件系统，这将会在大型硬件系统设计中占据重要的地位。

1 .F.Miller，P.Thomson，and T.Fogarty.Designing Electronic Circuits Using Evolutionary Algorithms.Arithmetic Circuits：A Case Study，chapter 6，in Genetic Algorithms and Evolution Stategies in Engineering and Computer Science：Recent Advancements and Industrial Applications.Wiley Press，1997（November）：36－60.

2 Thompson A.Hardware Evolution：Automatic design of electronic circuits in reconfigurable hardware by artificial evolution.Doctoral thesis，University of Sussex，UK，1996.

3 Coello C Carlos A.An Empirical Study of Evolutionary Techniques for Multiobjective Optimization in Engineering Design，PhD thesis，Tulane University，New orleans，1996.

4 Kalganova T.Evolvable Hardware Design for Combinational Logic Circuits.PhD thesis，Napier University，Edinburgh，UK，2000.

5 Zebulum R S.Synthesis of Electronic Circuits Through Artificial Evolutionary Systems.PhD Thesis，Catholic University of Rio，Portuguese，1998.