基于Pareto-ε优胜的自适应快速多目标演化算法

摘 要:在多目标优化领域,如何快速地为决策者提供合理、可行的解决方案尤为重要,为此,给出了多目标优化问题的一种新解法。定义了一种Pareto-ε优胜关系的概念,将此概念引入多目标优化问题中,设计了一种新的基于ε-优胜的自适应快速多目标演化算法。计算机仿真表明,该算法可以明显改善求解多目标优化问题时的寻优过程,能适应实际应用环境下快速、有效的决策要求。

关键词:

多目标优化; Pareto优胜; Pareto前沿; 演化算法; 自适应

中图分类号: TP18

文献标志码:A

Quick multi-objective evolutionary algorithm based on adaptive Pareto-ε dominance

WANG Jiang-qing1, YANG Xun2

(

1. College of Computer Science, South-Central University for Nationalities, Wuhan Hubei 430074, China;

2. Yan’an General Office, China Executive Leadership Academy,Yan’an Shaanxi 716000, China

)

Abstract:

For multi-objective optimization problems (MOP), it is very important to provide proper and feasible solutions rapidly for the decision makers. A method for MOP was given. First, a conception of Pareto-ε dominance was defined. Then, based on this conception, a new adaptive multi-objective evolutionary algorithm was proposed. The numerical results demonstrate that the new algorithm can improve the process of MOP optimization, and can meet the requirement of the high-speed, effectiveness in application.

For Multi-objective Optimization Problems (MOP), it is very important to provide proper and feasible solutions rapidly for the decision makers. A method for MOP was given. First, a concept of Pareto-ε dominance was defined. Then, based on this concept, a new adaptive multi-objective evolutionary algorithm was proposed. The simulation results demonstrate that the new algorithm can improve the process of MOP optimization, and can meet the requirements of high-speed and effectiveness in application.

Key words:

multi-objective optimization; Pareto dominance; Pareto front; evolutionary algorithm; adaptive

0 引言

科学研究和工程应用中的优化问题大多是多目标优化问题(Multi-objective Optimization Problem,MOP),如车辆路径路径问题、QoS路由等。这类问题通常包含若干个相互矛盾且没有共同量纲的目标 [1-3]。如何在优化过程中既兼顾各目标利益又体现各目标的地位,是求解此类问题的关键[4-5]。

多目标优化的目的是使决策者最终能够找到一个满意的决策方案。目前在多目标优化算法中,基于Pareto优胜的算法非常流行[6-8]。这些算法主要集中于利用算法找到最大的Pareto最优解集,找到Pareto 前沿与已知全局前沿的最小距离,及找到解的最大宽度等[9-10]。然而,在实际的应用系统中,决策者通常期望算法能够在较短的时间内提供一个或几个可采纳的解决方案。在算法的效率和解的质量不能同时满足的情况下,如何快速地给决策者提供合理、易决策、可接受的解决方案,是算法走向实际应用的一个关键问题。

本文定义了一种Pareto-ε优胜的概念,并基于此概念提出了一种新的基于ε-优胜的多目标演化算法(Pareto-ε Multi-Objective Evolutionary Algorithm,PEMOEA)。该算法采用一种新的带调节度的搜索策略以调节搜索的步长,加快算法的收敛,并采用ε的自适应调整策略改进解的质量。实验结果显示,新策略可以使搜索更加快速有效地到达Pareto前沿,为决策者提供可行的解决方案。

1 Pareto-ε的相关定义

图1为Pareto比较搜索示意图。图中f1 和f2为两个子目标,表示搜索空间中的随机点,所组成的曲线表示最终的Pareto前沿。

图片

图1 Pareto比较搜索示意图

如果从随机点A出发进行搜索,那么A的附近有B、C、D优于它(极小化)。逐步推进搜索到E、F、G、H,然后搜索到N、O、…、S,最后才能搜索到Pareto前沿…。通过分析发现,从A搜索到最优解,做了许多无用功。如果采取一定的策略,适当调整搜索的步长,搜索速度将会大幅度提高。

定义1 Pareto-ε优胜。向量u=(u1,…,un)ε-优胜于向量v=(v1,…,vn)(表示为u┆华εv)当且仅当i∈{1,…,n},满足ui≤vi±ε,ε≥0。

与以往文献的区别在于,本文定义的ε-优胜可以加上ε也可以减去ε:如果加上ε,称该调节度为带宽容度的;如果减去ε,称该调节度为带苛刻度的。

定义2 Pareto-ε无差别。向量u=(u1,…,un)无差别于向量v=(u1,…,un)当且仅当i∈{1,…,n} 满足|ui-vi|≤ε,ε≥0。

