在许多工业应用和科学研究中，须要进行大量试验来改进产品．由于一次试验的代价有时比较昂贵，因此要求试验方案具有较好的均匀性和覆盖性，以此达到模拟整个试验区域的目的．经典的试验设计方法包括正交试验设计[1-3]、拉丁方试验设计[4]、因子设计[5]和均匀试验设计[6]等．对于某些复杂的实际问题，试验变量之间往往存在众多约束条件，目前解决约束条件下的试验设计方法大致可分为三类：传统均匀设计方法，基于数论的均匀设计方法，基于启发式搜索的均匀设计方法．针对复杂约束区域下的均匀试验设计问题，由于传统方法和基于数论的方法在解决强约束时较为困难，因此目前主要采取基于启发式搜索的方法．文献[7]提出一种采用中心复合偏差(CCD)[8]作为目标函数的离散PSO的均匀试验设计算法．文献[9]在文献[7]的基础上考虑了非碰撞性，采用种群最小距离和投影距离加权作为新的度量标准来进行优化．文献[10]提出一种两阶段差分进化算法(ToPDE)，但该算法主要采用差分算法生成子代，对种群的均匀性提升不足．本研究提出一种基于自适应邻域搜索的约束区域均匀试验设计算法，简称邻域搜索均匀设计(NSUD)．NSUD采用两阶段优化的策略：第一阶段采用基于聚类差分进化的方法，快速生成满足试验方案数量的可行解；第二阶段采用自适应邻域搜索策略来生成子代，并采用局部更新和全局更新相结合的混合策略来更新种群，提升种群的均匀性．1 约束区域均匀试验设计问题约束区域均匀试验设计的目的是在可行域内找到一个具有良好均匀性的试验点集．基于启发式搜索的均匀试验设计方法以最大化均匀性为目标函数，将均匀试验设计问题转化为一个单目标带约束优化问题，即max  f(X);s.t.  gix≤0    (j=1,2,…,lg);hix=0    (j=lg,lg+1,…,lh);x∈S;X={x1,x2,…,xN}, (1)式中：g(x)为不等式约束函数；h(x)为等式约束函数；f(X)为解集的均匀性函数．假定每个点的约束违反程度G(x)可表示为G(x)=∑j=1lhGj(x);Gjx=max0,gix(1≤j≤lg),max0,|hix-δ|(1≤j≤lh), (2)式中δ为等式约束的正容忍值．则式(1)中的等式约束和不等式约束可以进行统一表述：max  f(X);s.t.  G(x)=0;x∈S;X={x1,x2,…,xN}.2 NSUD算法NSUD算法分为可行解生成阶段和均匀性提升阶段．可行解生成阶段主要生成一定数量并具有多样性的可行解，作为均匀性提升阶段的初始种群；均匀性提升阶段主要提升种群的均匀性，得到具有良好均匀性的解集，作为算法最终输出．2.1　可行解生成阶段在可行解生成阶段，沿用ToPDE算法中提出的聚类DE算法，保证生成一定数量且具有优良多样性的可行解集．聚类DE算法每一轮迭代将种群聚类为多个子种群，在各个子种群内采用差分进化算子生成子代并根据约束违反程度进行选择，然后将所有子种群合并为下一代种群．当每个子种群都有一定数量的可行解时，可行解生成阶段结束．2.2　均匀性提升阶段种群的最小距离Mp越大表明其均匀性越好，有Mp=mini=1,2,…,Nmi，式中：m为个体到其他个体距离的最小值；i为个体数．本研究提出一种自适应邻域搜索策略，通过优化每个个体的m来达到优化Mp的目的．每一代都对种群中的每个个体Pi进行邻域搜索得到候选解Qi，并根据Pi和Qi到种群其他个体的最小距离来选择对提升均匀性帮助更大的个体．NSUD算法均匀性提升阶段流程图如图1所示．在经过C次迭代后，如Mp未明显提高，则算法终止．10.13245/j.hust.220518.F001图1NSUD算法均匀性提升阶段流程图2.2.1　自适应计算搜索方向本研究提出一种反向搜索策略来确定搜索方向．设距离个体Pi最近的个体为Pc，趋近Pc的搜索方向为正向，远离Pc的搜索方向为反向．如采用正向搜索，则Pi与Pc的距离越来越近，均匀性降低，故为提升种群均匀性，应尽可能采取反向搜索．图2为一个二维的均匀设计示意图，图中：x1和x2分别为解空间的两个维度；A，B，C，D为当前种群个体；E和F分别为B点正向搜索和反向搜索生成的解．可以看到：F点对于种群均匀性提升帮助较大，而E点对于种群均匀性提升帮助较小．10.13245/j.hust.220518.F002图2二维均匀设计示意图设w为Pi指向Pc的拥挤方向向量，有w=Pc-Pi，(3)则Pi的搜索方向di为满足wdi≤0的任一单位向量．2.2.2　自适应计算搜索步长搜索步长在邻域搜索中起着至关重要的作用，直接影响算法结果．本研究设计了一种基于种群均匀性信息来计算搜索步长的自适应策略，自适应搜索步长si计算过程为si=maxj=1,2…,Nmj-mi(mim¯);mi-minj=1,2,…,Nmj(mi≥m¯), (4)式中m¯为种群中所有个体最小距离的平均值．为了避免个体的搜索步长过小导致群体过早收敛，个体的实际搜索步长si'取为si与一个预定的较小值(本研究中设为m¯与种群大小的比值)中的较大者，具体计算式为si'=max{si,m¯/N}．(5)2.2.3　候选解生成及约束处理候选解Qi通过父代个体Pi根据一定的搜索方向和步长生成，即Qi=Pi+sidi，(6)式中si为搜索步长．由于式(6)在搜索方向上存在较大随机性，因此无法保证生成的候选解均为可行解．当生成不可行解时，通常采取通过多次迭代不同搜索方向的策略来确保生成可行解．而对于等式约束问题和一些强约束问题，由于解空间的不规则性，上述策略很难奏效，因此本研究对搜索方向进行优化，以不同搜索方向更新得到的新个体的约束违反程度作为目标值，对其使用差分算法进行求解以获得一个合适的搜索方向，确保可行解的生成．候选解生成算法流程如算法1所示，其中：W为差分算法的初始种群；ND为种群大小；T 为循环次数．算法1 生成候选解输入 个体Pi，距离Pi最近的个体Pc，决策变量维度n输出 个体Pi的候选解Qi步骤1 根据式(3)计算决策拥挤方向向量w，根据式(4)和式(5)计算搜索步长si'，设t=0，初始化差分算法初始种群W；步骤2 对标准正态分布进行n次采样获得向量di，并将di归一化为单位向量，计算di与w内积u；步骤3 根据式(6)计算候选解Qi；步骤4 若Qi为可行解且u≤0，则转步骤7，若Qi为可行解且u0，则t++转步骤5，若Qi为不可行解，则将di加入W，转步骤5；步骤5 若tT或W的元素数量少于ND，则转步骤2，若tT，则转步骤7，若W的元素数量等于ND，则转步骤6；步骤6 以W为初始种群进行差分算法，根据差分算法输出的方向重新计算候选解Qi；步骤7 输出Qi．2.2.4　种群更新由于ToPDE仅采用全局更新策略来更新种群，导致某些子代候选解当具有较大的m但无法提升Mp时被舍弃，因此本研究采取局部更新和全局更新的混合策略．当经过C/2代Mp都未明显提高，且Qi到种群中所有个体(包括Pi)的最小距离大于Mp时，采用全局更新策略来更新种群，即删去种群中最小距离最小的个体，将Qi加入种群，采用这种全局更新策略可以有效避免mi最小的个体一直得不到更新而导致算法终止，有助于提升算法均匀性．此外，本研究引入局部更新策略，即当某个个体的候选解的m值比该个体的m值更大时，选择候选解来替换该个体，进一步提高求解的均匀性．具体的种群更新流程如算法2所示，其中c为Mp未发生明显提高的代数．在更新的过程中，如果能找到一个合适的更新顺序，那么会大大提高更新的成功率，而找到合适的更新顺序比较困难，这里仅根据个体选择的顺序来进行更新．算法2 种群更新算法输入 当前种群P，候选解种群Q输出 更新后的种群P步骤1 计算每个个体的m值．步骤2 对于P中的每个个体Pi，计算Qi到种群除Pi外其他个体间的最小距离mi'；若cC/2，mi'Mp，且distance(Qi,Pi)Mp，则删去m最小的个体，将Qi加入种群，其中distance(∙)为距离度量函数，本研究中使用的是欧氏距离；若以上条件不满足，但是mi'Mp，则Qi替代Pi．步骤3 输出P．2.2.5　种群迭代时间复杂度分析一次种群迭代包括候选解生成和种群更新两个阶段．在候选解生成阶段，NSUD算法须计算每个个体的m值，时间复杂度为O(N2)；在种群更新阶段，NSUD算法须计算每个候选解到其他个体的最小距离，时间复杂度为O(N2)．ToPDE算法在候选解生成阶段没有额外计算，但在更新阶段须要计算N次Mp值，时间复杂度为O(N3)，因此NSUD算法种群迭代的时间复杂度相比ToPDE算法复杂度降低了一个数量级．3 实验结果及分析为验证NSUD算法的性能，选择8个试验设计的标准测试问题[11]进行对比实验，并记录了迭代过程之中Mp随生成的有效解数量的变化情况，以此观测NSUD对于Mp的优化效果，进一步验证NSUD算法中全局更新策略的有效性．3.1　评价指标及测试问题目前广泛应用的均匀性度量指标是最大最小距离MD[10]，即根据可行域内所有点到解集的最小距离的最大值来评价解集均匀性，具体计算为MD=maxy∈Sfmini=1,2,…,Ndistance(y,Pi)，式中Sf为可行域范围．若MD越小，则解集的均匀性越好．计算MD须要一个包含大量可行解的测试集来模拟可行域中的所有点，往往不够准确，因此本研究引入另一种评价指标均匀度MR [13]，其计算公式为：P¯=1N∑i=1NPi;R2=1/N;MR=MD/R,式中R2为解集决策变量的方差．R2越大，解集分布越为扩散，均匀性越好，因此MR值越小，解集的均匀性越好．表1列出了8个测试问题的具体属性，表中：V为问题的决策变量维度；Il为问题的线性不等式约束数量；In为问题的非线性不等式约束数量；Ie为问题的等式约束数量．10.13245/j.hust.220518.T001表1测试问题属性测试问题VIlInIeG045060G054203G0710350G082020G097040G108330G1890130G2170153.2　标准测试问题结果比较实验选取ToPDE和ToPDEEDA[12]算法作为对比算法．参考文献[10]，各算法的参数设置如下：第一阶段的种群大小Np设置为200；聚类子种群大小Ns设置为20；目的试验数量N设置为100；差分进化算子参数CR和F都设置为0.9．为保证公平性，所有算法的停机条件参数C均设置为100，每个测试问题独立运行50次．表2～3分别展示了上述算法在MD和MR两个指标上的对比结果，结果表明NSUD算法相比其他两个算法可以获得更好的均匀性．值得指出的是：NSUD算法在等式约束问题上(G05和G21)有明显优势，其原因为NSUD算法采用自适应邻域搜索的方式生成子代，比其他算法更容易找到有助于提升种群均匀性的个体．10.13245/j.hust.220518.T002表2MD标准测试问题实验结果统计表测试问题NSUDToPDEToPDEEDAG04均值0.443 00.471 40.465 6方差0.012 50.018 30.021 0G05均值0.005 40.168 90.137 8方差0.000 40.057 20.045 7G07均值0.404 10.406 10.385 2方差0.012 10.028 60.019 3G08均值0.008 80.009 70.009 5方差0.000 60.000 80.000 8G09均值0.399 20.408 40.398 3方差0.011 20.012 70.012 7G10均值0.317 50.315 70.295 7方差0.015 00.029 10.014 3G18均值0.063 00.072 10.067 5方差0.004 70.006 90.005 6G21均值0.079 90.117 4/方差0.005 60.089 3/注：“/”表示计算失败(下同)．10.13245/j.hust.220518.T003表3MR标准测试问题实验结果统计表测试问题NSUDToPDEToPDEEDAG04均值0.595 90.660 20.631 7方差0.017 70.028 10.029 5G05均值0.025 40.706 10.547 2方差0.001 90.340 60.201 0G07均值0.642 50.776 30.693 2方差0.016 20.062 40.037 0G08均值0.183 50.211 60.204 0方差0.015 60.018 80.018 6G09均值0.697 80.806 10.753 4方差0.022 50.026 60.024 5G10均值0.537 40.618 10.552 6方差0.024 20.059 70.027 8G18均值0.800 81.117 91.109 4方差0.068 10.113 00.087 5G21均值0.120 00.206 9/方差0.009 10.209 8/图3展示了NSUD算法和ToPDE算法在G04和G09的收敛过程，图中NF为生成可行解个数．可以发现：相比ToPDE算法，由于NSUD算法采用了自适应邻域搜索策略，因此在算法迭代后期可以更快找到有助于提升种群均匀性的个体进行更新，收敛效果更优．10.13245/j.hust.220518.F003图3迭代过程中Mp优化效果图4为NSUD算法和ToPDE算法在测试问题G05上求得最终解集的二维对比，由图4可知NSUD算法可以获得均匀性更好的解集．10.13245/j.hust.220518.F004图4G05问题上解集对比3.3　全局更新策略对算法的影响分析为了测试不同的更新策略对算法最终结果的影响，进一步对全局更新策略对算法的提升程度进行分析，记不包含全局更新策略的算法为NSUD-．表4和表5展示了NSUD-与NSUD在MD和MR两个指标上的比较结果．10.13245/j.hust.220518.T004表4MD全局更新策略实验结果统计表测试问题NSUDNSUD-G04均值0.443 00.449 9方差0.012 50.019 2G05均值0.005 40.017 2方差0.000 40.004 7G07均值0.404 10.407 8方差0.012 10.011 8G08均值0.008 80.008 9方差0.000 60.000 9G09均值0.399 20.399 2方差0.011 20.011 4G10均值0.317 50.321 1方差0.015 00.015 8G18均值0.063 00.063 1方差0.004 70.004 7G21均值0.079 90.104 9方差0.005 60.013 410.13245/j.hust.220518.T005表5MR全局更新策略实验结果统计表测试问题NSUDNSUD-G04均值0.595 90.608 7方差0.017 70.028 0G05均值0.025 40.070 5方差0.001 90.021 9G07均值0.642 50.656 2方差0.016 20.022 1G08均值0.183 50.185 9方差0.015 60.019 0G09均值0.697 80.703 9方差0.022 50.023 9G10均值0.537 40.544 2方差0.024 20.026 4G18均值0.800 80.8135方差0.068 10.0661G21均值0.120 00.143 1方差0.009 10.020 8从表4和表5可以看出：NSUD在测试问题G05和G21上取得了明显优于NSUD-的结果，表明引入全局更新策略可以更好提升算法求解性能．4 结语本研究在ToPDE算法的基础上，针对其第二阶段差分进化算子的随机性过强、在算法后期难以找到优良候选解的问题，提出一种基于自适应邻域搜索的均匀区域试验设计方法NSUD．NSUD对个体采用自适应邻域搜索策略产生候选解，能更有效找出有助于提升种群均匀性的后代个体．通过在8个标准测试问题的实验对比表明：相比ToPDE和ToPDEEDA，所提出的NSUD算法在解集质量和收敛速度上都能取得更好的结果．