基于Pareto熵的多目标粒子群优化算法

软件学报ISSN 1000-9825, CODEN RUXUEW E-mail: jos@http://wendang.chazidian.com

Journal of Software,2014,25(5):1025?1050 [doi: 10.13328/j.cnki.jos.004496] http://wendang.chazidian.com

©中国科学院软件研究所版权所有. Tel/Fax: +86-10-62562563

基于Pareto熵的多目标粒子群优化算法

胡 旺1,2, Gary G. YEN2, 张 鑫1

1

2??(电子科技大学 信息与软件工程学院,四川 成都 610054) (School of Electrical and Computer Engineering, Oklahoma State University, USA)

通讯作者: 胡旺, E-mail: scuhuwang@http://wendang.chazidian.com

摘 要: 粒子群优化算法因形式简洁、收敛快速和参数调节机制灵活等优点,同时一次运行可得到多个解,且能逼

近非凸或不连续的Pareto最优前端,因而被认为是求解多目标优化问题最具潜力的方法之一.但当粒子群优化算法

从单目标问题扩展到多目标问题时,Pareto最优解集的存储与维护、全局和个体最优解的选择以及开发与开采的平

衡等问题亦随之出现.通过目标空间变换方法,采用Pareto前端在被称为平行格坐标系统的新目标空间中的分布熵

及差熵评估种群的多样性及进化状态,并以此为反馈信息来设计进化策略,使得算法能够兼顾近似Pareto前端的收

敛性和多样性.同时,引入格占优和格距离密度的概念来评估Pareto最优解的个体环境适应度,以此建立外部档案更

新方法和全局最优解选择机制,最终形成了基于Pareto熵的多目标粒子群优化算法.实验结果表明:在IGD性能指标

上,与另外8种对等算法相比,该算法在由ZDT和DTLZ系列组成的12个多目标测试问题集中表现出了显著的性

能优势.

关键词: 多目标优化问题;粒子群优化;平行格坐标系统;Pareto熵;自适应参数

中图法分类号: TP301 中文引用格式: 胡旺,Yen GG,张鑫.基于Pareto熵的多目标粒子群优化算法.软件学报,2014,25(5):1025?1050. http://www.jos.

http://wendang.chazidian.com/1000-9825/4496.htm

英文引用格式: Hu W, Yen GG, Zhang X. Multiobjective particle swarm optimization based on Pareto entropy. Ruan Jian Xue

Bao/Journal of Software, 2014,25(5):1025?1050 (in Chinese). http://wendang.chazidian.com/1000-9825/4496.htm

Multiobjective Particle Swarm Optimization Based on Pareto Entropy

HU Wang1,2, Gary G. YEN2, ZHANG Xin1

1

2(School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu 610054, China) (Oklahoma State University, School of Electrical and Computer Engineering, USA) Corresponding author: HU Wang, E-mail: scuhuwang@http://wendang.chazidian.com

Abstract: Due to its concise formation, fast convergence, and flexible parameters, particle swarm optimization (PSO) with the ability to

gain multiple solutions at a run and to approximate the Pareto front of those non-convex or discontinuous multiobjective optimization

problems (MOPs) is considered to be one of the most promising techniques for MOPs. However, several challenges, such as maintaining

the archive, selecting the global and personal best solutions, and balancing the exploration and exploitation, occur when extending PSO

from single-objective optimization problems to MOPs. In this paper, the distribution entropy and its difference of an approximate Pareto

front in a new objective space, named parallel cell coordinate system (PCCS), are proposed to assess the diversity and evolutionary status

of the population. The feedback information from evolutionary environment is served in the evolutionary strategies to balance the

convergence and diversity of an approximate Pareto front. Meanwhile, the new concepts, such as cell dominance and individual density

based on cell distance in the PCCS, are introduced to evaluate the individual environmental fitness which is the metric using in updating

the archive and selecting the global best solutions. The experimental results illustrate that the proposed algorithm in this paper

? 基金项目: 中央高校基本科研业务费专项资金(2672013ZYGX2013J078)

收稿时间: 2013-04-19; 修改时间: 2013-06-18; 定稿时间: 2013-09-09

