求解全局優(yōu)化問(wèn)題的兩階段模式搜索算法

孫莉，王傳偉，潘浩

1.山東農(nóng)業(yè)大學(xué)信息科學(xué)與工程學(xué)院，山東泰安2710182.山東農(nóng)業(yè)大學(xué)農(nóng)業(yè)資源與環(huán)境博士后科研流動(dòng)站，山東泰安271018

?

求解全局優(yōu)化問(wèn)題的兩階段模式搜索算法

孫莉1，2，王傳偉1，潘浩1

1.山東農(nóng)業(yè)大學(xué)信息科學(xué)與工程學(xué)院，山東泰安271018
2.山東農(nóng)業(yè)大學(xué)農(nóng)業(yè)資源與環(huán)境博士后科研流動(dòng)站，山東泰安271018

摘要：將Matlab中全局優(yōu)化工具箱中的模式搜索求解器與割峰函數(shù)結(jié)合，提出一個(gè)兩階段模式搜索算法。首先通過(guò)模式搜索求解器求解包含多個(gè)極小值的優(yōu)化問(wèn)題，返回結(jié)果后，在當(dāng)前迭代點(diǎn)處定義割峰函數(shù)，繼而采用模式搜索求解器進(jìn)一步極小化輔助函數(shù)尋找比當(dāng)前結(jié)果更好的下降點(diǎn)。該算法簡(jiǎn)單易行，數(shù)值結(jié)果表明新算法提高了模式搜索求解器獲得全局解的效率。

關(guān)鍵詞：全局優(yōu)化工具箱；模式搜索求解器；割峰函數(shù)；全局優(yōu)化問(wèn)題

1　引言

全局優(yōu)化問(wèn)題中有多個(gè)局部極小點(diǎn)，因此不能簡(jiǎn)單用通常意義下的局部極小化方法求解。目前Matlab全局優(yōu)化工具箱中設(shè)計(jì)了5個(gè)求解器處理這類(lèi)問(wèn)題，包含全局搜索和多初始點(diǎn)求解器，遺傳算法求解器，多目標(biāo)遺傳算法求解器，模式搜索求解器和模擬退火求解器。其中模式搜索求解器（patternsearch）的求解過(guò)程無(wú)需目標(biāo)函數(shù)的梯度信息，適合于求解工程中常見(jiàn)的目標(biāo)函數(shù)不可微甚至不連續(xù)的具體問(wèn)題。另一方面，多初始點(diǎn)和模式搜索求解器易于并行［1，2］，使得這類(lèi)算法更加適合于求解大規(guī)模的優(yōu)化問(wèn)題。由于至今仍沒(méi)有很好的全局性判斷準(zhǔn)則，因此提高現(xiàn)有算法獲知全局最優(yōu)解的效率意義重大。

本文考慮如下界約束全局最優(yōu)化問(wèn)題，

經(jīng)測(cè)試，模式搜索求解器在一些算例中被局部極小值所限，未能在全局搜尋更好的解。本文提出的兩階段模式搜索算法，在模式搜索終止前，于返回解處定義割峰函數(shù)，隨后再次利用

論文結(jié)構(gòu)如下：第二部分給出割峰函數(shù)的定義，并提出兩階段模式搜索算法，第三部分通過(guò)數(shù)值測(cè)試驗(yàn)證新算法的有效性。

2　兩階段模式搜索算法

2.1割峰函數(shù)

下面給出與本文算法相關(guān)的定義，文獻(xiàn)［3］中的割峰函數(shù)定義如下，

定義1（割峰函數(shù)）

定義2（選擇函數(shù)）

2.2新的割峰函數(shù)

考慮到具體應(yīng)用中，迫切需要簡(jiǎn)單、易操作的全局優(yōu)化算法，我們對(duì)文獻(xiàn)［3］中的割峰函數(shù)法進(jìn)行改進(jìn)，將其與Matlab全局優(yōu)化包中的模式搜索求解器結(jié)合起來(lái)。

本文中的割峰函數(shù)定義如下：

圖1給出了與本文密切相關(guān)的三個(gè)函數(shù)：目標(biāo)函數(shù)（l）、割峰函數(shù)（w）、選擇函數(shù)（F）的關(guān)系。圖中目標(biāo)函數(shù)為，割峰函數(shù)

圖1　選擇函數(shù)、目標(biāo)函數(shù)和割峰函數(shù)Fig.1 Relation of the choice function, objective function and cut peak function

2.3兩階段模式搜索算法

步0選取初始點(diǎn)x0，置k： =0。

步1（第一階段）

以xk為初始點(diǎn)，利用模式搜索求解器獲得問(wèn)題（1）的局部極小點(diǎn)

