自然计算模型系列之 粒子群( 鱼群鸟群) 算法_第1页
自然计算模型系列之 粒子群( 鱼群鸟群) 算法_第2页
自然计算模型系列之 粒子群( 鱼群鸟群) 算法_第3页
自然计算模型系列之 粒子群( 鱼群鸟群) 算法_第4页
自然计算模型系列之 粒子群( 鱼群鸟群) 算法_第5页
已阅读5页,还剩74页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

先进计算模型(2)自然计算模型系列之

粒子群(

鱼群/鸟群)算法四川大学计算机学院2009博士生课程(遗传算法,基因表达式编程,粒子群算法(PSO),蚁群算法,鱼群算法,….)唐常杰

四川大学计算机学院2023/9/271目录,大致计划第一次自然计算模型系列1:概述篇自然计算模型系列2粒子群(

鱼群/鸟群)算法自然计算模型系列3基因表达式编程第二次自然计算模型系列4:模拟退火算法自然计算模型系列5:蚁群算法自然计算模型系列6:免疫计算模型(思路和比喻)下载URL:校园网和学院网

/~chjtang/teach/tang_teaching.htm7/~tangchangjie/teach/tang_teaching.htm2023/9/272今天

自然计算模型(NatureComputing)概述GEP基因表达式编程PSO

粒子群算法鱼群鸟群算法下一次蚁群算法模拟退火算法人工免疫思想(比喻)

……

欢迎同学在下次发言(5-30分钟均可)(如A先讲,可跳至32页)提纲2023/9/273资料出处和致谢参考资料:本PPT仅作和同学们在讨论版内交流之用参考了若干教科书,文献和论文和报告。在末尾列出50多篇,但参考的文献不只这些,主要是遗传算法、基因表达式编程、粒子群算法的相关作者等等,包括国内外,校内外专家和本实验室成员的工作对未列出的文献作者也在此一并致谢。参考文献可能有遗漏,欢迎未列出的文献作者及时指出,,以便即时在参考文献中补充。作PPT类似于把小说改编为剧本,有重新创作的成分,也希望其它引用本PPT材料的标注本PPT2023/9/274欢迎指正我们在PSO方面的工作不多,难免疏漏:我们在PSO方面的工作不多,可能有疏漏,欢迎指正:

1张培颂,唐常杰,丁鑫鑫,徐开阔,“基于划分和重分布的粒子群算法及优化策略”,四川大学学报(自然科学版)Vol.44,No.2pp312-315,2007.4,ZHANGPei-song,TANGChang-jie,DINGXin-xin,XUKai-kuo,“AnImprovedParticleSwarmOptimizationBasedonDivisionandRedistribution”,JournalofSichuanUniversity(NaturalScienceEdition),Vol.44,No.2pp312-315,2007.42苏辉,唐常杰,乔少杰,徐开阔,张培颂,宋美娇“基于搜索空间划分和Sharing函数的粒子群优化算法”,四川大学学报(自然科学版)Vol.44,No.5pp985-989,2007.10,SUHui,TANGChang-jie,QiaoShao-jie,XUKai-kuo,ZHANGPei-song,SongMei-jiao“AnImprovedParticleSwarmOptimizationBasedonSearchSpaceDivisionandSharingFunction”,JournalofSichuanUniversity(NaturalScienceEdition),Vol.44,No.5pp985-989,2007.103倪胜巧,唐常杰,曾旭晟,乔少杰,曾春秋,"EAMode:一种新的基于引擎粒子系统的图像渲染模式",Vol.44No.6,Dec.2007.p1220-1224;NISheng-qiao,TANGChang-jie,ZENGXu-sheng,QIAOShao-jie,ZENGChun-qiu,"E&AMode:ANewModeforImageRomancingBasedonEngineParticlesSystem",JournalofSichuanUniversity(NaturalScienceEdition),Vol.44No.6,Dec.2007.p1220-12244QihongLiu,TiandeLi,ChangjieTang,QiweiLiu,JunZhu,XinxinDing,JiangWu:TwoPhaseParallelParticleSwarmAlgorithmbasedonRegionalandSocialStudyofObjectOptimization.ThirdInternationalConferenceonNaturalComputation,ICNC2007,Vol.3,Aug.2007,p:827~831.EI5丁鑫鑫唐常杰曾涛张培颂徐开阔刘齐宏,基于最佳粒子共享和分层搜索的并行粒子群优化算法tobepublished.2023/9/275课程计划和特点有多位(7-8位)博士生导师作专题讲座,每个老师讲课8小时(大约需要准备40—60小时)特点广---N位导师,N=8~9,N+

个领域,M个课题,(M>N).“N家讲座”,不敢比百家…新

---要求报告新技术前沿浅

