第6期 周树德，等：遗传算法中的联结关系 ·487… 可以证明4)，该算法所需要的适应值函数计算 对于任意函数f:{0,1,2}3→R,如果w101是极大非 次数的上限为】 - 零傅里叶系数，那么掩码串01201的任何子串，都必 下面通过一个具体 然存在背景串c,使得它的探针值非零.例如一定存 例子来说明该算法的计算工作量.设问题为 在背景串c1使得二阶子串01200的探针值P(f, f代x）=g(x0,x1,x2)+g(x2,3,4)+ 01200,c1)≠0，一定存在背景串c2使得一阶子串 g(4,x5,x6）+g(x1,7,g). 00001的探针值P(f,00001,c2)≠0. r100, :=0:,=4,xk=0k; 如果o是极大 00☒ 式中：g(x,x,x)= 非零傅里叶系数 ixk 其他， 显然该问题的联结集合为{，x1,x2}、{2,3,x4}, o题00 020圈 Do网o {34,5,x6}、{x6,x7,x8}、 o 000 o0o0o000题 对于该例，若采用前面的一般计算公式，计算傅 哪么一定存在C使得以上掩码串的探针值0 里叶系数需要计算3°=19683次函数评价，而利用 图4探针性质2的直观解释 确定性算法仅需计算1512次函数评价.显然利用该 Fig.4 Explanation of the property 2 of probe operator 算法可大大减少计算工作量. 性质3任意给定函数f(x):Z→R,如果掩模 3.3联结关系检测的随机性算法 串m∈Zk所标识的变量之间存在联结关系，那么当 确定性算法具有严格的理论基础，并给出了最 且仅当存在c∈B(m)使得P(f,m,c)≠0. 坏情况下的复杂度估计，而且可以准确地给出联结 根据性质3，需要遍历所有c∈B(m)来计算 关系的检测结果，这些是该算法的优点，它的不足是 P(f,m,c),才能判断是否存在c∈B(m)使得P(f, 需要先验知识k,当k较大时计算量仍然较大 m,c)≠0.这个计算工作量是很大的.实际计算时， 为了提高算法的效率，下面将给出一种随机算 随机选择背景串c∈B(m),计算它的探针值P(∫， 法.该算法的基本思想是，基于傅里叶分析定义“探 m,c),如果探针值P(∫，m,c)≠0，则表明存在c∈ 针”算子，该探针的值反映了联结关系，进而给出一 B(m)使得P(f,m,c)≠0；否则继续随机选择背景 种自低价到高价的检测算法.该随机算法比确定算 串c来计算探针值，至多进行N,次，如果W。次的探 法效率更高，且不需要先验知识k 针值都为0，则认为不存在c使得该掩码串的探针 定义离散域探针为 值非零.这里N,是需要设定的参数，它表示对掩码 1 PUm,e）=￡"(0i⊕e. 串m进行随机探测的次数.显然V,越大，成功检测 的概率便越大.性质4可以帮助估计这个概率 式中：m是掩模串，S(m)是m的模板集，c∈B(m). 性质4设f(x):Z→R是k阶限定问题，m∈ B(m)是m的背景集，它是将m的非零位置变为O ZM且‖m‖=j,Jj≤k,如果c∈B(m)是随机选择的 及将m的0位置变为通配符“*”后的字符串集合 背景串，那么P(f,m,c)≠0的概率至少是M- 如m=01201,则m的模板集S(m)=0**0*,m 考虑函数f八0，x1,x2)=g(0,1)+g2(x2),其 的背景集B(m)=*00*0. 可以证明4们，探针P(f,m,c)具有如下性质： 中(x0,x1,2)∈{0,1,2}3，有2个极大联结集合 性质1任意给定函数f(x):Z→R,如果®m {x,x1和{x2},该函数傅里叶系数非零的有：①m、 是它的一个极大非零傅里叶系数，那么对任意的背 D10、0200oi0、D0、00D、0o1、d2,其他的傅里 叶系数都等于0.如图5所示，按照自低阶到高阶的 景串c∈B(a),均有P(f,m,c)=①m 步骤，首先检测空掩码串000，得到非零的探针值。 性质2任意给定函数f(x):ZM→R,如果®m 然后检测1阶掩码串，以001为例进行说明：因为 是一个极大非零傅里叶系数，那么对于任何m的子 001所有子串（此情况下只有一个0阶子串000）均 串a(m2a)都存在背景串c∈B(a)使得 有不为0的探针值，所以需要计算001的探针值，计 P(f,m,c）≠0. 算后得到非零的探针值.当所有1阶掩码串都被检 下面通过一个例子来说明性质2.如图4所示