《并行遗传算法》由会员分享，可在线阅读，更多相关《并行遗传算法（16页珍藏版）》请在金锄头文库上搜索。
1、并行遗传算法PGAs,介绍,遗传算法是一类基于自然选择和遗传学原理的 有效搜索方法，许多领域成功地应用遗传算法 得到了问题的满意解。虽然SGA 通常能在合理 的时间内找到满意解，但随着求解问题的复杂 性及难度的增加，提高遗传算法的运行速度便 显得尤为突出。,并行群体模型对SGA的修改,要把串行SGA 的单一群体分成多个子群体并分而治之要控制、管理子群体之间的信息交换,PGA的四种基本模型,主从式模型细粒度模型粗粒度模型混合模型,主从式模型,主从式模型是遗传算法的直接并行化方案, 不改变 遗传算法的基本结构特点, 它只有一个群体, 选择、 交叉和变异等全局操作由主节点机(或主处理器) 串行进行,
2、 而适应度的评价和计算由各从节点机 (或从处理器) 并行执行。,主从式模型优缺点,此模型易于实现, 是一个非常有效的并行化方法。可以直接应用SGA 的理论结果。,经常会出现主、从节点机负荷忙闲不均匀的情况。存在通信瓶颈和通信延迟问题。,细粒度模型,细粒度模型又称作邻域模型, 在整个进化过程中虽 然保持一个群体, 但要求子群体的划分要非常细小, 最理想状态是每个节点机(或处理器) 只有一个个 体, 要求各节点机具有极强的通信能力, 对于每个染 色体, 选择和交叉操作都只在所处的节点机及其邻 域中进行。 由于整个进行过程中, 不需要或者需要 很少的全局操作, 因此充分发挥了并行特性。,细粒度模型,
3、通常情况下, 对于较小的群体中, 应采用大范围的拓 扑; 而对于较大的群体中, 多采用具有4 个或8 个通 信邻域的方格超环面网格。具体采用哪种邻域拓 扑较好目前尚无定论, Shapiro B 等通过对8 个最优 近邻域, 4 个最近邻域在距离r 内的全部邻域进行实 验, 发现当r 2时, 结果最差, 4 个邻域模式优于8 个 邻域模式。,采用什么样的邻域结构是需 要解决的主要问题之一！,粗粒度模型,粗粒度模型又被称作分布式模型或孤岛模型, 是适应性最强和应用最广的遗传算法的并行模型。它将群体依照节点机(或处理器) 的个数分成若干个子群体, 各个子群体在各自的节点机(或处理器) 上并发独自运行
4、遗传算法, 每经过一定的进化代, 各个子群体间将交换若干个个体。,粗粒度模型,粗粒度模型,迁移规模,迁移规模由两个重要参数来控制: 迁移周期和迁移率。,迁移规模由两个重要参数来控制: 迁移周期和迁移率。,粗粒度模型,迁移策略,迁移基本上可以采用与匹配选择和生存选择相同的策略, 虽然区域选择更偏向区域内部较好的个体, 但在实际的迁移选择和替换中, 也可以采用其它标准。,粗粒度模型,迁移拓扑,迁移拓扑确定了子群体之间个体的迁移路径,目前 迁移拓扑大多都采用了类似给定并行机的互联拓 扑, 如完全隔离、单向环、双向环、超立方体和网 格等。迁移拓扑是影响PGA 性能的重要方面, 也 是迁移成本的主要因素。,混合模型,混合模型是近些年快速发展起来的模型结构, 主要是通过把前面三种基本模型混合形成层次 结构。目前混合模型组合关系主要有三种: 粗粒度-细粒度、粗粒度-粗粒度和粗粒度-主从式。,模型比较,THANK YOU!,
