相关性粒子群优化模型_申元霞

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

Journal of Software,2011,22(4):695?708 [doi: 10.3724/SP.J.1001.2011.03728] http://wendang.chazidian.com

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

相关性粒子群优化模型

申元霞1,2,3, 王国胤1,2+, 曾传华3

1

2

3? (西南交通大学 信息科学与技术学院,四川 成都 610031) (重庆邮电大学 计算机科学与技术研究所,重庆 400065) (重庆文理学院 计算机学院,重庆 402160)

Correlative Particle Swarm Optimization Model

SHEN Yuan-Xia1,2,3, WANG Guo-Yin1,2+, ZENG Chuan-Hua3

1

2

3(School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031, China) (Institute of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China) (School of Computer Science, Chongqing University of Arts and Sciences, Chongqing 402160, China)

+ Corresponding author: E-mail: wanggy@http://wendang.chazidian.com, http:// http://wendang.chazidian.com

Shen YX, Wang GY, Zeng CH. Correlative particle swarm optimization model. Journal of Software,

2011,22(4):695?708. http://wendang.chazidian.com/1000-9825/3728.htm

Abstract: In the study of particle swarm optimization, propertly using the individual experience and social

sharing information of particles has always been a problem. To solve this problem, this paper analyzes the random

factors in updating the velocity eguation in the view of cognition and creates the intrinsic cognitive relation between

individual experience and social sharing information. First, a correlative particle swarm optimization model is

developed, which uses the Copula function to measure the dependence among random factors. In the new model, the

different correlation structures and degrees of correlation between random factors can denote different strategies,

which are used to process individual experience and social sharing experience. Meanwhile, this paper provides a

flowchart of the correlative particle swarm optimization model, based on Gaussian Copula. Second, the relationship

between the degrees of correlation and population diversity is presented, which shows that the random factors with

positive linear correlation avail to maintain population diversity. Finally, the relationship between the degrees of

correlation and convergence is analyzed and the convergence conditions of the correlative particle swarm

optimization model are provided. Experimental simulations show that the correlation of random factors have a much

greater influence on the performance of the new model, which can greatly improve convergence velocity and

precision when the random factors are a completely positive linear correlation.

Key words: PSO (particle swarm optimizer); correlation; Copula; convergence

摘 要: 在粒子群优化算法中,粒子如何合理地利用自身经验信息和群体共享信息的问题一直未能有效解决.针

对这一问题,基于认知论的观点,对速度更新公式中的随机因子进行了分析,建立了粒子对自身经验信息和群体共享

? 基金项目: 国家自然科学基金(60773113); 重庆市杰出青年科学基金(2008BA2041); 重庆市自然科学基金重点项目

收稿时间: 2009-03-26; 修改时间: 2009-07-06; 定稿时间: 2009-08-26 (2008BA2017)

696 Journal of Software 软件学报 Vol.22, No.4, April 2011

信息认知的内在联系,提出了相关性粒子群优化模型.该模型采用Copula函数去刻画随机因子间的相关结构,而不同的相关结构和相关性程度反映了粒子对自身经验信息和群体共享信息的利用策略的差异,同时给出了基于Gaussian Copula的相关性粒子群优化模型的实现方法.理论上给出了随机因子间相关程度与群体多样性的关系式,表明了当随机因子间正线性相关时有利于维持群体的多样性.证明了随机因子间相关程度与算法收敛性的关系,同时给出了相关性粒子群优化模型的收敛条件.仿真实验结果表明,随机因子间相关程度的水平设置对模型的优化性能有非常显著的影响,当粒子的自身经验信息和群体共享信息被同等利用时,模型表现出优良的整体性能. 关键词: 粒子群优化;相关性;Copula;收敛性

中图法分类号: TP183 文献标识码: A

