张荣华 刘长征 郭 理

一种两状态动态优化的自学习差异进化算法

张荣华 刘长征*郭 理

(新疆石河子大学信息科学与技术学院 新疆 石河子 832003)

提出一种具有自学习机制的差异进化算法SeDE(Self-Learning Differential Evolution)，提高在动态优化求解过程中群体适应环境动态变化的能力。采用重新评估特定个体的方式监测环境变化。通过群体向新状态历史最优解引导学习，将当代最优个体和两随机个体共同引导个体，保持群体多样性的同时加快算法收敛速度，降低环境的频繁变化对算法搜索能力的影响。通过6个动态函数测试了变化周期、函数维数对算法的影响，同时将新算法与两个同类算法比较，实验结果表明，自学习差异进化能更快地适应环境动态变化，获得更好的优化结果。

智能计算 差异进化 动态优化 自学习机制

0 引 言

在科学与工程中存在大量的动态优化问题。这类问题的设计变量、目标函数、约束条件或者参数等都随着时间的变化而变化，改变了函数的拓扑结构，因此在优化该类函数时，所获得的最优解具有时效性，极大地增加了优化该类问题的复杂度。目前研究者设计的动态环境共分三类[1]：(1) 约束条件的变化产生的动态优化环境，如动态背包问题；(2) 基于二进制编码的异或运算生成的动态测试环境，个体编码中二进制字符串发生异或运算，从而改变了优化环境；(3) 改变函数的拓扑结构，如函数的维度、峰的高度、宽度和位置等属性均发生改变，从而得到动态优化环境。在上述三类动态优化问题中，前两类问题都得到较好的解决，而第三类动态优化问题中，由于多个因素同时发生变化，极大地增加了问题解决的难度，致使当前的优化结果不甚理想。在处理动态优化问题时，智能优化算法表现出良好的竞争力[2]，但在动态环境中，环境的改变极大地降低了历史信息的复用性。同时在环境变化后，群体需要迅速地适应新的环境，是对群体学习能力的极大考验。当群体陷入局部极值点时，所有的个体趋向一致丧失多样性，失去进化能力。为了算法能及时跟踪变化后的极值点，尽快适应环境的变化，进化群体需要保持较好的多样性， Cobb等[3]通过超级变异或可变局部搜索增加群体的多样性，当探测到环境发生变化后，“瞬间”增大或者逐步增加个体的变异率。Yao[4]提出基于群体的增量学习模式，进化个体增加学习率以适应环境的变化。Yang等[5]提出了具有导向性的个体迁入机制，能够更高效地解决某几类动态优化问题。Rosa等[6]认为汉明距离较远的个体交叉，其后代具有更好的多样性，并用动态欺骗函数问题验证了该结论。文献[7,8]将预测和记忆机制引入到动态进化算法的研究中，对算法所得的某些信息进行记忆并构建预测模型，当环境发生变化时能够通过预测模型对动态环境进行预先判断。董明刚等[9]提出一种改进的Oracle罚函数方法与三种自适应差分进化算法相结合，提出三种自适应约束差分进化算法，减少动态环境算法参数。文献[11]采用一种带有动态变量的DE和自适应约束处理方法来自适应动态环境变化。Thanh等[10]较为系统的论述了群体智能进化算法在动态优化问题求解中的优势与不足，并比较了不同进化算法的求解机制和效果。

为此，受前两类动态问题的启发，减少引起环境动态变化的因素，降低解决问题的难度，设计可行的解决方案，进而推进第三类问题的解决。本文提出具有自学习机制的自适应差异进化算法SeDE，处理两阶段动态优化问题。该算法在保持良好群体多样性的同时，加强了精英个体对进化群体的引导作用，利用历史信息加快群体适应环境的动态变化。

1 动态函数设计

动态优化问题DOPs(Dynamic Optimzation Problems)的数学描述为：

minf(x,t)

(1)

其中f(x,t)是与时间相关的目标函数，hi(x,t)=0是第i个与时间t相关的等式约束条件，共m个等式约束条件。gj(x,t)<0是第j个与时间t相关的不等式约束条件，共有n个。

当时间因素t发生变化时，函数f(x,t)的维度、极值、极值的位置等因素均可能发生变化，本文处理极值位置变化引起的动态优化问题。设静态环境下的n维函数f(x)，第i个状态点为οi(ci1,ci2,…,cin)，i=1,2,…,K。则动态函数为:

F(x,ο,t)=f(φ(x,ο),t)

(2)

其中F(x,ο,t)是与时间相关的动态函数；φ(x,ο)是变量x和状态点o间的映射关系；t是驱动f(x)动态变化的时间变量，如算法中的迭代次数、运算平台的物理时间等因素。