1026

Journal of Software软件学报 Vol.25, No.5, May 2014

significantly outperforms the other eight peer competitors in terms of IGD on 12 test instances chosen from the ZDT and DTLZ test suites.

Key words: multiobjective optimization problem (MOP); particle swarm optimization (PSO); parallel cell coordinate system (PCCS);

Pareto entropy; adaptive parameter

大多数工程和科学问题都可以归结为多目标优化问题(multiobjective optimization problem,简称MOP),其求解方法一直都是学术界和工程界共同关注的焦点.多目标优化问题通常存在多个彼此冲突的目标,其优化结果为Pareto最优解集.与数学规划方法相比,进化算法因一次运行可得到多个解,且能逼近非凸或不连续的Pareto最优前端,从而被认为是更适合求解多目标优化问题的智能方法.

粒子群优化算法(particle swarm optimization,简称PSO)[1]是由Kennedy和Eberhart在1995年提出的仿生算法,它是受到飞鸟集群活动规律的启发,根据社会学和心理学而建立的群体智能模型.粒子群优化算法是一种具有形式简洁、收敛快速和参数调节机制灵活等优点的进化算法,并且已经成功应用于单目标优化问题,被认为是求解多目标优化问题最具潜力的方法之一.但当粒子群优化算法从单目标问题扩展到多目标问题而形成多目标粒子群优化(multiple objective particle swarm optimization,简称MOPSO)时,新的技术问题随之出现.多目标优化问题的Pareto最优解集特征和粒子群优化算法的快速收敛特征,使得多目标粒子群优化算法面临以下技术挑战:① 维护存储Pareto最优解集的档案,使算法最终输出的Pareto前端能够兼顾收敛性和多样性,这是第二代进化多目标算法的共性问题;② 从群体和个体的Pareto最优解集中分别选举全局最优解(gBest)和个体最优解(pBest),使这两个最优解引导粒子尽最大可能地发现高质量的新解;③ 平衡进化过程中的开采(exploration)和开发(exploitation),使得种群既保持快速收敛的优点,但又尽可能地避免陷入局部Pareto前端或者收敛到单一解.后面两个挑战是多目标粒子群优化算法区别于其他多目标进化算法的特有问题.

本文将根据多目标优化问题和粒子群优化算法的特征,采用近似Pareto前端的分布熵及其变化来估计种群进化状态,并依据这些进化过程反馈信息设计具有动态平衡开采和开发能力的进化策略,形成基于Pareto熵的多目标粒子群优化算法.

为了内容相对独立以及统一本文术语和符号,本文第1节简要介绍多目标优化问题和粒子群优化算法的基本概念.第2节综述与本文内容相关的多目标粒子群优化算法的研究现状和存在的问题.第3节阐述Pareto熵的计算方法以及基于Pareto熵的种群进化状态检测方法.第4节描述本文算法的主要进化策略和完整的算法流程.第5节分析对比实验结果.最后,在第6节中给出全文结论.

1 预备知识

1.1 多目标优化问题

对于最小化无约束连续多目标优化问题(在优化计算领域,最大化问题与最小化问题是一组对偶问题.在无特别说明的情况下,本文所指最优化均为最小化问题),可以定义如下:

min F(x)=[f1(x),f2(x),…,fM(x)]T for all x??D,

其中,x=[x1,x2,…,xD]T?S,D为决策变量个数,S是D维决策空间.一组目标函数f1,f2,…,fM将决策空间映射到目标空间,S????M,M为目标个数,?是M维目标空间.

下面给出与本文使用了Pareto最优的相关定义.

定义1(Pareto占优). 对于任意两个向量u,v??,称u占优v,或称v被u占优,记作u?v,当且仅当

?i=1,2,…,m, ui≤vi??j=1,2,…,m, uj<vj.

定义2(Pareto最优解). 一个解x*??被称为Pareto最优解或非占优解,当且仅当

?x??:x?x*.

定义3(Pareto最优解集和Pareto前端). 所有Pareto最优解的集合PS={x*| ?x??:x?x*}称为Pareto最优 解集.所有Pareto最优解对应目标函数值所形成的区域PF={F(x*)|x*?PS}称为Pareto前端,或Pareto均衡面.

