第七章 粒子群优化算法.

Slides:



Advertisements
Similar presentations
元大京華證券 組員名單 : A 楊之奇 A 廖本揚 A 宋俊承 A 陳冠廷 A 郭峻瑋 A 指導教授 : 許素華 副教授.
Advertisements

達悟族報告 作者 : 林琪崴, 許原碩 座號 :13 號,14 號 原碩負責 : 簡介, 傳說, 圖驣, 達悟族飛魚季, 琪崴 : 地理位置, 土地利用方式, 飲食文化, 豐收祭.
主讲:张天明 影像艺术工程师. 声音的聆听 指出听到的是什么物体发出的声音,这一 声音是在什么样的空间环境中传播的。 一、 答案: 1 、打气筒打气的声音 2 、手打打气筒给足球打气的声音 3 、手打打气筒给自行车轮胎打气的声音 4 、七次(七声)打气筒打气的声音 5 、(气流)摩擦的声音 6 、猪在发急时的叫声.
概念導向命題技巧與試題分析 臺灣師大地理系 陳國川. 教學評量是一種『抽樣調查』 實施教學評量時,需具備二項條件: 其一,瞭解命題的理論及其實踐的方法; 其二,瞭解各種題型的功能與命題方式。 壹、前言.
第十八章 林肯大郡 第十八章 林肯大郡災變緊急搶救應變措施 1997 年 8 月 18 日溫妮颱風襲台,汐止鎮 的林肯大郡山崩,遭崩場土石撞擊 1997 年 8 月 18 日溫妮颱風襲台,汐止鎮 的林肯大郡山崩,遭崩場土石撞擊造成二十八人罹難八十戶住宅倒塌的慘劇 此災變要喚起國人的重視 本章介紹搜救行動緊急應變措施。
高峰植物園行前解說 2005/12/07 By 羽明. 陽性先驅物種 陽性植物 --- 陽光需求量大 陰性 ( 或耐蔭性 ) 植物 --- 陽光需求量少, 或 日照太強反而無法生存 先驅植物 --- 森林大火或土石流地震後產生的 裸露空地, 先生長出來的植物.
報 告 人 : 胡 嘉 琪 ˙ˇ˙ 、 王 紫 庭 = ˇ = 台灣夜市文化 作者: 郭明澤‧私立明道高中‧綜二 4 班 馬炯修‧私立明道高中‧綜二 4 班.
5 ˙ 1 第五章 生物的協調作用 5 ‧ 1 神經系統. 5 ˙ 1 人體的神經系統 1. 協調動物生理反應的系統: 神經 系統、 內分 泌 系統。 2. 神經系統負責 統整 和 協調 。分為 中樞 神經 和 周圍 神經。 (1) 中樞神經包括 腦 和 脊髓 。 (2) 周圍 神經包括 腦神經 和.
index 目次 ( 請按一下滑鼠,解答就會出現喔 !) 接續下頁解答 3-1 極限的概念.
从《西游》看大学生的成长 主讲人:颜廷学 时间: 地点:演艺大楼流行剧场.
新员工培训 设计部 思安新能源股份有限公司 主讲人: 韩少华 时 间:
前言:河流的主要功能 1. 交通運輸 優點-運費低廉,維護費用低 缺點-速度慢,裝載費時,不能到達生產區或消費區 的末端,需要轉載。 尚受到河流網路,河口位置,水量變化,河床 狀況,冰封時期 2. 水資源系統.
幽夢影~張潮 小佑子工作室 關於《幽夢影》 作者張潮,記寫他個人對人生世事之體驗透悟的 書。 書中文字,全為「語錄」形式,屬於格言,也是 最精鍊的隨筆。 全書可分為九卷:論才子佳人、論人與人生、論 朋友知己、論讀書、論閒情逸趣、論立身處世、 談文論藝、論四時佳景、論花鳥蟲魚。
成人高考高起点 语文 冲刺班 主讲老师:邓君媚. 复习指导 高考语文含四大块内容: 语言知识和语言表达,古代诗文阅读,现 代文阅读,写作。 在全面复习的前提下,按照《考试大纲》 的要求,要做好思路整理,建立高考的整体框 架的工作。认真归纳整理基础知识、培养基本 能力,复习做到有的放矢。 复习指导.
老师,我可以不 爱 吗? 山东省淄博市张店区实验中学 杜桂兰 星期一的早晨,我紧张而又兴奋,因为 我的赛教课就要开始了。 这是一次级别很 高 的竞赛。
财政部 国家税务总局 中国人民银行(央行) 银监会 证监会 保监会. 法定存款准备金率 利率 税率 政府投资 楼继伟,周小川,易纲.
油蔴菜籽 指導老師:陳瑜霞 學生: 商設一甲 謝旻璇 車輛三乙 許勝傑 工管四甲 彭凱雲. 作者介紹: 廖輝英( 1948 年生)臺大中文系畢業。 從初三開始寫作,早期作品多以散文為主,大四 畢業時才暫時封筆。畢業後進了廣告界,成為廣 告文案好手,後為企畫主管,在廣告界縱橫十餘 年,也曾任職於建設公司,辦過社區報高雄一周。
蘭嶼情人洞傳說 林庭羽製 林庭羽製. 台灣的蘭花特別多,台灣有個蘭 嶼島,島上面的蘭花更多.所以 叫蘭嶼.這裡留下了動人的傳說。
職業訪談報告. 成員 : 鐘怡君 劉沛君 謝明達 賴映辰.
南台科大幼保實習課程 見習幼兒園心得報告 夜四技幼保四甲 998i0021 黃欣婷.
第一章 生殖 1‧2 無性生殖.
高教三十条 — 科技创新能力提升 科技创新能力提升工程方案起草小组 2013年7月4日.
你不可不知之 十二年國教二三事 教務主任:傅瑞琪.
鞋 楦 的 材 質.
最古怪的15種動物.
走! 一起去拜訪筏子溪.
台灣文學館之旅.
單車環島之旅 組員: 495D0072 胡閎智 495D0074 何冠緯 495D0020 王怡雯 495D0047 葉亭君
 耕地分割 及 執 行 內政部地政司 視察:林玲女.
