宋巨龍,錢富才,梁錦錦

(1.西安石油大學(xué) 理學(xué)院, 陜西 西安 710065;2.西安理工大學(xué) 自動化與信息工程學(xué)院, 陜西 西安 710048)

一種新的無約束優(yōu)化問題的混合算法

宋巨龍1,錢富才2,梁錦錦1

(1.西安石油大學(xué) 理學(xué)院, 陜西 西安 710065;2.西安理工大學(xué) 自動化與信息工程學(xué)院, 陜西 西安 710048)

將傳統(tǒng)的一維搜索方法——成功-失敗法與新的Apollonius填充算法相結(jié)合,給出一種新的平面上的無約束優(yōu)化方法。該方法既將成功-失敗法推廣到了平面上,又將Apollonius填充算法的適用對象由約束問題推廣到了無約束問題。數(shù)值實(shí)驗(yàn)表明,該方法適用于較為復(fù)雜的非線性可微凸函數(shù),如果對計(jì)算時間要求不高的話,該方法可以適用于具有較高復(fù)雜度的非線性可微凸函數(shù),具有一定的實(shí)際應(yīng)用價值。

Apollonius填充; 成功-失敗法; 非線性最優(yōu)化; 算法

非線性函數(shù)尋優(yōu)問題由于其在非線性分析[1]、函數(shù)逼近[2]、系統(tǒng)控制[3]、模式識別[4]等領(lǐng)域的廣泛應(yīng)用,一直受到科學(xué)研究人員與工程技術(shù)人員的高度關(guān)注。關(guān)于這方面的研究,成果眾多,諸如經(jīng)典共軛梯度算法[5]、遺傳算法[6]、模擬退火算法、蟻群算法等等[7],各有其獨(dú)到的優(yōu)點(diǎn),當(dāng)然也都有其局限性,比如共軛梯度法要求目標(biāo)函數(shù)為凸函數(shù),否則會陷入局部最優(yōu),遺傳算法盡管以概率1收斂到目標(biāo)函數(shù)的最優(yōu)解,但由于用不確定性的方法搜索確定性問題,使得搜索效率大大下降。因此,探索新的更為有效的算法成為本文研究的出發(fā)點(diǎn)。

目前,被理論界和工程界廣為接受的眾多算法中,成功-失敗法[8]是一個經(jīng)典的一維搜索算法。該方法用于尋找一維凸函數(shù)的搜索區(qū)間,即包含目標(biāo)函數(shù)最優(yōu)解的區(qū)間,同時該方法也可以直接用來求一維凸函數(shù)的最優(yōu)解,只是效率比黃金分割法等經(jīng)典算法稍低些。此外,該方法的適用范圍僅僅局限于一維凸函數(shù)。

在古老的初等幾何問題中,有一個被命名為Apollonius的問題,就是求任意三個已知圓的公切圓,該問題已經(jīng)圓滿解決。以此為基礎(chǔ),一些關(guān)于該問題的應(yīng)用被提出,文獻(xiàn)[9]利用Apollonius問題的結(jié)論,給出了一個用無限多個圓將一個圓填滿的具體方法,這就是著名的Apollonius填充。文獻(xiàn)[10]在文獻(xiàn)[9]的基礎(chǔ)上對Apollonius填充的構(gòu)造進(jìn)行了深入研究,得到了一些可以在工程設(shè)計(jì)中應(yīng)用的結(jié)果,在那里僅就分形的構(gòu)造進(jìn)行了研究。而文獻(xiàn)[11]則進(jìn)一步將Apollonius填充應(yīng)用到有著廣泛應(yīng)用前景、并且是目前的一個研究難點(diǎn)的非線性全局最優(yōu)化問題中去。在那里將Apollonius填充和分形的思想相結(jié)合,得到了一種特殊區(qū)域——圓域約束下的全局最優(yōu)化計(jì)算方法。該方法可以很好的解決定義在特殊區(qū)域——圓域上的非線性函數(shù)的全局最優(yōu)解,不過在那里,該方法只適用于圓域約束下的非線性函數(shù)最優(yōu)解的求解。

