徑向基函數(shù)插值中的一種新的重啟動策略

齊 靜

(重慶師范大學(xué)涉外商貿(mào)學(xué)院 數(shù)學(xué)與計算機(jī)學(xué)院,重慶 合川 401520)

?

徑向基函數(shù)插值中的一種新的重啟動策略

齊 靜

(重慶師范大學(xué)涉外商貿(mào)學(xué)院 數(shù)學(xué)與計算機(jī)學(xué)院,重慶 合川 401520)

針對徑向基函數(shù)插值方法,提出了一種新的重啟動策略來改進(jìn)徑向基的優(yōu)化效果.在采用SLHD(symmetryLatinHypercubedesign,對稱拉丁超立方設(shè)計)方法換新的初始點對優(yōu)化效果沒有太大改進(jìn)的時候,提出了一種更換徑向基函數(shù)的重啟動策略,可以取得更好的優(yōu)化效果.通過數(shù)值算例說明了采用這種新的重啟動策略在迭代次數(shù)上的優(yōu)越性.

徑向基函數(shù);全局最優(yōu)化;響應(yīng)面模型;重啟動策略;對稱拉丁超立方設(shè)計

1 前言及預(yù)備知識

其中：f是一個確定性的連續(xù)函數(shù),x∈Rd,‖x-xi‖表示x與中心點xi之間的歐氏距離,λi∈R,i=1,2,…,n.b∈Rd,a∈R.φ就是徑向基函數(shù)，選定一個徑向基函數(shù)φ之后,定義一個n×n的矩陣Φij:=φ(‖xi-xj‖)，i,j=1,2,…,n.

λi,b,a可以從下面的線性方程組中獲得：

其中：

常見的徑向基函數(shù)φ[2]取自于下面的5種：

2 SLHD方法選取初始點

根據(jù)文獻(xiàn)[3]中所介紹的拉丁超立方設(shè)計的矩陣(symmetry Latin Hypercube matrix),矩陣的每一列都是由{1,2,…,n}隨機(jī)生成的.對稱的拉丁超立方具有下列性質(zhì):在一個n×d的對稱拉丁超立方矩陣中,若(a1,a2,…,ad)是矩陣的某一行, 必有n+1-a1,n+1-a2,…，n+1-ad)是這個矩陣的另外一行.

3 徑向基函數(shù)插值的算法步驟

本文采用文獻(xiàn)[4]中的徑向基插值算法的一般步驟.

Step 0：根據(jù)SLHD方法生成n個初始點.

Step 1：計算f(x1),f(x2),…,f(xn).

Step 2：計算minf(xi),medf(xi),maxf(xi).i=1,2,…,n.

令Rl=medf(xi)-minf(xi),Ru=maxf(xi)-medf(xi).若max(Rl,Ru)≥4min(Rl,Ru),則用φ(f(x))來替換f(x)，其中φ(x)[5]如下：

Step 3：構(gòu)建響應(yīng)面模型.根據(jù)給定的初始點x1,x2…,xn,以及它們的函數(shù)值f(x1)，f(x2)，…,f(xn),取定徑向基函數(shù)φ,構(gòu)建徑向基函數(shù)模型sn(x).

φ(‖x-xi‖)+bTx+a.

其中：n0表示初始點的個數(shù)，N表示循環(huán)長度(通常令N=5).

Step 6:下一個迭代點xn+1取自于gn(y)的極小點[7].

其中：ln(y,xi)=0,i=1,2,…,n,ln(y,y)=1.

4 重啟動策略

使用徑向基插值算法在進(jìn)行全局搜索時,算法可能會在某個局部極小點處進(jìn)行較長時間的局部搜索,連續(xù)多次迭代都沒有取得明顯的實質(zhì)性的進(jìn)展,從而導(dǎo)致算法不能準(zhǔn)確定位全局最優(yōu)點.為了解決這個問題,文獻(xiàn)[9]中提出一種使用新的SLHD的重啟動策略.那么受文獻(xiàn)[9]的啟發(fā),本文提出一種使用新的徑向基函數(shù)的重啟動策略.數(shù)值算例1說明了當(dāng)采用文獻(xiàn)[9]的使用新的SLHD策略對算法沒有太大改進(jìn)的時候,使用本文的換用新的徑向基函數(shù)的策略可使算法減少迭代次數(shù),從而快速收斂到全局最優(yōu)點.

