劉建軍，石定元，武國(guó)寧

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

0 引 言

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

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

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

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

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

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

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

此時(shí)，它的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ū)間分布相對(duì)較均勻。

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

2 Nelder－Mead單純形法

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

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

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

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

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

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

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

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

單純形算法具有計(jì)算量小、收斂速度快且對(duì)優(yōu)化函數(shù)要求低 （不要求可微）的特點(diǎn)，因此被應(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）。算法分為兩個(gè)階段，即粗搜索階段和細(xì)搜索階段。在粗搜索階段使用Kent映射，以提高算法遍歷搜索空間的能力。而細(xì)搜索階段結(jié)合了變尺度方法和單純形算法的優(yōu)勢(shì)，此階段又分為前期和后期，即細(xì)搜索的前期利用變尺度方法的大區(qū)間上的尋優(yōu)能力將最優(yōu)解的搜索范圍最終確定在一個(gè)小的區(qū)間上，然后在細(xì)搜索的后期利用單純形算法的局部尋優(yōu)能力以搜索到一個(gè)精度較高的最優(yōu)解。本文的這種混合策略不但可以保證解的全局最優(yōu)性，同時(shí)相較于傳統(tǒng)的變尺度混沌方法具有更快的收斂速度和獲得更高精度解的能力。

本文算法的步驟如下：

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

令flag1控制粗混沌迭代搜索進(jìn)程，flag2控制細(xì)搜索前期的進(jìn)程，flag3控制細(xì)搜索后期的進(jìn)程。ε1和ε2分別表示細(xì)搜索的前期和后期的精度，fmin用于存儲(chǔ)更新的函數(shù)極小值。初始混沌變量設(shè)為個(gè)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 細(xì)搜索。

（1）用變尺度法搜索。

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

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

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

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

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

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

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

4 算法性能測(cè)試與分析

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

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

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

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

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

表1 測(cè)試函數(shù)

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

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

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

5 結(jié)束語

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

［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］.計(jì)算機(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ìn)化算法性能分析 ［J］.計(jì)算機(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.