均勻設(shè)計與Powell算法結(jié)合思考

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

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

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

0引言

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

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

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

1背景介紹

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

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

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

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

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

1．3Powell算法

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

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

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

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

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

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

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

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

2．2并行化

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

/*確定每個進程需要處理的第一個初始點Begin_Row和最后一個初始點End_Row*/

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

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

//Row_Num為分配該進程初始點個數(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;

//進入計算部分

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

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

2．3性能分析

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

(2)并行效率分析

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

3算法測試

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

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

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

265個四路節(jié)點機；

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

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

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

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

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

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

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

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

3．4時間復(fù)雜度測試

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

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

4結(jié)束語

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

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

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

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

參考文獻：

［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è)計與均勻設(shè)計表[M].北京：科學(xué)出版社，1992:1－80.

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

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

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