一种求解动态优化问题的改进自适应差分进化算法

刘树强，秦 进

（贵州大学计算机科学与技术学院，贵阳 550025）

0 概述

在现实生活中很多优化问题均具有动态变化特性［1］，例如在调度问题中，随着新任务的到达，机器可能随时发生故障，原材料质量也会随时间产生变化，而静态优化方法无法有效解决上述问题，因此动态优化方法应运而生［2］。当前研究通常将动态优化问题（Dynamic Optimization Problem，DOP）视为一系列静态优化问题（Static Optimization Problem，SOP）的组合，由于目标函数随时改变，因此会导致最优解位置和搜索空间特征的不断变化［3］，而解决动态优化问题的关键是控制解的多样性［4］。传统演化算法在解决静态优化问题方面取得了较好的效果，但不能很好地解决动态优化问题，因为其在运行一段时间后会收敛到固定值，失去探索区域所需的多样性，导致不能跟踪到新环境下已变化的最优解［5］。在动态优化问题中，对不断变化的最优解的快速追踪与找到最优解本身同等重要［6］，这就要求动态优化问题的求解方法同时具备快速收敛和保持多样性的能力。国内外许多研究人员对传统演化算法进行了相关改进，使其能够更好地解决动态优化问题。在过去十几年中，研究人员提出了许多求解动态优化问题的算法及提升算法性能的策略［7］。

差分进化算法与多数演化算法相比，实现过程更简单和直观，具备良好的全局搜索能力，适用于处理大规模问题［8］。差分进化算法不仅在求解静态问题方面表现出较好的性能，而且被证明可用于解决动态优化问题［9］。自适应差分进化（Self-Adaptive Differential Evolution，SADE）是差分进化的分支，通过适应性地改变算法参数值有效处理动态优化问题［10］。文献［11］在动态自适应差分进化算法中引入种群竞争机制。文献［12］认为动态环境下的自适应分为元启发级别、DOP机制级别以及两者组合3个主要的应用级别。文献［13］提出一种动态环境下的自适应差分进化算法，不仅使用自适应控制机制改变其中的控制参数，而且采用带老化机制的多种群方法处理停滞问题，并利用存档的个体重新初始化得到新个体。文献［14］提出一种改进的动态自适应差分进化算法DDEBQ，该算法使用布朗个体和自适应量子个体与差分进化个体共同维持种群的多样性和探索能力，还利用邻域驱动的双变异策略控制摄动以防止过快收敛，并通过排斥规则将子种群分布到更大的搜索空间以加强最优值追踪能力，同时使用老化机制防止算法陷入局部最优。

求解动态优化问题的进化算法需要探索与开发之间的平衡，探索对应算法的全局搜索能力，开发对应算法的局部搜索能力。进化算法既不能陷于局部最优，过分开发某一局部区域，丧失探索其他区域的能力，也不能一直在探索其他区域而不收敛或过慢收敛，忽视开发某一局部区域。差分进化算法是全局搜索能力较好的进化算法，但在演化后期通常收敛慢，局部搜索能力有待提升。自适应差分进化算法虽然通过算子的适应性变化提高了寻优精度，但是参数值的变化仍不能为种群提供足够的多样性。本文提出一种邻域搜索差分进化（Neighborhood Search Differential Evolution，NSDE）算法，运用邻域搜索机制增强差分进化算法中每个子种群的局部搜索能力，在传统基于距离的排斥方案基础上引入hill-valley 函数追踪邻近峰以提高寻优精度。

1 邻域搜索差分进化算法

1.1 动态自适应差分进化算法

SADE 使用rand/1/bin 策略的自适应控制机制，在算法运行过程中改变控制参数F和CR，而种群规模NP 在演化过程中保持不变。自适应控制参数的计算公式如下：

其中：randj，j∈{1，2，3，4}表示取值为［0，1］的均匀随机数；τ1和τ2分别为控制参数F和CR 的调整概率；τ1、τ2、Fl、Fu分别取固定值0.1、0.1、0.1、0.9；F取值为［0.1，1.0］的随机数；CR 取值为［0，1］的随机数；通常在变异前计算得到，从而影响新向量的变异、交叉和选择。

在原始动态SADE 算法［13］中，老化机制的第i个个体的老化算法以及改进和老化算法如算法1 和算法2 所示，利用存档的个体重新初始化算法如算法3所示，其中，subSize 是子种群大小，ARC 是关于个体的存档，arcNum 是存档大小，mRand（）是产生随机数的函数，age 是个体年龄。

算法1第i个个体的老化算法

算法2改进和老化算法

算法3重新初始化算法

原始动态SADE 算法的具体内容详见文献［13］，本文在原始动态SADE 算法的基础上提出NSDE 算法（如算法4 所示），主要改进为邻域搜索和排斥算法。

算法4NSDE 算法

1.2 邻域搜索机制

