基于混沌局部搜索的粒子群算法及其應(yīng)用

劉道文，楊擁軍

(許昌學(xué)院 電氣機電工程學(xué)院，河南 許昌 461000)

0 引 言

工程實際問題的決策往往涉及到最優(yōu)控制或最佳方案選擇，在多個備選或可行方案中確定最佳的方案，其實質(zhì)是通過構(gòu)建適當?shù)臄?shù)學(xué)模型將決策問題轉(zhuǎn)化為問題狀態(tài)空間上的全局最小值求解問題[1]。在求解問題狀態(tài)空間上的最優(yōu)值時通?？梢圆捎镁植績?yōu)化算法和全局優(yōu)化算法等兩大類方法，每類優(yōu)化算法均包含多種具體的優(yōu)化方法且各具優(yōu)缺點，在進行最優(yōu)化計算時需結(jié)合目標問題特點權(quán)衡精度、收斂性、搜索能力和迭代量等指標來選擇和確定合適和具體的優(yōu)化方法[2]。一般地，局部優(yōu)化算法收斂速度快但易陷入局部極小值，全局優(yōu)化算法通過概率性搜索獲得概率意義上的全局最優(yōu)解但其局部搜索能力較低[3]，針對現(xiàn)實中的復(fù)雜多極值最優(yōu)化問題不僅需要在問題狀態(tài)空間的全局范圍內(nèi)搜索最優(yōu)解以避免陷入局部極小值，而且需要提高搜索能力以提升算法效率，基本的解決思路是將不同的優(yōu)化方法結(jié)合，充分發(fā)揮各自優(yōu)勢形成混合優(yōu)化方法[4]?；煦缭谙嗫臻g上能夠不重復(fù)地遍歷所有狀態(tài)，在充分長的時間內(nèi)可以遍歷問題狀態(tài)空間上的每一個點，因此混沌優(yōu)化的基本思想是利用混沌遍歷特性將混沌變量映射到問題狀態(tài)空間，將問題狀態(tài)空間上的最優(yōu)解搜索過程轉(zhuǎn)化為混沌軌跡的遍歷過程[5]，實現(xiàn)對問題狀態(tài)空間的全局搜索以避免陷入局部極小值，但其需要大量的迭代次數(shù)才能搜索到滿足條件最優(yōu)值。粒子群優(yōu)化算法是通過粒子在問題狀態(tài)空間追隨最優(yōu)粒子進行最優(yōu)解搜索，其收斂速度快但存在早熟收斂和局部搜索能力差等問題[6]。

混沌優(yōu)化作為最優(yōu)化理論與應(yīng)用研究新方向，引起學(xué)者廣泛關(guān)注并從最優(yōu)化理論、最優(yōu)化方法以及最優(yōu)化應(yīng)用等層面開展了系列研究，已取得一些研究成果和拓展了混沌優(yōu)化的應(yīng)用領(lǐng)域。徐亮等[7]以混沌擴頻信號作為水聲信號，利用混沌信號相關(guān)性通過相關(guān)法提高測距精度；李騰輝等[8]提出了一種基于混沌人工魚群算法的魯棒保性能控制權(quán)值矩陣優(yōu)化方法，解決了基本人工魚群算法存在的后期收斂速度慢、易陷入局部最優(yōu)等缺點；唐菁敏等[9]提出了一種基于混沌理論的粒子群優(yōu)化LSSVM參數(shù)的短期負荷預(yù)測的方法。

1 混沌遍歷性

混沌是存在于確定性系統(tǒng)中的類隨機運動，其運動軌跡始終限定在一個特定的混沌吸引域內(nèi)，并在充分長的時間內(nèi)經(jīng)過混沌吸引域內(nèi)任何一個狀態(tài)點而不駐留，如圖1所示。由于混沌運動在特定的吸引域內(nèi)具有的這種不重復(fù)性，可采用迭代的方法從某個初始值開始來遍歷整個相空間，如圖2所示?；煦缇哂械谋闅v性、初始值敏感性、類隨機性和內(nèi)在規(guī)律性為基于混沌理論的最優(yōu)化求解提供了理論依據(jù)[10]。

圖1 混沌相空間軌跡(x-z平面)

圖2 相空間中的混沌迭代序列

2 基于混沌局部搜索粒子群算法

混沌優(yōu)化算法作為一種全局優(yōu)化算法能夠遍歷目標函數(shù)解空間上的各個點和搜索出目標函數(shù)的全局最優(yōu)值，但該算法尚存在搜索結(jié)果精度不高和搜索過程比較耗時等不足，該文提出基于混沌局部搜索粒子群算法以進一步提高最優(yōu)化搜索結(jié)果的精度。

