萊維飛行與粒子群的混合搜索算法

牛海帆，宋衛(wèi)平，寧愛平

(太原科技大學(xué)電子信息工程學(xué)院，太原 030024)

?

萊維飛行與粒子群的混合搜索算法

牛海帆，宋衛(wèi)平，寧愛平

(太原科技大學(xué)電子信息工程學(xué)院，太原 030024)

摘要：粒子群算法在解決多維的復(fù)雜優(yōu)化問題時(shí)，存在收斂精度不高和易陷入局部收斂等不足，針對這些問題，將萊維飛行與偏好隨機(jī)游動引入粒子群算法中，提出萊維飛行與粒子群的混合搜索算法。在該算法的解更新過程中，采用萊維飛行、偏好隨機(jī)游動與粒子群算法的更新方程以串行方式對得到的解進(jìn)行更新尋優(yōu)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的混合算法與粒子群算法相比較，加快了收斂速度，提高了搜索精度。

關(guān)鍵詞：粒子群優(yōu)化算法；萊維飛行；函數(shù)優(yōu)化

粒子群算法(PSO)[1-2]是在1995年由Kennedy和Eberhart提出的一種元啟發(fā)式算法，同遺傳算法[3]、蟻群算法[4]、螢火蟲算法[5]等類似，是基于群體搜索策略的群智能優(yōu)化算法。該算法原理簡單、參數(shù)少，易于編程實(shí)現(xiàn)。然而，基本的粒子群算法亦存在缺點(diǎn)：易陷入早熟收斂，解的質(zhì)量不高等。近年來研究者們?nèi)匀灰恢痹谂λ惴ㄌ岢龈倪M(jìn)，如：李俊吉、崔志華、崔炎在2010年提出了一種空間分割微粒群算法[6]，張英杰、邵歲峰在2011年提出了基于云模型的粒子群算法[7]；Zahra Beheshti，Siti Mariyam Shamsuddin，Siti Sophiayati Yuhaniz在2013年提出了一種二進(jìn)制加速粒子群算法[8]；G.Giftson Samuel， C.Christober Asir Rajan在2015年提出了將粒子群算法、遺傳算法、和蛙跳算法相融合的一種混合算法[9]等。每種改進(jìn)算法都在不同程度上提高了收斂性能，但仍然存在諸多不足。文獻(xiàn)[6]中的算法對低維耦合性的測試函數(shù)的尋優(yōu)能力較差。文獻(xiàn)[7]中的算法參數(shù)較多，且參數(shù)的選擇對算法性能的影響還有待進(jìn)一步證明與研究。文獻(xiàn)[8]中的算法局限于解決離散優(yōu)化問題。文獻(xiàn)[9]中的算法結(jié)構(gòu)復(fù)雜，不易編程。

萊維飛行[10]是一種隨機(jī)行走，其飛行間隔服從冪率分布。在智能優(yōu)化算法中應(yīng)用萊維飛行，能夠擴(kuò)大搜索范圍、增加種群多樣性[11]，更加容易跳出局部最優(yōu)點(diǎn)。在本文中，將萊維飛行搜索方法應(yīng)用于粒子群算法，正好能夠彌補(bǔ)粒子群算法存在的不足。通過對5個(gè)基準(zhǔn)測試函數(shù)的仿真測試，仿真結(jié)果表明這種改進(jìn)算法的收斂性能明顯優(yōu)于基本的粒子群算法。

1PSO算法

在基本PSO中，設(shè)有n個(gè)粒子構(gòu)成一個(gè)群體，其中第i個(gè)粒子的位置由D維向量Xi=(xi1,xi2,…,xiD)來表示，速度用Vi=(vi1,vi2，…,viD)來表示。粒子的初始位置和初始速度是在搜索區(qū)域內(nèi)隨機(jī)初始化得到的。每個(gè)粒子的位置代表一個(gè)解，將向量Xi代入目標(biāo)函數(shù)就可以計(jì)算出其適應(yīng)值f1，比較各粒子的適應(yīng)值，適應(yīng)值最小的位置即是目前群體的最優(yōu)位置。在粒子第t+1次迭代中，粒子的位置與速度更新公式如下：

Vg+1,i=ωVg,i+c1r1(Pg,i-Xg,i)+c2r2(Pg-Xg,i)

(1)

