計(jì)算智能與深度學(xué)習(xí) 課件 6粒子群算法

第6章粒子群算法

6.1粒子群算法的基本原理

6.1.1粒子群算法的提出

6.1.2粒子群算法的原理描述6.2基本粒子群優(yōu)化算法

6.2.1基本粒子群算法描述

6.2.2參數(shù)分析

6.2.3與遺傳算法的比較6.3改進(jìn)粒子群優(yōu)化算法

6.3.1離散二進(jìn)制PSO

6.3.2慣性權(quán)重模型

6.3.3收斂因子模型

6.3.4研究現(xiàn)狀6.4粒子群優(yōu)化算法的應(yīng)用

6.4.1求解TSP問(wèn)題

6.4.2其它應(yīng)用6.5群智能優(yōu)化的特點(diǎn)與不足由JamesKenney（社會(huì)心理學(xué)博士）和RussEberhart（電子工程學(xué)博士，/~eberhart/

）于1995年提出粒子群算法（ParticleSwarmOptimization,PSO）

6.1粒子群算法的基本原理6.1.1粒子群算法的提出源于對(duì)鳥群捕食行為的研究，是基于迭代的方法簡(jiǎn)單易于實(shí)現(xiàn)，需要調(diào)整的參數(shù)相對(duì)較少在函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、工業(yè)系統(tǒng)優(yōu)化和模糊系統(tǒng)控制等領(lǐng)域得到了廣泛的應(yīng)用。6.1粒子群算法的基本原理6.1.1粒子群算法的提出鳥群：假設(shè)一個(gè)區(qū)域，所有的鳥都不知道食物的位置，但是它們知道當(dāng)前位置離食物還有多遠(yuǎn)。PSO算法

每個(gè)解看作一只鳥，稱為“粒子(particle)”，所有的粒子都有一個(gè)適應(yīng)值，每個(gè)粒子都有一個(gè)速度決定它們的飛翔方向和距離，粒子們追隨當(dāng)前最優(yōu)粒子在解空間中搜索。6.1粒子群算法的基本原理6.1.2粒子群算法的原理描述PSO算法

初始化為一群隨機(jī)粒子，通過(guò)迭代找到最優(yōu)。每次迭代中，粒子通過(guò)跟蹤“個(gè)體極值（pbest）”和“全局極值(gbest)”來(lái)更新自己的位置。6.1粒子群算法的基本原理6.1.2粒子群算法的原理描述粒子速度和位置的更新

假設(shè)在D維搜索空間中，有m個(gè)粒子；其中第i個(gè)粒子的位置為矢量其飛翔速度也是一個(gè)矢量，記為第i個(gè)粒子搜索到的最優(yōu)位置為整個(gè)粒子群搜索到的最優(yōu)位置為第i個(gè)粒子的位置和速度更新為：6.2基本粒子群優(yōu)化算法6.2.1基本粒子群算法描述粒子速度和位置的更新

其中，w稱為慣性權(quán)重，

c1和c2為兩個(gè)正常數(shù)，稱為加速因子。將vidk限制在一個(gè)最大速度vmax內(nèi)。6.2基本粒子群優(yōu)化算法6.2.1基本粒子群算法描述xkvkppgbestxk+1vk+1kkk+1k+1粒子速度和位置的更新

6.2基本粒子群優(yōu)化算法6.2.1基本粒子群算法描述“慣性部分”，對(duì)自身運(yùn)動(dòng)狀態(tài)的信任“認(rèn)知部分”，對(duì)微粒本身的思考，即來(lái)源于自己經(jīng)驗(yàn)的部分“社會(huì)部分”，微粒間的信息共享，來(lái)源于群體中的其它優(yōu)秀微粒的經(jīng)驗(yàn)迭代過(guò)程

6.2基本粒子群優(yōu)化算法6.2.1基本粒子群算法描述算法流程

6.2基本粒子群優(yōu)化算法StartInitializeparticleswithrandompositionandvelocityvectors.Foreachparticle’sposition(xi)evaluatefitnessIffitness(xi)betterthanfitness(p)thenp=xiLoopuntilallparticlesexhaustSetbestofpsasgBestUpdateparticlesvelocityandpositionLoopuntilmaxiterStop:givinggBest,optimalsolution.6.2.1基本粒子群算法描述慣性權(quán)重w

使粒子保持運(yùn)動(dòng)慣性，使其有擴(kuò)展搜索空間的趨勢(shì)，有能力探索新的區(qū)域。表示微粒對(duì)當(dāng)前自身運(yùn)動(dòng)狀態(tài)的信任，依據(jù)自身的速度進(jìn)行慣性運(yùn)動(dòng)。較大的w有利于跳出局部極值，而較小的w有利于算法收斂。6.2基本粒子群優(yōu)化算法6.2.2參數(shù)分析加速常數(shù)c1和c2

