結構分析與優化設計的并行計算方法

摘要由于并行計算機的出現，對結構工程應用的有限元與優化設計算法的研究已取得較大進展，本文論述了有限元分析與優化設計并行算法的國內外研究狀況，并對結構分析與優化設計的并行算法進行了概括及對其未來發展做了展望。

關鍵詞并行算法 有限元法 優化設計

中圖分類號:TP3文獻標識碼:A

1引言

針對在現有硬件和軟件條件，不降低求解精度求解復雜結構問題，要么耗時巨大，要么無能為力。應用于并行的集群和并行編譯算法和環境就是在這種情況下產生的，并取得了長足的發展，如并行數值算法的開發。傳統的有限元和優化算法都是基于串行，為了適用并行求解，有必要對串行算法進行添加并行形語句或者重新編寫適合特定問題的并行算法。有限元法是而今用于結構分析最廣泛的一種數值方法;工程優化領域為了節省費用、成本為國民建設服務，需要對許多結構進行優化設計，而優化設計是具有多個設計變量的問題，求解是循環、迭代耗時大，并且優化后還要進行有限元結構分析，這兩個設計任務迫切需求高效算法的出來。

2 國內外研究現狀

2.1并行有限元算法的研究

上世紀50年代來，隨著有限元方法和優化理論的發展，為結構分析和優化設計提供了強有力的工具，而且形成一套用于結構分析的有限元商業軟件及改進和優化設計的理論，工程結構優化設計得到了迅速發展并在實際工程中得到應用。由于現有大多軟件和優化理論都是基于串行編程，在求解復雜大規模工程結構問題的效率低，耗時長;在不降低精度的條件下快速進行結構分析及優化設計成為迫切需求，巨型機、集群及分布式、共享式編程模式的出現使其成為現實。并行算法及編譯環境的出現對有限元分析和優化設計提出了革命性的要求，如今并行有限元算法及并行優化算法已成為計算機、數學、計算力學及工程設計等領域的研究熱點。