2.1 混沌局部搜索

混沌是一種具有內(nèi)在規(guī)律性、貌似隨機的非線性現(xiàn)象，具有對初始條件極端敏感性、遍歷性和類隨機性[10]，在充分長的時間內(nèi)混沌運動可以不重復(fù)地遍歷相空間中的各個點[11]，因此可以利用這種特性進行最優(yōu)解搜索。粒子群優(yōu)化算法對目標函數(shù)要求低且具有較好的全局尋優(yōu)能力，被廣泛地應(yīng)用于最優(yōu)化求解問題，但其也存在早熟收斂和局部搜索能力較弱等不足[12]。為克服粒子群優(yōu)化算法局部搜索能力不足和避免陷入局部極小值，將混沌優(yōu)化納入到粒子群優(yōu)化算法中，利用混沌優(yōu)化進行粒子群局部搜索以跳出局部最優(yōu)搜索區(qū)域，避免陷入局部極小值和實現(xiàn)在全局范圍上搜索最優(yōu)值[13]。利用混沌優(yōu)化進行粒子群局部搜索的基本思想是將決策變量映射為混沌變量區(qū)間迭代產(chǎn)生新的混沌序列值，再將其進行速度和位置更新，并通過目標函數(shù)對新解進行評價直至搜索到局部最優(yōu)值?；煦缇植克阉魉惴ㄟ^程主要包括混沌變量產(chǎn)生、混沌變量調(diào)制到問題空間、利用混沌序列值求解目標函數(shù)、最優(yōu)解判定、二次優(yōu)化等步驟，具體過程如下[5]：

(1)

(2)

一般地，工程技術(shù)上的最優(yōu)化問題往往是帶約束條件的數(shù)學(xué)模型，針對此類求解最大值(最小值)問題在算法實現(xiàn)時可采用如下流程[14]：

①約束條件判定：初始向量X是0-1均勻分布的隨機序列，利用調(diào)制方法將其調(diào)制到問題空間上的向量Temp_X中，并將Temp_X向量代入約束條件判定函數(shù)中以判定當前初始值是否滿足約束條件，滿足則執(zhí)行算法后續(xù)步驟，否則結(jié)束本次執(zhí)行和重新選擇初始值，直至找到滿足約束條件的初始值為止；

②在找到滿足約束條件初始向量的情況下，利用初始向量計算目標函數(shù)的結(jié)果Max_F，并將其做為最優(yōu)結(jié)果的初始值；

③利用迭代方法生成Logistic混沌序列，將其映射到問題空間定義域上，且代入目標函數(shù)中計算得到對應(yīng)的結(jié)果Temp_F，并將其與Max_F進行比較；若Temp_F>Max_F，則將當前的混沌序列值賦給向量Max_X、Temp_F賦給Max_F；

④判定當前最優(yōu)解是否滿足要求，滿足要求則結(jié)束，否則，重新產(chǎn)生混沌序列用來初始化向量X，并在第一次混沌優(yōu)化得到的搜索空間的基礎(chǔ)上進一步縮小搜索范圍尋找最優(yōu)解，進行二次混沌優(yōu)化，直至搜索到滿足要求的最優(yōu)解。

2.2 基于混沌局部搜索粒子群算法流程

粒子群優(yōu)化算法將每個尋優(yōu)的問題解看作一個只具有速度和位置的粒子，所有的粒子在N維空間通過迭代進行最優(yōu)搜索，各粒子均由目標函數(shù)確定相應(yīng)的適應(yīng)值以用來評價當前位置的優(yōu)劣，在每次迭代中粒子通過跟蹤個體當前最佳位置(pbest)和粒子群體中全局最佳位置(gbest)來確定下一步的運動。

(4)

(5)

式中，d∈[1,N],i∈[1,m]，k為迭代次數(shù)，r1、r2為(0,1)區(qū)間上均勻分布的隨機數(shù)，c1、c2為學(xué)習(xí)因子，ω為慣性因子。

基于混沌局部搜索的粒子群算法將傳統(tǒng)的粒子群算法用于全局搜索，而利用混沌優(yōu)化進行局部搜索，其實現(xiàn)流程如下[5,15]：

①初始化粒子群：用0-1均勻分布的隨機值初始化各粒子的位置和速度，并設(shè)定慣性因子ω、學(xué)習(xí)因子c1和c2、搜索區(qū)間[xmin,xmax]、最大迭代次數(shù)M、混沌搜索最大步數(shù)MaxC以及粒子數(shù)目m等參數(shù)。

