分片Lorenz混沌軌道堆棧聚集變密度振蕩搜索算法

林之博，劉媛華

(上海理工大學(xué) 管理學(xué)院，上海 200093)

1 引 言

復(fù)雜連續(xù)函數(shù)極值問(wèn)題是一類(lèi)常見(jiàn)的優(yōu)化難題，對(duì)特定的復(fù)雜函數(shù)，通?？梢酝ㄟ^(guò)求導(dǎo)的方法找出精確極值解.但實(shí)際情況中存在維度較高、求解域廣泛、全局最優(yōu)解在微搜索域褶皺中難以定位的復(fù)雜函數(shù)，精確求解方法往往無(wú)效，只能用啟發(fā)式算法嘗試求出滿意解.目前有學(xué)者提出改進(jìn)混合粒子群算法[1]，針對(duì)特定工程應(yīng)用問(wèn)題有一定的效果；另有研究使用改進(jìn)的水波優(yōu)化求解優(yōu)化問(wèn)題，在水波優(yōu)化算法基礎(chǔ)上融合了單純型法和簡(jiǎn)單Logistic混沌特性，能夠有限提升算法性能[2]；此外常見(jiàn)的優(yōu)化過(guò)的遺傳算法、蟻群算法、粒子群算法等也具有求解中等復(fù)雜連續(xù)函數(shù)極值的能力，但收斂時(shí)間容易過(guò)長(zhǎng)[3].上述算法雖能對(duì)某些問(wèn)題取得較好求解效果，但普遍容易陷入局部最優(yōu)后無(wú)法跳出.

混沌優(yōu)化算法最早是由李兵等人于1997年提出的一類(lèi)智能優(yōu)化算法[4]，該算法理論上具有很強(qiáng)的跳出能力，可以規(guī)避蟻群算法、遺傳算法等陷入局部最優(yōu)無(wú)法跳出的情況[4].通常在該算法中引入Logistic混沌系統(tǒng)[5，6]，利用混沌映射的遍歷性、初值敏感性等特征產(chǎn)生混沌序列作為搜索最優(yōu)解的軌道[1，4].沿該軌道對(duì)解空間進(jìn)行搜索，有更大的可能性找到目標(biāo)最優(yōu)解[4，6].混沌優(yōu)化算法自提出后常被用于結(jié)合改善其他算法，例如結(jié)合混沌系統(tǒng)構(gòu)成新型混沌粒子群算法[1]、混沌鯨魚(yú)算法[5]、以及混沌煙花算法[7]用于解決多維復(fù)雜單目標(biāo)連續(xù)函數(shù)極值問(wèn)題.

雖然現(xiàn)有混沌優(yōu)化算法具有較好跳出局優(yōu)的能力，但Logistic系統(tǒng)模型在數(shù)據(jù)仿真實(shí)驗(yàn)中展現(xiàn)出明顯的過(guò)度邊緣游走現(xiàn)象[8]，導(dǎo)致同等算力下算法對(duì)解空間中心區(qū)域的搜索過(guò)于稀疏，落入局部最優(yōu)可能增大，在李金屏等人的仿真測(cè)試結(jié)果[8]中可得到佐證.故以Logistic為混沌內(nèi)核的算法往往帶有這類(lèi)特性.王德成等人改進(jìn)了Logistic混沌[9]，利用反三角Logistic映射產(chǎn)生混沌軌道，以達(dá)到等概率搜索的目的，但經(jīng)過(guò)點(diǎn)分布檢測(cè)仿真實(shí)驗(yàn)發(fā)現(xiàn)其均勻度魯棒性欠佳，且算法不均衡，收斂性較弱；官國(guó)榮等人提出的改進(jìn)Lorenz系統(tǒng)所得新模型能夠產(chǎn)生更復(fù)雜的混沌行為[10]，但軌道形狀難以規(guī)范到指定區(qū)間.此外，原始的混沌優(yōu)化算法和基于隨機(jī)過(guò)程的智能進(jìn)化算法容易落入微搜索域褶皺上的局部最優(yōu)值，典型例子是在解決高維Griewank函數(shù)極值優(yōu)化問(wèn)題時(shí)，很難找出全局最優(yōu)，在解決“大海撈針問(wèn)題”一類(lèi)函數(shù)時(shí)也非常容易落入包圍式局部極值點(diǎn)，通常增加混沌軌道長(zhǎng)度能緩解該問(wèn)題，但會(huì)導(dǎo)致混沌軌道過(guò)于密集，浪費(fèi)計(jì)算能力的同時(shí)也造成了運(yùn)算時(shí)間增長(zhǎng)[11].

