非線性最優(yōu)化問題的一種混合解法

1、非線性最優(yōu)化問題的一種混合解法     摘 要：把BFGS方法與混沌優(yōu)化方法相結合，基于混沌變量提出一種求解具有變量邊界約束非線性最優(yōu)化問題的混合優(yōu)化方法。混合算法兼顧了混沌優(yōu)化全局搜索能力強和BFGS方法收斂速度快的優(yōu)點，成為一種求解非凸優(yōu)化問題全局最優(yōu)的有效方法。算例表明，當混沌搜索的次數(shù)達到一定數(shù)量時，混合優(yōu)化方法可以保證算法收斂到全局最優(yōu)解，且計算效率比混沌優(yōu)化方法有很大提高。    關鍵詞：混合法；BFGS方法；混沌優(yōu)化方法；全局最優(yōu)    1 引言  &

2、#160;   在系統(tǒng)工程、控制工程、統(tǒng)計學、反問題優(yōu)化求解等領域中，很多問題是具有非凸性的。對此普通的優(yōu)化技術只能求出局部最優(yōu)解，因為這些確定性算法總是解得最近的一個極值點1，只有能夠給出很好的初始點才有可能得出所需要的全局最優(yōu)解。為此，實際應用中通過在多個初始點上使用傳統(tǒng)數(shù)值優(yōu)化方法來求取全局解的方法仍然被人們所采用，但是這種處理方法求得全局解的概率不高，可靠性低，建立盡可能大概率的求解全局解算法仍然是一個重要問題。近年來基于梯度法的全局最優(yōu)化方法已經(jīng)有所研究2，基于隨機搜索技術的遺傳算法和模擬退火算法等在全局優(yōu)化問題中的應用也得到越來越大的重視3-4。本文則基于混沌優(yōu)

3、化和BFGS方法，提出一種求解具有簡單界約束最優(yōu)化問題(1)的混合算法。 min (1)     混沌是存在于非線性系統(tǒng)中的一種較為普遍的現(xiàn)象?；煦邕\動宏觀上無序無律，具有內隨機性、非周期性和局部不穩(wěn)定性，微觀上有序有律，并不是完全的隨機運動，具有無窮嵌套的自相似幾何結構、存在普適性規(guī)律，并不是雜亂無章的。利用混沌變量的隨機性、遍歷性和規(guī)律性特點可以進行優(yōu)化搜索5，且混沌優(yōu)化方法容易跳出局部最優(yōu)點。但是某些狀態(tài)需要很長時間才能達到，如果最優(yōu)值在這些狀態(tài)時，計算時間勢必很長5?？梢哉f混沌優(yōu)化具有全局搜索能力，其局部搜索能力稍顯不足，文5采用二次載波技術，文

4、6考慮逐漸縮小尋優(yōu)變量的搜索空間都是為了彌補這一弱點。而本文則采用混沌搜索與BFGS方法進行優(yōu)化求解，一方面采用混沌搜索幫助BFGS方法跳出局部最優(yōu)，另一方面利用BFGS增強解附近的超線性收斂速度和搜索能力，以提高搜索最優(yōu)的效率。     2 混沌BFGS混合優(yōu)化方法     2.1 BFGS方法     作為求解無約束最優(yōu)化問題的擬牛頓方法類最有代表性的算法之一，BFGS方法處理凸非線性規(guī)劃問題，以其完善的數(shù)學理論基礎、采用不精確線性搜索時的超線性收斂性和處理實際問題有效性

5、，受到人們的重視7-9。擬牛頓方法使用了二階導數(shù)信息，但是并不直接計算函數(shù)的Hesse矩陣，而是采用一階梯度信息 來構造一系列的正定矩陣 來逼近Hesse矩陣 。BFGS方法求解無約束優(yōu)化問題min ( )的主要步驟如下：     (1) 給變量賦初值x0，變量維數(shù)n和BFGS方法收斂精度，令B0=I（單位陣），k=0，計算 在點x0的梯度g0。     (2) 取sk=-Bk-1gk，沿sk作一維搜索，確定最優(yōu)步長k， ，得新點xk+1=xk+ksk，計算xk+1點的梯度gk+1。  

6、0;  (3) 若|gk+1|，則令 ， ，BFGS搜索結束，轉步驟3；否則執(zhí)行(4)。      (4) 計算Bk+1：      (2)      (3)      (5) k=k+1，轉(2)。     2.2 混沌優(yōu)化方法     利用混沌搜索求解問題(1)時，先建立待求變量 與混沌變量 的一一對應關系，本文采用 。然后,由Logistic