–因为时间短,主要将思想,方法,介绍成果。不可能深入到公式和算法细节实---结合实际,结合博士生可能的选题2023/9/276

启发式搜索的方法,用于解决那些属于NP的比较困难的计算方法。对简单问题,可以确定算法解决的(如解一元二次方程)不要用这些方法。下面看一个实例任务请两同学去电脑城买一款性能价格比高的电脑启发式规则:人多力量大,三个臭皮匠,赛过诸葛亮带上上手机启发式搜索及示例2023/9/277

启发式搜索的方法,用于解决那些属于NP的比较困难的计算方法。对简单问题,可以确定算法解决的(如解一元二次方程)不要用这些方法。实例

请两同学

去电脑海洋城

买一款指定性能,价格低的电脑启发式规则:人多力量大,三个臭皮匠,赛过诸葛亮。

带上上手机,互通消息启发式搜索及示例2023/9/278“人多力量大”规则的启发下搜索比喻:两人带手机到电脑海洋城选购机器,货比多家

纵坐标价格这样搜索比穷举搜索快,不一定最好,(没有穷举)但比较快,比较好实际上这是是N=2的PSO,有见廉思齐的机制2023/9/279鸟群算法其他应用例子并发地搜山抓嫌疑人,并发地排查嫌疑人比喻,事件不同哲理同2023/9/2710

书归正传今天内容PSO之一:ParticleSwarmOptimization

PSO算法国际网站http:///2023/9/2711PSO:特点

1可看成是遗传算法家族的成员(或亲戚)sharesmanysimilaritieswithevolutionarycomputationsuchasGeneticAlgorithms(GA).

initializedwithapopulationofrandomsolutionssearchesforoptimabyupdatinggenerations.愚公移山2PSO=GA–(交叉+简单变异)+(见贤思齐的变异)unlikeGA,PSOhasnoevolutionoperatorssuchascrossoverandmutation.Solutions=particles,flythroughtheproblemspace

Byfollowingthecurrentoptimumparticles..紧跟头鸟

2一种说法

:PSO是GA的特例,简化,

后面看:是不是这样?PSO

2023/9/2712简介ParticleSwarmOptimization

解决优化问题的方法

传统搜寻方法如果问题是可计算,且是多项式复杂度的确定图灵机,确定算法,(参见可计算理论课程)保证能找到最佳解HeuristicSearch

启发性规则:有道理,不保证100%成功,可能含矛盾。三思而行(哪三思?危、变、退)当断不断反受其乱如森林中下山沿小溪

两条规则似乎矛盾2023/9/2713一种说法:一种说法:PSO=GA–(变异+交叉

)PSO是GA的特例,简化在遗传算法或GEP中去掉变异和交叉

后面看:是不是这样?2023/9/2714PSO先驱

RussellEberhart

(罗素爱伯罕?)RussEberhartRussellEberharteberhart@2023/9/2715PSO先驱

JamesKennedy

(詹姆斯,肯尼迪?)JamesKennedyJamesKennedyKennedy_Jim@2023/9/2716PSO外师物化(启发),内得心源(灵感)生物学家对鸟(鱼)群觅食的行为研究社会行为(Social-OnlyModel)认知模型(Cognition-OnlyModel)什么行为?且看下页分解2023/9/2717观察家里鱼缸:一条鱼(当前的带头鱼,通常是老鱼)发现食物

,其他的(通常是新鱼)同伴能感知声波,..养鱼能发现算法,不是玩物丧志!

2023/9/2718问题鱼群鸟群都是低智能动物,人比鱼群、鸟群高了很多层次,人群中高智能的计算机科学家去模拟低智能动物,不是见贤思齐,而是,见低思齐,礼贤下”物“,值得吗,有用吗?答案值得。看下面细细道来。2023/9/2719问题鱼群鸟群都是低智能动物,人比鱼群、鸟群高了很多层次,人群中高智能的计算机科学家去模拟低智能动物,不是见贤思齐,而是,见低思齐,礼贤下”物“,值得吗,有用吗?答案:值得。且看下面细细道来。2023/9/2720你们把观察的现象形式化吗?建立模型,抽象化,粒子群特性看看现象,你们把观察的现象形式化吗?提示:一群鸟在觅食2023/9/2721寻优问题

解

想象成一只鸟(鱼),称Particle每个Particle都有记忆性所有的Particle都透过FitnessFunction以判断目前的位置之好坏每个Particle透过Velocity(速度)Function以决定移动的距离与方向建立模型,抽象化,2023/9/2722鸟(鱼)有记忆鸟(鱼)能比较鸟(鱼)可通讯(广播)鸟(鱼)会学习

向好鸟(鱼)学习,见异思迁(有点贬义)见贤思齐从善如流

(褒义)