胡旺 等:基于Pareto熵的多目标粒子群优化算法

1027

多目标优化算法的目标是:生成数量尽可能多的Pareto最优解集,同时,尽可能地使对应的Pareto前端分布多样化,包括均匀性(uniformity)和延展性(extensiveness).

1.2 粒子群优化算法

在粒子群优化算法中,一个无质量的粒子i可以由位置向量xi和速度向量vi表示,其中,xi=[xi,1,xi,2,…,xi,D]T? ?D,vi=[vi,1,vi,2,…,vi,D]T??D,i=1,2,…,N,N是种群中的粒子个数,D是决策变量个数.种群中的每一个粒子,在进化过程中根据公式(1)更新速度和位置:

?vi(t?1)??vi(t)?c1r1(pBesti?xi(t))?c2r2(gBest?xi(t)) (1) ?x(t?1)?x(t)?v(t?1)ii?i

其中,t表示迭代次数,?≥0表示惯性权重系数,c1,c2≥0表示加速系数,r1和r2是在[0,1]上均匀分布的随机数, pBesti表示第i个粒子的个体最优解,gBest表示整个群体的全局最优解.

在公式(1)的速度更新方程中，第1部分为粒子当前速度乘以惯性权重进行加速,表示粒子对当前自身运动的信任,依据自身的速度进行惯性运动;第2部分为自我认知部分,表示粒子对自身历史的思考;第3部分为社会认知部分,表示粒子在群体中的信息共享和相互合作.

2 相关研究工作

自Coello等人[2]于2002年提出采用粒子群算法来求解多目标优化问题以来,多目标进化领域中的成功经验被迅速借鉴到多目标粒子群优化算法中,出现了大量的阶段性研究成果,其中以Coello等人[3]采用超网格和变异方法的多目标粒子群优化算法最为经典.Reyes-Sierra[4]对2006年之前的多目标粒子群优化算法做了综述总结,随后,Padhye[5,6]做了一些专题比较研究.关于多目标进化算法的最新综述可参见文献[7,8].

对多目标粒子群优化算法的研究主要集中档案维护、全局最优解选择和种群多样性增加等方面,也有少部分工作对个体最优解选择和粒子变异方面进行了研究.

在外部档案维护策略方面,主要借鉴多目标遗传算法中档案维护的有效策略,如采用聚类、拥挤距离(crowding distance)、自适应超网格(adaptive grid)、-占优(-dominance)、最大化最小适应度(maximin fitness)、?值等形成相应的多目标粒子群优化算法中的档案维护策略[9,10].这些不同的策略都是直接或间接地评估档案中每个个体的密度(拥挤度)或者占优强度.当档案中的Pareto最优解个数超出容量限制时,通常直接将个体适应度较好的新解来更新个体适应度较差的旧解,从而使得Pareto前端具有更好的分布性能.

在全局最优解选择策略方面,基于随机选择、?值、拥挤距离、动态邻居、自适应超网格、聚类、占优树、非占优排序(non-dominated sorting)、Pareto占优、超体积(hyper-volume)、最大化最小适应度、小生境(niche)、综合学习(comprehensive learning)等策略多目标粒子群优化算法被相继提出来[9?12].在这些方法中,大多数通过评估外部档案中的个体密度来选择那些处于相对稀疏区域的Pareto最优解作为全局最优解以降低选择压力,避免收敛到单一解,以及增加Pareto前端的多样性;而另一部分基于“占优”概念的最优解选择策略则偏重算法的收敛性能,但容易导致过高的选择压力而容易收敛到局部极值.

在个体最优解选择策略方面,虽然绝大部分算法为了降低计算开销而仅保留一个Pareto最优解,但仅一个个体最优解不足以描述个体Pareto最优前端.Branke[13]和Abido[14]分别研究了采用个体外部档案保存个体Pareto最优解的方法(类似种群外部档案保存种群Pareto最优解),获得了比单一个体Pareto最优解更好的性能.另外,最大化最小个体间距离和加权和[13]等策略被用来作为选择个体最优解的标准.

