CIMS論文的天地

 

非線性最優化問題的一種混合解法

注意:本論文已在《工程力學 》2001,18(3)61-66發表
使用者請注明論文出處

(EI已收錄本文)

王登剛1,2 ,劉迎曦1,2 ,李守巨1,2

(1.大連理工大學工程力學系,遼寧 大連,116023;2.工業裝備結構分析國家重點實驗室,遼寧大連,116023)

摘 要:把BFGS方法與混沌優化方法相結合,基于混沌變量提出一種求解具有變量邊界約束非線性最優化問題的混合優化方法。混合算法兼顧了混沌優化全局搜索能力強和BFGS方法收斂速度快的優點,成為一種求解非凸優化問題全局最優的有效方法。算例表明,當混沌搜索的次數達到一定數量時,混合優化方法可以保證算法收斂到全局最優解,且計算效率比混沌優化方法有很大提高。
關鍵詞:混合法;BFGS方法;混沌優化方法;全局最優
中圖分類號:O39 文獻標識碼:A

1  引言

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

    混沌是存在于非線性系統中的一種較為普遍的現象。混沌運動宏觀上無序無律,具有內隨機性、非周期性和局部不穩定性,微觀上有序有律,并不是完全的隨機運動,具有無窮嵌套的自相似幾何結構、存在普適性規律,并不是雜亂無章的。利用混沌變量的隨機性、遍歷性和規律性特點可以進行優化搜索[5],且混沌優化方法容易跳出局部最優點。但是某些狀態需要很長時間才能達到,如果最優值在這些狀態時,計算時間勢必很長[5]。可以說混沌優化具有全局搜索能力,其局部搜索能力稍顯不足,文[5]采用二次載波技術,文[6]考慮逐漸縮小尋優變量的搜索空間都是為了彌補這一弱點。而本文則采用混沌搜索與BFGS方法進行優化求解,一方面采用混沌搜索幫助BFGS方法跳出局部最優,另一方面利用BFGS增強解附近的超線性收斂速度和搜索能力,以提高搜索最優的效率。

2  混沌-BFGS混合優化方法

2.1 BFGS方法

作為求解無約束最優化問題的擬牛頓方法類最有代表性的算法之一,BFGS方法處理凸非線性規劃問題,以其完善的數學理論基礎、采用不精確線性搜索時的超線性收斂性和處理實際問題有效性,受到人們的重視[7-9]。擬牛頓方法使用了二階導數信息,但是并不直接計算函數的Hesse矩陣,而是采用一階梯度信息 來構造一系列的正定矩陣 來逼近Hesse矩陣 BFGS方法求解無約束優化問題min ( )的主要步驟如下:

  (1)  給變量賦初值x0,變量維數nBFGS方法收斂精度ε,B0=I(單位陣),k=0,計算 x0的梯度g0

  (2)  sk=-Bk-1gk,沿sk作一維搜索,確定最優步長αk ,得新點xk+1=xkksk,計算xk+1點的梯度gk+1

  (3)  ||gk+1||≤ε,則令 BFGS搜索結束,轉步驟3;否則執行(4)。

  (4)  計算Bk+1

            (2)

                         (3)

  (5)  k=k+1,轉(2)。

2.2 混沌優化方法

利用混沌搜索求解問題(1)時,先建立待求變量 與混沌變量 的一一對應關系,本文采用 。然后,由Logistic映射式(4)產生 個軌跡不同的混沌變量 )進行優化搜索,式(4)中 =4。已經證明, =4是“單片”混沌, 在[0,1]之間歷遍。

                (4)

  (1)給定最大混沌變量運動次數M;給 賦初值 ,計算 ;置

  (2) 

  (3) 

  (4)  k<M

            ,令

            保持不變;

            然后令k=k+1 ,轉(2)

          k>M,則 ,混沌搜索結束。

2.3 混合優化方法

    混沌方法和BFGS方法混合求解連續對象的全局極小值優化問題(1)的步驟如下:

step1  設置混沌搜索的最大次數M,迭代步數iter=0,變量賦初值x0

step2   為始點BFGS搜索,得當前BFGS方法最優解 =

step3 ,取 = ;若 ,取 ;若 ,取 是相對于 , 較小的數。

step 4  為始點進行混沌搜索M次,得混沌搜索后的最優解 =

step5  < iter=iter+1 ,轉step2;否則執行step6

