一种求解约束优化问题的自适应差分进化算法

閤大海,李元香,龚文引,何国良

(1.武汉大学软件工程国家重点实验室,武汉大学计算机学院,湖北武汉430072;2.中国地质大学(武汉)计算机学院,湖北武汉 430074)



一种求解约束优化问题的自适应差分进化算法

閤大海1,李元香1,龚文引2,何国良1

(1.武汉大学软件工程国家重点实验室,武汉大学计算机学院,湖北武汉430072;2.中国地质大学(武汉)计算机学院,湖北武汉 430074)

自适应算子选择方式已被用于差分进化算法求解全局优化问题及多目标优化问题,然而在求解约束优化时难于为自适应算子选择方式找到一种方式来恰当分配信用.为此,本文提出了一种基于混合种群的自适应适应值方式来对约束优化问题中变异策略进行信用分配并采用概率匹配方法自适应选择差分变异策略,同时对算法变异缩放因子与交叉率进行自适应设置提高算法的成功率.实验结果表明算法在求解约束优化问题相比于CODEA/OED,ATMES,εBBO-dm,COMDE 以及εDE算法有较高的收敛精度及收敛速度,同时验证了自适应方式的有效性.该算法可用于预报、质量控制、会计过程等科学和工程应用领域.

约束优化;差分进化算法;自适应;信用分配;概率匹配

1 引言

差分进化算法需要根据实际问题需要设置相关参数(种群规模NP,变异缩放因子F,交叉率CR)以及选择合适变异策略,这通常需要进行反复试验才能得到最佳设置.而且随着算法搜寻的解空间区域不同,不同区域所需要的参数及变异策略也不相同[1].因此自适应选择变异策略及设置参数是一种较好的方式.

自适应算子选择(Adaptive Operator Selection,AOS)开始被用于遗传算法[2,3],近来被引入差分进化算法解决全局优化[4,5]以及多目标优化[6]问题,就作者所知该类方法尚未用于解决约束优化问题(Constrained Optimization Problems,COPs).文献[5]提出了一种利用概率匹配(probability matching)方式自适应选择算子的差分进化算法,受此启发本文提出了一种用于解决约束优化的自适应算子选择方法.自适应算子选择需要解决两个问题:一是如何根据操作算子在近期搜寻过程中的表现给出相应信用分配(credit assignment),本文为此提出了一种基于混合种群的自适应适应值的方法来分配信用;二是如何根据分配的信用值来选择操作算子,本文使用了概率匹配方式来选择.此外,对于算法的交叉率CR和缩放因子F,本文采用了JADE算法[7]算法机制来对参数做自适应设置.新的自适应差分约束算法称为PJAD-CDE算法,通过标准测试函数测试测试表明算法在求解约束优化问题时有较好的收敛精度及收敛速度并验证了自适应方法的有效性.

2 约束优化问题定义

不失一般性,约束优化问题可按照以下规则定义:

(1)

一般将等式约束转换为不等式约束处理

|hj(x)|-δ≤0,j∈{q+1,…,m}

(2)

δ为一个正的容忍值.一个解x到第j个约束的距离定义为

(3)

解x到可行区域边界的距离定义为G(x),反映了x违反约束值的大小

(4)

3 标准差分进化算法

标准差分进化算法利用个体混合变异杂交产生后代个体,当后代个体优于父代个体时替换父代个体.差分进化算法中的主要参数包括种群规模NP,变异缩放因子F,以及交叉率CR.

变异算子是差分算法的主要算子.对于种群个体xi,经过变异算子变异后产生的相应变异个体记为vi,常用的差分变异算子包括:

(1)”DE/rand/1”:

vi=xr1+F(xr2-xr3)

(5)

(2)”DE/rand/2”:

vi=xr1+F(xr2-xr3)+F(xr4-xr5)

(6)

(3)”DE/rand-to-best/2”:

vi=xr1+F(xbest-xr1)+F(xr2-xr3)+F(xr4-xr5)

(7)

(4)”DE/current-to-rand/1”:

vi=xi+F(xr1-xi)+F(xr2-xr3)

(8)

其中xr1,xr2,xr3,xr4,xr5是从整个种群中随机选取的互不相同个体,xbest为整个种群中适应值最好的个体.

