基于分解的多目标量子差分进化算法

常新功　刘文娟　吕亚丽

(山西财经大学信息管理学院　山西 太原 030031)



基于分解的多目标量子差分进化算法

常新功刘文娟吕亚丽

(山西财经大学信息管理学院山西 太原 030031)

基于分解的多目标进化算法MOEA/D(Multi-objective Evolutionary Algorithm Based on Decomposition)具有收敛速度快、分布性好等特点，但其在非凸函数上的性能有待提高。鉴于量子进化算法在多峰值函数上的优良性能，将MOEA/D与量子进化算法相结合，提出基于分解的多目标量子差分进化算法QD-MOEA/D(Quantum Differential Multi-objective Evolutionary Algorithm Based on Decomposition)。QD-MOEA/D的量子染色体采用实数编码，节省存储空间，加快运算速度。为了加快算法收敛速度并提高算法探测能力，量子染色体采取差分进化，其变异方式为量子非门。在多个标准测试函数的实验结果表明，该算法改进了MOEA/D在非凸函数上的收敛性和分布性。

MOEA/D量子计算差分进化实数编码

0　引　言

在科学研究和实际应用中存在多个目标同时优化的问题，这些问题称之为多目标优化问题MOPs(Multi-objective Optimization Problems)。在MOPs中，多个目标之间往往存在着冲突，如何在多个目标之间进行权衡得到最优解，是求解MOPs的核心和关键。大量探索研究表明，进化算法是求解MOPs的有效方法。通过进化计算可以得到一组或多组最优解[1,2]。

Zhang等人[3]于2007年提出基于分解的多目标进化算法MOEA/D。该算法将MOPs中的多个目标以不同的权重分解为若干个单目标优化子问题，然后进化由这些子问题的解组成的种群，逼近真实的Pareto前沿PF(Pareto Front)。MOEA/D算法因其简单、高效而备受关注[4,5]。

为改进算法性能，在原版MOEA/D的基础上引入DE算子，提高了算法的收敛速度，有效地解决了复杂PF问题[4]；另一版本的MOEA/D采用动态分配计算资源的策略，优化了资源配置[6]。在MOEA/D中采用两种不同聚合函数能降低选择聚合函数的难度[7]。Noura等人将MOEA/D算法与PSO算法进行结合，进一步改善了算法的性能[8]。模糊Pareto支配的概念引入，明显提高了算法的收敛速度[9]。针对MOEA/D中的交配池固定这一问题，MOEA/D-AMS动态调整个体交配池以避免陷入局部最优[10]。在国内，刘海林等人采用在超球面均匀取点构造权重的策略，提高了非劣解的均匀性[11]；辜方清等人提出一种基于投影和等距插值的动态权重设计方法，增强解的均匀性[12]；周攀等人将正交试验设计、自适应占优机制以及精英策略引入到MOEA/D算法中，提高了算法的性能[13]。

上述研究主要针对算法的收敛性和分布性，很少对MOEA/D算法在非凸PF的MOPs上的不足进行改进。量子进化算法QEA(Quantum Evolutionary Agorithm)[14-16]是一种收敛速度快、全局寻优能力强的算法。该算法在量子计算的理论基础上，结合进化算法的思想，采用量子位编码染色体，并用量子门更新种群完成进化搜索。与传统进化算法相比，QEA能够在探索与开发之间取得平衡，尤其在多峰值函数上有着出色的表现。

鉴于量子进化算法的优良性能，本文试图将MOEA/D与QEA结合以达到提高非凸PF问题的性能的目的。但单纯地将QEA引入到MOEA/D中不仅无法提高算法在非凸PF问题的性能，还降低了算法在凸PF问题的收敛性。由此，本文提出一种基于分解的多目标量子差分进化算法QD-MOEA/D。该算法按照权重将多个目标分解为多个子问题，每个子问题的个体采用量子染色体编码。其中，量子染色体采用实数编码，利用差分算子进行进化，采用量子与非门进行变异，探测后产生的实数个体用于更新邻域。以期提高MOEA/D在非凸PF的MOPs上的性能。

1　相关定义

1.1多目标优化问题(MOP)

定义1多目标优化问题(MOP)

多目标优化问题由n个决策变量参数，m个目标函数和c个约束条件组成，可描述为：

minimizeF(x)=[f1(x),f2(x),…,fm(x)]T

subject tog(x)=(g1(x),g2(x),…,gk(x))≤0

(1)

