《遗传算法的并行实现》由会员分享，可在线阅读，更多相关《遗传算法的并行实现（22页珍藏版）》请在金锄头文库上搜索。
1、北京工业大学并行计算课程设计（论文） 1 遗 传 算 法 （基于遗传算法求函数最大值） 指导老师：刘建丽 学 号：S201007156 姓 名：杨平 班 级：研 10 级 1 班 北京工业大学并行计算课程设计（论文） 2 遗传算法遗传算法 一、一、 遗传算法的基本描述遗传算法的基本描述 遗传算法（Genetic Algorithm，GA）是通过模拟自然界生物进化过程来求解优化问题的一类自组织、自适应的人工智能技术。它主要基于达尔文的自然进化论和孟德尔的遗传变异理论。 多数遗传算法的应用是处理一个由许多个体组成的群体， 其中每个个体表示问题的一个潜在解。对个体存在一个评估函数来评判其对环境的适应
2、度。为反映适者生存的思想，算法中设计一个选择机制，使得：适应度好的个体有更多的机会生存。在种群的进化过程中，主要存在两种类型的遗传算子：杂交和变异。这些算子作用于个体对应的染色体，产生新的染色体，从而构成下一代种群中的个体。该过程不断进行，直到找到满足精度要求的解，或者达到设定的进化代数。显然，这样的思想适合于现实世界中的一大类问题，因而具有广泛的应用价值。遗传算法的每一次进化过程中的，各个体之间的操作大多可以并列进行，因此，一个非常自然的想法就是将遗传算法并行化，以提高计算速度。本报告中试图得到一个并行遗传算法的框架，并考察并行化之后的一些特性。为简单起见（本来应该考虑更复杂的问题，如 TS
3、P。因时间有些紧张，做如 TSP 等复杂问题怕时间不够，做不出来，请老师原谅） ，考虑的具有问题是：对给定的正整数 n、n 元函数 f，以及定义域 D，求函数 f 在 D 内的最大值。 二、二、 串行遗传算法串行遗传算法 1 染色体与适应度函数染色体与适应度函数 对函数优化问题，一个潜在的解就是定义域 D 中的一个点011(,.,)nx xx，因此， 我们只需用一个长度为 n 的实数数组来表示一个个体的染色体。由于问题中要求求函数 f 的最大值， 我们可以以个体所代表点011(,.,)nx xx在 f 函数下的值来判断该个体的好坏。因此，我们直接用函数 f 作为个体的适应度函数。 2 选择机制
4、选择机制 选择是遗传算法中最主要的机制，也是影响遗传算法性能最主要的因素。若选择过程中适应度好的个体生存的概率过大， 会造成几个较好的可行解迅速占据种群，从而收敛于局部最优解；反之，若适应度对生存概率的影响过小，则会使算法呈现出纯粹的随机徘徊行为，算法无法收敛。下面我们介绍在实验中所使用的选择机制。 北京工业大学并行计算课程设计（论文） 3 我们定义P为当前种群内所有个体的集合，(0)(1)(1),.,nxxx为P中所有个体的一个固定排列。若xP为某一个体，( )f x表示该个体的适应度，则种群P的适应度定义为： 1 ( )0( )()n iis Pf x对任意个体xP，x的相对适应度定义为(
5、 )( )/ ( )r xf xs P。相对适应度( )r x反映了个体( ) ix的适应度在整个适应度总和中所占的比例。个体适应度越高，被选中的概率越高。累积适应度定义为: 进 行选择之前，先产生一个 0 到 1 之间的随机实数t，若满足1()()kkr xtr x，则第 k+1 个个体被选中。循环以上过程，即得到生成下一代种群的母体。 具体实现见如下函数： void pop_select(void) int mem, i, j, k; double sum = 0; double p; /* 计算种群适应度之和 */ for (mem = 0; mem = populationj.cfit
6、ness /*记录染色体的基因*/ double fitness; /* 适应度*/ double rfitness; /* 相对适应度*/ double cfitness; /* 累积适应度*/ *population, *newpopulation; double lowerboundNVARS; double upperboundNVARS; double local_best_individualNVARS+1; /* 局部最优解*/ double best_individualNVARS+1; /* 全局最优解*/ int generation; double lower_fitne
7、ss; /*最小的适应度*/ FILE *galog; int pid, pnum; /*记录进程编号和进程数*/ double randval(double low, double high) /*编码函数*/ double val; 北京工业大学并行计算课程设计（论文） 12 val = (double)(rand()%1000)/1000.0)*(high - low) + low; return val; void initialize(void) /*初始化函数*/ FILE *infile; int i, j, r; double lbound, ubound; MPI_Statu
8、s status; population = (struct genotype*)malloc(sizeof(struct genotype)*(TASK_NUM(pid)+1); /定义一个genotype类型指针，用于存放种群 newpopulation = (struct genotype*)malloc(sizeof(struct genotype)*(TASK_NUM(pid)+1); /定义一个genotype类型指针newpopulation，用于存 放产生新的种群 if (pid !=pnum - 1) if (infile = fopen(“yangping.txt“,“r“
9、)=NULL) /打开文件，读入每个自变量的定义域 fprintf(galog,“nCannot open input file!n“); exit(1); srand(time(0); for (i=0; i populationTASK_NUM(pid).fitness) cur_best = mem; /用Cur_best记录最大适应度的 染色体 populationTASK_NUM(pid).fitness = populationmem.fitness; /printf(“nG%4d: the best individual in Process %d is %d, the fitn
10、ess is %lf.n“, generation, pid, cur_best, populationcur_best.fitness); for (i = 0; i = populationj.cfitness else point = (rand() % (NVARS - 1) + 1; /随机选择交叉点 北京工业大学并行计算课程设计（论文） 17 for (i = 0; i populationi+1.fitness) if (populationi.fitness = best) best = populationi.fitness; best_mem = i; if (popula
11、tioni+1.fitness = best) best = populationi+1.fitness; best_mem = i + 1; if (best = populationTASK_NUM(pid).fitness) for (i = 0; i NVARS; i+) populationTASK_NUM(pid).genei = populationbest_mem.genei; local_best_individuali+1 = populationbest_mem.genei; 北京工业大学并行计算课程设计（论文） 19 populationTASK_NUM(pid).fi
12、tness = populationbest_mem.fitness; local_best_individual0 = populationbest_mem.fitness; else for (i = 0; i NVARS; i+) populationworst_mem.genei = populationTASK_NUM(pid).genei; populationworst_mem.fitness = populationTASK_NUM(pid).fitness; /printf(“ Generation %d in Process %d: best = %lf, worst =%
13、lfn“, generation, pid, local_best_individual0, worst); /printf(“nG%4d: the best individual in Process %d is %d, the fitness is %lf.n“, generation, pid, best_mem, populationbest_mem.fitness); /*输出函数，输出到指定的文件*/ void report(void) int i, j; fprintf(galog, “nGene data in %d for generation %d is:n“, pid,
14、generation); for (j = 0; j TASK_NUM(pid); j+) fprintf(galog, “%4d :“, j); for (i = 0; i NVARS; i+) fprintf(galog, “t%10.6lf “, populationj.genei); fprintf(galog, “: %20.6lfn“, populationj.fitness); void gene_max(double *in, double *inout, int *len, MPI_Datatype *dptr) int i; if (inout0 in0) /* 比较适应度*/ for (i=0; i *len; +i) /* 复制适应度较高的个体*/ inouti = ini; int main(int argc, char *argv) double startwtime = 0.0, endwtime; /*定义starttime和endtime用于北京工业大学并行计算课程设计（论文） 20 记录运行所需要的时间*/ int i, j, flag; int n = 0; MPI_Op my_op; MPI_Init( MPI_Comm_size(MPI_COMM_WORLD, /得到进程数，放入pnum中 MPI
