基于动态区域划分的多种群进化算法

陈 昊，许春蕾，黎 明，张聪炫

1.南昌航空大学无损检测技术教育部重点实验室，南昌330063

2.南昌航空大学信息工程学院，南昌330063

进化算法现已应用于实际的复杂优化问题，而多种群策略表示子种群对解空间中不同区域采用不同的进化策略，并通过迁移等操作实现子种群间的信息交互，此类算法被称为多种群进化算法.近年来，多种群进化算法的研究主要包括以下三方面：

1）在进化的过程中，以个体之间的相关性、相似程度以及个体分布等为依据，采用聚类策略划分种群或搜索空间.文献[1]首先根据聚类算法将搜索区域划分成不同的等级，然后针对高等级区域加强搜索以逐步缩小搜索空间，这样不但提高了收敛速率而且降低了复杂度.文献[2]提出一种新的多种群遗传算法，即以一个新的相似性测量函数决定两个点是否属于同一个集群，从而将种群分为N个小集群.文献[3]提出一种基于多个子种群的参数自适应差分进化算法，通过一个循环实现子种群间的信息共享与交换，并借助上一级子种群的当前最优个体引导本种群的进化.

2）基于解空间拓扑结构的多种群进化算法先将整个解空间划分为多个子区域，再以区域内个体的适应度评价区域属性，且各区域中采用不同的进化策略.为增强粒子的全局搜索能力，文献[4]采用一种基于随机图论的邻居拓扑结构，通过构造均匀程度不同的拓扑结构来影响粒子群优化算法的性能.文献[5]研究了粒子间的信息交互与共享过程，分析了典型的静态邻居拓扑结构的图形特征对粒子群算法性能的影响，并通过实验证明了算法的稳定性较好，不过寻优速度较慢.文献[6]在进化过程中确定一种对偶知识，通过引入不同类型的知识来影响进化过程.

3）异构多种群策略根据常规方法在一个区间上同时生成多个子种群，而各个子种群可以采用不同的进化策略，但要确保此方法生成的子种群所在区间完全重合.文献[7]研究一种将多种群粒子群算法和遗传算法进行混合的进化策略，也就是将粒子群的群体分解为多个子种群，而各子种群可以利用不同的策略并行进化使粒子具有不同特性，以此提高种群的多样性.文献[8]将多种群策略引入文化算法使每个子种群在进化过程中单独运算，然后改变算法控制参数使各子种群并行寻优.文献[9]针对动态优化问题提出一种自适应多种群人工蜂群算法以便各子种群独立寻优，通过设计一种跨种群算子实现子种群间的信息交互.

除上述3 种子种群划分方法以外还有其他群划分方法，如各进化策略间的相互协作关系、迁移策略等.文献[10]依据每种差分进化模型的特点为子种群动态分配进化策略，从而使多种策略之间协同进化，并通过实验证明了该算法的性能提升幅度较大.文献[11]以并行差分进化策略优化种群聚类，增强了子种群间的通信迁移能力.文献[12]针对协同进化中各策略的贡献度差异，采用多种群合作的方法缩小算法的搜索空间，有利于求得全局最优解.

上述研究表明，在进化算法中采用多种群策略对提高算法的求解性能具有重要意义，这些探索为进化算法应用于求解复杂优化问题提供了新的思路和途径.然而，目前关于进化算法的多种群策略研究大致有以下缺陷：1）利用拓扑结构进行划分时既不能区分每个区间的重要程度，也无法体现子种群之间的差异性；2）基于异构的区域划分方法通常只能针对一个特定的空间进行操作；3）对子种群如何划分没有一个确定的标准，也无理论依据，不能保证划分后的区域比原有区域找到最优解的概率更大.鉴于此，本文提出一种基于动态区域划分的多种群进化算法，主要是将云模型与原问题结合以重新估计原问题，并对估计后的新问题进行解空间区域划分，不仅提供了一套完整的子种群划分标准，而且大大缩小了种群的搜索区域，降低了问题难度.除此之外，本文还推导了相关的定义和定理.

1 关键概念

1.1 云模型理论

为了处理定性概念中广泛存在的随机性和模糊性问题，文献[13]提出了包括基本云模型、云发生器、虚拟云、云变换、云可视化等内容在内的云模型.这种云模型是用语言值表示的某个定性概念与其定量表示之间的不确定转换模型，已解决了各种优化问题[14-16].

1.1.1 云的定义

