安華萍，李文靜

（1.河源職業(yè)技術(shù)學(xué)院 電子與信息工程學(xué)院，廣東 河源 517000；2.許昌學(xué)院 機(jī)電工程學(xué)院，河南 許昌 461000）

細(xì)分矩形方法（DIviding RECTangles，DIRECT）作為一種全局優(yōu)化算法，由Donald R.Jones在1993年提出，它可以收斂并搜索到全局最佳點(diǎn)［1］.DIRECT算法將定義域當(dāng)作一個(gè)維超矩形，并對(duì)其進(jìn)行不斷細(xì)分，然后根據(jù)每次迭代采樣點(diǎn)函數(shù)估值和細(xì)分情況決定搜索區(qū)域，直至搜索到全局最優(yōu)解，因此非常適合于黑箱函數(shù)的優(yōu)化仿真.

然而，DIRECT算法需在定義域內(nèi)多次采樣才能保證搜索到全局最優(yōu)解，其函數(shù)估值次數(shù)要比其它方法大的多，因此仿真過(guò)程需要消耗昂貴的計(jì)算機(jī)資源.如果能利用搜索過(guò)程中產(chǎn)生的采樣點(diǎn)來(lái)構(gòu)建精確的代理模型以替代復(fù)雜的源模型進(jìn)行優(yōu)化，那么就能大大減少源模型的迭代仿真次數(shù)，縮短優(yōu)化時(shí)間，提高算法收斂速度，從而節(jié)省寶貴的計(jì)算機(jī)資源.基于此，本文提出一種新的DIRECT算法，通過(guò)對(duì)優(yōu)化迭代過(guò)程中產(chǎn)生采樣點(diǎn)的數(shù)據(jù)分析，構(gòu)建比較精確的元模型，從而達(dá)到提高收斂速度的目的.

1 DIRECT算法

DIRECT方法是針對(duì)Lipschitz算法的不足而提出的，Lipschitz算法由于在搜索時(shí)必須取較大的常數(shù)而導(dǎo)致收斂速度緩慢.對(duì)于一個(gè)定義域?yàn)閰^(qū)間的函數(shù)（見(jiàn)圖1），若搜索函數(shù)全局最小值，Lipschitz方法是假設(shè)存在一Lipschitz常數(shù)（此假設(shè)適用任意端點(diǎn)可估值閉區(qū)間），滿足式：

圖1 計(jì)算Lipschitz下限值示意圖

式（3）作為L(zhǎng)ipschitz算法的核心要素，其算法步驟首先從函數(shù)端點(diǎn)和搜索，然后估算x1=X( a, b, f, K)函數(shù)值，因此將設(shè)計(jì)空間分為，然后選擇擁有最小值的區(qū)間進(jìn)行下一步搜索，估算值，此時(shí)將設(shè)計(jì)空間分為三個(gè)區(qū)間，依次類推，每次迭代過(guò)程中的采樣點(diǎn)均在分段近似函數(shù)最小值位置，因而可以不斷逼近函數(shù)，直至滿足終止標(biāo)準(zhǔn).這種算法的缺陷在于：（1）Lipschitz算法強(qiáng)調(diào)全局搜索，從而導(dǎo)致收斂速度緩慢；（2）在初始化過(guò)程中對(duì)函數(shù)端點(diǎn)和估算，尤其是擴(kuò)展到維時(shí)需估算搜索空間的個(gè)頂點(diǎn)，因而進(jìn)行優(yōu)化過(guò)程中算法較復(fù)雜.

為了克服Lipschitz算法缺點(diǎn)，文獻(xiàn)［1］通過(guò)改進(jìn)設(shè)計(jì)空間的分割方法提出DIRECT算法.它著重強(qiáng)調(diào)對(duì)中心點(diǎn)而不是搜索空間的個(gè)頂點(diǎn)進(jìn)行函數(shù)估值，用中心點(diǎn)區(qū)間，令式（1）中參數(shù)值為，則應(yīng)滿足式：

