《电气自动化毕业论文分布式并行计算环境下混合遗传算法的研究.doc》由会员分享，可在线阅读，更多相关《电气自动化毕业论文分布式并行计算环境下混合遗传算法的研究.doc（3页珍藏版）》请在三一办公上搜索。
1、分布式并行计算环境下混合遗传算法的研究 分布式并行计算环境下混合遗传算法的研究 摘要：为提高混合遗传算法的计算效率和求解质量，提出一个并行混合遗传算法框架。该框架主要由遗传算法、小生境操作和单纯形3部分组成，遗传算法和小生境操作采用串行执行方式，单纯形采用分布式并行执行方式。分布式并行计算环境由4台计算机通过交换机连接构成，并设计了一个动态任务调度方案。一个典型工程算例验证了新算法的有效性，并且在分布式并行环境下取得了较好的加速比和并行效率。 关键词：遗传算法；小生境；单纯形；分布式并行计算；任务调度 工程中的许多优化问题都是非凸、高度非线性和存在多个局部极值，采用传统的优化方法容易陷入局部极
2、值，难以求得全局最优解，而以遗传算法为代表的现代优化方法在求解这类复杂全局优化问题上展现出了独特魅力。但是遗传算法存在容易过早收敛和局部搜索能力差的不足，前者常使算法收敛于局部最优解，后者导致进化后期搜索效率低。在遗传算法的进化过程中，遗传算子并不完全具备将种群引向最佳静态适应度的模式的能力，所以从整体上讲，改进遗传算子和调整遗传算子的控制参数，不能保证遗传算法求得全局最优解3。当前，以遗传算法全局搜索为主体，引入其他局部搜索算法，构造合理的混合遗传算法，被认为是提高遗传算法求解质量的有效方法，这也是近年来遗传算法研究的热点4。文献5-6提出一种基于单纯形的混合遗传算法，该算法以遗传算法流程为
3、主体，在完成遗传算法的选择、交叉和变异后再进行单纯形操作，达到增强遗传算法局部搜索能力的目的。但由于在遗传算法中引入了其他算法，显然增加了算法的计算时间，降低了算法的效率，解决办法是把混合遗传算法改成并行算法，采用分布式并行计算。分布式并行计算就是充分利用高速局域网中的计算机资源，实现大型问题的松耦合并行计算，它具有自治性、并行性和成本低等优点7，它需要一个可移植的网络计算环境，PVM（Parallel Virtual Machine）就是这样一个被广泛应用的环境。在PVM的控制之下，由用户指定的通过网络互连的众多异构机器就形成一个单一的虚拟并行计算机系统，这些异构机器可以是多处理机、工作站和
4、PC机，它们之间的消息传递、数据转换和任务分配等均由PVM以对用户透明的方式自动完成。 构造了一个基于单纯形的并行混合遗传算法（Parallel Hy-brid Genetic Algorithm，PHGA）。该算法以遗传算法流程为基础，引入小生境操作和单纯形，在增加了种群多样性的同时也增强了遗传算法的局部搜索能力，并且在运算过程中，单纯形的计算采用基于PVM的分布式并行计算，节约了计算时间。通过一个典型工程算例的计算，验证了该算法的有效性，并分析了在分布式并行环境下的加速比和并行效率。 1 PHGA的框架 本文将单纯形和小生境技术有机地融入遗传算法，以维护种群多样性和增强局部搜索能力，全面搜
5、索复杂的可行域，快速可靠地获得高精度的全局最优解。单纯形是一种确定性搜索技术，算法的核心思想是用单纯形中最差顶点、最好顶点和其他顶点估算方向梯度，方向是从最差顶点到除最差顶点之外的其他各顶点的形心，然后用既能使目标函数值下降又能满足约束条件的新顶点替换最差顶点，不断构成新的单纯形。单纯形作为一种有效的局部搜索算法，可以弥补遗传算法局部搜索能力差的不足8。小生境技术通过在种群中构造不同的和特定的个体生存环境，并对生存环境中优秀个体实施保护措施，加速淘汰适应值低的个体，达到维持种群多样性和防止过早收敛的目的。 文献5构造了基于单纯形的混合遗传算法，该算法在完成当代种群的选择、交叉和变异3个遗传操作
6、后，单纯形执行全局探测和局部开采。在全局探测阶段，根据个体相似性构成不同的小生境，运用单纯形以一定概率对各个小生境进行搜索；在局部开采阶段，运用单纯形以一定概率集中搜索当前种群的最优个体的邻域，并将搜索到的优秀个体代替原种群中的最差个体。在整个算法框架中，遗传算法和单纯形采用串行执行方式，总的计算时间主要由遗传算法的计算时间和所有单纯形的计算时间组成，同单个遗传算法相比，增加了算法的运行时间，降低了算法的效率。本文为解决这一问题，提出了一个并行混合遗传框架，如图1所示，该算法框架主要由遗传算法、小生境操作和单纯形3个部分组成，遗传算法和小生境操作采用串行执行方式，单纯形采用分布式并行执行方式，
7、也就是说，在执行完遗传算法的基本操作和小生境操作之后，局部开采中的单纯形和全局探测中各个小生境的单纯形在分布式计算环境中进行并行运算，达到节约计算时间的目的。另外为了提高混合遗传算法的求解质量，局部开采和全局探测不设概率，保证每代在进行遗传算法后必须用单纯形进行全局探测和局部开采。 2 PHGA的实现 根据上述思想，基于单纯形和小生境操作相结合的并行混合遗传算法实现如下：（1）初始化种群。设置进化代数计数器t=1，设置最大进化代数T。随机生成由M个个体组成的初始种群P，计算出各个个体的适应度，将P作为父代种群。根据个体的适应度进行降序排序，记忆前N个个体（N （2）选择运算。采用随机联赛选择方
8、式，对种群P进行选择运算，得到种群P。 （3）交叉操作。采用自适应的交叉概率对种群P进行算术交叉运算，得到种群P。 （4）变异操作。采用自适应的变异概率对种群P进行非均匀变异，得到种群P?。 （5）小生境操作。将第（4）步得到的M个个体和所记忆的N个个体合并成M+N个个体的新种群，对这M+N个个体，按照下式计算每两个个体Xi和Xj之间的归一化欧式距离，小生境半径为D，对每一个个体Xi，当其适应度F(Xi)3 >0时，若Xi-Xj Xi-Xj=1 n?k=1n(xik-xjk)2?i=12M+N-1j=i+1M+N（6）单纯形的局部开采和全局探测。该部分在分布式并行计算环境中并行计算。局部
9、开采阶段，对种群P?进行降序排列，取前N个优秀个体进行单纯形搜索，得到种群P?1；全局探测阶段，统计种群P?中小生境个数和每个小生境中的个体数，在个体数大于2的所有小生境内分别进行单纯形搜索，得到种群P?2。 （7）小生境操作。种群P? 1、P?2和P?合并后按照第（5）步的方法进行小生境操作，降序排序后取前M个个体赋给种群P作为下一代进化种群，同时记忆前N个个体。 （8）终止条件判断。若tT，更新进化迭代计数器t=t+1，转到第（2）步，若t>T，则输出结果，计算结束。 3 PHGA的分布式并行计算 分布式并行计算环境是互联局域网中不同计算能力的异构机器，达到实现高性能并行计算的目的。
10、分布式并行计算环境也需要一个可移植的网络计算环境，PVM（Parallel Virtu-al Machine）就是这样一个被广泛应用的环境。在PVM的控制之下，由用户指定的通过网络互连的众多异构机器就形成一个单一的虚拟并行计算机系统，这些异构机器可以是多处理机、工作站和PC机，它们之间的消息传递、数据转换和任务分配等均由PVM以对用户透明的方式自动完成。 搭建的分布式并行计算环境如图2所示，由4台PC机通过交换机连接而成，在每台PC机上安装PVM软件，其中1台PC机为主节点机，其他PC机为从节点机，在主节点机上执行遗传算法和小生境操作等主进程，在主节点机和从节点机上执行单纯形进程。也就是说，主
11、节点机上的主进程通过PVM启动主节点机和从节点机上的单纯形进程，再对当前种群进行选择、交叉与变异等遗传操作和小生境操作，并把数据传递给单纯形进程，这时主进程必须等待结果返回，同时在主节点机和3台从节点机上分布式并行计算局部开采中的单纯形和全局探测中各个小生境的单纯形，当所有计算结果都返回给主节点机上的主进程后，主进程才进行小生境等操作，如果没有满足收敛条件就进入下一次迭代。为了平衡各节点机的负载，设计了一个如图3所示的动态任务调度方案，每代PVM执行的任务数等于1次局部开采加上全局探测中的小生境数量，根据任务数的不同执行不同的分发策略，如果任务数不大于节点机数，一次性分发完所有任务给节点机；否
12、则进行异步方式的多轮分发，首次给分布式并行计算环境中的每台节点机分配一个任务，当某台节点机计算完毕返回结果后就马上给它分配新任务，这样动态分配任务直到所有任务计算完毕，多轮分发体现了“能者多劳”原则。 4算例 分布式并行计算环境中的4台计算机均为联想开天M4000，配置为Pentium?4 3.0 GHz CPU，512 MB内存。参数设置为：种群规模M为20，N为0.3M，最大进化代数T为200，交叉概率0.8，变异概率0.3，小生境半径D为0.01。选取一个52杆的空间桁架结构的优化设计问题作为算例，如图4所示。所有节点都位于一个半径为6 m的球面上，每个非固定节点上均附加质量50 kg，
13、弹性模量为21011Pa，密度为7 800 kg/m3。在优化设计过程中，结构的对称性保持不变，结构要求第一阶自振圆频率不大于100 rad/s和第二阶自振圆频率不小于180 rad/s，杆件截面积在0.000 1 m2和0.001 m2之间，非固定节点允许移动的范围在3个坐标方向的上下界限是2 m，设计变量包括8类杆件的截面积和5个节点坐标共13个变量，优化目标是结构重量最小化，其余细节请参考文献5。本文用NHGA在1台机和PHGA在1台机、2台机、3台机、4台机上对算例进行15次优化计算，统计结果如表1所示。从表1可知：（1）本文算法计算的最好目标值、平均目标值和最差目标值都好于NHGA的
14、计算结果，说明本文算法有效和稳定。（2）本文算法在1台机的计算时间比NHGA多了1.26个小时，但在2台机节约了2.32个小时、3台机节约了2.99个小时和4台机节约了3.59个小时，说明随着节点机数的增加，计算时间减少，并行算法明显提高了计算速度。（3）取得了较好的加速比和并行效率。但2台机的并行效率最大为0.77，4台机的并行效率最小为0.48，说明随着节点机数的增加，并行效率在减少，所以要根据实际问题和通信开销合理选择节点机的规模。 5结束语 构造了一个基于单纯形的并行混合遗传算法，该算法不但考虑了遗传算法的全局搜索和单纯形的局部搜索，同时也考虑了在分布式并行环境下运算可以大大节约计算时间。一个典型工程算例的计算结果表明，提出的并行算法提高了遗传算法的求解质量和计算效率。今后尚需更加深入地研究并行混合遗传算法，寻求既保证求解质量同时也能降低通信开销的方法，以及研究各个参数对算法性能的影响。 参考文献： 刑文训，谢金星.现代优化计算方法M.北京：清华大学出版社，2005. 徐宗本，高勇.遗传算法过早收敛现象的特征分析及其预防J.中国科学：E辑，1996，26（4）：364-375. 3温显斌，张桦，张颖，等.软计算及其应用M.北京：科学出版社，2009. 4El-Mihoub T A，Hopgood A A，Nolle L，et al.Hybrid gen3