设U是一个用精确数值表示的定量论域，C是U空间上的定性概念，若定量值x(x ∈U)是定性概念C的一次随机实现，x对C的确定度u(x)∈[0,1]是具有稳定倾向的随机数：u(x):U →[0,1],∀x ∈U,x →u(x)，则x在论域U上的分布称为云(Cloud)，记为云C(x)，每一个x称为一个云滴.当C(x)服从正态分布时，该模型称为正态云模型.如果概念对应的论域是n维空间，那么可以拓广至n维云.

1.1.2 云的数字特征

云模型所表达概念的整体特性可用云的数字特征来表征，分别为期望Ex、熵En、超熵He，记作C(Ex,En,He).期望是在数域空间中最能代表定性概念的点，反映云滴群的重心；熵用来综合度量定性概念的模糊度和概率，反映了这个概念的不确定性；超熵是熵的不确定度量，反映了在数域空间代表该语言值所有点不确定度的凝聚性.多维云模型的整体特征可由多组数字特征表示.

1.1.3 云模型的产生方法

生成云滴的算法或硬件称为云发生器，本文用的云发生器为X条件云发生器.给定云的3 个数字特征{Ex,En,He}、特定的x0及云滴数k，产生云滴drop(x0,ua)的伪代码如下：

1.2 进化算法困难性指标

用适应值距离关联测试法[17](fitness distance correlation,FDC)作为衡量进化算法的困难性指标，该方法表明：如果R中的可行解与全局最优解的距离和它与全局最优解的适应值的差成正比，则问题比较容易；反之则问题比较困难.FDC 方法以测试样本集P上的适应值与距离之间的相关系数描述进化算法的困难性.适应值距离相关系数FDCP的具体公式如下：

式中，d(x)表示x到最优解的距离；分别表示样本集P的适应值均值和所有样本到最优解的距离均值.FDCp ∈[−1,1]，当最大(小)值问题趋于−1(1)时，难度变小.

2 基于云模型的问题估计

假设当前最优解为全局最优解，则可以找到一个与原问题相对应的云模型，且只存在一个云模型与原问题差异最小.若此假设成立，则估计的云模型与原问题的最优解相同，且原问题可以转化为一个难度降低的新问题.云模型可在任意时刻对原问题进行估计，进而根据估计结果划分解空间的区域.按照原问题与云模型估计的结果，可以将原问题的解空间划分为期望区域与违背区域.

定义1若原问题为fg(x)，估计的云模型为fc(x)，则在云模型上的数值大于原问题数值的种群空间区域为期望区域(expectation area,EA).

定义2将不满足期望区域定义的种群空间作为违背区域(breach area,BA).

原问题与云估计的位置对比如图1所示，此处以单维问题为例，其中连续复杂适应值曲面代表原问题，云估计代表在过程中的某一时刻建立的云模型.针对此模型，可引出定理1.

定理1若云模型的中心点xT不是全局最优解xO，则xO一定在违背区域内.

证明假设在当前进化过程中问题的全局最优解为xO,云模型的中心点为xT，则中心点在云模型上的适应值为fc(xT)，对于有fc(x)< fc(xT).因为所以fg(xT)< fg(xO)，又fg(xT) =fc(xT)，于是有fc(xO)< fc(xT) =fg(xT)< fg(xO)，可以得出fc(xO)< fg(xO)，进一步可以得出如下结论：若云模型中心点不是全局最优解，则全局最优解一定在违背区域内.此时，对于一个优化问题，若能根据估计的云模型寻找到其违背区域，则可缩小种群的搜索范围，有助于降低问题的难度.

图1 原问题与云估计位置的对比Figure1 Comparison of original problem and cloud estimation position

3 基于动态区域划分的多种群进化算法研究

3.1 问题适应值曲面估计算子

问题适应值曲面估计算子的作用是产生与原问题差异最小的云模型重新估计原问题，其本质是寻找云模型的最优期望值与熵值，从而可将寻找过程归纳为一个优化问题，用数学模型描述为

式中，α为缩放因子，R={x1,x2,··· ,xm}为当前评价集的集合，m为评价集中点的数目.评价集的构造原理详见3.2 节.

本文以当前最优个体Pbest作为云模型的期望值Ex，以原问题与云模型在评价集上的差值为评价标准产生云模型的熵值En.产生熵值的伪代码如下：

3.2 评价算子

评价算子可以产生评价个体优劣的适应值函数，并构造规模固定的评价集对问题进行评价.评价个体优劣的适应值函数f(x)按如下方法选取：

构造评价集的伪代码如下：