4 PJAD-CDE算法的变异策略自适应选择

本文和文献[5]一样选取式(5)～(8)的变异策略组成变异策略池来进行自适应选择.自适应选择实现包括:(1)信用分配机制,即如何衡量不同的变异策略在搜寻中的优劣;(2)策略选择机制,即采用何种方式选择变异策略.下面介绍两者的实现.

4.1 信用分配机制

信用分配机制包括:(1)如何衡量由单个策略造成的适应值变化;(2)如何根据适应值变化分配恰当的信用值.对于(1),约束优化问题需要同时考虑个体的目标函数值和违约值,因此需要找到一个恰当的标准来衡量个体的适应值变化.文献[8]提出了一种在约束优化中的个体排序标准,受此启发本文提出了一种混合种群的自适应适应值(combined population based adaptive fitness)方法来衡量个体的适应值变化.将当前种群记为Pt,下代种群记为Pt+1,将Pt和Pt+1混合之后的种群记为Pc.种群Pc分为三种状态:不可行状态,半可行状态,可行状态.计算个体xi的适应值Fit(xi)方法如下:

(1)不可行状态.该状态下种群中只有不可行个体,因此找到可行个体是最重要的,所以个体适应值按照违约值G(xi)计算.

Fit(xi)=G(xi)

(9)

(2)半可行状态.在半可行状态下,种群中同时包含可行个体和非可行个体,按照文献[9]中的自适应适应值转换(Adaptive Fitness Transformation,AFT)方法来计算个体适应值.

将种群Pc分为可行解集合(Z1)和非可行解集合(Z2),个体xi的目标函数值f(xi)按以下公式转换

f′(xi)=

(10)

φ为种群Pc可行解所占比率,xbest与xworst为Z1的最好与最差个体.f′(x)标准化为

(11)

用式(4)来计算个体的违约值并将其标准化

(12)

个体适应值按以下公式计算

Fit(xi)=fnor(xi)+Gnor(xi)

(13)

(3) 可行状态.该状态下种群中只有可行解,适应值由目标函数值f(xi)决定.

Fit(xi)=f(xi)

(14)

种群Pt中的个体xi适应值记为Fit(xi),对应试验个体xi+1适应值记为Fit(xi+1),适应值变化FIi= Fit(xi)-Fit(xi+1).由于在进化早期低劣个体较多适应值提高较大,在进化晚期则反之,因此直接使用适应值的差来计算适应值提高FIi会使进化早期效果较好的策略在进化中占据优势,所以对F(xi)进行标准化.

(15)

个体适应值提高FIi按以下方式计算

FIi=Fitnormal(xi)-Fitnormal(xi+1)

(16)

将Sa记为策略a(a=1,…,k)在第t代的适应值提高集合.则策略a在第t代的信用分配ra(t)按集合Sa的平均值计算:

(17)

4.2 策略选择机制

在策略选择机制上,本文采用概率匹配方法来选择策略.ra(t)为策略a在第t代所获取的信用,qa(t)为策略的已知质量,则该策略在下代质量qa(t+1)的更新公式为:

qa(t+1)=qa(t)+α[ra(t)-qa(t)]

(18)

α∈(0,1]为适应率.策略选择概率按以下公式更新

(19)

pmin∈(0,1)为最小选择概率.

5 PJAD-CDE算法中的参数自适应设置

(20)

(21)

meanL(·)为Lehmer平均值.

(22)

6 PJAD-CDE算法流程

PJAD-CDE算法具体流程如下,”DE/rand-to-best/2”策略中的best个体按如下方式选择:(1)可行个体优于不可行个体;(2)不可行个体中违反约束值G(x)小的个体占优;(3)可行个体中目标函数值f(x)小的个体占优.在处理等式约束时,按文献[9]中类似机制将等式约束转换为不等式约束处理,t为进化代数

算法1 PJAD-CDE算法

输入:搜索空间R,目标函数f,违约函数G;

输出:最优解;

(1) 初始化种群,评估个体的目标函数值与违约值

(2) 对每个策略a,设置qa(t)=0,pa(t) = 1/k

(3) while不满足停止条件

