基于杰出选择策略的伪并行遗传算法.pdf

35№．4B 计算机科学2008VoL 基于杰出选择策略的伪并行遗传算法*) 徐金荣1李允1唐苗苗2 (西南交通大学信息科学与技术学院 成都610031)1(成都中医药大学临床医学院 成都610075)2 摘要为了解决遗传算法(GA)中存在的早熟收敛、收敛速度慢等问题，提出了一种基于杰出选择策略的伪并行遗 传算法(ESPP_．GA)。该算法从遗传算子以及并行计算等几个方面对其作了改进，使用了杰出选择模型和邻居群体模 型。杰出选择模型能将当代最优个体保留下来，邻居群体模型用来增加种群的多样性。基于典型复杂函数的优化仿 真结果表明，ESPP_GA算法比标准遗传算法(SGA)有更好的收敛性和更高的精度，显著地提高了收敛速度和搜索全 局最优解的能力。 关键词遗传算法，伪并行，杰出选择模型，邻居群体模型 ①种群遗传代数计数器初始化：初始化种群Po(￡)，t=O， 1 引言 GEN=O，t表示伪并行代数，GEN表示实际代数，G斟=N 遗传算法(Genetic ‘fo Algorithm，简称GA)[1]是模拟生物 在自然环境中的遗传和进化过程而形成的一种自适应全局优 ②将初始群体Po(￡)随机划分为n个子群体： 化概率搜索算法。它最早由美国密执安大学的Holland教授 Po(￡)={P1(z)，P2(￡)，…，Pf(￡)，…，只(￡)} 提出，起源于20世纪60年代对自然和人工自适应系统的研其中，九为分组数。 究‘21。 ③对各群体Pi(f)(i=1，2，…，n)，采用杰出选择策略进 Genetic 标准遗传算法(StandardAlgorithms，简称行分组独立进化，各分组进化后的群体为Pi(f)(i--1，2，…， SGA)[3]作为一种通用的自适应随机搜索算法，还存在着早熟恕)。 收敛和收敛速度慢这两大难题“]，而影响它的一个关键因素 ④分组计算各Pi(￡)(i=1，2’．．·，砣)中个体的适应度，并 就是“种群多样性”。种群多样性差，就会使得算法搜索空间 保存它们。 减小，进而导致算法错误地收敛到局部最有解，即早熟收 ⑤采用邻居群体模型对子群体Pi(f)(i=1，2，…，九)进行 敛[5]。虽然SGA算法中可以通过交叉算子和变异算子来增操作，获得下一代子群体，见式1。 加种群的多样性，但是交叉概率和变异概率会直接影响算法 ⑥各子群体Pt(f)(i一1，2，…，竹)一起汇人到进化池，形 的收敛性和收敛速度[6]。交叉概率越大，新个体产生的速度 成下一代的初始种群Po(￡+1)，供产生分组用。 越快，但具有高适应度的个体结构被破坏的可能性也越大[7]。 ⑦终止条件判断。若不满足终止条件，则：￡++，刚 变异概率过小不易产生新的个体结构，过大则可能变为简单 一GEN+N，转向第②步；若满足终止条件，则：输出优化结 果，算法结束。 的随机搜索，从而减低收敛速度[8]。所以在SGA算法中，种 群多样性很大程度上决定于交叉算子和变异算子这两个操 ESPP_GA算法的主要构造过程如图1所示。初始群体 作。 P(f)经过随机分组后，产生挖个子群体，分别对各子群体使用 为了加快算法的收敛速度，提高搜索精度，本文提出一种 杰出选择模型和邻居群体模型进行操作，以便产生新一代之 Ge- 群体。杰出选择模型的作用是执行选择，交叉，变异操作，邻 基于杰出选择策略的伪并行遗传算法(Pseudo-Parallel netic