在平衡开发与开采策略方面,如果不合理利用粒子群算法快速收敛的优点,则容易导致早熟而陷入局部极值.一些算法从种群角度提出平衡策略,如动态调整种群大小策略[15]和子群策略[16?18];一些算法采用文化进化框架提出平衡策略[19,20];一些算法从粒子运动参数选择角度提出平衡策略,如线性下降惯性权重参数和自适应参数等[21];一些算法从粒子扰动(变异)角度提出平衡策略,自Coello[3]在多目标粒子群算法中提出变异方法后,后续多目标粒子群优化算法几乎都采用变异方法来增强种群多样性;还有一些算法采用混合平衡策略[22,23].

1028

Journal of Software软件学报 Vol.25, No.5, May 2014

但是,多目标粒子群优化算法仍然面临一些技术挑战:

? 一方面,个体适应度评估决定了多目标粒子群优化算法中选择全局最优解和维护档案这两个关键策

略.但当前的个体适应度都是单一度量标准,要么是基于密度的评估来考察个体的多样性潜力,要么是基于Pareto占优关系的评估来考察个体的收敛性潜力.因而导致在维护外部档案时不能兼顾Pareto最优前端的多样性和收敛性,而在选择全局最优解时不能兼顾平衡开发和开采.

? 另一方面,全局最优解频繁更换和快速收敛特征,使得开发与开采的平衡问题在多目标粒子群优化算

法中更为突出:过度地开发将会导致收敛性不足而影响优化精度,而过度地开采将会导致多样性匮乏而陷入局部极值.虽然已经存在自适应单目标粒子群优化算法[24],但多目标问题的Pareto最优解集特征,使得在多目标空间中监测种群进化环境更为复杂.而当前已经存在的多目标粒子群优化算法缺乏种群进化环境的动态监测机制来获取反馈信息,难以决定算法“在何时调节何种进化策略到何种 程度”.

熵在热力学中表示系统混乱状态,而在生态学中表示生物的多样性.本文将通过对目标空间变换来获得Pareto前端的熵,以此来度量多目标粒子群优化算法中种群的多样性,并利用差熵来估计种群的进化状态,从而为算法提供实时的进化环境反馈信息.同时,在变换后的目标空间中评估Pareto最优解的个体密度和格占优强度,为算法中外部档案更新和全局最优解选择提供决策依据.

3 Pareto熵及进化状态检测

本节先介绍Pareto熵的计算方法,包括将采用平行格坐标系统映射目标空间映射的方法和Pareto熵及差熵的定义;然后,根据外部档案更新算法中Pareto熵的变化情况,分析不同进化状态的临界阈值;最后,归纳出种群进化状态的判定条件.

3.1 平行格坐标系统

平行坐标(parallel coordinates)[25]是一种广泛使用的多维数据分析和可视化方法.多目标优化问题的目标向量正是一种多维数据(在进化多目标优化计算社区中,通常将2~3个目标的优化问题称为multi-objective optimization problem,简称MOP,而将4个以上目标的优化问题称为many-objective optimization problem,简称MaOP).受这一方法启发,将存储在外部档案中的多维Pareto前端按照平行坐标方式转化到二维平面中,并将Pareto前端的笛卡尔坐标值映射成整数值坐标,从而多维Pareto前端被转换成一张二维平面网格.对应于笛卡尔坐标系统,在此将这种二维平面网格称为平行格坐标系统(parallel cell coordinates system,简称PCCS).下面采用采用数学形式来描述这种映射方法.

对于Pareto最优解集中第k个非占优解对应的第m个目标值fk,m可以按照公式(2)映射到一个具有K?M个格子(cell)的二维平面网格中: Lk,mmin?fk,m?fm? (2) ??Kmaxmin??ffmm??

其中,?x?是向上取整函数,返回不小于x的最小整数;k=1,2,…,K,K为外部档案在当前迭代中的成员个数;m=1,

maxmin2,…,M,M为待优化问题的目标个数;fm?maxfk,m和fm?minfk,m分别是当前Pareto前端上第m个目标的 kk

最大值和最小值;Lk,m?{1,2,…,K}是fk,m被映射到PCCS中的整数标号,表示第k个非占优解的第m个格坐标分

