魏文红，周建龙，陶　铭，袁华强

(1．东莞理工学院计算机学院，广东东莞523808; 2．西安交通大学城市学院计算机系，陕西西安，710018)



一种基于反向学习的约束差分进化算法

魏文红1，周建龙2，陶铭1，袁华强1

(1．东莞理工学院计算机学院，广东东莞523808; 2．西安交通大学城市学院计算机系，陕西西安，710018)

摘要:差分进化算法是一种结构简单、易用且鲁棒性强的全局搜索启发式优化算法，它可以结合约束处理技术来解决约束优化问题．机器学习在进化算法中，经常可以引导种群的进化，而且被广泛地应用于无约束的差分进化算法中，但对于约束差分进化算法却很少有应用．针对这一情况，提出了一种基于反向学习的约束差分进化算法框架．该算法框架采用基于反向学习的机器学习方法，提高约束差分进化算法的多样性和加速全局收敛速度．最后把该算法框架植入了两个著名的约束差分进化算法: (μ+λ) -CDE和ECHT，并采用CEC 2010的18个Benchmark函数进行了实验评估，实验结果表明:与(μ+λ) -CDE和ECHT相比，植入后的算法具有更强的全局搜索能力、更快的收敛速度和更高的收敛精度．

关键词:反向学习;差分进化;约束优化;收敛性

1　引言

优化问题(Optimization Problem，OP)一直都是人工智能领域研究的热点，起初人们一直研究着无约束的优化算法．但实际上许多的科学和工程问题都存在着各种各样的约束条件，这就导致了人们加强了对约束优化问题(Constrained Optimization Problem，COP)的研究［1］．在一般的进化算法(Evolution Algorithm，EA)中，约束条件的出现，会导致可行解区域减小并使得搜索解的过程变得更为复杂．虽然约束优化问题复杂，但人们还是成功地在无约束优化算法中加入约束处理机制来解决约束优化问题．

差分进化算法(Differential Evolution，DE)是由Storn和Price提出的一种功能强大、结构简单、易用且鲁棒性强的全局优化算法［2］，该算法已经被成功地用于各种不同的应用领域．加入约束处理机制的差分进化算法可以解决约束优化问题，如Storn［3］提出的约束适应性差分进化算法(CADE)，它是一种多成员的差分进化算法; Lampinen［4］提出了一种基于帕雷托占优约束处理技术的差分进化算法; Mezura-Montes等人［5］提出了一种基于多成员多样性的差分进化算法(MMDE)，该算法允许每一个父辈可以产生多个子代; Wang等人［6］提出了(μ+λ) -CDE算法，该算法通过μ个种群产生λ个子代，然后把(μ+λ)个种群一起进行迭代; Mallipeddi等人［7］提出了一种合并多个约束处理技术的ECHT-DE算法;在CEC 2006［8］竞赛中，基于ε约束处理技术的εDE算法获得了第一名［9］．大多数的约束差分进化算法虽然在一定程度上解决了约束优化问题，但它们却存在容易过早收敛而陷入局部最优且收敛速度较慢的缺点［10］．

机器学习(Machine Learning)在进化算法中起着重要的作用［11］，由于进化算法在迭代搜索过程中需要存储搜索空间、问题特征和种群信息等大量的数据，因此机器学习方法可以分析这些数据的特征来提高搜索性能．即在全局优化过程中，提取有用的信息来理解搜索行为，用以指导下一步的搜索方向．在许多应用领域，引入机器学习方法的进化算法在收敛速度和问题求解精度方面都有所提高［11］．