②通過目標函數(shù)計算每個粒子的適應(yīng)值，評價各粒子的適應(yīng)度，將當前各粒子的位置和適應(yīng)值存儲在其對應(yīng)的pbest中，并將全體最優(yōu)的位置和適應(yīng)值存儲在gbest中。

③依據(jù)式(4)和式(5)更新各粒子的位置和速度。

④將各粒子代入目標函數(shù)中計算對應(yīng)的目標函數(shù)值，保留粒子群體中一定比例(p%)的適應(yīng)函數(shù)值最優(yōu)的粒子，并對其進行混沌局部搜索，相應(yīng)地更新各粒子的pbest和gbest。

⑤若混沌局部搜索滿足預(yù)設(shè)精度要求或者達到最大迭代次數(shù)，則停止搜索和輸出結(jié)果，否則轉(zhuǎn)下一步執(zhí)行。

⑥按照式(6)和式(7)收縮搜索區(qū)域，式中r∈(0,1)，xg,i表示當前pbest的第i維向量值。

xmin,i=max{xmin,i,xg,i-r*(xmax,i-xmin,i)}

(6)

xmax,i=max{xmax,i,xg,i-r*(xmax,i-xmin,i)}

(7)

⑦在收縮后的新區(qū)域內(nèi)隨機生成(1-p%)比例的粒子替代原粒子群中性能較差的粒子，轉(zhuǎn)步驟②繼續(xù)執(zhí)行。基于混沌局部搜索的粒子群算法的實現(xiàn)流程如圖3所示。

圖3 基于混沌局部搜索的粒子群算法流程

3 算例分析

Rosenbrock函數(shù)等高線大致呈拋物線形，如圖4所示，其全局最小值0在香蕉型山谷(1,1)點處，但山谷內(nèi)數(shù)值變化較小，不易搜索到該全域最小值，可以用該函數(shù)來測試和衡量基于混沌局部搜索的粒子群算法的性能。因此，分別用混沌優(yōu)化算法和基于混沌局部搜索粒子群算法來對算例Rosenbrock函數(shù)進行全局尋優(yōu)，并分析比較二者的搜索結(jié)果。

針對基于混沌局部搜索粒子群算法，設(shè)置粒子數(shù)為50、學(xué)習(xí)因子c1和c2為2、慣性因子ω為0.8、適應(yīng)度最佳粒子比例為20%、最大迭代次數(shù)為8 000、混沌最大迭代步數(shù)為10，并對其進行全局最小值尋優(yōu)搜索。為對比和評價基于混沌局部搜索的粒子群算法性能，取μ=4的Logistic混沌序列利用混沌優(yōu)化算法對Rosenbrock函數(shù)進行全局最小值尋優(yōu)搜索，最大迭代次數(shù)設(shè)置為10 000；考慮混沌優(yōu)化算法在遍歷狀態(tài)空間上相點時需要充分長的時間，同時為保證兩種算法在迭代次數(shù)上的一致性，利用混沌優(yōu)化對Rosenbrock函數(shù)進行全局尋優(yōu)時，最大迭代次數(shù)亦設(shè)置為10 000。為便于直觀分析和對比兩種優(yōu)化算法的性能，采用均方根誤差(RMSE)來衡量搜索結(jié)果與理論值的偏差。

圖4 Rosenbrock函數(shù)

(8)

式中，s(i)是每次尋優(yōu)搜索的結(jié)果，t是目標函數(shù)理論最優(yōu)值。仿真過程中分別利用兩種優(yōu)化算法對Rosenbrock函數(shù)隨機連續(xù)進行10次尋優(yōu)搜索，并計算出相應(yīng)的均方根誤差，兩種優(yōu)化算法搜索結(jié)果和均方根誤差如表1所示。仿真計算結(jié)果表明，基于混沌局部搜索的粒子群算法能夠較準確地搜索出全局最優(yōu)值。

表1 搜索結(jié)果與誤差分析

4 基于混沌局部搜索粒子群算法應(yīng)用

隨著經(jīng)濟社會的快速發(fā)展和人民生活水平的不斷提高，國內(nèi)城市機動車保有量普遍呈現(xiàn)快速增長態(tài)勢，而當前停車設(shè)施的建設(shè)卻未能很好地滿足停車需求的增加，形成了“停車難”和“停車亂”等社會交通問題，已在相當程度上阻礙了城市交通的健康發(fā)展和制約了管理服務(wù)水平的持續(xù)提升。對于國內(nèi)大多數(shù)城市而言，加強停車設(shè)施建設(shè)是緩解停車供需結(jié)構(gòu)性矛盾的關(guān)鍵途徑，并已成為城市規(guī)劃和建設(shè)的緊迫任務(wù)，因此，科學(xué)地進行停車場規(guī)劃能夠為規(guī)劃部門的決策提供有力的支持，具有應(yīng)用價值和現(xiàn)實意義。

