基于均勻設(shè)計(jì)與Ｐｏｗｅｌｌ算法的全局最優(yōu)化算法及并行實(shí)現(xiàn)

摘要：復(fù)雜函數(shù)的全局最優(yōu)化問題是在求解各種復(fù)雜工程與科學(xué)計(jì)算問題中提煉出來的亟待解決的計(jì)算問題，均勻設(shè)計(jì)具有讓試驗(yàn)點(diǎn)在高維空間內(nèi)均勻分散的特點(diǎn)，而Powell算法具有很好的求解局部最優(yōu)解的能力，將兩種方法進(jìn)行有效改進(jìn)后使之相結(jié)合，設(shè)計(jì)出并行全局最優(yōu)化算法。通過經(jīng)典的全局最優(yōu)化函數(shù)對(duì)算法進(jìn)行了比較測(cè)試，發(fā)現(xiàn)該算法具有比以前的算法更好的尋優(yōu)能力，并對(duì)算法時(shí)間、空間復(fù)雜度以及并行性進(jìn)行分析和測(cè)試。基于均勻設(shè)計(jì)與Powell算法的全局最優(yōu)化并行算法具有尋優(yōu)能力強(qiáng)，時(shí)間開銷與問題因素個(gè)數(shù)的平方和布點(diǎn)數(shù)成線性復(fù)雜度，空間開銷與因素個(gè)數(shù)和布點(diǎn)數(shù)成線性復(fù)雜度，并行效率好的特點(diǎn)。 

關(guān)鍵詞：并行計(jì)算；均勻設(shè)計(jì)；Powell算法；全局最優(yōu)化

中圖分類號(hào)：TP301．6文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2007)05－0169－04

0引言

最優(yōu)化理論方法是應(yīng)用數(shù)學(xué)的一門分支，研究決策問題的最佳選擇，構(gòu)造尋找最佳解的計(jì)算方法，探討這些計(jì)算方法的理論性質(zhì)及計(jì)算表現(xiàn)。目前，求解線性規(guī)劃、非線性規(guī)劃、隨機(jī)規(guī)劃、非光滑規(guī)劃、多目標(biāo)規(guī)劃、組合優(yōu)化等各種最優(yōu)化問題的新方法不斷涌現(xiàn)。除了自然科學(xué)的各個(gè)領(lǐng)域之外，在建筑設(shè)計(jì)、金融設(shè)計(jì)、醫(yī)藥設(shè)計(jì)、生產(chǎn)管理、交通運(yùn)輸?shù)戎T多方面均涉及最優(yōu)化的應(yīng)用。隨著高速計(jì)算機(jī)的普及和優(yōu)化方法的不斷進(jìn)步，規(guī)模越來越大的優(yōu)化問題得到解決。

面對(duì)最優(yōu)化問題，目前的困難主要表現(xiàn)在兩個(gè)方面：①目標(biāo)函數(shù)常常多峰，隨著優(yōu)化問題規(guī)模的增大，局部最優(yōu)解的數(shù)目將會(huì)迅速增加，往往得到的是局部最優(yōu)解，而不能得到全局最優(yōu)解。如何有效地跳出局部最優(yōu)點(diǎn)而又不大幅度地增加計(jì)算代價(jià)，是目前的一個(gè)難題。②許多在串行計(jì)算環(huán)境下的最優(yōu)化算法并不適合于并行環(huán)境，并行化難度大。

首先利用均勻設(shè)計(jì)具有使實(shí)驗(yàn)點(diǎn)高維空間均勻分散的特點(diǎn)，與Powell算法結(jié)合，并適當(dāng)改進(jìn)，經(jīng)過經(jīng)典的全局最優(yōu)化函數(shù)測(cè)試發(fā)現(xiàn)它能夠跳出局部最優(yōu)陷阱，從而準(zhǔn)確地找到全局最優(yōu)點(diǎn)。最后，對(duì)算法的時(shí)間空間復(fù)雜度進(jìn)行了測(cè)試，數(shù)據(jù)統(tǒng)計(jì)顯示本文算法時(shí)間復(fù)雜度與計(jì)算問題需要考慮的因素個(gè)數(shù)的二次方和布點(diǎn)數(shù)成線性關(guān)系，空間復(fù)雜度與因素個(gè)數(shù)和布點(diǎn)數(shù)成線性關(guān)系。對(duì)算法進(jìn)行了并行化，經(jīng)測(cè)試得知并行效率很高。該算法具有很好的求解大型優(yōu)化問題的潛力。

