484 智能系统学报 第4卷 1 遗传算法与联结关系 (极大联结块)，该问题的阶数为2，并称问题是二阶 限定的.注意这里{x3,2}和{x2,x1}存在交叠， 考虑2个变量x和y,如果x的赋值对函数值f 2二值编码的联结关系检测 的影响与y的赋值有关系，则称x和y之间存在联 结关系.例如(x,y)=x+y,x和y之间无联结关 设每一个基因位表示一个变量，并设每个变量 系，这时x和y可分别进行优化；若(x,y）=y,则 均为离散取值.本节首先考虑离散取值仅为0或1 x和y之间存在联结关系，这时必须同时考虑x和y 的二值取值的简单情况，然后再推广到多值取值的 2个变量进行优化， 一般情况 联结关系的复杂程度直接影响问题的求解难 对于给定二进制编码的黑箱问题，关键是如何 度.在遗传算法中，传统的交叉操作并没有考虑联结 检测哪些变量之间存在联结关系.下面介绍2种检 关系，因而使性能受到影响.如果在遗传算法编码 测算法， 中，具有联结关系的变量基因位置比较靠近，称为紧 2.1近似检测算法 致编码，那么遗传算法就很容易求得问题的最优解. 考虑一个待优化的函数f(,,…,1-),每 如果具有联结关系的变量基因位置很分散，称为松 个变量的取值为0或1的二值编码.设二进制字符 散编码，那么交叉操作则很容易造成基因流失和早 串x=x0出1…x-1,选择2个变量：和，通过扰动2 熟收敛.图1表示了单点交叉与基因位置的关系.由 个变量的赋值来观测函数f的变化，进而判断：和 图1可以看出：当紧致编码时，交叉操作后很容易保 x是否关联.设 持原来的基因组特性；当松散编码时，交叉操作将以 Af=f…x…）-f……）, 很大的概率破坏掉原来的基因组特性，紧致编码使 Af=f……）-f…x…）, 得低阶的模式块容易通过交叉操作构成高阶的模式 Af=f……*…）-fx…光…） 块，而松散编码使得交叉操作很容易破坏掉有用的 式中：x=1-,=1- 模式块[2,6」 如果Af=△f+△f,即x:和：对f的影响是线 性叠加关系，则认为x:和x不存在联结关系.如果 A B AT 交叉 △f≠△f+A,则认为x:和x存在联结关系.该算 b a8 法的计算复杂度为O(L). 该算法的主要特点是比较直观，容易理解，它每 次对2个变量进行联结检测，对于联结关系无交叠 4B 交叉 或交叠简单的问题很有效.它的缺点是不精确，尤其 a□ a6 是对于联结关系有交叠的复杂情况很难处理.例如 图2(a)所示的联结关系，采用上述近似检测算法可 图1编码方式对交叉操作的影响 能得出如图2(b)所示的错误结果，其中虚线所示为 Fig.1 The influence of coding to crossover operator 误判的联结关系。 遗传算法的编码方式对算法的性能有着很重要 的影响.对于一些简单问题，遗传算法可以搜索到较 好的解，但对于一些复杂问题，必须利用问题结构的 先验知识才能有效地对问题求解」 一般情况下，具有联结关系的变量越多，问题的 最优解越难找到.具有联结关系的变量集合称作联结 (a)真实的联结关系 (b)误判的联结关系 集合或联结块对于联结块S,当且仅当不存在变量 图2真实的联结关系和误判的联结关系 x:S使SU{x:}仍是联结块时，称S为最大联结块 Fig.2 True linkage and false linkage (denoted by dashed line) (极大联结块).如果问题至多有飞个变量相互关联，k 2.2联结关系检测算法 称作问题的阶数，并称问题的联结集合是k阶限定 针对上述近似检测算法所存在的不足，Hecken- 的.例如，若f(,2,1,0)=32+21+x0+名1，则 dom等人提出了以沃尔什变换为工具的二进制编码 {x3,2,{x2,x1},{x0}是联结块，且都是最大联结块 联结关系检测算法？).该检测算法具有严格的理