定义3 Pareto-ε最优解。对于给定的MOP F(x),解x∈X称为X上的Pareto-ε最优解,当且仅当不存在x′∈X,使得F(x′)沪F(x)。

定义4 Pareto-ε最优解集。对于给定的MOP,其Pareto-ε最优解集P*-ε定义为:

P*-ε={x∈X|开霆x′∈X,使得F(x′)沪F(x)}

由以上定义可以看出,Pareto-ε最优解集是在Pareto最优解集基础上的推广,是一个比Pareto最优解集更大的区域(宽容度下)或者更狭窄的区域(苛刻度下)。

定义5 Pareto-ε前沿。Pareto-ε前沿Pf-ε*定义为:

Pf-ε*={u=F(x)|x∈P-ε*}

Pareto优胜关系与Pareto-ε优胜关系的区别如图2所示。

图片

图2 Pareto与Pareto-ε比较

图中,f1和f2Х直鸨硎MOP的两个子目标,a、b、c、d、e、f、g、h、i分别代表目标空间中的一个区域。显然,优胜于a的是b、e、d区域。而根据本文的定义1、2可知,ε-优胜于a的是c、f、i、h、g区域,b、e、d区域与a是ε-无差别的。a的非劣域正好由L曲线(Pareto优胜下的)所标识的区域向前推进到达U曲线(Pareto-ε优胜下)所标识的区域。

Pareto优胜与Pareto-ε优胜相比,每次找到的Pareto最优解的范围是一条曲线或者曲面,而找到的Pareto-ε最优解的范围是带一定宽度的区域带;基于Pareto-ε优胜比较的搜索步伐要明显快于Pareto优胜比较的。

┑4期 ┩踅晴等:基于Pareto-ε优胜的自适应快速多目标演化算法

┆扑慊应用 ┑30卷

2 PEMOEA算法

2.1 算法设计

由于当前研究MOP大多数是基于演化算法的,为验证Pareto-ε优胜的新定义及其相关策略,本节基于演化算法,给出一类新的基于Pareto-ε优胜的多目标优化算法。算法框架如下:

程序前

begin

t=0;

随机产生初始群体Pt={x1,x2,…,xM};

计算群体中所有个体的Rank函数值;

while (不满足终止条件) do

从Ptе腥〕Rank值最大的前N个个体x1,x2,…,xN进行遗传操作,产生KЦ鲂赂鎏;

Pt′=Pt∪K;

计算Pt′е兴有个体的Rank值并从大到小排列;

取前M个个体形成新一代群体Pt+1;

t=t+1;

endwhile;

输出Ptё魑求出的Pareto-ε最优解集,计算出与PtФ杂Φ哪勘晗蛄考;

end

程序后

2.2 自适应Е诺髡策略

算法采用动态调整策略,通过动态调整ε的值,使算法开始时快速向Pareto真实前沿逼近,但最终又不受ε的影响,也就是让εг谒惴ㄔ诵泄程中逐步回归为0,从而更好地逼近真实的Pareto前沿。本文设计了一个公式,该公式的值可以随着算法执行代数的增加而减少,逐步趋近为0,从而减弱Е弄Ф宰詈蠼獾挠跋,如式(1)所示。

ε=-(gig┆max+l)h+d (1)

其中:gi为算法当前的运行代数;g┆max是最大运行代数;l、r、s分别为调节参数。

3 实验结果和讨论

3.1 实验仿真

实验所使用的物理平台为Pentium 4 CPU 3.0@GHz、512@MB内存,软件平台为VC++6.0和Matalab 7.0。算法分别采用三种搜索策略进行测试:带苛刻度的、带宽容度的、动态调整Е诺摹T谒惴ㄔ诵泄程中只是εУ娜≈挡煌,实施动态调整策略后,也只是增加了对式(1)的计算,并未增加时间复杂度和较大的计算量。因此,本文采用算法终止时所花费的计算代数来衡量算法的性能。从仿真实验中随机选择一组测试数据,测试函数为:

F=(f1(x,y), f2(x,y))(2)

其中:

f1(x,y)=(x-2)2+(y-1)2+2;

f2(x,y)=9x+(y-1)2。

函数的Pareto前沿最终效果如图3所示。

图片

图3 函数Pareto前沿效果

Е湃「髦植煌值时算法的终止代数如表1所示。表2为对ε实行动态调整后的计算结果。图4则给出了g┆max=5B000, l=1,r=-3,s=0.3下的Pf-ε*效果图,其中M为群体大小。

3.2 性能分析