基于對成功-失敗法和Apollonius問題的了解,本文嘗試將兩者相結(jié)合,提出了一種新的優(yōu)化算法。本文的主要方法和目的是:將經(jīng)典的成功-失敗法和Apollonius填充算法相結(jié)合,得到一種基于Apollonius填充的成功-失敗法。其特點(diǎn)是:一方面將成功-失敗法的適用范圍由只適用于一維非線性凸函數(shù)推廣到也適用于二維非線性凸函數(shù),另一方面又可將只適用于圓域約束優(yōu)化問題的Apollonius填充算法推廣到了適用于無約束非線性凸函數(shù)的優(yōu)化問題。數(shù)值實(shí)驗(yàn)表明,該方法可以有效地求得二維非線性凸函數(shù)的無約束最優(yōu)解,除此之外,新方法對搜索路徑通過圖形給出了形象清晰的描述?？偟膩碚f,新方法是對無約束非線性優(yōu)化問題的一種新的探索,給出了一種新的二維無約束優(yōu)化算法,對非線性優(yōu)化研究人員以及工程技術(shù)人員都有一定的參考和實(shí)用價值。

1 成功-失敗法

成功-失敗法是一種傳統(tǒng)的一維搜索方法,其主要功能在于求一維函數(shù)的搜索區(qū)間,也可以用來直接求一維函數(shù)的最優(yōu)解,該方法只適用于單峰函數(shù),具體步驟如下:

為求函數(shù)的最小值點(diǎn),通常分兩步走,首先確定函數(shù)的搜索區(qū)間,然后不斷收縮搜索區(qū)間,直至區(qū)間收縮為一點(diǎn)為止。成功-失敗法正是基于這一理念而產(chǎn)生的。

為方便起見,設(shè)函數(shù)f(x)是R1上的凸函數(shù)。?x0∈R1,步長h>0。

1) 若f(x0)>f(x0+h), 則當(dāng)f(x0+h)>f(x0+3h)時,步長加倍,向前推進(jìn),即令x0=x0+h,h=2h,重新開始搜索;否則得搜索區(qū)間[a,b]=[x0,x0+3h]。

2) 若f(x0)=f(x0+h),則得搜索區(qū)間[a,b]=[x0,x0+h]。

通過這樣的步驟,可以得到凸函數(shù)f(x)的最優(yōu)解所在的區(qū)間。如果還不滿足于此,想進(jìn)一步直接求得函數(shù)的最優(yōu)解,則可采取如下步驟:

Step1 ?x0∈R1,步長h>0,計(jì)算精度ε>0。

Step2 計(jì)算f0=f(x0),f1=f(x0+h)。

Step3 如果|h|<ε,則停止計(jì)算,可取x0為近似最優(yōu)解。

Step4 如果f0>f1,則令x0=x0+h,f0=f1,h=2h,轉(zhuǎn)Step3。

否則，令h=-0.25h,轉(zhuǎn)Step3。

這樣即可獲得目標(biāo)函數(shù)的近似最優(yōu)解。該方法簡單有效,是一種很實(shí)用的一維搜索方法。

2 Apollonius填充及其算法

2.1 Apollonius填充

所謂Apollonius填充,指的是將任意一個圓,用位于其內(nèi)部的無限多個相互外切的圓將該圓完全填滿,使得該圓中的任意一點(diǎn)都可以落入某個填充圓中。至于其中具體的填充方式是可以選擇的。圖1所示是一個填充結(jié)果,無數(shù)個半徑不等的小圓將一個大圓完全填滿。當(dāng)然，這里所謂的填滿其實(shí)是理論上的,由于計(jì)算時間、計(jì)算機(jī)計(jì)算功能及顯示功能的限制,實(shí)際上只能做到近似填滿，不過,如果需要,是可以使填充的滿足程度達(dá)到任意精度的。構(gòu)造該填充的關(guān)鍵方法在于求任意三個相切圓的公切圓,也就是所謂的Apollonius問題的求解,對于如何求解Apollonius問題以及如何實(shí)現(xiàn)Apollonius填充,在文獻(xiàn)[10]中有著詳細(xì)的論述,所以具體實(shí)現(xiàn)方法請參閱文獻(xiàn)[10]。

2.2 Apollonius填充算法

Apollonius填充算法是由文獻(xiàn)[11]提出的,該算法的主要功能在于求解約束區(qū)域?yàn)閳A域的非線性約束問題的全局最優(yōu)解。其主要特點(diǎn)有兩個:①不要求目標(biāo)函數(shù)為凸函數(shù),任意可微非線性函數(shù)都可以,即對目標(biāo)函數(shù)的要求很低;②求得的非線性函數(shù)的最優(yōu)解是圓形約束區(qū)域內(nèi)的全局最優(yōu)解。具體實(shí)現(xiàn)方法如下:

1) 首先任選可行圓域中的一點(diǎn),將其作為當(dāng)前近似最優(yōu)解,對應(yīng)的函數(shù)值作為當(dāng)前近似最優(yōu)值。

2) 對圓形約束區(qū)域進(jìn)行Apollonius填充,也可以看成是對圓域進(jìn)行Apollonius分割,將目標(biāo)函數(shù)的函數(shù)值在每一個圓上的下界進(jìn)行估計(jì),將那些圓域中目標(biāo)函數(shù)值的下界大于當(dāng)前近似最優(yōu)值(即該圓域中必不含有目標(biāo)函數(shù)最優(yōu)解)的圓放棄掉,不對該圓進(jìn)行進(jìn)一步的分割，否則轉(zhuǎn)到下一步。

3) 對那些圓域中目標(biāo)函數(shù)值的下界小于當(dāng)前近似最優(yōu)值,即該圓域中有可能含有目標(biāo)函數(shù)最優(yōu)解的圓,進(jìn)行進(jìn)一步的Apollonius分割。在分割之前,計(jì)算一下該圓圓心的坐標(biāo)以及目標(biāo)函數(shù)在該圓心上的函數(shù)值,如果該函數(shù)值小于當(dāng)前近似最優(yōu)值,則用圓心替代當(dāng)前近似最優(yōu)解,同時用該圓心處的函數(shù)值替代當(dāng)前近似最優(yōu)值。如此不斷進(jìn)行下去,直到滿足事先規(guī)定的精度為止,比如所論圓的直徑小于某精度,或者迭代次數(shù)達(dá)到事先規(guī)定的次數(shù)。

對于上述算法,可能有人會提出這樣的疑問:填充已經(jīng)是無限的了,還要對其中的每個圓再進(jìn)行無限填充,如此大的數(shù)據(jù)量,可以實(shí)現(xiàn)嗎?會不會發(fā)生數(shù)據(jù)爆炸?其實(shí)對此大可不必過于擔(dān)心,由于在計(jì)算過程中要不斷的對目標(biāo)函數(shù)進(jìn)行估計(jì),一旦目標(biāo)函數(shù)在該圓上的下界大于當(dāng)前近似最優(yōu)值,就不再對該圓進(jìn)行進(jìn)一步分割了,所以大多數(shù)圓都很快被放棄掉了,只有少部分圓需要分割,故不會發(fā)生數(shù)據(jù)爆炸。文獻(xiàn)[11]中對大量復(fù)雜的例子進(jìn)行了數(shù)值實(shí)驗(yàn),并沒有發(fā)生數(shù)據(jù)爆炸。

3 新算法的基本原理

下面就新算法的基本原理進(jìn)行論述。

本法求解的優(yōu)化問題為非線性無約束最優(yōu)化問題,優(yōu)化問題的目標(biāo)函數(shù)應(yīng)是非線性可微凸函數(shù)。

本法的基本原理:從任意一點(diǎn)出發(fā),以該點(diǎn)為圓心,取適當(dāng)長度為半徑,用Apollonius填充算法求目標(biāo)函數(shù)在該圓上的全局最優(yōu)解,若該最優(yōu)解落在圓域內(nèi)部,則終止計(jì)算,由于目標(biāo)函數(shù)為凸函數(shù),故該點(diǎn)即為所求目標(biāo)函數(shù)的無約束最優(yōu)解,若該最優(yōu)解落在該圓邊界上,或者非常靠近邊界,則以該最優(yōu)解為新的圓心,仍以上述給定的半徑為半徑,再次用Apollonius填充算法求目標(biāo)函數(shù)在該圓域上的全局最優(yōu)解,直到某最優(yōu)解落入圓的內(nèi)部且遠(yuǎn)離邊界的時候終止,此時,當(dāng)前的近似最優(yōu)解即為所求無約束問題的近似最優(yōu)解。

本法的具體方法如下:

前兩年，有關(guān)方面組織編寫出版的《中國當(dāng)代雜文家》和《走近雜文家》兩書，讓我忝列其中，還鼓勵我參評“首屆全國魯迅雜文獎”，并獲得金獎，這是對我這個“創(chuàng)作勞?！钡囊环N獎賞，對此我心存感激。