~完備、周密、迅速 ~ 行政院農業部畜產試驗所
建筑设计基础讲义 (02-1) 建筑水彩渲染.
現代文學導讀 (中國現代散文發展的歷史軌道)
谨以此文—— 送给所有的人.
方 孝 孺 指喻.
保護地球人人有責:我能做的事 若想讓地球、人類社會明天會更好的話,可以考慮日常生活中採取什麼綠色行動,逐步恢復按上天設計大自然規定的方式做人,從而減少個人的「生態足印」,爭取可以延續的未來。 
小 王 子 <第六組> 組長: 謝汶芳 組員: 劉佳蓉 曹展愛 陳建妏
據說: 烏鴉有四種--- 巨烏 祥烏 鳳烏 慈烏~ 知恩 感恩 報恩.
桃園傅小弟遭刺青施虐事件 指導老師:高家斌 班級:幼保四甲 姓名與學號: 496I0004 程千芸、496I0010 林昀嫻
北科大學士學位 冷凍空調 甲、乙、丙 級技術士 三年工作經驗 大一階段 專精訓練 大三階段 回流訓練.
9.2.2 会计基本法律制度 一、会计机构和会计人员制度 二、会计核算制度
指導教授:林劭仁老師 組員:范紋綺、王宣惠、蔡雅玲 王思樺、陳可馨、吳芷容.
歡欣鼓舞過新年之四-跟年有關的故事 蘇澳國小 三年三班導師 張怡玲.
淺談中醫養生保健之道 國立中正大學醫務室 中醫科 楊明穎 醫師 中國醫藥學院 醫學士中醫師 高雄醫學院 藥學士藥師
日期: 六 福 村.
物流系统的目标.
关于在宝钢全体党员中开展“学党章党规、 学系列讲话,做合格党员”学习教育的 实施方案
爱的表达方式.
?????? ?????? ?????? 他是我生的 我愛怎樣就怎樣 這樣對嗎? 影片欣賞.
牛 奔 生物启发式优化方法 及其在管理中的应用
第十章 运动训练基础 康复教研室:安乐.
第六章 社会主义初级阶段理论 第一节 社会主义初级阶段是我国最大的实际 第二节 社会主初级阶段的基本路线和基本纲领
我的社區_觀塘 第三課.
他是一位叱咤风云的人物,一位毁誉参半的领袖。
做最好的自己 ——七(6)班主题班会.
作者:碧.威爾森(Bee Wilson) 出版社:八旗文化
大肚宮廟巡禮 下一頁.
第三章 搜索技术 第一节 引言 一、搜索 对于无成熟方法可用的问题求解,必须一步步地摸索求解,这种问题求解过程就是搜索。
大嶼山 香港國際機場 及 寶蓮寺.
第Ⅱ部分 问题求解 第4章 超越经典搜索 中国科大 计算机学院.
Particle Systems 粒子系统 李博杰 PB
人生哲理 每一句話都充滿著智慧,值得和朋友們分享、共勉~ <每隔 6 秒,自動換頁 !!>
Particle Swarm Optimization Xidian University, Xi’an, China © 2005
第二章 基本遗传算法(GA) 2.1 基本遗传算法描述 基本遗传算法的构成要素 (1) 染色体编码方法
Particle Swarm Optimization(PSO)
105學年度 服務學習教育說明會 Service Learning.
遊戲設計 Special Effects.
第二章 基本遗传算法(GA) 2.1 基本遗传算法描述 基本遗传算法的构成要素 (1) 染色体编码方法
全台灣最美的日出好美…好美… 這就是傳說中的潑墨二寮,耳聞她的日出有如國畫般 所以稱為潑墨二寮
研究方向及之相關主題介紹 徐培倫 研究室:電資學院 D719室 年8月6日.
轉換成二進位、八進位及十六進位 = ( ) = ( ) = ( )16.
Presentation transcript:

第七章 粒子群优化算法

第七章 粒子群优化算法 一.前言 二.基本算法 三.标准算法 四.PSO的改进与变形 五.学习PSO的几点体会

一.前言 PSO的产生 Particle Swarm Optimization(PSO),粒子群优化或者微粒群优化 PSO算法由美国学者Kennedy (社会心理学家)和Eberhart(电机工程师) 于1995年提出,通过模拟鸟群和鱼群的社会交互行为而不仅仅依赖个体认知行为而设计的一种智能优化方法 Kennedy

一.前言 PSO的产生 2000年以后,PSO算法在国际上逐步被接受,并有大批不同领域的学者投入该算法相关研究,已经成为智能优化领域研究的热门算法 2003年,《控制与决策》第二期刊登国内第一篇综述性文章

一.前言 PSO的基本思想 对社会行为的模拟 对鸟群行为的模拟:Reynolds和Heppner,Grenander在1987年和1990年发表的论文中都关注了鸟群群体行动中蕴涵的美学。他们发现,由数目庞大的个体组成的鸟群飞行中可以改变方向,散开,或者队形的重组等等,那么一定有某种潜在的能力或者规则保证了这些同步的行为。这些科学家都认为上述行为是基于不可预知的鸟类社会行为中的群体动态学。在这些早期的模型中他们把重点都放在了个体间距的处理,也就是让鸟群中的个体之间保持最优的距离。

一.前言 PSO的基本思想 对社会行为的模拟 对鱼群行为的研究:1975年,生物社会学家Wilson在论文中阐述了对鱼群的研究。他在论文中提出:“至少在理论上,鱼群的个体成员能够受益于群体中其他个体在寻找食物的过程中发现的和以前的经验,这种受益是明显的,它超过了个体之间的竞争所带来的利益消耗,不管任何时候食物资源不可预知的分散于四处。”这说明,同种生物之间信息的社会共享能够带来好处。

一.前言 PSO的基本思想 对社会行为的模拟 对人类的社会行为的模拟: a. 与前者不同,最大区别在于抽象性! b. 鸟类和鱼类是调节他们的物理运动,来避免天敌, 寻找食物,优化环境的参数,比如温度等。人类调节 的不仅是物理运动,还包括认知和经验。我们更多的 是调节自己的信仰和态度,来和社会中的杰出人物或 者专家,或者在某件事情上获得最优解的人保持一致。

一.前言 PSO的基本思想 对社会行为的模拟 对人类的社会行为的模拟: c. 这种不同导致了计算机仿真上的差别,至少有一个 明显的因素:碰撞(collision)。 d. 两个个体即使不被绑在一块,也具有相同的态度和 信仰,但是两只鸟是绝对不可能不碰撞而在空间中占 据相同的位置。这是因为动物只能在三维的物理空间 中运动,而人类还在抽象的多维心理空间运动,这里 是碰撞自由的(collision-free)。

一.前言 PSO的基本思想 采纳基于种群(swarm)的机制 个体(particle)均是问题的一个潜在解 算法寻优依赖于在种群拓扑结构上个体间的社会交互行为