基于反向学习(Opposition-based Learning，OBL)的机器学习方法是由Tizhoosh［12］首次提出的，该方法为了获得更优的解来进行下一代迭代，在每次迭代过程中，不仅要评价本次搜索到的最优解，而且还要评价与该最优解处于相反方向的解，然后得出最终的最优解，用来进行下一次迭代．最近基于反向学习的机器学习方法被广泛用于一些启发式进化算法如差分进化、粒子群、人工神经网络、蚁群和人工蜜蜂算法等［13］．Rahnamayan等人［14］首次提出了基于反向学习的差分进化算法，在该算法中，采用基于反向学习的机制来初始化种群．接下来的几年里，包括Rahnamayan自己在内的许多专家学者，分别提出了改进的基于反向学习的差分进化算法［15～19］．Ahandani等人［15］利用基于反向学习策略提出了交换的差分进化算法(SDE) ; Omran［16］结合混沌搜索、基于反向学习、差分进化和量子机制提出了CODEQ算法; Miao等人［17］提出了一种自适应的基于反向学习的差分进化算法(SAODE) ;最近Wang等人［18］推广了基于反向学习的机制，提出了一种基于推广反向学习的差分进化算法(GODE)．所有这些基于反向学习的差分进化算法都是处理无约束优化问题的，然而对于基于反向学习的约束差分进化算法却少见报道，目前Omran提出的CODEQ算法可以处理一些简单的约束优化问题［19］，然而该算法针对CEC 2006［8］中的24 个Benchmark函数只测试了5个约束函数，不能够说明该算法具有很强的优势．在这种背景下，本文提出了一种基于反向学习的约束差分进化算法框架(OBLCDE)，并且把OBL-CDE植入到两个著名的约束差分进化算法(μ+λ) -CDE和ECHT-DE中，针对CEC 2010［20］中的18个Benchmark函数全部进行了实验测试．测试结果显示，与(μ+λ) -CDE和ECHT-DE算法相比，我们的算法具有更强的全局搜索能力、更快的收敛速度和更高的收敛精度．

虽然OBL-CDE与CODEQ都是基于反向学习的约束差分进化算法，但OBL-CDE与CODEQ仍然存在本质的区别: (1) CODEQ是一种具体的算法，OBL-CDE是一种算法框架．OBL-CDE可以植入其它的一些具体的约束差分进化算法中，而CODEQ却不能; (2) CODEQ将混沌搜索、基于反向学习、差分进化和量子机制集于一体，使得算法结构变得复杂;而OBL-CDE只包含了基于反向学习的机制，并不改变差分进化算法的主体结构，因此算法结构简单，运算速度快; (3) CODEQ只测试了CEC 2006中24个Benchmark函数的5个，显然不能证明该算法具有很强的优势，而OBL-CDE测试了CEC 2010中全部的Benchmark函数，并通过各种实验比较说明了OBL-CDE的优势．

2　相关背景知识

2.1约束优化问题

在约束优化问题中，不但包括等式约束条件和不等式约束条件，还包括向量x的上界和下界，具体如下:

其中x = (x1，x2，…，xn)是一个n维决策向量，f(x)为目标函数，gj(x)≤0和hj(x) = 0分别表示q个不等式约束和m－q个等式约束．函数f，gj和hj为线性或非线性实数函数．ui和li分别为变量xi的上界和下界．另外，假定可行解空间中满足所有约束的点集合用U表示，搜索空间中满足上界和下界约束的点集合用S表示，其中SU．

一般地，在约束进化算法中，等式约束经常需要转化成不等式约束，具体如下:

其中j∈{ q +1，…，m}，δ为等式约束违反的容忍因子，一般取正整数，解x到第j个约束的距离可以表示为:

那么解x到可行解区域的边界距离，即约束违反程度可以表示为:

2.2差分进化算法

差分进化算法是一类比较流行的进化算法，并且具有良好的性能，广泛地应用于各种应用领域．在差分进化算法中，一般包括NP个种群，每个个体向量的维度为n．一般地，个体表示为: xri，t= (x1i，t，x2i，t，…，xni，t)，其中i =1，2，…，NP，NP为种群大小，n为个体向量的维度，t为当前种群的代数．差分进化算法包括三个主要的操作，分别是:变异，交叉和选择［21］．

变异在变异操作中，对于每个种群产生目标向量vi，t，变异策略主要如下:

其中下标r1、r2、r3、r4和r5都是随机从集合{ 1，2，…，NP} { i}中选取的，另外xbest，t为种群在第t代最好的个体．缩放因子F为实数，F∈［0，1］．

