基于交叉和变异的多目标粒子群算法
收稿日期:2010-06-17;修回日期:2010-08-26。 基金项目:国家863计划项目(2008AA04A105);广东省自然科学基金资助项目(9451806001002294);贵州教育厅社科项目(0705204);遵义科技攻关项目([2008]21号)。
作者简介:刘衍民(1978-),男,黑龙江牡丹江人,讲师,博士研究生,主要研究方向:运筹学、进化计算; 牛奔(1980-),男,安徽全椒人,博士,主要研究方向:进化计算; 赵庆祯(1943-),男,山东利津人,教授,博士生导师,主要研究方向:运筹学、进化计算、物流工程。
文章编号:1001-9081(2011)01-0082-03
do:i 10.3724/SP .J .1087.2011.00082
基于交叉和变异的多目标粒子群算法
刘衍民1,2
,牛 奔3
,赵庆祯
2
(1.遵义师范学院数学系,贵州遵义563002; 2.山东师范大学管理与经济学院,济南250014;
3.深圳大学管理学院,广东深圳518060)
(yanm i n7813@163.co m )
摘 要:为了保证粒子群算法求得的非劣解尽可能接近真实的P areto 前沿并保持多样性分布,提出一种基于交叉和变异的多目标粒子群算法(C MM O PS O )。在C MMO PSO 中,首先识别P areto 前沿的稀疏部分包含的粒子,并对这
些粒子进行交叉操作以增加多样性分布;接着对远离Pareto 前沿的粒子进行变异操作,以提升粒子向真实的Pa reto 前沿飞行的概率。在基准函数的测试中,结果显示C MMO PS O 比其他算法有更好的运行效果。
关键词:多目标优化;粒子群算法;交叉;变异;外部存档
中图分类号:T P301.6 文献标志码:A
M ulti objective particle s w arm optim ization based on crossover and mutati on
LIU Y an m i n 1,2
,N IU Ben 3
,ZHAO Q ing zhen
2
(1.De part m e n t of M a t h e m atics ,Zuny iNor m al Colle g e ,Zunyi Gu i zh ou 563002,Ch i na;
2.S c h ool of M anage m e n t and E cono m ics ,S hand ong N or m al Universit y ,Jinan Shand ong 250014,Ch i na;
3.Colle g e o f M anag e m e n t ,Shenzh e n Un i versit y,Shenzh e n G uangdong 518060,C hina )
Abstract :In order to m i n i m i ze t he distance o f the P areto front produced by P arti c le S w ar m O pti m ization (PSO )w ith respec t to the globa l Pareto front and m ax i m i ze t he spread of so l u ti ons found by PSO,a mu lti ob j ec tive particle s war m
op ti m ization based on cro ssover and m utation (C MMO PSO ).In t he C MM OPSO,firstl y ,the nu m ber o f particle i n sparse part of Pareto front w as defi ned and the crossover operator w as e mp l oyed t o i ncrease t he d i versity of the nondo m i nated so luti ons ;next ,the m utation opera tion w as used for t he particles fa r a w ay fro m P are t o front to i m prove t he probability to fly to Pa reto front .In bench m ark functi ons ,C MM OPSO ach i eves better so l utions than other algorith m s .
K ey words :m ulti ob jecti ve opti m iza ti on ;P article Sw ar m Opti m ization (PSO );cro ssover ;mu tati on ;external arch i v e
0 引言
粒子群算法(P article Sw ar m Op ti m ization ,PSO )[1]是一类基于群体智能的随机优化算法。该算法操作简单,收敛速度快。鉴于此,许多学者提出将粒子群算法来处理多目标问题(M u lti ob j ective PSO,M O PS O )。Coell o 等人[2]提出通过合并Pa reto 占优的概念,并采用外部存档控制器来存储和决定每一代中哪些粒子将会成为非劣解的成员,这些成员被用来引导其他粒子的飞行。在文献[3]中,作者提出了动态人口多种群M O PS O,这种算法应用了自适应局部外部存档来提升每个种群的多样性,进而提升每个粒子收敛到真实P are t o 前沿的能力。Y en 等人
[4]
提出了一种类似于文献[3]的动态多
群MO PS O 算法,通过分配一定数量的子群来保证算法在运行过程中收敛到真实的P are to 前沿。这些研究都基于下述两个目标:1)所得非劣解集尽可能接近真实的Pa reto 前沿;2)所得非劣解集要尽可能保持多样性分布。因此,为了更好地实现这两个目标,在文献[2]提出的多目标粒子群算法基础上,提出一种基于交叉和变异的多目标粒子群算法(M ulti O bjective PSO based on Cro ssover and M u tati on ,C MM O PS O )来提升粒子群算法求解多目标问题的能力。
1 基本粒子群算法
K ennedy 等人[1]在1995年首先提出粒子群算法,每个粒子根据自身的最优历史位置和全局最优的粒子位置共同调整
飞行方向。通常来说,根据粒子邻居拓扑结构的不同,PSO 分为局部版本粒子群算法(L oca l Partic l e Swa r m O pti m ization ,LPSO )和全局版本粒子群算法(G l oba l P article Sw ar m O pti m iza ti on ,GPSO )。在LPSO 算法中,每个粒子的邻居是由与它直接相连的那些粒子构成;而GP S O 算法中,每个粒子的邻居由群体中除自己外的所有粒子构成。这样,GPSO 和LPSO 算法的粒子速度和位置更新方程可分别描述为:
v i (t +1)=v i (t)+ 1 r 1(p i (t)-x i (t))+ 2 r 2(p g (t)-x i (t))x i (t +1)=x i (t)+v i (t +1)
(1)
v i (t +1)=v i (t)+ 1 r 1(p i (t)-x i (t))+ 2 r 2(p neighbo r i (t)-x i (t))x i (t +1)=x i (t)+v i (t +1)
(2)其中:p i (t)表示在迭代时刻t ,粒子i 所经历的最好位置;p g (t)表示在迭代时刻t ,群体中的粒子所经历的最好位置,称做粒子的 社会部分!;p neighbo r i (t)表示在迭代时刻t ,粒子i
第31卷第1期
2011年1月
计算机应用
Journal o f Computer A pp licati ons
V o.l 31N o .1
Jan .2011
的邻居中所有粒子经历的最好位置。这两种算法从本质上是相同的,只是在粒子速度更新时,学习样本的选择范围不同。
2 基于交叉和变异的MOPS O
2.1 外部存档
粒子群算法在每一次迭代都产生一组非劣解。因此,在算法运行中,采用外部存档来存储每一代产生的非劣解。随着迭代的进行,每一代所产生的非劣解用来更新外部存档;同时,为了保证产生更加接近真实P areto 前沿的非劣解,采用网格技术对外部存档中的非劣解进行筛选,并采用自适应网格策略控制外部存档规模。对于网格的确定方法,请参照文献[2]。
PSO 算法在求解单目标问题时,每次迭代产生一个全局最优粒子;而在求解多目标问题时,在每次迭代过程中,产生一组非劣解。在众多的非劣解中,无法确定哪一个非劣解是最优的。对于如何在一组非劣解中选取一个最优的,这里采用自适应网格和轮盘赌选择策略[2]在外部存档中选择非劣解。
2.2 P are to 前沿稀疏部分的确定
对于任何一种给定的多目标进化算法,使所得非劣解集尽可能保持多样性分布,即所得非劣解尽可能地均匀分布在Pa reto 前沿是研究目标之一。但是,由于粒子群算法是通过种群间相互学习来调整粒子的飞行方向,这样,在某种情况下会出现大量的粒子集聚一起,导致分布不均匀,出现Pa reto 前沿的稀疏部分,如图1所示。因此,识别P areto 前沿的稀疏部分,并在稀疏部分产生新的非劣解是提升非劣解分布均匀性的一种有效途径。式(3)、(4)给出了P areto 前沿的
稀疏部分识别策略。
图1 Pareto 前沿稀疏部分
S ={a |a =f ind (d i > d ),i ?rep }(3)P ={x |x =unique(S,S )}
(4)
其中:S 表示Pareto 前沿稀疏部分;re p 表示外部存档;d i 表示任意相邻两点间的欧氏距离; 控制稀疏部分个数的参数,本文提出的算法中 =2.8;d 表示所有d i 的平均值;find ( )函数表示寻找元素对应的位置;P 表示稀疏点集合;S,S 表示S 元素的端点;unique( )表示寻找所有S,S 端点中的不同元素。
通过对稀疏点进行扰动产生用于交叉操作的粒子,这样可以保证P areto 前沿的稀疏部分有更多的粒子产生,进而提升多样性分布。
y 1ij
=x ij +d q r -d
2q
(5)y 2ij =x ij -
d q r -d
2q
(6)
其中:y 1ij 和y 2ij 分别表示由稀疏点x ij 通过扰动因子q 产生的两
个粒子;i 表示粒子;j 表示维数;r 表示均值为0、方差为1的高
斯白噪声。注意如果稀疏点个数为N,经过式(5)、(6)扰动后,稀疏点个数变为2N 。2.3 模拟二进制交叉
在文献[5]中,作者证实了模拟二进制交叉在帮助种群跳出局部最优解(类似于多目标问题中的伪Pareto 前沿)起到了积极的作用。因此,对稀疏点粒子进行模拟二进制交叉以产生更多的粒子来提升多样性分布。该过程如下:
x 1,k =1
2
[(1- k ) x r ,1,k +(1+ k )x r ,2,k ]
x 2,k =1
2
[(1+ k ) x r ,1,k +(1- k )x r ,2,k ]
(7)
其中:x r ,i,k 是随机选择的粒子,x i ,k (i =1,2)表示在SBC 后新产生的粒子的第k 维, k (#0)通过式(8)产生。
k =
(2u)1/(!c +1),
u <0.5
[2(1-u )]1/(!c +1),u #0.5
(8)
其中:u 是(0,1)内的随机数;!c 定义新产生的粒子的分布指数,它等于粒子规模。2.4 多项式变异
当一个种群停止进化时(即当种群中所有粒子的速度几乎等于零时),这将导致整个种群陷入局部最优解,而在多目标情况下,整个种群将陷入伪Pa reto 前沿。文献[6]提出通过变异来产生新的全局最优粒子使得当前种群跳出局部最优状态。因此,为了使所得非劣解集尽可能接近真实的Pareto 前沿,对远离P areto 前沿的非劣解进行多项式变异,在C MMO PS O 中,远离P are t o 前沿的定义如下:
p ={m |m =f ind (l i >l),i ?rep }
(9)
其中:p 表示远离P areto 前沿的所有非劣解集合;r e p 表示外部存档;l i 表示每个非劣解和最接近的P are to 解间的欧氏距离;l 表示所有l i 的平均值;find( )函数表示寻找元素对应的位置。图2给出了远离P areto 前沿的非劣解与最接近Pareto 解间的示例图。
图2 非劣解与最接近Pareto 解间距离
确定远离Pa re t o 前沿的所有非劣解后,要对这些非劣解进行变异,这里采用文献[7]提出的多项式变异,变异过程如下:
x i (t +1)=x i (t)+(x U i (t)-x L i (t)) ?i
(10)
其中:x i (t)表示在迭代时刻t ,当前粒子i 的位置;x U i (t)和x L i (t)分别表示x i (t)的上界和下界;?i 是粒子i 的扰动项,它的生成见式(11)。
?k
=(2r k )1
!m +1-1,r k <0.51-[2 (1-r k )]
1
!m +1
,
r k #0.5
(11)
其中:r k 表示(0,1)内均匀分布的随机数;!m 变异分布指数,
它等于人口规模。
2.5 C MMO PS O
综合上述策略,采用全局版本粒子群算法。这样,粒子的学习样本包括两部分:向自身的最优位置学习和向全局最
83
第1期刘衍民等:基于交叉和变异的多目标粒子群算法
优的粒子位置学习。这样粒子的进化方程由式(12)、(13)来确定:
v i (t+1)=v
i
(t)+
1
r
1
(p
i
(t)-x
i
(t))+
2
r
2
(r e p
h
(t)-x
i
(t))(12)
x i (t+1)=x
i
(t)+v
i
(t+1)(13)
其中:r e p
h (t)表示在迭代时刻t选取的全局最优粒子,
1
=
2
=2。
算法1给出了C MM OPSO流程。
算法1
I n iti alize pos i ti on s and ass oci ated vel oci ti es of all parti cles.
V m ax=0.25(X max-X m i n).
Set t he curren t parti cle pos iti on as pb est.
W h il e(fitcoun t F i nd sparse part i n Pareto fron t i n ter m s of Eq.(3)(4). C onstru ct adap tive gri d. P roduce t h e parti cles u s ed f or cross over fro m s parse part. P roduce t h e parti cles u s ed f or m utati on. For each parti cle(i=1:ps) S el ect an exe m plar fro m external arch i ve Em p l oy crossover f or s parse part of Pareto fron t. Em p l oy mu tati on f or t he particl es far a w ary fro m Pareto fron t using E q.(10). Updat e vel ocit y and pos i ti on us i ng Eq.(12)(13). E val uate t he fitness val u es of the cu rrent particl e.i Updat e t h e pb est of each parti cle. End f or Update external arch i ve by Paret o dom i n ace. Output res u lts E nd w h il e 3 CMMOPSO性能测试与分析 3.1 检测函数及算法的参数设置 与本文提出的C MM O PS O进行比较的算法为:N S GA II[8]算法和MO PSO[2]算法。所选取检测函数为:ZDT1、ZDT2和ZDT3,它们的表达式收集在文献[3]中,这三个检测函数分别用来测试算法解决Pareto最优前沿是凸、非凸和不连续的优化问题的能力。这里,每个检测函数含有两个目标函数和30维变量。所有算法的迭代次数为200,存档规模为100,粒子规模为100,其他参数设置与各种算法提出时所用参数设置一致。 3.2 实验结果及其分析 仿真实验在型号为T h i nkP ad SL400电脑上应用M atlab 7.7.0(R2008b)软件完成。实验中,每个函数独立运行20 次。图3给出了各种算法所获得P are to前沿图,其中f 1和f 2 表示目标函数值。可以看出C MM OPSO得到的P areto前沿比M O PS O和N S GA II算法更要接近真实的P areto前沿,表明C MMO PS O处理这类多目标问题要优于其他几种算法。 同时,为了证明算法的有效性,应用分布指标(#)[8]和收敛性指标(?)[2]来评价不同算法的运行,其中?越小表示算法的收敛性越好;#越小意味着所得非劣解有较好的分布。表1给出了不同算法在20次独立运行中的结果,其中,B表示运 行最好的结果,W表示运行最差的结果,M表示平均值。从表1可以看出C MM OP S O在分布指标和收敛性指标方面要优于其他算法,M OPSO和N SGA II几乎有相同的运行特征。 图3 各种算法所得Pareto前沿 表1 不同算法评价指标 算法 CMMOPSO ?# M OPSO ?# NSGA II ?# ZDT1 B0.01040.320.0690.560.0710.59 W0.04860.530.2160.890.2340.87 M0.03250.410.0890.720.0860.66 ZDT2 B0.01280.360.1260.630.1980.63 W0.04630.690.6030.830.6190.81 M0.02930.430.3810.740.3520.69 ZDT3 B0.01270.310.1560.490.1140.43 W0.02350.460.3170.810.2860.74 M0.01790.380.2150.630.1850.56 4 结语 考虑到所有的多目标进化算法都要满足所得非劣解集尽可能接近真实的Pa re t o前沿并且所得非劣解集要尽可能保持多样性分布,提出一种基于交叉和变异的多目标粒子群算法(C MMO PS O)。该算法通过对Pareto前沿的稀疏部分进行交叉操作以提升多样性分布,并用过多项式变异操作增加粒子向真实的Pa reto前沿飞行的概率。通过典型测试函数对C MM OP S O在处理P areto前沿为凸、凹、不连续的目标空间中解分布不均匀问题进行了测试,结果表明C MM OPSO是一种处理多目标问题的有效算法。 参考文献: [1] KENNEDY J,EBERHART R C.Particl e s w ar m op ti m iz ati on[C]// P roceed i ngs of IEEE I n ternati onal C on feren ce on N eural Net w ork s. W ash i ngt on,DC:I EEE,1995:1942-1948. (下转第117页) 84 计算机应用第31卷 [0,1]?R ?[0,0]?A ?[0,0]的所有请求,在删除R 1前 这些请求的结论为D eny ,删除R 1后属于S ?[0,0]?R ?[0,0]?A ?[0,0]的请求结果仍然为D eny ,但属于S ?[1,1]?R ?[0,0]?A ?[0,0]的请求结果变为P er m it 。输出删除规则R 1变更分析结果如下:S ?[0,0]?R ?[0,0]?A ? [0,0]% D eny V S D eny S ?[1,1]?R ?[0,0]?A ? [0,0]% D eny V S P erm it 3.2 规则插入 根据定理2,计算规则插入的影响类似于规则删除。若策略P 包含n 条规则&R 1,R 2,?,R n (,假设插入规则R 得到策略P )&R 1,?,R i-1,R i+1,?,R n (,为计算插入的影响,首先计算规则R 在P )中的有限集合。然后构造&R i+1,R i+2,?,R n (类似如图1的树形结构(&R i+1,R i+2,?,R n (也可以构成一个独立策略,因为最后一条规则匹配所有前面规则未曾匹配的请求)。最后遍历树形结构检查哪一个路径修改前后的结论不同然后得知变更分析结果。 3.3 规则修改 根据定理3,计算策略中规则R i 修改成R i )后的变更影响必需先计算R (R i ,P )?R (R i ),P ))和R (R i ,P )-R (R i ),P ))。接下来讨论怎么计算它们。给定两个匹配集合R a 和R b 分别可表示成两个有效集合{e 1,e 2,?,e m }和{%1,%2,?,%n }。可得: R a ?R b =+m i=1+l j=1 (M (e i )?M (%j )) 其中M (e i )?M (%j )可由(Se i ?S %j )?(R e i ?R %j )?(A e i ?A %j )求得,可以看做是规则e i 和%j 在主体、资源和动 作分别的交集。 给定两个匹配集合R a 和R b 分别可表示成两个有效集合{e 1,e 2,?,e m }和{%1,%2,?,%n },R ,为完整性说明规则。R a -R b 为策略{e 1,?,e m ,%1,?,%n ,R ,}中每一个e i 的有效集合的并集。 所以规则修改的影响可以用以下步骤计算。1)计算R i 在P,R i )在P )中的有效集合。 2)假如R i 和R i )有相同结论,直接跳到第3)步。若结论不同,计算R (R i ,P )?R (R i ),P )),如果R (R i ,P )?R (R i ),P ))? ,输出变更分析结果。 3)计算R (R i ,P )-R (R i ),P ))。4)由规则&R i+1,?,R n (构造树图。遍历树图,检查每个 路径的结论是否合变更前冲突,若有则输出变更分析结果。 4 算法实现 算法采用Java 语言实现了一个原型系统,策略评估引擎采用S UN PDP ,设置策略导入功能以及统一变更输入界面,针对规则删除、插入、修改的变更分析算法采用独立的功能模块,并把结果输出到统一界面。测试平台采用一台2.56GH z 的AM D 双核CPU 、8GB 内存并运行W i ndo w s Se rver 2003操作系统的PC 机。对一个有1000条规则的策略中一条规则的变更分析运行20次,平均耗时100m s 。 5 结语 本文分析了XAC M L 策略定制中变更影响的各种可能 性,归纳出变更分析理论基础,并提出规则删除、规则插入和规则修改的变更分析算法,对可能的变更结果做出预测输出分析结果,为系统管理员提供直观的决策参考,降低了策略定制中出现安全纰漏的几率。相关方法结论还可以应用到其他安全隐私策略语言。实验证明本文算法在保证正确准确情况下耗时短,可应用于各种策略语言。参考文献: [1] ANDERSON A .A co m pari son of t w o privacy policy l anguages :EP AL and XACM L [C ]//Proceed i ngs of the 3rd ACM W ork s hop on S ecu reW eb Servi ces .Ne w York :ACM,2006:53-60. [2] 王雅哲,冯登国.一种XAC M L 规则冲突及冗余分析方法[J ]. 计算机学报,2009,32(3):516-530. [3] P I ETRO M,BRUNO C,S W A M I NATHAN S,et al .XAC M L policy i ntegrati on algorit hm s [J ].AC M Transactions on In f or m ati on and Syste m Secu rit y ,2008,11(1):1-29. [4] RYDER B,T IP F .Ch ange i m pact an al ysis for ob j ect ori en t ed pro gra m s [C ]//Proceed i ngs of t he 2001AC M SI GPLAN S I GSOFT W ork s hop on Progra m Anal ysis for Soft w are Tools and Engi n eeri ng .Ne w York :ACM,2001:46-53. [5] LI U A,CHEN F ,HW ANG J ,e t al .Xengi n e :A fast and scalab l e XACM L policy eval u ati on engi n e [C ]//Proceedings of t he 2008ACM SI GM ETRICS In ternati onal C onferen ce on M eas ure m ent and M odeli ng of Co m puter Syste m s .Ne w York:ACM,2008:265-276.[6] L I U A ,GOUD A https://www.wendangku.net/doc/db13019342.html,p lete redundancy det ecti on i n fi re w alls [C ]//Proceed i ngs of t he 19th Annual IFIP Conference on Dat a and App li cati on s Securit y .B erli n:Spr i nger Verl ag ,2005:196-209. (上接第84页) [2] COELLO C A C , P UL I DO G T,LECHUGA M S .H and li ng m u l ti p l e ob jecti ves w it h parti cle s w ar m op ti m iz ati on [J].IEEE Tran s acti ons on Evol u ti onary Co m putation ,2004,8(3):256-279. [3] LEONG W F ,YEN G G.PSO based m u lti ob j ecti ve opti m izati on w ith dyna m i c popu l ation size and adap tive l ocal arch i ves[J].IEEE T ransacti ons on Syste m s ,M an , and Cyb ern eti cs ...Part B:C ybernetics ,2008,38(5):1270-1293. [4] YEN G G , LEONG W F .Dyna m i c m u lti p le s w ar m s i n mu lti ob j ecti ve parti cle s war m opti m i zati on [J ].IEEE T ran s acti ons on S yste m s , M an , and Cybern eti cs ...Part A: Sys t e m s and Hum an s ,2009,39(4):890-911. [5] M ARTI NEZ S Z ,COELLO C A C.H yb ri d i z i ng an evoluti onary al gori thm w i th m athe m atical p rogra mm i ng techn i ques for mu lti ob j ecti ve opti m i zati on [C ]//Proceedings of the 10th Annual Geneti c and E vol u tionary Co m putati on C onference .Ne w York:ACM,2008:769-770. [6] STACEY A ,J ANC IC M,GRUNDY I .Parti cle s w ar m op ti m iz ati on w it h m utation [C ]//CEC 03:Proceedi ngs of I EEE C ongress on E voluti onary C o m pu tati on .W as h i ngton ,DC:IEEE,2003:1425-1430.[7] DEB K, GOYAL M. A co m b i ned gen eti c adap tive search (Gene AS )for engi n eeri ng design [J ].Co m puter Science and In f or m atics ,1996,26(4):30-45. [8] DEB K,PRATAP A ,AAGR WAL l S , et a l .A fast and eli tist mu ltiob j ecti ve gen eti c algorit hm:NSGA II [J].IEEE T ransacti on s on E vol u ti onary Co m putati on ,2002,6(2):182-197. 117第1期王强等:隐私安全策略中的变更影响分析 基本粒子群算法的原理和matlab程序 作者——niewei120（nuaa） 一、粒子群算法的基本原理 粒子群优化算法源自对鸟群捕食行为的研究，最初由Kennedy和Eberhart提出，是一种通用的启发式搜索技术。一群鸟在区域中随机搜索食物，所有鸟知道自己当前位置离食物多远，那么搜索的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。PSO 算法利用这种模型得到启示并应用于解决优化问题。PSO 算法中，每个优化问题的解都是粒子在搜索 空间中的位置，所有的粒子都有一个被优化的目标函数所决定的适应值，粒子还有一个速度值决定它们飞翔的方向和距离，然后粒子群就追随当前的最优粒子在解空间中搜索。 PSO 算法首先在给定的解空间中随机初始化粒子群，待优化问题的变量数决定了解空间的维数。每个粒子有了初始位置与初始速度。然后通过迭代寻优。在每一次迭代中，每个粒子通过跟踪两个“极值”来更新自己在解空间中的空间位置与飞翔速度。第一个极值就是单个粒子本身在迭代过程中找到的最优解粒子，这个粒子叫做个体极值。另一个极值是种群所有粒子在迭代过程中所找到的最优解粒子，这个粒子是全局极值。上述的方法叫全局粒子群算法。如果不用种群所有粒子而只用其中一部分作为该粒子的邻居粒子，那么在所有邻居粒子中的极值就是局部极值，该方法称为局部PSO 算法。 速度、位置的更新方程表示为： 每个粒子自身搜索到的历史最优值p i ，p i=(p i1,p i2,....,p iQ)，i=1,2,3,....,n。所有粒子搜索到的最优值p g，p g=(p g1,p g2,....,p gQ)，注意这里的p g只有一个。 是保持原来速度的系数，所以叫做惯性权重。 是粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识，所以叫“认知”。通常设置为2。 是粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识，所以叫做“社会知识”，经常叫做“社会”。通常设置为2。 是[0,1]区间内均匀分布的随机数。 是对位置更新的时候，在速度前面加的一个系数，这个系数我们叫做约束因子。通常设 置为1 。 粒子群优化算法综述 摘要：本文围绕粒子群优化算法的原理、特点、改进与应用等方面进行全面综述。侧重于粒子群的改进算法，简短介绍了粒子群算法在典型理论问题和实际工业对象中的应用，并给出了粒子群算三个重要的网址，最后对粒子群算做了进一步展望。 关键词；粒子群算法；应用；电子资源；综述 0.引言 粒子群优化算法]1[(Particle Swarm Optimization ，PSO)是由美国的Kenned 和Eberhar 于1995年提出的一种优化算法,该算法通过模拟鸟群觅食行为的规律和过程，建立了一种基于群智能方法的演化计算技术。由于此算法在多维空间函数寻优、动态目标寻优时有实现容易，鲁棒性好，收敛快等优点在科学和工程领域已取得很好的研究成果。 1. 基本粒子群算法]41[- 假设在一个D 维目标搜索空间中，有m 个粒子组成一个群落，其中地i 个粒子组成一个D 维向量，),,,(21iD i i i x x x x =，m i ,2,1=，即第i 个粒子在D 维目标搜索空间中的位置是i x 。换言之，每个粒子 的位置就是一个潜在的解。将i x 带入一个目标函数就可以计算出其适 应值，根据适应值得大小衡量i x 的优劣。第i 个粒子的飞翔速度也是一个D 维向量，记为),,,(21iD i i i v v v v =。记第i 个粒子迄今为止搜索到的最优位置为),,,(21iD i i i p p p p =，整个粒子群迄今为止搜索到的最优位置为),,,(21gD gi g g p p p p =。 粒子群优化算法一般采用下面的公式对粒子进行操作 )()(22111t id t gd t id t id t id t id x p r c x p r c v v -+-+=+ω (1) 11+++=t id t id t id v x x (2) 式中，m i ,,2,1 =；D d ,,2,1 =；ω是惯性权重， 1c 和2c 是非负常数， 称为学习因子， 1r 和2r 是介于]1,0[间的随机数；],[max max v v v id -∈，max v 是常数，由用户设定。 2. 粒子群算法的改进 与其它优化算法一样PSO 也存在早熟收敛问题。随着人们对算 法搜索速度和精度的不断追求，大量的学者对该算法进行了改进，大致可分为以下两类：一类是提高算法的收敛速度；一类是增加种群多样性以防止算法陷入局部最优。以下是对最新的这两类改进的总结。 2.1.1 改进收敛速度 量子粒子群优化算法]5[:在量子系统中，粒子能够以某一确定的 概率出现在可行解空间中的任意位置，因此，有更大的搜索范围，与传统PSO 法相比，更有可能避免粒子陷入局部最优。虽然量子有更大的搜索空间，但是在粒子进化过程中，缺乏很好的方向指导。针对这个缺陷，对进化过程中的粒子进行有效疫苗接种，使它们朝着更好的进化方向发展，从而提高量子粒子群的收敛速度和寻优能力。 文化粒子群算法]6[:自适应指导文化PSO 由种群空间和信念空间 两部分组成。前者是基于PSO 的进化，而后者是基于信念文化的进化。两个空间通过一组由接受函数和影响函数组成的通信协议联系在一起，接受函数用来收集群体空间中优秀个体的经验知识；影响函数利用解决问题的知识指导种群空间进化；更新函数用于更新信念空间； 主函数源程序（main.m） %------基本粒子群优化算法（Particle Swarm Optimization）-----------%------名称：基本粒子群优化算法（PSO） %------作用：求解优化问题 %------说明：全局性，并行性，高效的群体智能算法 %------初始格式化--------------------------------------------------clear all; clc; format long; %------给定初始化条件---------------------------------------------- c1=1.4962;%学习因子1 c2=1.4962;%学习因子2 w=0.7298;%惯性权重 MaxDT=1000;%最大迭代次数 D=10;%搜索空间维数（未知数个数） N=40;%初始化群体个体数目 eps=10^(-6);%设置精度(在已知最小值时候用) %------初始化种群的个体(可以在这里限定位置和速度的范围)------------for i=1:N for j=1:D x(i,j)=randn;%随机初始化位置 v(i,j)=randn;%随机初始化速度 end end %------先计算各个粒子的适应度，并初始化Pi和Pg----------------------for i=1:N p(i)=fitness(x(i,:),D); y(i,:)=x(i,:); end pg=x(1,:);%Pg为全局最优 for i=2:N if fitness(x(i,:),D) 粒子群算法综述 【摘要】：粒子群算法(pso)是一种新兴的基于群体智能的启发式全局搜索算法，具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已得到广泛研究和应用。为了进一步推广应用粒子群算法并为深入研究该算法提供相关资料，本文对目前国内外研究现状进行了全面分析，在论述粒子群算法基本思想的基础上，围绕pso的运算过程、特点、改进方式与应用等方面进行了全面综述，并给出了未来的研究方向展望。 【关键词】：粒子群算法优化综述 优化理论的研究一直是一个非常活跃的研究领域。它所研究的问题是在多方案中寻求最优方案。人们关于优化问题的研究工作，随着历史的发展不断深入，对人类的发展起到了重要的推动作用。但是，任何科学的进步都受到历史条件的限制，直到二十世纪中期，由于高速数字计算机日益广泛应用，使优化技术不仅成为迫切需要，而且有了求解的有力工具。因此，优化理论和算法迅速发展起来，形成一门新的学科。至今已出现线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。这些优化技术在诸多工程领域得到了迅速推广和应用，如系统控制、人工智能、生产调度等。随着人类生存空间的扩大，以及认识世界和改造世界范围的拓宽，常规优化法如牛顿法、车辆梯度法、模式搜索法、单纯形法等已经无法处理人们所面的复杂问题，因此高效的 优化算法成为科学工作者的研究目标之一。 1.粒子群算法的背景 粒子群算法(particle swarm optimization，pso)是一种新兴的演化算法。该算法是由j.kennedy和r.c.eberhart于1995年提出的一种基于群智能的随机优化算法。这类算法的仿生基点是：群集动物(如蚂蚁、鸟、鱼等)通过群聚而有效的觅食和逃避追捕。在这类群体的动物中，每个个体的行为是建立在群体行为的基础之上的，即在整个群体中信息是共享的，而且在个体之间存在着信息的交换与协作。如在蚁群中，当每个个体发现食物之后，它将通过接触或化学信号来招募同伴，使整个群落找到食源；在鸟群的飞行中，每只鸟在初始状态下处于随机位置，且朝各个方向随机飞行，但随着时间推移，这些初始处于随机状态的鸟通过相互学习(相互跟踪)组织的聚集成一个个小的群落，并以相同的速度朝着相同的方向飞行，最终整个群落聚集在同一位置──食源。这些群集动物所表现的智能常称为“群体智能”，它可表述为：一组相互之间可以进行直接通讯或间接通讯(通过改变局部环境)的主体，能够通过合作对问题进行分布求解。换言之，一组无智能的主体通过合作表现出智能行为特征。粒子群算法就是以模拟鸟的群集智能为特征，以求解连续变量优化问题为背景的一种优化算法。因其概念简单、参数较少、易于实现等特点，自提出以来已经受到国内外研究者的高度重视并被广泛应用于许多领域。 粒子群算法程序 tic D=10;%粒子群中粒子的个数 %w=0.729;%w为惯性因子 wmin=1.2; wmax=1.4; c1=1.49445;%正常数，成为加速因子 c2=1.49445;%正常数，成为加速因子 Loop_max=50;%最大迭代次数 %初始化粒子群 for i=1:D X(i)=rand(1)*(-5-7)+7; V(i)=1; f1(i)=X(i)^2; f2(i)=(X(i)-2)^2; end Loop=1;%迭代计数器 while Loop<=Loop_max%循环终止条件 %对粒子群中的每个粒子进行评价 for i=1:D k1=find(1==Xv(i,:));%找出第一辆车配送的城市编号 nb1=size(k1,2);%计算第一辆车配送城市的个数 if nb1>0%判断第一辆车配送城市个数是否大于0，如果大于0则 a1=[Xr(i,k1(:))];%找出第一辆车配送城市顺序号 b1=sort(a1);%对找出第一辆车的顺序号进行排序 G1(i)=0;%初始化第一辆车的配送量 k51=[]; am=[]; for j1=1:nb1 am=find(b1(j1)==Xr(i,:)); k51(j1)=intersect(k1,am);%计算第一辆车配送城市的顺序号 G1(i)=G1(i)+g(k51(j1)+1);%计算第一辆车的配送量 end k61=[]; k61=[0,k51,0];%定义第一辆车的配送路径 L1(i)=0;%初始化第一辆车的配送路径长度 for k11=1:nb1+1 L1(i)=L1(i)+Distance(k61(k11)+1,k61(k11+1)+1);%计算第一辆车的配送路径长度end else%如果第一辆车配送的城市个数不大于0则 G1(i)=0;%第一辆车的配送量设为0 L1(i)=0;%第一辆车的配送路径长度设为0 end 基本粒子群算法的原理和matlab 程序 作者—— niewei120 （nuaa） 一、粒子群算法的基本原理 粒子群优化算法源自对鸟群捕食行为的研究，最初由Kennedy 和 Eberhart 提出，是一种通 用的启发式搜索技术。一群鸟在区域中随机搜索食物，所有鸟知道自己当前位置离食物多远， 那么搜索的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。PSO 算法利用这种模型得到启示并应用于解决优化问题。PSO 算法中，每个优化问题的解都是粒子在搜索 空间中的位置，所有的粒子都有一个被优化的目标函数所决定的适应值，粒子还有一个速度值决定它们飞翔的方向和距离，然后粒子群就追随当前的最优粒子在解空间中搜索。 PSO 算法首先在给定的解空间中随机初始化粒子群，待优化问题的变量数决定了解空间的维数。每个粒子有了初始位置与初始速度。然后通过迭代寻优。在每一次迭代中，每个粒子通过跟踪两个“极值”来更新自己在解空间中的空间位置与飞翔速度。第一个极值就是单个粒子本身在迭代过程中找到的最优解粒子，这个粒子叫做个体极值。另一个极值是种群所有粒子在迭代过程中所找到的最优解粒子，这个粒子是全局极值。上述的方法叫全局粒子群算法。如果不用种群所有粒子而只用其中一部分作为该粒子的邻居粒子，那么在所有邻居粒子中的极值就是局部极值，该方法称为局部PSO 算法。 速度、位置的更新方程表示为： 每个粒子自身搜索到的历史最优值p i，p i=(p i1 ,p i2 ,....,p iQ )， i=1,2,3,....,n 。所有粒子搜索到的最优值p g， p g=(p g1 ,p g2,....,p gQ )，注意这里的p g只有一个。 是保持原来速度的系数，所以叫做惯性权重。 是粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识，所以叫“认知”。通常设置为 2 。 是粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识，所以叫做“社会知识”，经常叫做“社会”。通常设置为2。 是[0,1] 区间内均匀分布的随机数。 是对位置更新的时候，在速度前面加的一个系数，这个系数我们叫做约束因子。通常设 置为 1 。 摘要 在智能领域，大部分问题都可以归结为优化问题。常用的经典优化算法都对问题有一定的约束条件，如要求优化函数可微等，仿生算法是一种模拟生物智能行为的优化算法，由于其几乎不存在对问题的约束，因此，粒子群优化算法在各种优化问题中得到广泛应用。 本文首先描述了基本粒子群优化算法及其改进算法的基本原理,对比分析粒子群优化算法与其他优化算法的优缺点，并对基本粒子群优化算法参数进行了简要分析。根据分析结果,研究了一种基于量子的粒子群优化算法。在标准测试函数的优化上粒子群优化算法与改进算法进行了比较,实验结果表明改进的算法在优化性能明显要优于其它算法。本文算法应用于支持向量机参数选择的优化问题上也获得了较好的性能。最后,对本文进行了简单的总结和展望。 关键词：粒子群优化算法最小二乘支持向量机参数优化适应度 目录 摘要...................................................................... I 目录....................................................................... II 1.概述. (1) 1.1引言 (1) 1.2研究背景 (1) 1.2.1人工生命计算 (1) 1.2.2 群集智能理论 (2) 1.3算法比较 (2) 1.3.1粒子群算法与遗传算法(GA)比较 (2) 1.3.2粒子群算法与蚁群算法(ACO)比较 (3) 1.4粒子群优化算法的研究现状 (4) 1.4.1理论研究现状 (4) 1.4.2应用研究现状 (5) 1.5粒子群优化算法的应用 (5) 1.5.1神经网络训练 (6) 1.5.2函数优化 (6) 1.5.3其他应用 (6) 1.5.4粒子群优化算法的工程应用概述 (6) 2.粒子群优化算法 (8) 2.1基本粒子群优化算法 (8) 2.1.1基本理论 (8) 2.1.2算法流程 (9) 2.2标准粒子群优化算法 (10) 2.2.1惯性权重 (10) 2.2.2压缩因子 (11) 2.3算法分析 (12) 2.3.1参数分析 (12) 2.3.2粒子群优化算法的特点 (14) 3.粒子群优化算法的改进 (15) 3.1粒子群优化算法存在的问题 (15) 3.2粒子群优化算法的改进分析 (15) 3.3基于量子粒子群优化(QPSO)算法 (17) 3.3.1 QPSO算法的优点 (17) 3.3.2 基于MATLAB的仿真 (18) 3.4 PSO仿真 (19) 3.4.1 标准测试函数 (19) 3.4.2 试验参数设置 (20) 3.5试验结果与分析 (21) 4.粒子群优化算法在支持向量机的参数优化中的应用 (22) 4.1支持向量机 (22) 4.2最小二乘支持向量机原理 (22) 粒子群优化算法(1)—粒子群优化算法简介 PSO算法就是模拟一群鸟寻找食物的过程，每个鸟就是PSO中的粒子，也就是我们需要求解问题的可能解，这些鸟在寻找食物的过程中，不停改变自己在空中飞行的位置与速度。大家也可以观察一下，鸟群在寻找食物的过程中，开始鸟群比较分散，逐渐这些鸟就会聚成一群，这个群忽高忽低、忽左忽右，直到最后找到食物。这个过程我们转化为一个数学问题。寻找函数y=1-cos(3*x)*exp(-x)的在[0,4]最大值。该函数的图形如下： 当x=0.9350-0.9450，达到最大值y=1.3706。为了得到该函数的最大值，我们在[0, 4]之间随机的洒一些点，为了演示，我们放置两个点，并且计算这两个点的函数值，同时给这两个点设置在[0, 4]之间的一个速度。下面这些点就会按照一定的公式更改自己的位置，到达新位置后，再计算这两个点的值，然后再按照一定的公式更新自己的位置。直到最后在y=1.3706这个点停止自己的更新。这个过程与粒子群算法作为对照如下： 这两个点就是粒子群算法中的粒子。 该函数的最大值就是鸟群中的食物。 计算两个点函数值就是粒子群算法中的适应值，计算用的函数就是粒子群算法中的适应度函数。 更新自己位置的公式就是粒子群算法中的位置速度更新公式。 下面演示一下这个算法运行一次的大概过程： 第一次初始化 第一次更新位置 第二次更新位置 第21次更新 最后的结果（30次迭代） 最后所有的点都集中在最大值的地方。 粒子群优化算法(2)—标准粒子群优化算法 在上一节的叙述中，唯一没有给大家介绍的就是函数的这些随机的点（粒子）是如何运动的，只是说按照一定的公式更新。这个公式就是粒子群算法中的位置速度更新公式。下面就介绍这个公式是什么。在上一节中我们求取函数y=1-cos(3*x)*exp(-x)的在[0, 4]最大值。并在[0,4]之间放置了两个随机的点，这些点的坐标假设为x1=1.5，x2=2.5；这里的点是一个标量，但是我们经常遇到的问题可能是更一般的情况—x 为一个矢量的情况，比如二维z=2*x1+3*x22的情况。这个时候我们的每个粒子均为二维，记粒子P1＝(x11,x12),P2=(x21,x22),P3=(x31,x32)，......Pn=(xn1,xn2)。这里n 为粒子群群体的规模，也就是这个群中粒子的个数，每个粒子的维数为2。更一般的是粒子的维数为q ，这样在这个种群中有n 个粒子，每个粒子为q 维。 由n 个粒子组成的群体对Q 维（就是每个粒子的维数）空间进行搜索。每个粒子表示为：x i ＝（x i1,x i2,x i3,...,x iQ ），每个粒子对应的速度可以表示为v i =(v i1,v i2,v i3,....,v iQ )，每个粒子在搜索时要考虑两个因素： 1. 自己搜索到的历史最优值 p i ，p i =(p i1,p i2,....,p iQ )，i=1,2,3,....,n ； 2. 全部粒子搜索到的最优值p g ，p g =(p g1,p g2,....,p gQ )，注意这里的p g 只有一个。 下面给出粒子群算法的位置速度更新公式： 112()()()()k k k k i i i i v v c rand pbest x c rand gbest x ω+=+??-+??-, 11k k k i i i x x av ++=+. 这里有几个重要的参数需要大家记忆，因为在以后的讲解中将会经常用到，它们是： ω是保持原来速度的系数，所以叫做惯性权重。1c 是粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识，所以叫“认知”。通常设置为2。2c 是粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识，所以叫做“社会知识”，经常叫做“社会”。通常设置为2。()rand 是[0,1]区间内均匀分布的随机数。a 是对位置更新的时候，在速度前面加的一个系数，这个系数我们叫做约束因子。通常设置为1。这样一个标准的粒子群算法就介绍结束了。下图是对整个基本的粒子群的过程给一个简单的图形表示。 判断终止条件可是设置适应值到达一定的数值或者循环一定的次数。 注意：这里的粒子是同时跟踪自己的历史最优值与全局（群体）最优值来改变自己的位置预速度的，所以又叫做全局版本的标准粒子群优化算法。 //粒子群PSO算法 #include 启发式优化算法综述 一、启发式算法简介 1、定义 由于传统的优化算法如最速下降法，线性规划，动态规划，分支定界法，单纯形法，共轭梯度法，拟牛顿法等在求解复杂的大规模优化问题中无法快速有效地寻找到一个合理可靠的解，使得学者们期望探索一种算法:它不依赖问题的数学性能，如连续可微，非凸等特性; 对初始值要求不严格、不敏感，并能够高效处理髙维数多模态的复杂优化问题，在合理时间内寻找到全局最优值或靠近全局最优的值。于是基于实际应用的需求，智能优化算法应运而生。智能优化算法借助自然现象的一些特点，抽象出数学规则来求解优化问题，受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。 为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。因此，采用一种相对好的求解算法，去尽可能逼近最优解，得到一个相对优解，在很多实际情况中也是可以接受的。启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。 启发式算法是和问题求解及搜索相关的，也就是说,启发式算法是为了提高搜索效率才提出的。人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题 时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案，以随机或近似随机方法搜索非线性复杂空间中全局最优解的寻取。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决。 2、发展历史 启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，才能取得了巨大的成就。纵观启发式算法的历史发展史： 40年代：由于实际需要，提出了启发式算法（快速有效）。 50年代：逐步繁荣，其中贪婪算法和局部搜索等到人们的关注。 60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规模的问题仍然无能为力（收敛速度慢）。 70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。由此必须引入新的搜索机制和策略。 Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的兴趣。 80年代以后：模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。 最近比较火热的：演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms），拟人拟物算法，量子算法等。 程序1 当22111==c c ，5.12212==c c ，2.1=w 。 a)%主函数源程序（main.m ） %------基本粒子群算法 （particle swarm optimization ） %------名称： 基本粒子群算法 %------初始格式化 clear all ; %清除所有变量 clc; %清屏 format long ; %将数据显示为长整形科学计数 %------给定初始条条件------------------ N=40; %3初始化群体个数 D=10; %初始化群体维数 T=100; %初始化群体最迭代次数 c11=2; %学习因子1 c21=2; %学习因子2 c12=1.5; c22=1.5; w=1.2; %惯性权重 eps=10^(-6); %设置精度（在已知最小值的时候用） %------初始化种群个体（限定位置和速度）------------ x=zeros(N,D); v=zeros(N,D); for i=1:N for j=1:D x(i,j)=randn; %随机初始化位置 v(i,j)=randn; %随机初始化速度 end end %------显示群位置---------------------- figure(1) for j=1:D if (rem(D,2)>0) subplot((D+1)/2,2,j) else subplot(D/2,2,j) end plot(x(:,j),'b*');grid on xlabel('粒子') ylabel('初始位置') tInfo=strcat('第',char(j+48),'维'); if(j>9) tInfo=strcat('第',char(floor(j/10)+48)，char(rem(j,10)+48),'维'); end title(tInfo) end %------显示种群速度 figure(2) for j=1:D if(rem(D,2)>0) subplot((D+1)/2,2,j) else subplot(D/2,2,j) end plot(x(:,j),'b*');grid on xlabel('粒子') ylabel('初始速度') tInfo=strcat('第,char(j+48),'维'); if(j>9) tInfo=strcat('第',char(floor(j/10)+48), char(rem(j,10)+48),'维); end title(tInfo) end figure(3) %第一个图 subplot(1,2,1) 附录 程序1 当22111==c c ，5.12212==c c ，2.1=w 。 a)%主函数源程序（main.m ） %------基本粒子群算法 （particle swarm optimization ） %------名称： 基本粒子群算法 %------初始格式化 clear all ; %清除所有变量 clc; %清屏 format long ; %将数据显示为长整形科学计数 %------给定初始条条件------------------ N=40; %3初始化群体个数 D=10; %初始化群体维数 T=100; %初始化群体最迭代次数 c11=2; %学习因子1 c21=2; %学习因子2 c12=1.5; c22=1.5; w=1.2; %惯性权重 eps=10^(-6); %设置精度（在已知最小值的时候用） %------初始化种群个体（限定位置和速度）------------ x=zeros(N,D); v=zeros(N,D); for i=1:N for j=1:D x(i,j)=randn; %随机初始化位置 v(i,j)=randn; %随机初始化速度 end end %------显示群位置---------------------- figure(1) for j=1:D if(rem(D,2)>0) subplot((D+1)/2,2,j) else subplot(D/2,2,j) end plot(x(:,j),'b*');grid on xlabel('粒子') ylabel('初始位置') tInfo=strcat('第',char(j+48),'维'); if(j>9) tInfo=strcat('第',char(floor(j/10)+48),char(rem(j,10)+48),'维'); end title(tInfo) end %------显示种群速度 figure(2) for j=1:D if(rem(D,2)>0) subplot((D+1)/2,2,j) else subplot(D/2,2,j) end plot(x(:,j),'b*');grid on xlabel('粒子') ylabel('初始速度') tInfo=strcat('第,char(j+48),'维'); if(j>9) tInfo=strcat('第',char(floor(j/10)+48), char(rem(j,10)+48),'维); end title(tInfo) end figure(3) 粒子群优化算法 1. 引言 粒子群优化算法(PSO)是一种进化计算技术(evolutionary computation)，由Eberhart博士和kennedy博士发明。源于对鸟群捕食的行为研究 PSO同遗传算法类似，是一种基于迭代的优化工具。系统初始化为一组随机解，通过迭代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)。而是粒子在解空间追随最优的粒子进行搜索。详细的步骤以后的章节介绍 同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域 2. 背景: 人工生命 "人工生命"是来研究具有某些生命基本特征的人工系统. 人工生命包括两方面的容 1. 研究如何利用计算技术研究生物现象 2. 研究如何利用生物技术研究计算问题 我们现在关注的是第二部分的容. 现在已经有很多源于生物现象的计算技巧. 例如, 人工神经网络是简化的大脑模型. 遗传算法是模拟基因进化过程的. 现在我们讨论另一种生物系统- 社会系统. 更确切的是, 在由简单个体组成的群落与环境以及个体之间的互动行为. 也可称做"群智能"(swarm intelligence). 这些模拟系统利用局部信息从而可能产生不可预测的群体行为 例如floys 和boids, 他们都用来模拟鱼群和鸟群的运动规律, 主要用于计算机视觉和计算机辅助设计. 在计算智能(computational intelligence)领域有两种基于群智能的算法. 蚁群算法(ant colony optimization)和粒子群算法(particle swarm optimization). 前者是对蚂蚁群落食物采集过程的模拟. 已经成功运用在很多离散优化问题上. 粒子群优化算法(PSO) 也是起源对简单社会系统的模拟. 最初设想是模拟鸟群觅食的过程. 但后来发现PSO是一种很好的优化工具. 3. 算法介绍 粒子群算法原理及其在函数优化中的应用 1粒子群优化(PSO)算法基本原理 1.1标准粒子群算法 假设在一个D 维的目标搜索空间中，有 m 个代表问题潜在解的粒子组成一 个种群x [X i ,X 2,...,X m ],第i 个粒子的信息可用D 维向量表示为 X i [X ii , X i2,..., X iD ]T ，其速度为V i [V ii ,V i2,...,V iD ]T 。算法首先初始化m 个随机粒 子，然后通过迭代找到最优解。每一次迭代中，粒子通过跟踪2个极值进行信息 交流，一个是第i 个粒子本身找到的最优解，称之为个体极值，即 P i [P il , P i2,...,厢]丁 ；另一个是所有粒子目前找到的最优解，称之为群体极值， 即P g [P gi ,P g2,..., P gD 「。粒子在更新上述2个极值后，根据式(1)和式(2)更新自 己的速度和位置。 t 1 t t t t t\ V i WV i C 1「1（P i X i ） C 2「2（P g X i ） 式中，t 代表当前迭代次数，「1,「2是在[0,1]之间服从均匀分布的随机数，C 1,C 2 称为学习因子，分别调节粒子向个体极值和群体极值方向飞行的步长， w 为惯性 权重，一般在0.1~0.9之间取值。在标准的PSO 算法中，惯性权重w 被设为常数, 通常取w 0.5。在实际应用中，x 需保证在一定的范围内，即x 的每一维的变化 范围均为[X min ,X max ],这在函数优化问题中相当丁自变量的定义域 1.2算法实现步骤 步骤1:表示出PSO 算法中的适应度函数fitness(x)；(编程时最好以函数的 形式保存，便丁多次调用。) 步骤2:初始化PSO 算法中各个参数(如粒子个数，惯性权重，学习因子， 最大迭代次数等)，在自变量x 定义域内随机初始化x ，代入fitness(x)求得适应 度值，通过比较确定起始个体极值P i 和全局极值P g 。 步骤3:通过循环迭代更新x 、p i 和p g : ① 确定惯性权重w 的取值(当w 不是常数时)。 ② 根据式(1)更新粒子的速度V ：1,若速度中的某一维超过了 V max ，则取为 V max - ③ 根据式(2)更新自变量x ,若x 的取值超过其定义域，则在其定义域内重新 初t 1 X i t t 1 X i V i 一．粒子群优化算法综述 1.6粒子群优化算法的参数设置 1.6.1粒子群优化算法的参数设置—种群规模N 种群规模N影响着算法的搜索能力和计算量： PSO对种群规模要求不高，一般取20-40就可以达到很好的求解效果，不过对于比较难的问题或者特定类别的问题，粒子数可以取到100或200。 1.6.2粒子的长度D 粒子的长度D由优化问题本身决定，就是问题解的长度。 粒子的范围R由优化问题本身决定，每一维可以设定不同的范围。 1.6.3最大速度Vmax决定粒子每一次的最大移动距离，制约着算法的探索和开发能力 Vmax的每一维一般可以取相应维搜索空间的10%-20%，甚至100% ，也有研究使用将Vmax按照进化代数从大到小递减的设置方案。 1.6.4惯性权重控制着前一速度对当前速度的影响，用于平衡算法的探索和开发能力 一般设置为从0.9线性递减到0.4，也有非线性递减的设置方案； 可以采用模糊控制的方式设定，或者在[0.5, 1.0]之间随机取值； 设为0.729的同时将c1和c2设1.49445，有利于算法的收敛。 1.6.5压缩因子限制粒子的飞行速度的，保证算法的有效收敛 Clerc0.729，同时c1和c2设为2.05 。 1.6.6加速系数c1和c2 加速系数c1和c2代表了粒子向自身极值pBest和全局极值gBest推进的加速权值。 c1和c2通常都等于2.0，代表着对两个引导方向的同等重视，也存在一些c1和c2不相等的设置，但其范围一般都在0和4之间。研究对c1和c2的自适应调整方案对算法性能的增强有重要意义。 1.6.7终止条件 终止条件决定算法运行的结束，由具体的应用和问题本身确定。将最大循环数设定为500，1000，5000，或者最大的函数评估次数，等等。也可以使用算法 % 优化函数以m文件的形式放在fitness.m里面，对不同的优化函数只要修改fitness.m 就可 %------基本粒子群优化算法（Particle Swarm Optimization, PSO）----------- %------初始格式化-------------------------------------------------- clear all; clc; format long; %------给定初始化条件---------------------------------------------- c1=1.4962; %学习因子1 c2=1.4962; %学习因子2 w=0.7298; %惯性权重 MaxDT=1000; %最大迭代次数 D=4; %搜索空间维数（未知数个数） N=10; %初始化群体个体数目 eps=10^(-6); %设置精度(在已知最小值时候用) %------初始化种群的个体(可以在这里限定位置和速度的范围)------------ x=0:0.1:1，y=[-.447,1.978,3.11,5.25,5.02,4.66,4.01,4.58,3.45,5.35,9.22] %------先计算各个粒子的适应度，并初始化Pi和Pg---------------------- for i=1:N p(i)=fitness(x(i,:),D); y(i,:)=x(i,:); end pg=x(1,:); %Pg为全局最优 for i=2:N if fitness(x(i,:),D) 1 群体智能概述 1.1 群体智能的概念与特点 群体智能的概念源于对蜜蜂、蚂蚁、大雁等这类群居生物群体行为的观察和研究，是一种在自然界生物群体所表现出的智能现象启发下提出的人工智能实现模式，是对简单生物群体的智能涌现现象的具体模式研究。群体智能指的是“简单智能的主体通过合作表现出复杂智能行为的特性”。该种智能模式需要以相当数目的智能体来实现对某类问题的求解功能。作为智能个体本身，在没有得到智能群体的总体信息反馈时，它在解空间中的行进方式是没有规律的。只有受到整个智能群体在解空间中行进效果的影响之后，智能个体在解空间中才能表现出具有合理寻优特征的行进模式。自然界中动物、昆虫常以集体的力量进行觅食生存，在这些群落中单个个体所表现的行为是简单缺乏智能的，且各个个体之间的行为是遵循相同规则的，但由个体组成的群体则表现出了一种有效的复杂的智能行为。群体智能可以在适当的进化机制引导下通过个体交互以某种突现形式发挥作用，这是个体的智能难以做到的。 通常，群体智能是指一种人工智能模式，体现的是一种总体的智能特性。人工智能主要有两种研究范式，即符号主义和联接主义。符号主义采用知识表达和逻辑符号系统来模拟人类的智能。联接主义则从大脑和神经系统的生理背景出发来模拟它们的工作机理和学习方式。符号主义试图对智能进行宏观研究，而联接主义则是一种微观意义上的探索。20世纪90年代后，计算智能的研究逐渐成为了联接主义人工智能的一个代表性流派。计算智能系统是在神经网络、模糊系统、进化计算三个分支发展相对成熟的基础上，通过相互之间的有机融合而形成的新的科学方法，也是智能理论和技术发展的崭新阶段。神经网络反映大脑思维的高层次结构；模糊系统模仿低层次的大脑结构；进化系统则是从生物种群的群体角度研究智能产生和进化过程。对群居性生物群体行为涌现的群体智能的研究是进化系统的一个新兴研究领域。 群体智能中，最小智能但自治的个体利用个体与个体和个体与环境的交互作用实现完全分布式控制，其具有以下特点： （1）自组织。自组织是一种动态机制，由底层单元(部件)的交互而呈现出系统的全局性的结构。交互的规则仅依赖于局部信息，而不依赖于全局的模式。自组织并不是外部的影响施加给系统而体现的一种性质，而是系统自身涌现出的一种性质。系统中没有一个中心控制模块，也不存在一个部分控制另一部分。正反馈（positive feedback）群体中的每个具有简单能力的个体表现出某种行为，会遵循已有的结构或者信息指引自己的行动，并且释放自身的信息素，这种不断的反馈能够使得某种行为加强。尽管一开始都是一些随机的行为，大量个体遵循正(完整word版)基本粒子群算法的原理和matlab程序
粒子群优化算法综述
基本粒子群算法的matlab源程序
粒子群算法综述
用粒子群算法求解多目标优化问题的Pareto解
(完整word版)基本粒子群算法的原理和matlab程序.doc
粒子群优化算法及其应用研究【精品文档】(完整版)
粒子群优化算法介绍及matlab程序
c语言实现的粒子群算法代码及解释
启发式优化算法综述【精品文档】(完整版)
6种粒子群算法程序
粒子群优化算法及其参数设置
粒子群优化算法综述
粒子群算法原理及在函数优化中的应用(附程序)
粒子群优化算法参数设置
粒子群算法通用matlab程序
粒子群优化算法