一.前言 名称的由来:Swarm和Particle Swarm:在美国传统字典中有三个意思 一大群尤指正在行进中的一大群昆虫或其它细小生物 蜂群由蜂王带领迁移到别处建立一新据点的一群蜜蜂 一大群尤指处于骚乱中或成群出动的一大批喧闹的人或动物 作者引用此词是借用了Millonas在1994年的论文中的人工生命的一个应用模型中的提法

一.前言 名称的由来:Swarm和Particle Particle: 算法中有速度和加速度的字眼,这比较适合于粒子。Reeves在1983年的论文中讨论了粒子系统包括基本粒子团和云、火、烟雾等弥漫性物体 作者的想法是让粒子尽量具有一种普遍性的意义 用粒子在超空间(Hyperspace)的飞行来模拟个体的社会性行为

二.基本算法 算法描述 种群中m个个体分布在一个D维搜索空间中 每个个体均具有当前位置、速度以及历史最优位置三个属性 种群具有一定的拓扑结构,个体可以基于种群拓扑结构与其邻域内的其他个体进行相互作用 算法迭代时,每个个体会根据自身信息(认知行为)和邻域内其他个体的信息(社会行为)进行状态更新

二.基本算法 基本PSO的公式 Index 粒子i 粒子群

二.基本算法 基本PSO的公式 (1) (2)

二.基本算法 基本PSO的公式 c1和c2:学习因子(learning factor)或加速系数(acceleration coefficient),一般为正常数。学习因子使粒子具有自我总结和向群体中优秀个体学习的能力,从而向自己的历史最优点以及群体内或邻域内的历史最优点靠近。通常等于2。 ξ和η:0-1之间的随机数

二.基本算法 基本PSO的公式 粒子的速度被限制在[-Vmax, Vmax]的范围内。引入Vmax的原因: 防止溢出 保证算法稳定

二.基本算法 基本PSO的公式 粒子群的拓扑结构决定个体间的相互影响程度 PSO的全局版本将整个群体看作是一个全连通图,群体内所有个体共享一个邻域最优 gbest PSO的局部版本中每个个体的邻域将是整个群体的一个子集,此时影响个体的gbest取决于具体的拓扑结构,一种简单的方法是群体内粒子根据其编号相邻的原则组成一个环状结构

二.基本算法 基本PSO算法流程图 begin initialize and evaluate a swarm of particles with random positions and velocities on D dimensions in the search space; repeat for each particle i do update gbest of particle i; endfor adapt the velocity of particle i using Equation (1); update the position of particle i using Equation (2); evaluate the fitness of particle i; update pbest of particle i; until a stop condition is met end

三.标准PSO 带有惯性权重的PSO 为改善算法收敛性能,Shi和Eberhart在1998年的论文中引入了惯性权重的概念,将速度更新方程修改为: (3)

三.标准PSO 带有惯性权重的PSO 这里,w称为惯性权重,其大小决定了对粒子当前速度继承的多少,合适的选择可以使粒子具有均衡的探索和开发能力。可见,基本PSO算法是惯性权重w=1的特殊情况。 分析和实验表明,设定Vmax的作用可以通过惯性权重的调整来实现。现在的PSO基本上使用Vmax进行初始化,将Vmax设定为每维变量的变化范围,而不必进行细致的选择与调节。

四.PSO的改进与变形 带有收缩因子的PSO 2002年Clerc和Kennedy在基本PSO算法中引入可收缩因子的概念,指出该因子对于算法的收敛是必要的,将速度更新公式修改为: 其中, (4)

四.PSO的改进与变形 带有收缩因子的PSO Clerc将参数取值为: 则 若带有惯性权重的PSO采用如下的参数设置:

三.标准PSO 计算举例 求解无约束优化问题:5维的Rosenbrock函数

三.标准PSO 计算举例 简单分析: Rosenbrock是一个著名的测试函数,也叫香蕉函数,其特点是该函数虽然是单峰函数,在[100,100]n上只有一个全局极小点,但它在全局极小点临近的狭长区域内取值变化极为缓慢,常用于评价算法的搜索性能。这种实优化问题非常适合于使用粒子群优化算法来求解。

三.标准PSO 计算举例 算法设计 编码:因为问题的维数为5,所以每个粒子为5维的实数向量。 初始化范围:根据问题要求,设定为[-30,30]。根据前面的参数分析,我们知道,可以将最大速度设定为Vmax=60。 种群大小:为了说明方便,这里采用一个较小的种群规模,m=5。 停止准则:设定为最大迭代次数100次。