交叉交叉操作主要产生试验向量ui，t= (u1i，t，u2i，t，…，uni，t)，具体如下:

其中i =1，2，…，NP，j = 1，2，…，n，jrand是属于从1到n之间的一个随机整数，randj(0，1)为对于每个j产生［0，1］均匀分布的随机数．使用参数jrand是为了保证试验向量ui，t不同于目标向量xi，t．交叉概率因子CR的取值通常在0－1之间．

选择在选择操作中，目标向量xi，t和试验向量ui，t根据它们的适应值进行比较，选择适应值更优的进入下一代种群:

2.3基于反向学习

为了更形象地、更清楚地解释基于反向学习的概念，必须先理解反向点的概念．图1显示了区间［a，b］之间x的反向点的例子．

如果对于一个n维向量的反向点，则用如下定义表示．

定义2假设P = (x1，x2，…，xn)为一个n维向量空间的点，其中有了反向点的定义之后，那么基于反向学习的优化可以定义如下．

定义3假设P = (x1，x2，…，xn)为一个n维向量空间的点(比如P是候选解)，f(·)是候选解的目标函数适应值，另外根据反向点的定义可知P的反向点为．如果，则表示比P具有更好的适应值，此时选择珔P代替P，否则保持P不变．

3　算法框架

本文提出的算法并不是一种新的约束差分进化算法，而是基于反向学习机制的一种通用算法框架以改善约束差分进化算法的搜索性能，特别是搜索求解的精度和收敛速度．由定义3可知，基于反向学习的机制需要比较种群与反向种群的适应值，而约束优化问题的适应值不能简单地由目标函数值决定，因此我们就采用一种适应值变换的方法来处理基于反向学习机制中的适应值比较问题．

3.1适应值变换

一般情况下，在无约束差分进化算法中，适应值都等于目标函数值，但是在约束差分进化算法中，由于约束的存在，不能简单地考虑适应值等于目标函数值，必须要考虑约束条件的存在．比如，对于最小值优化问题，解向量X的目标函数值比Y小，但X却违反了约束条件，而Y没有违反约束条件．此时，应该考虑可能解向量Y比X更优．为了更好地处理约束差分进化算法中的适应值，采用适应值变换(Adaptive Fitness Transformation，简称AFT)［22］方法把种群分成三种状态:不可行状态、半可行状态和可行状态．

不可行状态在不可行状态下，种群只包含了不可行解，因此不用考虑目标函数值，只需要考虑约束违反程度．约束违反程度可以通过式(7)计算，此时适应值计算公式如下:

半可行状态在半可行状态下，种群既包含了部分可行解又包含了部分不可行解，因此就必须在目标函数值和约束违反程度之间找到一个平衡点．从解的层面分析，此时把种群细分为可行解组(Z1)和不可行解组(Z2)．因此解xi的目标函数值f'(xi)就可以转换成:

其中φ是上一代种群的可行解比率，xbest和xworst分别是可行解组Z1最优和最差的解．进一步把式(16)归一化为:

式(7)可以计算约束违反程度，在此状态下，式(7)归一化为:

因此最终的适应值可以表示为:

可行状态在可行状态下，种群中所有个体都是可行解，因此就可以看作是无约束优化问题来处理．此时适应值就等于目标函数值f(xi) ，具体如下:

3.2算法描述

在进化算法中，基于反向学习的机制基本上都是用于种群初始化和代跳跃阶段．在种群初始化阶段，对于随机生成的初始种群P0(其中种群大小为NP，个体向量的维度为n)，通过公式OPji，0= aj+ bj－Pji，0计算出相应的反向种群OP0，式中i = 1，2，…，NP，j = 1，2，…，n．然后再从种群P0和OP0中选出适应值更优的个体组成新的初始种群P0．在种群代跳跃阶段，与初始化阶段不同的是，首先，该阶段的执行必须满足一个代跳跃概率Jr，在绝大部分情况下Jr= 0．3［14］．其次，反向种群的计算公式为OPji，t= MIN(Pji，t) + MAX(Pji，t)－Pji，t，其中MIN(Pji，t)和MAX(Pji，t)分别表示第t代种群中最差和最优的个体．OBL-CDE算法伪代码如下:

算法1 OBL-CDE伪代码

算法1中的函数Select－Fitbest－Individual(P，OP)表示从种群P和反向种群OP中选取最优的个体组成新的种群，函数Select－Fitbest－Individual(P，OP)详细描述如下:

算法2 Select－Fitbest－Individual(P，OP)

从算法描述中可以看出，OBL-CDE算法简单且容易操作，它可以植入到所有的约束差分进化算法中．另外，OBL-CDE的时间复杂度为O(Gmax·NP·n)，其中Gmax表示迭代的最大代数．如果植入到其它约束差分进化中，并不会增加它们的时间复杂度．

3.3OBL-CDE算法移植讨论

根据OBL-CDE算法的描述和伪代码，可以看出OBL-CDE算法核心有两部分: (1)在种群初始阶化段采用OBL机制求出该初始种群的反向种群，然后使用适应值变换方法从原始种群和其反向种群中选择最优的种群作为新的初始种群; (2)在子种群的生存选择之后，采用代跳跃方法使当前的子种群跳入到新的候选解中以加速收敛速度．也就是说，求出当前子种群的反向种群，然后也使用适应值变换方法从当前子种群和其反向种群中选择最优的种群作为新的子种群．由于所有的CDE算法都有种群初始化和生存选择两部分，所以我们只要把OBLCDE算法中求初始反向种群和代跳跃两部分的代码植入到其它CDE算法中种群初始化和生存选择的位置便可完成植入过程．由于只需要修改两个位置的代码就可完成OBL-CDE框架到其它CDE算法的植入，所以该植入过程简单可靠，而且通用性强．

4　实验测试

我们对(μ+λ) -CDE和OBL-(μ+λ) -CDE、ECHTDE和OBL-ECHT-DE四个算法选取CEC 2010中18个Benchmark函数的10维(10D)测试函数和30维(30D)测试函数分别进行了对比实验测试．实验环境为64位的Windows 7系统，其中CPU为Intel Core TM 2.83GHz，内存为4GB．我们没有对50维(50D)或更高维的测试函数进行实验，是因为目前的进化算法求解效果都很差，难以分出胜负．与此同时，我们也没有选取CEC 2006中的Benchmark函数做实验测试，因为目前绝大多数的约束差分进化算法对于CEC 2006中的24 个Benchmark函数都能求解到最优解．另外，由于目前大多数的约束差分进化算法都是针对CEC 2006进行实验测试的，而OBL-(μ+λ) -CDE和OBL-ECHT-DE算法对于CEC 2006中的24个Benchmark函数也同样能求解到最优解，因此无法区分出优劣．所以我们的算法只和CEC 2010竞赛中冠军算法εDEag［23］进行了对比测试．

4.1实验参数设置

为了比较公平，OBL-(μ+λ) -CDE与(μ+λ) -CDE设置相同的参数，具体如下［6］: (1)种群大小:μ= 70 (NP =μ)，λ=210; (2)交叉概率: CR = 0．9; (3)缩放因子: F =0．8; (4)代跳跃概率: Jr=0．3．

其它参数的设置也与文献［6］相同，根据文献［6］，变异策略概率pm=0.05，用户自定义参数g =200，阈值代因子k =0.6和容忍因子δ=0.0001．

与前面类似，OBL-ECHT-DE与ECHT-DE设置相同的参数［7］: (1)种群大小:μ=50(NP =μ) ; (2)交叉概率: CR = 0．7; (3)缩放因子: F =0．9; (4)代跳跃概率: Jr=0．3．

4.2性能评价指标

(1)可行解比率:在算法所有次数的运行过程中，成功找到可行解的个数占所有种群个数的比率平均值．该可行解比率的最大值等于1，最小值等于0．值越大，表示算法能成功找到可行解的性能越好．

(2)收敛图:用来表示算法在求解过程中，向最优解靠近的一种渐近走向．该走向的趋势下降的越快，表示收敛性越好．

