粒子群最佳化演算法

粒子群最佳化演算法

ParticleSwarmOptimization(PSO)李維平老師緒論

粒子群最佳化演算法(簡稱為PSO)，是一種以群體為基礎(Population-based)的最佳化搜尋技術由JamesKennedy和RussellEberhart兩位學者於1995年時所提出BionicComputingLab,2005BionicComputingChungYuanChristianUniversity12/21/05DMcourse粒子群最佳化ParticleSwarmsOptimization

RussEberhart整合群體行為、人類決策與鳥群行為發展而成稱為粒子群演算法。

【Eberhart,Kennedy,1995】緒論PSO是模擬鳥群覓食的社會行為所衍生從1995年以來陸續有許多研究學者投入研究已經有超過了三百篇以上的研究成果被發表出來起源

提出演算法的兩位學者，藉由觀察鳥群覓食的社會行為得到啟發鳥群於食物存在的空間中飛行覓食，一開始並不知道最佳的覓食點在哪個位置每隻鳥可能會憑藉著自己的經驗或是直覺，飛往牠所覺得較佳的地點來搜尋食物BionicComputingLab,2005BionicComputingChungYuanChristianUniversity12/21/05DMcourse鳥群(魚群)行為ParticleSwarmsOptimization

師法大自然BionicComputingLab,2005BionicComputingChungYuanChristianUniversity12/21/05DMcourse鳥群(魚群)行為ParticleSwarmsOptimization

粒子群特性起源

當其他鳥發現了更佳的覓食地點時，鳥群間會有某種類似廣播的溝通行為，漸漸的將其他鳥群引領至較佳的地點這樣的覓食行為是利用社會中所存在的互相影響的概念，來引領所有個體朝向最佳解位置起源粒子群的概念視為一個簡單的社會系統每隻個體被視為一個解答，稱之為粒子(Particle)每個粒子經由適應函數的衡量而具有一個適應値區域最佳解全域最佳解運動向量慣性向量BionicComputingLab,2005BionicComputingChungYuanChristianUniversity12/21/05DMcourseParticleSwarmsOptimization

craziness動能向量概論PSO向量示意圖目前最佳解區域最佳解W**Rand()*()*Rand()*()=++2維簡例BionicComputingLab,2005BionicComputingChungYuanChristianUniversity12/21/05DMcourse粒子群最佳化ParticleSwarmsOptimization

Note合理解目前最優解區域最佳解全域區域符號說明pbest代表粒子本身到目前為止所達到最佳解

Pi代表粒子最佳解的位置gbest即代表全體群體到目前為止最佳解

Pg代表全體最佳解的位置PSO目標式速度：vid(t+1)=wxvid(t)+c1xrand()x[pid(t)-xid(t)(t)]+c2xrand()x[Pgd(t)-xid(t)(t)]v-速度

w-慣性權重

C-學習因子

pid-區域最佳解

Pgd-全域最佳解原來速度

vid過去自身經驗同伴飛行經驗運動向量目前的區域最佳解pbest目前的全域最佳解gbest原來位置xid(t)新位置xid(t+1)原來速度vid(t)新速度vid(t+1)位置：xid(t+1)=xid(t)+vid(t+1)PSO流程

以任意的位置和速度來初始化粒子評估各個粒子的適應值更新pbest與gbest值更新各個粒子位置及速度開始滿足終止條件結束否是PSO演算法1.以任意的位置和速度來初始化粒子2.利用適應函數計算每個粒子的適應値3.將粒子的適應值和pbest值作比較，假如優於pbest值，則更新pbest值及其位置4.將粒子的適應值和gbest值作比較，如果優於gbest值，則更新gbest值及其位置5.依照下面的兩個式子來改變粒子的速度和位置:

6.回到步驟2重複執行這些步驟，直到停止準則條件符合為止，通常停止準則會被設定為到達最大執行次數，或是達到所期望的適應值時。RastriginBionicComputingLab,2005BionicComputingChungYuanChristianUniversity12/21/05DMcourse相關論文研討ParticleSwarmsOptimization

PerformancetestRosenbrock粒子群优化算法的分析与改进Rosenbrock函數

Rastrigin函數

PSO特性PSO演算法類似GA演算法粒子擁有記憶性粒子的特點為位置與速度廣域搜尋和區域搜尋迭代演化後搜索到空間中的最佳解優點PSO吸引人之處，在於只有少數的參數需要調整並且能加快速度收斂至最佳解可以被應用來解決大多數的最佳化問題。PSO與GA比較同異PSO1)由一組隨機解開始2)經過不斷搜尋，找出最佳解None,soeasyGA1)Crossover2)MutationSocomplex!PSO與GA比較-相同相同的演算法流程1.群體隨機初始化2.對群體內每一個體計算適應值(FitnessValue)適應值與最佳解的距離直接有關3.群體根據適應值進行複製4.如果滿足終止條件就停止，否則回到步驟2PSO與GA比較-相異PSO沒有遺傳操作-交換（Crossover）、突變（Mutation）而是根據自己的速度來決定搜尋PSO有記憶性PSO有廣泛的應用領域例如:系統設計、多目標最佳化、分類、型樣識別、生物系統模擬、排程、遊戲、機器人應用、決策制定、網路安全及路由選擇、神經網路訓練、模擬和識別等而其相關的實例則包含了模擬控制器設計、工作排程、影像分割、語音識別、時間頻率分析、燒燙傷診斷、手勢姿勢識別和自動目標偵測等問題上附錄DoCalculatefitnessofparticleUpdatepbestifthecurrentfitnessisbetterthanpbestDeterminenbestforeachparticle:choosetheparticlewiththebestfitnessvalueofalltheneighborsasthenbestForeachparticleCalculateparticlevelocityaccordingto(1)Updateparticlepositionaccordingto(2)WhilemaximumiterationsorminimumcriteriaisnotattainedPSO演算法Step1:初始化 包括參數設定及隨機初始化粒子的位置和速度。Setp2:計算每顆粒子的適應值。Step3:每顆粒子與該粒子所經歷的最