機(jī)器學(xué)習(xí)-第03講-1-2-2-PSO

機(jī)器學(xué)習(xí)——

粒子群優(yōu)化算法

ParticleSwarmOptimization-PSO

智能工程研究室計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2大綱一、算法概述二、產(chǎn)生基礎(chǔ)三、算法內(nèi)容四、和其它優(yōu)化算法的比較五、應(yīng)用舉例3算法概述PSO是Kennedy&Eberhart于1995年提出的Kennedy博士心理學(xué)研究人員

/cathyk/jimk.htmlEberhart博士計(jì)算智能 /~eberhart/PSO是一種基于疊代的優(yōu)化工具PSO概念簡(jiǎn)單容易實(shí)現(xiàn)KennedyJ.andEberhartR.C.,Particleswarmoptimization,ProceedingsoftheIEEEInternationalConferenceonNeuralNetworks,1995，pp.1942–1948.4算法概述應(yīng)用領(lǐng)域廣發(fā)展很快系統(tǒng)設(shè)計(jì)、多目標(biāo)優(yōu)化、分類(lèi)、模式識(shí)別、信號(hào)處理、機(jī)器人技術(shù)應(yīng)用、決策制定、模擬和證明等目前被“國(guó)際進(jìn)化計(jì)算會(huì)議”(IEEEInternationalConferencesonEvolutionaryComputation,CEC)列為一個(gè)討論的專(zhuān)題。5背景對(duì)鳥(niǎo)群行為的模擬：Reynolds、Heppner和Grenader提出鳥(niǎo)群行為的模擬。他們發(fā)現(xiàn)，鳥(niǎo)群在行進(jìn)中會(huì)突然同步的改變方向，散開(kāi)或者聚集等。那么一定有某種潛在的能力或規(guī)則保證了這些同步的行為。這些科學(xué)家都認(rèn)為上述行為是基于不可預(yù)知的鳥(niǎo)類(lèi)社會(huì)行為中的群體動(dòng)態(tài)學(xué)。在這些早期的模型中僅僅依賴(lài)個(gè)體間距的操作，也就是說(shuō)，這種同步是鳥(niǎo)群中個(gè)體之間努力保持最優(yōu)的距離的結(jié)果。6背景對(duì)魚(yú)群行為的研究：生物社會(huì)學(xué)家E.O.Wilson對(duì)魚(yú)群進(jìn)行了研究。提出：“至少在理論上，魚(yú)群的個(gè)體成員能夠受益于群體中其它個(gè)體在尋找食物的過(guò)程中的發(fā)現(xiàn)和以前的經(jīng)驗(yàn)，這種受益超過(guò)了個(gè)體之間的競(jìng)爭(zhēng)所帶來(lái)的利益消耗，不管任何時(shí)候食物資源不可預(yù)知的分散?！边@說(shuō)明，同種生物之間信息的社會(huì)共享能夠帶來(lái)好處。這是PSO的基礎(chǔ)。7設(shè)想這樣一個(gè)場(chǎng)景：一群鳥(niǎo)在隨機(jī)的搜索食物。在這個(gè)區(qū)域里只有一個(gè)放置食物的地方，所有的鳥(niǎo)都不知道食物在哪里。但是它們知道自己當(dāng)前的位置距離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么？最簡(jiǎn)單有效的就是搜尋目前離食物最近的鳥(niǎo)的周?chē)鷧^(qū)域。背景8PSO是對(duì)簡(jiǎn)化的社會(huì)系統(tǒng)的模擬源于對(duì)鳥(niǎo)群覓食行為的研究信息共享機(jī)制心理學(xué)假設(shè)在尋求一致的認(rèn)知過(guò)程中，個(gè)體往往記住它們的信念，同時(shí)考慮其它個(gè)體的信念。當(dāng)個(gè)體察覺(jué)其它個(gè)體的信念較好的時(shí)候，它將進(jìn)行適應(yīng)性地調(diào)整背景9算法內(nèi)容概述粒子：優(yōu)化問(wèn)題的解粒子的適應(yīng)度：評(píng)價(jià)解的質(zhì)量，由優(yōu)化問(wèn)題決定粒子的速度：飛行方向和距離粒子的行為：追隨當(dāng)前的最優(yōu)粒子，不斷根據(jù)自身和同伴的經(jīng)驗(yàn)來(lái)更新自己10粒子群原理示意圖算法內(nèi)容該粒子以前最優(yōu)位置全局最優(yōu)粒子當(dāng)前飛行行為受以前最優(yōu)位置影響受上一次飛行行為影響受全局最優(yōu)粒子影響新的飛行食物源11算法內(nèi)容形式(多維標(biāo)準(zhǔn)）假設(shè)搜索空間為D維，取N個(gè)粒子，第i個(gè)粒子表示為Xi=(xi1,xi2,…,xiD)Xi經(jīng)歷過(guò)的最好位置記為Pi=(pi1,pi2,…,piD)，它是粒子本身所找到的最優(yōu)解，稱(chēng)為個(gè)體最優(yōu)解，記為pBest所有粒子經(jīng)歷過(guò)的最好位置，是整個(gè)群體目前找到的最優(yōu)解，稱(chēng)為群體最優(yōu)解，記為gBest12算法內(nèi)容核心公式慣性項(xiàng)個(gè)體經(jīng)驗(yàn)群體經(jīng)驗(yàn)13算法內(nèi)容算法的實(shí)現(xiàn)步驟粒子表示：實(shí)數(shù)編碼，整數(shù)編碼適應(yīng)度函數(shù)設(shè)計(jì)：非負(fù)，易于度量停止條件設(shè)置：最大更新代數(shù)，適應(yīng)度函數(shù)增量群體規(guī)模設(shè)置：可參考粒子的維數(shù)群體初始化：在有效范圍內(nèi)隨機(jī)產(chǎn)生群體更新：個(gè)體最佳位置，群體最佳位置個(gè)體速度，個(gè)體位置14算法內(nèi)容參數(shù)分析粒子數(shù)一般取20–40.其實(shí)對(duì)于大部分的問(wèn)題10個(gè)粒子已經(jīng)足夠可以取得好的結(jié)果粒子的維度由優(yōu)化問(wèn)題決定，每一維可以設(shè)定不同的范圍最大速度(Vmax)決定粒子在一個(gè)循環(huán)中最大的移動(dòng)距離,通常設(shè)定為粒子的范圍寬度15算法內(nèi)容參數(shù)分析學(xué)習(xí)因子C1=C2=2r1=r2

是隨機(jī)量，為了避免一致性）慣性權(quán)重 V[]=W*V[]+C1*rand()*(pBest[]-present[])+C2*rand()*(gBest[]-present[])16初始化粒子群體是計(jì)算每個(gè)粒子的適應(yīng)度值輸出最終解速度(v)和位置(x)更新否更新個(gè)體最優(yōu)解pBest更新群體最優(yōu)解gBest滿(mǎn)足停止條件？粒子群算法流程圖在找到這兩個(gè)最優(yōu)值時(shí)，粒子根據(jù)如下的公式來(lái)更新自己的速度和新的位置：

v[]=w*v[]+c1*rand()*(pbest[]-present[])+c2*rand()*(gbest[]-present[])(a)

present[]=persent[]+v[](b)

v[]是粒子的速度,w是慣性權(quán)重,persent[]是當(dāng)前粒子的位置.pbest[]andgbest[]如前定義rand()是介于（0，1）之間的隨機(jī)數(shù).c1,c2是學(xué)習(xí)因子.通常c1=c2=2.

程序的偽代碼如下

Foreachparticle

____Initializeparticle

END

Do

____Foreachparticle

________Calculatefitnessvalue

________Ifthefitnessvalueisbetterthanthebestfitnessvalue(pBest)inhistory

____________setcurrentvalueasthenewpBest

____End

____ChoosetheparticlewiththebestfitnessvalueofalltheparticlesasthegBest

____Foreachparticle

________Calculateparticlevelocityaccordingequation(a)

________Updateparticlepositionaccordingequation(b)

____End

Whilemaximumiterationsorminimumerrorcriteriaisnotattained

在每一維粒子的速度都會(huì)被限制在一個(gè)最大速度Vmax，如果某一維更新后的速度超過(guò)用戶(hù)設(shè)定的Vmax，那么這一維的速度就被限定為Vmax20應(yīng)

用

舉

例21應(yīng)用舉例粒子表示：2維實(shí)數(shù)向量X=(x,y)’速度表示：2維實(shí)數(shù)向量V=(vx,vy)’適應(yīng)度函數(shù)：f(X)=f(x,y)停止條件設(shè)置：最大更新代數(shù)50群體規(guī)模：10群體初始化方法：隨機(jī)產(chǎn)生0<x,y<8,0<v1，v2<8控制參數(shù)：C1=C2=2,w=122算法演示函數(shù)優(yōu)化1（演示）f(x,y)=100*(x^2-y)^2+(1-x)^2,(-2.048<x,y<2.048)全局最小點(diǎn)（1，1），全局最小值0函數(shù)優(yōu)化2f(x,y)=sin(x)*cos(y),(-pi/2<x,y<pi/2)全局最小點(diǎn)（-pi/2,0）,全局最小值-123函數(shù)優(yōu)化3f(x,y)=(4-2.1x^2+x^4/3)x^2+xy+(-4+4y^2)y^2-10<x,y<10全局最小點(diǎn)(-0.0898,0.7126),(0.0898,-0.7126)，最小值-1.03162函數(shù)優(yōu)化4f(x,y)=-0.5+(sin(sqrt(x^2+y^2))^2-0.5)/(1+0.001(x^2+y^2))^2,-100<x,y<100全局最小點(diǎn)(0,0),全局最小值-1算法演示24PSO算法已經(jīng)用來(lái)應(yīng)用于分析人的顫抖，對(duì)人的顫抖的診斷，包括帕金森(Parkinson)病和基本的顫抖一個(gè)電氣設(shè)備的功率反饋和電壓控制其它應(yīng)用領(lǐng)域25解旅行商問(wèn)題的離散粒子群優(yōu)化算法如何把求解連續(xù)優(yōu)化問(wèn)題的PSO改造成能夠求解離散優(yōu)化問(wèn)題的算法？設(shè)計(jì)粒子表示方法重新定義粒子速度重新定義粒子位移確定適應(yīng)度函數(shù)形式26解旅行商問(wèn)題的離散粒子群優(yōu)化算法設(shè)計(jì)粒子表示方法采用整數(shù)形式的粒子表示方法152643727解旅行商問(wèn)題的離散粒子群優(yōu)化算法粒子速度定義粒子分量交換的次數(shù)適應(yīng)度距離28解旅行商問(wèn)題的離散粒子群優(yōu)化算法粒子位移定義相對(duì)于個(gè)體最優(yōu)位置和群體最優(yōu)位置的變換SWAP(Xi,Xl,k):（l=pBest或者l=gBest,k=rand()(0<k<=n)）

Xi:Xj:

SWAP(Xi,Xj,5)12345673564127123756429粒子群算法求解旅行商問(wèn)題的流程圖解旅行商問(wèn)題的離散粒子群優(yōu)化算法數(shù)據(jù)結(jié)構(gòu)（群體規(guī)模為m，粒子維數(shù)為n）X[m][n]:粒子位移V[m][n]:粒子速度YpBest[m][n]:個(gè)體最佳位置YgBest[n]:群體最佳位置30PSO和GA的比較GA選擇操作交叉操作變異操作逆轉(zhuǎn)操作需要把連續(xù)變量轉(zhuǎn)化成二進(jìn)制編碼適應(yīng)度影響個(gè)體遺傳的概率PSO根據(jù)速度進(jìn)行最優(yōu)解搜索最適用于連續(xù)變量的優(yōu)化問(wèn)題適應(yīng)度近供pBest和gBest的判定收斂速度快共同點(diǎn)：需要適應(yīng)度函數(shù)評(píng)價(jià)個(gè)體的質(zhì)量31補(bǔ)充閱讀資料32離散PSO算法在廣義TSP問(wèn)題中的擴(kuò)展廣義TSP問(wèn)題:把給定的n個(gè)城市分成m個(gè)組，旅行商要選擇一條訪(fǎng)問(wèn)每個(gè)組中一個(gè)（或至少一個(gè)）城市的最短旅行回路應(yīng)用領(lǐng)域:覆蓋遍歷問(wèn)題、物流系統(tǒng)設(shè)計(jì)問(wèn)題、郵箱收集問(wèn)題以及隨機(jī)車(chē)輛路由問(wèn)題等33WuC.G.,LiangY.C.,LeeH.P.andLuC.Ageneralizedchromosomegeneticalgorithmforgeneralizedtravelingsalesmanproblemsanditsapplicationsformachining.PhysicalReviewE,2004,(70):016701-1-13.廣義染色體

廣義染色體的模式

廣義染色體的一個(gè)例子

離散PSO算法在廣義TSP問(wèn)題中的擴(kuò)展34與上圖廣義染色體對(duì)應(yīng)的回路

35SWAP(Xi,Xj,k)XiXj離散PSO算法在廣義TSP問(wèn)題中的擴(kuò)展36離散PSO算法在廣義TSP問(wèn)題中的擴(kuò)展兩種局部搜索技術(shù)頭局部搜索在頭部某一個(gè)節(jié)點(diǎn)，搜索最佳的城市號(hào)，并用它取代原來(lái)的城市號(hào)體局部搜索每次迭代的時(shí)候隨機(jī)地交換兩個(gè)廣義頂點(diǎn)的順序，如果適應(yīng)度增大則保留交換，否則，保持原順序不變

37初始化粒子群對(duì)每個(gè)粒子執(zhí)行“交換子”操作執(zhí)行頭局部搜索結(jié)束是否執(zhí)行體局部搜索是否滿(mǎn)足終止條件？對(duì)每個(gè)粒子搜索Pi

以及Pg針對(duì)廣義TSP問(wèn)題的離散PSO算法流程圖38一些標(biāo)準(zhǔn)測(cè)試問(wèn)題的計(jì)算結(jié)果ProblemOptBestresultWorstresultAverageresultErr(%)11EIL51174176186180.213.5714ST70316315328317.110.3516EIL76209214232221.846.1416PR7664825649276784465670.741.3020KROA100971197