粒子群最佳化演算法

粒子群最佳化演算法

ParticleSwarmOptimization(PSO)李維平老師緒論

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

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

【Eberhart,Kennedy,1995】緒論P(yáng)SO是模擬鳥群覓食的社會(huì)行為所衍生從1995年以來陸續(xù)有許多研究學(xué)者投入研究已經(jīng)有超過了三百篇以上的研究成果被發(fā)表出來起源

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

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

粒子群特性起源

當(dāng)其他鳥發(fā)現(xiàn)了更佳的覓食地點(diǎn)時(shí)，鳥群間會(huì)有某種類似廣播的溝通行為，漸漸的將其他鳥群引領(lǐng)至較佳的地點(diǎn)這樣的覓食行為是利用社會(huì)中所存在的互相影響的概念，來引領(lǐng)所有個(gè)體朝向最佳解位置起源粒子群的概念視為一個(gè)簡(jiǎn)單的社會(huì)系統(tǒng)每隻個(gè)體被視為一個(gè)解答，稱之為粒子(Particle)每個(gè)粒子經(jīng)由適應(yīng)函數(shù)的衡量而具有一個(gè)適應(yīng)値區(qū)域最佳解全域最佳解運(yùn)動(dòng)向量慣性向量BionicComputingLab,2005BionicComputingChungYuanChristianUniversity12/21/05DMcourseParticleSwarmsOptimization

craziness動(dòng)能向量概論P(yáng)SO向量示意圖目前最佳解區(qū)域最佳解W**Rand()*()*Rand()*()=++2維簡(jiǎn)例BionicComputingLab,2005BionicComputingChungYuanChristianUniversity12/21/05DMcourse粒子群最佳化ParticleSwarmsOptimization

Note合理解目前最優(yōu)解區(qū)域最佳解全域區(qū)域符號(hào)說明pbest代表粒子本身到目前為止所達(dá)到最佳解

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

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

w-慣性權(quán)重

C-學(xué)習(xí)因子

pid-區(qū)域最佳解

Pgd-全域最佳解原來速度

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

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

6.回到步驟2重複執(zhí)行這些步驟，直到停止準(zhǔn)則條件符合為止，通常停止準(zhǔn)則會(huì)被設(shè)定為到達(dá)最大執(zhí)行次數(shù)，或是達(dá)到所期望的適應(yīng)值時(shí)。RastriginBionicComputingLab,2005BionicComputingChungYuanChristianUniversity12/21/05DMcourse相關(guān)論文研討ParticleSwarmsOptimization

PerformancetestRosenbrock粒子群優(yōu)化算法的分析與改進(jìn)Rosenbrock函數(shù)

Rastrigin函數(shù)

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