鲁宇明,张祥飞,涂传明,黎政秀

1(南昌航空大学 航空制造工程学院,南昌 330063) 2(南昌航空大学 信息工程学院,南昌 330063)

1 引 言

在科学研究、工程应用和商业等诸多领域中,很多实际优化问题往往伴随着许多约束条件,约束条件的存在给问题的求解带来很大的挑战.近十几年以来,采用进化算法求解约束优化问题吸引了众多研究者参与研究,并且提出了各种形式的约束优化算法[1-3].各种约束处理技术也陆续提出,其中,以Pareto支配为代表的多目标优化法,因其具有突出的收敛性能和效果,及对低可行域的优化问题具有良好的适应性,得到了广大的研究人员的青睐[4-6],但该方法也存在计算成本大、难以有效兼顾收敛性和多样性等方面的不足[7].

差分进化算法[8]具有高效的搜索性能、结构简单等特点,广泛应用于各个领域[9],差分进化多目标优化算法作为一种约束处理技术,具有良好地处理约束优化问题的能力.Wang等人[10]根据多目标优化方法具有低参数等方面的优势,提出了一种基于Pareto支配的CMODE算法,Wang[11]等人从多目标优化方法中分解角度展开研究,提出一种基于多目标分解的DeCODE算法,用以解决约束优化问题.毕晓君等人[12]针对约束优化算法易陷入局部最优和鲁棒性不好等缺点,提出了一种基于自适应ε约束处理法的εCOA算法,Wang等人[13]针对约束优化问题求解过程中难以平衡目标函数和约束条件的问题,提出了一种基于目标函数和约束条件之间关系和可行性准则的CORCO算法,Mallipeddi等人[14]提出了一种集成多个不同约束处理技术的ECHT-DE算法,在差分进化算法方面,Wang等人[15]提出了利用不同变异策略的特性平衡收敛性和多样性的C2ODE算法,閤大海等人[16]提出了根据进化过程中的特点自适应选择变异算子的PJAD-CDG算法,冯艳红等人[17]提出了帝王蝶优化算法和差分进化算法相结合的DEMBO算法,王柳静[18]等人提出基于状态估计反馈的策略自适应差分进化算法,通过设计状态评价因子自适应判定种群个体所处于的阶段,实现变异策略的反馈调节.大多数约束优化算法都是单一的强调约束处理技术或者变异搜索方式的使用,虽然Wang等人[19]通过替换更新机制和变异策略等方式,对可行性准则的贪婪性和鲁棒性进行了削减和改善,并提出了具有良好收敛能力和鲁棒性FROFI算法,但是将具有不同勘探和搜索能力的变异策略与约束处理技术的特点进行结合方面的研究依旧稀少.

针对以多目标优化方法为约束处理技术的算法,会产生高额计算成本以及难以兼顾收敛性和多样性等方面问题,本文从约束处理技术和差分进化算法相结合的适应性出发,研究不同类型的变异搜索方式和多目标方法的约束处理技术相结合的互补方式,提出了一种改进的CMODE算法.将具有全局搜索能力和贪婪搜索能力的变异策略相结合,以一种基于切比雪夫距离的聚类判别方法实现变异方式的切换,达到控制其贪婪性和扰动能力的目的,该算法保持了进化早期种群的多样性,提升CMODE算法进化后期收敛速度.

2 约束优化问题的定义

约束优化问题定义为如下形式:

minf(x)
s.t.gj(x)≤0,j=1,…,q
hj(x)=0,j=q+1,…,m

(1)

式中:x是决策变量,f(x)是目标函数,gj(x)表示第j个不等约束,hj(x)表示第j-q个等式约束,q和m-q分别表示不等式与等式的数量.

在求解中,通常把等式约束转化成不等式约束:

|hj(x)|-δ≤0,q+1≤j≤m

(2)

式中δ为等式约束的容忍参数.

决策变量x在第j个约束条件上的约束违反程度表示:

(3)

所以,决策变量的总约束违反程度表示为:

(4)

3 多种变异方式的串联搜索模式

3.1 差分进化算法的有关算子

差分进化主要由变异、交叉和选择组成,其中一般使用的变异算子如下式:

DE/rand/1:

vi=xr1+F·(xr2-xr3)

(5)

DE/best/1:

vi=xbest+F·(xr1-xr2)

(6)

DE/rand-to-best/1:

vi=xr1+F·(xbest-xr1)+F·(xr2-xr3)