故考慮改進(jìn)設(shè)計(jì)一種新的混沌映射系統(tǒng)，使得混沌軌道均勻度與魯棒性盡可能高；同時(shí)，基于新模型設(shè)計(jì)一套混沌優(yōu)化算法，一定程度上增強(qiáng)跳出局部最優(yōu)的能力并提高算法收斂效率.對(duì)新模型進(jìn)行混沌分布檢測(cè)和算例測(cè)試對(duì)比，以證明該算法具有更好的優(yōu)化性能[11].

2 模型性質(zhì)與改進(jìn)

2.1 混沌系統(tǒng)性質(zhì)

混沌系統(tǒng)是一類(lèi)具有運(yùn)動(dòng)狀態(tài)長(zhǎng)期不可預(yù)測(cè)且對(duì)系統(tǒng)初始狀態(tài)極端敏感的動(dòng)力系統(tǒng)[4].這類(lèi)系統(tǒng)一般由狀態(tài)參量與控制參量共同組成，其中狀態(tài)參量表示系統(tǒng)在狀態(tài)空間里的運(yùn)動(dòng)過(guò)程中所處的位置[12]；而控制參量可對(duì)系統(tǒng)的運(yùn)行狀態(tài)產(chǎn)生顯著影響.從某一時(shí)刻的初始系統(tǒng)狀態(tài)出發(fā)，使系統(tǒng)按照混沌方程式進(jìn)行演化，產(chǎn)生的軌跡局部上完全雜亂無(wú)章，但全局來(lái)看卻具有其規(guī)律性(例如Lorenz混沌)[13].混沌系統(tǒng)常被應(yīng)用于通信加密、工程控制領(lǐng)域，根據(jù)不同需求可用特定手段產(chǎn)生或消減混沌.所有混沌系統(tǒng)運(yùn)動(dòng)普遍具有共同特征，此處對(duì)研究所需的幾種性質(zhì)做出簡(jiǎn)單描述.

性質(zhì)1.混沌系統(tǒng)具有初值敏感性[4].對(duì)任意一個(gè)混沌系統(tǒng)的初始條件給予極其輕微的擾動(dòng)，都可以造成系統(tǒng)運(yùn)行軌跡完全改變.例如Logistic混沌系統(tǒng)中，給予初始Xn大小為10-6的擾動(dòng)，可導(dǎo)致系統(tǒng)運(yùn)動(dòng)到n=24時(shí)，整體偏離值達(dá)到0.8719.因此，在優(yōu)化領(lǐng)域可利用該性質(zhì)產(chǎn)生長(zhǎng)度相等但差異巨大的序列用于生成搜索軌道，即待優(yōu)化函數(shù)的可行解集[6].

性質(zhì)2.混沌系統(tǒng)具有隨機(jī)性，即任何混沌系統(tǒng)狀態(tài)的改變長(zhǎng)期難以預(yù)測(cè)，近乎隨機(jī)[6].例如Lorenz混沌系統(tǒng)從吸引子某一葉上發(fā)生跳轉(zhuǎn)的行為都是隨機(jī)產(chǎn)生的，但這種隨機(jī)行為發(fā)自系統(tǒng)非線性因素[14].該性質(zhì)在合理增強(qiáng)后，有助于加快對(duì)解空間的均衡搜索.

性質(zhì)3.混沌系統(tǒng)具有遍歷性，只要給予足夠長(zhǎng)的時(shí)間，混沌系統(tǒng)能在某范圍內(nèi)永不重復(fù)地游走、經(jīng)過(guò)該空間中所有的系統(tǒng)狀態(tài).利用該性質(zhì)有助于規(guī)避局部最優(yōu)[9].

性質(zhì)4.對(duì)于混沌動(dòng)力學(xué)系統(tǒng)，其Lyapunove指數(shù)與軌道或其等效的映射的表示形式無(wú)關(guān)[15].即對(duì)于線性變換，Lyapunove指數(shù)不會(huì)發(fā)生變化，也不會(huì)改變系統(tǒng)的混沌行為.因此對(duì)混沌軌道進(jìn)行縮放操作不改變系統(tǒng)混沌特性[16，17].

2.2 改進(jìn)混沌系統(tǒng)

原Logistic混沌的方程式如式(1)所示[4，6]，其中X為狀態(tài)參量，μ為控制參量，當(dāng)μ取值為4時(shí)，系統(tǒng)進(jìn)入完全混沌態(tài)；式(2)為王德成等人提出的反三角變換方程式[9].

Xn+1=μXn(1-Xn)

(1)

(2)