粒子群优化(particle swarm optimizer,简称PSO)[1]是一种基于群体智能的优化算法,受到人工生命和社会心理学的启发,由美国社会心理学家Kennedy和电气工程师Eberhart于1995年提出,其基本概念源于对鸟群和鱼群捕食行为的研究.由于PSO算法具有概念简单、实现容易、不受问题解空间限制性假设的约束等优点,使其在电力系统、机器学习、模式识别、图像处理等领域得到了广泛的应用[2].PSO算法的第i个粒子在第d维空间的运动方程,可以由一组差分方程来描述,如公式(1)、公式(2)所示:

Vid(t+1)=ωVid(t)+c1r1(t)(Pid(t)?Xid(t))+c2r2(t)(Pgd(t)?Xid(t)) (1)

Xid(t+1)=Xid(t)+Vid(t+1) (2)

其中:Xid和Vid分别代表第i个粒子第d维的位置与速度分量,|Vid|≤Vmax;Pid为粒子个体所经历的历史最佳位置(pbest)分量;Pgd为群体所经历的历史最佳位置(gbest)分量;ω为惯性权重;c1和c2为加速系数;r1和r2为[0,1]之间均匀分布的随机数,称为随机因子.算法的速度更新方程可分成3项:第1项为动量部分,表示粒子以先前速度所进行的惯性运动;第2项为“认知”部分,表示粒子本身的思考;第3项为“社会”部分,表示粒子间的信息共享与相互合作.

PSO算法根据个体粒子和群体粒子的搜索经验向着最优解的方向运动,合理地利用粒子的个体经验信息pbest和群体共享信息gbest为精确有效地寻找最优解提供一条重要途径[3].粒子对这两个信息的利用依赖于下面两个因素:加速系数和随机因子.加速系数c1和c2代表将每个粒子推向其pbest和gbest的统计加速项的权重,加速系数c1和c2通常取值为2[1],Clerc建议,(c1+c2)/2的取值为1.494[4].文献[5]表明,认知参数c1选择大些,社会参数c2选择小些,但当c1+c2≤4时能够得到更好的结果.Ratnaweera[3]提出加速系数随迭代次数线性变化的策略,文献[6]提出加速系数为gbest与pbest之比的非线性函数.文献[7]通过度量多样性来调整加速系数.上述策略从一定程度上改善了PSO算法的全局优化能力,但是只针对于加速系数的调整,而忽略了随机因子对算法性能的影响.目前对随机因子的研究甚少,随机因子r1,r2可以保证微粒群体的多样性和搜索的随机性[1].但在经典PSO算法中,r1,r2的独立性假设使得群体在各自认知及信息共享的部分完全随机地去适应历史,没有加以区别地利用个体经验和群体共享的信息.为了进一步研究粒子对pbest和gbest的利用,对随机因子进行深入的探讨是非常必 要的.

本文从认知论角度对随机因子进行分析,给出随机因子r1,r2的相关性假设,提出基于Copula相关性PSO模型及具体的模型实现方法.之后,从理论上分析随机因子间相关程度与群体多样性之间的关系,剖析相关性PSO模型的内在机理.同时,对随机因子间相关程度与算法收敛性之间的关系进行理论分析,并给出其收敛条件.最后通过仿真实验表明,粒子对pbest和gbest不同的认知策略的相关性PSO模型的优化性能.

1 相关性PSO模型

1.1 随机因子的认知分析

PSO算法的心理学假设是个体在寻求一致的认知过程中记住它自身信念的同时考虑同事们的信念[2]. pbest,gbest分别是粒子根据自身的经验持有的信念和粒子对同伴共享信息持有的信念.随机因子r1和r2刻画了粒

申元霞 等:相关性粒子群优化模型 697

子对持有信念的倾向强度.r1的随机性反映了粒子对持有的自身信念pbest是否会影响算法收敛速度的不确定性;r2的随机性则反映了粒子对共享信念gbest是否为全局最优的不确定性.r1,r2的随机性综合体现了粒子在认知过程中的非理性行为,反映出粒子作为认知主体的情绪[8].加速系数视为粒子对这种情绪的心理效应[8],加速系数的增大或减小是对该情绪的放大或减弱.