1)Pareto-ε优胜比较策略。实验证明该策略可以增加搜索步长,加快算法的收敛速度,无论是带宽容度的还是带苛刻度的比较策略都可以显著改善收敛性质。在带宽容度的情况下,Е旁酱蟊冉咸跫就越弱,搜索速度就越快,随着ε值的增大算法的收敛性能逐步减弱。在带苛刻度的情况下,虽然比较条件加强了,但是每次成功的移动步长增大了,从而收敛速度也加快了。但两种情况均有不足,在带宽容度的情况下,ε的值增大到一定程度后,解的质量会下降;在带苛刻度的情况下,若ε过大会导致收敛速度过快而早熟,甚至出现比较条件过强而算法无法启动的情况。

2)自适应的ε调整策略。针对以上不足,本文通过动态调整εУ闹,使算法开始时快速向Pareto前沿逼近,最终让Е弄г谒惴ㄔ诵泄程中逐步回归为0,从而更好地逼近真实的Pareto前沿。该策略既可以提高算法的搜索和收敛速度,又可以消除Е弄е刀宰钪战獾闹柿康挠跋臁S氤S玫亩嗄勘晁惴ㄏ啾,这种包括自适应的Е弄У髡策略的PEMOEA算法在处理MOP上具有显著的优越性。

表格(有表名)

表1 不同Е弄取值下的算法终止代数

运算次数ε

00.1-0.1-0.2-0.5-1-1.1-1.2-1.2-1.5-2

1403430359393317377334370370358285

2450485394372392367352344344394305

3437396377382302322353339307329313

4450462394354392344338384377376297

5398389371447354349302316319322332

6438333403349404334337347299322390

7438338404387377341383319301292356

8403338421414348383370358346310320

9425390390434357368327372356363329

10377430435415337358336330348354328

11392366403454367345338350398324327

12421410454456352346318356350305319

13393454442378346340291359342312293

平均运算代数417.3401.6403.6402.6357.3351.8336.8349.5342.8335.4322.6

图片

图4 不同群体规模下的Pf-ε*效果

表格(有表名)

表2 动态调整Е弄У乃惴ㄖ罩勾数

运算ご问ε

-1/(i/m+1)-0.2-1/(i/m+1)-1/(i/m+1)+0.2

1389312333

2375351318

3381368354

4314338370

5411340303

6347337376

7347374319

8345369354

9362352350

10328313330

11336334355

12361336379

13334350362

14332397366

15318348402

16378355360

平均运に愦数353.625348.375351.938

4 结语

本文定义了一种Pareto-ε优胜关系的概念,提出了一种新的自适应ε调整策略,设计了一个新的基于ε-优胜的快速多目标演化算法,分析了ε取值对算法的影响。实验表明,Pareto-ε概念是合理、有效的,加快了算法寻优的速度,可以快速地为决策者提供合理、满意的决策方案。下一步的工作重点在于:进一步探讨ε的取值及其动态变化规律;探索在宽容度和苛刻度下,算法性能得以进一步改进的内在机制。

参考文献:

[1]ELMUSRATI M, EL-SALLABI H, KOIVO H. Applications of multi-objective optimization techniques in radio resource scheduling of cellular communication systems[J]. IEEE Transactions on Wireless Communications, 2008,7(1):343-353.

[2]DASHENG L, TAN K C, GOH C K. A particle swarm algorithm for multiobjective design optimization [J]. IEEE Transactions on Systems Man and Cybernetics, 2007,37(1):42-50.

[3]HO S L, YANG S Y, ZHANG G. A particle swarm optimization-based method for multi-objective design optimizations [J]. IEEE Transactions on Magnetics, 2005,41(5):1756-1759.

[4]刘淳安,王宇平.动态多目标优化的进化算法及其收敛性分析[J].电子学报,2007,35(6): 1118-1121.

[5]石川,李清勇,史忠植.一种快速的基于占优树的多目标进化算法[J].软件学报,2007,18(3): 505-516.

[6]郑向伟,刘弘.多目标进化算法研究进展[J].计算机科学,2007,34(17): 187-191.

[7]VALENZUELA C L.A simple evolutionary algorithm for multi-objective optimization (SEAMO)[C]// CEC’02:Proceedings of the 2002 Congress on Evolutionary Computation.Honolulu:IEEE, 2002: 717-722.

[8]DEB K, MOHAN M, MISHRA S. Evaluating the epsilon-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions[J]. Evolutionary Computation,2005,13(4):501-525.

[9]李密青,郑金华,罗彪,等.一种基于邻域的多目标进化算法[J].计算机应用,2008,28(6):1570-1574.

[10]LAUMANNS M, THIELE L, DEB K,et al. Combining convergence and diversity in evolutionary multiobjective optimization[J]. Evolutionary Computation, 2002, 10(3): 263-282.