粒子群優(yōu)化算法詳細(xì)易懂很多例子

1、粒子群優(yōu)化算法詳細(xì)易懂很多例子第1頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二智能算法向大自然學(xué)習(xí)遺傳算法(GA)物競(jìng)天擇，設(shè)計(jì)染色體編碼，根據(jù)適應(yīng)值函數(shù)進(jìn)行染色體選擇、交叉和變異操作，優(yōu)化求解人工神經(jīng)網(wǎng)絡(luò)算法(ANN)模仿生物神經(jīng)元，透過(guò)神經(jīng)元的信息傳遞、訓(xùn)練學(xué)習(xí)、聯(lián)想，優(yōu)化求解模擬退火算法(SA)模模仿金屬物質(zhì)退火過(guò)程第2頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二解決最優(yōu)化問(wèn)題的方法傳統(tǒng)搜索方法保證能找到最優(yōu)解Heuristic Search不能保證找到最優(yōu)解第3頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二 由Kennedy和Eberhart于1

2、995年提出 群體迭代，粒子在解空間追隨最優(yōu)的粒子進(jìn)行搜索. 簡(jiǎn)單易行 粒子群算法: 收斂速度快 設(shè)置參數(shù)少 已成為現(xiàn)代優(yōu)化方法領(lǐng)域研究的熱點(diǎn)粒子群算法發(fā)展歷史簡(jiǎn)介 第4頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二粒子群算法的基本思想粒子群算法的思想源于對(duì)鳥群捕食行為的研究模擬鳥集群飛行覓食的行為，鳥之間通過(guò)集體的協(xié)作使群體達(dá)到最優(yōu)目的，是一種基于Swarm Intelligence的優(yōu)化方法。馬良教授在他的著作蟻群優(yōu)化算法一書的前言中寫到：大自然對(duì)我們的最大恩賜！“自然界的蟻群、鳥群、魚群、羊群、牛群、蜂群等，其實(shí)時(shí)時(shí)刻刻都在給予我們以某種啟示，只不過(guò)我們常常忽略了大自然對(duì)我們

3、的最大恩賜！.”第5頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二第6頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二粒子群算法的基本思想 設(shè)想這樣一個(gè)場(chǎng)景：一群鳥在隨機(jī)搜索食物 在這塊區(qū)域里只有一塊食物; 所有的鳥都不知道食物在哪里; 但它們能感受到當(dāng)前的位置離食物還有多遠(yuǎn). 已知那么:找到食物的最優(yōu)策略是什么呢？ 搜尋目前離食物最近的鳥的周圍區(qū)域 根據(jù)自己飛行的經(jīng)驗(yàn)判斷食物的所在。PSO正是從這種模型中得到了啟發(fā) PSO的基礎(chǔ): 信息的社會(huì)共享 第7頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二生物學(xué)家對(duì)鳥(魚)群捕食的行為研究社會(huì)行為 (Social-O

4、nly Model)個(gè)體認(rèn)知 (Cognition-Only Model)第8頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二粒子群特性第9頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二算法介紹 每個(gè)尋優(yōu)的問(wèn)題解都被想像成一只鳥，稱為“粒子”。所有粒子都在一個(gè)D維空間進(jìn)行搜索。所有的粒子都由一個(gè)fitness function 確定適應(yīng)值以判斷目前的位置好壞。每一個(gè)粒子必須賦予記憶功能，能記住所搜尋到的最佳位置。每一個(gè)粒子還有一個(gè)速度以決定飛行的距離和方向。這個(gè)速度根據(jù)它本身的飛行經(jīng)驗(yàn)以及同伴的飛行經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)調(diào)整。 第10頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14

5、分，星期二粒子群優(yōu)化算法求最優(yōu)解 D維空間中，有N個(gè)粒子； 粒子i位置：xi=(xi1,xi2,xiD)，將xi代入適應(yīng)函數(shù)f(xi)求適應(yīng)值； 粒子i速度：vi=(vi1,vi2,viD) 粒子i個(gè)體經(jīng)歷過(guò)的最好位置：pbesti=(pi1,pi2,piD) 種群所經(jīng)歷過(guò)的最好位置：gbest=(g1,g2,gD)通常，在第d（1dD）維的位置變化范圍限定在 內(nèi)， 速度變化范圍限定在 內(nèi)（即在迭代中若 超出了邊界值，則該維的速度或位置被限制為該維最大速度或邊界 位置） 第11頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二粒子i的第d維速度更新公式： 粒子i的第d維位置更新公式：

