遗传算法的并行实现

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

1、BEIJID UNIVk HSITY OF TE+IN(MJKiY（基于遗传算法求函数最大值）指导老师：刘建丽学 号：S201007156姓 名：杨平班 级：研10级1班遗传算法一、遗传算法的基本描述遗传算法（GeneticAlgorithm, GA）是通过模拟自然界生物进化过程来求解 优化问题的一类自组织、自适应的人工智能技术。它主要基于达尔文的自然进化 论和孟德尔的遗传变异理论。多数遗传算法的应用是处理一个由许多个体组成的 群体，其中每个个体表示问题的一个潜在解。对个体存在一个评估函数来评判其 对环境的适应度。为反映适者生存的思想，算法中设计一个选择机制，使得：适 应度好的个体有更多的机会

2、生存。在种群的进化过程中，主要存在两种类型的遗 传算子：杂交和变异。这些算子作用于个体对应的染色体，产生新的染色体，从 而构成下一代种群中的个体。该过程不断进行，直到找到满足精度要求的解，或 者达到设定的进化代数。显然，这样的思想适合于现实世界中的一大类问题，因 而具有广泛的应用价值。遗传算法的每一次进化过程中的，各个体之间的操作大 多可以并列进行，因此，一个非常自然的想法就是将遗传算法并行化，以提高计 算速度。本报告中试图得到一个并行遗传算法的框架，并考察并行化之后的一些 特性。为简单起见（本来应该考虑更复杂的问题，如TSP。因时间有些紧张，做 如TSP等复杂问题怕时间不够，做不出来，请老师

3、原谅），考虑的具有问题是： 对给定的正整数n、n元函数f，以及定义域D，求函数f在D内的最大值。二、串行遗传算法1 染色体与适应度函数对函数优化问题，一个潜在的解就是定义域D中的一个点（x ,xx ），因01n -1此，我们只需用一个长度为n的实数数组来表示一个个体的染色体。由于问题中 要求求函数f的最大值，我们可以以个体所代表点（x ,x x ）在f函数下的值0 1n -1来判断该个体的好坏。因此，我们直接用函数f作为个体的适应度函数。2选择机制选择是遗传算法中最主要的机制，也是影响遗传算法性能最主要的因素。若 选择过程中适应度好的个体生存的概率过大，会造成几个较好的可行解迅速占据 种群，从

4、而收敛于局部最优解；反之，若适应度对生存概率的影响过小，则会使 算法呈现出纯粹的随机徘徊行为，算法无法收敛。下面我们介绍在实验中所使用 的选择机制。我们定义P为当前种群内所有个体的集合，x(0), X,，X( n -1)为P中所有个体的 一个固定排列。若X G P为某一个体，f (X )表示该个体的适应度，则种群戶的 适应度定义为：n 1s (P ) = Y f (X( i”i - 0对任意个体x g P，x的相对适应度定义为r (x ) = f (x ) / s (P )。相 对适应度r(x)反映了个体x的适应度在整个适应度总和中所占的比例。个 体适应度越高，被选中的概率越高。累积适应度定义

5、为：kc (x(k)=工 r (x(i)进行选择之前，先产生一个0到1之间的随机实数t，若满足 r(xk ) t r xk +i )则第k+1个个体被选中。循环以上过程，即得到生成下一代 种群的母体。具体实现见如下函数：void pop_select(void) int mem, i, j, k;double sum = 0;double p;/*计算种群适应度之和*/for (mem = 0; mem POPSIZE; mem+) /*按照累积适应度概率选取母体种群*/ for (i = 0; i POPSIZE; i+) p = rand()%1000/1000.0;if (p popul

6、ation0.cfitness) newpopulationi二 population0;else /*计算种群的总适应度*/ for (i = 0; i POPSIZE; i+) populationi二 newpopulationi;for (j = 0; j = populationj.cfitness & p populationj+l.cfitness) newpopulationi二 populationj+l;sum += (populationmem. fitness - lower_fitness);/*计算相对适应度*/for (mem = 0; mem POPSIZE;

7、mem+) populationmem.rfitness = (populationmem. fitness - lower_fitness)/sum;population0.cfitness = population0.rfitness;/*计算累积适应度*/for(mem = 1; mem POPSIZE; mem+) populationmem.cfitness = populationmem-l.cfitness + populationmem.rfitness;3杂交算子杂交算子的流程一般如下：(1) 按杂交概率选择一对参与进化的个体；(2) 随机确定一个截断点；(3) 将两个个体的

8、染色体从截断点处截断，并交换，从而得到新的染色体。 具体算法见如下函数：void crossover(void)int i, j, k, m, poi nt;int first 二 0;double x;for (k = 0; k POPSIZE; k+) x = rand()%1000/1000.0; /产生随机交叉概率if (x PXOVER)/*如果随机交叉概率小于交叉概率，则进行交叉*/first+;if (first % 2 = 0) if (NVARS = 2) point = 1;/得到一个交叉点else point = (rand() % (NVARS 1) + 1;for (

9、j = 0; j point; j+)/交叉运算，两个个体的交叉点前的基因进行交换swap(&populationm.genej, &populationk.genej);else m = k;4变异算子 在遗传算法中使用变异算子有两个目的：改善遗传算法的局部搜索能力。维持群 体的多样性，防止出现早熟现象。变异操作的实现相当简单，只需遍历各染色体 的各个单元，按某一变异概率将该单元变成一个随机的合法值。其执行过程是：(1) 对个体的每一个基因组，依变异概率Pm指定为变异点。(2) 对每一个指定的变异点，对其基因取非或者用其他等位基因值来代替，从而产生一个新的个体。实现代码如下： void mu

10、tate(void)int i, j；double Ibound, hbound;/定义p为随机变异概率double p;for (i = 0; i POPSIZE; i+) for (j = 0; j NVARS; j+) p = rand()%1000/1000.0; if (p PMUTATION) popula tion i.genej = randval(lowerj, upperj); 串行遗传算法的主要流程如图1所示。在每一次进化过程中，总是找出种群 中的最优解与最差解，并将最优解保存,将本次最差解用上次保存的最优解替换， 这样保证了各次进化的最优解的适应度不会降低，从而增快收敛

11、的速度。开始图1串行遗传算法基本流程三、算法设计分析图1中的串行算法，容易看出，在选择函数中，计算相对适应度需要用 到全局种群的适应度之和，计算个体X的累积适应度依赖于x的累积适应度，k+1k如果在并行算法中要原封不动地模拟串行算法的运算，这些数据依赖关系都将产 生通讯。更为不幸的是，选择后的个体需在各进程中作大量数据迁移。杂交算子 中，一次杂交需要用到母体中的两个个体，若在这两个个体分配在不同进程，则 需要进行一次通讯。此后的变异和评估都可以非常容易的实现并行，并且完全不 需要任何通讯。但最后一步求最优个体和最差个体需要对各进程进行归约。由这 些分析可以看出，完全地模拟串行情形将使算法变得相

12、当低效。幸运地是，遗传算法本身是一个概率算法，我们完全可以对串行算法作些必 要的改变。如图2所示，我们将整个种群分成p个子种群，每一子种群由一个单 一的进程负责。各进程独立地完成串行遗传算法的整个过程，唯一不同的是选择 函数。各进程作选择操作时，首先计算各子种群内的局部累积适应度，然后根据 局部累积适应度选择若干（本算法实现中使用的是常数3,也可以设为子种群大 小的一个函数）个体按一固定规则轮流发送到其他进程；同时，按照该规则相应 地从其他进程获取若干用来进行交流的个体。获取到个体后，先将其暂存；然后 按串行算法中的选择机制从原子种群中选择进行进化的母体；最后再用之前暂存 的个体完成进程间的种

13、群交流。对每一个待交流的个体，具体策略如下：（1）随机地从本地的待进化母体种群内抽取与之进行交流的母体；（2）比较本地个体与传送过来的待交流个体，选取适应度高者作为最终母 体。各进程在每一次进化过程中，均分别保留各自的局部最优解，用来在下一次 进化中替换局部最差的个体。各进程均完成所预定的进化迭代后，最后对各进程 的局部最优解进行归约，从而得到整个算法的全局最优解。算法的主要流程详见 图2。图2并行遗传算法基本流程(mem本0；mfF TAsK_NUM(pid); mem+) populationmem.rfitness =(populationmem. fitness -lower_fitn

14、ess)/sum;fornewpopulationi;一Jf勢)*/ rand()%TASK_NUM(pid);i则(i =Jif (populationj.fitness ex for (k 二.、0; k NVARS; k+) populationj.genek_memberi.fitn ess) :ex_memberi.genek;四、算法实现该算法实现的最关键部分为选择中的种群交流，该功能有如下函数实现void pop_select(void)MPI_Status status; MPI_Request handle; int mem, i, j, k; double sum = 0; double p;static struct genotype ex_memberEX_NUM；(mem愷0；聲黑娶 TAsK_NUM(pid); mem+) sum += (populationmem. fitness lower_fitness);/*计for 1population0.cfitness = population0.rfitness;/*计算各个体累积适应度*/for (mem = 1; mem T