粒子对pbest和gbest信息的利用实质上就是对这两个信息进行认知和加工.由上面的分析可知:随机因子r1,r2的独立性假设忽视了粒子对pbest和gbest认知的联系;同时,单纯的加速系数调整也不能体现pbest和gbest在信息加工系统中的内在联系.如何权衡信息加工系统中对pbest和gbest的利用,需要建立粒子对这两个信息持有态度的关联性,即随机因子r1,r2的相关性描述和分析.

1.2 基于Copula相关性的PSO模型

相关性分析是研究事物的相互关系,测定它们联系的紧密程度,揭示其变化的具体形式和规律性的统计方法.在相关性理论中,线性相关系数是分析随机变量间相关关系的一个重要工具.但是近年来却发现,线性相关系数在描述相关性时存在一定的缺陷[9],而Copula函数[10]为相关性的全面分析提供了一条崭新的途径.因此,本文采用Copula来刻画随机因子的相关性.Copula由Sklar于1959年首度引入,在20世纪90年代后期得到了极大的重视并得以迅速发展,在金融风险分析的相关性建模中得到成功的应用[11].

1.2.1 Copula的相关知识

Copula函数实际上是一种将联合分布与其各自的边缘分布连接在一起的函数,称为连接函数.鉴于本文仅讨论两个随机因子r1,r2的相关性,下面给出二元Copula函数的有关定义及定理.

定义1[10]. 一个二元函数C:[0,1]2→[0,1],如果满足以下两个条件:

(1) 对于?t∈[0,1],C(t,0)=C(0,t)=0且C(t,1)=C(1,t)=t;

(2) 对于u1,u2,v1,v2∈[0,1]且u1≤u2,v1≤v2,有C(u2,v2)?C(u1,v2)?C(u2,v1)?C(u1,v1)≥0,

则称函数C为一个Copula.

Copula理论中的奠基性工作就是著名的Sklar定理,它是一切基于Copula的相关性分析的理论支撑. 定理1[10]. 设随机变量X,Y的联合分布函数为H:R2→[0,1],其边缘分布函数分别为FX,FY,则存在一个Copula C:[0,1]2→[0,1],对任意x=(x1,x2)∈R2,有

相反地,如果C:[0,1]2→[0,1]是一个Copula函数,FX,FY分别是随机变量X,Y的分布函数,那么存在一个以FX,FY为边缘分布的联合分布函数H,满足对任意的(u1,u2)∈[0,1]2,有

函数F的值域. 而且,如果FX,FY是连续的,则Copula函数C是唯一的;否则,C在Ran(FX)×Ran(FY)上唯一确定.Ran(F)表示H(x1,x2)=C(FX(x1),FY(x2)) (3) ?1C(u1,u2)=H(FX(u1),FY?1(u2)) (4)

Sklar定理指出Copula函数的存在性,同时给出如何利用联合分布函数求解Copula函数的方法.Copula理论中有3种基本的Copula:Fréchet-Hoeffding下界W(u,v)=max(u+v?1,0),Fréchet-Hoeffding上界M(u,v)=min(u,v)和乘积Copula:Π(u,v)=uv.如果将这3种Copula函数均视为两个[0,1]均匀分布随机变量U,V的联合分布函数,则这3种特殊的Copula函数依次对应着3种特殊的相关关系:完全负线性相关(U=1?V)、完全正线性相关(U=V)和独立.Copula函数与其Fréchet-Hoeffding上、下界之间有如下Fréchet-Hoeffding界值定理:

定理2[10]. 设C为任意给定的一个Copula函数,则对任意u,v∈[0,1]2,有

W(u,v)≤C(u,v)≤M(u,v) (5)

Copula函数有很多类型,不同类型的Copula有不同的特征,可以描述不同的相关结构.在常见的Copula中, Gaussian Copula用于线性相关的结构,Gumbel Copula用于极值分布,而Archimedean Copula和t-Copula用于尾部相关性研究[10].