wherex=(x1,x2,…,xn)T∈Ω

1.2Pareto最优解及Pareto前沿

定义2Pareto支配关系

对于任意决策向量a,b∈Ω，当且仅当∀i∈{1,2,…,m}，有fi(a)≤fi(b)且∃j∈{1,2,…,m}，使fj(a)

定义3Pareto最优解

Pareto最优解是指如果Ω中没有支配x*的解，则称x*为式(1)中MOP的一个最优解。

通常多目标优化问题有多个Pareto最优解，这些解的集合称为Pareto最优解集。Pareto最优解在目标函数空间的像集称为Pareto前沿。

1.3量子编码及测量

在量子进化算法(QEA)中，采用量子编码方式。在该编码方式中，每个个体可由m个量子位组成。量子位是用一个二维列向量(α,β)T表示的QEA中最小信息单位，其中α,β∈R，且α2+β2=1，α2表示该量子位为0的概率，β2表示该量子位为1的概率。

一个l位的Q-bit组成的一个决策变量q可以表示为如下的2×l矩阵形式：

(2)

在进化算法中，量子染色体表示一次进化过程中所有决策变量的组合，可表示为：

(3)

其中，Qi代表第i个个体的染色体，i∈(1,2,…,g)，g为种群规模，n为决策变量的维度，l为每个决策变量的量子位个数。

探测是指将由量子染色体表示的种群转化为满足约束条件的决策变量种群的过程。具体步骤为：对量子染色体中每个量子位，随机产生一个0到1之间的随机数r，将r与量子位中表示的0的概率进行比较，如果r较小，则该位取0，否则取1。

1.4切比雪夫法

在MOEA/D中，最常用的分解多目标的方法是切比雪夫法，该分解方法如下所示：

(4)

2　基于分解的多目标量子差分进化算法

QD-MOEA/D主要针对MOEA/D在求解非凸MOP函数上的不足，利用量子进化算法在多峰值函数上优良性能，将量子计算引入到MOEA/D中。在算法中，量子染色体采用实数编码，简化量子计算；差分进化量子染色体，加快收敛速度；采用量子非门进行变异，有效地保障了进化种群的多样性。

2.1实数量子染色体编码

量子染色体采用实数编码减少存储空间，简化运算，提高算法性能[17]。在传统的量子进化算法中，由于量子比特(α,β)T。可以用实数θ表示为：(cosθ,sinθ)T，问题式(1)的决策变量维度为n，令每个决策变量用1个量子位表示，则第i个体xi可以表示为：

xi=(|xi,1|xi,2|∧|xi,n|)

(5)

其中，θ=2πrand，rand是[0,1]范围内的随机数，i∈(1,2,…,g)，g为进化算法的进化过程中种群的规模。

(6)

其中，i∈(1,2,…,g)，g为进化算法的进化过程中种群的规模，j∈(1,2,…,n)，n为决策变量维度。

2.2基于差分进化的量子染色体更新

差分进化算法(DE)[18]是一种基于种群的全局启发式全局搜索算法，具有原理简单、受控参数少、鲁棒性强等特点。将差分进化算法应用到量子染色体的更新，能够充分利用邻域信息，加快算法收敛速度。

差分进化算法有多种形式，在算法QD-MOEA/D中，采用DE/rand/1/bin的方式对量子染色体进行进化，其交叉、变异操作具体所示：

量子变异操作: 随机当前个体的邻域中选择一个量子染色体，用其量子位作为基向量和另外两个不同的邻域量子染色体的量子位作为差分向量，生成的方法如下:

(7)

其中，s1、s2、s3是个体i的邻域中的三个不同的个体，F∈[0,1]为收缩因子，k表示当前种群，k+1表示下一代种群。

量子交叉操作: 将新产生的量子变异个体种群与父代个体种群混合产生新个体种群。

(8)

其中，j∈(1,2,…,n)，n为决策变量维度，rand是[0,1]之间的随机数，CR为量子交叉因子，一般是[0,1]区间的数。

2.3量子变异与测量

量子门是量子进化算法进化的动力，量子门有多种，本文采用量子非门对量子染色体进行变异，量子非门的变异处理方法如下:

(9)

令变异概率为PM，若rand

量子染色体是二维向量，经过测量后才能在多目标函数中进行计算，测量的方法如下：

(10)

其中r是随机产生的一个0到1之间的随机数，i∈(1,2,…,g)，g为进化算法的进化过程中种群的规模，j∈(1,2,…,n)，n为决策变量的维度。

