基于Kent映射的混合混沌優(yōu)化算法

劉建軍，石定元，武國寧

（1.中國石油大學(xué) 理學(xué)院，北京102249；2.北京航空航天大學(xué) 電子信息工程學(xué)院，北京100191）

0 引 言

基本的混沌優(yōu)化算法 （COA）［1－7］在搜索末期易陷入局部且收斂慢，因此，各種混合及改進混沌優(yōu)化算法相繼被提出，將混沌優(yōu)化算法與梯度類算法結(jié)合［8，9］，改進混沌優(yōu)化算法中初始變量的選?。?0］等相結(jié)合后的混合算法均獲得一些良好的效果。以上各種改進或混合算法仍存在不足之處，如基于梯度類混合算法要求目標(biāo)函數(shù)可微等。為使算法中變量的分布具有更好遍歷性、算法收斂快及得到高精度的全局最優(yōu)解，本文在變尺度混沌優(yōu)化算法的基礎(chǔ)上，提出一種改進的混合混沌優(yōu)化算法。改進算法既引入了遍歷性更好的Kent映射來生成初始變量，又引入了穩(wěn)定變化的尺度因子，在算法末期加入Nelder－Mead單純形搜索策略，提高算法的收斂速度和解的精度。通過對一些典型測試函數(shù)進行數(shù)值比較實驗，驗證了改進算法的高效性。

1 Logistic映射與Kent映射的分布特征

現(xiàn)有的混沌優(yōu)化算法及改進均采用Logistic映射生成新變量 （解），但Logistic映射的遍歷性并不是最好的，從數(shù)學(xué)上講，Kent映射與Logistic映射是同構(gòu)的［11］，因此Kent映射也可用于隨機優(yōu)化算法中生成隨機新解的方法，而Kent映射具有比Logistic映射更好的均勻遍歷性，其迭代過程同樣適合程序化運行。我們可以通過統(tǒng)計的方法說明Kent映射比Logistic映射好的遍歷性。

由Logistic映射生成的混沌序列服從切比雪夫型分布，其概率密度函數(shù)具有邊緣稠密、內(nèi)部稀疏的特點，不利于搜索的效率和能力。Logistic映射的系統(tǒng)方程為

式中：μ——控制參數(shù)，取值范圍為0＜μ ≤4。當(dāng)μ ＝4時，該映射對應(yīng)一種滿映射混沌狀態(tài)，此時的Lyapunov指數(shù)約等于0.691。在區(qū)間（0，1）內(nèi)的概率密度函數(shù)為

Kent映射是另一個具有代表性且形式簡單的離散混沌系統(tǒng)，其系統(tǒng)方程可表為如下形式

其中控制參數(shù)a∈（0，1），當(dāng)a＝0.4時，其概率密度函數(shù)在（0，1）內(nèi)服從均勻分布，即

此時，它的Lyapunov 指數(shù)約為0.696，大于經(jīng)典的Logistic映射的0.691。而Lyapunov指數(shù)可以用來刻畫初始狀態(tài)微小不確定性的發(fā)散比率，因此，Kent映射比Logistic映射具有更好的遍歷性。圖1 是將Kent映射與Logistic映射各迭代20 000次得到的 ［0，1］上的概率分布直方圖。圖中顯示Logistic 映射在區(qū)間 ［0，0.0125］和［0.9875，1］上取值概率較高。而Kent映射在各區(qū)間分布相對較均勻。

圖1 Kent映射和Logistic映射的概率分布直方圖

2 Nelder－Mead單純形法

Nelder－Mead單純形法是求解無約束優(yōu)化的一種直接方法，由于它不需要目標(biāo)函數(shù)的梯度信息，因此被廣泛應(yīng)用于不可微的連續(xù)函數(shù)優(yōu)化及諸多啟發(fā)式算法中［12］。單純形法是在給定Rn中一個單純形后，先計算出n＋1個頂點上的函數(shù)值，再找出最大函數(shù)值的點 （稱為最高點）和最小函數(shù)值的點 （稱為最低點），然后經(jīng)過反射、擴展、壓縮等過程，確定出一個較好點，最后用它取代最高點來構(gòu)成新的單純形，也可以通過向最低點收縮，形成新的單純形。單純形法即是通過構(gòu)造一系列的單純形來逼近極小點。