對(duì)原Logistic混沌與反三角Logistic系統(tǒng)進(jìn)行對(duì)照分析檢驗(yàn).利用Logistic、反三角Logistic混沌系統(tǒng)各產(chǎn)生兩條長(zhǎng)度為1000的序列，歸一化到[0，1]區(qū)間構(gòu)成XOY上的分布.設(shè)XOY面上混沌區(qū)域中心為(x0，y0)，計(jì)算從中心開(kāi)始逐步等面積間隔擴(kuò)大統(tǒng)計(jì)范圍對(duì)應(yīng)的橫縱坐標(biāo)增量，公式如下：

(3)

其中，UpB為坐標(biāo)軸上限，DownB為坐標(biāo)軸下限.分別統(tǒng)計(jì)軌道上落在公式(4)所示區(qū)間上的點(diǎn)數(shù)，記為序列Counter.

(4)

若一個(gè)混沌系統(tǒng)軌道分布均勻度較高，則Counter曲線線性表現(xiàn)越明顯.計(jì)算Counter中所有元素間差值C[k]-C[k-1]，記為E序列.則混沌軌道均勻度可通過(guò)公式(5)計(jì)算：

(5)

依該方法計(jì)算得出原混沌優(yōu)化中Logistic模型、反三角函數(shù)Logistic混沌軌道分布均勻度指標(biāo)如表1所示.

表1 Logistic與反三角Logistic混沌100次采樣均勻度對(duì)比

作出兩個(gè)混沌系統(tǒng)的Counter序列曲線與混沌分布對(duì)比如圖1所示，圖1(c)所示Logistic混沌邊緣搜索導(dǎo)致的Counter曲線指數(shù)型上翹；而圖1(b)展示的反三角Logistic混沌比圖1(a)所示Logistic混沌分布更加均勻，結(jié)合圖1(d)和表1可見(jiàn)反三角函數(shù)Logistic混沌系統(tǒng)均勻度確實(shí)優(yōu)于原Logistic混沌，但該混沌系統(tǒng)均勻度并不穩(wěn)定，時(shí)大時(shí)小，魯棒性欠佳.

圖1 混沌分布與Counter曲線對(duì)照

為了更好地避免引入Logistic邊緣游走效應(yīng)的影響、并提高混沌軌道均勻度魯棒性，考慮基于Lorenz混沌系統(tǒng)改進(jìn)設(shè)計(jì)新混沌模型.Lorenz混沌是Lorenz于1963年研究天氣演化時(shí)提出的簡(jiǎn)化描述方程，其模型[10]如式(6)-式(8)所示.其中，Xn+1、Yn+1、Zn+1都為L(zhǎng)orenz混沌系統(tǒng)的狀態(tài)參量，a、b、c都是Lorenz混沌系統(tǒng)的控制參量，通常取a=10、b=28、c=8/3.Lorenz系統(tǒng)在空間中呈現(xiàn)蝴蝶翅膀形狀的兩個(gè)混沌吸引子，因此又被稱為“蝴蝶混沌”[10].

Xn+1=Xn+a·(Yn-Xn)·Δs

(6)

Yn+1=Yn+(b·Xn-Xn·Zn-Yn)·Δs

(7)

Zn+1=Zn+(Xn·Yn-c·Zn)·Δs

(8)

由于該系統(tǒng)具有不同于Logistic離散系統(tǒng)的連續(xù)混沌特性，在狀態(tài)空間中進(jìn)行更均勻的遍歷，故減少類(lèi)似Logistic系統(tǒng)邊緣游走的效果更加良好.

對(duì)系統(tǒng)產(chǎn)生的Z軸序列做模運(yùn)算和信號(hào)變換操作如公式(9)所示，可獲得分布較均勻的混沌軌道Zsn+1，并規(guī)避細(xì)微擾動(dòng)時(shí)混沌軌道間偏移過(guò)小的情況.

Zsn+1=Zn+1·IMODGear

(9)

I為信號(hào)放大控制參量，不妨取15或16；Gear用于調(diào)控序列分片模式，當(dāng)Gear=10或Gear=10I時(shí)，軌道都會(huì)喪失隨機(jī)，經(jīng)仿真實(shí)驗(yàn)認(rèn)為取Gear=10I/3時(shí)效果最佳.

使用公式(3)-公式(5)計(jì)算改進(jìn)模型的分布均勻度如表2所示，其二維分布如圖2所示.可知改進(jìn)后模型相對(duì)反三角Logistic混沌系統(tǒng)模型產(chǎn)生的混沌軌道具有更高的分布均勻度和更好的魯棒性.

表2 分片Lorenz混沌100次采樣均勻度

圖2 改進(jìn)Lorenz混沌分布與Counter曲線對(duì)照

故根據(jù)性質(zhì)2，理論上基于新設(shè)計(jì)的混沌系統(tǒng)模型開(kāi)發(fā)新型混沌優(yōu)化算法會(huì)具有更高的搜索效率.為便于描述，后文統(tǒng)一將基于改進(jìn)模型的新型算法簡(jiǎn)稱為“MLC”算法.

