多目标问题中的适应度评估方法

数字电路演化的目标电路一般有多个目标。其中，最重要的目标是门的功能要完全正确；其次，整个电路延时最小；最后，整个电路功耗最小。

由于这是个有偏好的多目标问题，故采用加权评估值的方法即可以实现。

（1）门的功能按照与真值表的匹配程度计算：假设目标电路有M 个输入端，N 个输出端（O1，O2，…，ON），染色体对应电路输出端的适应度值为（F1，F2，…，FN），在给予真值表中某一行输入值时，Oi 输出值与真值表对应行列值相同，则Fi 增加1。如果Fi=2M，则说明该输出端对应支路是完全正确的，当每条支路都完全正确时，整个电路自然完全正确。门功能的适应度函数最终确定为：

（2）电路延时的计算方法如下：延时的真实计算不仅仅与连接的门电路有关，而且还与电路的负载有关，所以真实的延时是不容易计算的，它需要考虑电路的拓扑结构。这里采用一种简单算法，折中求取延时。

对于一条具体的电路，可能有多个输出端，从输入端到输出端可能存在许多不同的路径，每条路径的延时一般都不会相等，我们分别计算每一条路径的延时，将其中最大值作为整个电路的延时，如图5-16中的一位全加器，从A 输入端或B输入端出发，经过异或、与门，到达或门至C0 这条路的延时最大，这条路径延时的计算方法如下：

T=Tinstrinsic（异或门）+Tinstrinsic（与门）+Tinstrinsic（或门）

第一级异或门：t1=0.137 3（ns）

第二级与门：t2=0.080 1（ns）

第三级或门：t3=0.061 7（ns）

总的延时：t=t1+t2+t3=0.279 1（ns）

这里转换一下目标，改为计算整个电路的最大层数：假设目标电路有M 个输入端，染色体三元组数量为CLB_SIZE，则定义一个长度为CLB_SIZE+M 的整型数组Length[CLB_SIZE+M]，并赋初值为0，依次扫描染色体的每一个三元组Ui（Ai，Bi，Ci）则有：

式中，当Ci ＜0时，Length Ci=0；Ci≥0时，Length Ci=Length[Ci]。(www.xing528.com)

按照前面所述动态选择输出端以后，整个电路的层数L=max{Length[Oi]}。

图5-16　一位全加器

（3）电路功耗的计算方法最为简单，将电路中所有用到的逻辑门各自的功耗相累加即可。同样，电路门数越少，一般整个电路的功耗就越小，因此，只需要统计有效门的个数。当某个门单元在后面的三元组中没有被用到，则该门单元可以视为是无效的。可先统计每个单元的被连接次数，从后向前，当某个单元没有被连接时，则将其设为无效，接着该单元连接的单元连接次数减少1，最终扫描完染色体时，没有被设为无效的单元即为有效门。各逻辑门功耗和延时如表5-1所示。

表5-1　逻辑门功耗和延时表

注：功耗单位μW/MHz，延时单位ns。

（4）最终适应度可以采用加权的方法。

式中，ω1 ＞ω2，体现延时比功耗更加重要。