步2（第二階段）

3　數(shù)值測(cè)試

這一部分給出方向割峰函數(shù)算法的數(shù)值試驗(yàn)結(jié)果。我們引用全局優(yōu)化問(wèn)題中的4個(gè)經(jīng)典算例進(jìn)行測(cè)試，同一算例采用相同的初始點(diǎn)，分別通過(guò)MATLAB 2010a中的patternsearch solver（PS）以及兩階段模式搜索算法求解（TSPS）求解。

下列表格中的IT表示總體迭代次數(shù)，IF表示目標(biāo)函數(shù)值的計(jì)算次數(shù)，IW表示割峰次數(shù)，F(xiàn)P表示最優(yōu)點(diǎn)，F(xiàn)F表示最優(yōu)解處的函數(shù)值。

算例1 Six-hump Camel-back Function

表1　算例1的測(cè)試結(jié)果Table 1 Numerical results of problem 1

算例2 Shubert I Function（n=2）

表2　算例2的測(cè)試結(jié)果Table 2 Numerical results of problem 2

算例3 Shubert II Function（n=2）

表3　算例3的測(cè)試結(jié)果Table 3 Numerical results of problem 3

算例4 Shubert III Function（n=2）

數(shù)值結(jié)果表明，在局部最優(yōu)點(diǎn)處定義的割峰函數(shù)可有效判斷當(dāng)前點(diǎn)是否為全局最優(yōu)解，它的引入提高了原有模式搜索求解器獲知全局最優(yōu)解的效率。

4　結(jié)論

本文提出的兩階段模式搜索算法，原理簡(jiǎn)單，易操作，為工程應(yīng)用中的全局優(yōu)化問(wèn)題提供了新的有效方法。下一步我們將針對(duì)具體問(wèn)題的特性，通過(guò)調(diào)整割峰函數(shù)的形式，提高優(yōu)化問(wèn)題的求解精度。

參考文獻(xiàn)

［1］黃利國(guó)，孫莉，韓叢英.整體異步的并行轉(zhuǎn)換算法［J］.計(jì)算機(jī)工程，2008，34（21）：54-58

［2］黃利國(guó)，韓叢英，孫莉.基于變量轉(zhuǎn)換的并行優(yōu)化算法［J］.計(jì)算機(jī)工程，2010，36（23）：34-35

［3］Wang YC，F(xiàn)ang WW，Wu TJ. A cut-peak function method for global optimization［J］. J. Comput. Appli. Math，2009，230：135-142

［4］Yang YJ，Shang YL. A new filled function method for unconstrained global optimization［J］. Appli. Math. Comput，2006，173（1）：510-512

［5］Yao Y. Dynamic tunneling algorithm for global optimization［J］. IEEE Trans. System Man Cybernet，1989，19（5）：1222-1230

［6］孫莉，賀國(guó)平，房亮.基于求解大規(guī)模界約束問(wèn)題的三種有效集識(shí)別策略的比較［J］.數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用，2009，30（1）：41-47

［7］張煜東，吳樂(lè)南，王水花.基于遺傳算法與模式搜索的混合優(yōu)化算法［J］.南京信息工程大學(xué)學(xué)報(bào)：自然科學(xué)版，2012（1）：34-39

The Method of Two Stage Pattern Search for Bound Constrained Global Optimization

SUN Li1，2，WANG Chuan-wei1，PAN Hao1

1. College of Information Science and Engineering/Shandong Agricultural University，Taian 271018，China
2. The Post-doctorate Research Station of Agricultural Resources and Environment/Shandong Agricultural University，Taian 271018，China

Abstract：We presented a two stage pattern search method，which combined the cut-peak function and the pattern search solver in Matlab. A simple cut-peak function and choice function were defined at solution returned by pattern search solver. By minimizing the choice function，a global descent of the original objective function was assured. Since the pattern search method did not require the gradient of the choice function，smoothing technique was not employed. The new algorithm was simple to implement and numerical results indicated that the new method improved the efficiency of finding the global minimization.

Keywords：Global optimization toolbox；pattern search solver；cut peak function；global optimization

中圖法分類(lèi)號(hào)：O221；TP312

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1000-2324（2016）03-0465-04

收稿日期：2014-02-23修回日期：2014-03-05

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（10901094，11301307）；山東省優(yōu)秀中青年科學(xué)家科研獎(jiǎng)勵(lì)基金資助項(xiàng)目（BF2011SF024，BF2012SF025）

作者簡(jiǎn)介：孫莉（1980-），女，泰安人，副教授，博士，研究方向?yàn)樽顑?yōu)化算法與理論. E-mail：sunlishi@hotmail.com