機器學習-第03講-1-2-2-PSO

機器學習——

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

ParticleSwarmOptimization-PSO

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

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

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

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

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

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

程序的偽代碼如下

Foreachparticle

____Initializeparticle

END

Do

____Foreachparticle

________Calculatefitnessvalue

________Ifthefitnessvalueisbetterthanthebestfitnessvalue(pBest)inhistory

____________setcurrentvalueasthenewpBest

____End

____ChoosetheparticlewiththebestfitnessvalueofalltheparticlesasthegBest

____Foreachparticle

________Calculateparticlevelocityaccordingequation(a)

________Updateparticlepositionaccordingequation(b)

____End

Whilemaximumiterationsorminimumerrorcriteriaisnotattained

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

用

舉

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

Xi:Xj:

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

廣義染色體的模式

廣義染色體的一個例子

離散PSO算法在廣義TSP問題中的擴展34與上圖廣義染色體對應的回路

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

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

以及Pg針對廣義TSP問題的離散PSO算法流程圖38一些標準測試問題的計算結(jié)果ProblemOptBestresultWorstresultAverageresultErr(%)11EIL51174176186180.213.5714ST70316315328317.110.3516EIL76209214232221.846.1416PR7664825649276784465670.741.3020KROA100971197