劉道文，楊擁軍

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

0 引 言

工程實(shí)際問(wèn)題的決策往往涉及到最優(yōu)控制或最佳方案選擇，在多個(gè)備選或可行方案中確定最佳的方案，其實(shí)質(zhì)是通過(guò)構(gòu)建適當(dāng)?shù)臄?shù)學(xué)模型將決策問(wèn)題轉(zhuǎn)化為問(wèn)題狀態(tài)空間上的全局最小值求解問(wèn)題[1]。在求解問(wèn)題狀態(tài)空間上的最優(yōu)值時(shí)通?？梢圆捎镁植?jī)?yōu)化算法和全局優(yōu)化算法等兩大類方法，每類優(yōu)化算法均包含多種具體的優(yōu)化方法且各具優(yōu)缺點(diǎn)，在進(jìn)行最優(yōu)化計(jì)算時(shí)需結(jié)合目標(biāo)問(wèn)題特點(diǎn)權(quán)衡精度、收斂性、搜索能力和迭代量等指標(biāo)來(lái)選擇和確定合適和具體的優(yōu)化方法[2]。一般地，局部?jī)?yōu)化算法收斂速度快但易陷入局部極小值，全局優(yōu)化算法通過(guò)概率性搜索獲得概率意義上的全局最優(yōu)解但其局部搜索能力較低[3]，針對(duì)現(xiàn)實(shí)中的復(fù)雜多極值最優(yōu)化問(wèn)題不僅需要在問(wèn)題狀態(tài)空間的全局范圍內(nèi)搜索最優(yōu)解以避免陷入局部極小值，而且需要提高搜索能力以提升算法效率，基本的解決思路是將不同的優(yōu)化方法結(jié)合，充分發(fā)揮各自優(yōu)勢(shì)形成混合優(yōu)化方法[4]。混沌在相空間上能夠不重復(fù)地遍歷所有狀態(tài)，在充分長(zhǎng)的時(shí)間內(nèi)可以遍歷問(wèn)題狀態(tài)空間上的每一個(gè)點(diǎn)，因此混沌優(yōu)化的基本思想是利用混沌遍歷特性將混沌變量映射到問(wèn)題狀態(tài)空間，將問(wèn)題狀態(tài)空間上的最優(yōu)解搜索過(guò)程轉(zhuǎn)化為混沌軌跡的遍歷過(guò)程[5]，實(shí)現(xiàn)對(duì)問(wèn)題狀態(tài)空間的全局搜索以避免陷入局部極小值，但其需要大量的迭代次數(shù)才能搜索到滿足條件最優(yōu)值。粒子群優(yōu)化算法是通過(guò)粒子在問(wèn)題狀態(tài)空間追隨最優(yōu)粒子進(jìn)行最優(yōu)解搜索，其收斂速度快但存在早熟收斂和局部搜索能力差等問(wèn)題[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]以混沌擴(kuò)頻信號(hào)作為水聲信號(hào)，利用混沌信號(hào)相關(guān)性通過(guò)相關(guān)法提高測(cè)距精度；李騰輝等[8]提出了一種基于混沌人工魚群算法的魯棒保性能控制權(quán)值矩陣優(yōu)化方法，解決了基本人工魚群算法存在的后期收斂速度慢、易陷入局部最優(yōu)等缺點(diǎn)；唐菁敏等[9]提出了一種基于混沌理論的粒子群優(yōu)化LSSVM參數(shù)的短期負(fù)荷預(yù)測(cè)的方法。

1 混沌遍歷性

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

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

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

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

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

2.1 混沌局部搜索

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

(1)

(2)

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

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

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

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

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

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

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

(4)

(5)

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

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

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

②通過(guò)目標(biāo)函數(shù)計(jì)算每個(gè)粒子的適應(yīng)值，評(píng)價(jià)各粒子的適應(yīng)度，將當(dāng)前各粒子的位置和適應(yīng)值存儲(chǔ)在其對(duì)應(yīng)的pbest中，并將全體最優(yōu)的位置和適應(yīng)值存儲(chǔ)在gbest中。

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

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

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

⑥按照式(6)和式(7)收縮搜索區(qū)域，式中r∈(0,1)，xg,i表示當(dāng)前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)隨機(jī)生成(1-p%)比例的粒子替代原粒子群中性能較差的粒子，轉(zhuǎn)步驟②繼續(xù)執(zhí)行?；诨煦缇植克阉鞯牧Ｗ尤核惴ǖ膶?shí)現(xiàn)流程如圖3所示。

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

3 算例分析

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

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

圖4 Rosenbrock函數(shù)

(8)

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

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

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

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

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

(9)

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

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

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

minf(x)=

(10)

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

圖5 搜索得到的停車場(chǎng)坐標(biāo)分布

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

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

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

5 結(jié)束語(yǔ)

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