粒子群算法優(yōu)化研究
發(fā)布時間:2018-06-25 來源: 日記大全 點(diǎn)擊:
[提要] 粒子群算法控制參數(shù)較少、使用簡單,受到很多專家學(xué)者的關(guān)注。但是,傳統(tǒng)粒子群算法在求解非線性規(guī)劃問題時,比較容易陷入局部最優(yōu)而找不到全局最優(yōu)解。本文在算法設(shè)計過程中,對傳統(tǒng)的粒子群算法進(jìn)行改進(jìn),以提高求解效果。
關(guān)鍵詞:非線性規(guī)劃;粒子群算法;回收網(wǎng)絡(luò)
中圖分類號:F27 文獻(xiàn)標(biāo)識碼:A
收錄日期:2017年11月28日
一、引言
粒子群算法(Particle Swarm Optimization,PSO)為常見優(yōu)化算法,是一種模擬鳥類覓食過程來尋求最優(yōu)解的算法,很多問題的優(yōu)化都可以使用,如核動力、車輛調(diào)度、巡回旅行等。因控制參數(shù)少、使用簡單、易實(shí)現(xiàn),粒子群算法受到很多專家學(xué)者的關(guān)注。但是傳統(tǒng)粒子群算法在求解非線性規(guī)劃問題時,比較容易陷入局部最優(yōu)而找不到全局最優(yōu)解,本文在傳統(tǒng)的粒子群算法上進(jìn)行了改進(jìn),以提高求解效果。
二、粒子群算法介紹
粒子群算法(PSO)是一種基于群體的隨機(jī)優(yōu)化方法。傳統(tǒng)的粒子群算法思路如下:
設(shè)S在維目標(biāo)搜索空間中,有m個微粒組成一個群體,那么其中粒子i可以表示為一個S維的向量xi=(xi1,xi2,…,xis),i=1,2,…,m。同理,群體中的每個粒子都可以以同樣的方式表示,每個粒子的位置就是一個可行解。將其預(yù)先設(shè)定的目標(biāo)函數(shù)來計算每一個粒子的適應(yīng)值,并根據(jù)適應(yīng)值大小來衡量粒子所在位置的優(yōu)劣程度。在搜索空間中第i個粒子的飛翔速度也是一個S維向量,記為V=(v1,v2,…,vs)。除了粒子的飛行位置和飛行速度以外,還需要記錄兩個重要的信息:第i個粒子迄今為止搜索到的最優(yōu)位置為PbestiS=(Pbesti1,Pbesti2,…,Pbesti3);整個粒子群迄今為止搜索到的最優(yōu)位置為GbestS=(Gbest1,Gbest2,…,Gbest3)。設(shè)f(x)為目標(biāo)函數(shù),則微粒當(dāng)前最好位置由下式確定:
p(t+1)=pi(t) 若f(xi(t+1))≥f(pi(t))xi(t+1) 若f(xi(t+1))≤f(pi(t))
在基礎(chǔ)上進(jìn)行微粒飛行迭代為兩步操作:位置移動和速度變化,基本迭代公式分別為:
v(t+1)=v(t)+c1·(Gbest[]-present[])+c2·(Pbest-p(t)) (1)
x(t+1)=x(t)+v(t+1) (2)
其中,學(xué)習(xí)因子c1、c2為非負(fù)常數(shù),c1調(diào)節(jié)粒子飛向自身最好位置方向的步長,c2調(diào)節(jié)粒子飛向全局最好位置方向的步長。r1、r2為相互獨(dú)立的偽隨機(jī)數(shù),服從[0,1]上的均勻分布。
經(jīng)典的PSO算法步驟如下:
Step1:初始化一個規(guī)模為m的粒子群,并設(shè)定各個微粒的初始位置和速度。
Step2:設(shè)置適應(yīng)度函數(shù)并計算每個微粒的適應(yīng)值。
Step3:把每個微粒的適應(yīng)值與其經(jīng)歷過的最好位置時的適應(yīng)值作比較,若當(dāng)前微粒所在位置的適應(yīng)值較好,則將其作為微粒當(dāng)前的最好位置。
Step4:把每個微粒的適應(yīng)值與整個粒子群經(jīng)歷過的最好位置時的適應(yīng)值作比較,若當(dāng)前微粒所在位置的適應(yīng)值較好,則將其作為當(dāng)前的粒子群全局的最好位置。
Step5:根據(jù)方程(1)、(2)分別對粒子的速度和位置進(jìn)行更新。
Step6:如果滿足終止條件,則輸出最優(yōu)解;否則返回Step2。
三、改進(jìn)的粒子群算法設(shè)計
基本粒子群算法在求解非線性規(guī)劃問題時,比較容易陷入局部最優(yōu)而找不到全局最優(yōu)解,因此,本文在算法設(shè)計過程中,對傳統(tǒng)的粒子群算法進(jìn)行了改進(jìn),以提高求解效果。改進(jìn)的算法分別采用強(qiáng)引導(dǎo)型粒子群算法和自適應(yīng)粒子群算法對原有位置、速度迭代公式進(jìn)行優(yōu)化,對式(1)、(2)進(jìn)行改進(jìn),使改進(jìn)的位置迭代公式為:
x(t+1)=x(t)+(rand()+k)·v(t)+10-6·rand()
其中,rand()為0~1之間的隨機(jī)數(shù),k為調(diào)節(jié)系數(shù),隨著迭代次數(shù)的增加,調(diào)節(jié)系數(shù)逐漸降低,可取k=kmax-·iter,其中iter表示迭代次數(shù)。速度更新采用自適應(yīng)速度更新公式,在傳統(tǒng)的速度更新公式中隨迭代次數(shù)改變?棕,例如迭代100次,可。
?棕=0.5 1≤gen≤400.1 40≤gen≤600.001 60≤gen≤100
速度更新公式可表示為:
v()=?棕·v()+c1·rand()·(Gbest[]-present[])+c2·rand()(Pbest-present[])
其中,學(xué)習(xí)因子c1和c2為常數(shù),避免粒子陷入局部最優(yōu)并實(shí)現(xiàn)信息共享,以保證粒子的空間搜索能力,數(shù)值大小設(shè)置具體應(yīng)視情況而定。
。ㄒ唬┝W拥木幋a形式。編碼過程是整個算法設(shè)計過程中的難點(diǎn)之一,高效的編碼方式能夠大大減輕模型運(yùn)算的難度,提高模型求解效率,因此編碼的設(shè)計十分關(guān)鍵。再制造物流網(wǎng)絡(luò)中參數(shù)較多,編碼過程需要把每個變量進(jìn)行合理編碼,以保證在交叉迭代過程中解得可行性,并保證迭代效率。主要的編碼設(shè)計思路為:分派過程中對粒子進(jìn)行實(shí)數(shù)編碼,根據(jù)分派比例設(shè)定粒子的每一個分向量,如對I個回收點(diǎn)、J個倉儲點(diǎn)、K個分揀點(diǎn)的編碼可采用如下形式:
。▁1,1…xi,j…xI,J"|y1,1…yj,k…yJ,K||z1,1…zk,s…zK,S||v1,1…vi,j…vI,J||u1,1…uj,k…uJ,K||w1,1…wk,s…wK,S)x代表從回收點(diǎn)到倉庫段粒子的位置,y代表從倉庫到分揀中心段粒子的位置,z代表從分揀中心到再制造中心段粒子的位置,v代表x的變化速度,u代表y的變化速度,w代表z的變化速度,分揀中心到再利用中心的費(fèi)用另外計算。
熱點(diǎn)文章閱讀