代表將微粒推向pbest和gbest位置的統(tǒng)計(jì)加速項(xiàng)的權(quán)重。表示粒子的動(dòng)作來(lái)源于自己經(jīng)驗(yàn)的部分和其它粒子經(jīng)驗(yàn)的部分。低的值允許粒子在被拉回之前可以在目標(biāo)區(qū)域外徘徊，而高的值則導(dǎo)致粒子突然沖向或越過(guò)目標(biāo)區(qū)域。

6.2基本粒子群優(yōu)化算法6.2.2參數(shù)分析加速常數(shù)c1和c2

將c1和c2統(tǒng)一為一個(gè)控制參數(shù)，φ=c1+c2

如果φ很小，微粒群運(yùn)動(dòng)軌跡將非常緩慢；如果φ很大，則微粒位置變化非?？欤粚?shí)驗(yàn)表明，當(dāng)φ=4.1（通常c1=2.0，c2=2.0）時(shí)，具有很好的收斂效果。6.2基本粒子群優(yōu)化算法6.2.2參數(shù)分析粒子數(shù)

一般取20～40，對(duì)較難或特定類別的問(wèn)題可以取

100～200。最大速度vmax

決定粒子在一個(gè)循環(huán)中最大的移動(dòng)距離，通常設(shè)定為粒子的范圍寬度。終止條件

最大循環(huán)數(shù)以及最小錯(cuò)誤要求。6.2基本粒子群優(yōu)化算法6.2.2參數(shù)分析共性

（1）都屬于仿生算法；（2）都屬于全局優(yōu)化方法；（3）都屬于隨機(jī)搜索算法；（4）都隱含并行性；（5）根據(jù)個(gè)體的適配信息進(jìn)行搜索，因此不受函數(shù)約束條件的限制，如連續(xù)性、可導(dǎo)性等；（6）對(duì)高維復(fù)雜問(wèn)題，往往會(huì)遇到早熟收斂和收斂性能差的缺點(diǎn)，都無(wú)法保證收斂到最優(yōu)點(diǎn)。6.2基本粒子群優(yōu)化算法6.2.3與遺傳算法的比較差異

（1）PSO有記憶，所有粒子都保存較優(yōu)解的知識(shí)，而GA，以前的知識(shí)隨著種群的改變被改變；（2）PSO中的粒子是一種單向共享信息機(jī)制。而GA中的染色體之間相互共享信息，使得整個(gè)種群都向最優(yōu)區(qū)域移動(dòng)；（3）GA需要編碼和遺傳操作，而PSO沒(méi)有交叉和變異操作，粒子只是通過(guò)內(nèi)部速度進(jìn)行更新，因此原理更簡(jiǎn)單、參數(shù)更少、實(shí)現(xiàn)更容易。6.2基本粒子群優(yōu)化算法6.2.3與遺傳算法的比較用途

基本PSO是用來(lái)解決連續(xù)問(wèn)題優(yōu)化的，離散二進(jìn)制PSO用來(lái)解決組合優(yōu)化問(wèn)題。運(yùn)動(dòng)方程不同

粒子的位置只有(0,1)兩種狀態(tài)。速度值越大，則粒子位置取1的可能性越大，反之越小。6.3改進(jìn)粒子群優(yōu)化算法6.3.1離散二進(jìn)制PSO思路

在考慮實(shí)際優(yōu)化問(wèn)題時(shí)，往往希望先采用全局搜索，使搜索空間快速收斂于某一區(qū)域，然后采用局部精細(xì)搜索以獲得高精度的解。研究發(fā)現(xiàn)，較大的w

值有利于跳出局部極小點(diǎn)，而較小的w

值有利于算法收斂，因此提出了自適應(yīng)調(diào)整的策略，即隨著迭代的進(jìn)行，線性地減小w

的值。6.3改進(jìn)粒子群優(yōu)化算法6.3.2慣性權(quán)重模型變化的慣性權(quán)重

wmax、wmin分別是w的最大值和最小值；iter、itermax分別是當(dāng)前迭代次數(shù)和最大迭代次數(shù)。6.3改進(jìn)粒子群優(yōu)化算法6.3.2慣性權(quán)重模型提出

1999年Clerc對(duì)算法的研究證明，采用收斂因子能

夠確保算法的收斂。收斂因子模型

通常將φ設(shè)為4.1，經(jīng)計(jì)算k為0.729。6.3改進(jìn)粒子群優(yōu)化算法6.3.3收斂因子模型主要研究方向主要集中于對(duì)算法結(jié)構(gòu)和性能的改善方面，包括：參數(shù)設(shè)置、粒子多樣性、種群結(jié)構(gòu)和算法的融合。發(fā)展方向

