遗传算法并行化的研究..docVIP

遗传算法并行化的研究 学号：S 姓名：黄鑫 摘要 本文是针对遗传算法并行化进行了研究，首先简要给出了基本遗传算法的形式化描述，然后做了并行性的分析，详细介绍了遗传算法的结构化并行模型：步进模型，岛屿模型，邻接模型，最后指出了进一步要研究的课题。 关键词 ：遗传算法，并行计算，结构化GA 引言 遗传算法（GA）是根据达尔文进化论“优胜劣汰，适者生存”的一种启发式有哪些信誉好的足球投注网站算法。采用选择，交叉，变异等基本变化算子在解空间同时进行多点有哪些信誉好的足球投注网站，本身固有并行性。随着大规模并行机的迅速发展，将并行机的高速性与遗传算法并行性结合起来，从而促进遗传算法的发展。然而，仅仅将基本遗传算法硬件并行化伴随着大量通讯开销等问题，从而必须对标准GA的进行改进，使得并行遗传算法不单单是遗传算法硬件并行实现，更重要的是结构化的遗传算法。本文首先给出了GA形式化描述，对基本GA的可并行性做出分析，然后给出了并行GA的模型，最后指出了并行遗传算法还需要解决的问题。 2 基本遗传算法 在这里我们不对遗传算法做过多的介绍，只是给出基本遗传算法的形式化描述： begin initialization 产生一个初始群体 评估第一代整个群体的适应度值 （2）while running do 选择父代 交叉操作 子代变异 评估子代的适应度 子代取代父代，形成新的一带个体 endwhile end 3 遗传算法的并行性分析 从第一节对遗传算法的描述，我们可以看出基本遗传算法模型是一个反复迭代的进化计算过程，通过对一组表示候选解的个体进行评价、选择、交叉、变异等操作，来产生新一代的个体(候选解)，这个迭代过程直到满足某种结束条件为止。对应于基本遗传算法的运行过程，为实现其并行化要求，可以从下面四种并行性方面着手对其进行改进和发展。 并行性Ⅰ：个体适应度评价的并行性。 个体适应度的评价在遗传算法中占用的运行时间比较大。通过对适应度并行计算方法的研究，可提高个体适应度评价的计算效率。 并行性Ⅱ：整个群体各个个体适应度评价的并行性。 群体中各个个体适应度的评价过程无相互依赖关系，这样各个个体适应度的评价或计算过程就可以相互独立、相互并行地在不同的处理机上同时进行。 并行性Ⅲ：子代群体产生过程的并行性。 从父代群体中产生下一代群体所需进行的选择、交叉、变异等遗传操作可以独立并行地进行。 并行性Ⅳ：基于群体分组的并行性。 群体中的单个或一组个体的进化过程可以相互独立地进行，在适当的时候，它们再以适当的方式交换信息。即不同个体或不同组个体的进化过程是同时进行的。在上述四种并行方式中，前三种方式并未从总体上改变简单遗传算法的特点，第四种并行方式却对简单遗传算法的结构有较大的改变，并且这种方式也最自然，在并行机或局域网环境下实现起来也最简单，所以受到了人们较大的重视。目前已开发出的并行遗传算法基本上都是基于上述四种并行机制或其组合来实现的。 4 遗传算法的并行化 为提高遗传算法的运算速度、改善其性能，人们在并行机或局域网环境下开发出了一些并行遗传算法。概括起来，这些方法大体可分为如下两类：1标准并行方法；2分解型并行方法。 4．1标准并行方法(standard parallel approach) 这类方法并不改变简单遗传算法的基本结构特点，即群体中的全部都在统一的环境中进化。其基本出发点是从局部的角度开发个体进化的并行性。在应用遗传算法进行优化计算时，各个个体的适应度计算、选择、变异等操作是可以相互独立进行的。这样，利用共享存贮器结构的并行机，就可对群体的进化过程进行并行计算以达到提高遗传算法运行速度的目的。这类方法在适应度计算量较大的场合是比较有效的，上一节所介绍的前三种并行性都可以通过这类方法来实现。但另一方面，由于并行机之间通信等的限制，选择、交叉、变异等遗传操作的对象集中在一个处理机上较为方便，所以这类方法的应用受到一些限制，在有些场合应用效果不太明显。 这种并行方法的一个典型例子是由T.C.Fogarty等开发的一个基于共享存贮器方式的并行遗传算法，该算法将全部群体存放在一个共享的存贮器中，各处理机并行评价各个个体的适应度。 4．2分解型并行方法(decomposition parallel approach) 这种方法是将整个群体划分为几个子群体，各个子群体分配在各自的处理机或局域网工作站上独立地进行简单遗传算法的进化操作，在适当的时候各个子群体之间相互交换一些信息。其基本出发点是从全局的角度开发群体进化的并行性。这种方法改变了简单遗传算法的基本特点，各子群体独立地进行进化，而不是全部群体采用同一机制进化。它是实现上述第4种并行性的方法，并且是一个简单常用、易于实现的方法。这种方法不仅能够提高遗传算法的运算速度，而且由于保持了各处理机上子群体进化的局部特性，还