(3) Wilcoxon符号秩检验［24］:该方法是在成对观测数据的符号检验基础上发展起来的，比传统的单独用正负号的检验更加有效，是非参数的统计测试方法．例如，A算法和B算法进行Wilcoxon符号秩检验测试，如果在测试结果中，A算法对于B算法的R+比R－的值要大，则表明A算法优于B算法．

(4) Friedman测试［25］:与Wilcoxon符号秩检验不同的是，Friedman测试可以针对三个及以上算法进行Rank测试，Rank值越小，表明算法性能越好．

4.3实验结果分析

根据CEC 2010的要求，实验中的每一个算法对于每一个测试函数都运行50次，在每一次运行过程中，对于10D测试函数设置Max－FEs =2×105，对于30D测试函数设置Max－FEs =6×105．

(1) OBL-(μ+λ) -CDE与(μ+λ) -CDE比较

我们对OBL-(μ+λ) -CDE和(μ+λ) -CDE算法针对CEC 2010的Benchmark函数进行了实验测试，结果显示在表1中，其中粗体表示该算法的值更优．从表中的结果来看，在10D测试函数方面，对于平均值，OBL-(μ+λ) -CDE比(μ+λ) -CDE胜出16个函数，有2个函数处于劣势;对于可行解比率，OBL-(μ+λ) -CDE比(μ +λ) -CDE也是胜出16个函数，有2个函数处于劣势．而在30D测试函数方面，对于平均值，OBL-(μ+λ) -CDE比(μ+λ) -CDE胜出17个函数，只有1个函数处于劣势;对于可行解比率，OBL-(μ+λ) -CDE比(μ+ λ) -CDE胜出15个函数，有3个函数相等．比较结果说明了对于高维测试函数，OBL-(μ+λ) -CDE更有优势．另外，我们对10D和30D测试函数各随机选取了一个测试函数进行了收敛性测试，并画出了它们的收敛图，如图2所示．其中图2(a)为10D测试函数c13的收敛图，图2(b)为30D测试函数c15的收敛图．从图2中很明显可以看出，无论是10D测试函数还是30D测试函数，OBL-(μ+λ) -CDE的收敛性都好于(μ+λ) -CDE．

(2) OBL-ECHT-CDE与ECHT-CDE比较

我们也对OBL-ECHT-CDE和ECHT-CDE算法针对CEC 2010的Benchmark函数进行了实验测试，表2显示了比较结果，其中粗体表示该算法的值更优．从表2中可以看到，对于10D测试函数，OBL-ECHT-DE在平均值方面比ECHT-DE胜出14个函数，有4个函数处于劣势;可行解比率方面的情况与平均值差不多，OBL-ECHT-DE 比ECHT-DE胜出13个函数，有1个函数相等，4个函数处于劣势．而对于30D测试函数，在平均值方面，OBLECHT-DE比ECHT-DE胜出16个函数，只有2个函数处于劣势;在可行解比率方面，OBL-ECHT-DE比ECHTDE胜出14个函数，有3个函数相等，只有1个函数处于劣势．比较结果也说明了对于高维测试函数，OBLECHT-DE优势更明显．图3给出了OBL-ECHT-CDE 与ECHT-CDE的收敛图，从图中可以看出，无论是10D测试函数还是30D测试函数，OBL-ECHT-CDE的收敛性都明显优于ECHT-CDE．

表1　OBL-(μ+λ) -CDE与(μ+λ) -CDE实验结果比较

表2　OBL-ECHT-DE与ECHT-DE实验结果比较

表3　OBL-(μ+λ) -CDE、OBL-ECHT-DE与其εDEag算法比较结果

(3) OBL-(μ+λ) -CDE、OBL-ECHT-DE与εDEag算法比较

εDEag算法是CEC 2010竞赛中的冠军算法，即在目前求解CEC 2010的18个Benchmark函数的差分进化算法中，εDEag算法是最优的．在表3和表4中，具有灰色底纹加粗的数据表示最优，仅仅加粗的数据表示次优．

