遗传算法并行化的研究

《遗传算法并行化的研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、遗传算法并行化的研究学号：SC02011036姓名：黄鑫摘要木文是针对遗传算法并行化进行了研究，首先简要给出了基木遗传算法的形式化描述，然后做了并行性的分析，详细介绍了遗传算法的结构化并行模型：步进模型，岛屿模型，邻接模型，最后指出了进一步婆研究的课题。关键词:遗传算法，并行计算，结构化GA1引言遗传算法(GA)是根据达尔文进化论“优胜劣汰，适者生存”的一种卅发式捜索算法。釆用选择，交叉，变界等基本变化算子在解空间同吋进行多点搜索，本身固有并行性。随曹大规模并行机的迅速发展，将并行机的高速性与遗传算法并行性结合起來，从而促进遗传算法的发展。然而，仅仅将基本遗传算法硬件并行化伴随着人量通

2、讯开销等问题，从而必须对标准GA的进行改进，使得并行遗传算法不单单是遗传算法硬件并行实现，更重要的是结构化的遗传算法。本文首先给出了GA形式化描述，对基木GA的可并行性做出分析，然后给出了并行GA的模型，最后指出了并行遗传算法还需要解决的问题。2基本遗传算法在这里我们不对遗传算法做过多的介绍，只是给出基木遗传算法的形式化描述：begin(1)initialization(1.1)产生一个初始群体(1.2)评估第一代整个群体的适应度值(2)whilerunningdo(2.1)选择父代(2.2)交叉操作(2.3)了代变异(2.4)评估子代的适应度(2.5)子代取代父代，形成新的一带个体e

3、ndwhileend3遗传算法的并行性分析从笫一节对遗传算法的描述，我们可以看出基本遗传算法模型是一个反复迭代的进化计算过程，通过对一组表示候选解的个体进行评价、选择、交叉、变异等操作，来产生新一代的个体(候选解)，这个迭代过程直到满足某种结束条件为止。对应于基本遗传算法的运行过程，为实现其并行化耍求，可以从下面四种并行性方面着手对其进行改进和发展。并行性I:个体适应度评价的并行性。个体适应度的评价在遗传算法中占•用的运行时间比较人。通过对适应度并行计算方法的研究，可提高个体适应度评价的计算效率。并行性II：整个群体各个个体适应度评价的并行性。群体屮各个个体适应度的评价过程无相互依赖关

4、系，这样各个个体适应度的评价或计算过程就可以相互独立、相互并行地在不同的处理机上同吋进行。并行性III:了代群体产生过程的并行性。从父代群体屮产牛下一代群体所需进行的选择、交义、变异等遗传操作可以独立并行地进行。并行性IX基于群体分组的并行性。群体中的单个或一组个体的述化过程可以相互独立地进行，在适当的时候，它们再以适当的方式交换信息。即不同个体或不同组个体的进化过程是同时进行的。在上述四种并行方式屮，前三种方式并未从总休上改变简单遗传算法的特点，第四种并行方式却对简单遗传算法的结构有较人的改变，并且这种方式也最自然，在并行机或局域网环境下实现起来也最简单，所以受到了人们较大的重视。冃

5、前已开发出的并行遗传算法棊本上都是基于上述四种并行机制或其组合来实现的。4遗传算法的并行化为提高遗传算法的运算速度、改善其性能，人们在并行机或局域网环境下开发出了一些并行遗传算法。概括起来，这些方法人体可分为如下两类：1标准并行方法；2分解型并行方法。4.1标准并行方法（standardparallelapproach）这类方法并不改变简单遗传算法的棊木结构特点，即群体中的全部都在统一的环境屮进化。其基本出发点是从局部的角度开发个体进化的并行性。在应川遗传算法进行优化计算时，各个个体的适应度计算、选择、变界等操作是可以相互独立进行的。这样，利用共厚存贮器结构的并行机，就可对群体的进化过

6、程进行并行计算以达到提高遗传算法运行速度的口的。这类方法在适应度计算量较大的场合是比较有效的，上一节所介绍的前三种并行性都可以通过这类方法來实现。但另一方面，由于并行机之间通信等的限制，选择、交叉、变异等遗传操作的对象集屮在一个处理机上较为方便,所以这类方法的应用受到一•些限制，在有些场合应用效果不A明显。这种并行方法的一个典型例了是由T.C.Fogarty等开发的一个基于共享存贮器方式的并行遗传算法，该算法将全部群体存放在一个共享的存贮器中，各处理机并行评价各个个体的适应度。4.2分解型并行方法（decompositionparallelapproach）这种方法是将整个群体划分为几

7、个了群体，各个了群体分配在各自的处理机或局域网工作站上独立地进行简单遗传算法的进化操作，在适当的时候各个子群体Z间相互交换一些信息。其基本出发点是从全局的角度开发群体进化的并行性。这种方法改变了简单遗传算法的基木特点，各了群体独立地进行进化，而不是全部群体采川同一机制进化。它是实现上述第4种并行性的方法，并且是一个简单常用、易于实现的方法。这种方法不仅能够提高遗传算法的运算速度，而且由于保持了各处理机上了群体进化的局部特性，还能够有效地冋避遗传