Step1 從任意一點(diǎn)x0出發(fā),將該點(diǎn)作為當(dāng)前近似最優(yōu)解,相應(yīng)的函數(shù)值作為當(dāng)前的近似最優(yōu)值,給定一個半徑r0。

Step2 以x0為圓心,r0為半徑作圓,用Apollonius填充算法求目標(biāo)函數(shù)在該圓上的全局最優(yōu)解。

Step3 判斷該最優(yōu)解是否落在該圓域的邊界上,若沒有落在邊界上,則由于目標(biāo)函數(shù)為凸函數(shù),所以該最優(yōu)解必為目標(biāo)函數(shù)的無約束最優(yōu)解,因而停止計(jì)算;若落在邊界上(若非?？拷吔?也認(rèn)為是落在邊界上了),則以該最優(yōu)解為新的圓心x0,仍以r0為半徑,轉(zhuǎn)Step2。

關(guān)于本算法的收斂性說明如下。

首先,本文所涉及的目標(biāo)函數(shù)應(yīng)該是連續(xù)可微凸函數(shù),該函數(shù)的最優(yōu)解應(yīng)該是存在的,也就是說函數(shù)在整個區(qū)域上是有下界的,而在算法中每次迭代所得到的近似最優(yōu)解xn處的最優(yōu)值f(xn)是單調(diào)遞減的,即滿足:

故依單調(diào)有界原理知其必收斂。

其次,由于本算法求得的最終的最優(yōu)解必位于某圓域內(nèi)部,且是該圓域內(nèi)部的全局最優(yōu)解,而所論目標(biāo)函數(shù)是凸函數(shù),從而在圓域外部必沒有目標(biāo)函數(shù)的最優(yōu)解,因此該近似最優(yōu)解點(diǎn)列的極限點(diǎn)必為目標(biāo)函數(shù)的最優(yōu)解。

4 數(shù)值算例

下面是利用本法求解的非線性優(yōu)化問題的數(shù)值實(shí)驗(yàn)結(jié)果。

解:顯然這是一個單峰函數(shù),搜索過程見圖2。搜索過程中,從左下角第一個圓開始,逐步經(jīng)過若干個圓域的搜索,最終落到坐標(biāo)系第一象限,在精確解的周圍又進(jìn)行了更為密集的,也就是更為精確的搜索。最后一個黑點(diǎn)即為精確最優(yōu)解的位置,可以看出,真正搜過的區(qū)域并不是很大。

本例精確解為(x*,y*)=(8,12), 最優(yōu)值為f*=0。經(jīng)本法搜索的結(jié)果為:(x*,y*)=(8.001 9,11.999 6),最小值為f*=3.883 3×10-6。

例2 圓函數(shù)：

minf(x,y)=x2+2y2+4x+4

解:本例精確解為(x*,y*)=(-2,0),最小值為f*=0。經(jīng)本法搜索的結(jié)果為: (x*,y*)=(-1.999 025,3.527 198×10-4),最小值為f*=1.198 969×10-6。圖3為本例搜索過程圖。通過圖3可看出,本例大面積的區(qū)域被迅速地刪除,只搜索了很少一部分區(qū)域就找到了最優(yōu)解。搜索路徑為一弧線。

例3 香蕉函數(shù)：

minf(x,y)=(x-y)2+100(y-1)2

解:本例函數(shù)是一個具有槽狀平底的單峰函數(shù),一般優(yōu)化方法不容易得到精度較高的最優(yōu)解。圖4為本例搜索過程圖。從圖4可看出：只搜索了很少一部分區(qū)域就得到了精度相當(dāng)高的最優(yōu)解；在奔向槽底時搜索速度較快,而在槽底時則搜索的速度較慢,搜索區(qū)域較大,但總體上搜索過的區(qū)域并不是很大。本例精確解為(x*,y*)=(1,1),最小值為f*=0。經(jīng)本法搜索的結(jié)果為(x*,y*)=(1.008 48,0.997 65),最小值為f*=6.690 235×10-4。

5 結(jié) 論

本文將經(jīng)典的成功-失敗法與新的Apollonius填充算法相結(jié)合,獲得一種新的無約束最優(yōu)化方法,該方法將成功-失敗法的應(yīng)用范圍由僅適用于一維無約束非線性凸函數(shù)的優(yōu)化問題推廣到二維無約束非線性凸函數(shù)的優(yōu)化問題。同時也使Apollonius填充算法在無約束非線性凸函數(shù)優(yōu)化問題中得到應(yīng)用。數(shù)值實(shí)驗(yàn)表明,本法對較為復(fù)雜的非線性凸函數(shù)是有效的;搜索路徑是清晰可見的。本法的局限性在于這種方法只能應(yīng)用于二維問題,無法進(jìn)一步推廣到更高維數(shù)的優(yōu)化問題。