追尾行为,一条鱼发现食物时,伙伴会尾随算法思想:模拟鸟(鱼)觅食、聚群和追尾行为写论文时,写观察不需要证明,大多数情况下成立,能解决问题,就有用几个观察或假定2023/9/2723鸟(鱼)有记忆鸟(鱼)能比较鸟(鱼)可通讯(广播)鸟(鱼)会学习

向好鸟(鱼)学习,见异思迁(有点贬义)见贤思齐从善如流

(褒义)

追尾行为,一条鱼发现食物时,伙伴会尾随算法思想:模拟鸟(鱼)觅食、聚群和追尾行为写论文时,写观察不需要证明,大多数情况下成立,能解决问题,就有用几个观察或假定2023/9/2724算法思想模拟鸟(鱼)觅食、聚群和追尾行为找食不如找带头鸟(动态带头鸟,可罢免、重选),追随领袖(或邻域中领袖,部落酋长)跟踪两个“极值”来更新自己。

自己的经验:自己历史上最优解个体极值pBest.

全局经验和部落经验:gBest。另(邻居极值)向领袖学习,见贤思齐,从善如流,不断更新自己2023/9/2725鸟(鱼)有记忆鸟(鱼)能比较向好鸟(鱼)学习,见异思迁,从善如流写论文时,写观察不需要证明,观察结论在大多数情况下成立,能解决以大批问题,有用从观察到理论,是实验科学的研究方法三个观察或假定2023/9/2726分隔规则,尽量避免与临近伙伴过于拥挤对准规则,尽量与临近伙伴的平均方向一致;内聚规则,尽量朝临近伙伴的中心移动。追尾行为当鱼群中的一条或几条鱼发现食物时,其临近的伙伴会尾随其快速到达食物点。更多的观察或假定2023/9/2727PSO的主要步骤

遗传算法-编译-交叉Initialize

初始化Evaluation评价FindthePbest

单个粒子迄今最佳位置(有历史观)FindtheGbest

UpdatethePosition

更新回到Evaluation继续執行,符合終止条件成立2023/9/2728PSO的主要步骤

遗传算法-编译-交叉Initialize

初始化Evaluation评价FindthePbest

单个粒子迄今最佳位置(有历史观)FindtheGbest

UpdatethePosition

更新回到Evaluation继续執行,符合終止条件成立2023/9/2729PSO的主要步骤

遗传算法-编译-交叉Initialize

初始化Evaluation评价FindthePbest

单个粒子迄今最佳位置(有历史观)FindtheGbest

UpdatethePosition

更新回到Evaluation继续執行,符合終止条件成立2023/9/2730PSO的主要步骤

遗传算法-编译-交叉Initialize

初始化Evaluation评价FindthePbest

单个粒子迄今最佳位置(有历史观)FindtheGbest

UpdatethePosition

更新回到Evaluation继续執行,符合終止条件成立2023/9/2731PSO的主要步骤

遗传算法-编译-交叉Initialize

初始化Evaluation评价FindthePbest

单个粒子迄今最佳位(有历史)FindtheGbest

UpdatethePosition

更新循环到Evaluation,知道符合終止条件成立2023/9/2732PSO的初始化随机设置每Particle之初始位置与速度2023/9/2733PSO的适应度评价用

FitnessFunction计算出其FitnessValue判断每一Particle之好坏初步印象:技术比GEP简单,功能能可能也差一些)2023/9/2734FindthePbest—单个粒子优化找出每个Particle到目前为止的搜寻过程中最佳解(迄今的觅食的最佳速度和位置,鸟能记忆和比较),称为PbestP--pastPastBestSolution注意这里局部优化2023/9/2735FindtheGbest高度表示得分多少。山峰处得分高找出所有Particle到目前為止全局最优解,记为GbestGlobalBestSolutionPastBestSolution注意这里2023/9/2736PSO更新

(相当于遗传算法的新的一代,进化)更新位置(从善若流,与时俱进,调整自己)依VelocityFunction更新每Particle的移动方向与速度回Evaluation步骤继续,直到符合終止条件2023/9/2737PSO流程(与遗传算法相比,少了变异和交叉)比喻为遗传算法的新生一代,相当于凤凰涅槃2023/9/2738PSOVelocityFunction

速度函数的构成Cognition-OnlyModelPSOVelocityFunctionSocial-OnlyModel||+两个分量主观的客观的2023/9/2739插曲:一个有趣的比喻三国时,群雄并起,很多粒子:曹操,孙权,类被,袁绍….,他们要觅食(地盘和资源)许邵评论曹操用了一个先天歧义的句子两个分量都有a3许邵评曹操:乱世奸雄治世能臣

乱世奸雄治世能臣现在回到PSO现实中状语:表达客观条件(社会模型)决定人人生动宾结构:表达主观愿望(认知模型)决定人生2023/9/2740插曲:一个有趣的比喻三国时,群雄并起,很多粒子:曹操,孙权,类被,袁绍….,他们要觅食(地盘和资源)许邵评论曹操用了一个先天歧义的句子两个分量都有a3许邵评曹操:乱世奸雄治世能臣

