基于均匀设计与Powell算法的全局最优化算法及并行实现

　　摘要：复杂函数的全局最优化问题是在求解各种复杂工程与问题中提炼出来的亟待解决的计算问题，均匀设计具有让试验点在高维空间内均匀分散的特点，而Powell算法具有很好的求解局部最优解的能力，将两种方法进行有效改进后使之相结合，设计出并行全局最优化算法。通过经典的全局最优化函数对算法进行了比较测试，发现该算法具有比以前的算法更好的寻优能力，并对算法时间、空间复杂度以及并行性进行分析和测试。基于均匀设计与Powell算法的全局最优化并行算法具有寻优能力强，时间开销与问题因素个数的平方和布点数成线性复杂度，空间开销与因素个数和布点数成线性复杂度，并行效率好的特点。 ?
　　关键词：并行计算；均匀设计；Powell算法；全局最优化?
　
　　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.