种群最优个体邻域范围内的解会有较高的可能性靠近最优值点，该可能性随着维度的增加而增加。本文提出一种种群最优个体的邻域解生成方式，首先利用自适应差分进化算法产生初步的种群最优个体，然后对种群最优个体的邻域空间进行适当划分，分别在不同范围内产生候选解，构成候选解集合，最后选取集合中的最优解，对种群最优个体进行迭代，以期逼近最优值点。

组成动态优化问题的静态优化问题可表示为：

其中，X、L、U均为n维向量，X=(x1，x2，…，xn)，L=(l，l，…，l)，U=(u，u，…，u)，X各分变量的取值均为［l，u］。

NSDE 算法利用矩形定义点的邻域，通过同心超矩形划分当前解分量xj(j=1，2，…，n)的邻域空间［15］，如图1 所示，假设分成k个空间，按式（2）划分每个空间大小：

图1 邻域空间划分Fig.1 Division of neighborhood space

在Ri（i=1，2，…，k）的每个同心矩形内随机选取1 个点，这k个点构成当前解分量xj的候选值集合（如算法5 所示），整个候选解的产生如图2 所示，其中，MaxIter 是迭代次数，mRand（）是产生随机数的函数，candiNum 是邻域候选解个数，r是邻域半径r0，x是某个子种群中的最优个体，xi是x的第i维的值，candiSol′是得到的候选解集合，BestSol是候选解集合中的最优解。

算法5邻域搜索算法

图2 候选解的产生Fig.2 Generation of candidate solutions

1.3 排斥方案

排斥方案的关键为将每个子种群维持在适应度（fitness）范围内的不同峰上，子种群可以由其中的最优个体代表。每个子种群实施一种排斥方案，如果与其他子种群在同一个峰上，那么较好的子种群保持不变并重新初始化较坏的子种群。文献［16］提出一种基于距离的排斥方案，该方案假设所有的峰均匀分布在整个搜索空间中，如果两个子种群间的距离小于阈值，那么较坏的子种群被重新初始化，其中，n是维数，A是解的范围，m是峰数。

基于距离的排斥方案中的两个峰可能很接近，以至于它们之间的距离比排斥方案的阈值还小，在此情况下很难同时找到这两个峰。本文在基于距离的排斥方案的基础上增添一个hill-valley函数［9］，如图3所示。当满足基于距离的排斥方案条件时，判断是否存在满足f（z）＜min｛f（x），f（y）｝，如果不满足，则最终进行排斥操作（如算法6所示），其中，x和y分别是两个子种群中的最优个体，z=c⋅x+(1-c)⋅y，c∈{0.05，0.50，0.95}。

图3 基于hill-valley 函数的排斥方案Fig.3 Exclusion scheme based on hill-valley function

算法6排斥算法

2 实验与结果分析

2.1 对比算法

在求解动态优化问题的演化算法中，本文采用人工免疫网络动态优化（Dynamic Optimization of Artificial Immune Network，dopt-aiNet）算法［17］、原始动态SADE算法（简称SADE）［13］、多种群竞争差分进化（Differential Evolution with Competitive Strategy Based on Multi-Population，DECS）算法［18］和改进差分进化（Modified Differential Evolution，MDE）算法［19］与NSDE 算法进行对比，具体为：1）dopt-aiNet 算法对opt-aiNet 算法［20］进行扩展，增加了分离的记忆种群、新的变异算子和种群规模最大值及控制衰退的搜索过程和亲近度测量过程，可避免opt-aiNet算法的细胞数盲目扩增问题；2）SADE算法使用自适应控制机制、多种群机制与老化机制改变控制参数；3）DECS 算法将竞争机制融入多种群差分进化算法中，增强算法寻优能力；4）MDE 算法将种群分为跟踪和搜索两个子种群，对两个子种群采用不同的变异策略，利用跟踪种群判断环境变化，采用搜索种群扩大搜索范围。为避免算法结果的复现问题，SADE算法的实验数据由实际仿真得到，而dopt-aiNet、DECS和MDE 算法的实验数据来自文献［17-18］。

2.2 测试函数与算法参数设置

本文使用GDBG 生成器［21］验证NSDE 算法的有效性。GDBG 是一种广义动态benchmark 生成器，构造二元空间、实空间与组合空间的动态问题，这些问题具有大量的旋转操作和局部最优解以及更高的维度。GDBG 包含6 种测试函数和7 种变化情况，总计49 个测试问题，通用参数设置如表1 所示，其中高度范围、起始高度和采样频率的单位为1。

表1 GDBG 通用参数设置Table 1 General parameter setting of GDBG

测试函数由表2所示的Sphere、Rastrigin、Weierstrass、Griewank、Ackley 这5 种函数通过旋转、组合产生，F1 测试函数求解最大值优化问题，F2～F6 测试函数求解最小值优化问题，其中F1 分为带有10 个峰和带有50 个峰两种情况，具体定义为：