从OBL-(μ+λ) -CDE与εDEag的比较可以看出，对于10D函数，在最优值方面，OBL-(μ+λ) -CDE胜出3个函数，有11个函数相等，只有4个函数处于劣势;在平均值方面，OBL-(μ+λ) -CDE胜出4个函数，有3个函数相等，有11个函数处于劣势;在最差值方面，基本情况与平均值差不多，只是多胜出1个函数，即共胜出5个函数．对于30D函数，在最优值方面，OBL-(μ+ λ) -CDE胜出5个函数，有1个函数相等，有13个函数接近或略差于εDEag算法;在平均值方面，OBL-(μ+ λ) -CDE也胜出了3个函数，有15个函数接近或略差于εDEag算法;在最差值方面，与平均值的情况相同．从OBL-ECHT-CDE与εDEag的比较可以看出，对于10D函数，在最优值方面，OBL-ECHT-CDE胜出4个函数，有11个函数相等，只有3个函数处于劣势;在平均值方面，OBL-ECHT-CDE胜出4个函数，有3个函数相等，其它函数是接近或略差于εDEag算法，在最差值方面，与平均值的情况相同;对于30D函数，在最优值方面，OBL-ECHT-CDE胜出6个函数，有1个函数相等，其它函数是接近或略差于εDEag算法．在平均值方面，OBL-ECHT-CDE胜出2个函数，其它函数是接近或略差于εDEag算法，在最差值方面，与平均值的情况相同．

表4　OBL-(μ+λ) -CDE、OBL-ECHT-DE与其εDEag算法比较结果(续)

我们对于OBL-(μ+λ) -CDE、(μ+λ) -CDE、OBLECHT-DE、ECHT-DE四个算法进行了Friedman测试，测试结果如表5所示．从测试数据很明显可以看出，无论是对于10D测试函数还是30D测试函数，OBL-(μ+ λ) -CDE和OBL-ECHT-DE的排名都分别排在(μ+λ) -CDE和ECHT-DE的前面．另外还可以看出，对于10D测试函数，OBL-(μ+λ) -DE稍优于ECHT-DE;而对于30D测试函数，OBL-(μ+λ) -DE则明显优于ECHT-DE．

最后我们对于OBL-(μ+λ) -CDE、(μ+λ) -CDE、OBL-ECHT-DE、ECHT-DE和εDEag算法进行了Wilcoxon符号秩检验测试，表6是这个几个算法的Wilcoxon符号秩检验测试结果，从结果中可以知道，OBL-(μ+ λ) -CDE和OBL-ECHT-DE分别明显优于(μ+λ) -CDE 和ECHT-DE，稍差于εDEag，但OBL-ECHT-DE在10D函数的最优值方面要优于εDEag．

通过与εDEag算法的比较，我们发现OBL-(μ+λ) -CDE和OBL-ECHT-DE算法并没有很大的优势，甚至稍弱于εDEag算法．这是因为我们提出的是一种算法框架，而不是某一个具体的算法，因此在与εDEag算法比较时，能否超越εDEag算法，还要取决于OBL-CDE植入的母体算法(如(μ+λ) -CDE、ECHT-CDE等)．当然，我们将来的工作，可以考虑将OBL-CDE植入到εDEag算法中，以证明我们所提出的算法框架的优越性．

表5　四个算法针对CEC 2010的Friedman测试结果

表6　Wilcoxon符号秩检验结果

5　结束语

在过去的几年中，加入约束处理技术的差分进化算法可以用于解决约束优化问题，但大数的约束差分进化算法容易陷入局部最优．基于反向学习的机制是机器学习中一种常用的方法，它用于约束差分进化算法中，通过设置反向种群引导算法跳出局部最优的限制．本文提出了一种基于反向学习的约束差分进化算法框架，它采用基于反向学习的机制引导种群进化，以提高求解精度和收敛速度．最后我们把该算法框架应用于(μ+λ)－CDE和ECHT-DE算法，并针对CEC 2010中的18个Benchmark函数进行了实验测试，实验结果表明，我们的算法植入(μ+λ) -CDE和ECHT-DE后，对(μ+λ) -CDE和ECHT-DE算法都有相当明显的改进．将来的工作就是如何把我们的算法框架植入到更多的约束差分进化算法或其它具有约束的进化算法中，以改进它们的性能．