综上所述，匹多莫德口服液联合葛根素治疗儿童过敏性紫癜有效改善患儿血清OPN、PTX3表达水平，提升患儿的免疫功能，降低复发率，安全性较好，疗效显著，值得在临床工作中进行推广。

(4) fori=1 to NP do

(5) 按轮盘赌方式选择策略SIi

(6) 随机选择个体r1≠r2≠r3≠r4≠r5≠i,生成jrand= rndint(1,D)

(8) forj=1 toDdo

(10) 使用策略SIi生成个体uij

(11)endif

(12)endfor

(13)endfor

(14)fori=1toNPdo

(15) 评估后代ui

(16)ifF(ui)≤F(xi)then

(17) 用式(16)计算FIi并用个体ui替代个体xi

(18)else

(19)FIi=0

(20)endif

(21) SSIi=FIi

(22)endfor

(23) 根据式(17)计算每个策略的报酬ra(t)

(24) 根据式(18)更新每个策略的质量qa(t)

(25) 根据式(19)更新每个策略的选择概率pa(t)

(27) t=t+1

(28)endwhile

(29) 输出当前最优解

7 实验结果及分析

为了验证PJAD-CDE算法的有效性,本文选取了13个约束优化测试函数来测试,测试函数详见文献[10].将PJAD-CDE算法与ATMES[9],CODEA/OED[11],εDE[12],COMDE[13],εBBO-dm[14]5种约束算法进行比较.PJAD-CDE算法参数设置如下:k=4,pmin=0.05,α=0.3,c=0.1.7.1 PJAD-CDE与其它算法的性能比较

将PJAD-CDE算法与CODEA/OED,ATMES,εBBO-dm,COMDE,εDE5种算法进行比较,PJAD-CDE,CODEA/OED,εBBO-dm,ATMES均独立运行30次,最大函数评价次数为240000次.εDE运行50次,最大函数评价次数为2000000次.COMDE运行30次,最大函数评价次数为200000次.

由表1看到就收敛精度而言,PJAD-CDE在除函数g02外的其余12个测试函数中的运行得到的最优值,最差值以及平均值均小于或等于其它5种算法的运行结果.函数g02为高维多峰函数,主要考察算法的寻优能力.在该函数的运行结果上，PJAD-CDE运行结果略差于εDE，好于其它几种算法,但考虑到εDE的函数评价次数远大于PJAD-CDE,可以认为PJAD-CDE与εDE在g02上的表现至少是相当的，表明PJAD-CDE的搜索能力强于或者不弱于其它几种算法.在含有等式约束的函数g03,g05,g11,g13的运行结果中,函数g03和g05只有PJAD-CDE找到了最优解.对于函数g11和g13PJAD-CDE与εBBO-dm,COMDE均在每次运行中找到了最优解.显然PJAD-CDE相对于其它5种算法有更好的解决含有等式约束的问题的能力.对于函数g01,g04,g06-g10以及g12,PJAD-CDE与εBBO-dm每次均能找到最优解,优于其它3种算法.在鲁棒性上,PJAD-CDE在函数g01,g03,g05-g08,g11-g13中的方差均小于等于其它5种算法，显然PJAD-CDE在鲁棒性上占优.通过以上对比可以看出在寻优精度及稳定性上PJAD-CDE优于其它算法.

表1 算法运行结果比较

续表

为了对比算法的收敛速度,表2给出了PJAD-CDE算法与CODEA/OED,ATMES,εBBO-dm以及COMDE在函数评价次数为240000次到达最优解的成功率以及在最大函数评价次数为500000次时到达最优解所用的平均函数评价次数的比较,NA表示达到最大评价次数仍未找到最优解,SR表示成功率,NFEs表示评估次数.对于εDE,其函数评价次数为2000000次远高于其它算法而寻优精度劣于PJAD-CDE,显然PJAD-CDE时间复杂度小于εDE.由表3可以看到在成功率上PJAD-CDE算法优于其它4种算法.在函数评价次数上,PJAD-CDE在函数g01,g02,g07,g09,g10,g12上优于其它算法.为了进一步衡量算法在评价次数上的优劣,对5种算法给出Friedman排名.由表3可得PJAD-CDE和εBBO-dm表现最好.但在平均评价次数上,PJAD-CDE明显优于εBBO-dm.总体来看,PJAD-CDE在收敛速度上优于其它算法.