3 算法設(shè)計(jì)

3.1 MLC搜索算法框架

設(shè)計(jì)MLC算法總體框架如圖3所示，算法由4項(xiàng)子算法、載波控制器、混沌擾動(dòng)模塊和停機(jī)控制器構(gòu)成.

圖3 算法總框架

算法開(kāi)始需設(shè)定初始化參數(shù)，例如混沌系統(tǒng)狀態(tài)參量和初始可行解等，并指定待優(yōu)化目標(biāo)函數(shù)和優(yōu)化方向.開(kāi)始子迭代過(guò)程，運(yùn)行混沌發(fā)生子算法，由性質(zhì)1：基于2.2設(shè)計(jì)的改進(jìn)模型通過(guò)隨機(jī)微小擾動(dòng)可產(chǎn)生規(guī)定大小的均勻混沌搜索軌道(即可行解集).將產(chǎn)生的軌道輸入到解堆棧子算法中，構(gòu)造解堆棧；由性質(zhì)3可知當(dāng)軌道足夠長(zhǎng)或擾動(dòng)次數(shù)足夠多時(shí)，堆棧中一定包含滿意解.將堆棧放入聚集出棧子算法，根據(jù)堆棧中的解計(jì)算搜索中心.

對(duì)于新產(chǎn)生的搜索中心，使用載波控制器計(jì)算當(dāng)前解下降是否達(dá)到目標(biāo)精度；若未達(dá)到，運(yùn)行搜索域密度縮放子算法縮小搜索的區(qū)域和搜索密度后，轉(zhuǎn)回混沌發(fā)生子算法繼續(xù)進(jìn)行該子迭代；否則，當(dāng)子迭代產(chǎn)生更優(yōu)解時(shí)，進(jìn)入停機(jī)判斷，若子迭代產(chǎn)生解非更優(yōu)，則用振蕩模塊修改子迭代初始搜索上下限后再進(jìn)入停機(jī)判斷.

接下來(lái)對(duì)各項(xiàng)子算法給出詳細(xì)描述.

3.2 混沌發(fā)生子算法

設(shè)F(X)為待優(yōu)化目標(biāo)函數(shù)，其中X={xi}為函數(shù)的i個(gè)變量；另有參數(shù)up、down分別表示由X中各個(gè)變量的區(qū)間上限和下限構(gòu)成的向量；z0為混沌系統(tǒng)的初始Z取值；step為狀態(tài)轉(zhuǎn)移步長(zhǎng)，研究過(guò)程中取值為0.01；times為設(shè)定混沌軌道總長(zhǎng)；aband為混沌系統(tǒng)初始演化軌道上刪去的長(zhǎng)度，用于保證獲得的混沌軌道完全處于混沌狀態(tài)中，一般取100.設(shè)XLorenz(up，down，Z0，step，T，aband)為分片Lorenz混沌模型在第T次移動(dòng)時(shí)產(chǎn)生的混沌Z軸值；取信號(hào)放大參量I=1016，分片參數(shù)Gear=105.混沌發(fā)生子過(guò)程如下：

Input：input={up，down，Z0，step，T，aband}；

Output：TrackMat；

Step 1.初始化Lorenz混沌狀態(tài)參量X、Y、Z，設(shè)置a=10，b=28，c=8/3；設(shè)置系統(tǒng)初始空間位置為x=1，y=1，z=Z0；

Step 2.給予z=1一個(gè)10-4級(jí)別的隨機(jī)擾動(dòng)，按照給定的軌道長(zhǎng)度T利用分片Lorenz混沌系統(tǒng)模型產(chǎn)生混沌軌道；

Step 3.若混沌軌道數(shù)量未達(dá)到待求解問(wèn)題維度，返回Step 2；否則轉(zhuǎn)到Step 4；

Step 4.使用最大最小映射法方法，將混沌軌道壓縮到當(dāng)前搜索域；

Step 5.將混沌軌道作為一個(gè)數(shù)據(jù)矩陣TrackMat輸出.

該算法根據(jù)輸入up、down序列的長(zhǎng)度i產(chǎn)生和返回i個(gè)混沌序列構(gòu)成的可行解集矩陣TrackMat；在輸入變量中引入隨機(jī)過(guò)程來(lái)增加算法的不確定性，每個(gè)變量對(duì)應(yīng)的混沌序列是通過(guò)z加一個(gè)極小的隨機(jī)數(shù)作為初值擾動(dòng)后輸入算法中得到的.故有產(chǎn)生更多完全不同的可行解集的能力，使算法得以多次進(jìn)行泛化運(yùn)行測(cè)試.

