结构分析与优化设计的并行计算方法

周 勇

摘要由于并行计算机的出现,对结构工程应用的有限元与优化设计算法的研究已取得较大进展,本文论述了有限元分析与优化设计并行算法的国内外研究状况,并对结构分析与优化设计的并行算法进行了概括及对其未来发展做了展望。

关键词并行算法 有限元法 优化设计

中图分类号: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并行计算机,又适合分布存储并行环境。基于分布存储环境的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)并行进化算法。并行进化算法是对个体所进行的各种进化操的一种算法,它的各种进化操作都有一定的相互独立性,因此它具有一种天然的并行结构。进化算法在解决一些实际问题时,由于它一般具有较大的种群规模,需要对较多的个体进行大量的遗传和进化操作,特别是要对大量的个体进行适应度计算或评价,从而使得算法的进化运算过程进展缓慢,难以达到计算速度上的要求,因而进化算法的并行计算问题受到了较大的重视。由于进化算法的天然并行性,人们认识到了对其进行并行处理的可能性,从而基于各种并行计算机或局域网,开发出了多种并行进化算法。开发并行进化算法的主要目的是为了提高进化算法的运行速度。实践表明,各种并行进化算法都能不同程度地达到这个要求。

综上所述,有限元分析及优化算法本身存在并发性。基于MPI和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.