Gaussian Copula是椭圆Copula簇中的一种,也是一种最常见且应用最为广泛的Copula.利用Sklar定理,可以得出二元Gaussian Copula的定义.

698

Journal of Software 软件学报 Vol.22, No.4, April 2011

定义2[10]. 对于任意(u,v)∈[0,1]2,二元Gaussian Copula可定义为

Cρ(u,v)=Φρ(Φ?1(u),Φ?1(v)) (6)

式中的Φ是标准正态变量X和Y的分布函数;Φρ是二维正态变量X,Y的联合分布函数;Φ?1是Φ的逆函数;ρ是随机变量X和Y的线性相关系数,且?1<ρ<1.ρ 的不同取值反映了随机变量X和Y之间不同的相关特性.当ρ=?1时,令Cρ(u,v)=W(u,v);当ρ=0时,令Cρ(u,v)=Π(u,v);当ρ=1时,令Cρ(u,v)=M(u,v).

1.2.2 模型描述

在经典的PSO算法中,随机因子r1,r2的概率假设为两个独立的[0,1]均匀分布随机变量,模型描述简单.刻画随机因子r1,r2的相关性则是建立相关性PSO模型的关键.由Copula函数的定义可知,二元Copula函数的实质是两个[0,1]均匀分布随机变量的联合分布函数.因此,本文将采用Copula函数描述随机因子r1,r2的相关结构,具体如下:

式(7)后,就可以得出相关性PSO模型的定义. H(r1,r2)=C(r1,r2) (7) 式中的H为随机因子r1,r2的联合分布函数,C为相应的Copula函数.在给出随机因子r1,r2的相关性假设公

定义3. 由公式(1)、公式(2)和公式(7)共同描述粒子运动规律的算法模型称为相关性PSO模型.

在相关性PSO模型中,随机因子r1,r2的不同相关性结构(Copula函数)和同一相关性结构下不同的相关性程度都体现了粒子对pbest和gbest不同的认知策略.随机因子的相关性假设为探求粒子对pbest和gbest的利用平衡问题提供了一条新的途径.

Gaussian Copula是关于线性相关系数ρ的分布函数簇,可以全面反映随机因子r1,r2的线性相关特性.同时,具有Gaussian Copula的相关随机数的生成算法较为简单.本文将采用Gaussian Copula描述随机因子r1,r2的相关结构,对应的线性相关系数ρ刻画了随机因子间的相关程度以及不同的相关系数对应粒子对pbest和gbest的不同的认知策略.

1.2.3 模型实现

在经典PSO算法中,随机因子r1,r2为独立的[0,1]均匀分布随机变量,算法实现方法简单.在相关性PSO模型中,随机因子r1,r2为相关随机变量,模型实现的难点是如何生成两个相关的具有给定Copula函数的随机因子.相关随机变量的生成方法有很多,其中最常用的是直接利用Copula函数C(u,v)的方法.直接利用Copula函数的

(?1)生成方法具有很大的局限性,它需要计算C的偏导Cu(或Cv)及偏导的拟逆Cu(或Cv(?1))[10].由于Copula函数表

达的复杂性,这些计算往往仅能通过数值方法来实现.采用Gaussian Copula描述的相关性PSO模型无需直接借助Gaussian Copula的函数表达,通过线性变换就可以产生具有Gaussian Copula的相关的[0,1]均匀分布随机数.

下面给出基于Gaussian Copula 相关性PSO模型实现的具体流程.

第1步.初始化算法参数;

第2步.产生初始群体,其中所有子粒的位置和速度都是随机的,并给gbest粒子赋予初值;

第3步.群体的进化操作:

1) 给定相关系数ρ,生成相关的[0,1]均匀分布随机变量r1,r2;

(a) 产生两个独立的[0,1]均匀分布的随机变量u1,u2;