其中，违背区域划分准则以及代表个体的选择详见3.3 节.

3.3 区域划分算子

区域划分算子的作用主要是将原问题的解空间划分为期望区域与违背区域，并按聚类方法将违背区域划分为多个子区域.在子区域中，运用差分进化算法(differential evolution algorithm,DE)和遗传算法(genetic algorithm,GA)进行精细搜索，即根据异构策略在不同的区域采用不同的进化方式进行搜索，则子区域间的信息交互及相互转化可保证整个种群之间的信息共享.异构策略图如图2所示.

图2 异构策略图Figure2 Heterogeneous strategy graph

假设违背区域中有N个违背点，于是根据K-均值聚类算法将违背点聚类，聚类完成后参照评价个体优劣的适应值函数在每一类中选出代表个体，并为每个代表个体定义新的搜索区域进行局部搜索.新区域每一维的搜索范围定义如下：

式中，表示第t代第i个代表个体的第j维变量，l为可调因子.

区域划分算子伪代码如下：

其中，N为违背点数目，n为划分区域数目，Np为种群个体数目.

对于一个具体的优化问题，首先建立与其相对应的云模型进行重新估计，并根据估计后的新问题将解空间划分为期望区域与违背区域，然后在划分后的各个子区域使用不同的搜索策略，以期减小搜索区域，降低问题难度，从而使问题求解变得更加简单.因此，本文提出一种基于动态区域划分的多种群进化算法(multi-population evolutionary algorithm based on dynamic area division,DD-MEA)，具体实现步骤如下：

步骤1种群初始化.设进化代数为t，初始化种群为Pt.

步骤2以评价算子构造初始评价集Rt.

步骤3由问题适应值曲面估计算子产生云模型Ct=[Ex(t),En(t),He(t)].

步骤4依据区域划分算子将解空间划分为期望区域EAt和违背区域BAt，得到代表个体{b1,b2,··· ,bn}.

步骤5适应值计算.

步骤5.1y1=fg(Pt)

步骤5.2y2=fc(Pt)

步骤5.3以评价算子评估个体的适应值fitness(Pt)=max(y1,y2)

步骤6将种群中适应值较低的个体替换为{b1,b2,··· ,bn}.

步骤7执行遗传操作（选择、交叉、变异）后更新种群.

步骤8对当前最优个体进行局部搜索.

步骤9以评价算子更新评价集.

步骤10终止条件判断.若t>tmax，则算法结束并输出结果，否则跳转到步骤3.其中，当前最优个体的搜索原理同代表个体.

4 实验数据及分析

本文以CEC2013 测试函数库中的6 个函数为测试函数来分析4 种算法的性能.这4 种算法分别为文化算法(cultural algorithm,CA)、差分进化算法(DE)、元胞遗传算法(cellular genetic algorithm,CGA)、本文所提出的基于动态区域划分的多种群进化算法(DD-MEA)，其种群规模都为200.在这6 个测试函数中，每种算法在不同维度上独立运行30 次，进化代数均设置为500 代.在分析本文算法与其他算法寻优性能的基础上，增添7 个简单的测试函数，运用DD-MEA 算法测试算法的困难性指标.

4.1 算法性能对比分析实验

CEC2013 测试函数如表1所示，其中F1、F2、F3为连续单峰函数，F4、F5、F6为复杂多峰函数，每个测试函数的特点各不相同，在下面的测试结果分析中会具体说明.

表1 CEC2013 测试函数Table1 CEC2013 test functions

函数测试结果如表2所示，其中f表示算法的平均寻优值，即30 次寻优结果的目标函数值的平均值；s为平均收敛代数，即算法收敛到全局最优解所用进化代数的平均值；t为平均收敛时间，即满足收敛条件时所用时间的平均时间，单位为s；“+”表示在同等条件下本文算法所得结果与其他3 种算法所得结果具有显著性差异，显著性分析采用T检验方法，显著性水平设置为0.05；数据加粗表示本文算法在同等条件下得到的指标数据最优.

表2 函数测试结果Table2 Testing results of function