Xg+1,i=Xg,i+Vg+1,i

(2)

式中，ω是慣性權(quán)重，c1、c2是學(xué)習(xí)因子；r1、r2是介于(0,1)之間服從均勻分布的隨機(jī)數(shù)；Vg,i和Xg,i分別代表了第g代第i個(gè)粒子的速度和位置；Pg+1,i是第i個(gè)粒子目前搜索到的最優(yōu)位置，Pg是整個(gè)種群搜索到的歷史最優(yōu)值。

2萊維飛行與粒子群的混合搜索算法

2.1　萊維飛行

萊維飛行隨機(jī)游動是一種很好的搜索策略，其飛行的步長滿足一個(gè)重尾的穩(wěn)定分布。在智能優(yōu)化算法中采用萊維飛行，能夠擴(kuò)大搜索范圍、增加種群多樣性，更容易跳出局部收斂。

在粒子群算法中采用萊維飛行對目前的粒子位置Xi進(jìn)行更新，更新公式為：

Xg+1,i=Xg,i+α⊕Levy(β)

(3)

式中，Xg,i是g代第i個(gè)粒子的位置；α是步長因子；⊕是點(diǎn)乘積，Levy(β)為隨機(jī)搜索路徑，Levy(β)表示服從參數(shù)為β的萊維分布，即：

Levy(β)~u=t-1-β

(4)

采用式(5)計(jì)算萊維隨機(jī)數(shù)[12]：

(5)

其中u，v均服從標(biāo)準(zhǔn)正態(tài)分布；β的取值區(qū)間一般為1<β<3，在本文中，β=1.5；

(6)

式中Γ是標(biāo)準(zhǔn)的Gamma函數(shù)。

由以上式子可知萊維飛行更新位置方程為：

(7)

2.2　偏好隨機(jī)游動

隨機(jī)游動在解決定位目標(biāo)的查找問題時(shí)具有很好的能力，所以將其應(yīng)用在智能優(yōu)化算法中能夠加快找到最優(yōu)解的速度。在優(yōu)化算法的解更新過程中，按一定的概率(發(fā)現(xiàn)概率)丟棄部分解之后，算法采用偏好隨機(jī)游動重新生成相同數(shù)量的新解，見式(8)：

Xg+1,i=Xg,i+r(Xg,l-Xg,k)

(8)

其中r是(0,1)區(qū)間內(nèi)服從均勻分布的隨機(jī)數(shù)；Xg,l和Xg,k是代表第g代的兩個(gè)不同的隨機(jī)解。

2.3　混合算法的步驟

混合算法的基本思想就是將萊維飛行和偏好隨機(jī)游動引入粒子群算法，彌補(bǔ)粒子群算法收斂精度低、易陷入局部收斂的不足。這種新的搜索算法定名為HPSO.如圖1為HPSO算法的流程。

圖1　混合粒子群算法流程圖

混合算法步驟如下：

步驟1：目標(biāo)函數(shù)f(X)，初始化種群A和B.隨機(jī)產(chǎn)生n個(gè)粒子的初始位置和初始速度，每個(gè)粒子的位置代表一個(gè)解。搜索空間維數(shù)為D，設(shè)置粒子群算法的其他基本參數(shù)。

步驟2：對A種群根據(jù)式(7)更新粒子位置，評價(jià)適應(yīng)度值，將A中的s個(gè)較優(yōu)粒子位置替換掉B中的相應(yīng)個(gè)體。

步驟3：對步驟2更新后的B種群按式(1)和(2)更新粒子速度和位置，比較適應(yīng)度值，將B中的s個(gè)較優(yōu)粒子位置替換掉A中的相應(yīng)個(gè)體。

步驟4：對步驟3更新后的A種群按隨機(jī)偏好游動更新式(8)更新當(dāng)前位置，保留較優(yōu)位置。

步驟5：判斷是否滿足結(jié)束條件，若達(dá)到，則循環(huán)結(jié)束，否則，返回步驟2.

步驟6：輸出全局最優(yōu)值。

3對函數(shù)優(yōu)化問題的實(shí)驗(yàn)研究

3.1　實(shí)驗(yàn)設(shè)計(jì)