1背景介紹

1．1全局最優(yōu)化模型

對(duì)于解決實(shí)際優(yōu)化問題，特別是對(duì)于科學(xué)與工程計(jì)算問題，全局優(yōu)化方法非常重要。全局最優(yōu)化問題可以描述成如下的數(shù)學(xué)模型： 

1．2均勻設(shè)計(jì)

均勻設(shè)計(jì)是20世紀(jì)80 年代，由我國科學(xué)家方開泰和王元開創(chuàng)的一種全新的試驗(yàn)設(shè)計(jì)方法。其思路是讓試驗(yàn)點(diǎn)在試驗(yàn)范圍內(nèi)充分均勻分散，這種從均勻性出發(fā)的設(shè)計(jì)被稱為均勻設(shè)計(jì)。

均勻設(shè)計(jì)主要通過對(duì)均勻設(shè)計(jì)表的設(shè)計(jì)來體現(xiàn)。均勻設(shè)計(jì)表是一種規(guī)格化的表格，是均勻試驗(yàn)設(shè)計(jì)的基本工具。均勻設(shè)計(jì)表有一個(gè)代號(hào)Un(qs)。其中U表示均勻設(shè)計(jì)，s表示因素個(gè)數(shù)，q為試驗(yàn)水平數(shù)，n 表示所作試驗(yàn)次數(shù)。均勻設(shè)計(jì)的最大特點(diǎn)是試驗(yàn)次數(shù)等于最大水平數(shù)，而正交設(shè)計(jì)試驗(yàn)次數(shù)是實(shí)驗(yàn)水平數(shù)的平方，這也是均勻設(shè)計(jì)的優(yōu)勢(shì)。

1．3Powell算法

Powell算法是一種方向集方法，假設(shè)計(jì)算的問題是m因數(shù)，它取m個(gè)m維的共軛向量，并沿每一向量的方向進(jìn)行最優(yōu)值搜索，那么任何一個(gè)m元函數(shù)均可用一維搜索方法求其最優(yōu)值。它專門針對(duì)當(dāng)目標(biāo)函數(shù)特別復(fù)雜，因而沒有辦法掌握目標(biāo)函數(shù)特性的一類優(yōu)化問題，在實(shí)際工程與科學(xué)計(jì)算中十分有用。它的主要計(jì)算步驟如下：

2并行算法的實(shí)現(xiàn)及性能分析

2．1將均勻設(shè)計(jì)思想與Powell算法結(jié)合

均勻設(shè)計(jì)可以根據(jù)均勻設(shè)計(jì)原則在可行域內(nèi)均勻分布優(yōu)化初始點(diǎn)，而Powell算法具有很好的求得局部最優(yōu)值能力。本文將上述兩者結(jié)合起來設(shè)計(jì)尋求模型的全局最優(yōu)解方法。該方法的基本思路如下： 

（1)采用均勻設(shè)計(jì)方法，在優(yōu)化模型的設(shè)計(jì)變量空間內(nèi)均勻分布一系列點(diǎn)，這些點(diǎn)在變量空間內(nèi)均勻分散。 

（2)將可行域內(nèi)的上述系列布點(diǎn)作為Powell優(yōu)化計(jì)算的初始點(diǎn)，通過Powell算法分別從各初始點(diǎn)開始對(duì)模型(1)進(jìn)行優(yōu)化計(jì)算，得到優(yōu)化模型的一系列局部最優(yōu)點(diǎn)和局部最優(yōu)值。

（3) 取所有局部最優(yōu)值中的最優(yōu)值，認(rèn)為在一定程度上獲得了優(yōu)化模型(1)的全局最優(yōu)解。 

顯然，均勻布點(diǎn)數(shù)n越多，所得的結(jié)果越逼近全局最優(yōu)解，但計(jì)算量也會(huì)隨之增加。因此，合理確定布點(diǎn)數(shù)也是值得研究的問題。

2．2并行化

按照算法設(shè)計(jì)中所述基本思路，將初始點(diǎn)平均分配給多個(gè)進(jìn)程，讓這些進(jìn)程并行計(jì)算，最后將結(jié)果匯集到root進(jìn)程0。如此實(shí)現(xiàn)以后通信量少，并行度高。并行化部分代碼如下：

/*確定每個(gè)進(jìn)程需要處理的第一個(gè)初始點(diǎn)Begin_Row和最后一個(gè)初始點(diǎn)End_Row*/

