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

遗传算法并行化研究
学号: SC0036
姓名: 黄鑫
摘要
本文是针对遗传算法并行化进行了研究, 首先简明给出了基础遗传算法形式化描述, 然后做了并行性分析, 具体介绍了遗传算法结构化并行模型: 步进模型, 岛屿模型, 邻接模型, 最终指出了深入要研究课题。
关键词 : 遗传算法, 并行计算, 结构化GA
1 引言
遗传算法（GA）是依据达尔文进化论“优胜劣汰, 适者生存”一个启发式搜索算法。采取选择, 交叉, 变异等基础改变算子在解空间同时进行多点搜索, 本身固有并行性。伴随大规模并行机快速发展, 将并行机高速性与遗传算法并行性结合起来, 从而促进遗传算法发展。然而, 仅仅将基础遗传算法硬件并行化伴伴随大量通讯开销等问题, 从而必需对标准GA进行改善, 使得并行遗传算法不单单是遗传算法硬件并行实现, 更关键是结构化遗传算法。本文首先给出了GA形式化描述, 对基础GA可并行性做出分析, 然后给出了并行GA模型, 最终指出了并行遗传算法还需要处理问题。
2 基础遗传算法
在这里我们不对遗传算法做过多介绍, 只是给出基础遗传算法形式化描述:
begin
(1) initialization
(1.1) 产生一个初始群体
(1.2) 评定第一代整个群体适应度值
（2）while running do
(2.1) 选择父代
(2.2) 交叉操作
(2.3) 子代变异
(2.4) 评定子代适应度
(2.5) 子代替换父代, 形成新一带个体
endwhile
end
3 遗传算法并行性分析
从第一节对遗传算法描述, 我们能够看出基础遗传算法模型是一个反复迭代进化计算过程, 经过对一组表示候选解个体进行评价、 选择、 交叉、 变异等操作, 来产生新一代个体(候选解), 这个迭代过程直到满足某种结束条件为止。对应于基础遗传算法运行过程, 为实现其并行化要求, 能够从下面四种并行性方面着手对其进行改善和发展。
并行性Ⅰ: 个体适应度评价并行性。
个体适应度评价在遗传算法中占用运行时间比较大。经过对适应度并行计算方法研究, 可提升个体适应度评价计算效率。
并行性Ⅱ: 整个群体各个个体适应度评价并行性。
群体中各个个体适应度评价过程无相互依靠关系, 这么各个个体适应度评价或计算过程就能够相互独立、 相互并行地在不一样处理机上同时进行。
并行性Ⅲ: 子代群体产生过程并行性。
从父代群体中产生下一代群体所需进行选择、 交叉、 变异等遗传操作能够独立并行地进行。
并行性Ⅳ: 基于群体分组并行性。
群体中单个或一组个体进化过程能够相互独立地进行, 在合适时候, 它们再以合适方法交换信息。即不一样个体或不一样组个体进化过程是同时进行。在上述四种并行方法中, 前三种方法并未从总体上改变简单遗传算法特点, 第四种并行方法却对简单遗传算法结构有较大改变, 而且这种方法也最自然, 在并行机或局域网环境下实现起来也最简单, 所以受到了大家较大重视。现在已开发出并行遗传算法基础上都是基于上述四种并行机制或其组合来实现。
4 遗传算法并行化
为提升遗传算法运算速度、 改善其性能, 大家在并行机或局域网环境下开发出了部分并行遗传算法。概括起来, 这些方法大致可分为以下两类: 1标准并行方法; 2分解型并行方法。
4．1标准并行方法(standard parallel approach)
这类方法并不改变简单遗传算法基础结构特点, 即群体中全部都在统一环境中进化。其基础出发点是从局部角度开发个体进化并行性。在应用遗传算法进行优化计算时, 各个个体适应度计算、 选择、 变异等操作是能够相互独立进行。这么, 利用共享存贮器结构并行机, 就可对群体进化过程进行并行计算以达成提升遗传算法运行速度目。这类方法在适应度计算量较大场所是比较有效, 上一节所介绍前三种并行性都能够经过这类方法来实现。但其次, 因为并行机之间通信等限制, 选择、 交叉、 变异等遗传操作对象集中在一个处理机上较为方便, 所以这类方法应用受到部分限制, 在有些场所应用效果不太显著。
这种并行方法一个经典例子是由T.C.Fogarty等开发一个基于共享存贮器方法并行遗传算法, 该算法将全部群体存放在一个共享存贮器中, 各处理机并行评价各个个体适应度。
4．2分解型并行方法(decomposition parallel approach)
这种方法是将整个群体划分为多个子群体, 各个子群体分配在各自处理机或局域网工作站上独立地进行简单遗传算法进化操作, 在合适时候各个子群体之间相互交换部分信息。其基础出发点是从全局角度开发群体进化并行性。这种方法改变了简单遗传算法基础特点, 各子群体独立地进行进化, 而不是全部群体采取同一机制进化。它是实现上述第4种并行性方法, 而且是一个简单常见、 易于实现方法。这种方法不仅能够提升遗传算法运算速度, 而且因为保持了各处理机上子群体进化局部特征, 还能够有效地回避遗传算法早熟现象。结构这种并行遗传算法时, 需要考虑下述多个关键问题:
.子群体划分方法
1.整个群体均匀地分配到各个处理机方法(是粗粒度分配, 还是细粒度分配? )。
.交换信息方法
①参与信息交换对象(哪多个处理机之间能够交换信息? );
②交换信息内容(是交换, 还是择优交换? );
③交换时间或频率(何时交换? );
④交换信息量(交换多个个体? )。
据对这多个问题不一样处理, 组成了不一样类型群体交换模型, 亦即形成了不一样并行遗传算法。
⑴步进模型(stepping-stonemodel)这个模型各个子群体中所含个体数量多于1, 各个子群体在其处理机上并行独立地运行简单遗传算法, 子群体之间信息交换只能是在地理上邻接处理机之间进行。该模型因为对处理机之间通信要求不高, 所以实现起来比较简单。图1为步进模型示例。