3.3 解堆棧子算法

解堆棧子算法可以最快的速度從TrackMat中確定一組逐漸逼近最優(yōu)的解.該算法按照替代優(yōu)化和漸進(jìn)禁忌法則依次將混沌搜索軌道上找出的漸進(jìn)優(yōu)化解壓入堆棧中，在子算法結(jié)束時(shí)棧頂元素必定為本次迭代搜索到的最優(yōu)解.運(yùn)算過(guò)程下：

輸入：TrackMat，order；

輸出：Solution；

Step 1.在搜索域中隨機(jī)選取初始解向量，作為臨時(shí)棧底解；

Step 2.按照順序提取TrackMat中的解，并計(jì)算解值；

Step 3.比較該解和棧頂解，當(dāng)order要求求解最大值時(shí)，若當(dāng)前解對(duì)應(yīng)解值比棧頂解解值大，則將該解壓入棧中，否則拋棄；若order要求求解最小值時(shí)，若當(dāng)前解對(duì)應(yīng)解值比棧頂解解值小，則將該解壓入棧中，否則拋棄；

Step 4.若軌道中所有解向量都被遍歷到，轉(zhuǎn)Step 5；否則轉(zhuǎn)回Step 2；

Step 5.輸出堆棧Solution；

算法在搜索域中隨機(jī)生成臨時(shí)棧底解，這一隨機(jī)過(guò)程使得有多種解堆棧的可能性，由于混沌軌道解值完全隨機(jī)排列，有很大可能在較早的搜索過(guò)程中就遇到較優(yōu)解，使得漸進(jìn)禁忌標(biāo)準(zhǔn)迅速逼近最優(yōu)解值，從而縮減解堆棧的高度；替換優(yōu)化過(guò)程則反復(fù)更替擬采用解，進(jìn)一步逼近全局最優(yōu)可能存在的域.通過(guò)解堆棧算法構(gòu)造的堆棧一般情況規(guī)模較小，能減少出棧時(shí)的計(jì)算量.

3.4 聚集出棧子算法

在子迭代前期的大搜索域中取得解堆棧后，如果直接使用棧頂元素作為下次縮放搜索中心，有較大可能性導(dǎo)致最終收斂到局部最優(yōu)解，尤其是類(lèi)似于如圖4所示SCHAFFER N.2函數(shù)微搜索域褶皺上的局部最優(yōu)解.

圖4 SCHAFFER N.2褶皺上的局部最優(yōu)

因此設(shè)計(jì)聚集出棧子算法，在一定程度上，控制搜索中心在搜索域縮減到不可逆之前向適應(yīng)度相近的其他鄰域的方向偏移，并在搜索軌道運(yùn)行到微搜索域時(shí)逐漸減少干涉，使落入局部最優(yōu)的機(jī)會(huì)偏小.設(shè)Pk為堆棧Solution中第k行解向量，P0為棧底解，Pn-1為棧頂暫定最優(yōu)解；將棧中元素依次出棧，并通過(guò)公式(10)-公式(13)計(jì)算出棧元素與已出棧元素的歐氏距離矩陣S：

(10)

(11)

(12)

(13)

即可判斷應(yīng)將哪些解納入用于搜索中心計(jì)算的聚集組.計(jì)算流程如下：

輸入：Solution；

輸出：Track；

Step 1.利用公式(10)-公式(13)通過(guò)輸入的Solution計(jì)算得到Sa序列；

Step 2.將Track暫時(shí)賦值為棧頂解向量；令k=1；

Step 4.當(dāng)k+2≠n-1時(shí)，重復(fù)Step 3；否則轉(zhuǎn)Step 5；

Step 5.輸出Track；

該子算法在子迭代前期發(fā)揮作用，搜索域逐漸收縮之后，由于此時(shí)的偏移調(diào)整量極小，幾乎可以忽略不計(jì)，故算法逐漸自動(dòng)退化，等效于取棧頂解，避免了大幅調(diào)整造成的發(fā)散解.

3.5 搜索域密度縮放與振蕩模塊

搜索域密度縮放主要針對(duì)子迭代的解空間，而振蕩模塊主要對(duì)主迭代解空間范圍更新.3.4中找出更適合作為縮放搜索中心的解向量Track后，若經(jīng)過(guò)載波控制器檢測(cè)尚未達(dá)到精度，則需要重新確定以Track為中心的搜索區(qū)域.劃定新區(qū)域時(shí)，需保證新區(qū)域不躍出初始搜索域造成解發(fā)散，并隨搜索域收縮控制混沌軌道長(zhǎng)度以減少低效計(jì)算量.