針對一般的無約束優(yōu)化問題

下面給出Nelder－Mead單純形法算法的步驟框架。

（1）構(gòu)造初始單純形。任意選取n＋1個不同的點并計算其函數(shù)值。通過比較這些值的大小，確定最高 （壞）點xh，最低 （好）點xl，次低 （壞）點xg，并且yh＝

（2）計算除xh以外的n 個點的中心點xc，即xc＝求出反射點xr＝xc＋α（xc－xh），其中α為反射系數(shù)，一般取值為1。計算函數(shù)值yr＝f（xr）；

（3）若yr≥yh，則進行壓縮，并令壓縮點xs＝xh＋λ（xr－xh）其中0＜λ＜1稱為壓縮因子；若ys≤yl，令xl＝xs，否則進行擴張，令擴張點xe＝xh＋μ（xr－xh）其中，μ＞1稱為擴張因子。一般取1.2＜μ＜2。若ye≤yr，令xs＝xe，否則xs＝xr；

（4）若ys≤yg，則令xh＝xs。以新的xh與其它的n個點一起構(gòu)成新的單純形，重新確定xh，xl和xg，并重復(fù)前述步驟 （2）。否則進行下一步；

（5）單純形向點xl收縮，令xi＝，i＝1，2，…，n。然后轉(zhuǎn)向（1）。重復(fù)上述過程，直到滿足停止條件｜yhyl｜≤ε，其中ε為預(yù)先給定的精度。

單純形算法具有計算量小、收斂速度快且對優(yōu)化函數(shù)要求低 （不要求可微）的特點，因此被應(yīng)用于很多不可微函數(shù)優(yōu)化問題中。單純形法的不足之處是過分依賴于初始解的位置，容易陷于局部，很難搜索到全局最優(yōu)解。因此，將單純形法與混沌優(yōu)化算法相結(jié)合，可以提高混沌優(yōu)化算法的收斂速度和最優(yōu)解的精度。

3 基于Kent映射的混合混沌優(yōu)化算法

應(yīng)用Kent映射、變尺度因子和單純形算法，構(gòu)造一種混合混沌優(yōu)化算法 （KSCOA）。算法分為兩個階段，即粗搜索階段和細搜索階段。在粗搜索階段使用Kent映射，以提高算法遍歷搜索空間的能力。而細搜索階段結(jié)合了變尺度方法和單純形算法的優(yōu)勢，此階段又分為前期和后期，即細搜索的前期利用變尺度方法的大區(qū)間上的尋優(yōu)能力將最優(yōu)解的搜索范圍最終確定在一個小的區(qū)間上，然后在細搜索的后期利用單純形算法的局部尋優(yōu)能力以搜索到一個精度較高的最優(yōu)解。本文的這種混合策略不但可以保證解的全局最優(yōu)性，同時相較于傳統(tǒng)的變尺度混沌方法具有更快的收斂速度和獲得更高精度解的能力。

本文算法的步驟如下：

步驟1 初始化各項參數(shù)。

令flag1控制粗混沌迭代搜索進程，flag2控制細搜索前期的進程，flag3控制細搜索后期的進程。ε1和ε2分別表示細搜索的前期和后期的精度，fmin用于存儲更新的函數(shù)極小值。初始混沌變量設(shè)為個m 具有微小差異的初值ci，i＝1，2，...，m。

步驟2 將混沌變量ci按式 （6）映射到函數(shù)優(yōu)化變量的分量取值區(qū)間［ai，bi］

步驟3 粗搜索。開始混沌迭代搜索。

如果f（xi）＜fmin，則fmin＝f（xi），＝xi，否則利用Kent映射生成新混沌變量，即ci＝kent（ci），flag1：＝flag1＋1。轉(zhuǎn)步驟2，如果flag1＞flag1max，轉(zhuǎn)步驟4。

步驟4 細搜索。