為了觀察混合算法求解多維優(yōu)化問題的收斂速度和收斂精度，選擇的測試環(huán)境為：Windows7，內(nèi)存4 G，MATLAB7.1.將HPSO應(yīng)用在5個(gè)測試函數(shù)中，見表1.f1是簡單的單峰函數(shù)。f2-f4是多峰函數(shù)，其局部極值點(diǎn)隨維數(shù)的增加而增加。f5在維數(shù)為2或3時(shí)是復(fù)雜的單峰函數(shù)，但維數(shù)高時(shí)可能有多個(gè)極值點(diǎn)。

表1　測試函數(shù)

實(shí)驗(yàn)中參數(shù)具體設(shè)置為：PSO算法中，種群大小設(shè)置為20，慣性權(quán)重ωmax=0.9，ωmin=0.4，c1=c2=2.0.在HPSO算法中，參數(shù)設(shè)置與PSO算法相同，兩種算法分別對5個(gè)基準(zhǔn)測試函數(shù)的最小值尋優(yōu)，分別獨(dú)立運(yùn)行50次后取平均值作為最終的測試結(jié)果。

3.2　實(shí)驗(yàn)結(jié)果與分析

3.2.1收斂精度與收斂速度測試

固定最大迭代次數(shù)為2 000.實(shí)驗(yàn)結(jié)果如表2-6和圖2-6所示。在表2-6中分別比較了HPSO和PSO算法下的最優(yōu)值、最差值、平均值、中位數(shù)、標(biāo)準(zhǔn)差值。圖2-6是函數(shù)f1、f2、f3、f4、f5采用HPSO和PSO算法獨(dú)立運(yùn)行50次的平均適應(yīng)度值的進(jìn)化曲線圖。實(shí)驗(yàn)結(jié)果顯示，在優(yōu)化f2、f3函數(shù)時(shí)，HPSO雖然后期收斂速度較慢，但仍然比PSO算法具有更好的優(yōu)化能力。在優(yōu)化f1、f5函數(shù)時(shí)，雖然在前期HPSO算法的收斂速度沒有PSO算法快，但是HPSO更易跳出局部收斂，得出比PSO算法更優(yōu)的解。HPSO明顯具有較好的收斂精度和較快的收斂速度。在優(yōu)化f4函數(shù)時(shí)，雖然兩種算法的收斂精度沒有明顯提高，但HPSO與PSO相比具有更快的收斂速度。結(jié)果表明，總體上來說HPSO算法比PSO算法性能更優(yōu)。

3.2.2固定目標(biāo)精度的成功率和迭代次數(shù)測試

表7為5種基準(zhǔn)測試函數(shù)在各自固定的目標(biāo)精度下獨(dú)立運(yùn)行50次的成功率和迭代次數(shù)，其最大迭代次數(shù)設(shè)置為2 000.由表7 可以看出，HPSO在已設(shè)置的條件下，能夠100%的達(dá)到目標(biāo)精度，而PSO的成功率相對較低。同時(shí)，HPSO算法達(dá)到目標(biāo)精度的迭代次數(shù)明顯比PSO算法少。實(shí)驗(yàn)結(jié)果說明，HPSO算法的優(yōu)化能力比PSO算法好。

表2　sphere函數(shù)實(shí)驗(yàn)結(jié)果

表3　griewank函數(shù)實(shí)驗(yàn)結(jié)果

表4　rastrigin函數(shù)實(shí)驗(yàn)結(jié)果

表5　schaffer函數(shù)實(shí)驗(yàn)結(jié)果

表6　rosenbrock函數(shù)實(shí)驗(yàn)結(jié)果

表7　在固定目標(biāo)精度下的迭代次數(shù)

圖2　sphere函數(shù)在20維下的進(jìn)化曲線

圖3　griewank函數(shù)在20維下的進(jìn)化曲線

圖4　Rastrigin函數(shù)在20維下的進(jìn)化曲線

圖5　schaffer函數(shù)在20維下的進(jìn)化曲線

圖6　rosenbrock函數(shù)在20維下的進(jìn)化曲線

4結(jié)論

對基本的粒子群算法與萊維飛行和隨機(jī)偏好游動相結(jié)合，利用萊維飛行搜索范圍大、易跳出早熟收斂的優(yōu)點(diǎn)和偏好隨機(jī)游動的優(yōu)勢，彌補(bǔ)了粒子群易陷入局部極值點(diǎn)的不足，達(dá)到了改進(jìn)的目的。對幾個(gè)基準(zhǔn)測試函數(shù)算法進(jìn)行了仿真測試，并對改進(jìn)算法與基本粒子群算法進(jìn)行了比較分析。仿真結(jié)果表明了這種串行的改進(jìn)粒子群算法解決尋優(yōu)問題的有效性。