設(shè)算法當(dāng)前主迭代解優(yōu)化次數(shù)為epoch；Oup、Odown分別表示初始的up與down序列，Scope=Oup-Odown表示MLC算法初始時(shí)設(shè)定的搜索域中各個(gè)變量的取值尺度；store為最低保留軌道長(zhǎng)度；設(shè)置搜索域收縮速度為Speed.則對(duì)搜索域進(jìn)行變換后的搜索上下界計(jì)算公式如公式(14)、公式(15)所示，其中index表示第index個(gè)變量.

newup=Track[index]+Scope[index]·Speed(1+epoch)

(14)

newdown=Track[index]-Scope[index]·Speed(1+epoch)

(15)

搜索域與密度更新的算法如下：

輸入：Track；epoch；up；down；times；Scope；Oup；Odown；store；

Step 1.按照變量順序讀取下一個(gè)變量搜索域取值；

Step 2.若對(duì)于當(dāng)前變量取值范圍[up，down]，根據(jù)公式(14)-公式(15)計(jì)算newup、newdown.

Step 3.若[newup，newdown]沒(méi)有超出原始搜索范圍Scope=[Oup，Odown]，則取之作為新搜索域邊界；否則，將超出的一邊的初始邊界作為下次迭代的邊界；

Step 4.若所有變量的新邊界都已計(jì)算完畢，轉(zhuǎn)到Step 5；否則，轉(zhuǎn)回Step 1；

Step 5.計(jì)算新的軌道長(zhǎng)度times=「timesspeed+store?；

Speed、store參數(shù)根據(jù)不同問(wèn)題可以手動(dòng)調(diào)整.此處為研究方便起見(jiàn)取Speed=0.5，store=500.該算法使搜索域收縮的同時(shí)，混沌解規(guī)模也隨之縮減為原來(lái)的一半以節(jié)省算力和時(shí)間，且由性質(zhì)4可知混沌系統(tǒng)的特性不會(huì)在搜索域收縮后發(fā)生改變.

對(duì)主迭代中初始搜索域設(shè)置振蕩縮放過(guò)程，防止搜索域收縮過(guò)快使全局最優(yōu)在被發(fā)現(xiàn)前被排除，具體如下：

Step1.當(dāng)發(fā)現(xiàn)更優(yōu)解時(shí)，按照公式(14)、公式(15)更新每次子迭代初始的搜索域，轉(zhuǎn)Step 3；否則，轉(zhuǎn)Step 2；

Step2.產(chǎn)生一個(gè)隨機(jī)數(shù)，當(dāng)隨機(jī)數(shù)落在指定收縮概率區(qū)間時(shí)，按照公式(14)、公式(15)更新每次子迭代初始的搜索域；當(dāng)隨機(jī)數(shù)落入指定擴(kuò)張概率區(qū)間時(shí)，則將公式(14)、公式(15)中Speed的指數(shù)改為log2(1+epoch)后按新式子更新每次子迭代初始的搜索域使搜索域回彈.轉(zhuǎn)Step 3；當(dāng)隨機(jī)數(shù)落入兩區(qū)間之外，則直接轉(zhuǎn)Step 3；

Step3. 將超出邊界的上下限移動(dòng)到初始邊界，主迭代結(jié)束，進(jìn)入停機(jī)判斷.

如此模擬出低頻的搜索域振蕩效果，增加全局最優(yōu)解的發(fā)現(xiàn)可能，同時(shí)也保持搜索空間的對(duì)數(shù)型持續(xù)收縮.

3.6 載波控制器

載波控制器主要任務(wù)為監(jiān)測(cè)每次子迭代構(gòu)建的解堆棧求得的解值是否達(dá)到精度要求并控制重載波.故在每次子迭代末期，停機(jī)控制器需要對(duì)本次求解得到的解和解值做好記錄，以備下次監(jiān)測(cè)使用.評(píng)估辦法基于解值的差分：

ΔF*=F[(Trackk)-F(Trackk-1)]2

(16)

當(dāng)檢測(cè)到ΔF*小于或等于要求的精度值(一般取10-w，w為正整數(shù))，則終止載波和子迭代過(guò)程，根據(jù)解的優(yōu)化情況更新搜索域后，進(jìn)入停機(jī)控制器；否則，運(yùn)行搜索域密度收縮子算法，并向混沌擾動(dòng)模塊輸入重載波參數(shù)，給予微小擾動(dòng)后開(kāi)始新的子迭代.

3.7 停機(jī)控制器與混沌擾動(dòng)模塊

停機(jī)控制器用于在達(dá)到最大迭代次數(shù)時(shí)終止算法.由于混沌優(yōu)化算法每次迭代結(jié)果都具有隨機(jī)性，沒(méi)有有效的解監(jiān)測(cè)辦法，故只能用最大迭代次數(shù)作為控制因素.