6、第k次迭代粒子i飛行速度矢量的第d維分量 第k次迭代粒子i位置矢量的第d維分量 c1,c2加速度常數(shù)，調(diào)節(jié)學(xué)習(xí)最大步長(zhǎng) r1,r2兩個(gè)隨機(jī)函數(shù)，取值范圍0，1，以增加搜索隨機(jī)性 w 慣性權(quán)重，非負(fù)數(shù)，調(diào)節(jié)對(duì)解空間的搜索范圍第12頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二粒子速度更新公式包含三部分： 第一部分為粒子先前的速度 第二部分為“認(rèn)知”部分，表示粒子本身的思考，可理解為粒子i當(dāng)前位置與自己最好位置之間的距離。 第三部分為“社會(huì)”部分，表示粒子間的信息共享與合作，可理解為粒子i當(dāng)前位置與群體最好位置之間的距離。第13頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二

7、區(qū)域最佳解全域最佳解運(yùn)動(dòng)向量慣性向量 Study Factorpg第14頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二第15頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二算法流程Initial：初始化粒子群體（群體規(guī)模為n），包括隨機(jī)位置和速度。Evaluation：根據(jù)fitness function ，評(píng)價(jià)每個(gè)粒子的適應(yīng)度。Find the Pbest： 對(duì)每個(gè)粒子，將其當(dāng)前適應(yīng)值與其個(gè)體歷史最佳位置（pbest）對(duì)應(yīng)的適應(yīng)值做比較，如果當(dāng)前的適應(yīng)值更高，則將用當(dāng)前位置更新歷史最佳位置pbest。Find the Gbest：對(duì)每個(gè)粒子，將其當(dāng)前適應(yīng)值與全局最佳位置

8、（gbest）對(duì)應(yīng)的適應(yīng)值做比較，如果當(dāng)前的適應(yīng)值更高，則將用當(dāng)前粒子的位置更新全局最佳位置gbest。Update the Velocity：根據(jù)公式更新每個(gè)粒子的速度與位置。如未滿足結(jié)束條件，則返回步驟2 通常算法達(dá)到最大迭代次數(shù) 或者最佳適應(yīng)度值的增量小于某個(gè)給定的閾值時(shí)算法停止。第16頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二粒子群優(yōu)化算法流程圖 開始初始化粒子群計(jì)算每個(gè)粒子的適應(yīng)度根據(jù)適應(yīng)度更新pbest、gbest，更新粒子位置速度結(jié)束noyes達(dá)到最大迭代次數(shù)或全局最優(yōu)位置滿足最小界限？第17頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二2維簡(jiǎn)例Not

9、e合理解目前最優(yōu)解區(qū)域最佳解全域區(qū)域第18頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二粒子群算法的構(gòu)成要素 -群體大小 m m 是一個(gè)整型參數(shù) m 很小: m 很大: 當(dāng)群體數(shù)目增長(zhǎng)至一定水平時(shí)，再增長(zhǎng)將不再有顯 但收斂速度慢著的作用陷入局優(yōu)的可能性很大 PSO的優(yōu)化能力很好，第19頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二粒子群算法的構(gòu)成要素 -權(quán)重因子 權(quán)重因子：慣性因子 、學(xué)習(xí)因子 失去對(duì)粒子本身的速度的記憶 社會(huì)經(jīng)驗(yàn)部分 前次迭代中自身的速度 自我認(rèn)知部分 基本粒子群算法 粒子的速度更新主要由三部分組成： 慣性因子 第20頁(yè)，共48頁(yè)，2022年，5月20

