载入中....
设为首页 收藏本站 联系我们 网站地图
论文网
您现在的位置: 免费毕业论文网 >> 工学论文 >> 自动化专业 >> 正文
搜索: 论文

分布式并行计算环境下混合遗传算法的研究

更新时间 2011-5-7 15:06:17 点击数:

分布式并行计算环境下混合遗传算法的研究
    摘要:为提高混合遗传算法的计算效率和求解质量,提出一个并行混合遗传算法框架。该框架主要由遗传算法、小生境操作和单纯形3部分组成,遗传算法和小生境操作采用串行执行方式,单纯形采用分布式并行执行方式。分布式并行计算环境由4台计算机通过交换机连接构成,并设计了一个动态任务调度方案。一个典型工程算例验证了新算法的有效性,并且在分布式并行环境下取得了较好的加速比和并行效率。
     关键词:遗传算法;小生境;单纯形;分布式并行计算;任务调度
    工程中的许多优化问题都是非凸、高度非线性和存在多个局部极值,采用传统的优化方法容易陷入局部极值,难以求得全局最优解,而以遗传算法为代表的现代优化方法在求解这类复杂全局优化问题上展现出了独特魅力[1]。但是遗传算法存在容易过早收敛和局部搜索能力差的不足[2],前者常使算法收敛于局部最优解,后者导致进化后期搜索效率低。在遗传算法的进化过程中,遗传算子并不完全具备将种群引向最佳静态适应度的模式的能力,所以从整体上讲,改进遗传算子和调整遗传算子的控制参数,不能保证遗传算法求得全局最优解[3]。当前,以遗传算法全局搜索为主体,引入其他局部搜索算法,构造合理的混合遗传算法,被认为是提高遗传算法求解质量的有效方法,这也是近年来遗传算法研究的热点[4]。文献[5-6]提出一种基于单纯形的混合遗传算法,该算法以遗传算法流程为主体,在完成遗传算法的选择、交叉和变异后再进行单纯形操作,达到增强遗传算法局部搜索能力的目的。但由于在遗传算法中引入了其他算法,显然增加了算法的计算时间,降低了算法的效率,解决办法是把混合遗传算法改成并行算法,采用分布式并行计算。分布式并行计算就是充分利用高速局域网中的计算机资源,实现大型问题的松耦合并行计算,它具有自治性、并行性和成本低等优点[7],它需要一个可移植的网络计算环境,PVM(Parallel Virtual Machine)就是这样一个被广泛应用的环境。在PVM的控制之下,由用户指定的通过网络互连的众多异构机器就形成一个单一的虚拟并行计算机系统,这些异构机器可以是多处理机、工作站和PC机,它们之间的消息传递、数据转换和任务分配等均由PVM以对用户透明的方式自动完成。
    构造了一个基于单纯形的并行混合遗传算法(Parallel Hy-brid Genetic Algorithm,PHGA)。该算法以遗传算法流程为基础,引入小生境操作和单纯形,在增加了种群多样性的同时也增强了遗传算法的局部搜索能力,并且在运算过程中,单纯形的计算采用基于PVM的分布式并行计算,节约了计算时间。通过一个典型工程算例的计算,验证了该算法的有效性,并分析了在分布式并行环境下的加速比和并行效率。
    1 PHGA的框架
    本文将单纯形和小生境技术有机地融入遗传算法,以维护种群多样性和增强局部搜索能力,全面搜索复杂的可行域,快速可靠地获得高精度的全局最优解。单纯形是一种确定性搜索技术,算法的核心思想是用单纯形中最差顶点、最好顶点和其他顶点估算方向梯度,方向是从最差顶点到除最差顶点之外的其他各顶点的形心,然后用既能使目标函数值下降又能满足约束条件的新顶点替换最差顶点,不断构成新的单纯形。单纯形作为一种有效的局部搜索算法,可以弥补遗传算法局部搜索能力差的不足[8]。小生境技术通过在种群中构造不同的和特定的个体生存环境,并对生存环境中优秀个体实施保护措施,加速淘汰适应值低的个体,达到维持种群多样性和防止过早收敛的目的。
    文献[5]构造了基于单纯形的混合遗传算法,该算法在完成当代种群的选择、交叉和变异3个遗传操作后,单纯形执行全局探测和局部开采。在全局探测阶段,根据个体相似性构成不同的小生境,运用单纯形以一定概率对各个小生境进行搜索;在局部开采阶段,运用单纯形以一定概率集中搜索当前种群的最优个体的邻域,并将搜索到的优秀个体代替原种群中的最差个体。在整个算法框架中,遗传算法和单纯形采用串行执行方式,总的计算时间主要由遗传算法的计算时间和所有单纯形的计算时间组成,同单个遗传算法相比,增加了算法的运行时间,降低了算法的效率。本文为解决这一问题,提出了一个并行混合遗传框架,如图1所示,该算法框架主要由遗传算法、小生境操作和单纯形3个部分组成,遗传算法和小生境操作采用串行执行方式,单纯形采用分布式并行执行方式,也就是说,在执行完遗传算法的基本操作和小生境操作之后,局部开采中的单纯形和全局探测中各个小生境的单纯形在分布式计算环境中进行并行运算,达到节约计算时间的目的。另外为了提高混合遗传算法的求解质量,局部开采和全局探测不设概率,保证每代在进行遗传算法后必须用单纯形进行全局探测和局部开采。
    2 PHGA的实现
    根据上述思想,基于单纯形和小生境操作相结合的并行混合遗传算法实现如下:(1)初始化种群。设置进化代数计数器t=1,设置最大进化代数T。随机生成由M个个体组成的初始种群P,计算出各个个体的适应度,将P作为父代种群。根据个体的适应度进行降序排序,记忆前N个个体(N
    (2)选择运算。采用随机联赛选择方式,对种群P进行选择运算,得到种群P′。
    (3)交叉操作。采用自适应的交叉概率对种群P′进行算术交叉运算,得到种群P″。
    (4)变异操作。采用自适应的变异概率对种群P″进行非均匀变异,得到种群P?。
    (5)小生境操作。将第(4)步得到的M个个体和所记忆的N个个体合并成M+N个个体的新种群,对这M+N个个体,按照下式计算每两个个体Xi和Xj之间的归一化欧式距离,小生境半径为D,对每一个个体Xi,当其适应度F(Xi)

[1] [2] [3] 下一页

返回栏目页:自动化专业论文

设为主页】【收藏论文】【保存论文】【打印论文】【回到顶部】【关闭此页