486 智能系统学报 第4卷 虑函数f代，名1,2,3）=0出+名2+名，其中{x0, 根据上面的分析，可以通过计算适应度函数的 1,x2,x3}∈{0,1,2}4，显见，f的联结集合为0， 傅里叶系数来确定变量之间的联结关系.但是值得 {xo}、{1}、{x2、{x3、{0,x}、{x1,x2}计算得到 注意的是，按照式(1)来计算傅里叶系数。需要遍 它的傅里叶系数如表1所示，表中未列出的掩码 历整个定义域空间，显然这个计算工作量很大.下面 串的0均等于0.~非0的掩码串反映了该问题的 将在上述分析的基础上，进一步介绍有效的联结关 联结结构.例如，01≠0，则说明0011所标识的变 系检测算法 量xo和x1之间存在联结关系；⊙mo≠0，则说明 需要注意的是，在一般离散域中，一个联结集合 0210所对应的变量集{x1,x2{是联结集合 可能对应多个不同的掩码串（其傅里叶系数非0）. 表1傅里叶系数0，与联结结构的关系 例如在表1中，联结集合{1，x2}对应4个掩码串 Table 1 The relationship between Fourier Coefficients 0110、0120、0210、0220.只要其中有一个掩码串的傅 and the linkage structure 里叶系数非0，就可以说明x1和x2存在联结关系 掩码串 傅里叶系数 联结集合 在空间Z中，一个k阶联结集合至少对应一个、至 0000 多对应(M-1)个傅里叶系数非0的掩码串.这与 0001 -0.5000+0.2887i 二值编码的情况是不同的，二值编码情况的联结块 0002 -0.5000-0.2887i 0010 -1.0000+0.57741 与掩码串是一一对应的。 {x1 0020 -1.0000+0.5774i 3.2联结关系检测的确定性算法 0011 0.1667-0.28871 假定问题是k阶限定的，也即最多有k个变量 0012 0.3333 是相互关联的，在这种假设下，根据前面的结论，显 0021 0.3333 然当j‖>k时，傅里叶系数①=0.其中‖j‖表示 0022 0.1667+0.2887i 字符串j中非0位置的个数，例如j=01020021, 0100 -0.5000+0.2887i {2 Ij‖=4. 0200 -0.5000-0.2887i 0110 0.1667-0.2887i 对于给定函数f(x):Z→R,若k≤L,由于 0120 0.3333 川j‖>k时，傅里叶系数=0，则可大大诚少计算 {出1，南} 0210 0.3333 o的工作量. 0220 0.1667+0.2887i 根据前面计算ω的一般公式及这里问题k阶 1000 -0.5000+0.2887i x3 限定的假设，可以推得4： 2000 -0.5000-0.28871 1 ,‖i‖=k; ∑f代x)n(x) Is)I fx)(x)- 人 xes(i) ∑e0"（(x)() J2&>i ,‖i‖<k: (2) ∑(x)(x) xES(i ,‖i>k. 式中：S()是i的模板集，它是将i的非0位置变为通 o:的工作量.然后根据式(2)中的第2个式子计算‖i 配符“*”后的字符串集合.例如，若i=01020∈Z,则 ‖=k-1时的0：，这时式中需要的f(x)和0都是前 i的模板集为S(i)=0*0*0,其中*遍历0、1、2，即 面已经计算过的，无需重新计算，然后依次计算 S(i)=0*0*0={00000,00010,00020,01000,01010, ‖i‖=k-1,k-2,…,0时w.这样就将所有傅里叶 01020,02000,02010,02020.首先根据式(2)中的第1 系数ω：计算出来了. 个式子计算‖i‖=k时的，它需要遍历i的模板集 在式(2)的计算中，如果注意到：=o:的事实， S(),而在式(1)的一般计算公式中，计算o,需要遍 还可以进一步提高计算效率其中i是i的逆元，它 满足④i=0. 历整个定义域空间Z.当k≤L时，将大大减小计算