10、日，17點(diǎn)14分，星期二粒子群算法的構(gòu)成要素-權(quán)重因子 權(quán)重因子：慣性因子 、學(xué)習(xí)因子 社會(huì)經(jīng)驗(yàn)部分 前次迭代中自身的速度 自我認(rèn)知部分 粒子的速度更新主要由三部分組成： 學(xué)習(xí)因子 無(wú)私型粒子群算法 “只有社會(huì)，沒(méi)有自我”迅速喪失群體多樣性，易陷入局優(yōu)而無(wú)法跳出第21頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二粒子群算法的構(gòu)成要素 -權(quán)重因子 權(quán)重因子：慣性因子 、學(xué)習(xí)因子 社會(huì)經(jīng)驗(yàn)部分 前次迭代中自身的速度 自我認(rèn)知部分 粒子的速度更新主要由三部分組成： 自我認(rèn)知型粒子群算法 “只有自我，沒(méi)有社會(huì)”完全沒(méi)有信息的社會(huì)共享，導(dǎo)致算法收斂速度緩慢 學(xué)習(xí)因子 第22頁(yè)，共48頁(yè)，20

11、22年，5月20日，17點(diǎn)14分，星期二粒子群算法的構(gòu)成要素-權(quán)重因子 權(quán)重因子：慣性因子 、學(xué)習(xí)因子 社會(huì)經(jīng)驗(yàn)部分 前次迭代中自身的速度 自我認(rèn)知部分 粒子的速度更新主要由三部分組成： c1,c2都不為0，稱為完全型粒子群算法 完全型粒子群算法更容易保持收斂速度和搜索效果的均衡，是較好的選擇 第23頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二粒子群算法的構(gòu)成要素-最大速度 但 在于維護(hù)算法的探索能力與開發(fā)能力的平衡 Vm較大時(shí)，探索能力增強(qiáng)， 作用: Vm較小時(shí)，開發(fā)能力增強(qiáng)， Vm一般設(shè)為每維變量變化范圍的1020. 但 粒子容易飛過(guò)最優(yōu)解 容易陷入局部最優(yōu) 第24頁(yè)，共48

12、頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二粒子群算法的構(gòu)成要素- 鄰域的拓?fù)浣Y(jié)構(gòu) 全局粒子群算法和局部粒子群算法 粒子群算法的鄰域拓?fù)浣Y(jié)構(gòu)包括兩種，一種是將群體內(nèi)所有個(gè)體都作為粒子的鄰域，另一種是只將群體中的部分個(gè)體作為粒子的鄰域 群體歷史最優(yōu)位置 鄰域拓?fù)浣Y(jié)構(gòu)決定 由此，將粒子群算法分為第25頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二粒子群算法的構(gòu)成要素- 鄰域的拓?fù)浣Y(jié)構(gòu) 全局粒子群算法 1. 粒子自己歷史最優(yōu)值 2. 粒子群體的全局最優(yōu)值局部粒子群算法 1. 粒子自己歷史最優(yōu)值 2. 粒子鄰域內(nèi)粒子的最優(yōu)值 鄰域隨迭代次數(shù)的增加線性變大，最后鄰域擴(kuò)展到整個(gè)粒子群。 經(jīng)

13、過(guò)實(shí)踐證明：全局版本的粒子群算法收斂速度快，但是容易陷入局部最優(yōu)。局部版本的粒子群算法收斂速度慢，但是很難陷入局部最優(yōu)。現(xiàn)在的粒子群算法大都在收斂速度與擺脫局部最優(yōu)這兩個(gè)方面下功夫。其實(shí)這兩個(gè)方面是矛盾的。看如何更好的折中了。第26頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二 粒子群算法的構(gòu)成要素 -停止準(zhǔn)則 停止準(zhǔn)則一般有如下兩種： 最大迭代步數(shù) 可接受的滿意解 第27頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二 粒子群算法的構(gòu)成要素 - 粒子空間的初始化 較好地選擇粒子的初始化空間，將大大縮短收斂時(shí)間初始化空間根據(jù)具體問(wèn)題的不同而不同，也就是說(shuō)，這是問(wèn)題依賴的

14、從上面的介紹可以看到，粒子群算法與其他現(xiàn)代優(yōu)化方法相比的一個(gè)明顯特色就是所需調(diào)整的參數(shù)很少相對(duì)來(lái)說(shuō)，慣性因子和鄰域定義較為重要這些為數(shù)不多的關(guān)鍵參數(shù)的設(shè)置卻對(duì)算法的精度和效率有著顯著影響第28頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二3. 粒子群算法示例 例 求解如下四維Rosenbrock函數(shù)的優(yōu)化問(wèn)題 種群大?。?解 算法的相關(guān)設(shè)計(jì)分析如下 編碼：因?yàn)閱?wèn)題的維數(shù)是4，所以每個(gè)粒子的位置和 即算法中粒子的數(shù)量，取 速度均4 維的實(shí)數(shù)向量設(shè)定粒子的最大速度： 第29頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二初始位置： 設(shè)各粒子的初始位置 和初始速度 為： 對(duì)粒子

