周 勇

摘要由于并行計算機(jī)的出現(xiàn),對結(jié)構(gòu)工程應(yīng)用的有限元與優(yōu)化設(shè)計算法的研究已取得較大進(jìn)展,本文論述了有限元分析與優(yōu)化設(shè)計并行算法的國內(nèi)外研究狀況,并對結(jié)構(gòu)分析與優(yōu)化設(shè)計的并行算法進(jìn)行了概括及對其未來發(fā)展做了展望。

關(guān)鍵詞并行算法 有限元法 優(yōu)化設(shè)計

中圖分類號:TP3文獻(xiàn)標(biāo)識碼:A

1引言

針對在現(xiàn)有硬件和軟件條件,不降低求解精度求解復(fù)雜結(jié)構(gòu)問題,要么耗時巨大,要么無能為力。應(yīng)用于并行的集群和并行編譯算法和環(huán)境就是在這種情況下產(chǎn)生的,并取得了長足的發(fā)展,如并行數(shù)值算法的開發(fā)。傳統(tǒng)的有限元和優(yōu)化算法都是基于串行,為了適用并行求解,有必要對串行算法進(jìn)行添加并行形語句或者重新編寫適合特定問題的并行算法。有限元法是而今用于結(jié)構(gòu)分析最廣泛的一種數(shù)值方法;工程優(yōu)化領(lǐng)域?yàn)榱斯?jié)省費(fèi)用、成本為國民建設(shè)服務(wù),需要對許多結(jié)構(gòu)進(jìn)行優(yōu)化設(shè)計,而優(yōu)化設(shè)計是具有多個設(shè)計變量的問題,求解是循環(huán)、迭代耗時大,并且優(yōu)化后還要進(jìn)行有限元結(jié)構(gòu)分析,這兩個設(shè)計任務(wù)迫切需求高效算法的出來。

2 國內(nèi)外研究現(xiàn)狀

2.1并行有限元算法的研究

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

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

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

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

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

(3)并行EBE( Element by Element)法。并行EBE算法是一種在單元上實(shí)施并行化的有限元整體運(yùn)算迭代算法,它可以避免總剛度矩陣的組集。既適合向量機(jī)或MIMD并行計算機(jī),又適合分布存儲并行環(huán)境。基于分布存儲環(huán)境的EBE-PCG是一種有效的算法。

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

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

綜上所述,針對復(fù)雜問題,開發(fā)其并發(fā)性,通過研究常規(guī)問題的并行數(shù)值算法,并在現(xiàn)有硬件和軟件條件基礎(chǔ)上編程求解大規(guī)模問題,并評價其并行算法性能進(jìn)行度量,進(jìn)入提出更高效的算法。

2.2并行優(yōu)化算法的研究

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

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

第二類算法針對來優(yōu)化問題求解的特點(diǎn),發(fā)展了許多并行優(yōu)化算法:并行模擬退火算法、并行遺傳算法、并行進(jìn)化算法。這些算法均屬于隨機(jī)搜索法的范疇,都具有較可靠的全局尋優(yōu)基礎(chǔ)。

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

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

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

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

3 結(jié)論和展望

并行數(shù)值算法和編譯環(huán)境為開發(fā)問題的并發(fā)性提供了支持并行的許多方案。一方面也發(fā)展了許多并行有限元算法:子結(jié)構(gòu)并行凝聚法、并行EBE法、FETI法;另一方面產(chǎn)生了一些并行優(yōu)化算法如:并行遺傳算法、并行進(jìn)化算法等。但是較少使有限元分析與優(yōu)化設(shè)計結(jié)合起來的高效算法,并對幾種并行算法進(jìn)行性能研究。

針對大規(guī)模結(jié)構(gòu)分析和優(yōu)化設(shè)計問題在單機(jī)上求解效率低、甚至不可能,提出了適合單機(jī)和集群系統(tǒng)上的高效算法,為大型復(fù)雜工程結(jié)構(gòu)的有限元分析、優(yōu)化設(shè)計問題提供解決方案;并促進(jìn)并行數(shù)值算法在工程優(yōu)化學(xué)科中的應(yīng)用和發(fā)展。

神經(jīng)網(wǎng)絡(luò)是在研究生物神經(jīng)系統(tǒng)的啟示下發(fā)展起來的一種信息處理方法。可以處理模糊的,非線性的數(shù)據(jù),在進(jìn)行結(jié)構(gòu)分析之前使用神經(jīng)網(wǎng)絡(luò)進(jìn)行判斷減少重分析的量,提高尋優(yōu)的效率?？蓪⑵湟氲接邢拊治鲋?減少重分析次數(shù),并與并行結(jié)合的混合算法。

參考文獻(xiàn)

[1] 陳耿東.工程結(jié)構(gòu)優(yōu)化設(shè)計基礎(chǔ)[M].北京:水利水電出版社,1984.

[2] 錢令希.工程結(jié)構(gòu)優(yōu)化設(shè)計[M].北京:水利水電出版社,1984.

[3] 阮紅河.結(jié)構(gòu)分析理論的并行有限元方法[D].上海:同濟(jì)大學(xué),2004.

[4] 呂濤,石濟(jì)民,林鄭寶.區(qū)域分解算法[M].北京:科學(xué)出版社,1992.

[5]張汝清.概說并行計算結(jié)構(gòu)力學(xué)[J].計算結(jié)構(gòu)力學(xué)及應(yīng)用,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] 李曉梅,吳建平.數(shù)值并行算法與軟件[M].北京:科學(xué)出版社,2007.

[8] 陳國良.并行計算-結(jié)構(gòu),算法.編程[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環(huán)境的并行模擬退火算法及其工程應(yīng)用[J]. 水利與建筑工程學(xué)報, 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] 張旭風(fēng),王紀(jì)川等. 并行遺傳算法收斂性分析及優(yōu)化[J]. 西安工程科技學(xué)院學(xué)報,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] 余榮祖. 并行進(jìn)化算法及其在組合優(yōu)化中的應(yīng)用[D]. 西安:西安電子科技大學(xué),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.