并行遗传算法

《并行遗传算法》由会员分享，可在线阅读，更多相关《并行遗传算法（19页珍藏版）》请在金锄头文库上搜索。

1、并行遗传算法并行实验室遗传的基本概念 遗传算法（genetic algorithms,简称GA）是 J.Holland于1975年受生物进化论的启发而提出 来的。GA是基于“适者生存”的一种高度并行、随 机和自适应的优化算法，它将问题的求解表示成“ 染色体”适者生存的过程，通过“染色体”群的一代 代不断进化，包括复制、交叉和变异等操作，最 终收敛到“最适应环境”的个体，从而求得问题的 最优解或满意解。 优点：隐含并行性全局解空间搜索能力遗传与算法的对应 遗传算法通过模拟自然界优胜劣汰的进化 现象，将搜索空间映射为遗传空间，把可 能的解编码成一个向量（即染色体），向 量的每个元素称为基因，然后通

2、过不断计 算各染色体的适应度值，选择最好的染色 体，获得最优解。遗传算法的基本步骤确定决策变量及各种约束条件，即确定个 体的表现型X和问题的解空间； 建立优化模型，即确定目标函数的类型； 确定表示可行解的染色体编码方案，即确 定出个体的基因型X及遗传算法的搜索空 间； 确定编码方法，即确定出由基因型X到个 体表现型X的对应关系或转换方法； 确定个体适应度的量化评价方法，即确定 由目标函数值f(x)到个体适应度F(x)的变 换规则； 设计遗传算子，即确定出选择、交叉、变 异的具体操作方法； 确定遗传算法的有关运行参数，即确定遗 传算法的Pc,Pm等参数。特点 遗传算法以决策变量的编码作为运算对象

3、； 遗传算法直接以目标函数值作为搜索信息，它使 用由目标函数值变换得到的适应度函数值作为下 一步搜索方向和范围的判断标准； 遗传算法同时使用多个搜索点的搜索信息。它是 从很多个体所组成的一个初始群体开始最优解的 搜索，而不是从单一的个体开始搜索。这样可以 避免一些不必要的搜索，其实内在包含了算法的 隐含并行性； 遗传算法属于非确定性的概率算法。正是由于它 的不确定和概率性，导致算法找到的解只能够是 相对最优解。遗传算法的实现 确定问题的编码方案 确定适配值函数 设计遗传算子 算法参数选择，主要包括种群数目、交叉 与变异概率、进化代数等。 确定算法的终止条件。编码 编码就是将问题的解用一种计算机

4、可以识别的码 来表示，将问题空间的状态空间与GA的码空间相 对应。GA的优化过程是在一定编码机制对应的码 空间上进行的，因此编码的选择是影响算法性能 与效率的重要因素。 编码方式：二进制编码方法格雷码编码方法浮点数编码方法 通常所采用的编码方式是二进制编码。二进制编码方法二进制编码所构成的个体基因是一个经过编码的符号串，二进制编码符号串的长 度和问题的精度有关。假设问题的参数取值范围是Umin,Umax,使用长度为L的 二进制编码符号串表示该参数，则能产生2L种不同的编码。 若参数的编码的对应关系如下：000000000000=0Umin000000000001=1 Umin+11111111

5、1111= 2L-1 Umax二进制的编码精度为：设每个个体的编码为：对应的解码公式：适配值函数 适配值函数用于对个体进行评价，是优化 过程发展的依据。 在简单问题的优化时，通常可以将目标函 数直接变换成适配值函数，譬如将个体X的 适配值f(x)定义为M-c(x)或eac(x),其中M为 一足够大正数，c(x)为个体的目标值，a0 。在复杂问题的优化时，往往需要构造合 适的评价函数，适应GA进行优化。算法参数选择 种群的数目：影响算法优化性能和效率。种群太小导致采 样点数目不足，算法性能低；而种群数目太大又会增加计 算量，导致收敛时间过长。所以在设计算法时应该针对具 体问题选择适宜的种群数目；

6、 交叉概率：用于控制交叉操作的频率。概率太大，种群中 串的更新很快，会使高适配值的个体很快被破坏掉；概率 太小，交叉操作很少进行，会使搜索停止不前； 变异概率：增加种群多样性。基于二进制编码的GA中， 一个非常小的变异率就会改变整个种群的基因。变异概率 必须取一个适当的值，太小不会产生新个体，太大又会使 GA完全的随机搜索；总结：遗传算法参数的选择是非常重要的，同时也非常复 杂，参数选取需要按照问题的实际大小来进行选择。选择算子选取选择的定义：从群体中选择优秀的个体，淘汰劣质个体的操作。 选择算子的作用：将优化的解直接遗传到下一代，或通过配对交叉的方式遗传到 下一代。 常用选择算子：适应度比例