2.4算法流程

QD-MOEA/D采用Tchebycheff分解方法。设G为种群的规模,λ1,λ2,…,λg为一个分布均匀的权向量集,z*为参考点,QD-MOEA/D将求解PF的问题式(1)采用Tchebycheff方法分解为G个单目标子问题,第i个子问题可描述为:

在 QD-MOEA/D 中，从权向量λi所在的集合{λ1,λ2,…,λG}中选择与λi距离最近的T个权向量作为λi的邻域，权向量λi的邻域所在的子问题就是第i子问题的邻域。每一代种群由各个子问题的当前最优解构成，而每一个子问题的优化用到邻域信息。

在进化过程中，QD-MOEA/D 要保存的信息有:

① 组成群体的G条实数量子染色体：θ1,θ2,…,θG∈ΩQEA，其中θi为子问题i的量子染色体；

② 组成群体的G个满足约束条件实数个体：x1,x2,…,xG∈ΩMOP，其中xi为子问题i的当前最优解；

③ FV1,FV2,…,FVG,其中FVi=F(xi)，i=1,2,…,N;

④ z=(z1,z2,…,zm)T,其中zi为目标函数fi目前为止所找到的最优值;

⑤ 外部群体(EP),用于存储搜索过程中所找到的非支配解。

QD-MOEA/D算法的流程如下

输入：

① MOP (1);

② 结束条件;

③ G：QD-MOEA/D 所分解的子问题个数;

④ λ1,λ2,…,λG：分布均匀的G个权向量;

⑤ T:权向量的邻域的大小。

输出：EP。

Step 1初始化。

Step 1.1设置EP=φ。

Step 1.2计算任意两个权向量的欧氏距离,为每个权向量选出最近的T个向量作为它的邻域。设第i个子问题的邻域权向量下标为B(i)={i1,i2,…,iT}，其中i=1,2,…,G，即λi1,λi2,…,λiT为距离λi最近的T个权向量。

Step 1.3按照式(5)生成随机的量子染色体θ1,θ2,…,θG，按照式(6)对染色体进行空间变换，按照式(10)对染色体进行探测，得到初始化种群x1,x2,…,xG,设FVi=F(xi)，其中i=1,2,…,G。

Step 1.4根据计算得到目标函数的函数值，初始化z=(z1,z2,…,zm)T。

Step 2更新。

For i=1,2,…,G do

Step 2.1产生新个体：从B(i)中随机选出三个不同的元素s1、s2、s3，取出其对应的量子染色体，按照式(7)进行量子变异操作，按照式(8)进行量子交叉操作，按照式(9)对量子染色体进行量子非门变异操作，按照式(6)进行空间变换，按照式(10)探测，生成新解y。

Step 2.2更新最优解：对每个函数fj，若zj>fj(y),则zj=fj(y)，其中j=1,2,…,m。

Step 2.3更新邻域数值：在第i个子问题中，令每个邻域下标b∈B(i)，对于每个邻域个体xb，如果gte(y|λb,z)≤gte(xb|λb,z),则xb=y，FVb=F(y)。

Step 2.4更新EP：将EP中所有被F(y)支配的解移出EP;若F(y)不被EP中的任意解支配,则将F(y)移入EP。

Step 3停止判断:若满足停止准则,则算法停止,输出EP,否则返回Step2。

3　算法测试及结果分析

为了分析测试QD-MOEA/D的收敛性和分布性，本文选择9个标准的测试函数，分别为ZDT1、ZDT2、ZDT3、ZDT4、ZDT6、DTLZ1、DTLZ2、DTLZ3、DTLZ4[19,20]作为测试用例。并通过计算QD-MOEA/D与MOEA/D和NSGAII[21]的评价指标来验证QD-MOEA/D算法的性能。

3.1测试函数

测试函数的选择关系到算法的评价, 选择科学合理的测试函数有助于对算法的评价。选择测试函数通用的做法是选择大众认可的具有代表性的测试函数。本文中采用了5个标准的两目标的的函数ZDT1、ZDT2、ZDT3、ZDT4、ZDT6[19]，其中函数ZDT1、ZDT4的为凸函数，ZDT2、ZDT6为凹函数，ZDT3为分段函数。同时采用了4个标准三目标的函数DTLZ1、DTLZ2、DTLZ3、DTLZ4[20]，其中DTLZ1为凸函数，DTLZ2、DTLZ3、DTLZ4为非凸函数。并且上述函数的决策变量的维数均设置为10。上述所选9个测试用例能够客观地表现QD-MOEA/D的性能。