(7)

式中xr1,xr2和xr3是3个相互不同的个体,xbest是种群中最好的个体,F是变异因子.

交叉算子如下式:

(8)

式中,randj是在[0,1]之间产随机数,jrand是(1,…,n)中随机的一个整数,CR是交叉因子.

不同类型的变异算子在均衡全局与局部的搜索能力上具有明显差异,式(5)相对与式(6)式(7)具有良好的全局搜索能力,而式(6)和式(7)类型的变异的方式,引入最优个体参与变异,具有贪婪属性,也同时具有良好的局部搜索能力,这是一种贪婪变异,易导致算法早熟.

3.2 自适应贪婪变异策略

在具有贪婪属性的变异方式中,贪婪性和扰动能力的控制是极其重要的[15,20].本文通过调整贪婪变异结构和参数自适应的方式,控制其贪婪性和扰动能力.

1)贪婪变异结构调整

以DE/rand-to-best/1的算子为基础,调整参与变异的个体,改进DE/rand-to-best/1如式(9)所示:

vi=xr1+rand·(xbest-xr2)+F·(xr2-xr3)

(9)

2)参数自适应设置

为确保使用具有贪婪属性的变异方式初期具有较高的扰动和较低贪婪性,后期则具有较低的扰动和较高的贪婪性.引入sigmoid函数,对式(9)变异因子F进行自适应设置,设置结合了sigmoid函数变化特点和求解问题的复杂程度,如式(10)所示,其变化趋势如图1所示.

图1 F与t函数关系Fig.1 Function relation between F and t

(10)

式中,t表示当前进化代数,T表示最大进化代数,a表示首次切换变异方式时进化代数,若F大于1,则设定F为0.9～0.95之间的随机数.

3.3 串联搜索模式

本文采取多种变异策略,用以满足进化不同阶段对勘探和搜索需求[21].对于单目标优化问题,在前期阶段,进化过程更多是强调全局搜索能力,在后期阶段种群聚焦于某一区域,强调局部搜索能力.因此,本文提出一种基于贪婪变异策略的串联搜索模式.此框架在前期阶段的全局搜索部分采用式(5)的变异方式,交叉算子同时使用式(8),算法初期全局搜索能力得到保证,在后期阶段,采用具有贪婪属性的变异方式式(9),强化算法后期的局部搜索能力,框架如图2所示.

图2 串联搜索模式框架Fig.2 Tandem search pattern framework

4 基于切比雪夫距离的变异方式切换机制

基于聚类思想,本文提出一种基于切比雪夫距离(Chebyshev distance)的变异搜索方式切换机制,该机制主要通过切比雪夫距离衡量比较目标值优秀的个体之间差异,实现变异方式的切换.具体比较方式如式(11)所示:

(11)

式中,k为1～n之间整数 ,xi=(xi,1,…,xi,n) ,xj=(xj,1,…,xj,n),di,j表示个体xi与xj之间的切比雪夫距离,当di,j小于一个较小的阈值μ则认定二者相似,当种群中若干个目标值优秀的个体之间的差异都小于阈值μ则认定算法开始收敛,可以切换为贪婪变异方式.

5 ICMODE算法流程

ICMODE算法具体流程如下,其中式(9)中的xbest选择原则基于可行性准则,根据文献[22]建议,采用贪婪变异策略不与二项式交叉算子同时使用,具体流程图如下所示:

算法1.ICMODE算法框架

输入：Np:种群规模;

λ:参与DE操作个体数;

k:执行替换机制的代数间隔;

MAX_FES:函数最大评估次数.

输出：x*:种群中最优的个体.

Step1.初始化

1.1.在决策空间中随机生成一个规模为Np的种群P;

1.2.计算初始种群Pt的适应度ft和约束违反程度Gt;

1.3.设定评估次数FES=Np;

1.4.设定存档集A=φ;

1.5.初始化进化代数t=1;

1.6.初始化变异类型ARE=0;/*ARE=0表示原始搜索方式,ARE=1表示改进的贪婪变异搜索方式*/

Step2.种群进化

2.1.从Pt随机选择λ个个体(Q);

2.2.Pt=Pt-Q

2.3.根据串联搜索模式选择变异搜索方式,并基于可行性准则确定Q中xbest;

2.4.根据Q生成子代C;

2.5.计算C中个体的适应度fc和约束违反程度Gc;