F(x,ο,t)=(x1-οi1)2+(x2-οi2)2

(3)

当t满足条件τ时i=1，否则i=2，τ可以与进化代数相关的控制参数。当t变化时，函数的最小值在ο1和ο2间切换。

2 自适应差异进化算法

SeDE算法主要由动态环境检测机制、两阶段的个体学习机制和参数的自适应调整三部分构成。其主要框架如下所示。

算法1 SeDE

输入：动态环境下被优化函数f(x)及其定义域

输出：算法获得的函数f(x)的最优适应值

Step1 初始化群体P：在定义域内初始化群体P、NP个体、D维，P={xij},i=1,2,…,NP;j=1,2,…,D,初始化参数F和CR；

Step2 动态环境检测：检测环境变化，若优化环境改变则执行Step3至Step8，否则执行Step4至Step8；

Step3 学习操作1：判定当前优化环境所在的状态，用当前状态的历史最优解引导群体P学习适应环境；

Step4 学习操作2：群体P向当代最优个体学习；

Step5 评估群体P，从父代和对应的子代中选择优秀个体；

Step6 控制参数调整：采用自适应机制更新变异步长F和交叉概率CR；

Step7 记录最优解x*与最优解对应的适应值fit=f(x*)；

Step8 若满足结束条件，则输出相关统计数据；否则执行Step2。

2.1 环境检测机制

环境检测机制包含两个阶段，首先检测环境是否发生变化，其次确定当前环境所处的状态。在DOPs中检测环境变化的方法主要有两种[12]，即重新评估环境监测器和监测算法行为，优化问题的特点决定了环境检测方式的选择。本文处理的动态优化问题有两个不同的状态，当环境从一个状态转变到另一个状态后，个体适应值发生明显变化。图1以二维Sphere函数为例。

图1 环境变化瞬间个体适应值变化

其次是确定环境所处的状态。在算法中用变量changTime统计环境变化的次数，设定初始值changTime=1，若环境发生变化则changTime=changTime+1。用逻辑变量Status标志当前环境所处的状态，Status=mod(changeTime,2)，其中mod表示取余函数。Status=1表明当前环境处于状态1；否则处于状态2。

2.2 个体自学习机制

为让群体尽快适应变化后的环境，算法采用精英引导下的个体学习机制。根据进化过程中所处的“时空”位置，群体的学习过程分为两个阶段。第一阶段，环境变化后的“瞬间”即环境从状态i转变到状态j时，群体向状态j下的历史最优解学习，i≠j,i,j∈{1,2}。第二阶段，向历史最优解学习结束后，群体向当代最优个体学习。算法2详细描述了群体在两个阶段的学习过程。

算法2 Self-learning algorithm

输入：群体P及其适应值fit；

状态的历史最优解stageBestIndi 及适应值stageBestFit changeTime=1;

% 环境变化次数记录器

输出：测试向量 v

Step1 确定当前群体的最优解bestIndi和最优值bestFit;

Step2 if bestFit≠Revaluate(bestIndi)

% 重新评估最优解，确定优化环境发生改变;

Step3 flag=mod(changeTime, 2);

Step4 if flag==2;

% 优化环境从第一种状态转变到第二种状态;

Step5 if bestFit

% 更新第一种状态的历史最优解与适应值;

Step6 update(bestIndi, bestFit) ;

Step7 对群体P中的所有个体x, v=x+w×(stageBestIndi(2)-x)

% 向状态2下的历史最优个体学习;

Step8 else

% 环境从第二种状态转变到第一种状态;

Step9 if bestFit

% 更新第二种状态的历史最优解与适应值;

Step10 update(bestIndi, bestFit)；

Step11 对群体P中的所有个体x, v= w×(stageBestIndi(1)-x)

% 向状态1下的历史最优个体学习;

Step12 changeTime=changeTime+1;

Step13 else

% 环境没有发生动态变化, 向当代最优个体学习;

Step14 对群体P中所有个体x，vi=bestIndi+F×(bestIndi-randP1)+k×(randP2-randP3)。

向历史最优解学习 当优化环境从状态i转变到状态j后，个体适应值和优秀程度均发生变化，群体需要尽快学习、适应新环境。因此，算法以状态j下的历史最优解作为个体的学习对象。

设算法在状态j下的历史最优解为stageBest(j)。当环境从i转变为j后，个体x在历史最优个体stageBest(j)引导下学习，学习策略如下。

(4)

图2以二维空间中两状态的动态Sphere函数为例，说明了个体x的学习过程。状态1下的个体被状态2的历史最优解引导到v点，更接近状态2下的Sphere函数的最优解，比学习之前有更好的适应值。

图2 个体自学习机制