表2 算法在成功率,平均评价次数的对比

表3 算法在函数评价次数上的Friedman排名

由以上分析可知PJAD-CDE算法相对于CODEA/OED,ATMES,εBBO-dm,εDE以及COMDE5种算法在求解约束问题的收敛精度以及收敛速度上均有明显优势.

7.2 自适应选择策略的有效性验证

为了验证基于自适应选择策略的有效性,将PJAD-CDE算法的策略自适应部分改为运行策略“DE/rand/1”,“DE/rand/2”,“DE/rand-to-best/2”,“DE/current-to-rand/1”,算法分别定义为PJAD-CDE1,PJAD-CDE2,PJAD-CDE3,PJAD-CDE4.运行30次,函数最大评估次数为500000次.运行结果如表4,NFEs表示评价次数,SR表示成功率.

表4 PJAD-CDE与PJAD-CDE1,PJAD-CDE2,PJAD-CDE3,PJAD-CDE4在平均评价次数及成功率的对比

续表

由表4可以看到在成功率上,PJAD-CDE与PJAD-CDE1相同,优于PJAD-CDE2,PJAD-CDE3,PJAD-CDE4.在评价次数上PJAD-CDE在函数g01-g12以及平均评价次数上均优于 PJAD-CDE1.PJAD-CDE3在函数g01,g02,g04-g10,g12的评价次数上均优于其它四种算法,表明使用"DE/rand-to-best/2"策略在收敛速度上有较大优势,但同时易于陷入局部最优导致算法成功率下降.总体来看PJAD-CDE算法相比于使用单个策略的PJAD-CDE1,PJAD-CDE2,PJAD-CDE3,PJAD-CDE4算法在保持成功率同时有较好的收敛速度,显示了自适应选择策略的有效性.

7.3 参数自适应设置的有效性验证

PJAD-CDE算法使用了JADE算法机制对参数CR,F自适应设置.为了验证参数自适应设置的有效性,将参数CR,F取文献[5]中的值CR=0.9,F=0.5,算法命名为PJAD-CDE5,算法运行30次,函数最大评估次数为500000次运行，由运行结果发现PJAD-CDE与PJAD-CDE5在各函数的算法评价次数上相差不大,即表示参数自适应设置对算法收敛速度影响不明显.在此仅给出两者在成功率上的对比如表5,SR表示成功率.

表5 PJAD-CDE与PJAD-CDE5在成功率上的对比

由表5可以看到在PJAD-CDE算法在函数g02,g11,g13以及平均值上的成功率明显优于PJAD-CDE5.表明参数CR,F的自适应设置相比于固定取值方式来说在成功率上作用明显.

8 结束语

本文提出了一种自适应约束差分进化算法,算法提出了一种基于混合种群的自适应适应值的方法来分配信用值并采用概率匹配方式自适应选择差分变异算子,对于参数CR与F采用JADE算法机制进行自适应设置.与其他算法的对比结果验证了算法的有效性,同时也验证了自适应机制的有效性.

[1]A K Qin,V L Huang,P N Suganthan.Differential evolution algorithm with strategy adaptation for global numerical optimization[J].IEEE Transactions on Evolutionary Computation,2009,13(2):398-417.