2.6.FES=FES+λ;

2.7.确定C中的非劣个体集R,假设这里存在m个非劣个体,表示为x1,x2,…,xm;

2.8.假设在Q中存在c个个体被x1所支配,如果c≥1则随机地替换其中的一个,对R中的其他非劣个体保持同样的步骤更新Q;否则不更新Q.

2.9.Pt+1=Pt∪Q.

Step3.存档和替换机制

3.1.如果非劣个体集R中存在不可行解,则A=A∪x,x是R中不可行解中约束违反程度最小的个体,否则A=A∪x,x是R中目标值最小的个体;

3.2.如果mod(t,k)=0,则执行替换机制[10];

3.3.t=t+1;

3.4.终止标准:如果FES≥MAX_FES,则终止程序并输出中最好的个体,否则执行Step 2.

6 实验结果与分析

为验证改进算法的性能,使用CEC2006[23]的24个测试函数进行验证.将ICMODE算法与CMODE[10],C2ODE[15],FROFI[19],CORCO[13]4种约束优化算法进行比较.

6.1 实验参数及条件设置

改进算法设置的参数如下:Np=180;λ=8;k=22;δ=0.0001;F1为在0.5～0.6之间的随机数;CR为在0.9～0.95之间的随机数,阈值μ设定为0.1,

为保证对比算法可以达到最佳的优化效果,对比算法参数按照原文进行设置:

CMODE参数设置的参数如下:Np=180;λ=8;k=22;δ=0.0001;F1为在0.5～0.6之间的随机数;CR为在0.9～0.95之间的随机数;

C2ODE参数设置的参数如下:Np=50;δ=0.0001;Fpool=[0.6,0.8,1.0];CRpool=[0.1,0.2,1.0];ε和μ分别设置为0.5和10-8;

FROFI参数设置的参数如下:Np=80;δ=0.0001;Fpool=[0.6,0.8,1.0];CRpool=[0.1,0.2,1.0];MRN=max(5,D/2),如果D>10,MRN=D/2,否则,MRN=5;

CORCO参数设置的参数如下:Np=100;δ=0.0001;Fpool=[0.6,0.8,1.0];CRpool=[0.1,0.2,1.0];LearnGen=MaxGen/20,LearnGen=MaxFEs/NP;

实验按照文献[10]中规则进行,对每个测试函数单独进行测试25次,函数的最大评价次数(FEs)为500000次.所有实验在硬件配置为Inter Core,CPU:i7-6700,8GB内存,主频3.4GHz的计算机上进行,软件采用matlab2016a运行测试.

6.2 ICMODE与其他算法测试结果对比

5种算法分别以收敛精度、收敛速度和鲁棒性为指标,综合评价算法的普适性.由于5种算法在g20和g22上均未找到可行解,所以测试结果对比将在其余22个测试函数之间进行,表1和表2分别汇总了5种算法的误差值和函数评价次数.

在收敛精度上,以误差值f(xbest)-f(x*)为评价依据,其中x*为最优解,xbest为各算法所获取的最优解,本文提出的ICMODE算法除g21以外的21个测试函数的结果在各项指标均优于或类似于其他4种算法,在表1给出的ICMODE与其余4个算法测试结果中,g02为高维多峰函数,对算法的寻优能力要求较高,在该测试函数上ICMODE的测试结果较其他4个算法具有明显的优势,在中等维度的函数g03,g07,g10,g14,g18和g23上,也对 CMODE具有一定的优势,同时对其余3个算法结果也具有一定的竞争性,因此,ICMODE具有良好的兼顾收敛性和多样性的能力.

在收敛速度上,出于公平起见,我们排除了5种算法都不能寻找到优于或等于文献[23]中给定的最优解的测试函数,其中g17的最优解按文献[10]中的要求更正,在表2给出的5种算法在其余测试函数上搜索到最优解所用的函数评价次数对比中,NA表示在最大评价次数以内未寻找到最优解,ICMDOE在函数g03,g05,g07,g09,g13,g15,g17,g23上优于其他算法,但在平均值上稍差于FROFI,为进一步衡量算法在评价次数上的优劣,表3给出了5种算法Friedman排名[24],由表3可看出ICMODE 和FROFI表现最好.对于其余的测试函数,图3给出了随机地选择几个测试函数的收敛图,并以收敛图的形式比较算法之间的收敛速度,在 g02的收敛图中,C2ODE、FROFI和CORCO在初始阶段具有较快的收敛速度,

