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

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

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

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

4、2.1BFGS方法作為求解無約束最優(yōu)化問題的擬牛頓方法類最有代表性的算法之一，BFGS方法處理凸非線性規(guī)劃問題，以其完善的數(shù)學(xué)理論基礎(chǔ)、采用不精確線性搜索時(shí)的超線性收斂性和處理實(shí)際問題有效性，受到人們的重視7-9。擬牛頓方法使用了二階導(dǎo)數(shù)信息，但是并不直接計(jì)算函數(shù)的Hesse矩陣，而是采用一階梯度信息來構(gòu)造一系列的正定矩陣來逼近Hesse矩陣。BFGS方法求解無約束優(yōu)化問題min()的主要步驟如下：(1)給變量賦初值x0，變量維數(shù)n和BFGS方法收斂精度，令B0=I（單位陣），k=0，計(jì)算在點(diǎn)x0的梯度g0。(2)取sk=-Bk-1gk，沿sk作一維搜索，確定最優(yōu)步長(zhǎng)k，得新點(diǎn)xk+1=xk+

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

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

7、解全局極小問題min?；旌纤惴ㄖ谢煦缢阉鞯淖饔檬谴蠓秶暧^搜索，使得算法具有全局尋優(yōu)性能。而BFGS搜索的作用是局部地、細(xì)致地進(jìn)行優(yōu)化搜索，處理的是小范圍搜索問題和搜索加速問題。3算例圖1函數(shù)-特性示意圖圖2函數(shù)特性示意圖采用如下兩個(gè)非常復(fù)雜的、常用于測(cè)試遺傳算法性能的函數(shù)測(cè)試本文算法：函數(shù)稱為Camel函數(shù)，該函數(shù)有6個(gè)局部極小點(diǎn)(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)為兩個(gè)全局最小點(diǎn)，最小值為-1.031628。函數(shù)稱為Schaffer's函數(shù)，該函數(shù)有無數(shù)個(gè)極大值，其中只有（0，0）為全局最大點(diǎn)，最大值為1。此函數(shù)的最大峰值周圍有一圈脊，它們的取值均為0.990283，因此很容易停留在此局部極大點(diǎn)。文獻(xiàn)10采用該函數(shù)對(duì)該文提出的基于移動(dòng)和人工選擇的改進(jìn)遺傳算法（GAMAS）其性能進(jìn)行了考察，運(yùn)行50次，40的情況下該函數(shù)的唯一全局最優(yōu)點(diǎn)能夠找到。而采用本文混合算法，由計(jì)算機(jī)內(nèi)部隨機(jī)函數(shù)自動(dòng)隨機(jī)生產(chǎn)100個(gè)不同的初始點(diǎn)，由這些初始點(diǎn)出發(fā)，一般混合算法迭代24次即能夠收斂。M取不同數(shù)值時(shí)對(duì)函數(shù)、的計(jì)算結(jié)果分別如

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

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

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

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

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

14、矢勇等非數(shù)值并行算法（第一冊(cè)）模擬退火算法M北京：科學(xué)出版社，19984劉勇，康立山，陳琉屏非數(shù)值并行算法（第二冊(cè)）遺傳算法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)化計(jì)算方法M上海：上?？茖W(xué)技術(shù)出版社，19839PressWH,TenkolskySA,VetterlingWT,FlanneryBPNumericalRecipesinC,TheArt

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