采用面向连接的杂交方法优化交叉操作

一直以来，在数字电路优化设计中，由于电路的网络复杂性，使得一般的杂交方法难以实施，面向单元的杂交方法是不可行的，举例如下。

图5-3和图5-4中，C1、C2 为选择的交叉结点，交叉后染色体1的结点B1 失去了一个连接，染色体2的结点D2、E2 连接同时改变。因此，采用面向单元（结点）的杂交方法是不可行的。由此，本书提出采用面向连接的杂交方法。

图5-3　染色体1

图5-4　染色体2

图5-5和图5-6中，染色体1结点D1 的一个连接是C1 支路，染色体2中两个结点D2、E2 共享一个连接C2 支路。则交叉时，染色体1结点D1 的连接改变，结点B1 的连接不变；染色体2结点D2、E2 中，任选一个结点使其连接改变，或者两个均改变。

图5-5　染色体1

图5-6　染色体2

图5-7和图5-8即是染色体1结点D1 的第2连接与染色体2结点D2 的第2连接交叉后的结果。具体实现如图5-9和图5-10所示。

图5-7　交叉后的染色体1

图5-8　交叉后的染色体2

图5-9　编号后的染色体1

图5-10　编号后的染色体2

将染色体1、2中各结点编号（图5-9和5-10），编码如下。

染色体1：

1(E,E,R)2(E,E,R)3(E,E,R)4(1,2,R)5(E,E,R)6(3,4,R)7(4,5,R)8(6,7,R)

染色体2：

1(E,E,R)2(E,E,R)3(1,2,R)4(E,E,R)5(4,3,R)6(E,E,R)7(E,5,R)8(5,6,R)9(7,8,R)

其中，E表示任意输入，R 表示任意功能。

则交叉操作实际上针对染色体1 的8号单元的第2连接和染色体2的7号单元第2连接。

具体操作步骤如下。(www.xing528.com)

（1）扫描染色体1，获得需交叉的连接的关联单元为（1，2，4，5，7），共有5个关联单元；

（2）扫描染色体2，获得需交叉的连接的关联单元为（1，2，3，4，5），共有5个关联单元；

（3）染色体1全体编号增加5，将染色体2（1，2，3，4，5）单元依次加入染色体的头部；

（4）染色体1全体三元组连接编号增加5，除了交叉连接（即8号单元的第2连接7），交叉连接编号改为5；

（5）染色体2全体编号增加5，将染色体1（1，2，4，5，7）单元依次加入染色体的头部；

（6）染色体2全体三元组连接编号增加5，除了交叉连接（即7号单元第2连接5），交叉连接编号改为5（这里由于特殊而编号没有改变）。

通过上述6步操作，即完成了染色体的连接交叉操作。交叉后的染色体编码如下。

染色体1：

1(E,E,R)2(E,E,R)3(1,2,R)4(E,E,R)5(4,3,R)6(E,E,R)7(E,E,R)8(E,E,R)9(6,7,R)10(E,E,R)11(8,9,R)12(9,10,R)13(11,5,R)

染色体2：

1(E,E,R)2(E,E,R)3(1,2,R)4(E,E,R)5(3,4,R)6(E,E,R)7(E,E,R)8(6,7,R)9(E,E,R)10(9,8,R)11(E,E,R)12(E,5,R)13(10,11,R)14(12,13,R)

染色体1交叉后，原来的7号单元（现在的12号单元）变成了无效单元，但是对整体没有影响，因为每一代都要经过有效单元检查，7号单元自然会被过滤掉。