3.2评价指标

为了能够更加准确、全面地对该算法进行评价，避免单个性能度量指标的片面性，本文采用以下三个常用的性能评价指标来分析算法的收敛性和分布性。在下面性能指标中，P*为真实PF上均匀分布的 Pareto 最优解集合, X是通过多目标进化算法得到的近似 Pareto 最优解集，m为目标函数的个数，|X|为集合X中元素的个数。

(1) Generational Distance (GD)指标[22]

GD指标度量X到P*的距离,定义为:

(12)

其中,d(v,P*)是v距离P*的最小欧氏距离。因此,该指标越低，表明算法得到的解收敛性越好，越接近真实PF。如果GD(A,P*)=0表明所求得的每个近似 Pareto 最优解都是真实Pareto最优解,这是最理想的情况。

(2) IGD(Inverted Generational Distance)指标[22]

IGD指标度量X到P*的距离,定义为:

(13)

其中，d(y*,P)是y*距离X的最小欧氏距离。若P*中真实的Pareto解足够多且能描绘出完整的Pareto前沿，则IGD指标在一定的程度上能同时反映出所求得的近似PF的多样性和收敛性。 IGD指标值越小,所求得的近似PF越接近整个真实PF,而不能遗漏任何一部分。

(3) Spacing(S)指标[23]

S指标定义为:

(14)

式中，S指标用于评估算法所求得的近似Pareto解在目标空间上的均匀性。该指标越小，表明所求得的Pareto解在目标空间上分布越均匀。

3.3参数设置

本文中所有算法对所有测试函数均采用以下设置：进化群体规模G=100，邻居大小T=20；缩放因子F=0.5，交叉因子CR=0.5,变异概率PM=0.05。

3.4实验结果及分析

为了验证QD-MOEA/D算法是否能够得到最优解，分别将该算法在9个函数上运行50次。为了更直观地看出算法的收敛性和非支配解的分布性，将QD-MOEA/D算法得到的非劣解绘制成近似PF，并与真实PF进行比较，如图1-图9所示。

图1　QD-MOEA/D在ZDT1上的测试结果

图2　QD-MOEA/D在ZDT2上的测试结果　　　　　　图3　QD-MOEA/D在ZDT3上的测试结果

图4　QD-MOEA/D在ZDT4上的测试结果　　　　　　图5　QD-MOEA/D在ZDT6上的测试结果

图6　QD-MOEA/D在DTLZ1上的测试结果　　　　　　图7　QD-MOEA/D在DTLZ2上的测试结果

图8　QD-MOEA/D在DTLZ3上的测试结果　　　　　　图9　QD-MOEA/D在DTLZ4上的测试结果

从以上QD-MOEA/D算法求解的近似PF可知，该算法在9个测试函数得到的近似PF多数逼近真实的PF，且分布比较均匀，只有ZDT4函数的测试效果较差，与真实PF距离较远。但从整体上看，QD-MOEA/D算法具有较好的收敛性，最后求解得出的Pareto解分布比较均匀，尤其是在非凸函数上，这种优势更加明显。

为了更加科学地分析QD-MOEA/D算法的性能，将算法与MOEA/D和NSGAII进行对比实验。QD-MOEA/D算法与QD-MOEA/D算法的参数设置如3.3节所示，NSGAII算法的种群规模为100，将三种算法分别在9个测试函数中运行50次，并计算度量指标GD、IGD、S的均值(mean)和方差(std)，对算法的收敛性、分布性进行比较分析。GD、IGD、S的统计结果如表1所示(效果较好的已用黑体标出)。

表1　各算法的GD、IGD、S均值和方差

由表1可知，在相同的条件下，与MOEA/D及NSGAII相比，QD-MOEA/D的收敛性、分布性在所测试的大多数函数中表现良好，且各个性能指标的方差非常小，表明算法具有良好的鲁棒性。

在表1中，对GD和IGD数据的均值和方差进行比较，除了凸函数ZDT4外， QD-MOEA/D在其他测试函数上的GD值和IGD值均小于MOEA/D，表明该算法的收敛性均优于MOEA/D。但在三目标优化函数DTLZ1和DTLZ3上，QD-MOEA/D和MOEA/D的GD值和IGD值高于NSGAII，故NSGAII在函数DTLZ1和DTLZ3的收敛性优于QD-MOEA/D和MOEA/D。对GD和IGD数据结果分析表明，QD-MOEA/D算法改进了MOEA/D在非凸函数上的收敛性。