7、映射式(4)產(chǎn)生 個軌跡不同的混沌變量 （ ）進行優(yōu)化搜索，式(4)中 =4。已經(jīng)證明， =4是“單片”混沌， 在0,1之間歷遍。      (4)     (1)給定最大混沌變量運動次數(shù)M；給 賦初值 ，計算 和 ；置 ， 。     (2) 。     (3) 。     (4) 若k<M，     若 ，令 ， ；  

8、0;  若 ， 和 保持不變；     然后令k=k+1， ，轉(2)。     若k>M，則 ， ，混沌搜索結束。    2.3 混合優(yōu)化方法     混沌方法和BFGS方法混合求解連續(xù)對象的全局極小值優(yōu)化問題(1)的步驟如下：     step1 設置混沌搜索的最大次數(shù)M，迭代步數(shù)iter=0，變量賦初值x0， 。    step2 以

9、為始點BFGS搜索，得當前BFGS方法最優(yōu)解 及 = 。    step3 若 ，取 = ；若 ，取 ；若 ，取 ， 是相對于 , 較小的數(shù)。    step 4 以 為始點進行混沌搜索M次，得混沌搜索后的最優(yōu)解 及 = 。    step5 若 < ，iter=iter+1， ，轉step2；否則執(zhí)行step6。    step6 改變混沌搜索軌跡，再次進行混沌搜索，即給 加微小擾動 ，執(zhí)行step 4，得搜索結果 和 。若 &

10、lt; ，iter=iter+1， ，轉step2；否則計算結束，輸出 、 。    對全局極大值問題，max ，可以轉化為求解全局極小問題min 。    混合算法中混沌搜索的作用是大范圍宏觀搜索，使得算法具有全局尋優(yōu)性能。而BFGS搜索的作用是局部地、細致地進行優(yōu)化搜索，處理的是小范圍搜索問題和搜索加速問題。    3 算例              圖

11、 1 函數(shù)- 特性示意圖 圖 2 函數(shù) 特性示意圖     采用如下兩個非常復雜的、常用于測試遺傳算法性能的函數(shù)測試本文算法：              函數(shù) 稱為Camel 函數(shù)，該函數(shù)有6個局部極小點(1.607105, 0.568651)、(-1.607105, -0.568651)、(1.703607, -0.796084)、(-1.703607, 0.796084)、(-0.0898,0.7126)和(0.0898,-0.71

12、26)，其中(-0.0898,0.7126)和(0.0898,-0.7126)為兩個全局最小點，最小值為-1.031628。函數(shù) 稱為 Schaffer's函數(shù)，該函數(shù)有無數(shù)個極大值，其中只有（0，0）為全局最大點，最大值為1。此函數(shù)的最大峰值周圍有一圈脊，它們的取值均為0.990283，因此很容易停留在此局部極大點。文獻10采用該函數(shù)對該文提出的基于移動和人工選擇的改進遺傳算法（GAMAS）其性能進行了考察，運行50次，40的情況下該函數(shù)的唯一全局最優(yōu)點能夠找到。而采用本文混合算法，由計算機內部隨機函數(shù)自動隨機生產(chǎn)100個不同的初始點，由這些初始點出發(fā)，一般混合算法迭代24次即能夠收

13、斂。M取不同數(shù)值時對函數(shù) 、 的計算結果分別如表1和表2所示，表中計算時間是指在奔騰133微機上計算時間。     由表2可見，當M=1500時，本文方法搜索到 最優(yōu)解的概率即達到40，而此時計算量比文獻10小。同樣由混合算法的100個起始點，采用文獻5的算法對函數(shù) 優(yōu)化計算100次，以 作為收斂標準，混沌搜索50000次，計算結果為67次搜索到最優(yōu)解，概率為67%，平均計算時間為1.2369s。而即使保證混合算法100次全收斂到 最優(yōu)解所花費的平均計算時間也只為0.2142s（表1），可見混合算法優(yōu)于文獻5的方法。   &

14、#160;表1M取不同數(shù)值時函數(shù) 的計算結果    _     M 搜索到全局最優(yōu)點的次數(shù) 搜索到最優(yōu)的概率 平均計算時間      (-0.0898,0.7126) (0.0898,-0.7126)_     1000 44 39 83% 0.1214s      3000 53 45 98% 0.1955s      5000 53 47 100% 0.

15、2142s _         表2M取不同數(shù)值時函數(shù) 的計算結果    _     M 搜索到全局最優(yōu)點的次數(shù) 搜索到最優(yōu)的概率 平均計算時間 _     1500 40 40% 0.1406s      5000 73 73% 0.2505s      10000 88 88% 0.4197s  