step6  改變混沌搜索軌跡,再次進行混沌搜索,即給 加微小擾動 ,執行step 4,得搜索結果 。若 < iter=iter+1 ,轉step2;否則計算結束,輸出

       對全局極大值問題,max ,可以轉化為求解全局極小問題min

混合算法中混沌搜索的作用是大范圍宏觀搜索,使得算法具有全局尋優性能。而BFGS搜索的作用是局部地、細致地進行優化搜索,處理的是小范圍搜索問題和搜索加速問題。

3  算例


        1   函數- 特性示意圖                                         2   函數 特性示意圖

采用如下兩個非常復雜的、常用于測試遺傳算法性能的函數測試本文算法:

     

                   

函數 稱為Camel 函數,該函數有6個局部極小點(1.607105, 0.568651)(-1.607105, -0.568651)(1.703607, -0.796084)(-1.703607, 0.796084)(-0.0898,0.7126)(0.0898,-0.7126),其中(-0.0898,0.7126)(0.0898,-0.7126)為兩個全局最小點,最小值為-1.031628。函數 稱為 Schaffer's函數,該函數有無數個極大值,其中只有(0,0)為全局最大點,最大值為1。此函數的最大峰值周圍有一圈脊,它們的取值均為0.990283,因此很容易停留在此局部極大點。文獻[10]采用該函數對該文提出的基于移動和人工選擇的改進遺傳算法(GAMAS)其性能進行了考察,運行50次,40%的情況下該函數的唯一全局最優點能夠找到。而采用本文混合算法,由計算機內部隨機函數自動隨機生產100個不同的初始點,由這些初始點出發,一般混合算法迭代2-4次即能夠收斂。M取不同數值時對函數 的計算結果分別如表1和表2所示,表中計算時間是指在奔騰133微機上計算時間。

由表2可見,當M=1500時,本文方法搜索到 最優解的概率即達到40%,而此時計算量比文獻[10]小。同樣由混合算法的100個起始點,采用文獻[5]的算法對函數 優化計算100次, 作為收斂標準,混沌搜索50000次,計算結果為67次搜索到最優解,概率為67%,平均計算時間為1.2369s。而即使保證混合算法100次全收斂到 最優解所花費的平均計算時間也只為0.2142s(表1),可見混合算法優于文獻[5]的方法。

1    M取不同數值時函數 的計算結果

