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

1、非線性最優(yōu)化問題的一種混合解法摘要：把BFGS方法與混沌優(yōu)化方法相結(jié)合，基于混沌變量提出一種求解具有變量邊界約束非線性最優(yōu)化問題的混合優(yōu)化方法?；旌纤惴骖櫫嘶煦鐑?yōu)化全局搜索能力強和BFGS方法收斂速度快的優(yōu)點，成為一種求解非凸優(yōu)化問題全局最優(yōu)的有效方法。算例表明，當(dāng)混沌搜索的次數(shù)達到一定數(shù)量時，混合優(yōu)化方法可以保證算法收斂到全局最優(yōu)解，且計算效率比混沌優(yōu)化方法有很大提高。關(guān)鍵詞：混合法；BFGS方法；混沌優(yōu)化方法；全局最優(yōu)1引言在系統(tǒng)工程、控制工程、統(tǒng)計學(xué)、反問題優(yōu)化求解等領(lǐng)域中，很多問題是具有非凸性的。對此普通的優(yōu)化技術(shù)只能求出局部最優(yōu)解，因為這些確定性算法總是解得最近的一個極值點1，只有

2、能夠給出很好的初始點才有可能得出所需要的全局最優(yōu)解。為此，實際應(yīng)用中通過在多個初始點上使用傳統(tǒng)數(shù)值優(yōu)化方法來求取全局解的方法仍然被人們所采用，但是這種處理方法求得全局解的概率不高，可靠性低，建立盡可能大概率的求解全局解算法仍然是一個重要問題。近年來基于梯度法的全局最優(yōu)化方法已經(jīng)有所研究2，基于隨機搜索技術(shù)的遺傳算法和模擬退火算法等在全局優(yōu)化問題中的應(yīng)用也得到越來越大的重視3-4。本文則基于混沌優(yōu)化和BFGS方法，提出一種求解具有簡單界約束最優(yōu)化問題(1)的混合算法。min(1)混沌是存在于非線性系統(tǒng)中的一種較為普遍的現(xiàn)象。混沌運動宏觀上無序無律，具有內(nèi)隨機性、非周期性和局部不穩(wěn)定性，微觀上有序

3、有律，并不是完全的隨機運動，具有無窮嵌套的自相似幾何結(jié)構(gòu)、存在普適性規(guī)律，并不是雜亂無章的。利用混沌變量的隨機性、遍歷性和規(guī)律性特點可以進行優(yōu)化搜索5，且混沌優(yōu)化方法容易跳出局部最優(yōu)點。但是某些狀態(tài)需要很長時間才能達到，如果最優(yōu)值在這些狀態(tài)時，計算時間勢必很長5。可以說混沌優(yōu)化具有全局搜索能力，其局部搜索能力稍顯不足，文5采用二次載波技術(shù)，文6考慮逐漸縮小尋優(yōu)變量的搜索空間都是為了彌補這一弱點。而本文則采用混沌搜索與BFGS方法進行優(yōu)化求解，一方面采用混沌搜索幫助BFGS方法跳出局部最優(yōu)，另一方面利用BFGS增強解附近的超線性收斂速度和搜索能力，以提高搜索最優(yōu)的效率。2混沌BFGS混合優(yōu)化方法

4、2.1BFGS方法作為求解無約束最優(yōu)化問題的擬牛頓方法類最有代表性的算法之一，BFGS方法處理凸非線性規(guī)劃問題，以其完善的數(shù)學(xué)理論基礎(chǔ)、采用不精確線性搜索時的超線性收斂性和處理實際問題有效性，受到人們的重視7-9。擬牛頓方法使用了二階導(dǎo)數(shù)信息，但是并不直接計算函數(shù)的Hesse矩陣，而是采用一階梯度信息來構(gòu)造一系列的正定矩陣來逼近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+

5、ksk，計算xk+1點的梯度gk+1。(3)若|gk+1|，則令，BFGS搜索結(jié)束，轉(zhuǎn)步驟3；否則執(zhí)行(4)。(4)計算Bk+1：(2)(3)(5)k=k+1，轉(zhuǎn)(2)。2.2混沌優(yōu)化方法利用混沌搜索求解問題(1)時，先建立待求變量與混沌變量的一一對應(yīng)關(guān)系，本文采用。然后,由Logistic映射式(4)產(chǎn)生個軌跡不同的混沌變量（）進行優(yōu)化搜索，式(4)中=4。已經(jīng)證明，=4是“單片”混沌，在0,1之間歷遍。(4)(1)給定最大混沌變量運動次數(shù)M；給賦初值，計算和；置，。(2)。(3)。(4)若kM，若，令，；若，和保持不變；然后令k=k+1，轉(zhuǎn)(2)。若kM，則，混沌搜索結(jié)束。2.3混合優(yōu)化方

6、法混沌方法和BFGS方法混合求解連續(xù)對象的全局極小值優(yōu)化問題(1)的步驟如下：step1設(shè)置混沌搜索的最大次數(shù)M，迭代步數(shù)iter=0，變量賦初值x0，。step2以為始點BFGS搜索，得當(dāng)前BFGS方法最優(yōu)解及=。step3若，取=；若，??；若，取，是相對于,較小的數(shù)。step4以為始點進行混沌搜索M次，得混沌搜索后的最優(yōu)解及=。step5若，iter=iter+1，轉(zhuǎn)step2；否則執(zhí)行step6。step6改變混沌搜索軌跡，再次進行混沌搜索，即給加微小擾動，執(zhí)行step4，得搜索結(jié)果和。若，iter=iter+1，轉(zhuǎn)step2；否則計算結(jié)束，輸出、。對全局極大值問題，max，可以轉(zhuǎn)化為求