目前大部分成果都是通過(guò)大量試驗(yàn)獲得的，缺少對(duì)算法機(jī)理的研究，對(duì)PSO中的參數(shù)分析沒(méi)有實(shí)質(zhì)性的認(rèn)識(shí)，還處于試驗(yàn)分析階段。6.3改進(jìn)粒子群優(yōu)化算法6.3.4研究現(xiàn)狀華東理工大學(xué)自動(dòng)化系2007年交換子和交換序設(shè)n個(gè)節(jié)點(diǎn)的TSP問(wèn)題的解序列為s=(ai)，i=1…n。定義交換子SO(i1,i2)為交換解S中的點(diǎn)ai1和ai2，則S’=S+SO(i1,i2)為解S經(jīng)算子SO(i1,i2)操作后的新解。一個(gè)或多個(gè)交換子的有序隊(duì)列就是交換序，記作SS，SS=(SO1,SO2,…SON)。其中，SO1,…,SON等是交換子，之間的順序是有意義的,意味著所有的交換子依次作用于某解上。6.4粒子群優(yōu)化算法的應(yīng)用6.4.1求解TSP問(wèn)題符號(hào)的定義若干個(gè)交換序可以合并成一個(gè)新的交換序，定義為兩個(gè)交換序的合并算子。設(shè)兩個(gè)交換序SS1和SS2按先后順序作用于解S上，得到新解S’。假設(shè)另外有一個(gè)交換序SS’作用于同一解S上，能夠得到形同的解S’，可定義6.4粒子群優(yōu)化算法的應(yīng)用6.4.1求解TSP問(wèn)題符號(hào)的定義和屬于同一等價(jià)集，在交換序等價(jià)集中，擁有最少交換子的交換序稱為該等價(jià)集的基本交換序。6.4粒子群優(yōu)化算法的應(yīng)用6.4.1求解TSP問(wèn)題解決TSP問(wèn)題的速度算式定義

α、β為[0,1]上的隨機(jī)數(shù)。

vid表示交換序，xid表示路徑序列（解）。6.4粒子群優(yōu)化算法的應(yīng)用6.4.1求解TSP問(wèn)題算法流程

1.初始化粒子群，給每個(gè)粒子一個(gè)初始解(xid)和隨機(jī)的交換序(vid);2.如果滿足結(jié)束條件，轉(zhuǎn)步驟5;3.根據(jù)粒子當(dāng)前位置xid計(jì)算下一新解xid’;4.如果整個(gè)群體找到一個(gè)更好的解，更新Pgd，轉(zhuǎn)步驟2;5.顯示結(jié)果。6.4粒子群優(yōu)化算法的應(yīng)用6.4.1求解TSP問(wèn)題算法流程

3.根據(jù)粒子當(dāng)前位置xid計(jì)算下一新解xid’:1）計(jì)算A=pid-xid，A是一個(gè)基本交換序，表示A作用于xid得到pid；

2）計(jì)算B=pgd-xid，B也是一個(gè)基本交換序；

3）更新速度，并將其轉(zhuǎn)換為一個(gè)基本交換序；

4）更新解；

5）如果找到一個(gè)更好得解，更新pid。6.4粒子群優(yōu)化算法的應(yīng)用6.4.1求解TSP問(wèn)題運(yùn)行結(jié)果

α=0.25

β=0.25

迭代次數(shù)=200

粒子數(shù)=806.4粒子群優(yōu)化算法的應(yīng)用6.4.1求解TSP問(wèn)題10城市TSP問(wèn)題（d*=2.691）0.40.4439;0.24390.1463;0.17070.2293;0.22930.761;0.51710.9414;0.87320.6536;0.68780.5219;0.84880.3609;0.66830.2536;0.61950.2634運(yùn)行結(jié)果

6.4粒子群優(yōu)化算法的應(yīng)用6.4.1求解TSP問(wèn)題運(yùn)行結(jié)果

6.4粒子群優(yōu)化算法的應(yīng)用6.4.1求解TSP問(wèn)題運(yùn)行結(jié)果

6.4粒子群優(yōu)化算法的應(yīng)用6.4.1求解TSP問(wèn)題運(yùn)行結(jié)果

6.4粒子群優(yōu)化算法的應(yīng)用6.4.1求解TSP問(wèn)題運(yùn)行結(jié)果

6.4粒子群優(yōu)化算法的應(yīng)用6.4.1求解TSP問(wèn)題運(yùn)行結(jié)果

6.4粒子群優(yōu)化算法的應(yīng)用6.4.1求解TSP問(wèn)題運(yùn)行結(jié)果

6.4粒子群優(yōu)化算法的應(yīng)用6.4.1求解TSP問(wèn)題神經(jīng)網(wǎng)絡(luò)的訓(xùn)練

主要包含3個(gè)方面：連接權(quán)重、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及傳

遞函數(shù)、學(xué)習(xí)算法。

每個(gè)粒子包含神經(jīng)網(wǎng)絡(luò)的所有參數(shù)，通過(guò)迭代來(lái)優(yōu)

化這些參數(shù)，從而達(dá)到訓(xùn)練的目的。與BP算法相比，使用PSO訓(xùn)練神經(jīng)網(wǎng)絡(luò)的優(yōu)點(diǎn)在于不使用梯度信息，可使用一些不可微的傳遞函數(shù)。多數(shù)情況下其訓(xùn)練結(jié)果優(yōu)于BP算法，而且訓(xùn)練速度非?？臁?.4粒子群優(yōu)化算法的應(yīng)用6.4.2其它應(yīng)用參數(shù)優(yōu)化