(b) 计算x=Φ?1(u1),y=Φ?1(u2).其中,Φ(?)是标准正态分布的分布函数;

(c) 由Cholesky分解获得两个相关的服从正态分布的随机数x,y:x=x,y=ρ x+(1?ρ2)0.5y;

(d) 计算r1=Φ(x),r2=Φ(y),r1,r2就是具有Gaussian Copula Cρ(u,v)的两个随机数;

2) 用公式(1)、公式(2)分别更新粒子的速度和位置;

3) 计算粒子的目标函数;

4) 更新粒子的gbest和pbest;

第4步.算法收敛性判断;

第5步.若未达到结束条件(通常为预设的运算精度或迭代次数),则返回步骤3,开始下一轮迭代计算:否则,

申元霞 等:相关性粒子群优化模型

取当前gbest作为最优解.

699

2 相关性PSO模型的粒子行为分析

2.1 粒子认知策略分析

Gaussian Copula是一类特殊的椭圆Copula.由Gaussian Copula的定义2可知,Cρ(r1,r2)=Cρ(r2,r1),即对于不同的相关系数ρ而言,随机因子r1,r2在矩形区域[0,1]×[0,1]中的取值是关于对角线r1=r2对称的,且随着相关系数

ρ∈[?1,1]的增大,随机因子r1,r2的取值在对角线r1=r2附近的聚集程度有所增加.特别地,当ρ=1时,随机因子r1,r2

的取值完全落在对角线r1=r2上.图1给出了具有Gaussian Copula且相关系数分别为?1,?0.4,?0.8.0.4,0.8和1的随机因子r1,r2的取值分布散点图.该图反映了随机因子r1,r2的分布关于对角线r1=r2的对称性以及不同相关系数所对应的r1,r2的取值在对角线r1=r2附近的聚集程度.

对于基于Gaussian Copula的相关性PSO模型,随机因子r1,r2的取值关于对角线r1=r2的对称性反映了粒子在整个寻优过程中对极值信息pbest和gbest利用的均衡性.随着相关系数ρ的增加,随机因子r1,r2的取值在对角线

r1=r2附近的聚集程度有所提高,这进一步反映了粒子在局部寻优过程中对极值信息pbest和gbest的均衡利用程度随相关系数ρ的增加而增大.

1.0 0.5

0.0

0 0.5 1

r2 1.00.50.0r1 r1

ρ=?1

1.00.50.0r1

ρ=?0.8

1.00.50.0r1

ρ=?0.4

0 0.5 1

r2 0 0.5 1

r2

ρ=0.8

1.00.50.0r1

ρ=0.8

1.00.50.0r1

ρ=1

0 0.5 1

r2 0 0.5 1

r2 0 0.5 1

r2

Fig.1 Bivariate scatter diagram of Gaussian Copula with different correlation coefficients

图1 不同相关系数的Gaussian Copula二维随机变量的散点图

2.2 群体多样性分析

群体多样性是用来表征群体内个体特征的差异性,是刻画群体进化过程中的一个重要特征.其实质是粒子的位置相对于某个几何中心的离差程度,几何中心的选取通常是重心

.Shi给出了一种广义的群体多样性计算公式[12]:

N

1ND

[Xid(t)?Xd(t)]2 (8) div(X(t))=∑∑NDi=1d=1

其中,d=∑i=1Xid(t)N是所有粒子位置X(t)重心的d维分量,N是种群规模,D是待求解问题的维数.

为了研究相关系数ρ对粒子群体多样性的影响,本文在当前状态下考察粒子群体下一时刻的群体多样性的变化.t+1时刻,群体多样性的表达式为

N

div(X(t+1))=

1ND

[Xid(t+1)?Xd(t+1)]2 (9) ∑∑NDi=1d=1

其中,d+=∑i=1Xid(t+1).此时,各个粒子在t时刻以及t时刻以前的位置和速度等信息都是已知的,粒