表1 ICMODE与其他4种算法在CEC2006约束测试函数上测试结果Table 1 ICMODE and other four algorithms test results on the CEC2006 constraint test function

随后收敛停滞,而ICMODE初始阶段收敛速度较慢但整个进化过程保持了良好的收敛能力,在g18收敛图中,ICMODE拥有对其他4个算法的绝对优势,在g16和 g24,ICMODE与FROFI具有基本相同的收敛速度,优于其他3个算法.因此,ICMODE可以通过提升收敛速度降低多目标优化方法带来的高额计算成本.

表2 ICMODE与其他4种算法平均函数评价次数对比Table 2 Comparison of average function evaluation times between ICMODE and other four algorithms

对于算法的普适性,在鲁棒性和收敛速度上,ICMOD和FROFI算法对CMODE、C2ODE和CORCO算法具有较为明显的优势,在算法收敛精度上,由于FROFI算法在g02和g17收敛精度较差,所以就整体而言,ICMODE算法的普适性优于其他4个算法.

表3 算法在平均函数评价次数上的Friedman排名Table 3 Friedman ranking of the algorithm in the average number of function evaluations

6.3 算法改进措施及参数的有效性验证

检验ICMODE算法采用的改进措施及参数的有效性,本小节对这些改进措施及参数进行验证,验证对象包括:改进的贪婪变异策略;变异搜索方式切换机制中优秀个体数量s和阈值μ.验证过程算法参数设置参考第3节,以最优解误差值的平均值(E)和搜索到最优解所用的函数评价次数平均值(NFES)作为评价指标.这里我们选择具有高维与低维、线性与非线性和等式与不等式约束的测试集g02,g03,g05,g15,g19和 g23.

1)改进的贪婪变异策略有效性验证

将ICMODE算法中使用改进的贪婪变异策略更改成式(6)和式(7)变异策略,式(6)、式(7)变异因子按照文献[16]设定,并分别命名为ICMODE-1和ICMODE-2,由表4可以看出采用改进的贪婪变异策略在收敛速度和部分问题的求解精度上具有良好的优势,且未陷入局部最优.

图3 ICMODE与其他4种算法在g02,g08,g16,g18,g19和g24收敛图对比Fig.3 Comparison of ICMODE and other four algorithms in g02,g08,g16,g18 and g24 convergence graphs

表4 ICMODE与ICMODE-1,ICMODE-2在平均误差和平均评价次数上的对比Table 4 Comparison of ICMODE,ICMODE-1 and ICMODE-2 in average error and average evaluation times

2)变异搜索方式切换机制中优秀个体数量s和阈值μ有效性验证

优秀个体数量s对算法性能影响与阈值μ相反,s值过大或μ值过小会降低算法的收敛速度,s值过小或μ值过大会导致算法提前使用贪婪变异策略,易陷入局部最优.问题变量维度s是柔性检测方法的一个分界点,这里s依次设置为4,6,8,10,12,14;μ依次设置为由1,0.5,0.1,0.05,0.01,表5和表6分别整体来看在s=8,μ=0.1时算法整体 性能最佳.

表5 s分别为4,6,8,10,12,14时算法在平均误差和平均评价次数上的对比Table 5 s is the comparison of the average error and average evaluation times of the algorithm when 4,6,8,10,12 and 14

7 结 论

本文从约束处理技术和差分进化算法相结合的适应性研究出发,针对以多目标优化方法为约束处理技术的算法,会产生高额的计算成本以及难以有效兼顾收敛性和多样性的问题,研究多目标优化方法和不同类型的变异策略的互补结合方式,在以多目标优化方法为约束处理技术的CMODE算法基础上,提出了一种有效的结合方式.算法在前期通过全局性的变异策略逼近最优解所在附近区域,弥补多目标法在兼顾收敛性和多样性上的不足,在后期改进的贪婪变异策略搜索最优解所在附近区域,提升算法的收敛速度,从而降低多目标优化方法在使用过程中高额计算成本.通过CEC2006测试函数,对改进CMODE算法进行仿真测试,分析和对比结果表明,与其他算法相比,改进CMODE算法在多峰函数上具有一定优势,在收敛精度和速度上具有良好的竞争性.局限性在于:优化目标数量相对单一,且不适合处理大规模高维多目标问题,由于目标函数单一,多目标函数的阵列约束优化将是下一步研究的方向.