基于均勻設計與Ｐｏｗｅｌｌ算法的全局最優化算法及并行實現

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

關鍵詞：并行計算；均勻設計；Powell算法；全局最優化

中圖分類號：TP301．6文獻標志碼：A

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

0引言

最優化理論方法是應用數學的一門分支，研究決策問題的最佳選擇，構造尋找最佳解的計算方法，探討這些計算方法的理論性質及計算表現。目前，求解線性規劃、非線性規劃、隨機規劃、非光滑規劃、多目標規劃、組合優化等各種最優化問題的新方法不斷涌現。除了自然科學的各個領域之外，在建筑設計、金融設計、醫藥設計、生產管理、交通運輸等諸多方面均涉及最優化的應用。隨著高速計算機的普及和優化方法的不斷進步，規模越來越大的優化問題得到解決。

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

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

1背景介紹

1．1全局最優化模型

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

1．2均勻設計

均勻設計是20世紀80 年代，由我國科學家方開泰和王元開創的一種全新的試驗設計方法。其思路是讓試驗點在試驗范圍內充分均勻分散，這種從均勻性出發的設計被稱為均勻設計。

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

1．3Powell算法

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

2并行算法的實現及性能分析

2．1將均勻設計思想與Powell算法結合

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

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

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

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

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

2．2并行化

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

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

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

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

//Row_Num為分配該進程初始點個數

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;

//進入計算部分

/*然后將每個進程計算結果傳給root進程0；root取最優值賦給result變量*/

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

2．3性能分析

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

(2)并行效率分析

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

3算法測試

3．1試驗環境

聯想深騰6800 超級計算機系統;

系統結構：COW；

265個四路節點機；

內存總容量2.6 TB，磁盤總容量80 TB；

高速連接網絡QsNet，點對點通信帶寬大于300 MB，延遲時間小于7 μs。

3．2尋優能力測試

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

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

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

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

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

3．4時間復雜度測試

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

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

4結束語

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

該方法可適用于各種數值和非數值優化的科學計算問題，如生物信息學和計算化學等領域，也可以用于多種工程計算方面，具有較為廣泛的應用。

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

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

參考文獻：

［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，FINCHAM 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]方開泰.均勻設計與均勻設計表[M].北京：科學出版社，1992:1－80.

[11]方開泰.均勻設計——數論方法在實驗設計的應用[J].應用數學學報，1980，3(4):363－372.

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

[13]鄒琳.基于遺傳算法的擠壓模具多目標優化設計與研究[D].武漢：華中科技大學博士論文，2004：35－38.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”