表1中S指标用于度量算法的分布性，从指标S的数据中可知，QD-MOEA/D的分布性在ZDT1、ZDT2、ZDT4上略差于MOEA/D，在DTLZ1和DTLZ3上略差于NSGAII。QD-MOEA/D的分布性和多样性表现欠佳的原因为：量子染色体进行差分进化时，随机从邻域选取三个点，在进化初期，因为个体均不相同，因此进化速度很快。到了进化后期，随着对领域的更新，使得很多个体的决策变量相同，尤其是在三个目标的函数中更为明显。邻域中相似的个体越多，种群的多样性越小，随机从邻域中选取的个体相同的概率就越大。因此新产生的个体很可能与原有个体相同，使种群失去进化能力，从而导致种群个体多样性低，分布性差。所以在算法运行后期，需要调整量子染色体的进化策略，从而提高算法性能。但从整体上看，QD-MOEA/D算法的收敛性、分布性均优于MOEA/D和NSGAII，且其鲁棒性强。

QD-MOEA/D与MOEA/D相比具有以下特点：

QD-MOEA/D是在MOEA/D的基础上引入QEA，在算法中用Q-bit对染色体进行编码，每个Q-bit都表示该量子在某种状态时的概率，对Q-bit的进化会影响到与之对应种群。在前期探查中，Q-bit通过对整个目标空间的搜索，保障了种群的多样性；探查的后期，Q-bit趋于某个固定的概率，使算法收敛。因此QD-MOEA/D对PF的形状不敏感，在非凸函数上依旧有良好的性能。

QD-MOEA/D的量子染色体采用实数编码。采用这种编码方式，在不减少个体信息前提下，节省了存储空间，与MOEA/D相比，在每个个体只需多记录一行实数值。此外，实数编码避免了传统QEA不同进制之间的转换，与MOEA/D相比，仅增加了量子染色体探测的过程，在每次迭代时，其时间复杂度仅增加O(1)，对整体的时间复杂度无太大的影响。

QD-MOEA/D沿用了MOEA/D的差分进化，但差分进化的对象不再是个体，而是量子染色体。差分计算使量子染色体在目标空间内进行启发式全局搜索，使量子染色体充分利用邻域信息，加快算法收敛速度，为进化提供新的动力。

QD-MOEA/D采用量子非门进行变异。传统的QEA中，量子门是算法进化的动力，但在QD-MOEA/D中，采用量子非门是为了增加个体的多样性，避免个体陷入局部最优。

上述实验结果也表明，QD-MOEA/D在进化后期种群的多样性减少，这主要是因为到了进化后期，更新邻域后邻域的个体都有重复，进行差分计算后新个体很有可能与原个体相同，使算法失去了进化能力。为了进一步提高算法的性能，可在对Q-bit进行差分计算时动态地增加一个θ值，这将是QD-MOEA/D未来的研究方向。

4　结　语

本文提出了一种基于分解的量子差分进化算法。该算法将MOEA/D与QEA相结合，对量子染色体进行实数编码并用差分进化、非门进行更新，增加个体的多样性，测量后更新邻域，充分利用邻域知识，加快进化速度。在9个标准测试函数上的实验结果表明，该算法明显改善了MOEA/D算法在非凸函数上的收敛性和分布性。但实验也反映出该算法由于依赖邻域信息，在进化后期使个体的多样性减少，从而使函数的分布性变差。因此，下一步的研究工作是如何在产生新个体时增加个体的多样性。

[1] Back T,Hammel U,Schwefel H P.Evolutionary computation:Comments on the History and Current State[J].IEEE Transactions on Evolutionary Computation,1997,1(1):3-17.

[2] Eiben A E,Smith J E.Introduction to Evolutionary Computing[M].Springer:Berlin,2003.

[3] Zhang Q,Li H.MOEA/D:A Multi-objective Evolutionary Algorithm Based on Decomposition[J].IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.

[4] Li H,Zhang Q.Multiobjective Optimization Problems with Complicated Pareto Sets,MOEA/D and NSGA-II[J].IEEE Transaction on Evolutionary Computation,2009,12(2):284-302.

[5] 公茂果,焦李成,杨咚咚,等.进化多目标优化算法研究[J].软件学报,2009,20(2):271-289.

