资源预览内容
第1页 / 共22页
第2页 / 共22页
第3页 / 共22页
第4页 / 共22页
第5页 / 共22页
第6页 / 共22页
第7页 / 共22页
第8页 / 共22页
第9页 / 共22页
第10页 / 共22页
亲,该文档总共22页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
北京工业大学并行计算课程设计(论文) 1 遗 传 算 法 (基于遗传算法求函数最大值) 指导老师:刘建丽 学 号:S201007156 姓 名:杨平 班 级:研 10 级 1 班 北京工业大学并行计算课程设计(论文) 2 遗传算法遗传算法 一、一、 遗传算法的基本描述遗传算法的基本描述 遗传算法(Genetic Algorithm,GA)是通过模拟自然界生物进化过程来求解优化问题的一类自组织、自适应的人工智能技术。它主要基于达尔文的自然进化论和孟德尔的遗传变异理论。 多数遗传算法的应用是处理一个由许多个体组成的群体, 其中每个个体表示问题的一个潜在解。对个体存在一个评估函数来评判其对环境的适应度。为反映适者生存的思想,算法中设计一个选择机制,使得:适应度好的个体有更多的机会生存。在种群的进化过程中,主要存在两种类型的遗传算子:杂交和变异。这些算子作用于个体对应的染色体,产生新的染色体,从而构成下一代种群中的个体。该过程不断进行,直到找到满足精度要求的解,或者达到设定的进化代数。显然,这样的思想适合于现实世界中的一大类问题,因而具有广泛的应用价值。遗传算法的每一次进化过程中的,各个体之间的操作大多可以并列进行,因此,一个非常自然的想法就是将遗传算法并行化,以提高计算速度。本报告中试图得到一个并行遗传算法的框架,并考察并行化之后的一些特性。为简单起见(本来应该考虑更复杂的问题,如 TSP。因时间有些紧张,做如 TSP 等复杂问题怕时间不够,做不出来,请老师原谅) ,考虑的具有问题是:对给定的正整数 n、n 元函数 f,以及定义域 D,求函数 f 在 D 内的最大值。 二、二、 串行遗传算法串行遗传算法 1 染色体与适应度函数染色体与适应度函数 对函数优化问题,一个潜在的解就是定义域 D 中的一个点011(,.,)nx xx,因此, 我们只需用一个长度为 n 的实数数组来表示一个个体的染色体。由于问题中要求求函数 f 的最大值, 我们可以以个体所代表点011(,.,)nx xx在 f 函数下的值来判断该个体的好坏。因此,我们直接用函数 f 作为个体的适应度函数。 2 选择机制选择机制 选择是遗传算法中最主要的机制,也是影响遗传算法性能最主要的因素。若选择过程中适应度好的个体生存的概率过大, 会造成几个较好的可行解迅速占据种群,从而收敛于局部最优解;反之,若适应度对生存概率的影响过小,则会使算法呈现出纯粹的随机徘徊行为,算法无法收敛。下面我们介绍在实验中所使用的选择机制。 北京工业大学并行计算课程设计(论文) 3 我们定义P为当前种群内所有个体的集合,(0)(1)(1),.,nxxx为P中所有个体的一个固定排列。若xP为某一个体,( )f x表示该个体的适应度,则种群P的适应度定义为: 1 ( )0( )()n iis Pf x对任意个体xP,x的相对适应度定义为( )( )/ ( )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.cfitness /*记录染色体的基因*/ 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_fitness; /*最小的适应度*/ 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_Status 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“)=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 fitness 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 (populationi+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).fitness = 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 =%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, 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
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号