向当代最优解学习 在应用智能优化问题处理问题时，评价次数、进化代数等均可看做驱动群体进化的资源。动态优化问题中由于环境的动态变换，算法需要在给定资源下快速适应新环境，进而获得相对较好的解。因此，算法采用个体向当代最优解学习的策略。

vi=bestIndi+F×(bestIndi-randP1)+k×(randP2-randP3)

其中，vi是对应于第i个体的过渡测试向量，bestIndi是本代的最优个体，randPj,j=1,2,3是从群体P中随机选择的，不同于bestIndi和当前个体的个体，F是控制变异步长的参数，k是(0,1]间的随机均匀分布。

2.3 个体交叉和更新

交叉对象是vi和Pi，生成目标向量ui，ui=(ui1,ui2,…,uiD)。

(5)

(6)

2.4 参数的自适应机制

群体P中个体均对应变异步长F和交叉概率CR两个控制参数，三者同时进化。第g+1代第i个体的参数F与CR的更新机制如下[12]：

(7)

(8)

其中，randj,j=1,2,3,4是[0,1]上的随机数,τ1和τ2是调整概率，都设定为0.1，Fl=0.1,Fu=0.9。

3 实验与分析

为了测试算法的性能，采用给出的6个测试函数作为测试样例，如表1所示。实验确定了算法在动态环境中不同参数下的优化性能，然后与基本差异进化、自适应差异进化比较。选择6个静态可扩展函数作为测试样例，包括了单峰函数f1至f4和多峰函数f5、f6两种类型。为了获得两个状态的动态环境，在函数f(x)的定义域范围内随机生成固定点O，令f*(x)=f(x-o)。实验中令优化环境在f(x)和f*(x)间循环转换。

表1 测试函数用例

3.1 低维、动态环境下的算法性能实验

为客观测试SeDE在低维问题上的优化性能，算法独立运行25次，在问题定义域上重新初始化群体，规模为30。进化代数限定为2500代。优化环境动态变化的频率为每25代，优化结果的精度设定为1E-8。实验的数值结果如表2所示。

表2 SeDE算法对低维动态函数的优化结果

针对每个测试问题，实验记录第k个状态下，第i独立次运行中第j个循环周期内的最小值pbest(k,i,j)。为了获得状态k下的近似最优值sbest(k)，独立运行算法25次，进化1E+5代，统计每次运行获得最优值的均值。结合上述两类实验数据，计算相对离线误差的最优值的均值和方差，表2中Score条目列出了算法对全部测试函数在状态k下的优化结果均值。可以发现，维数为5时算法在不同环境下的得分相差不大；当维数增加到10时，得分相差一个数量级。这是因为当函数维数从5维增加到10维时，问题的状态空间变大，复杂度增加，加大了算法对环境的跟踪难度，致使优化结果变差。

优化环境从状态i变化到状态j时，进化群体因环境的变化而发生波动，破坏了个体在状态i下的模式，这种“破坏”作用持续进行，直至环境状态j转变回状态i。同样，个体在环境i下的搜索学习过程也是对状态j下模式的破坏。所以，环境的转换过程也是当前环境下个体模式的“重建”和前一个环境下个体模式的“破坏”。上述过程的重复出现造成了适应值的类周期波动，其中横坐标为环境变化值，纵坐标为群体适应度值，如图3所示。

图3 动态环境中群体适应值的周期性波动

3.2 高维、动态环境下不同算法性能比较实验

本次实验比较了环境转变频率对不同算法的影响，并与标准DE算法和文献[12]自适应差分算法做比较。算法在每个频率下独立运行25次，并将每次运行最优结果的均值作为统计指标。为了保证不同周期下环境有相同次数的周期变化，设定算法的迭代次数为GenLmt×100。三个算法的群体规模都设定为30，函数维数设定为30，并在问题空间内随机初始化。实验结果如表3、表4所示。表3、表4中Score指标表示SeDE算法优化结果占优的函数个数。与另外两种算法相比，在不同的环境变化周期下SeDE算法的Score数值为4或5，优势明显。在genLmt=5，10时，环境的快速变化要求个体快速适应新环境，以便尽可能接近或者找到该状态下的最优解，因此要求进化群体具有快速学习能力。在SeDE算法中，新环境的历史最优解在环境变化的“瞬间”引领个体学习，之后当代最优解引导个体学习，这赋予SeDE算法良好的学习能力，比DE更快适应环境变化，获得较好的优化结果。当genLmt=50，100时，环境转变速度较慢，在搜索动态多模函数极值时要求进化群体能保持良好的多样性，以防止陷入局部极值。SeDE算法以保持群体多样性见长的DE算法为基础，并且在个体的学习过程中引入群体中的随机个体信息，所以SeDE算法具有良好的群体多样性，获得较好的优化结果。