_____________________________________________________________________

        M          搜索到全局最優點的次數      搜索到最優的概率   平均計算時間 

                                    (-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.2142s
________________________________________________________________________________________________

 

表2    M取不同數值時函數 的計算結果

___________________________________________________________

            M     搜索到全局最優點的次數  搜索到最優的概率    平均計算時間
____________________________________________________________________________________

           1500            40                     40%            0.1406s

           5000            73                     73%            0.2505s

          10000            88                     88%            0.4197s

      50000           100                    100%            1.6856s
____________________________________________________________________________________

 

 

4  計算結果分析

由表1和表2可見,混合算法全局尋優能力隨M的增加而增大,當M達到某一足夠大的數值Mu后,搜索到全局最優的概率可以達到100%。

       從理論上說,Mu趨向無窮大時,才能使混沌變量遍歷所有狀態,才能真正以概率1搜索到最優點。但是,本文混沌運動M次的作用是幫助BFGS方法跳出局部最優點,達到比當前局部最優函數值更小的另一局部最優附近的某一點處,并不是要混沌變量遍歷所有狀態。由混沌運動遍歷特性可知,對于某一具體問題,Mu達到某一具體有限數值時,混沌變量的遍歷性可以得到較好模擬,這一點是可以滿足的,實際算例也證實了這一點。

    由于函數性態、復雜性不同,對于不同函數,如這里的測試函數 ,數值Mu的大小是有差別的。對于同一函數,搜索區間增大,在相同混沌運動次數下,即使始點相同,總體而言會降低其搜索到全局最優的概率,要保證算法仍然以概率1收斂到全局最優,必然引起Mu 增大。跟蹤計算中間結果證實,當M足夠大時,混合算法的確具有跳出局部最優點,繼續向全局最優進行搜索的能力;并且混合算法的計算時間主要花費在為使混合算法具有全局搜索能力而進行混沌搜索上。

5  結語

利用混沌變量的運動特點進行優化,具有非常強的跳出局部最優解的能力,該方法與BFGS方法結合使用,在可以接受的計算量下能夠計算得到問題的最優解。實際上,混沌優化可以和一般的下降類算法結合使用,并非局限于本文采用的BFGS方法。采用的Logistic映射產生混沌變量序列,只是產生混沌變量的有效方式之一。

混沌運動與隨機運動是不同的。混沌是確定性系統中由于內稟隨機性而產生的一種復雜的、貌似無規的運動。混沌并不是無序和紊亂,更像是沒有周期的秩序。與隨機運動相比較,混沌運動可以在各態歷經的假設下,應用統計的數字特征來描述。并且,混沌運動不重復地經過同一狀態,采用混沌變量進行優化比采用隨機變量進行優化具有優勢。

混沌優化與下降類方法結合使用是有潛力的一種全局優化途徑,是求解具有變量界約束優化問題的可靠方法。如何進一步提高搜索效率,以及如何把混沌優化有效應用于復雜約束優化問題是值得進一步研究的課題。

本文算法全局收斂性的嚴格數學證明正在進行之中。

參考文獻

[1]胡山鷹,陳丙珍,何小榮,沈靜珠.非線性規劃問題全局優化的模擬退火法[J].清華大學學報,37(6)19975-9

[2]C A Floudas, A Aggarwal, A R Ciric Global optimum search for nonconvex NLP and MINLP problems[J]. Comput Chem Engng 1989 13(10) 1117~1132

[3]康立山,謝云,尤矢勇等.非數值并行算法(第一冊)――模擬退火算法[M].北京:科學出版社,1998

[4]劉勇,康立山,陳琉屏.非數值并行算法(第二冊)――遺傳算法[M].北京:科學出版社,1998

[5]李兵,蔣慰孫.混沌優化方法及其應用[J].控制理論與應用,14(4)1997613-615

[6]張彤,王宏偉,王子才.變尺度混沌優化方法及其應用[J].控制與決策,14(3)1999285-287

[7]席少霖.非線性最優化方法[M].北京:高等教育出版社,1992

[8]席少霖,趙鳳志.最優化計算方法[M].上海:上海科學技術出版社,1983

[9]Press W H, Tenkolsky S A, Vetterling W T, Flannery B PNumerical Recipes in C, The Art of Scientific Computing[M] Second edition Cambridge University Press 1992

[10]J C PortsThe development and evaluation of an improved genetic algorithm based on migration and artificial selection[J]IEEE Trans. Syst. Man and Cybern.1994, 24(1)73-85

A Hybrid Approach for Nonlinear Optimization

WANG Denggang1,2 ,  LIU Yingxi1,2 ,  LI-Shouju1,2

(1. Dalian University of Technology, Dalian, 116023     2.State Key Lab. of Struct. Anal. of Ind. Equip., Dalian, 116023) 

AbstractCombined BFGS method with chaos optimization method, a hybrid approach was proposed to solve nonlinear optimization problems with boundary restraints of variables. The hybrid method is an effective approach to solve nonconvex optimization problems, as it given both attentions to the inherent virtue to locate global optimum of chaos optimization method and the advantage of high convergence speed of BFGS method. Numerical examples illustrate that the present method possesses both good capability to search global optima and far higher convergence speed than that of chaos optimization method.
key wordshybrid approachBFGS methodchaos optimization methodglobal optimum


本站收錄的本文作者的其他論文:

1、A relialble approach to compute the forward kinematics of robot with uncertain geometric parameters

2、巷道圍巖初始應力場和彈性模量的區間反演方法

3、混凝土重力壩振動參數識別研究

4、求解不可微函數優化的一種混合遺傳算法

5、結構可靠性分析的區間方法

 更多相關論文請點擊本站的<<<站內全文搜索>>>查找

歡迎您參加討論,發表您對此論文及其研究領域的看法!
(請在發言時在標題中使用所點評的論文的題目或研究方向,這樣方便大家瀏覽!)

返回首頁 | CIMS論文 | 并行工程 | 虛擬制造 | 敏捷制造 | 其他論文 | 項目開發 | 學術資源 | 站內全文搜索 | 免費論文網站大全 |

line.gif (4535 字節)

為了更好的為大家服務,歡迎您參加本站的投票調查

>>>>參加更多投票調查請點擊!

本站永久域名:http://www.sqvswk.live歡迎訪問

注意:本站內容未經書面允許不得轉載

All rights reserved, all contents copyright 2000-2019
本站自2000年3月總網頁訪問量為
pk10开奖记录直播