染色体编码及统一资源编号方法

CGP编码模型是Miller J F提出的[13]，假设某次数字电路优化设计中基本门电路最多有3个输入端、1个输出端，编码和其对应的端口连接如图5-1所示。

图5-1　CGP编码模型

这是一个6输入、3输出电路，4×4矩阵模型，每一个矩阵单元都是一个3输入、1输出的基本门，矩形中间的数字表示其功能编号：假设共有3种基本门，可以编号为0、1、2，则功能编号表示特定的门。矩形左边邻接的3条平行线表示门的3个输入端，同理右边的邻接线表示输出端。每个输入端都可以连接来自总电路输入端或门电路输出端。将所有可能被其他输入端连接的总电路输入端或门电路输出端进行统一资源编号：如图5-1，6个输入端被编号为0～5，4×4矩阵依次被编号为6～17。门电路左边输入端上的数字是统一的资源编号，即表示其连接该编号的总电路输入端或门电路输出端。最右边的3条平行线代表总电路的输出端，线上的数字即代表由哪一个门电路输出。

该连线图对应的基因型在其上方，每个基因都是一个四元组（A、B、C、D），A 表示功能，B、C、D 表示输入连接，最后的3个数字即表示电路的输出端编号。

从图5-1可以看出，只要满足特定的约定下（四元组第一个数字属于门的功能编号，其他数字都属于统一资源编号），任意一个基因型都可以有对应的连线图，而任意一个连线图均有其对应的基因型，它们是一一对应的关系。

（1）三元组编码。如果将二路选择器当作基本门，那么在基本门中，除了二路选择器是三输入门电路外，其他都是二输入门电路。我们可以采用三元组（A、B、C）代替原来的四元组来表示一个门电路。其中，A 表示第一个输入连接编号，B 表示第二个输入连接编号，C ＞0则表示二路选择器选择信号连接编号，C ＜0则表示门电路功能编号。(www.xing528.com)

（2）阵列变换。CGP模型之所以采用阵列形式布置门电路，是为了防止产生反馈电路，阵列中门单元需要满足互联约束，即后一列单元的输入只能来自前面单元的输出或总电路输入资源。但阵列规模的设定是自由多变的，如何设定阵列规模也是需要考虑的问题。实验表明，采用1×N 阵列，演化效率更高（需要实验论证），因为采用M×N 阵列，染色体资源浪费过大，而且随着染色体的增长，搜索空间急剧增大，使得演化更难收敛。

（3）动态选择输出端。CGP模型输出端一般是固定的，在阵列的最右端，可固定输出端演化算法的收敛性能较低，所以就有了动态选择输出端方法：

我们在对个体进行评估的过程中，需要对每个单元的输出值进行计算，在得到单元的输出值后，我们就可以在此时将单元输出值与真值表中的每个输出列进行比对，在所有的电路单元输出值都计算完毕后，我们选取和输出Oi 匹配程度最高的单元输出作为Oi 的输出，这样我们可以保证个体中每个输出与真值表匹配程度的最大化，从而更加准确地反映个体的优劣情况。

假设该编码方案下一个电路有N 个输出端，依次为：O1，O2，…，ON（Oi 表示整个电路输出的资源编号），并设该电路有M 个输入端，染色体三元组数为CLB_SIZE，我们构建一个二维整型数组S[CLB_SIZE+1][N]。则对于i∈[0，CLB_SIZE），i∈Z，j∈[0，N），j∈Z，S[i][j]的值即可以表示编号为M+i单元与Oj 输出端相对于真值表的匹配程度。S[CLB_SIZE][j]，j∈[0，N），j∈Z，该整型数组中[j]可以存储与Oj 匹配程度最高的单元编号，即当前最佳输出端。