参考文献

［1］Runarsson T P，Yao X．Search biases in constrained evolutionary optimization［J］．IEEE Transactions on Systems，Man，and Cybernetics-Part C: Applications and Reviews，2005，35(2) : 233－243．

［2］Storn R，Price K．Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces［J］．Journal of Global Optimization，1997，11(4) : 341－359．

［3］Storn R．System design by constraint adaptation and differential evolution［J］．IEEE Transactions on Evolutionary Computation，1999，3(1) : 22－34．

［4］Lampinen J．A constraint handling approach for the differential evolution algorithm［A］．IEEE Congress on Evolutionary Computation［C］．Honolulu，HI: IEEE Computational Intelligence Society，2002．1468－1473．

［5］Mezura-Montes E，Velazquez-Reyes J，Coello Coello C A．Promising infeasibility and multiple offspring incorporated to differentialevolution for constrained optimization［A］．Proceedings of the Conference on Genetic and Evolutionary Computation［C］．Washington DC: ACM Press，2005．225 －232．

［6］Wang Y，Cai Z．Constrained evolutionary optimization by means of (μ+λ) -differential evolution and improved adaptive trade-off model［J］．Evolutionary Computation，2011，19(2) : 249－285．

［7］Mallipeddi R，Ponnuthurai P，Suganthan N．Ensemble of constraint handling techniques［J］．IEEE Transactions on Evolutionary Computation，2010，14(4) : 561－579．

［8］Liang J J，et al．Problem definitions and evaluation criteria for the CEC 2006 special session on constrained realparameter optimization［R］．Singapore: Nanyang Technological University，Technical Report，2006．1－24．

［9］Takahama T，Sakai S．Constrained optimization by the ε constrained differential evolution with gradient-based mutation and feasible elites［A］．IEEE Congress on Evolutionary Computation［C］．Vancouver，BC: IEEE Computational Intelligence Society，2006．1－8．

［10］Das S，Suganthan P N．Differential evolution: A survey ofthe state-of-the-art［J］．IEEE Transactions on Evolutionary Computation，2011，15(1) : 4－31．

［11］Zhang J，Zhan Z，Lin Y，et al．Evolutionary computation meets machine learning: A survey［J］．IEEE Computational Intelligence Magazine，2011，6(4) : 68－75．

［12］Tizhoosh H R．Opposition-based learning: A new scheme for machine intelligence［A］．Proceedings of the International Conferenceon Computational Intelligence for Modelling，Control and Automation，and International Conference on Intelligent Agents，Web Technologies and Internet Commerce［C］．Vienna: IEEE Computer Society，2005．695－701．

［13］Xu Q Z，Wang L，Wang N，et al．A review of oppositionbased learning from 2005 to 2012［J］．Engineering Applications of Artificial Intelligence，2014，29(1) : 1－12．

［14］Rahnamayan S，Tizhoosh H R，Salama M M A．Opposition-based differential evolution algorithms［A］．IEEE Congress on Evolutionary Computation［C］．Vancouver，BC: IEEE Computational Intelligence Society，2006．2010 －2017．

［15］Ahandani M A，Alavi-Rad H．Opposition-based learning in the shuffled differential evolution algorithm［J］．Soft Computing，2012，16(8) : 1303－1337．

［16］Omran M G H．CODEQ: An effective metaheuristic for continuous global optimization［J］．International Journal of Metaheuristics，2010，1(2) : 108－131．

［17］Miao X F，Mu D J，Han X W，et al．A hybrid differential evolution for numerical optimization［A］．International Conference on Biomedical Engineering and Informatics ［C］．Tianjin: IEEE Engineering in Medicine and Biology Society，2009．1－5．

［18］Wang H，Rahnamayan S，Wu Z J．Parallel differential evolution with self adapting control parameters and generalized opposition-based learning for solving high-dimensional optimization problems［J］．Journal of Parallel and Distributed Computing，2013，73(1) : 62－73．

［19］Omran M G H，Salman A．Constrained optimization using CODEQ［J］．Chaos，Solitons Fractals，2009，42(2) : 662 －668．

