DIRECT優(yōu)化算法計算機仿真研究1

安華萍，李文靜

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

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

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

1 DIRECT算法

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

圖1 計算Lipschitz下限值示意圖

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

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

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

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

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

多維DIRECT具體算法步驟為

③按文獻［2］所述方法細分超立方體，從超立方體處采樣并對超立方體進行更小的子超立方體細分.更新為新采樣點個數(shù)；

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

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

2 基于元模型的DIRECT算法

2.1 識別最優(yōu)域

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

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

②求最佳點與非最佳點之間的歐氏距離，對非最佳點集進行排序；從集合當前位置算出點的坐標值，計算其與前一點間的擴展區(qū)域；

2.2 基于元模型的DIRECT算法

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

①按照原DIRECT算法進行采樣；

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

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

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

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

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

圖2 基于元模型的DIRECT算法

3 數(shù)值分析

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

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

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

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

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

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

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

4 結(jié)語

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