if (PopSize%size!=0)// PopSize為布點(diǎn)數(shù)，size為進(jìn)程數(shù)

{if(myid< PopSize %size) Row_Num = PopSize /size+1;

//Row_Num為分配該進(jìn)程初始點(diǎn)個(gè)數(shù)

else Row_Num = PopSize /size;

if(myid<= PopSize %size)

Begin_Row=myid*( PopSize /size+1);

else Begin_Row = myid*(PopSize /size) +n%size;

}

else

{

Begin_Row =myid*(PopSize /size);

Row_Num = PopSize /size;

}

End_Row=Begin_Row+Row_Num;

//進(jìn)入計(jì)算部分

/*然后將每個(gè)進(jìn)程計(jì)算結(jié)果傳給root進(jìn)程0；root取最優(yōu)值賦給result變量*/

MPI_Reduce(min，result，1，MPI_DOUBLE_PRECISION，MPI_MIN，0，mycomm);

2．3性能分析

(1)時(shí)間與空間復(fù)雜度

(2)并行效率分析

并行實(shí)現(xiàn)以后，各個(gè)計(jì)算過程中進(jìn)程之間不需要數(shù)據(jù)傳輸，所以并行效率比較高。這個(gè)結(jié)論在3.3節(jié)的測(cè)試中得到驗(yàn)證。

3算法測(cè)試

3．1試驗(yàn)環(huán)境

聯(lián)想深騰6800 超級(jí)計(jì)算機(jī)系統(tǒng);

系統(tǒng)結(jié)構(gòu)：COW；

265個(gè)四路節(jié)點(diǎn)機(jī)；

內(nèi)存總?cè)萘?.6 TB，磁盤總?cè)萘?0 TB；

高速連接網(wǎng)絡(luò)QsNet，點(diǎn)對(duì)點(diǎn)通信帶寬大于300 MB，延遲時(shí)間小于7 μs。

3．2尋優(yōu)能力測(cè)試

(1)為測(cè)試該算法的尋找最優(yōu)值的能力，選擇兩個(gè)具有代表性的經(jīng)典全局最優(yōu)化函數(shù)作為測(cè)試的目標(biāo)函數(shù)。其特點(diǎn)是局部極值點(diǎn)非常多，因而全局最優(yōu)值很難準(zhǔn)確找到。最后將本文的計(jì)算結(jié)果與遺傳算法的結(jié)果進(jìn)行了對(duì)比分析。

從圖2中可以看到局部最優(yōu)值點(diǎn)非常多，所以布的點(diǎn)比較多。在實(shí)際工程計(jì)算中，一般應(yīng)該根據(jù)問題的復(fù)雜程度布盡量多的點(diǎn)。從表2可以看出，在上述4個(gè)進(jìn)程中有2個(gè)找到了全局最優(yōu)值點(diǎn)。最終root進(jìn)程0選取結(jié)果為最優(yōu)值點(diǎn)：(0)；最優(yōu)值為：1。

(2)與遺傳算法的比較

從表3和4中可以看出，本文設(shè)計(jì)的算法分別在小數(shù)點(diǎn)后面3位和4位比遺傳算法精確，這顯然不是機(jī)器精度的問題，而主要?dú)w功于Powell算法具有很強(qiáng)的局部尋優(yōu)能力。遺傳算法是一種帶有隨機(jī)性的尋優(yōu)方法，有其很強(qiáng)的跳出局部陷阱的能力，但在局部尋優(yōu)方面卻不十分強(qiáng)。Powell算法在尋找全局最優(yōu)解方面不理想，針對(duì)這一點(diǎn)本文用均勻布點(diǎn)的方法將其化解。

由并行加速比和并行效率可以看出該并行算法并行效率比較高。這個(gè)測(cè)試結(jié)果與2.3節(jié)中算法性能分析的結(jié)論一致。

3．4時(shí)間復(fù)雜度測(cè)試