參考文獻(xiàn)：

[1]RICARDO DE A L RABLO，MARCUS V LEMOS，DANIEL BARBOSA.Power System Harmonics Estimation using Particle Swarm Optimization[C]∥IEEE World Congress on Computational Intelligence.Brisbane，Australia，2012：10-15.

[2]JEHAD ABABNEH.Greedy particle swarm and biogeography-based optimization algorithm[J].International Journal of Intelligent Computing and Cybernetics，2015，8(1)：28-49.

[3]CLAUDIO FABIANO，MOTTA TOLEDO，LUCAS DE OLIVEIRA，et al.A genetic algorithm/mathematical programming approach to solve a two-level soft drink production problem[J].Computers & Operations Research，2014，48(2)：40-52.

[4]周明秀，程科，汪正霞.動態(tài)路徑規(guī)劃中的改進(jìn)蟻群算法[J].計(jì)算機(jī)科學(xué)，2013，40(1)：314-316.

[5]歐陽喆，周永權(quán).自適應(yīng)步長螢火蟲優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用，2011，31(7)：1084-1087.

[6]李俊吉，崔志華，崔炎.空間分割微粒群算法[J].太原科技大學(xué)學(xué)報(bào)，2010，31(1)：19-24.

[7]張英杰，邵歲鋒.一種基于云模型的云變異粒子群算法[J].模式識別與人工智能，2011，24(1)：90-96.

[8]ZAHRA BEHESHTI，SITI MARIYAM SHAMSUDDIN，SITI SOPHIAYATI YUHANIZ.Binary Accelerated Particle Swarm Algorithm (BAPSA)for discrete optimization problems[J].Journal of Global Optimization，2013，57(2)：549-573.

[9]GIFTSON SAMUEL G，CHRISTOBER ASIR RAJAN C.Hybrid：Particle Swarm Optimization-Genetic Algorithm and Particle Swarm Optimization-Shuffled Frog Leaping Algorithm for Long-term Generator Maintenance Scheduling[J].International Journal of Electrical Power and Energy Systems，2015，65(3)：432-444.

[10]YAHYA M，SAKA M P.Construction site layout using multi-objective artificial bee colony algorithm with Levy flights[J].Automation in Construction，2014，38(2)：14-29.

[11]李煜，馬良.新型元啟發(fā)式布谷鳥搜索算法[J].系統(tǒng)工程，2012，30(8)：64-69.

[12]王李進(jìn)，尹義龍，鐘一文.逐維改進(jìn)的布谷鳥搜索算法[J].軟件學(xué)報(bào)，2013，24(11)：2687-2698.

Hybrid Search Algorithm on Particle Swarm Optimization and Levy Flight

NIU Hai-fan，SONG Wei-ping，NING Ai-ping

(School of Electronic and Information Engineering，Taiyuan University of Science and Technology，

Taiyuan 030024，China)

Abstract：Particle swarm optimization algorithm has some weak points to solve multi-dimensional and complex optimization problems.Its convergence precision is not high enough，and it is easy to fall into local convergence.In order to overcome these problems，Levy flight and preference of rand walk are applied in the basic particle swarm optimization algorithm.The main method is to incorporate the updating equation of particle swarm optimization algorithm with levy flight and preference of rand walk in a serial fashion.The experimental results demonstrate that the improved algorithm has considerable advantages in search accuracy and the convergence speed while comparing with the basic particle swarm algorithm.

Key words：particle swarm optimization algorithm，levy flight，function optimization

中圖分類號：TP183

文獻(xiàn)標(biāo)志碼：A

doi：10.3969/j.issn.1673-2057.2016.01.002

文章編號：1673-2057(2016)01-0006-06

作者簡介：牛海帆(1991-)，女，碩士研究生，主要研究方向?yàn)殡姶偶嫒菁肮收显\斷。

基金項(xiàng)目：太原科技大學(xué)博士科研啟動基金(20142003)；太原科技大學(xué)研究生科技創(chuàng)新項(xiàng)目(20145019)

收稿日期：2014-12-29