支路杂交操作：如何优化染色体组合

电路演化过程中，种群可能出现这样的两种个体，它们各支路的匹配程度各不相同，可能染色体A 支路1匹配程度很高，但支路2匹配程度很低；而染色体B 支路2匹配程度很高，但支路1匹配程度较低。如果可以将这两条染色体两支路中取其较优的支路组合在一起，就完成了支路杂交操作。

事实上，支路杂交操作与上文的子电路杂交操作是类似的，只不过支路杂交不需要随机选择杂交点，杂交点即为电路输出结点。

一般情况下，对于这样一条染色体（图5-11），结点3和结点7是待交换点，交换结点的输出指向即可实现交换，如图5-12所示。

但是对于如图5-13所示的交换点，就不能用上述的方法来交换了。因为结点4的输出指向不止一个，因此，交换操作同样应该面向连接。这种情况下，可以看作交换结点6的第2连接与结点8的第2连接。

图5-11　交换前染色体

图5-12　交换后染色体

这里出现了一个新的问题：如何保证结点序？ 实际染色体编码中，每个结点（单元）都是有序的，如图5-14交换后，原来在前的结点6居然接受了来自结点7的输出，这是不允许的。

图5-13　多输出交换结点染色体示例

图5-14　多输出交换点交换示例

其实这个问题很好解决：假设待交换的两个结点编号为A、B（A＜B），A 的输出连接中，待交换的连接指向的结点编号为C，如果C＞B，则直接满足结点序；如果C＜B，则交换B 与C 单元内容，同时扫描染色体，将所有三元组中的连接，B 与C 调换位置；如果C=B，则不进行任何操作，或者更换C 单元的另一连接进行交换。

同样以三元组编码染色体进行示例。

交换前染色体：

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)

整个交换过程如下。(www.xing528.com)

（1）按照图5-15进行交换，交换后的染色体为：

图5-15　最终交换后的染色体示例

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

（2）由于A=4，B=7，C=6＜B，需要交换6号与7号三元组的内容，交换后的染色体为：

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

（3）扫描染色体三元组，交换编号6与7，交换后的染色体为：

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

画出该染色体的连线图如图5-15所示。