7、解全局極小問題min?；旌纤惴ㄖ谢煦缢阉鞯淖饔檬谴蠓秶暧^搜索，使得算法具有全局尋優(yōu)性能。而BFGS搜索的作用是局部地、細(xì)致地進行優(yōu)化搜索，處理的是小范圍搜索問題和搜索加速問題。3算例圖1函數(shù)-特性示意圖圖2函數(shù)特性示意圖采用如下兩個非常復(fù)雜的、常用于測試遺傳算法性能的函數(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.7126)，其中(-0.0898,0.71

8、26)和(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)點能夠找到。而采用本文混合算法，由計算機內(nèi)部隨機函數(shù)自動隨機生產(chǎn)100個不同的初始點，由這些初始點出發(fā)，一般混合算法迭代24次即能夠收斂。M取不同數(shù)值時對函數(shù)、的計算結(jié)果分別如

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

10、126)_%0.1214s%0.1955s%0.2142s_表2M取不同數(shù)值時函數(shù)的計算結(jié)果_M搜索到全局最優(yōu)點的次數(shù)搜索到最優(yōu)的概率平均計算時間_15004040%0.1406s50007373%0.2505s%0.4197s%1.6856s_4計算結(jié)果分析由表1和表2可見，混合算法全局尋優(yōu)能力隨M的增加而增大，當(dāng)M達到某一足夠大的數(shù)值Mu后，搜索到全局最優(yōu)的概率可以達到100。從理論上說，Mu趨向無窮大時，才能使混沌變量遍歷所有狀態(tài)，才能真正以概率1搜索到最優(yōu)點。但是，本文混沌運動M次的作用是幫助BFGS方法跳出局部最優(yōu)點，達到比當(dāng)前局部最優(yōu)函數(shù)值更小的另一局部最優(yōu)附近的某一點處，并不是要

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

12、混沌變量的運動特點進行優(yōu)化，具有非常強的跳出局部最優(yōu)解的能力，該方法與BFGS方法結(jié)合使用，在可以接受的計算量下能夠計算得到問題的最優(yōu)解。實際上，混沌優(yōu)化可以和一般的下降類算法結(jié)合使用，并非局限于本文采用的BFGS方法。采用的Logistic映射產(chǎn)生混沌變量序列，只是產(chǎn)生混沌變量的有效方式之一。混沌運動與隨機運動是不同的?；煦缡谴_定性系統(tǒng)中由于內(nèi)稟隨機性而產(chǎn)生的一種復(fù)雜的、貌似無規(guī)的運動?；煦绮⒉皇菬o序和紊亂，更像是沒有周期的秩序。與隨機運動相比較，混沌運動可以在各態(tài)歷經(jīng)的假設(shè)下，應(yīng)用統(tǒng)計的數(shù)字特征來描述。并且，混沌運動不重復(fù)地經(jīng)過同一狀態(tài)，采用混沌變量進行優(yōu)化比采用隨機變量進行優(yōu)化具有優(yōu)勢。

13、混沌優(yōu)化與下降類方法結(jié)合使用是有潛力的一種全局優(yōu)化途徑，是求解具有變量界約束優(yōu)化問題的可靠方法。如何進一步提高搜索效率，以及如何把混沌優(yōu)化有效應(yīng)用于復(fù)雜約束優(yōu)化問題是值得進一步研究的課題。本文算法全局收斂性的嚴(yán)格數(shù)學(xué)證明正在進行之中。參考文獻1胡山鷹，陳丙珍，何小榮，沈靜珠非線性規(guī)劃問題全局優(yōu)化的模擬退火法J清華大學(xué)學(xué)報，37(6)，1997，5-92CAFloudas,AAggarwal,ARCiricGlobaloptimumsearchfornonconvexNLPandMINLPproblemsJ.ComputChemEngng1989，13(10)，111711323康立山，謝云，尤

14、矢勇等非數(shù)值并行算法（第一冊）模擬退火算法M北京：科學(xué)出版社，19984劉勇，康立山，陳琉屏非數(shù)值并行算法（第二冊）遺傳算法M北京：科學(xué)出版社，19985李兵，蔣慰孫混沌優(yōu)化方法及其應(yīng)用J控制理論與應(yīng)用，14(4)，1997，613-6156張彤，王宏偉，王子才變尺度混沌優(yōu)化方法及其應(yīng)用J控制與決策，14(3)，1999，285-2877席少霖非線性最優(yōu)化方法M北京：高等教育出版社，19928席少霖，趙鳳志最優(yōu)化計算方法M上海：上海科學(xué)技術(shù)出版社，19839PressWH,TenkolskySA,VetterlingWT,FlanneryBPNumericalRecipesinC,TheArt

15、ofScientificComputingMSecondedition，CambridgeUniversityPress，199210JCPortsThedevelopmentandevaluationofanimprovedgeneticalgorithmbasedonmigrationandartificialselectionJIEEETrans.Syst.ManandCybern.1994,24(1)，73-85AHybridApproachforNonlinearOptimizationAbstract：CombinedBFGSmethodwithchaosoptimizationmethod,ahybridapproachwasproposedtosolvenonlinearoptimizationproblemswithboundaryrestraintsofvariables.Thehybridmethodisaneffectiveapproachtosolvenonconvexoptimizationproblems,asitgivenbothattentionstotheinherentvirtuetolocateglobaloptimumofchaosoptimizationmethodandtheadvantageofhighconve