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