F1：旋转峰函数（10 and 50 peaks）；

F2：Sphere 函数的组合函数；

F3：Rastrigin 函数的组合函数；

F4：Griewank 函数的组合函数；

F5：Ackley 函数的组合函数；

F6：混合组合函数。

7种变化类型具体为小步变化（T1）、大步变化（T2）、随机变化（T3）、混沌变化（T4）、周期变化（T5）、带噪声的周期变化（T6）和维度改变的随机变化（T7）。

表2 GDBG 基本测试函数Table 2 Basic test function of GDBG

算法参数设置如表3 所示，种群规模、子种群数、子种群规模、F初始值、CR初始值的取值参考文献［13］，邻域半径、邻域候选解个数、迭代次数的取值通过简单实验计算得到。

表3 算法参数设置Table 3 Algorithm parameter setting

2.3 评价指标

本文选用平均误差和标准差作为评价算法性能的指标，平均误差和标准差的计算公式如下：

其中，nnum_change表示测试函数的变化次数，rruns表示算法独立运行的次数，(t)表示算法在第i次独立运行时第j次变化的适应度绝对误差值，计算公式如下：

其中，f(xbest(t))和f(x*(t))分别表示算法寻得的最优值和理论最优值。

2.4 结果分析

本文在Windows 7 x86_64 操作系统、Intel®CoreTMi3-3220 CPU、3.30 GHz 主频、8 GB RAM、C/C++编程语言环境下进行实验。对6 个测试函数进行20 次独立测试，实验结果如表4、表5 所示，并将5 种算法在每个测试函数下得到的平均误差的最小值加粗显示。根据对比实验结果，从测试函数角度分析可知，NSDE 算法在F1（50 peaks）、F2、F3、F4 和F5 测试问题上的精度相比SADE 算法提升最为明显，能够更好地应对F1（50 peaks）的峰数增加导致的环境复杂性变化以及F2、F3、F4 和F5 特征明显不同的环境动态变化。从变化类型角度分析可知，NSDE 算法在T1、T2、T5、T6 和T7 变化类型下的平均误差比SADE 算法小，即在小步变化、大步变化、周期变化、带噪声周期变化、维度改变随机变化情况下的寻优能力相较SADE 算法更好。可以看出：NSDE 算法相比SADE 算法在49 个测试问题中有28 个测试问题的平均误差更小，表明其具有更优的复杂问题求解能力；仅在F2、T1、T7 上劣于dopt-aiNet 算法，在49 个测试问题中有38 个测试问题的平均误差更小；仅在F4、T3 上劣于MDE 算法，在49 个测试问题中有38 个测试问题的平均误差更小；仅在F2、F4、T2、T7上劣于DECS，在49 个测试问题中有29 个测试问题的平均误差更小。可见，NSDE算法相比DECS、dopt-aiNet和MDE 算法具有更优的复杂问题求解能力。

根据仿真实验结果可以得出NSDE 算法在各类测试问题及各种变化类型下的收敛趋势，如图4 所示。相对误差（E）的计算如式（7）所示：

其中，f（x）是算法寻得的最优值，f（x＊）是理论最优值。

NSDE算法收敛曲线反映了收敛速度及陷入局部最优值的次数，进而体现算法响应环境变化的能力。由于F3测试函数的基础组成函数Rastrigin是典型的非线性多模态函数，峰与峰之间的起伏较大，并且具有大量局部极值点，因此算法在F3测试函数中的表现较差，相对而言更容易陷入局部最优而出现停滞状态。但除此之外，NSDE算法在其他测试函数中均表现良好，具有较快的收敛速度，能及时响应环境变化并快速搜索新的全局最优值并保持种群多样性。

表4 NSDE 与SADE 算法的实验结果Table 4 Experimental results of NSDE and SADE algorithms

表5 NSDE、DECS、dopt-aiNet 和MDE 算法的实验结果Table 5 Experimental results of NSDE，DECS，dopt-aiNet and MDE algorithms

续表

图4 NSDE 算法在7 个测试问题上的收敛曲线Fig.4 Convergence curves of NSDE algorithm on seven test questions

3 结束语

本文在原始动态SADE 算法的基础上提出一种邻域搜索差分进化（NSDE）算法，产生初步的种群最优个体，对种群最优个体的邻域空间进行划分，并在不同的领域空间范围内产生候选解构成候选解集合，选取集合中的最优解对种群最优个体进行迭代，增强算法局部搜索能力。在基于距离的排斥方案中，引入hill-valley函数提高算法寻优精度。实验结果表明，NSDE 算法相比SADE、dopt-aiNet、DECS 和MDE 算法整体性能更优。后续将对NSDE 算法做进一步优化，提升其在处理复杂动态问题时的适用性与稳定性。