現今，大規模并行處理機和工作站機群已成為高性能計算機領域的兩大重要研究方向。其中，工作站機群COW因具有較多優點而被大量中、小型計算用戶和科研院校所接受，成為高性能計算領域的一個新的發展熱點。針對并行發展了與之相關的許多并行數值計算方法:如矩陣并行計算，線性方程組的并行求解，矩陣特征值問題的并行計算等;并行編譯環境如常用的分布式消息傳遞接口MPI(Message passing interface)和共享式存儲并行編程OpenMP。OpenMP是一些語言擴展的集合，它被實現為編譯器指令。經常用于在串行代碼中添加并發性。MPI是一些例程的集合，這些例程提供進程管理、消息傳遞和某些通信操作(這些操作包括一個程序中所包含的所有進程，例如柵欄、廣播和歸約。

并行計算機的發展的這種趨勢為廣泛用于結構分析與設計中的數值分析方法-有限單元法注入了新的活力，為結構工程研究和設計者提供更強大的計算工具，使得他們不僅可以對大型的、復雜的結構進行分析與設計，且還允許他們考慮更多的影響因素，以提高分析、設計的精度與質量，并減少分析和設計的時間。而所有這一切的實現都需要有運行在并行計算機上的并行分析軟件的支持。在分布存儲并行環境下，有限元的并行策略主要包括:

(1)基于線性方程組并行數值求解器。利用求解器求解系統方程:①其中系統單元分析和系統方程的形成是串行過程，而系統方程組的求解是并行過程;②將剛度矩陣按行進行“分割”，各處理機存儲與每塊范圍有關的數據(單元、節點、荷載等)，所以單元分析與系統方程組裝過程可以并行進行。

(2)并行子結構法。子結構法在連續域問題中常被稱為區域分裂算法。并行子結構方法是根據傳統串行子結構的思想而實現的，即通過靜力凝聚削去子結構的內部自由度以建立整個結構在邊界結點上的平衡方程。在求得邊界結點的位移后，可同時求解各個子結構的內部自由度位移，并更新單元狀態。由于界面自由度個數遠小于整個自由度個數，因此界面方程的求解時間將大大減少，占整個分析過程的求解時間比例同樣也會減少，這對于提高算法的并行性是非常有利的。子結構內部自由度凝聚的處理，有兩種方法:①直接處理:矩陣分解和多波前法;②迭代處理:多重子結構法-子結構中嵌套子結構，如適合于MPP環境的HDDM(Hierarchical Domain Decompostion Method)法。

(3)并行EBE( Element by Element)法。并行EBE算法是一種在單元上實施并行化的有限元整體運算迭代算法，它可以避免總剛度矩陣的組集。既適合向量機或MIMD并行計算機，又適合分布存儲并行環境?；诜植即鎯Νh境的EBE-PCG是一種有效的算法。

(4)其它方法，如FETI( Finite Element Tearing and Interconnecting)法。與并行子結構法相類似，不同是子結構法以“界面位移”為基本未知量，而FETI法以“邊界力”(交界面上的力)為未知量。

采用并行有限元求解許多工程問題，如:基于MPI采用稀疏PCG(Preconditioned conjugate gradient)求解器來進行隱式非線性動力分析，在同步和異步并行計算環境上進行顯式非線性動力有限元分析等算例表明并行有限元具有至少線性的加速比。

綜上所述，針對復雜問題，開發其并發性，通過研究常規問題的并行數值算法，并在現有硬件和軟件條件基礎上編程求解大規模問題，并評價其并行算法性能進行度量，進入提出更高效的算法。

2.2并行優化算法的研究

前面是關于結構分析并行有限元算法的介紹，其中簡略介紹了科學計算中數值并行算法，以下將介紹與工程結構優化相關的并行算法的研究進展。在優化的目標函數和準則確定后，結構優化的實施工程包括設計變量的搜索和優化目標函數的計算分析。而設計變量的搜索主要是采用優化算法實現由當前設計變量向新的設計變量的搜索和更新。針對目標函數可以將優化算法分為兩大類:一類是確定性優化法(deterministic method);另一類是隨機優化算法(Stochastic method)。第一類中包括最流行的數學規劃法，特別基于梯度優化算子，這些方法利用設計變量的導數推導出的局部曲率信息來搜索新的最優點，當梯度不存在時有時采用有限差分法來近似計算敏度;第二類中以進化算法EA(Evolutionary Algorithms)、遺傳算法GA(Genetic Algorithms)為代表，這些方法都模擬生物自然進化的過程，這種嘗試性搜索雖然所需計算時間可能過長，但正好適合并行的求解，由多線程處理器共同完成。

第一類優化算法無論對于局部還是全局優化收斂速度都較快，但是容易陷于到局部最最優，有時不能保證全局最優，而且只適用凸域、情況。由于優化問題未知變量多，求解時間長，可以在編程時用共享式和分布式編程模式來完成如:循環的迭代、線性方程組的求解、矩陣運算、特征值特征向量的求解等。開發優化問題的并行性，提出并行方案如并行靈敏度分析，并用桁架的優化實例來驗證其求解效率。

第二類算法針對來優化問題求解的特點，發展了許多并行優化算法:并行模擬退火算法、并行遺傳算法、并行進化算法。這些算法均屬于隨機搜索法的范疇，都具有較可靠的全局尋優基礎。

(1)模擬退火算法。模擬退火算法是近年來發展起來的全局最優化算法，其主要有點是:求解目標函數的偏導數及解大型矩陣方程組，即能找到一個全局最優解，它源于對固體退火過程的模擬，采用Metropolis接受準則;并用一組稱為冷卻進度表的參數控制算法進程。其求解的質量有賴于大量的實驗，隨著問題的規模增大所需時間增長，而冷卻度表并不能從根本上提高算法的效率的解決途徑正是算法的并行實現，即并行模擬退火算法。

(2)并行遺傳算法。遺傳算法是基于生物進化機制的一種搜索算法，它與普通搜索算法(如梯度算法)一樣也是一種迭代算法，它通過遺傳基因代碼，利用復制、雜交和變異3種算子，從給定的初始解(種群)通過不斷的迭代，逐步實現種群的替代更新，最終收斂到全局優化解。而在此基礎上發展起來的并行遺傳算法有三種類型:主從式并行模式、粗粒度并行模式、細粒度并行模式。還有許多改進算法如:分布混合遺傳算法。

(3)并行進化算法。并行進化算法是對個體所進行的各種進化操的一種算法，它的各種進化操作都有一定的相互獨立性，因此它具有一種天然的并行結構。進化算法在解決一些實際問題時，由于它一般具有較大的種群規模，需要對較多的個體進行大量的遺傳和進化操作，特別是要對大量的個體進行適應度計算或評價，從而使得算法的進化運算過程進展緩慢，難以達到計算速度上的要求，因而進化算法的并行計算問題受到了較大的重視。由于進化算法的天然并行性，人們認識到了對其進行并行處理的可能性，從而基于各種并行計算機或局域網，開發出了多種并行進化算法。開發并行進化算法的主要目的是為了提高進化算法的運行速度。實踐表明，各種并行進化算法都能不同程度地達到這個要求。

綜上所述，有限元分析及優化算法本身存在并發性?；贛PI和OpenMP并行編譯環境，研究開發適合其并行操作的算法。一方面可以在現有的算法中添加并行性如:根據現有循環、迭代，矩陣運算的并行數值算法原理，改正原串行算法。另一方面可以重新開發有限元分析與優化設計的并行算法:如針對結構優化時有限元重分析耗時，可以引入人工神經網絡進行先判斷。由于結構優化問題往往需要有限元分析，其性質決定提出需要從優化問題、優化算法、有限元分析算法出發尋求其并行求解。本課題將為工程結構設計和優化問題提供一種快速高效的計算方法，從而為解決大規模復雜問題提供方案。

3 結論和展望

并行數值算法和編譯環境為開發問題的并發性提供了支持并行的許多方案。一方面也發展了許多并行有限元算法:子結構并行凝聚法、并行EBE法、FETI法;另一方面產生了一些并行優化算法如:并行遺傳算法、并行進化算法等。但是較少使有限元分析與優化設計結合起來的高效算法，并對幾種并行算法進行性能研究。

針對大規模結構分析和優化設計問題在單機上求解效率低、甚至不可能，提出了適合單機和集群系統上的高效算法，為大型復雜工程結構的有限元分析、優化設計問題提供解決方案;并促進并行數值算法在工程優化學科中的應用和發展。

神經網絡是在研究生物神經系統的啟示下發展起來的一種信息處理方法。可以處理模糊的，非線性的數據，在進行結構分析之前使用神經網絡進行判斷減少重分析的量，提高尋優的效率?？蓪⑵湟氲接邢拊治鲋?，減少重分析次數，并與并行結合的混合算法。

參考文獻

[1] 陳耿東.工程結構優化設計基礎[M].北京:水利水電出版社，1984.

[2] 錢令希.工程結構優化設計[M].北京:水利水電出版社，1984.

[3] 阮紅河.結構分析理論的并行有限元方法[D].上海:同濟大學，2004.

[4] 呂濤，石濟民，林鄭寶.區域分解算法[M].北京:科學出版社，1992.

[5]張汝清.概說并行計算結構力學[J].計算結構力學及應用，1995.12(4):477~48.

[6]Charbel Farhat*， Kendall pierson， Michel Lesoinne. The second generation FETI methods and their application to the parallel solution of large-scale linear and geometrically non-linear structural analysis problems[J]. Comput. Methods .Appl.Mech. Engrg. 184(2000):333~374.

[7] 李曉梅，吳建平.數值并行算法與軟件[M].北京:科學出版社，2007.

[8] 陳國良.并行計算-結構，算法.編程[M].北京:高等教育出版社，2003.

[9] A. Rama， Mohan Rao. MPI-based parallel finite element approaches for implicit nonlinear dynamics analysis employing sparse PCG solvers[J].Advances in Engineering Software， 2005.36: 181~198.

[10] A. Rama Mohan Rao.Explicit nonlinear dynamic finite element analysis on homogeneous/heterogeneous parallel computing environment [J].Advances in Engineering Software ， 2006(37): 701~720.

[11] Melhem R G. On the design of a pipelined/systolic finite element system [J]. Computers and structures， 1985.20(1-3): 67~75.

[12] Manolis Papadrakakis*，Nikolaos D. Lagaros. etc. Parallel computational strategies for structural optimization[J]. International journal for numerical methods in engineering， 2003.58: 1347~1380.

[13] Goldberg DE. Genetic Algorithms in search [M]. Optimization and Machine Learning， Addison-Wesley: Reading， MA，1989.

[14] J. Holland. Adaptation in natural and Artificial Systems. University of Michigan Press: Ann Arbor， MI， 1985.

[15] M. E. M， EI-Sayed . et al.Design optimization with parallel sensitivity analysis on the CRAY X-MP[J]. Structural Optimization， 1991.3: 247~251.

[16] P. K. Umesha，M. T. Venuraju. et al.Parallel computing Techniques for Sensitivity Analysis in Optimum Structural Design[J]. Journal of computing in civil engineering， 2007:463~477.

[17] S. P. Gurav， J. F. L. Goosen. et al. Bounded-But-Unknown uncertainty optimization using design sensitivities and parallel computing: Application to MEMS[J]. Computers and Structures， 2005.83: 1134~1149.

[18] Kirkpatrick S， Gelatt C D， Vecchi M P.Optimization by simulated annealing[J]. Sciencce， 1983.220: 671~680.

[19] B Hajeck. Cooling schedules for optimal annealing[J]. Mathematics of Operations Research， 1988.13: 311~329.

[20] 何靜， 彭濤. 基于MPI環境的并行模擬退火算法及其工程應用[J]. 水利與建筑工程學報， 2008.6(4): 99~111.

[21] S. D. Rajan，D. T. Nguyen. Design Optimization of Discrete Structural Systems Using MPI-enabled Genetic Algorithms[J]， Structural and multidisciplinary optimization， 2004.28(5): 340~348.

[22] 張旭風，王紀川等. 并行遺傳算法收斂性分析及優化[J]. 西安工程科技學院學報，2007.21(5):657~660.

[23] Hyo Seon Park，Yun Han Kwon，et al. Distributed Hybrid Genetic Algorithms for Structural Optimization on a PC Cluster[J]. Journal of structural engineering， 2006:1890~1897.

[24] 余榮祖. 并行進化算法及其在組合優化中的應用[D]. 西安:西安電子科技大學，2007.

[25] Nikolaos D. Lagaros， Dimos C， et al . An adaptive neural network strategy for improving the computational performance of evolutionary structural optimization[J]. Comput. Methods Appl. Mech. Engrg. 194(2005):3374~3393.

[26]Wind J. W. et al.Distributed multilevel optimization for complex structures[J]. Structural and Multidisciplinary Optimization， 2008.36:71~81.