［20］Mallipeddi R，Suganthan P N．Problem definitions and evaluation criteria for the CEC 2010 competition on constrained real-parameter optimization［R］．Singapore: Nanyang Technological University，Technical Report，2010．1－16．

［21］Storn R，Price K．Differential evolution: a simple and efficient heuristic for global optimization over continuous spaces［J］．Journal of Global Optimization，1997，11(4) : 341－359．

［22］Gong W，Cai Z，Liang D．Engineering optimization by means of an improved constrained differential evolution［J］．Computer Methods in Applied Mechanics and Engineering，2014，268(1) : 884－904．

［23］Takahama T，Sakai S．Constrained Optimization by the ε constrained differential evolution with an archive and gradient-based mutation［A］．IEEE Congress on Evolutionary Computation［C］．Barcelona: IEEE Computational Intelligence Society，2010．1－9．

［24］Derrac J，Garc?a S，Molina D，et al．A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms［J］．Swarm and Evolutionary Computation，2011，1 (1) : 3－18．

［25］Corder G，Foreman D．Nonparametric Statistics for Non-Statisticians: A Step-by-Step Approach［M］．Hoboken，NJ: John Wiley，2009．38－56．

魏文红男，1977年9月生于江西南昌，东莞理工学院副教授，博士，主要研究方向:高性能计算、进化算法、多目标优化处理．

E-mail: weiwh@ dgut．edu．cn

周建龙男，1974年6月出生于甘肃临洮，西安交通大学城市学院特聘教授，博士，研究兴趣包括:人机交互、体视化、增强现实、认知计算以及机器学习．

E-mail: zhou－jianlong@ hotmail．com

陶铭男，1986年6月生于安徽马鞍山，东莞理工学院副研究员，博士，主要研究方向:移动IP技术．

E-mail: taom@ dgut．edu．cn

袁华强(通信作者)男，1966年12月生于湖南衡东，东莞理工学院教授，博士，主要研究方向:智能计算．

E-mail: hyuan66@163．com

Constrained Differential Evolution Using Opposition-Based Learning

WEI Wen-hong1，ZHOU Jian-long2，TAO Ming1，YUAN Hua-qiang1
(1．School of Computer，Dongguan University of Technology，Dongguan，Guangdong 523808，China; 2．Department of Computer，Xi’an Jiaotong University City College，Xi’an，Shaanxi 710018)

Abstract:Differential evolution is a global heuristic algorithm，which is simple，easy-to-use and robust in practice．Combining with the constraint-handling techniques，it can solve constrained optimization problems．Machine learning often guides population to evolve in the evolution computation，and is widely applied to unconstrained differential evolution algorithm．However，machine learning is rarely applied to constrained differential evolution algorithm，so this paper proposed a constrained differential evolution algorithm framework using opposition-based learning．The algorithm can improve the diversity and convergence of differential evolution．At last，the proposed algorithm framework is applied to two popular constrained differential evolution variants，that is (μ+λ) -CDE and ECHT-DE．And 18 benchmark functions presented in CEC 2010 are chosen as the test suite，experimental results show that comparing with (μ+λ) -CDE and ECHT-DE，our algorithms are able to improve global search ability，convergence speed and accuracy in the majority of test cases．

Key words:opposition-based learning; differential evolution; constrained optimization; convergence

作者简介

基金项目:国家自然科学基金(No．61103037，No．61300198) ;广东省自然科学基金(No．S2013010011858) ;广东省高校科技创新项目(No．2013KJCX0178) ;陕西省工业科技攻关项目(No．2015GY012) ;陕西省自然科学基础研究计划项目(No．2015JM6331) ;西安交通大学城市学院科研项目(No．2015KZ01，2015KZ02)

收稿日期:2015-04-10;修回日期: 2015-07-08;责任编辑:马兰英

DOI:电子学报URL: http: / /www．ejournal．org．cn10．3969/j．issn．0372-2112．2016．02．026

中图分类号:TP38

文献标识码:A

文章编号:0372-2112 (2016) 02-0426-11