乱世奸雄治世能臣问题:能否用他描述或部分地描述三国群英?难,要简化模型现在回到PSO现实中状语:表达客观条件(社会模型)决定人人生动宾结构:表达主观愿望(认知模型)决定人生2023/9/2741PSOVelocityFunction(后面有动画演示)认知模型Cognition-OnlyModelVid:第i个particle(有d个维度)之速度Pid:该

particle到目前为止所出现的最佳位置Xid:该

particle目前之所在位置C1:学习常数rand():0~1之间的随机数速度的增量旨在弥补与先进的差距与先进的差距2023/9/2742社会模型Social-OnlyModelVid:第i个particle(有d个维度)之速度Pgd:所有

particle到目前为止所出现的最佳位置Xid:该

particle目前之所在位置C2:学习常数rand():0~1之间的随机数PSOVelocityFunction(后面有动画演示)速度的增量旨在弥补与先进的差距与先进的差距与上页不同点2023/9/2743

Vid:第i个particle(d维)速度

Pid:每个particle迄今出现的最佳位置

Pgd:所有particle迄今最佳位置

Xid:每个particle目前位置 C1,C2:学习常数

w:惯性权重 rand():0~1之间随机数PSOVelocityFunction(后面有动画演示)个体认知模型(主观)社会模型(客观)2023/9/2744區域最佳解全域最佳解运动向量惯性向量动画演示动能向量

StudyFactorHereIam!ThebestpositionofteamMybestpositionxpgpivPBestgBest2023/9/2745鸟(鱼)有记忆鸟(鱼)能比较,会总结向好鸟(鱼)学习,见贤思齐不但从善如流,还能统筹兼顾局部经验和全局经验上页的演示确实说明了这三点(必要时重新演示一次)复习:三个观察或假定2023/9/2746鸟(鱼)有记忆鸟(鱼)能比较,会总结向好鸟(鱼)学习,从善如流不但从善如流,还能统筹兼顾局部经验和全局经验上页的演示确实说明了这三点(必要时重新演示一次)复习:三个观察或假定2023/9/2747PSO算法

I)Foreachparticle:InitializeparticleII)Do:

a)Foreachparticle:

1)Calculatefitnessvalue

2)Ifthefitnessvalueisbetterthanthebestfitnessvalue(Pbest) inhistory

3)SetcurrentvalueasthenewPbest

End

b)Foreachparticle:

1)Findintheparticleneighborhood,theparticlewiththebest fitness2)Calculateparticlevelocityaccordingtothevelocityfunction3)UpdateparticlepositionaccordingtothepositionfunctionEnd

Whilemaximumiterationsorminimumerrorcriteriaisnotattained

初始化计算个体适应度总结,自己纵向比较2023/9/2748PSO算法

I)Foreachparticle:InitializeparticleII)Do:

a)Foreachparticle:

1)Calculatefitnessvalue

2)Ifthefitnessvalueisbetterthanthebestfitnessvalue(Pbest) inhistory

3)SetcurrentvalueasthenewPbest

End

b)Foreachparticle:

1)Findintheparticleneighborhood,theparticlewiththebest fitness2)Calculateparticlevelocityaccordingtothevelocityfunction3)UpdateparticlepositionaccordingtothepositionfunctionEnd

Whilemaximumiterationsorminimumerrorcriteriaisnotattained

吸取历史经验计算个体适应度总结,自己纵向比较,2023/9/2749PSO算法

I)Foreachparticle:InitializeparticleII)Do:

a)Foreachparticle:

1)Calculatefitnessvalue

2)Ifthefitnessvalueisbetterthanthebestfitnessvalue(Pbest) inhistory

3)SetcurrentvalueasthenewPbest

End

b)Foreachparticle:

1)Findintheparticleneighborhood,theparticlewiththebestfitness

2)Calculateparticlevelocityaccordingtothevelocityfunction3)UpdateparticlepositionaccordingtothepositionfunctionEnd

Whilemaximumiterationsorminimumerrorcriteriaisnotattained

横向比较,找适应度最好的邻居或部落领袖见贤思齐2023/9/2750PSO算法

I)Foreachparticle:InitializeparticleII)Do:

a)Foreachparticle:

1)Calculatefitnessvalue

2)Ifthefitnessvalueisbetterthanthebestfitnessvalue(Pbest) inhistory

3)SetcurrentvalueasthenewPbest

End

b)Foreachparticle:

1)Findintheparticleneighborhood,theparticlewiththebestfitness

2)Calculate

particlevelocityaccordingtothevelocityfunction

3)Updateparticlepositionaccordingtot

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论