文档介绍：并行遗传算法及其应用
1、遗传算法(GA概述
GA是一类基于自然选择和遗传学原理的有效搜索方法，它从一个种群开始， 利用选择、交叉、变异等遗传算子对种群进行不断进化，最后得到全局最优解。 生物遗传物质的主要载体是染色体，在 GA中同样将不同区域的抽样， 来估计不同区域的适应度，进而估计 最优解存在于不同区域的概率，以调整算法对不同区域的抽样密度和搜索力度， 进而不断提高对最优解估计的准确程度。可见，以邻域结构为依据划分等价类的 马尔可夫模型更符合实际，对问题的抽象更能体现优化问题的本质。
3、并行遗传算法（PGA
虽然在许多领域成功地应用遗传算法，通常能在合理的时间内找到满意解， 但随着求解问题的复杂性及难度的增加，提高 GA的运行速度便显得尤为突出， 采用并行遗传算法（PGA是提高搜索效率白^方法之一。由于 GA从种群出发，所 以具有天然的并行处理特性，非常适合于在大规模并行计算机上实现， 而大规模 并行计算机的日益普及，为PGAM定了物质基础。特别是GA中各个体适值计算 可独立进行而彼此间无需任何通信，所以并行效率很高。实现 PGA不仅要把用
行GA等价地变换成一种并行方案，更重要的是要将GA的结构修改成易于并行化 实现的形式，形成并行种群模型。并行种群模型对传统 GA的修改涉及到两个方
面：一是要把串行GA的单一种群分成多个子种群，分而治之；二是要控制、管 理子种群之间的信息交换。不同的分治方法产生不同的PG匐构。这种结构上的 差异导致了不同的PGA真型：全局并行模型、粗粒度模型、细粒度模型和混合模 型。
3、1全局PGA1型
该模型又称主从PGA真型，它是串行GA的一种直接并行化方案，在计算机 上以master-slave编程模式实现。它只有一个种群，所有个体的适应度都根据 整个种群的适应度计算，个体之间可以任意匹配，每个个体都有机会和其他个体 杂交而竞争，因而在种群上所作的选择和匹配是全局的。 对于这个模型有多种实 现方法：第一种方法是仅仅对适值度函数计算进行并行处理； 第二种方法是对遗
传算子进行并行处理。全局模型易于实现，如果计算时间主要用在评价上，这是 一种非常有效的并行化方法。
它最大的优点是简单，保留了串行 GA的搜索行为，因而可直接应用 GA的 理论来预测一个具体问题能否映射到并行 GA上求解。对于适应度估值操作比其 他遗传算子计算量大的多时，它是很有效的，并且不需要专门的计算机系统结构。 3、2粗粒度PGA真型
该模型又称分布式、MIMD岛模式遗传算法模型，它是对经典GAs结构的扩 展。它将种群划分为多个子种群（又称区域），每个区域独自运行一个GA此时， 区域选择取代了全局选择，配偶取自同一区域，子代与同一区域中的亲本竞争。 除了基本的遗传算子外，粗粒度模型引入了 “迁移”算子，负责管理区域之间的 个体交换。在粗粒度模型的研究中，要解决的重要问题是参数选择，包括：迁移 拓扑、迁移率、迁移周期等。
在种群划分成子种群（区域）后，要为种群指定某种迁移拓扑。迁移拓扑确定 了区域之间个体的迁移路径，迁移拓扑与特定的并行机结构有着内在的对应关 系，大多采用类似于给定并行处理机的互连拓扑。如果在顺序计算机上实现粗粒 度模型，则可以考虑采用任意结构。拓扑结构是影响
PGA性能的重要方面，也
是迁移成本的主要因素