粒子群算法毕业论文Word下载.doc
- 文档编号:3667692
- 上传时间:2023-05-02
- 格式:DOC
- 页数:82
- 大小:1.09MB
粒子群算法毕业论文Word下载.doc
《粒子群算法毕业论文Word下载.doc》由会员分享,可在线阅读,更多相关《粒子群算法毕业论文Word下载.doc(82页珍藏版)》请在冰点文库上搜索。
Particleswarmoptimizationalgorithmanditsparameterset
Speciality:
InformationandComputingScience
Student:
RenKan
Advisor:
XuXiaoping
Abstract
Particleswarmoptimizationisanemergingglobalbasedonswarmintelligenceheuristicsearchalgorithm,particleswarmoptimizationalgorithmcompetitionandcollaborationbetweenparticlestoachieveincomplexsearchspacetofindtheglobaloptimum.Ithaseasytounderstand,easytoachieve,thecharacteristicsofstrongglobalsearchability,andhasneverwidefieldofscienceandengineeringconcern,hasbecomethefastestgrowingoneoftheintelligentoptimizationalgorithms.Thispaperintroducestheparticleswarmoptimizationbasicprinciples,andanalyzesitsfeatures.Paperaroundtheparticleswarmoptimizationprinciples,characteristics,parameterssettingsandapplicationstoconductathoroughreview,focusingonasinglefactoranalysisofvariance,analysisoftheparticleswarmoptimizationalgorithmintheinertiaweight,accelerationfactorsettingthebasicpropertiesofthealgorithmtheimpactoftheexperienceofthealgorithmgivenparametersetting.Finally,itsfutureresearchedandprospectsareproposed.
Keyword:
Particleswarmoptimization;
Parameter;
Varianceanalysis;
Optimalsolution
目录
摘要 II
Abstract III
1.引言 1
1.1研究背景和课题意义 1
1.2参数的影响 1
1.3应用领域 2
1.4电子资源 2
1.5主要工作 2
2.基本粒子群算法 3
2.1粒子群算法思想的起源 3
2.2算法原理 4
2.3基本粒子群算法流程 5
2.4特点 6
2.5带惯性权重的粒子群算法 7
2.7粒子群算法的研究现状 8
3.粒子群优化算法的改进策略 9
3.1粒子群初始化 9
3.2邻域拓扑 9
3.3混合策略 12
4.参数设置 14
4.1对参数的仿真研究 14
4.2测试仿真函数 15
4.3应用单因子方差分析参数对结果影响 33
4.4对参数的理论分析 34
5结论与展望 39
致谢 43
附录 44
1.引言
1.1研究背景和课题意义
“人工生命”是来研究具有某些生命基本特征的人工系统。
人工生命包括两方面的内容:
1、研究如何利用计算技术研究生物现象。
2、研究如何利用生物技术研究计算问题。
现在已经有很多源于生物现象的计算技巧。
例如,人工神经网络是简化的大脑模型。
遗传算法是模拟基因进化过程的。
现在我们讨论另一种生物系统-社会系统。
也可称做“群智能”(swarmintelligence)。
这些模拟系统利用局部信息从而可能产生不可预测的群体行为。
粒子群优化算法(PSO)也是起源对简单社会系统的模拟。
最初设想是模拟鸟群觅食的过程。
但后来发现PSO是一种很好的优化工具。
优化是科学研究、工程技术和经济管理等领域的重要研究课题。
粒子群优化算法[1](简称PSO)是由Kennedy和Eberhart通过对鸟群、鱼群和人类社会某些行为的观察研究,于1995年提出的一种新颖的进化算法。
虽然PSO算法发展迅速并取得了可观的研究成果,但其理论基础仍相对薄弱,尤其是算法基本模型中的参数设置和优化问题还缺乏成熟的理论论证和研究。
鉴于PSO的发展历史尚短,它在理论基础与应用推广上都还存在一些缺陷,有待解决。
本文通过对PSO算法的步骤的归纳、特点的分析,利用统计中的方差分析,通过抽样实验方法,论证了该算法中关键参数因子:
惯性权值、加速因子对算法整体性能的影响效果,并提出了参数设置的指导原则,给出了关键参数设置,为PSO算法的推广与改进提供了思路。
1.2参数的影响
标准粒子群算法中主要的参数变量为(惯性权值),,(加速因子),,本文重点对参数,,做数据统计实验。
包括不变的情况下通过,变化找出加速因子对算法的影响。
还有保持,不变对分别取不同值分析其对算法结果影响。
1.3应用领域
近年来,PSO快速发展,在众多领域得到了广泛应用。
本文将应用研究分典型理论问题研究和实际工业应用两大类。
典型理论问题包括:
组合优化、约束优化、多目标优化、动态系统优化等。
实际工业应用有:
电力系统、滤波器设计、自动控制、数据聚类、模式识别与图像处理、化工、机械、通信、机器人、经济、生物信息、医学、任务分配、TSP等等。
1.4电子资源
身处信息和网络时代的我们是幸运的,丰富的电子资源能让我们受益匪浅。
如果想较快地对PSO有一个比较全面的了解,借助网络空间的电子资源无疑是不二之选。
对一些初学者而言,哪里能下载得到PSO的源程序,是他们很关心的话题;
即使对一些资深的读者,为了验证自己提出的新算法或改进算法,如果能找到高级别国际期刊或会议上最近提出的算法源程序,那也是事半功倍的美事。
这里介绍当今PSO研究领域较有影响的一个网址:
MauriceClerc博士(Maurice.Clerc@WriteM)的PSO主页:
http:
//clerc.maurice.free.fr/pso/
该主页主要介绍MauriceClerc博士带领的PSO研究小组的研究成果。
除了从中可以得到他们近几年公开发表的相关文献和源代码,还可以下载一些未公开发表的文章。
这些未公开发表的文章往往是MauriceClerc博士的一些设想,而且在不断更新,如“Backtorandomtopology”、“Initialisationsforparticleswarmoptimization”、“SomeideasaboutPSO”等等,对PSO研究人员很有启发。
1.5主要工作
论文内容介绍了基本粒子群算法,用matlab实现标准粒子群算法算法,对两个不同类型函数做具体分析,然后对其参数(惯性权值),,(加速因子)测试。
分别对其利用单因子方差分析法,说明不同参数水平对算法速率性能的影响。
并且通过公式计算准确判断参数对算法影响。
最后说明粒子群优化算法在实际中的应用以及对未来展望,最后总结了算法的优缺点,附录里面附有测试程序和测试函数。
2.基本粒子群算法
2.1粒子群算法思想的起源
粒子群优化(ParticleSwarmOptimization,PSO)算法[1]是Kennedy和Eberhart受人工生命研究结果的启发、通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法,1995年IEEE国际神经网络学术会议发表了题为“ParticleSwarmOptimization”的论文,标志着PSO算法诞生(注:
国内也有很多学者译为“微粒群优化”)。
它与其他进化算法一样,也是基于“种群”和“进化”的概念,通过个体间的协作与竞争,实现复杂空间最优解的搜索;
同时,PSO又不像其他进化算法那样对个体进行交叉、变异、选择等进化算子操作,而是将群体(swarm)中的个体看作是在D维搜索空间中没有质量和体积的粒子(particle),每个粒子以一定的速度在解空间运动,并向自身历史最佳位置pbest和邻域历史最佳位置聚集,实现对候选解的进化。
PSO算法具有很好的生物社会背景[2]而易理解、参数少而易实现,对非线性、多峰问题均具有较强的全局搜索能力,在科学研究与工程实践中得到了广泛关注[3-10]。
自然界中各种生物体均具有一定的群体行为,而人工生命的主要研究领域之一是探索自然界生物的群体行为,从而在计算机上构建其群体模型。
自然界中的鸟群和鱼群的群体行为一直是科学家的研究兴趣,生物学家CraigReynolds在1987年提出了一个非常有影响的鸟群聚集模型[7],在他的仿真中,每一个个体遵循:
(1)避免与邻域个体相冲撞;
(2)匹配邻域个体的速度;
(3)飞向鸟群中心,且整个群体飞向目标。
仿真中仅利用上面三条简单的规则,就可以非常接近的模拟出鸟群飞行的现象。
1990年,生物学家FrankHeppner也提出了鸟类模型[8],它的不同之处在于:
鸟类被吸引飞到栖息地。
在仿真中,一开始每一只鸟都没有特定的飞行目标,只是使用简单的规则确定自己的飞行方向和飞行速度(每一只鸟都试图留在鸟群中而又不相互碰撞),当有一只鸟飞到栖息地时,它周围的鸟也会跟着飞向栖息地,这样,整个鸟群都会落在栖息地。
1995年,美国社会心理学家JamesKennedy和电气工程师RussellEberhart共同提出了粒子群算法,其基本思想是受对鸟类群体行为进行建模与仿真的研究结果的启发。
他们的模型和仿真算法主要对FrankHeppner的模型进行了修正,以使粒子飞向解空间并在最好解处降落。
Kennedy在他的书中描述了粒子群算法思想的起源。
自20世纪30年代以来,社会心理学的发展揭示:
我们都是鱼群或鸟群聚集行为的遵循者。
在人们的不断交互过程中,由于相互的影响和模仿,他们总会变得更相似,结果就形成了规范和文明。
人类的自然行为和鱼群及鸟群并不类似,而人类在高维认知空间中的思维轨迹却与之非常类似。
思维背后的社会现象远比鱼群和鸟群聚集过程中的优美动作复杂的多:
首先,思维发生在信念空间,其维数远远高于3;
其次,当两种思想在认知空间会聚于同一点时,我们称其一致,而不是发生冲突。
2.2算法原理
PSO从这种模型中得到启示并用于解决优化问题。
PSO中,每个优化问题的潜在解都是搜索空间中的一只鸟,称之为粒子。
所有的粒子都有一个由被优化的函数决定的适值(fitnessvalue),每个粒子还有一个速度决定它们飞翔的方向和距离。
然后粒子们就追随当前的最优粒子在解空间中搜索[1]。
PSO初始化为一群随机粒子(随机解),然后通过迭代找到最优解。
在每一次迭代中,粒子通过跟踪两个极值来更新自己;
第一个就是粒子本身所找到的最优解,这个解称为个体极值;
另一个极值是整个种群目前找到的最优解,这个极值是全局极值。
另外也可以不用整个种群而只是用其中一部分作为粒子的邻居,那么在所有邻居中的极值就是局部极值。
假设在一个维的目标搜索空间中,有个粒子组成一个群落,其中第个粒子表示为一个维的向量
,。
第个粒子的“飞行”速度也是一个维的向量,记为
,。
第个粒子迄今为止搜索到的最优位置称为个体极值,记为
,。
整个粒子群迄今为止搜索到的最优位置为全局极值,记为
在找到这两个最优值时,粒子根据如下的公式(2.1)和(2.2)来更新自己的速度和位置[12]:
(2.1)
(2.2)
其中:
和为学习因子,也称加速常数(accelerationconstant),和为[0,1]范围内的均匀随机数。
式(2.1)右边由三部分组成,第一部分为“惯性(inertia)”或“动量(momentum)”部分,反映了粒子的运动“习惯(habit)”,代表粒子有维持自己先前速度的趋势;
第二部分为“认知(cognition)”部分,反映了粒子对自身历史经验的记忆(memory)或回忆(remembrance),代表粒子有向自身历史最佳位置逼近的趋势;
第三部分为“社会(social)”部分,反映了粒子间协同合作与知识共享的群体历史经验,代表粒子有向群体或邻域历史最佳位置逼近的趋势,根据经验,通常。
。
是粒子的速度,,是常数,由用户设定用来限制粒子的速度。
和是介于之间的随机数[2][5]。
2.3基本粒子群算法流程
算法的流程如下:
①初始化粒子群,包括群体规模,每个粒子的位置和速度
②计算每个粒子的适应度值;
③对每个粒子,用它的适应度值和个体极值比较,如果,则用替换掉;
④对每个粒子,用它的适应度值和全局极值比较,如果则用替;
⑤根据公式(2.1),(2.2)更新粒子的速度和位置;
⑥如果满足结束条件(误差足够好或到达最大循环次数)退出,否则返回②。
输出结果
根据方程(2.2)对粒子的位置进行进化
根据方程(2.1)对粒子的速度进行进化
求出整个群体的全局最优值
求出每个粒子的个体最优
计算每个粒子的适应值
初始化每个粒子的速度和位置
是否满足结束条件
是
否
开始
图2.1.PSO算法流程图
2.4特点
1、式(2.1)中第1部分可理解为粒子先前的速度或惯性;
第2部份可理解为粒子的“认知”行为,表示粒子本身的思考能力;
第3部分可理解为粒子的“社会”行为,表示粒子之间的信息共享与相互合作。
公式(2.2)表示了粒子在求解空间中,由于相互影响导致的运动位置调整。
整个求解过程中,惯性权重、加速因子和和最大速度共同维护粒子对全局和局部搜索能力的平衡。
2、粒子群优化算法初期,其解群随进化代数表现了更强的随机性,正是由于其产生了下一代解群的较大的随机性,以及每代所有解的“信息”的共享性和各个解的“自我素质”的提高。
3、PSO的一个优势就是采用实数编码,不需要像遗传算法一样采用二进制编码(或者采用针对实数的遗传操作)。
例如对于问题求解,粒子可以直接编码为,而适应度函数就是。
4、粒子具有“记忆”的特性,它们通过“自我”学习和向“他人”学习,使其下一代解有针对性的从“先辈”那里继承更多的信息,从而能在较短的时间内找到最优解。
5、与遗传算法相比,粒子群优化算法的信息共享机制是很不同的:
在遗传算法中,染色体互相共享信息,所以整个种群的移动是比较均匀的向最优区域移动;
在粒子群优化算法中,信息流动是单向的,即只有将信息给其他的粒子,这使得整个搜索更新过程跟随当前解。
2.5带惯性权重的粒子群算法
探索是偏离原来的寻优轨迹去寻找一个更好的解,探索能力是一个算法的全局搜索能力。
开发是利用一个好的解,继续原来的寻优轨迹去搜索更好的解,它是算法的局部搜索能力。
如何确定局部搜索能力和全局搜索能力的比例,对一个问题的求解过程很重要。
1998年,YuhuiShi[9]提出了带有惯性权重的改进粒子群算法。
其进化过程为:
(2.3)
(2.4)
在式(2.1)中,第一部分表示粒子先前的速度,用于保证算法的全局收敛性能;
第二部分、第三部分则是使算法具有局部收敛能力。
可以看出,式(2.3)中惯性权重表示在多大程度上保留原来的速度。
较大,全局收敛能力强,局部收敛能力弱;
较小,局部收敛能力强,全局收敛能力弱。
当时,式(2.3)与式(2.1)完全一样,表明带惯性权重的粒子群算法是基本粒子群算法的扩展。
实验结果表明,在之间时,PSO算法有更快的收敛速度,而当时,算法则易陷入局部极值。
2.7粒子群算法的研究现状
在算法的理论研究方面。
目前PSO算法还没有成熟的理论分析,少部分研究者对算法的收敛性进行了分析,大部分研究者在算法的结构和性能改善方面进行研究,包括参数分析,拓扑结构,粒子多样性保持,算法融合和性能比较等。
PSO由于有简单、易于实现、设置参数少、无需梯度信息等特点,其在连续非线性优化问题和组合优化问题中都表现出良好的效果。
3.粒子群优化算法的改进策略
由于PSO中粒子向自身历史最佳位置和邻域或群体历史最佳位置聚集,形成粒子种群的快速趋同效应,容易出现陷入局部极值、早熟收敛或停滞现象[12-14]。
同时,PSO的性能也依赖于算法参数[15]。
为了克服上述不足,各国研究人员相继提出了各种改进措施。
本文将这些改进分为4类:
粒子群初始化、邻域拓扑、参数选择和混合策略。
3.1粒子群初始化
研究表明,粒子群初始化对算法性能产生一定影响[16]。
为了初始种群尽可能均匀覆盖整个搜索空间,提高全局搜索能力,Richard和Ventura[17]提出了基于centroidalvoronoitessellations(CVTs)的种群初始化方法;
薛明志等人[18]采用正交设计方法对种群进行初始化;
Campana等人[19]将标准PSO迭代公式改写成线性动态系统,并基于此研究粒子群的初始位置,使它们具有正交的运动轨迹;
文献[16]认为均匀分布随机数进行初始化实现容易但尤其对高维空间效果差,并另外比较了3种初始化分布方法。
3.2邻域拓扑
根据粒子邻域是否为整个群体,PSO分为全局模型和局部模型[20]。
对于模型,每个粒子与整个群体的其他粒子进行信息交换,并有向所有粒子中的历史最佳位置移动的趋势。
Kennedy[21]指出,模型虽然具有较快的收敛速度,但更容易陷入局部极值。
为了克服全局模型的缺点,研究人员采用每个粒子仅在一定的邻域内进行信息交换,提出各种局部模型[21,]。
根据现有的研究成果,本文将邻域分为空间邻域(spatialneighborhood)、性能空间(performancespace)邻域和社会关系邻域(sociometricneighborhood)。
空间邻域直接在搜索空间按粒子间的距离(如欧式距离)进行划分,如Suganthan[23]引入一个时变的欧式空间邻域算子:
在搜索初始阶段,将邻域定义为每个粒子自身;
随着迭代次数的增加,将邻域范围逐渐扩展到整个种群。
性能空间指根据性能指标(如适应度、目标函数值)划分的邻域,如文献[24]采用适应度距离比值(fitness-distance-ratio)来选择粒子的相邻粒子。
社会关系邻域通常按粒子存储阵列的索引编号进行划分[25],这也是研究最多的一种划分手段,主要有[21]:
环形拓扑(ringorcircletopology)、轮形拓扑(wheeltopology)或星形拓扑(startopology)、塔形拓扑(pyramidtopology)、冯-诺以曼拓扑(VonNeumanntopology)以及随机拓扑(randomtopology)等。
针对不同的优化问题,这些拓扑的性能表现各异;
但总的来说,随机拓扑往往对大多数问题能表现出较好的性能,其次是冯-诺以曼拓扑[22]。
M.Clerc[25]对随机拓扑进行了进一步分析,并在2006年版和2007年版的标准PSO[23]中采用了随机拓扑。
此外,文献[21]提出动态社会关系拓扑(Dynamicsociometry),初始阶段粒子采用环形拓扑(ring-typetopology),随着迭代次数的增加,逐渐增加粒子间连接,最后形成星形拓扑(star-typetopology)。
此外,还有其它一些主要对群体进行划分的邻域结构(本文暂称“宏观邻域”;
则上述邻域称为“微观邻域”)。
文献[19]引入了子种群,子种群间通过繁殖(Breeding)实现信息交流。
Kennedy[20]提出了社会趋同(Stereotyping)模型,使用簇分析将整个粒子群划分为多个簇,然后用簇中心代替带收缩因子PSO中的粒子历史最佳位置或群体历史最佳位置。
X.Li[21]根据粒子相似性动态地将粒子群体按种类划分为多个子种群,再以每个子种群的最佳个体作为每个粒子的邻域最佳位置。
StefanJanson等人[22]提出等级PSO(hierarchicalparticleswarmoptimizer,HPSO),采用动态等级树作为邻域结构,历史最佳位置更优的粒子处于上层,每个粒子的速度由自身历史最佳位置和等级树中处于该粒子上一个节点的粒子的历史最佳位置决定。
文献[13]采用主-仆模型(master–slavermodel),其中包含一个主群体,多个仆群体,仆群体进行独立的搜索,主群体在仆群体提供的最佳位置基础上开展搜索。
文献[14]将小生境(niche)技术引入到PSO中,提出了小生境PSO(NichingParticleSwarmOptimizer)。
文献[15]采用多群体进行解的搜索。
文献[14]则每间隔一定代数将整个群体随机地重新划分,提出动态多群体PSO。
在标准的PSO算法中,所有粒子仅仅向自身和邻域的历史最佳位置聚集,而没有向邻域内其他个体(即使这些个体很优秀)学习,造成信息资源的浪费,甚至因此而陷入局部极值;
考虑到此因素,Kennedy等人[17]提出了全信息粒子群(fullyinformedparticleswarm,FIPS),在FIPS中,每个粒子除了自身和邻域最佳历史位置外,还学习邻域内其他粒子的成功经验。
上述粒子间学习是在整个维空间中构造邻域进行的,这样当搜索空间维数较高时往往容易遭受“维数灾(curseofdimensionality)”的困扰[
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 粒子 算法 毕业论文