min量.在特殊情况下,当fk,m?fm时,为了避免Lk,m处于PCCS之外,令Lk,m=1.

任何一个笛卡尔坐标形式的多维数据集(本文仅指Pareto前端上的点数据集)都可以通过公式(2)映射到PCCS中,如图1所示.图1(a)中的7个圆圈表示多目标优化问题测试函数DTLZ2(包含3个目标)的Pareto前端中7个目标向量;图1(b)是由7行3列构成的二维网格,其行数和列数分别对应于图1(a)中向量个数和目标个数,图1(a)中每一个点的每一个坐标分量都被公式(2)映射到图1(b)中对应目标列的某一个格子中,用Pk.fm的形式表示第k个目标向量的第m个格坐标分量.例如,图1(a)中P7点的平行格坐标是(6,2,4),在图1(b)中分别用

胡旺 等:基于Pareto熵的多目标粒子群优化算法

1029

P7.f1=6,P7.f2=2和P7.f3=4表示.为了清晰起见,用点划线连接了图1(b)中同一个目标向量在不同列的格坐标分量.

1.21.00.80.60.40.20.00

0.5

f2

1

1

f1

0.5

f3

765Label number

4321

1

2 3 Objective

(a) 笛卡尔坐标系统中的Pareto前端 (b) 平行个坐标系统中的Pareto前端

Fig.1 A mapping example for Pareto front from Cartesian coordinate system

to parallel cell coordinate system

图1 Pareto前端从笛卡尔坐标系统向平行格坐标系统映射的示例

尤其值得一提的是,K不是一个需要用户指定的参数,而是自动随外部档案中Pareto最优解集的成员个数

maxmin

变化而变化的目标维度分割数.每一个目标列上的格子边长将随fm,fm和K的变化而自动变化.这与

Adaptive Grid[26],-Box[27]和GrEA-grid[28]中需要用户指定每一个维度上的网格划分数(divisions)或盒子边长()不同,PCCS无需依赖用户对待优化多目标问题的领域先验知识.同时,公式(2)在每个维度上的最大值与最小值之间进行了归一化变换操作. 3.2 Pareto熵及其差熵

熵是一种度量微观分布均匀性的方法.在热力学中,熵表示系统混乱状态,而在生态学中熵表示物种的多样性.当存储在外部档案中的近似Pareto前端被映射到PCCS后,可以采用熵来度量近似Pareto前端的分布均匀性,间接地表达当前种群的多样性特征.如果近似Pareto前端发生变化,则会引起PCCS中的对应的格坐标分量重新分布,从而引起熵发生变化.因此,可以采用差熵来表示近似Pareto前端在相邻迭代时刻的熵的变化大小:

? 差熵越大,意味着近似Pareto前端重新分布的范围越大,这可能由于:① 算法生成的新解占优了大量的

maxmin

旧解而引起Pareto前端发生大范围变化;② 新解引起了fm或者fm发生变化而导致第k列上的格

坐标分量重新分布.

? 相反,差熵越小,近似Pareto前端重新分布的范围越小,这是因为在外部档案维护过程中,质量更好(如个

体密度较小)的新解替换了质量较差(个体密度较大)的旧解而引起个别格坐标分量的重新分布. 从而,通过差熵可以推测当前种群的发现新解的潜力,进而估计种群所处的进化状态,如收敛状态、多样化状态和停滞状态.这种进化状态是设计开发和开采进化策略的依据.

由于采用熵来度量近似Pareto前端的分布特征,间接地评估对应的Pareto最优解集的性能.本文为了强调在PCCS中这种分布熵评估的对象是近似Pareto最优解集所对应的近似Pareto前端,故将其称为Pareto熵.

在第t次迭代过程中,外部档案中存储的近似Pareto前端的Pareto熵Entropy(t)可以根据公式(3)计算:

KMCellCellk,m(t)k,m(t) (3) Entropy(t)????log

KMKMk?1m?1

其中,Cellk,m(t)表示近似Pareto前端被映射到PCCS后,落在第k行第m列的格子中的格坐标分量的个数.