可以看出，其值只與區(qū)間中心點(diǎn)函數(shù)值有關(guān).DIRECT算法則把迭代過(guò)程采樣方式變?yōu)橹行狞c(diǎn)采樣，并對(duì)所有潛在優(yōu)化區(qū)域進(jìn)行采樣，其算法步驟為：

對(duì)于多變量?jī)?yōu)化問(wèn)題，則需要把一維DIRECT算法擴(kuò)展至多維，這樣搜索空間則轉(zhuǎn)化為維超立方體單元，在搜索過(guò)程中，搜索空間被細(xì)分為更小的超立方體單元，因此，擴(kuò)展過(guò)程中需要解決的關(guān)鍵問(wèn)題：（1）如何細(xì)分這些超立方體.文獻(xiàn)［2］指出可以任意選擇一維將超立方體均分，其采樣方式為圍繞中心點(diǎn)上下左右進(jìn)行，空心點(diǎn)為新的采樣點(diǎn)；（2）如何使每個(gè)子超立方體單元均能在中心被采樣，其詳細(xì)步驟見(jiàn)文獻(xiàn)［3］.DIRECT算法首先在同一維度上識(shí)別潛在最佳域.文獻(xiàn)［4］指出將一超立方體細(xì)分為個(gè)超立方體單元，設(shè) 為第個(gè)單元中心點(diǎn)，為中心點(diǎn)與頂點(diǎn)之間距離，若有得超立方體滿足

則稱其為潛在最佳超立方體.

多維DIRECT具體算法步驟為

③按文獻(xiàn)［2］所述方法細(xì)分超立方體，從超立方體處采樣并對(duì)超立方體進(jìn)行更小的子超立方體細(xì)分.更新為新采樣點(diǎn)個(gè)數(shù)；

但是，在設(shè)計(jì)域內(nèi)DIRECT算法需要多次采樣，才能保證搜索到全局最佳點(diǎn)，特別是優(yōu)化后期，采樣點(diǎn)會(huì)越來(lái)越多，而且這些點(diǎn)為無(wú)效點(diǎn)，這樣造成收斂速度愈加緩慢.況且在實(shí)際優(yōu)化中，目標(biāo)模型一般較復(fù)雜，這樣優(yōu)化算法往往很難被接受.

實(shí)際上，在最佳點(diǎn)域內(nèi)，DIRECT算法假設(shè)目標(biāo)函數(shù)是連續(xù)的，所以，可以利用最佳點(diǎn)域內(nèi)的采樣點(diǎn)來(lái)構(gòu)造精確的近似模型，這樣，即可加快算法收斂速度.元模型作為代理模型（Surrogate），利用最小二乘回歸技術(shù)來(lái)實(shí)現(xiàn)二階多項(xiàng)式模型的擬合，可以通過(guò)實(shí)驗(yàn)產(chǎn)生的采樣點(diǎn)來(lái)構(gòu)造與源模型相近的數(shù)學(xué)模型代替源模型進(jìn)行仿真優(yōu)化分析，因而能節(jié)約計(jì)算資源，降低計(jì)算量.

2 基于元模型的DIRECT算法

2.1 識(shí)別最優(yōu)域

直接使用DIRECT算法產(chǎn)生的樣本點(diǎn)構(gòu)造元模型顯然是不合適的，因?yàn)樵O(shè)計(jì)域內(nèi)大量采樣點(diǎn)會(huì)導(dǎo)致元模型徑向基函數(shù)系數(shù)矩陣過(guò)于龐大.另外，采樣點(diǎn)分布不均也不利于構(gòu)造精確的模型.通過(guò)仿真分析可知，采樣點(diǎn)一般聚集在局部最佳點(diǎn)附近.因此，要構(gòu)造理想的元模型，就必須識(shí)別出包含當(dāng)前最佳點(diǎn)的最優(yōu)域.定義超立方體區(qū)域密度