5 數(shù)值試驗

例1考慮下面的問題:f(x)=-0.015 8x5+0.391 1x4-3.361 1x3+11.826 9x2-14.199 0x-1,x∈[0.2,1.2].(在此區(qū)間上的最優(yōu)值為(0.898 8,-6.402 3)).

算法在局部極小點0.0000附近進(jìn)行搜索,連續(xù)多次迭代都沒有取得一些明顯的進(jìn)展,所得數(shù)據(jù)如表1所示.

表1 算法在局部極小點0.070 3附近進(jìn)行較長時間的局部搜索
Tab.1 The algorithm near a local minimum point 0.070 3 for a long time local search

n值sn(x)的極小點sn(x)的極小值下一個點x(n+1)x(n+1)的函數(shù)值n值sn(x)的極小點sn(x)的極小值下一個點x(n+1)x(n+1)的函數(shù)值61.0000-6.20310.0571-1.7732191.0000-1.69550.0668-1.002571.0000-6.20360.0106-1.1495201.0000-1.69570.0667-1.000081.0000-6.21230.2296-1.0001211.0000-1.69580.0000-1.000291.0000-6.21940.9485-1.0005221.0000-1.69590.0000-1.0001101.0000-1.69120.2298-1.0000231.0000-1.69610.0000-1.0001111.0000-1.69230.2322-1.0000241.0000-1.69620.0001-1.0000121.0000-1.69300.9331-1.0000251.0000-1.69630.0000-1.0015131.0000-1.69360.0001-1.0000261.0000-1.69630.0000-1.0000141.0000-1.69410.0635-1.0001271.0000-1.69640.0000-1.0000151.0000-1.69450.9761-1.0000281.0000-1.69650.0000-1.0010161.0000-1.69480.0659-1.0015291.0000-1.69660.0000-1.0001171.0000-1.69510.0672-1.0000301.0000-1.69660.0000-1.0000181.0000-1.69530.0659-1.0000?????

分析表1的數(shù)據(jù)可知,算法在局部極小點x=0.000 0附近進(jìn)行搜索,連續(xù)30-6=24(次)迭代都沒有取得明顯的進(jìn)展,當(dāng)沒有改進(jìn)的函數(shù)值的數(shù)量超過一個臨界值(通常將這個臨界值取為30)之后,采用文獻(xiàn)[9]中的更換新的SLHD初始點的重啟動策略.

采用文獻(xiàn)[9]的更換新的SLHD的方法,算法仍然連續(xù)多次迭代都沒有取得明顯的進(jìn)展,所得數(shù)據(jù)如表2所示.

分析表2的數(shù)據(jù)可知,使用文獻(xiàn)[9]的換用新的SLHD的重啟動策略,對算法的迭代情況并沒有太大的改進(jìn).此時可以使用本文的更換徑向基函數(shù)的重啟動策略.

下面使用本文的更換徑向基函數(shù)的重啟動策略,徑向基函數(shù)更換為:Φ(r)=r2log(r).

初始點：(0.235 3,-3.728 9),(1.143 9,-6.166 3),(0.139 4,-2.758 5),(1.027 3,-6.401 6),(0.022 8,-1.317 6),(0.931 4,-6.401 6).

使用本文的更換徑向基函數(shù)的重啟動策略,達(dá)到最優(yōu)值所需迭代的次數(shù)為:11-6=5(次),所得數(shù)據(jù)如表3所示.

分析表3的數(shù)據(jù)可知,使用本文的更換徑向基函數(shù)的重啟動策略,可使算法及時跳出局部極小點,達(dá)到最優(yōu)值所需迭代的次數(shù)為:11-6=5(次).