[6] Zhang Q,Liu w,Li H.The Performance of a New Version of MOEA/D.CEC09 Unconstrained MOP Test Instances[C]//Austria:CEC’09.IEEE Congress,2009:203-208.

[7] Ishibuchi H,Sakane Y,Tsukamoto N,et al.Simultaneous use of different scalarizing functions in MOEA/D[C]//USA:Process of Genetic and Evolutionary Computation Conference-GECCO,2010:519-526.

[8] Noura A I Moubayed,Andrei Petrovski,John McCall.A Novel Smart Multi-Objective Particle Swarm Optimization Using Decomposition[C]//USA:PPSN,2010:1-10.

[9] Nasir M D,Mondall A K,Sengupta S,et al.An Improved Mutiobjective Evolutionary Algorithm based on Decomposition with Fuzzy Dominance[C]//USA:CEC,2011:765-772.

[10] Chiang Tsungche,Lai Yungpin.MOEA/D-AMS:Improving MOEA/D by an Adaptive Mating Selection Mechanism[C]//USA:CEC,2011:1473-1480.

[11] Liu Hailin,Li Xueqiang.The multiobjective evolutionary algorithm based on determined weight and sub-regional search[C]//IEEE Congress on Evolutionary Computation,2009:1928-1934.

[12] 辜方清.多目标进化算法中多样性与均匀性策略研究[D].广州:广东工业大学,2011.

[13] 周攀,张冬梅,龚文引,等.基于正交设计的自适应ε占优MOEA/D算法研究[J].计算机应用与软件,2013,30(2):58-64,124.

[14] Hey T.Quantum computing:An introduction[J].Computing and Control Engineering Journal,1996,10(3):105-112.

[15] Narayanan A,Moore M.Quantum-inspired genetic algorithms[C]//Proceedings of the International Congress on Evolutionary Computation,Piscataway:IEEE Press,July 1996:61-66.

[16] Han K H,Park K H,Lee C H,et al.Parallel Quantum-inspired genetic algorithm for combinational optimization problems[C]//Proceedings of the 2001 Congress on Evolutionary Computation:IEEE Press, May 2001.

[17] 陈晓峰,杨广明,黄明.一种实数编码的量子差分进化算法[J].小型微型计算机系统,2013,34(5):1141-1146.

[18] 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.

[19] Zitzler E,Deb K,Thiele L.Comparison of multiobjeetive evolutionary a1gorithms: empirical results[J].Evolutionary Computation,2000,8(2):173-195.

[20] Deb K,Thiele L,Laumanns M,et al.Scalable multiobjective optimization test problems[C]//Process of IEEE Congress on Evolutionary Computation (CEC’02),New Jersey:IEEE press,2002:825-830.

[21] Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

[22] Zitzler E,Thiele L,Laumanns M,et al.Performance assessment of multiobjective optimizers:an analysis and review[J].IEEE Trans.on Evolutionary Computation,2003,7(2):117-132.

[23] Schott J.Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization[D].Master Thesis.Department of Aeronautics and Astronautics,Massachusetts Institute of Technology,Cambridge,MA,1995.

A QUANTUM DIFFERENTIAL MULTI-OBJECTIVE EVOLUTIONARY ALGORITHM BASED ON DECOMPOSITION

Chang XingongLiu WenjuanLü Yali

(FacultyofInformationandManagement,ShanxiUniversityofFinanceandEconomics,Taiyuan030031,Shanxi,China)

Multi-objective evolutionary algorithm based on decomposition (MOEA/D) is featured by high convergence rate and good distribution. However, its performance in non-convex functions is not good enough. In view of the excellent properties of quantum evolutionary algorithm in multi-peak functions, we combined MOEA/D with QEA and proposed the decomposition-based quantum differential multi-objective evolutionary algorithm (QD-MOEA/D). The quantum chromosome of QD-MOEA/D adopts real number in encoding, this saves memory space and accelerates operation speed. In order to speed up convergence speed and improve detection ability of algorithm, the quantum chromosome adopts differential evolution, and its mutation way is the quantum non-gate. Results of experiments on several standard test functions showed that the algorithm improved the convergence and the distribution of MOEA/D in non-convex functions.

MOEA/DQuantum computationDifferential evolutionReal-encoding

2015-01-23。山西省自然科学基金项目(2013011016-4，2014011022-2)；山西省高校科技创新项目(2013124)。常新功，教授，主研领域：进化计算，数据挖掘。刘文娟，硕士生。吕亚丽，副教授。

TP301

A

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