15、群進(jìn)行隨機(jī)初始化 包括隨機(jī)初始化各粒子的位置和速度 第30頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二初始速度： 設(shè)各粒子的初始位置 和初始速度 為： 對(duì)粒子群進(jìn)行隨機(jī)初始化 包括隨機(jī)初始化各粒子的位置和速度 第31頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二初始速度： 初始位置： 計(jì)算每個(gè)粒子的適應(yīng)值 按照 計(jì)算適應(yīng)值 歷史最優(yōu)解第32頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二更新粒子的速度和位置： 取 ， , 得到速度和位置的更新函數(shù)為 初始速度： 初始位置： 群體歷史最優(yōu)解： 個(gè)體歷史最優(yōu)解： 第33頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)

16、14分，星期二更新速度，得：初始速度： 初始位置： 群體歷史最優(yōu)解： 個(gè)體歷史最優(yōu)解： 第34頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二更新位置，得：初始速度： 初始位置： 群體歷史最優(yōu)解： 個(gè)體歷史最優(yōu)解： 不強(qiáng)行拉回解空間 第35頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二更新位置，得：初始速度： 初始位置： 群體歷史最優(yōu)解： 個(gè)體歷史最優(yōu)解： 按照 計(jì)算適應(yīng)值 第36頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二重復(fù)上述步驟，將迭代進(jìn)行下去 按照 計(jì)算適應(yīng)值 歷史最優(yōu)解第37頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二 從上述結(jié)果，

17、可以看出，經(jīng)過(guò)10000次迭代，粒子群算法得到了比較好的適應(yīng)值. 第38頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二4. 粒子群算法流程 第2步 計(jì)算每個(gè)粒子的適應(yīng)值 第1步 在初始化范圍內(nèi)，對(duì)粒子群進(jìn)行隨機(jī)初始化，第5步 更新粒子的速度和位置，公式如下 第3步 更新粒子個(gè)體的歷史最優(yōu)位置 第6步 若未達(dá)到終止條件，則轉(zhuǎn)第2步 包括隨機(jī)位置和速度 第4步 更新粒子群體的歷史最優(yōu)位置 第39頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二慣性權(quán)重 1998年，Shi和Eberhart引入了慣性權(quán)重w，并提出動(dòng)態(tài)調(diào)整慣性權(quán)重以平衡收斂的全局性和收斂速度，該算法被稱為標(biāo)準(zhǔn)PS

18、O算法 慣性權(quán)重w描述粒子上一代速度對(duì)當(dāng)前代速度的影響。w值較大，全局尋優(yōu)能力強(qiáng)，局部尋優(yōu)能力弱；反之，則局部尋優(yōu)能力強(qiáng)。當(dāng)問(wèn)題空間較大時(shí)，為了在搜索速度和搜索精度之間達(dá)到平衡，通常做法是使算法在前期有較高的全局搜索能力以得到合適的種子，而在后期有較高的局部搜索能力以提高收斂精度。所以w不宜為一個(gè)固定的常數(shù)。第40頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二線性遞減權(quán)值 wmax最大慣性權(quán)重，wmin最小慣性權(quán)重，run當(dāng)前迭代次數(shù)，runmax為算法迭代總次數(shù) 較大的w有較好的全局收斂能力，較小的w則有較強(qiáng)的局部收斂能力。因此，隨著迭代次數(shù)的增加，慣性權(quán)重w應(yīng)不斷減少，從而使得粒子群算法在初期具有較強(qiáng)的全局收斂能力，而晚期具有較強(qiáng)的局部收斂能力。 第41頁(yè)，共48頁(yè)，2022年，5月20日，17點(diǎn)14分，星期二1999年，Clerc引入收縮因子以保證算法的收斂性。速度更新公式為其中，收縮因子K為受1 2 限制的w。1 2是需要預(yù)先設(shè)定的模型參數(shù)收縮因子法控制系統(tǒng)行為最終收斂，且可以有效搜索不同