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

《基于杰出选择策略的伪并行遗传算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机科学2008VoL35№．4B基于杰出选择策略的伪并行遗传算法*)徐金荣1李允1(西南交通大学信息科学与技术学院成都610031)1唐苗苗2(成都中医药大学临床医学院成都610075)2摘要为了解决遗传算法(GA)中存在的早熟收敛、收敛速度慢等问题，提出了一种基于杰出选择策略的伪并行遗传算法(ESPP_．GA)。该算法从遗传算子以及并行计算等几个方面对其作了改进，使用了杰出选择模型和邻居群体模型。杰出选择模型能将当代最优个体保留下来，邻居群体模型用来增加种群的多样性。基于典型复杂函数的优化仿真结果表明，ESPP_GA算法比标准遗传算法(SGA)有更好的收敛

2、性和更高的精度，显著地提高了收敛速度和搜索全局最优解的能力。关键词遗传算法，伪并行，杰出选择模型，邻居群体模型1引言遗传算法(GeneticAlgorithm，简称GA)[1]是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密执安大学的Holland教授提出，起源于20世纪60年代对自然和人工自适应系统的研究‘21。标准遗传算法(StandardGeneticAlgorithms，简称SGA)[3]作为一种通用的自适应随机搜索算法，还存在着早熟收敛和收敛速度慢这两大难题“]，而影响它的一个关键因素就是“种群多样性”。种群

3、多样性差，就会使得算法搜索空间减小，进而导致算法错误地收敛到局部最有解，即早熟收敛[5]。虽然SGA算法中可以通过交叉算子和变异算子来增加种群的多样性，但是交叉概率和变异概率会直接影响算法的收敛性和收敛速度[6]。交叉概率越大，新个体产生的速度越快，但具有高适应度的个体结构被破坏的可能性也越大[7]。变异概率过小不易产生新的个体结构，过大则可能变为简单的随机搜索，从而减低收敛速度[8]。所以在SGA算法中，种群多样性很大程度上决定于交叉算子和变异算子这两个操作。为了加快算法的收敛速度，提高搜索精度，本文提出一种基于杰出选择策略的伪并行遗传算法(Pseudo-Pa

4、rallelGe-neticAlgorithmBasedonElitistSelectionStrategy，简称E孓PP_A)[9]。该算法在SGA算法的基础之上使用了杰出选择策略[1刨和伪并行计算策略，这两种策略的应用能够有效地解决遗传算法中早熟收敛和收敛速度慢两大难题。2EqPP-GA算法思想．．在遗传算法的应用过程中，为了提高遗传算法运算速度而引入的并行遗传算法，除了能够提高运算速度外，也有维持群体多样性的能力，从而有可能抑制早熟现象的发生，但并行遗传算法一般要求运行在并行机或局域网上，而对于许多的问题，我们不需要如此高档的运行环境，ESPP—GA算法就

5、是一种利用并行遗传算法思想，在单处理器上运行的伪并行遗传算法。ESPP_GA算法的具体步骤如下：①种群遗传代数计数器初始化：初始化种群Po(￡)，t=O，GEN=O，t表示伪并行代数，GEN表示实际代数，G斟=N‘fo②将初始群体Po(￡)随机划分为n个子群体：Po(￡)={P1(z)，P2(￡)，⋯，Pf(￡)，⋯，只(￡)}其中，九为分组数。③对各群体Pi(f)(i=1，2，⋯，n)，采用杰出选择策略进行分组独立进化，各分组进化后的群体为Pi(f)(i--1，2，⋯，恕)。④分组计算各Pi(￡)(i=1，2’．．·，砣)中个体的适应度，并保存它们。⑤采用邻居

6、群体模型对子群体Pi(f)(i=1，2，⋯，九)进行操作，获得下一代子群体，见式1。⑥各子群体Pt(f)(i一1，2，⋯，竹)一起汇人到进化池，形成下一代的初始种群Po(￡+1)，供产生分组用。⑦终止条件判断。若不满足终止条件，则：￡++，刚一GEN+N，转向第②步；若满足终止条件，则：输出优化结果，算法结束。ESPP_GA算法的主要构造过程如图1所示。初始群体P(f)经过随机分组后，产生挖个子群体，分别对各子群体使用杰出选择模型和邻居群体模型进行操作，以便产生新一代之群体。杰出选择模型的作用是执行选择，交叉，变异操作，邻居选择模型用于交换相邻子群间的信息，目的

7、是增强群体的多样性。ESPP_GA算法中使用这两种模型能够有效地解决遗传算法中早熟收敛和收敛速度慢两大难题。fNeighbor_!Vlodel[Pi(f)，Pi+l(z)](i：1，2，⋯，N一1)以件D21Neighbor_Model[一Pi∽，P1(踟Q’(￡)，P1(z)]【(i：N)3ESPP_GA算法实现ESPPGA算法是在简单遗传算法中利用并行遗传算法的思想，将群体划分为一些子群体，各子群体按照一定的模式分别进行独立的进化，在适当的时候某一些群体之间交换一些信息。ESPP_GA算法中，子群体之间信息交换模型采用的是邻居群体模型。这样可以维持群体的多样

8、性，从而达到*)基金项目