表3 不同变化周期下，几种算法的性能比较

表4 不同变化周期下，几种算法的性能比较

4 结 语

本文针对动态优化问题，提出一种基于精英引导学习的新算法SeDE。新算法利用了DE算法群体多样性好的特点，采用重新评估特定个体的方式监测环境变化，同时采用个体的自学习机制，以适应环境的动态变化。当环境发生变化的“瞬间”，新环境的历史最优个体引导群体学习，以便快速适应环境的变化。进入新环境后个体向当代最优个体学习，保持群体多样性

的同时加快算法收敛速度。最后以两状态动态优化的实验结果表明算法能尽快适应环境的动态变化，具有良好的全局和局部搜索能力。但本文只设计了解决两状态的动态优化问题，而现实生活中存在大量多状态动态优化问题，此类问题的研究不仅具有极高的挑战性，也具有重要的实用价值。今后将着重研究此类问题，验证本文算法对多状态动态优化的适应性及应用效果。

[1] Gonza′lez J R,Pelta D A,Cruz C.Optimization in dynamic environments:a survey on problems,methods and measures[J].Soft Computing,2011,15(1):1427-1448.

[2] Yang S,Li C.A clustering particle swarm optimizer for locating and tracking multiple optima in dynamic environments[J].IEEE Transaction on Evolutionary Computation,2010,14(6):959-974.

[3] Cobb H G,Grefenstette J J.Genetic Algorithms for Tracking Changing Environments[C]//International Conference on Genetic Algorithms,Morgan Kaufmann,1993:523-530.

[4] Yao X,Yang S.Population-based incremental learning with associative memory for dynamic environments[J].IEEE Transactions on Evolutionary Computation,2008,12(5):542-561.

[5] Yang S.Genetic algorithms with memory and elitismbased immigrants in dynamic environments[J].Evolutionary Computation,2008,16(3):385-416.

[6] Rosa A C,Fernandes C M.Self adjusting the intensity of assortative mating in genetic algorithms[J].Soft Computing,2008,12(10):955-979.

[7] 陈昊,黎明,陈曦.动态环境下基于预测机制的多种群进化算法[J].小型微型计算机系统,2012,33(4):795-799.

[8] Chen Hao,Li Ming,Chen Xi.Hybrid memory scheme for genetic algorithm in dynamic environments[J].Journal of Applied Science,2010,28( 5):540-545.

[9] 董明刚,程小辉,牛秦洲.基于Oracle罚函数的自适应约束差分进化算法[J].计算机应用与软件,2014,31(1):290-292,322.

[10] Thanh N T,Yang S,Branke J.Evolutionary Dynamic Optimization:A Survey of the State of the Art[J].Swarm and Evolutionary Computation,2012,6(10):1-24.

[11] Silva E K,Barbosa H J C,Lemonge A C C.An adaptive constraint handling technique for differential evolution with dynamic use of variants in engineering optimization[J].Optimization and Engineering,2011,12(12):31-54.

[12] Brest J,Greiner S,Boškovic B,et al.Self-adapting control parameters in differential evolution:A comparative study on numerical benchmark problems[J].IEEE Transactions on Evolutionary Computation,2006,10(6):646-657.

A SELF-LEARNING DIFFERENTIAL EVOLUTION ALGORITHM WITH DUAL-STATE DYNAMIC OPTIMISATION

Zhang Ronghua Liu Changzheng*Guo Li

(SchoolofInformationScienceandTechnology,ShiheziUniversity,Shihezi832003,Xinjiang,China)

We proposed a differential evolution algorithm with self-learning mechanism for improving the capability of population in adapting to dynamic environmental changes in dynamically optimised solving process. By using the approach of re-evaluating specific individuals the algorithm monitors the environmental changes. Through population it guides the learning of the new state historical optimal solution, and guides the individuals by the contemporary optimal individual and the dual random individuals jointly; it keeps the diversity of the population while speeding up the convergence rate of the algorithm, and reduces the impact of frequent environmental changes on algorithm’s search ability. We tested the influences of change period and function’s dimension on the algorithm through 6 dynamic functions, and compared the new algorithm with two similar algorithms at the same time. Experimental result demonstrated that the self-learning differential algorithm could adapt to the dynamic environmental changes more rapidly and achieved better optimisation result.

Intelligent computation Differential evolution Dynamic optimisation Self-learning mechanism

2014-09-09。国家社科基金项目(14XXW004)；教育部社科基金项目(11XJJAZH001)；新疆生产建设兵团社科基金项目(13QN11)。张荣华，讲师，主研领域：人工智能。刘长征，高工。郭理，副教授。

TP18 TP31

A

10.3969/j.issn.1000-386x.2016.04.057