（1）用變尺度法搜索。

如果｜br＋1i－｜≤ε1，轉(zhuǎn)入 （2），否則，按式 （8）將當(dāng)前解變換到［0，1］區(qū)間

（2）用Nelder－Mead單純形算法搜索。

令x0＝為單純形搜索初始點構(gòu)造初始單純形S0＝［V0，V1，…，Vn］，按第2 節(jié)方法進行反射、延伸、收縮搜索，得 Si＝ ［，…］。 令若，則x＊＝V ，fmin＝f（x＊）。轉(zhuǎn)步驟5。

步驟5 輸出最小值fmin，最優(yōu)解x＊，算法終止。

在步驟4 （1）中，變尺度因子γ按式 （9）的選取，圖2顯示了變尺度參數(shù) （因子）與細搜索次數(shù)的變化曲線，這種變化既保證算法前期收斂平緩又能使得γ在后期趨于一個較小的值從而使算法能夠較快收斂

同時，算法在運行過程中，為保證區(qū)間縮小，必須要進行越界處理：若＜，則＝；若＞，則＝。

圖2 變尺度參數(shù)變化曲線

4 算法性能測試與分析

為測試改進算法KSCOA 的運算性能，這里選用6 個常用于驗證算法性能的典型測試函數(shù)進行實驗，其中只有第6個函數(shù)Schaffer函數(shù)為2維，其它均為任意有限維。表1列出了6個測試函數(shù)的表達式、多或單峰性、取值區(qū)間及最優(yōu)性情況。下面把本文改進算法與混沌優(yōu)化算法的3個變種，即粗搜索階段使用Logistic映射的傳統(tǒng)變尺度混沌優(yōu)化方法 （LCOA）、粗搜索階段使用Kent映射的傳統(tǒng)變尺度混沌優(yōu)化方法 （KCOA）、粗搜索階段用Logistic映射細搜索階段用單純形變尺度相結(jié)合方法 （LSCOA）的計算結(jié)果進行比較。

本文所用軟件壞境為：Win7 （X64），Matlab 7.7，計算機硬件配置為：奔騰雙核T3200主頻2GHZ，內(nèi)存2G。選取20個初始混沌變量c0（i）＝0.045i，i＝1，2，…，20，迭代次數(shù)設(shè)為1000。各算法均獨立運行50次。

表2給出了測試函數(shù)選取2維時，比較Logistic映射和Kent映射構(gòu)造的COA 算法的平均計算時間與函數(shù)平均值的比較結(jié)果。

從表2比較分析出，Kent映射雖然在時間復(fù)雜度上稍遜于Logistic映射，但前者所得的平均值明顯優(yōu)于后者，這是由于Logistic映射的遍歷均勻性較差，概率密度函數(shù)決定絕大部分搜索點都分布在邊界區(qū)域，如果全局最優(yōu)解不在區(qū)間邊界附近，則該映射的全局搜索效率將大為降低。而Kent映射對應(yīng)的搜索點在搜索區(qū)間內(nèi)分布較均勻，因此用Kent映射取代Logistic映射確實能提升算法的全局尋優(yōu)能力。

Sphere函數(shù)是單峰函數(shù)，用它可以驗證算法的收斂性，而Griewank函數(shù)是多峰函數(shù)的典型，用它可以驗證算法的全局收斂性。因此，圖3只繪出了4種算法針對Sphere函數(shù)與Griewank函數(shù) （5維）在某次迭代過程中的收斂曲線。圖3 （a）顯示了對于單極值的連續(xù)函數(shù)，搜索末期使用單純形算法相較繼續(xù)使用變尺度方法來說明顯加快了收斂。圖3 （b）顯示了對于多極值問題，本文方法仍具有收斂較快的優(yōu)勢。特別是對高維函數(shù)，變尺度混沌優(yōu)化算法很難得到高精度解，但是只要加入單純形法參與運行，則解的精度便會得到極大提高。

表1 測試函數(shù)

表2 Logistic與Kent的映射在粗搜索過程中的比較

圖3 4種算法對Sphere和Griewank函數(shù)的收斂曲線對比

