基于Kent映射的混合混沌優化算法

劉建軍，石定元，武國寧

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

0 引 言

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

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

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

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

式中：μ——控制參數，取值范圍為0＜μ ≤4。當μ ＝4時，該映射對應一種滿映射混沌狀態，此時的Lyapunov指數約等于0.691。在區間（0，1）內的概率密度函數為

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

其中控制參數a∈（0，1），當a＝0.4時，其概率密度函數在（0，1）內服從均勻分布，即

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

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

2 Nelder－Mead單純形法

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

針對一般的無約束優化問題

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

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

（2）計算除xh以外的n 個點的中心點xc，即xc＝求出反射點xr＝xc＋α（xc－xh），其中α為反射系數，一般取值為1。計算函數值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個點一起構成新的單純形，重新確定xh，xl和xg，并重復前述步驟 （2）。否則進行下一步；

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

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

3 基于Kent映射的混合混沌優化算法

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

本文算法的步驟如下：

步驟1 初始化各項參數。

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

步驟2 將混沌變量ci按式 （6）映射到函數優化變量的分量取值區間［ai，bi］

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

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

步驟4 細搜索。

（1）用變尺度法搜索。

如果｜br＋1i－｜≤ε1，轉入 （2），否則，按式 （8）將當前解變換到［0，1］區間

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

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

步驟5 輸出最小值fmin，最優解x＊，算法終止。

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

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

圖2 變尺度參數變化曲線

4 算法性能測試與分析

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

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

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

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

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

表1 測試函數

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

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

表3 4種優化方法的數值運算結果比較

5 結束語

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

［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）.［楊玲玲，馬良，張惠珍.多目標0－1規劃的混沌優化算法［J］.計算機應用研究，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.