[1]錢富才, 黃姣茹, 秦新強(qiáng). 基于魯棒優(yōu)化的系統(tǒng)辨識算法研究 [J].自動化學(xué)報, 2013, 40(5): 988-993. Qian Fucai, Huang Jiaoru, Qin Xinqiang. Research on algorithm for system identification based on robust optimization [J].Acta Automatic Sinica, 2013, 40(5): 988 -993.

[2]錢富才, 朱少平, 劉丁. 噪聲未知的LQG控制問題與研究 [J].控制理論與應(yīng)用, 2010, 27(8): 1017-1022. Qian Fucai, Zhu Shaoping, Liu Ding. On LOG problems with unknown noises [J].Control Theory & Applications, 2010, 27(8): 1017-1022.

[3]莫國端, 劉開第. 函數(shù)逼近論方法 [M].北京: 科學(xué)出版社, 2003.

[4]陳予恕, 唐云, 陸啟超，等.非線性動力學(xué)中的現(xiàn)代分析方法 [M].北京: 科學(xué)出版社, 2000.

[5]張光澄, 王文娟, 韓慧磊, 等. 非線性最優(yōu)化計(jì)算方法 [M].北京: 高等教育出版社, 2005.

[6]王竹榮，楊波，呂興朝，等. 一種改進(jìn)的量子遺傳算法研究[J].西安理工大學(xué)學(xué)報，2012，28(2)：145-151. Wang Zhurong, Yang Bo, Lü Xingchao, et al. An inproved quantum genetic algorithm[J].Journal of Xi’an University of Technology, 2012,28(2):145-151.

[7]Dorigo M, Stutzle T. Ant colony optimization [M].London: MIT Press, 2004.

[8]陳開周. 最優(yōu)化計(jì)算方法 [M].西安: 西安電子科技大學(xué)出版社, 1985.

[9]肯尼思·法爾科內(nèi). 分形幾何——數(shù)學(xué)基礎(chǔ)及其應(yīng)用 [M]. 曾文曲，劉世耀，戴連貴，等，譯. 沈陽: 東北大學(xué)出版社, 1991.

[10]宋巨龍, 林椹尠, 宋國鄉(xiāng). Apollonius填充在CAD中的應(yīng)用 [J].計(jì)算機(jī)應(yīng)用, 2005, 25(5): 1108-1109. Song Julong, Lin Zhenxian, Song Guoxiang. Application of Apollonius fill in CAD [J].Computation Application, 2005, 25(5): 1108-1109.

[11]Song Julong, He Xiangjian, Lin Zhenxian. Global optimization under nonlinear constraints based on Apollonius fill [C]∥Third International Conference on Natural Cpmputation V5, Los Almitos, 2007: 39-45.

(責(zé)任編輯 周蓓)

An innovation hybrid algorithm on unconstrained optimization problems

SONG Julong1,QIAN Fucai2,LIANG Jinjin1

(1.Faculty of Science, Xi’an Shiyou University, Xi’an 710065, China; 2.Faculty of Automatization and Information Engineering, Xi’an University of Technology, Xi’an 710048, China)

Combing one dimensional research method—Success-Failure method with novel Apollonius fill algorithm, gives a new kind of algorithm of unconstrained optimization method on the plane. The new algorithm has extended Success-Failure method to the plane. At the same time, the scope of application of Apollonius fill algorithm is extended from constrained optimization problems to unconstrained problems. Numerical experiment results show that this algorithm is suitable for complicated nonlinear differentiable convex function. If the calculation time is not highly required, the algorithm can be applied to any complicated nonlinear differentiable convex function. Whereby indicating that this algorithm is of the highly practical application value.

Apollonius fill; Success-Failure method; nonlinear optimization; algorithm

1006-4710(2015)04-0460-04

2015-03-10

國家自然科學(xué)基金資助項(xiàng)目(61273127,61304204);高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(2011611 8110008)。

宋巨龍,男,教授,研究方向?yàn)樽顑?yōu)化、數(shù)值計(jì)算。E-mail:sjlong@xsyu.edu.cn。

O151.21

A