分析表2数据可以发现：根据2 维F1和F6函数优化结果可知4 种算法都能完全找到最优解.在种群规模都相同的情况下，DD-MEA 的平均收敛代数和平均收敛时间最小，且平均收敛代数显著性差异明显，说明DD-MEA 相比于其他3 种算法具有更快的寻优速率.F2函数为一个单峰、不可分离函数，当F2函数的维数变为30 时，CA 和DE 几乎找不到全局最优解；CGA 寻找的结果与最优解接近，但进化时间太长；DD-MEA 不仅可以找到全局最优解，而且其进化代数和寻优时间也远远小于CGA，显然优于其他3 种算法.F3函数属于多模态函数且具有一个非常窄的峡谷，F4函数属于非均匀、多峰函数，这就使得算法的函数值很容易陷入局部最优解.对于F3和F4函数，CA、DE 和DD-MEA 在低维时通常能求到最优解，但各项指标与其他3 种算法存在显著性差异，而大于等于5 维时CA、DE 和CGA 并不能求到最优解，其值已经出现大幅度跳变的情况，DD-MEA 测试的结果是在最优解附近跳动，能求到与最优解附近相近的值.F5函数具有非对称及旋转的特性且局部最优解的数量很多，CA 在由低维至高维的测试过程中，算法的稳定性越来越差；DE 在低维时能找到最优解；DD-MEA 不仅在低维时能完全找到最优解，花费时间较少，而且高维时求到的解也几乎接近全局最优解.F6为可分离且不对称函数，当维数较低维时，4 种算法均能求到最优解.若以时间来衡量，则CGA 和DD-MEA 优于CA 和DE 且具有明显差异，因为DD-MEA 收敛代数远小于CGA，所以DD-MEA 求解低维F6问题时比其他3 种算法效果好，求解高维时更接近最优解，且在收敛代数上表现出较明显的优势.

通过以上实验测试结果可以看出，不管是对于低维还是高维优化问题，DD-MEA 在收敛效率、收敛精度以及收敛代数等方面都表现出较好的测试性能，在通用性和稳定性方面也取得了令人满意的测试效果.

4.2 困难性测试分析实验

困难性测试函数如表3所示，测试函数的维数均为2 维，采用DD-MEA 在一定搜索范围内分析函数在进化过程中各阶段的难度变化.

表3 困难性测试函数Table3 Difficulty test functions

函数困难性测试实验结果如表4所示，DD-MEA 运用适应值距离关联测试法(FDC)分别测试了T1∼T7这7 个函数的初始难度、第25 代难度、最后难度、平均难度以及最后难度和平均难度相对于初始难度有无显著性差异，测试方法与4.1 节中显著性分析部分相同.

根据表4中FDC 的测试结果可以发现，7 个测试函数由难到易分别为T4、T7、T6、T3、T5、T2、T1.由初始难度可知，这7 个测试函数既包括简单问题，也包括复杂问题.函数T4、T5、T6、T7的最后难度和平均难度相对于初始难度具有显著性差异，且最后难度与初始难度显著性差异明显.从问题难度降低的幅度来看，对于函数T4来说，难度降低的幅度最大，初始难度为0.04，平均难度为0.85；对于本身比较简单的函数T1来说，难度降低的幅度为2.24%，降低的幅度较小.函数T7为一多峰复杂函数，具有大量局部最优解，其最初始难度为0.29，进化到后期的难度降低为0.95，难度降低3.2 倍，由此可说明T7函数在进化过程中由原来的复杂问题转换成为一个简单的问题.

表4 函数困难性测试实验结果Table4 Experimental results for difficulty of functions

5 结 语

本文介绍了以多种群进化算法解决优化问题的重要性，引入了云模型理论和进化算法困难性指标两个基本概念，提出了一种基于动态区域划分的多种群进化算法.在传统进化算法的基础上引入云模型，从而将云模型与原问题相结合，通过对云模型的期望与熵的自适应调整来重构优化问题，对种群空间进行区域划分而简化原有复杂问题.

最后分别对3 种不同的进化算法和本文算法进行测试，通过比较分析得到以下结果：1）差分进化算法与文化算法在求解低维问题时效果较好，而求解遇到高维复杂问题时存在求解精度不高、易陷入局部最优以及稳定性差等问题.2）元胞遗传算法在一定程度上能够有效解决上述问题，但是通用性不高，因而对各类优化问题不具备良好的适应性.3）基于动态区域划分的多种群进化算法不仅能够有效避免差分进化算法与文化算法求解精度不高、易陷入局部最优以及元胞遗传算法通用性差等缺陷，在解决高维复杂问题时同样能准确快速地找到全局最优解.根据进化算法困难性测试结果发现，在进化算法过程中问题的困难性有所降低，特别是复杂多峰问题的困难指标降低得更明显，因此利用云模型对优化问题进行估计并对种群空间进行区域划分能够获得较好的求解效果，同时又可以提高算法的收敛速度.