當(dāng)算法連續(xù)多次迭代都沒有取得明顯進(jìn)展的時候,可以使用本文的換用徑向基函數(shù)的重啟動策略,可使算法達(dá)到最優(yōu)值的迭代次數(shù)減少.

表2 文獻(xiàn)[9]的更換新的SLHD初始點的迭代情況Tab.2 Replace the new SLHD iterative initial point in literature[9]

表3 更換徑向基函數(shù),快速達(dá)到最優(yōu)點Tab.3 Change the radial basis function,reach the most advantages quickly

6 小結(jié)

徑向基函數(shù)具有計算格式簡單、計算工作量小[10]等特點，在全局優(yōu)化問題方面有著廣泛的應(yīng)用.利用徑向基函數(shù)插值解決優(yōu)化問題時,當(dāng)使用文獻(xiàn)[9]的換用新的SLHD的重啟動策略對算法的優(yōu)化效果并沒有太大改進(jìn)的時候,可以使用本文的換用新的徑向基函數(shù)的重啟動策略,可使算法及時跳出局部極小點,減少迭代的次數(shù),加快收斂到最優(yōu)點.

[1] HOLMSTR?M K.An adaptive radial basis algorithm (ARBF) for expensive black-box global optimization[J].Journal of Global Optimization,2008,41:447-464.

[2] REGIS R G,SHOEMAKER C A.A quasi-multistart framework for global optimization of expensive function using response surface models[J].Journal of Global Optimization,2013,56:1719-1753.

[3] YE K Q,LI W,SUDJIANTO A.Algorithmic construction of optimal symmetric latin hypercube designs[J].Joumal of Statistial Planning and Inference,2000,90(1):145-159.

[4] 劉雨,劉廣磊,姜自武,等.徑向基函數(shù)插值配置點的自適應(yīng)選取算法[J].應(yīng)用數(shù)學(xué)進(jìn)展,2016,5(1):8-14.

[5] 齊靜.黑箱函數(shù)優(yōu)化問題中的響應(yīng)面優(yōu)化方法[J].重慶工商大學(xué)學(xué)報(自然科學(xué)版)，2015,32(12):27-30.

[6] REGIS R G,SHOEMAKER C A.Constrained Global Optimization of Expensive Black Box Function Using Radial Basis Function[J].Journal of Global Optimization,2005,31:153-171.

[7] 吳宗敏.函數(shù)的徑向基表示[J].數(shù)學(xué)進(jìn)展,1998,27(3):202-208.

[8] BJ?RKMAN M,HOLMSTR?M K.Global optimization of costly nonconvex functions using radial basis functions [J].Optimization and Engineering， 2000,4(1):373-397.

[9] REGIS R G,SHOEMAKER C A.Improved strategies for radial basis function methods for global optimization[J].Journal of Global Optimization,2007,37:113-135.

[10] 吳宗敏.散亂數(shù)據(jù)擬合的模型、方法和理論[M].北京：科學(xué)出版社,2007:82-83.

責(zé)任編輯：時 凌

A New Type of Restarting Strategy for Radial
Basis Function Interpolation

QI Jing

(School of Mathematics and Computer Science,Chongqing Normal University Foreign Trade and Business College,Hechuan 401520,China)

We propose a new restarting strategy to improve the optimization effect of the radial basis function interpolation method.When there is little improvement by using new initial points in the SLHD (symmetry Latin Hypercube design) method,we propose a restarting strategy of replacing the radial basis function which yields better numerical optimization performance. Then we illustrate the advantages of restarting strategy by some numerical examples.

radial basis function; global optimization; response surface model; restarting strategy;symmetry Latin Hypercube design

2016-07-16.

齊靜(1990- )，女，碩士，主要從事全局最優(yōu)化方法的研究.

1008-8423(2016)04-0398-04

10.13501/j.cnki.42-1569/n.2016.12.009

O241.6

A