(1）筆者同樣選擇函數(shù)(6)，問題因素個(gè)數(shù)也即自變量的維數(shù)m從100每次遞加100，每次同樣布211個(gè)點(diǎn)，同樣分配4個(gè)進(jìn)程。時(shí)間空間統(tǒng)計(jì)數(shù)據(jù)見表6，圖形顯示如圖4、5所示。

從(1)和(2)可以總結(jié)出，該算法的時(shí)間復(fù)雜度為O(維數(shù)2×布點(diǎn)數(shù))，空間復(fù)雜度為O(維數(shù)×布點(diǎn)數(shù))。該測(cè)試結(jié)果與2.3節(jié)中的性能分析(2)一致。

4結(jié)束語

本文將均勻設(shè)計(jì)與Powell算法相結(jié)合并進(jìn)行有效改進(jìn)，設(shè)計(jì)基于此的全局最優(yōu)化并行算法，經(jīng)過測(cè)試該全局最優(yōu)化算法尋優(yōu)能力強(qiáng)，時(shí)間復(fù)雜度與計(jì)算問題需要考慮的因素個(gè)數(shù)的二次方和布點(diǎn)數(shù)成線性關(guān)系，空間復(fù)雜度與因素個(gè)數(shù)和布點(diǎn)數(shù)成線性關(guān)系，經(jīng)過并行性測(cè)試該算法并行效率很好。

該方法可適用于各種數(shù)值和非數(shù)值優(yōu)化的科學(xué)計(jì)算問題，如生物信息學(xué)和計(jì)算化學(xué)等領(lǐng)域，也可以用于多種工程計(jì)算方面，具有較為廣泛的應(yīng)用。

由于本算法計(jì)算時(shí)，每個(gè)進(jìn)程只需要部分Uniform矩陣，對(duì)于大規(guī)模優(yōu)化問題，大內(nèi)存的需求可均勻地分布在各個(gè)節(jié)點(diǎn)的CPU上，故算法具有非常好的利用超級(jí)計(jì)算機(jī)求解大型優(yōu)化問題的潛力。

利用本算法的思想，也可用于均勻設(shè)計(jì)類似的正交設(shè)計(jì)、單純形法等方法進(jìn)行空間布點(diǎn)，然后利用可用于局部?jī)?yōu)化的Powell算法、共軛梯度法、最速下降法等方法進(jìn)行局部?jī)?yōu)化，也可能在特殊應(yīng)用領(lǐng)域達(dá)到較好的全局最優(yōu)化效果。

參考文獻(xiàn)：

［1］AIMO T， ANTANAS Z.Global optimization（lecture notes in compu－ter science）[M].Berlin:Springer－Verlag，1989：15－42. 

[2]WILLIAN H P，SANL A T，WILLIAN T，et al.Numerical recipes in C++[M].[S.l.]:Publishing House of Electronics Industry，2005:295－317.

[3]PARADALOS P M， SHALOWAY D，XUE G L.Optimization methods for computing global minima of non－convex potential energy functions[J].Journal of Global Optimization，1994，4(1):17－133.

[4]JIANG L L， XUE G L.Optimization of molecule similarity index with applications to biomolecules[J].Journal of Global Optimization，1999，14:299－312.

[5]CHEN H M， ZHOUJ J， XIE G P.A genetic evolved algorithm to predict bioactivity[J].Comput Sci.，1998，38:243－250. 

[6]BYRD R H，ESKOW E，SCHNABEL R B.Parallel global optimization:numerical methods， dynamic scheduling methods， and application to molecular configuration[D]//FORD B，F(xiàn)INCHAM A.Parallel computation.[S.l.]:Oxford University Press，1993:187－207.

[7]CRAMER E J，DENNIS J E， FRANK P D，et al.Problem formulation for multidisciplinary optimization[J].Siam Journal of Optimization，1994，4(4):754－776.

[8]AUDET C，DENNIS J E.A patten search filter method for nonlinear programming without derivatives[D].[S.l.]:Department of Computational and Applied Mathematics， Rice University，2000.

[9]STEVE B， LOIS C M， JORGE J M，et al.Users mannal. mathematics and computer science division，ANL/MCS－TM－242 revision 1.5[R].[S.l.]:[s.n.]，2003.

[10]方開泰.均勻設(shè)計(jì)與均勻設(shè)計(jì)表[M].北京：科學(xué)出版社，1992:1－80.

[11]方開泰.均勻設(shè)計(jì)——數(shù)論方法在實(shí)驗(yàn)設(shè)計(jì)的應(yīng)用[J].應(yīng)用數(shù)學(xué)學(xué)報(bào)，1980，3(4):363－372.

[12]方開泰，鄭胡靈.均勻性的新度量——最大對(duì)稱差準(zhǔn)則[J].應(yīng)用概率統(tǒng)計(jì)，1992，8(1):10－16.

[13]鄒琳.基于遺傳算法的擠壓模具多目標(biāo)優(yōu)化設(shè)計(jì)與研究[D].武漢：華中科技大學(xué)博士論文，2004：35－38.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”