7、法，也叫赌轮法或蒙特卡罗法。 选择执行过程：1)计算出群体中所有个体适应度的总值；2)计算每个个体相对适应度，即个体遗传到下一代的概率；3)使用模拟赌轮操作(srand(0,1)来确定各个个体被选中的次数。假设群体的大小为n，其中个体i的适应度值为fi，个体i被选择的概率pi表示为Pi反映了个体i的适应度在整个群体的个体适应度总和中所占的比例。适应度越高 ，被选中的概率越高。算法终止条件 在实际中算法是不允许无止境的发展下去 的，而且对通常问题的最优解具有不确定 性，因此需要一个条件来终止算法的进程 。目前最常用的终止条件是事先给定一个 最大进化步数，或者判断最佳优化值是否 连续且经过若干步后

8、都没有变化等。隐含并行性 设为一小正数，L (l-1)+1,N=2l,2，则遗传 算法一次处理的存活概率不小于1- 且定义 长度不大于L的模式数位O（N3）. 遗传算法表面上仅对每代的N个个体作处理 ，但实际上并行处理了大约O（N3）个模 式，并且无额外的存储，这正是遗传算法 具有高校搜索能力的原因，这就是遗传算 法的隐含并行。并行遗传算法 传统的遗传算法出现的问题：局部搜索性能较差，对某些分布变化缓慢，面对大型计算 问题速度难以达到要求 并行遗传算法提出：在遗传算法并行运算的基础上，通过多种群并行进化和引 入迁移算子进行进行种群之间的信息交流，实现多种群的 协同进化。通过人工选择系数对每个种

9、群最优化个体保存 ，通过对协调种群间的信息交换策略得到最好的进化效果 。 遗传算法的并行化实现就是将进化过程划分到不同的计算 节点上，进行分布式进化，并通过一定的种群间信息交换 策略实现优良基因的转换。并行遗传算法的分类 标准型并行方法：未改变串行遗传算法的基本特点，在一个总体的环 境中实现进化运算，它需要使用一个统一的群体。实现时需要一个全 局存储器和一个统一的控制机构来协调群体的遗传进化过程及群体之 间的通信过程。缺点：运行速率低。 分解型并行方法：将整个群体分解为几个子群体，各子群体彼此分配 在不同的节点上，各自运行自身节点上的遗传算法，在适当的时候各 节点之间交换信息。这种实现方法比较

10、符合个体自然进化的过程，保 存了各节点上群体进化的局部特性，有效回避了普通遗传算法早熟现 象。 目前比较常用的类型是分解型并行方法，按照不同的组织结构，它又 可以分为下面三种不同的类型： 主从式并行计算 粗粒度并行计算 细粒度并行计算主从式并行计算 在这种并行方式中，一个主过程调节若干个仆过程。其中 主过程控制选择、交叉和变异，仆过程仅执行适配值的计 算。 缺点：1、各仆过程计算适应度值的时间存在明显差异时 ，将会照成整个系统长时间的等待；2、整个系统可靠性 较差，对主过程状况的依赖性较大。 伪代码： Begin (1)产生一个初始群体 (2)while running do (2.1)for

11、 =1 to s do 计算个体i的适应度值(并行部分) （2.2）选择、交叉、变异操作，产生子代 （2.3）子代取代父代，形成新一代个体 End while End粗粒度并行算法在自然界中，物种的群体系由一些子群体构成。在处理器比较少的情况下，可以将群体分为若干个 子群体，每个子群体包含一些个体，每个群体分配一个处理器，让它们互相独立的并行执行进化， 每经过一定的间隔（即若干个进化带），就把最佳个体迁移到相邻的子群体中。 算法代码： Begin (1)产生一个初始群体并将它划分为p个子群体 (2)for 1 to p do /*P表示处理器个数，也是子群体的个数 (2.1)初始化 (2.2)

12、评估第一代子群体的适应度 (2.3)while condition to (2.3.1)for J=1 to H(generations)do a、选择父代 b、交叉操作 c、子代变异 d、子代取代父代形成新一代子群体 e、评估子代的适应度 end for (2.3.2)选择要迁移出去的个体 (2.3.3)do step a and b in parallel /*这里发送和接收进程是并发执行的 a、发送要迁出的个体 b、接手迁入的个体 end while end for end细粒度并行算法如果并行系统中有足够多的处理器，那么系统可以为每个个体分配一个处理器，让它 们相互独立的并行执行进程，这样就能获得并行遗传算法的最大可能的并发性。 代码： Begin (1)产生一个初始群体并将它分配到P=N个处理器上； (2)For=1 to N do while running do (2.1)do step (a) and (b) in parallel (a)接收迁入个体 (b)发送本个体 (2.2)对迁入个体进行适应度评估 (2.3)从迁入的个体中选择对象 (2.4)交叉操作 (2.5)子代变异 (2.6)评估本个体及其后代 (2.7)用后代取代本个体end while End for End谢谢大家！