混沌擾動(dòng)模塊通過(guò)在混沌系統(tǒng)控制參量上施加10-4的擾動(dòng)實(shí)現(xiàn)對(duì)混沌軌道的擾動(dòng)，即加減一個(gè)10-4級(jí)的隨機(jī)數(shù)即可.

4 實(shí)驗(yàn)分析

4.1 求解性能對(duì)比測(cè)試

為了驗(yàn)明3中設(shè)計(jì)的MLC算法是否具有更好的全局最優(yōu)求解能力，使用了單目標(biāo)優(yōu)化常用的測(cè)試函數(shù)SCHAFFER函數(shù)式(17)和“大海撈針”函數(shù)式(18)進(jìn)行算法測(cè)試.兩個(gè)函數(shù)在定義域內(nèi)的圖像如圖5所示，兩個(gè)函數(shù)都具有被局部最優(yōu)解包圍全局最優(yōu)解、且全局最優(yōu)解值與局部最優(yōu)解值差異較小的特點(diǎn).

圖5 SCHAFFER函數(shù)(上)和“大海撈針”函數(shù)(下)

(17)

(18)

其中，SCHAFFER函數(shù)全局最優(yōu)解為(0，0)，對(duì)應(yīng)函數(shù)值為1，圓環(huán)上的局部最優(yōu)為0.9903，外部的4個(gè)局部最優(yōu)解為0.6468.

實(shí)驗(yàn)表明使用Lingo軟件求解SCHAFFER所得解值為0.6468488，而使用Matlab可解出解值為0.9903；使用原Logistic混沌優(yōu)化算法需經(jīng)過(guò)1092次迭代才能得到全局最優(yōu)解[18]，而使用混沌遺傳算法則需迭代458次.“大海撈針”函數(shù)全局最優(yōu)解為(0，0)，對(duì)應(yīng)最優(yōu)解值為3600，4個(gè)角上分別存在4個(gè)局部最優(yōu)解，對(duì)應(yīng)解值都為2748.78；Lingo和Matlab運(yùn)算出現(xiàn)局部最優(yōu)概率高達(dá)95%，遺傳算法也需迭代300代才有60%可能找到最優(yōu)解.

設(shè)置MLC算法初始參數(shù)：目標(biāo)下降精度0.0001，收縮速度0.5，產(chǎn)生混沌軌道長(zhǎng)定義為500，最大迭代次數(shù)為50次；設(shè)振蕩收縮概率區(qū)間為[0.075，0.01]，擴(kuò)張概率區(qū)間為[0，0.075].分別對(duì)兩個(gè)待優(yōu)化函數(shù)運(yùn)行10次MLC算法.結(jié)果對(duì)于兩個(gè)問(wèn)題的求解都在3次迭代以內(nèi)找出都找到了全局最優(yōu)解，且二者分別進(jìn)行的10次實(shí)驗(yàn)中都有9次都收斂到全局最優(yōu)解，可粗略認(rèn)為有接近90%的概率一次計(jì)算得到全局最優(yōu).

4.2 中等復(fù)雜問(wèn)題求解能力綜合測(cè)試

為進(jìn)一步測(cè)試MLC算法是否有能力對(duì)中等復(fù)雜單目標(biāo)函數(shù)進(jìn)行最優(yōu)化求解，選擇了Ackley函數(shù)和Griewank函數(shù)作為測(cè)試用例，兩個(gè)函數(shù)基本式如公式(19)、公式(20)所示.其中，Ackley函數(shù)二維形態(tài)如圖6所示；Griewank二維形態(tài)從[-1000，1000]到[-5，5]區(qū)間縮放效果如圖7所示，可知Ackley具有頂峰局部最優(yōu)特性；而Griewank函數(shù)同時(shí)具有微搜索域褶皺豐富、局部最優(yōu)與全局最優(yōu)解值差異極端微弱的特性，搜索域較大時(shí)，只能大致判別出最優(yōu)解在0點(diǎn)附近，但當(dāng)搜索域縮減后，函數(shù)圖像上出現(xiàn)大量褶皺，且波峰波谷差距極其微小.這類(lèi)特性使得二維情況的求解都已經(jīng)非常困難.分別構(gòu)造10維Ackley函數(shù)和10維Griewank函數(shù)，設(shè)公式(19)中的d為10，a為20，b為0.2，設(shè)公式(20)中的d為10；分別設(shè)定Ackley函數(shù)變量取值范圍為[-50，50]，Griewank函數(shù)取值范圍為[-1000，1000].此處10維Ackley函數(shù)的解空間規(guī)模為10010；而10維Griewank函數(shù)的解空間規(guī)模為200010.已知兩函數(shù)最優(yōu)解都為[0，0，0，0，0，0，0，0，0，0]，對(duì)應(yīng)解值0.