图1步进模型
⑵岛屿模型(island model)这个模型也叫做粗粒度并行遗传算法(coarse-grainedPGA)。该模型每个处理机上子群体所含个体数量多于1, 各个子群体在其各自处理机上并行独立地运行简单遗传算法, 而且时间间隔、 在选择处理机之间交换个体信息。这种模型适适用于MIMD机器, 如基于Transputer多处理机系统。

图2岛屿模型
现在我们给出岛屿模型形式化语言描述
begin
(1) 产生一个初始群体并将它划分成p个子群体
(2) for i=1 to par-do
(2.1)初始化
（2.2）评定第一代子群体适应度
（2.3）while running do
(2.3.1)for j=1 to n(generations) do
(a) select parents
(b) reproduce
(c) mutate offspring
(d) replace parents
(e) evaluate sub-population
(2.3.2)select emigrants
(2.3.3)do step(a)and (b) in parallel
(a) send emigrants
(b) receive immigrants
endwhie
endfor
end
⑶邻接模型(neighborhood model)这个模型也叫做细粒度并行遗传算法(fine-grainedPGA)。该模型中每个处理机上只分配一个个体, 即子群体只由一个个体组成, 每个子群体只和与其海明距离为1“邻接”子群体相互交换信息。由该模型特点可知, 即使群体中某一个体适合度较高, 其作用也仅仅是逐步地才能到其邻近个体, 所以它能够有效地维持群体多样性, 有效地抑制早熟现象。这种模型适适用于SIMD系统, 如阵列式多处理器系统或连接机。

邻接单元

图3 邻接模型

5． 展望
尽管并行GA研究已经取得了很大进步, 在部分实际应用问题上达成了良好效果。然而, 还有大量前沿方向需要我们深入去研究。比如, 怎样处理动态函数优化问题, 并行GA理论研究, 并行GA关键参数对结果影响, 并行GA收敛性怎样, 并行GA与其她优化算法比较, 全部这些都要我们以后去处理。总来说, 并行GA有着良好发展和应用前景。
参考文件
[1]陈国良, 王熙法, 庄镇泉, 王东生, 《遗传算法及其应用》, 人民邮电出版社 1996
[2]S.Joachim.ParallelGeneticAlgorithms:TheoryandApplications.ISOPress,1993
[3]E.G.TalbiandP.Bessiere.AParallelGeneticAlgorithmfortheGraphPartitioningProblem.In:Proc.ofthe1991Int.Conf.onSupercomputing.ACMPress,1991,312-320
[4]Enrique Alba,Marco Tomassini,Parallelism and Evolutionary Algorithms, IEEE Transaction on Evolutionary Computation,vol 6,NO.5,OCTOBER