①根據(jù)式（9）求整個(gè)定義域內(nèi)平均域密度 ，找出函數(shù)值最小的當(dāng)前采樣點(diǎn)，即為當(dāng)前最佳點(diǎn)；

②求最佳點(diǎn)與非最佳點(diǎn)之間的歐氏距離，對(duì)非最佳點(diǎn)集進(jìn)行排序；從集合當(dāng)前位置算出點(diǎn)的坐標(biāo)值，計(jì)算其與前一點(diǎn)間的擴(kuò)展區(qū)域；

2.2 基于元模型的DIRECT算法

在DIRECT算法中，利用當(dāng)前采樣點(diǎn)來(lái)構(gòu)造精確的元模型，從而加快收斂速度，其具體步驟為

①按照原DIRECT算法進(jìn)行采樣；

②按式（8）識(shí)別潛在最佳超立方體，其中心點(diǎn)即為采樣點(diǎn)，對(duì)該中心點(diǎn)進(jìn)行函數(shù)估值；

③按2.1識(shí)別最優(yōu)域；

④收集最優(yōu)域內(nèi)采樣點(diǎn)，構(gòu)建元模型；

⑤利用相關(guān)函數(shù)搜索最佳點(diǎn)，并進(jìn)行函數(shù)估值，若該值小于所有采樣點(diǎn)的函數(shù)值，則該值為當(dāng)前最優(yōu)值；

⑥判斷是否收斂，若不滿足轉(zhuǎn)向步（2），否則退出循環(huán).收斂條件為：當(dāng)前最優(yōu)值與預(yù)設(shè)值的絕對(duì)或相對(duì)誤差小于（為設(shè)定極小值），或三次迭代最優(yōu)值之差小于，或超出預(yù)設(shè)估算值次數(shù).其流程圖見(jiàn)圖2.

圖2 基于元模型的DIRECT算法

3 數(shù)值分析

3.1 布蘭（Branin）函數(shù)

對(duì)比結(jié)果見(jiàn)表1，其中，orig表示原DIRECT算法，PRS［5］、RBF［6］、SVR［7］、KRIG［8］、MARS［8］表示基于不同元模型的DIRECT算法.

表1 布蘭函數(shù)優(yōu)化結(jié)果對(duì)比

3.2 六駝峰（six-hump camel-back）函數(shù)

改進(jìn)前DIRECT與改進(jìn)后的DIRECT迭代優(yōu)化對(duì)比結(jié)果見(jiàn)表2所示.其中，orig表示改進(jìn)前DIRECT算法，PRS、RBF、SVR、KRIG、MARS表示基于不同元模型的改進(jìn)DIRECT算法.

表2 六駝峰函數(shù)優(yōu)化結(jié)果對(duì)比

從表1、表2可知，相比標(biāo)準(zhǔn)DIRECT算法，基于元模型的改進(jìn)DIRECT算法更能快速地搜索至全局最優(yōu)點(diǎn)，尤其是基于RBF元模型的DIRECT算法至少比原DIRECT算法減少三分之二，效果非常明顯，這對(duì)于節(jié)約計(jì)算機(jī)資源，提高仿真優(yōu)化效率具有重要意義.

4 結(jié)語(yǔ)

DIRECT算法由于函數(shù)估值次數(shù)多，所以會(huì)造成收斂速度緩慢，耗費(fèi)較多的計(jì)算機(jī)資源，文章利用采樣點(diǎn)來(lái)構(gòu)造元模型，并搜索最佳點(diǎn)，從而加快該算法的收斂速度.通過(guò)上述函數(shù)及工程實(shí)例分析測(cè)試，表明該算法科學(xué)合理，效果良好，可以說(shuō)，這是一種值得考慮并具有很大研究前景的方法，對(duì)于優(yōu)化設(shè)計(jì)具有很重要的研究?jī)r(jià)值.