導(dǎo)語：均勻設(shè)計(jì)與Powell算法結(jié)合思考一文來源于網(wǎng)友上傳，不代表本站觀點(diǎn)，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

摘要：復(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è)試?；诰鶆蛟O(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)化

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ù)

elseRow_Num=PopSize/size;

if(myid<=PopSize%size)

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

elseBegin_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è)萘?.6TB，磁盤總?cè)萘?0TB；

高速連接網(wǎng)絡(luò)QsNet,點(diǎn)對(duì)點(diǎn)通信帶寬大于300MB，延遲時(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)，然后利用可用于局部優(yōu)化的Powell算法、共軛梯度法、最速下降法等方法進(jìn)行局部優(yōu)化，也可能在特殊應(yīng)用領(lǐng)域達(dá)到較好的全局最優(yōu)化效果。

參考文獻(xiàn)：

［1］AIMOT,ANTANASZ.Globaloptimization（lecturenotesincompu－terscience）[M].Berlin:Springer－Verlag,1989：15－42.

[2]WILLIANHP,SANLAT,WILLIANT,etal.NumericalrecipesinC++[M].[S.l.]:PublishingHouseofElectronicsIndustry,2005:295－317.

[3]PARADALOSPM,SHALOWAYD,XUEGL.Optimizationmethodsforcomputingglobalminimaofnon－convexpotentialenergyfunctions[J].JournalofGlobalOptimization,1994,4(1):17－133.

[4]JIANGLL,XUEGL.Optimizationofmoleculesimilarityindexwithapplicationstobiomolecules[J].JournalofGlobalOptimization,1999,14:299－312.

[5]CHENHM,ZHOUJJ,XIEGP.Ageneticevolvedalgorithmtopredictbioactivity[J].ComputSci.,1998,38:243－250.

[6]BYRDRH,ESKOWE,SCHNABELRB.Parallelglobaloptimization:numericalmethods,dynamicschedulingmethods,andapplicationtomolecularconfiguration[D]//FORDB,FINCHAMA.Parallelcomputation.[S.l.]:OxfordUniversityPress,1993:187－207.

[7]CRAMEREJ,DENNISJE,FRANKPD,etal.Problemformulationformultidisciplinaryoptimization[J].SiamJournalofOptimization,1994,4(4):754－776.

[8]AUDETC,DENNISJE.Apattensearchfiltermethodfornonlinearprogrammingwithoutderivatives[D].[S.l.]:DepartmentofComputationalandAppliedMathematics,RiceUniversity,2000.

[9]STEVEB,LOISCM,JORGEJM,etal.Usersmannal.mathematicsandcomputersciencedivision,ANL/MCS－TM－242revision1.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.