非線性最優(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)域中，很多問題是具有非凸性的。對此普通的優(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方法，提出一種求解具有簡單界約束最優(yōu)化問題(1)的混合算法。 min (1) 混沌是存在于非線性系統(tǒng)中的一種較為普遍的現(xiàn)象。混沌運(yùn)動宏觀上無序無律，具有內(nèi)隨機(jī)性、非周期性和局部不穩(wěn)定性

3、，微觀上有序有律，并不是完全的隨機(jī)運(yùn)動，具有無窮嵌套的自相似幾何結(jié)構(gòu)、存在普適性規(guī)律，并不是雜亂無章的。利用混沌變量的隨機(jī)性、遍歷性和規(guī)律性特點(diǎn)可以進(jìn)行優(yōu)化搜索5，且混沌優(yōu)化方法容易跳出局部最優(yōu)點(diǎn)。但是某些狀態(tài)需要很長時(shí)間才能達(dá)到，如果最優(yōu)值在這些狀態(tài)時(shí)，計(jì)算時(shí)間勢必很長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 混沌BF

4、GS混合優(yōu)化方法 2.1 BFGS方法 作為求解無約束最優(yōu)化問題的擬牛頓方法類最有代表性的算法之一，BFGS方法處理凸非線性規(guī)劃問題，以其完善的數(shù)學(xué)理論基礎(chǔ)、采用不精確線性搜索時(shí)的超線性收斂性和處理實(shí)際問題有效性，受到人們的重視7-9。擬牛頓方法使用了二階導(dǎo)數(shù)信息，但是并不直接計(jì)算函數(shù)的Hesse矩陣，而是采用一階梯度信息 來構(gòu)造一系列的正定矩陣 來逼近Hesse矩陣 。BFGS方法求解無約束優(yōu)化問題min ( )的主要步驟如下： 2.2 混沌優(yōu)化方法 利用混沌搜索求解問題(1)時(shí)，先建立待求變量 與混沌變量 的一一對應(yīng)關(guān)系，本文采用 。然后,由Logistic映射式(4)產(chǎn)生 個(gè)軌跡不同的混

5、沌變量 （ ）進(jìn)行優(yōu)化搜索，式(4)中 =4。已經(jīng)證明， =4是“單片”混沌， 在0,1之間歷遍。 2.3 混合優(yōu)化方法 混合算法中混沌搜索的作用是大范圍宏觀搜索，使得算法具有全局尋優(yōu)性能。而BFGS搜索的作用是局部地、細(xì)致地進(jìn)行優(yōu)化搜索，處理的是小范圍搜索問題和搜索加速問題。3 算例 采用如下兩個(gè)非常復(fù)雜的、常用于測試遺傳算法性能的函數(shù)測試本文算法： 函數(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,

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

7、M取不同數(shù)值時(shí)對函數(shù) 、 的計(jì)算結(jié)果分別如表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的算法對函數(shù) 優(yōu)化計(jì)算100次，以 作為收斂標(biāo)準(zhǔn)，混沌搜索50000次，計(jì)算結(jié)果為67次搜索到最優(yōu)解，概率為67%，平均計(jì)算時(shí)間為。而即使保證混合算法100次全收斂到 最優(yōu)解所花費(fèi)的平均計(jì)算時(shí)間也只為（表1），可見混合算法優(yōu)于文獻(xiàn)5的方法。表1M取不同數(shù)值時(shí)函數(shù) 的計(jì)算結(jié)果4 計(jì)算結(jié)果分析 由表1和表2可見，混合算法全局尋優(yōu)能力隨M的增加而增大，當(dāng)M達(dá)到某

8、一足夠大的數(shù)值Mu后，搜索到全局最優(yōu)的概率可以達(dá)到100。從理論上說，Mu趨向無窮大時(shí)，才能使混沌變量遍歷所有狀態(tài)，才能真正以概率1搜索到最優(yōu)點(diǎn)。但是，本文混沌運(yùn)動M次的作用是幫助BFGS方法跳出局部最優(yōu)點(diǎn)，達(dá)到比當(dāng)前局部最優(yōu)函數(shù)值更小的另一局部最優(yōu)附近的某一點(diǎn)處，并不是要混沌變量遍歷所有狀態(tài)。由混沌運(yùn)動遍歷特性可知，對于某一具體問題，Mu達(dá)到某一具體有限數(shù)值時(shí)，混沌變量的遍歷性可以得到較好模擬，這一點(diǎn)是可以滿足的，實(shí)際算例也證實(shí)了這一點(diǎn)。 由于函數(shù)性態(tài)、復(fù)雜性不同，對于不同函數(shù)，如這里的測試函數(shù) 、 ，數(shù)值Mu的大小是有差別的。對于同一函數(shù)，搜索區(qū)間增大，在相同混沌運(yùn)動次數(shù)下，即使始點(diǎn)相同，

9、總體而言會降低其搜索到全局最優(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é)語 利用混沌變量的運(yùn)動特點(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)動與隨機(jī)運(yùn)動

10、是不同的?；煦缡谴_定性系統(tǒng)中由于內(nèi)稟隨機(jī)性而產(chǎn)生的一種復(fù)雜的、貌似無規(guī)的運(yùn)動?；煦绮⒉皇菬o序和紊亂，更像是沒有周期的秩序。與隨機(jī)運(yùn)動相比較，混沌運(yùn)動可以在各態(tài)歷經(jīng)的假設(shè)下，應(yīng)用統(tǒng)計(jì)的數(shù)字特征來描述。并且，混沌運(yùn)動不重復(fù)地經(jīng)過同一狀態(tài)，采用混沌變量進(jìn)行優(yōu)化比采用隨機(jī)變量進(jìn)行優(yōu)化具有優(yōu)勢?；煦鐑?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清

11、華大學(xué)學(xué)報(bào)，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ù)值并行算法（第一冊）模擬退火算法M北京：科學(xué)出版社，1998 4劉勇，康立山，陳琉屏非數(shù)值并行算法（第二冊）遺傳算法M北京：科學(xué)出版社，1998 5李兵，蔣慰孫混沌優(yōu)化方法及其應(yīng)用J控制理論與應(yīng)用，14(4)，1997，613-615 6張彤，王宏偉，王

12、子才變尺度混沌優(yōu)化方法及其應(yīng)用J控制與決策，14(3)，1999，285-287 7席少霖非線性最優(yōu)化方法M北京：高等教育出版社，1992 8席少霖，趙鳳志最優(yōu)化計(jì)算方法M上海：上?？茖W(xué)技術(shù)出版社，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 eval

13、uation 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 Nonlinear OptimizationAbstract：Combined BFGS method with chaos optimization method, a hybrid approach was proposed to solve nonlinear optimizat

14、ion 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 t