[2]D Thierens.An adaptive pursuit strategy for allocating operator probabilities[A].Genetic and Evolutionary Computation Conference(GECCO'2005)[C].Washington DC,USA:ACM Press,2005.1539-1546.

[3]A Fialho,M Schoenauer,M Sebag,Analysis of adaptive operator selection techniques on the royal road and long k-path problems[A].Genetic and Evolutionary Computation Conference(GECCO'2009)[C].Montreal,Canada:ACM Press,2009.779-786.

[4]Wenyin Gong,Alvaro Fialho,Zhihua Cai,Hui Li.Adaptive strategy selection in differential evolution for numerical optimization:An empirical study[J].Information Sciences,2011,181(24):5346-5386.

[5]Wenyin Gong,A.Fialho,Zhihua Cai,Adaptive strategy selection in differential evolution[A].Genetic and Evolutionary Computation Conference(GECCO'2010)[C].Portland,USA:ACM Press,2010.409-416.

[6]Ke Li,A′ lvaro Fialho,Sam Kwong,Qingfu Zhang.Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation,2014,18(1):114-130.

[7]Jingqiao Zhang,Arthur C.Sanderso.JADE:Adaptive differential evolution with optional external archive[J].IEEE Transactions on Evolutionary Computation,2009,13(5):945-958.

[8]Wenyin Gong,Zhihua Cai,Dingwen Liang.Adaptive ranking mutation operator based differential evolution for constrained optimization[J].IEEE Transactions on Cybernetics,2015,45(4):716-727.

[9]Yong Wang,Zixing Cai,Yuren Zhou,An adaptive tradeoff model for constrained evolutionary optimization[J].IEEE Transactions on Evolutionary Computation,2008,12(1):80-92.

[10]Runarsson TP,Yao X.Stochastic ranking for constrained evolutionary optimization[J].IEEE Transactions on Evolutionary Computation,2000,4(3):284-294.

[11]蔡自兴,江中央,王勇,等.一种新的基于正交实验设计的约束优化进化算法[J].计算机学报,2010,33(5):855-864.

Cai Zixing,Jiang Zhongyang,Wang Yong,et al.A novel constrained optimization evolutionary algorithm based on orthogonal experimental design[J].Chinese Journal of Computers,2010,33(5):855-864.(in Chinese)

[12]郑建国,王翔,刘荣辉,等.求解约束优化问题的εDE算法[J].软件学报,2012,23(9):2374-2387.

Zheng Jianguo,Wang Xiang,Liu Ronghui,et al.ε-differential evolution algorithm for constrained optimization problems[J].Journal of Software,2012,23(9):2374-2387.(in Chinese)

[13]A W Mohamed,H Z Sabry.Constrained optimization based on modified differential evolution algorithm[J].Information Sciences,2012,194(1):171-208.

[14]毕晓君,王钰,李博,等.基于动态迁移的ε约束生物地理学优化算法[J].计算机研究与发展,2014,51(3):580-589.

Bi Xiaojun,Wang Jue,Li Bo,et al.An εconstrained biogeography-based optimization with dynamic migration[J].Journal of Computer Research and Development,2014,51(3):580-589.(in Chinese)

閤大海 男,1981年生于湖北随州.现为武汉大学计算机学院博士生.主要研究方向为演化计算,约束优化.

E-mail:xdh628@163.com

李元香 男，1962年出生于湖北监利，武汉大学计算机学院软件工程国家重点实验室教授，博士生导师，主要研究方向为演化计算的理论与应用研究.

E-mail:yxli@whu.edu.cn

龚文引 男,1979年出生于湖南永顺,博士,中国地质大学(武汉)计算机学院副教授,主要研究方向为演化计算及应用.

E-mail:wygong@cug.edu.cn

An Adaptive Differential Evolution Algorithm for Constrained Optimization Problems

XIA Da-hai1,LI Yuan-xiang1,GONG Wen-yin2,HE Guo-liang1

(1.CollegeofComputerScience,WuhanUniversity.Wuhan,Hubei430072,China;2.SchoolofComputerScience,ChinaUniversityofGeosciences.Wuhan,Hubei430074,China)

The adaptive operator selection method is used to solve the global optimization problem and multi-objective optimization problem of differential evolution algorithm.However,it is difficult to find a way to properly allocate credit for the adaptive operator selection in solving the constrained optimization problem.In order to realize the adaptive strategy selection in differential evolution,we present a combined population based adaptive fitness method to achieve the credit assignment of mutate strategies for constrained optimization problems and use probability matching method to select the mutate strategy adaptively.And we also set the mutation scaling factor and the crossover rate adaptively to improve the success rate of the algorithm.Experimental results show that the algorithm has higher accuracy and convergence speed comparing to CODEA/OED,ATMES,εBBO-dm,COMDE and εDE.We also test and verify the effectiveness of the adaptive method.The algorithm can be used in forecasting,quality control,accounting process,and other scientific and engineering applications.

constrained optimization; differential evolution algorithm;adaptation; credit assignment; probability matching

2015-11-20;

2016-01-07；责任编辑:覃怀银

国家重大仪器专项(No.2011YQ170065.4);国家自然科学基金(No.61573324)

TP18

A

0372-2112 (2016)10-2535-08

��学报URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.10.036