什么是并行遗传算法介绍

并行遗传算法(Parallel Genetic Algorithm）是指对遗传算法进行并行设计后的算法，是一种适用复杂优化问题的多种群并行进化的遗传算法。 该算法能有效克服标准遗传算法的早熟收敛问题, 具有较强的全局搜索能力。

并行遗传算法将并行计算机的高速并行性和遗传算法固有的并行性相结合，极大地提升了遗传算法的求解速度和质量。

并行遗传算法简介

遗传算法是一类基于自然选择和遗传学原理的有效搜索方法，许多领域成功地应用遗传算法得到了问题的满意解 。虽然遗传算法通常能在合理的时间内找到满意解，但随着求解问题的复杂性及难度的增加，提高遗传算法的运行速度便显得尤为突出 。遗传算法具有天然的并行性，非常适合于在大规模并行计算机上实现，而大规模并行计算机的日益普及，为并行遗传算法奠定了物质基础。实现并行遗传算法，不仅要把串行遗传算法等价地变换成一种并行方案，更重要的是要将遗传算法的结构修改成易于并行化实现的形式，形成并行群体模型。

并行遗传算法将并行计算机的高速并行性和遗传算法的天然并行性相结合，并行处理的引入不仅提高了求解速度，而且由于种群规模的扩大和各子种群的隔离，使种群的多样性得以丰富和保持，减少了未成熟收敛的可能性，提高了求解质量。

并行遗传算法遗传算法的并行形式

遗传算法具有天然的并行性，其并行形式有以下4类：

(1)个体适应度评价内部的并行性;

(2)种群中每个个体适应度评价的并行性;

(3)算法基本操作内部的并行性;

(4)基于种群分组的并行性

并行遗传算法遗传算法并行模型

实现并行遗传算法，不仅要把串行遗传算法等价地变成一种并行方案，更重要的是要将遗传算法的结构修改成易于并行化的形式，形成并行模型。目前遗传算法并行模型共分为四类：主从式模型 ，粗粒度模型，细粒度模型和混合模型。以下作详细介绍：

并行遗传算法主从式模型

主从式模型是遗传算法的直接并行化方案，不改变遗传算法的基本结构特点，它只有一个群体，选择、交叉和变异等全局操作由主节点机(或主处理器)串行进行，而适应度的评价和计算由各从节点机(或从处理器)并行执行主节点机(或主处理器)和从节点机(或从处理器)的通信表现在两个方面，一方面主节点机(或主处理器)把选择的群体部分个体发送给从节点机(或从处理器)；另一方面从节点机(或从处理器)把适应度的评价结果发送给主节点(或主处理器)。

并行遗传算法粗粒度模型

粗粒度模型又被称作分布式模型或孤岛模型 ,是适应性最强和应用最广的遗传算法的并行模型.它将群体依照节点机(或处理器)的个数分成若干个子群体,各个子群体在各自的节点机(或处理器)上并发独自运行遗传算法，每经过一定的进化代，各个子群体间将交换若干个个体， 一方面用来引入更优良的个体，另一方面丰富了种群的多样性，达到了防止未成熟早收敛现象 。对于粗粒度模型，可以看出何时交换个体，交换哪些个体，采用什么方式交换是关键问题，因此目前对粗粒度模型的研究，主要是解决这几个方面的问题，也就是我们常说的如何确定迁移规模、迁移策略和迁移拓扑等问题。

并行遗传算法细粒度模型

细粒度模型又称作邻域模型, 在整个进化过程中虽然保持一个群体, 但要求子群体的划分要非常细小 ,最理想状态是每个节点机(或处理器)只有一个个体,要求各节点机(或处理器)具有极强的通信能力 ,对于每个染色体,选择和交叉操作都只在所处的节点机(或处理器)及其邻域中进行。 由于整个进行过程中 ,不需要或者需要很少的全局操作, 因此充分发挥了遗传算法并行特性。

并行遗传算法混合模型

混合模型是近些年快速发展起来的模型结构, 主要是通过把前面三种基本模型混合形成层次结构。目前混合模型组合关系主要有三种:粗粒度—细粒度、粗粒度—粗粒度和粗粒度—主从式。在形成的层次结构中,在下层的并行模型中,子群体的规模是真实的 ,即为一个处理进程所处理的个体数量。而对于上层模型，将每个下层的并结构都视为一个‘’集合子群体”，而“集合子群体”之间按上层的并行模型协调运行。对于此混合模型，无论在下层还是在上层，都是子群体内部信息交互量大，之间信息交互量小。

对于此四种模型, 哪种模型更好没有一个明确的标准 ,甚至对于不同问题往往得出互相矛盾的答案. 对于主从式模型,由于仅适用计算时间主要集中在适应度评估的问题 , 因此适用的范围受到了极大的限制 ;对于细粒度模型 , 是采用大范围的邻域模型 ,还是采用小范围直径也有争议,特别是由于对节点机(或处理器)的数量和通信能力要求很高 ,所以细粒度模型的应用范围也不广;对于粗粒度模型 ,虽然采用什么样的迁移拓扑 、迁移规模和迁移策略还需深入研究 ,但由于通信开销较小,可获得接近线性的加速比,而且非常适合运行在通信带宽较低的集群系统上, 因此得到了广泛的应用;混合模型是在前三种模型的基础上建立起来的, 由于具有很好的并行性特点,已成为人们研究的主流,但从应用效果看,目前只有粗粒度 —主从式模型应用较好

并行遗传算法评价并行遗传算法

为更好和更实用地评价并行遗传算法，文献1和文献2结合实际给出了两条评价并行遗传算法的指标：

(1) 确定一个适应度指标，分别利用串行遗传算法和并行遗传算法计算达到某一个个体适用度高于指定适用度指标的时间，然后让串行搜索时间除以并行搜索时间，作为并行遗传算法的加速比指标。

(2) 给定一定时间，利用 PGAs 进行优化，测量能够得到的最高适用度比利用串行遗传算法搜索到的最高适应度高出多少。

对于上面两条评价指标， 不难发现，第二条评价指标更具有实用价值。对于不同问题， 由于问题差异、群体大小及采用不同的局部搜索方法等等因素不同 ，评价模型得出的结果也会有差异，因此对于并行遗传算法评价模型仍需深一步研究。