表3 4種優(yōu)化方法的數(shù)值運算結(jié)果比較

5 結(jié)束語

本文在變尺度混沌優(yōu)化算法的基礎(chǔ)上，構(gòu)造了一種混合混沌優(yōu)化算法。該算法主要有3個方面改進：①為了改善原算法的全局收斂性，本文用比傳統(tǒng)的Logistic映射具有更好遍歷性的Kent映射來生成隨機的初始變量；②為避免算法早熟，引入了非線性的尺度變化因子；③為保證算法在運行末期取得更高精度的解，采用單純形法進行搜索。數(shù)值實驗結(jié)果表明，在混沌優(yōu)化算法的粗搜索階段，Kent映射的均勻遍歷性提高了搜索到好解的可能性。而在細搜索法后期，改用單純形法后比繼續(xù)用變尺度的方法具有收斂快精度高的優(yōu)點。總之，本文將Kent映射、單純形方法及變尺度方法結(jié)合后得到的改良的混沌優(yōu)化算法具備較高的速率和精度，是一種混沌算法的較好的改進，期望在實際應(yīng)用中會有更好的效果。

［1］Yang D，Li G，Cheng G.On the efficiency of chaos optimization algorithms for global optimization ［J］.Chaos，Solitons ＆Fractals，2007，34 （4）：1366－1375.

［2］Tavazoei，Mohammad Saleh，Mohammad Haeri.An optimization algorithm based on chaotic behaviour and fractal nature［J］.Journal of Computational and Applied Mathematics，2007，206 （2）：1070－1081.

［3］Yuan XF，Li ST，Wang YN，et al.Parameter identification of electronic throttle using a hybrid optimization algorithm ［J］.Nonlinear Dyn，2011，63 （4）：549－557.

［4］Dos Santos Coelho L.Tuning of PID controller for an automatic regulator voltage system using chaotic optimization approach［J］.Chaos，Solitons ＆Fractals，2009，39 （4）：1504－1514.

［5］Khoa T Q D，Nakagawa M.Training multilayer neural network by global chaos optimization algorithms［C］//International Joint Conference on Neural Networks.IEEE，2007：136－141.

［6］YANG Lingling，MA Liang，ZHANG Huizhen.Chaotic optimization algorithm for multi－objective 0－1programming problem［J］.Application Research of Computers，2012，29 （12）：84－87（in Chinese）.［楊玲玲，馬良，張惠珍.多目標(biāo)0－1規(guī)劃的混沌優(yōu)化算法［J］.計算機應(yīng)用研究，2012，29 （12）：84－87.］

［7］Ikeguchi T，Hasegawa M，Kimura T，et al.Theory and applications of chaotic optimization methods ［M］.Innovative Computing Methods and Their Applications to Engineering Problems.Springer Berlin Heidelberg，2011：131－161.

［8］Luo Y Z，Tang G J，Zhou L N.Hybrid approach for solving systems of nonlinear equations using chaos optimization and quasi－Newton method［J］.Applied Soft Computing，2008，8（2）：1068－1073.

［9］Yang D，Liu Z，Zhou J.Chaos optimization algorithms based on chaotic maps with different probability distribution and search speed for global optimization ［J］.Communications in Nonlinear Science and Numerical Simulation，2014，19 （4）：1229－1246.

［10］SU Youliang，ZHOU Dejian.Performance analysis of chaos immune evolutionary algorithm with different maps ［J］.Computer Engineering，2010，36 （21）：222－224 （in Chinese）.［蘇有良，周德儉.不同映射的混沌免疫進化算法性能分析 ［J］.計算機工程，2010，36 （21）：222－224.］

［11］Tavazoei M S，Haeri M.Comparison of different one－dimen－sional maps as chaotic search pattern in chaos optimization algorithms［J］.Applied Mathematics and Computation，2007，187 （2）：1076－1085.

［12］Wang L，Xu Y，Li L.Parameter identification of chaotic systems by hybrid Nelder– mead simplex search and differential evolution algorithm ［J］.Expert Systems with Applications，2011，38 （4）：3238－3245.