為深化供給側(cè)改革和加大停車設(shè)施建設(shè)力度，某市規(guī)劃在4個小區(qū)周邊建設(shè)配套的公共停車場，緩解“停車難”的結(jié)構(gòu)性矛盾，城市規(guī)劃和交通管理部門根據(jù)歷史數(shù)據(jù)和經(jīng)驗提供了各小區(qū)的坐標和停車場建設(shè)的相關(guān)指標數(shù)據(jù)，如表2所示，停車場最優(yōu)選址的目標是要根據(jù)這些數(shù)據(jù)和指標確定單位出行成本最小的停車場建設(shè)位置坐標。建模時將各小區(qū)抽象成坐標點，將小區(qū)到停車場的實際路線長度抽象成二者間的直線距離，依據(jù)文獻[16]方法，出行單位總成本是各小區(qū)到停車場距離與其停車吸引量、權(quán)系數(shù)積的總和。因此，停車場選址決策問題的優(yōu)化目標函數(shù)可以用式(9)描述。

(9)

式中，Ti表示各小區(qū)的停車吸引量，ωi表示各小區(qū)的權(quán)系數(shù)，(xi,yi)表示各小區(qū)坐標，(u,v)表示停車場最優(yōu)選址位置坐標，f(x)表示對應(yīng)的單位成本值。

表2 新建小區(qū)坐標與相關(guān)指標

根據(jù)式(9)，代入表2數(shù)據(jù)建立停車場最優(yōu)選址數(shù)學(xué)模型，如式(10)所示。

minf(x)=

(10)

基于混沌局部搜索的粒子群算法進行目標問題求解，在進行停車場最優(yōu)選址仿真計算時，設(shè)置粒子數(shù)為50、學(xué)習(xí)因子c1和c2為2、慣性因子ω為0.8、適應(yīng)度最佳粒子比例為20%、最大迭代次數(shù)為9 000、混沌最大迭代步數(shù)為10，對目標函數(shù)進行全局最小值尋優(yōu)搜索，同時利用混沌優(yōu)化算法對目標函數(shù)進行全局最小值尋優(yōu)搜索[17]。在最優(yōu)化計算時在程序中設(shè)置了10次循環(huán)執(zhí)行，相應(yīng)地得到10個坐標點(如圖5所示)及與其分別對應(yīng)的單位成本值，并從搜索得到的10個單位成本值中確定最優(yōu)結(jié)果。

圖5 搜索得到的停車場坐標分布

從圖5可以看出，基于混沌局部搜索的粒子群算法搜索得到的停車場位置坐標點更逼近理論上的最佳位置點。利用式(8)對10次優(yōu)化計算得出的單位成本進行RMSE誤差分析，結(jié)果如表3所示，證明了該算法的計算結(jié)果優(yōu)于混沌優(yōu)化計算結(jié)果，更逼近理論最優(yōu)值，且誤差分析結(jié)果與圖5所示的停車場坐標分布具有一致性。

表3 停車場最優(yōu)選址結(jié)果與誤差分析

應(yīng)用研究結(jié)果表明，基于混沌局部搜索的粒子群算法提高了優(yōu)化結(jié)果的精度，驗證其在停車場最優(yōu)選址決策上具有可行性和有效性。

5 結(jié)束語

基于混沌局部搜索的粒子群算法結(jié)合混沌優(yōu)化算法和粒子群優(yōu)化算法對目標函數(shù)進行全局最優(yōu)化求解，利用粒子群算法進行全局搜索，在此基礎(chǔ)上收縮搜索區(qū)域并利用混沌優(yōu)化算法進行混沌局部搜索避免粒子群早熟。仿真研究結(jié)果表明，基于混沌局部搜索的粒子群算法搜索結(jié)果精度優(yōu)于混沌優(yōu)化算法，能夠解決停車場最優(yōu)選址決策問題。但該算法以概率性搜索為基礎(chǔ)，蘊含了一定的隨機性，難以憑借單次尋優(yōu)搜索來判定搜索結(jié)果為最優(yōu)解，需要通過連續(xù)多次仿真計算來考查整體尋優(yōu)情況和確定最優(yōu)解。因此，該算法的效率仍有待改進和提高，這將作為后續(xù)進一步研究的方向。