16、0;   50000 100 100% 1.6856s _         4 計算結果分析     由表1和表2可見，混合算法全局尋優(yōu)能力隨M的增加而增大，當M達到某一足夠大的數(shù)值Mu后，搜索到全局最優(yōu)的概率可以達到100。    從理論上說，Mu趨向無窮大時，才能使混沌變量遍歷所有狀態(tài)，才能真正以概率1搜索到最優(yōu)點。但是，本文混沌運動M次的作用是幫助BFGS方法跳出局部最優(yōu)點，達到比當前局部最優(yōu)函數(shù)值更小的另一局

17、部最優(yōu)附近的某一點處，并不是要混沌變量遍歷所有狀態(tài)。由混沌運動遍歷特性可知，對于某一具體問題，Mu達到某一具體有限數(shù)值時，混沌變量的遍歷性可以得到較好模擬，這一點是可以滿足的，實際算例也證實了這一點。     由于函數(shù)性態(tài)、復雜性不同，對于不同函數(shù)，如這里的測試函數(shù) 、 ，數(shù)值Mu的大小是有差別的。對于同一函數(shù)，搜索區(qū)間增大，在相同混沌運動次數(shù)下，即使始點相同，總體而言會降低其搜索到全局最優(yōu)的概率,要保證算法仍然以概率1收斂到全局最優(yōu)，必然引起Mu 增大。跟蹤計算中間結果證實，當M足夠大時，混合算法的確具有跳出局部最優(yōu)點，繼續(xù)向全局最優(yōu)進行搜索的能力；并

18、且混合算法的計算時間主要花費在為使混合算法具有全局搜索能力而進行混沌搜索上。    5 結語     利用混沌變量的運動特點進行優(yōu)化，具有非常強的跳出局部最優(yōu)解的能力，該方法與BFGS方法結合使用，在可以接受的計算量下能夠計算得到問題的最優(yōu)解。實際上，混沌優(yōu)化可以和一般的下降類算法結合使用，并非局限于本文采用的BFGS方法。采用的Logistic映射產(chǎn)生混沌變量序列，只是產(chǎn)生混沌變量的有效方式之一。    混沌運動與隨機運動是不同的?；煦缡谴_定性系統(tǒng)中由于內稟隨機性而產(chǎn)生的一

19、種復雜的、貌似無規(guī)的運動。混沌并不是無序和紊亂，更像是沒有周期的秩序。與隨機運動相比較，混沌運動可以在各態(tài)歷經(jīng)的假設下，應用統(tǒng)計的數(shù)字特征來描述。并且，混沌運動不重復地經(jīng)過同一狀態(tài)，采用混沌變量進行優(yōu)化比采用隨機變量進行優(yōu)化具有優(yōu)勢。    混沌優(yōu)化與下降類方法結合使用是有潛力的一種全局優(yōu)化途徑，是求解具有變量界約束優(yōu)化問題的可靠方法。如何進一步提高搜索效率，以及如何把混沌優(yōu)化有效應用于復雜約束優(yōu)化問題是值得進一步研究的課題。    本文算法全局收斂性的嚴格數(shù)學證明正在進行之中。   

20、 參考文獻     1胡山鷹，陳丙珍，何小榮，沈靜珠非線性規(guī)劃問題全局優(yōu)化的模擬退火法J清華大學學報，37(6)，1997，5-9     2C A Floudas, A Aggarwal, A R Ciric Global optimum search for nonconvex NLP and MINLP problemsJ. Comput Chem Engng 1989， 13(10)， 11171132     3康立山，謝云，尤矢勇等非數(shù)值并行算法（第一冊

21、）模擬退火算法M北京：科學出版社，1998     4劉勇，康立山，陳琉屏非數(shù)值并行算法（第二冊）遺傳算法M北京：科學出版社，1998     5李兵，蔣慰孫混沌優(yōu)化方法及其應用J控制理論與應用，14(4)，1997，613-615     6張彤，王宏偉，王子才變尺度混沌優(yōu)化方法及其應用J控制與決策，14(3)，1999，285-287     7席少霖非線性最優(yōu)化方法M北京：高等教育出版社，1992   

22、0; 8席少霖，趙鳳志最優(yōu)化計算方法M上海：上?？茖W技術出版社，1983     9Press W H, Tenkolsky S A, Vetterling W T, Flannery B PNumerical Recipes in C, The Art of Scientific ComputingM Second edition， Cambridge University Press， 1992     10J C PortsThe development and evaluation of an improved genetic algorithm based on migration and artificial selectionJIEEE Trans. Syst. Man and Cybern.1994, 24(1)，73-85     A Hybrid Approach for N