三.标准PSO 计算举例 算法设计 惯性权重:采用固定权重0.5。 邻域拓扑结构:使用星形拓扑结构,即全局版本的粒子群优化算法。

三.标准PSO 计算举例 一次迭代后的结果

三.标准PSO 计算举例 一次迭代后的结果 从上面的数据我们可以看到,粒子有的分量跑出了初始化范围。需要说明的是,在这种情况下,我们一般不强行将粒子重新拉回到初始化空间,即使初始化空间也是粒子的约束空间。因为,即使粒子跑出初始化空间,随着迭代的进行,如果在初始化空间内有更好的解存在,那么粒子也可以自行返回到初始化空间。 有研究表明,即使将初始化空间不设定为问题的约束空间,即问题的最优解不在初始化空间内,粒子也可能找到最优解。

三.标准PSO 计算举例

四.PSO的改进与变形 惯性权重 固定权重 即赋予惯性权重以一个常数值,一般来说,该值在0和1之间。固定的惯性权重使粒子在飞行中始终具有相同的探索和开发能力。显然,对于不同的问题,获得最好优化效果的这个常数是不同的,要找到这个值需要大量的实验。通过实验我们发现:种群规模越小,需要的惯性权重越大,因为此时种群需要更好的探索能力来弥补粒子数量的不足,否则粒子极易收敛;种群规模越大,需要的惯性权重越小,因为每个粒子可以更专注于搜索自己附近的区域。

四.PSO的改进与变形 惯性权重 时变权重 一般来说,希望粒子群在飞行开始的时候具有较好的探索能力,而随着迭代次数的增加,特别是在飞行的后期,希望具有较好的开发能力。所以希望动态调节惯性权重。可以通过时变权重的设置来实现。设惯性权重的取值范围为: 最大迭代次数为Iter_max,则第i次迭代时的惯性权重可以取为:

四.PSO的改进与变形 惯性权重 模糊权重 模糊权重是使用模糊系统来动态调节惯性权重。下面的文献给出了一种模糊权重的设置方式 Shi Y, Eberhart R. Fuzzy adaptive particle swarm optimization: IEEE Int. Congress on Evolutionary Computation [C]. Piscataway, NJ: IEEE Service Center, 2001: 101-106.

四.PSO的改进与变形 惯性权重 随机权重 随机权重是在一定范围内随机取值。例如可以取值如下: 其中,Random为0到1之间的随机数。这样,惯性权重将在0.5到1之间随机变化,均值为0.75。

四.PSO的改进与变形 邻域拓扑结构 基于索引号的拓扑结构 环形结构

四.PSO的改进与变形 邻域拓扑结构 基于索引号的拓扑结构 星形结构:每个粒子都与种群中的其他所有粒子相连,即将整个种群作为自己的邻域。也就是粒子群算法的全局版本。这种结构下,所有粒子共享的信息是种群中表现最好的粒子的信息。

四.PSO的改进与变形 邻域拓扑结构 基于距离的拓扑结构 基于距离的拓扑结构是在每次迭代时,计算一个粒子与种群中其他粒子之间的距离,然后根据这些距离来确定该粒子的邻域构成。 一种动态邻域拓扑结构:在搜索开始的时候,粒子的邻域只有其自己,即将个体最优解作为邻域最优解,然后随着迭代次数的增加,逐渐增大邻域,直至最后将群体中所有粒子作为自己的邻域成员。这样使初始迭代时可以有较好的探索性能,而在迭代后期可以有较好的开发性能。

四.PSO的改进与变形

四.PSO的改进与变形 学习因子 c1和c2同步时变

四.PSO的改进与变形 学习因子 c1和c2异步时变

四.PSO的改进与变形 学习因子 c1和c2异步时变 在优化的初始阶段,粒子具有较大的自我学习能力和较小的社会学习能力,这样粒子可以倾向于在整个搜索空间飞行,而不是很快就飞向群体最优解; 在优化的后期,粒子具有较大的社会学习能力和较小的自我学习能力,使粒子倾向于飞向全局最优解。

四.PSO的改进与变形

五.学习PSO的几点体会 收敛很快的算法 解决约束优化问题时,如何处理飞出约束域的粒子是个关键 较为适用于求解实优化问题