圖6 2D Ackley函數(shù)

圖7 2D Griewank函數(shù)

+a+exp(1)，xi∈[-50，50]

(19)

(20)

使用原Logistic混沌優(yōu)化算法迭代1000次，實(shí)驗(yàn)10次，其中有2次分別在632次迭代和944次迭代求得Ackley函數(shù)全局最優(yōu)解；但始終沒(méi)有找出Griwank函數(shù)全局最優(yōu)解.使用遺傳算法、螞蟻算法測(cè)試，都始終無(wú)法求出10維Griwank函數(shù)的全局最優(yōu)解.

調(diào)整MLC算法參數(shù)，設(shè)置最大迭代500次，混沌軌道長(zhǎng)度為5000，其余參數(shù)不變，分別對(duì)兩個(gè)函數(shù)運(yùn)行算法15次.

對(duì)于Ackley函數(shù)，15次實(shí)驗(yàn)都在第1次迭代中就找到全局最優(yōu)解.對(duì)于Griewank函數(shù)，15次測(cè)試的結(jié)果如表3所示，除了6號(hào)實(shí)驗(yàn)外，其余所有實(shí)驗(yàn)都在300次迭代內(nèi)找到全局最優(yōu)解，且解值精度達(dá)到99.9999%.其中有7次都在100次迭代內(nèi)找出全局最優(yōu)解.兩輪測(cè)試都能夠在較500次迭代內(nèi)有效找到全局最優(yōu)解，證明MLC算法對(duì)于中等連續(xù)復(fù)雜單目標(biāo)函數(shù)據(jù)具有較好的極值求解能力.

表3 10維Griewank函數(shù)±1000范圍內(nèi)最小化求解結(jié)果

5 總 結(jié)

針對(duì)常用的遺傳算法、蟻群算法一類(lèi)復(fù)雜連續(xù)函數(shù)求解方法存在的難以跳出局部最優(yōu)、收斂時(shí)間過(guò)長(zhǎng)等問(wèn)題，以及基于Logistic混沌系統(tǒng)設(shè)計(jì)的優(yōu)化算法存在的邊緣過(guò)度搜索缺陷，改進(jìn)Lorenz混沌映射系統(tǒng)設(shè)計(jì)了一套新的混沌映射系統(tǒng)模型，并基于該模型設(shè)計(jì)了分片Lorenz混沌堆棧聚集變密度振蕩搜索算法(簡(jiǎn)稱MLC算法).通過(guò)系統(tǒng)仿真分布統(tǒng)計(jì)實(shí)驗(yàn)和多輪求解能力測(cè)試，達(dá)成了以下目標(biāo)：

1)驗(yàn)證了改進(jìn)后的混沌模型具有優(yōu)于Logistic系列混沌的分布均勻度與隨機(jī)性，更適合作為改進(jìn)混沌優(yōu)化算法的搜索軌道發(fā)生核心；

2)相對(duì)經(jīng)典優(yōu)化算法，新算法在解決單目標(biāo)復(fù)雜連續(xù)函數(shù)極值問(wèn)題方面具備速度快、性能穩(wěn)定、局部跳出能力強(qiáng)等優(yōu)勢(shì)，能夠以較高且穩(wěn)定的概率直接找出簡(jiǎn)單函數(shù)全局最優(yōu)解，綜合性能優(yōu)于對(duì)比組的各項(xiàng)經(jīng)典算法和現(xiàn)有軟件.

利用MLC算法的優(yōu)勢(shì)，可以考慮其應(yīng)用于工程優(yōu)化領(lǐng)域，例如計(jì)算化工領(lǐng)域復(fù)雜化學(xué)反應(yīng)有效產(chǎn)出最大化或廢料最小化的原料配置問(wèn)題；或者用于解決非線性復(fù)雜管理科學(xué)工程問(wèn)題，例如對(duì)復(fù)雜博弈投資組合問(wèn)題計(jì)算投資產(chǎn)出最優(yōu)方案等；在生物運(yùn)動(dòng)信號(hào)處理方面，對(duì)該算法進(jìn)行改進(jìn)還可以用于九軸運(yùn)動(dòng)傳感器校準(zhǔn).

由于MLC算法框架針對(duì)復(fù)雜連續(xù)函數(shù)優(yōu)化的特異性，該算法尚不可直接用于解決組合優(yōu)化問(wèn)題.此外，算法的收斂策略缺乏非線性過(guò)程，這使得算法搜索不均衡；解空間的收縮則使算法放棄了邊界外的區(qū)域.上述不足之處有待后續(xù)研究.