遗传算法求解函数最大值

遗传算法求解函数最大值 广西大学 机械学院 人工智能 课程设计 人工智能 遗传算法函数优化 第 1 页 广西大学 机械学院 人工智能 课程设计 目录 1引言 ............................................................................. 3 1.1 摘要 ........................................................................................................................................... 3 1.2 背景 ........................................................................................................................................... 3 2 实验过程 .................................................................... 4 2.1 程序目标 ................................................................................................................................... 4 2.2 实验原理及步骤 ....................................................................................................................... 4 2.3程序 ............................................................................................................................................ 5 2.3.1程序理解: ..................................................................................................................... 5 2.3.3调试程序: ..................................................................................................................... 5 2.4 实验 ................................................................................................................................. 18 第 2 页 广西大学 机械学院 人工智能 课程设计 1引言 1.1 摘要 函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。本文将用一个详细的例子来说明用遗传算法解一个简单参数优化问题的过程。这里求解的是一个函数的最大值的问题。 1.2 背景 遗传算法采纳自然进化模型。通过保持一个潜在解的群体执行了多方向的搜索并支持这些方向上的信息构成和交换。群体经过一个模拟进化的过程:在每一代，相对“好”的解产生，相对“差”的解死亡。为区别不同解，我们使用了一个目标(评价)函数，它起着一个环境的作用。 选择是用来确定管理费用或交叉个体，以及被选个体将产生多少个代个体。 杂交组合了两个亲代染色体的特征，并通过交换父代相应的片断形成了两个相似的后代。杂交算子的意图是在不同潜在解之间进行信息交换。 变异是通过用一个等于变异率的概率随机地改变被选择染色体上的一个或多个基因。变异算子的意图是向群体引入一些额外的变化性。 运用遗传算法解题必经的五个步骤: 1( 对问题潜在解的遗传达。 2( 产生潜在解初始群体的方法。 3( 起环境作用的用“适应值”评价解的适应程度的评价函数。 4( 改变后代组成的各种遗传算子。 5( 遗传算法所使用的各种参数:群体规模、应用遗传算子的概率等。 第 3 页 广西大学 机械学院 人工智能 课程设计 2 实验过程 2.1 程序目标 在实验过程中，我们应用遗传算法来模拟一个函数优化的问题。程序所要解决的问题是求f(x1,x2)=21.5+x1*sin(4pi*x1)+x2*sin(20pi*x2)的最大值，其中-3.0?x1?12.1及4.1?x2?5.8。 2.2 实验原理及步骤 1 ) 首先确立变量x1的定义域长度为15.1;所要求的小数点以后第四位精度意味着区间[-3.0, 12.1]应该至少被分成15.1*10000个等距区间，即染色体的第一部分需要18位;自变量x2域长度为1.7，精度要求区间[4.1, 5.8]应该至少被分成1.7*10000个等距区间，即染色体的第二部分需要15位。所以染色体总长度为33位。用遗传算法的优化函数f,产生了一个有pop_size = 20个染色体的群体。所有染色体的33位都是随机初始化。对每个染色体进行解码并计算解码后的(x1,x2)的适应函数值，eval(vi) (i=1,..,pop_size) = f(x1,x2)。 2)为选择过程建立一个轮盘。计算群体的总适应值F，并计算每个染色体vi (i=1,..,pop_size)的选择概率pi:pi = eval(vi) / F 和累积概率qi: qi = p1 + .. + pi. 3)转动轮盘20次，每次为新群体选择一单个染色体。生成一个区间[0,1]里的20个数的一个随机序列。如果一个随机数位于qi于q(i+1)之间，则q(i+1)被选择。 4)对新群体中的个体应用杂交算子。杂交概率pc = 0.25，所以预计染色体中平均有25%将经历杂交。杂交按照下面的方法进行:对新群体中的每个染色体，产生在区间[0,1]里的随机数r,并从随机序列中选出r<0.25的染色体进行杂交。 5)对被选择的染色体随机进行配对。并从区间[1,32]里产生一个随机整数pos。数字pos表示杂交点的位置。 6)算子变异。在一位一位基础上执行。变异概率pm = 0.01,所以我们预计平均将有1%的位经历变异。整个群体共有m*pop_size = 660位，可以预计平均每代有6.6次变异。因为每一位都有均等的机会被变异，所以对群体中的每一位可以产生区间 第 4 页 广西大学 机械学院 人工智能 课程设计 [0,1]里的一个随机数r,如果r<0.01,则变异此位。 7)由上面得到最新的向量群体。对每个染色体进行解码，并计算解码后的(x1,x2)的适应函数值。选出最好染色体的评价值。 8)准备再一次运行选择过程，继续进行迭代计算，应用遗传算子及评价下一代。 2.3程序 2.3.1程序理解: 初始化函数:在变量限定的范围内初始化遗传因子的值。从gadata.txt'这个文件中读取每个变量的上下边界，并且在这个范围内随机初始化产生染色体中的值。 随机值生成函数:多次用到此函数。 评价函数:函数需要用户自己定义一个数学函数式。population[mem].fitness = 21.5+x[1]*sin(4.0*PI*x[1])+x[2]*sin(20.0*PI*x[2]); 最优个体(取优函数):前一代的最优成员被存储在数组的最后。但如果现今这一代的最优成员并没有上一代的好(值小于)，则后者(上一代的最优值)会取代本代中最差的成员。 如果当前代的最优值大于上一代的，则将当前代的最优值拷贝出来，否则则用上一代的最优值取代当前代的最差值。确保我们始终取到最适合的那个值。 选择函数:为的是解决优化模型中的最大问题，确保最优秀的成员始终存活下来。 :void Xover(int one, int two) 杂交函数 对选择出来的双亲进行杂交。 变异:void mutate(void) 某个被选择出来的要进行变异的因子，将会被一个取值范围内的随机量所代替。 报告函数:void report(void)用来报告演算程序的进展。输入output文件里的数据以逗号相隔。 2.3.3调试程序: 写好程序之后，就可以进行调试了。当在gadat.txt里输入3 5;6 9;7 8; 第 5 页 广西大学 机械学院 人工智能 课程设计 1 6四组数据时，在”galog.txt”文件中可以看到输出的结果。现附上迭代500 次的结果: 1, 32.922158615, 23.048467665, 5.926697571 2, 32.922158615, 25.219353332, 4.748125277 3, 32.922158615, 25.602532313, 4.471082127 4, 32.922158615, 26.483624415, 4.712873791 5, 34.004917169, 27.171438656, 4.401705026 6, 34.004917169, 27.632563061, 4.342945746 7, 34.004917169, 28.507499261, 4.102991080 8, 34.295500976, 28.367508993, 4.434875924 9, 34.295500976, 28.713407029, 3.942327273 。。。。。。。。。。。。 494, 34.295500976, 34.295500976, 0.000000664 495, 34.295500976, 34.295500976, 0.000000664 496, 34.295500976, 34.295500976, 0.000000664 497, 34.295500976, 34.295500976, 0.000000664 498, 34.295500976, 34.295500976, 0.000000664 499, 34.295500976, 34.295500976, 0.000000664 500, 34.295500976, 34.295500976, 0.000000664 Simulation completed var(0) = 4.654000000 var(1) = 8.721000000 var(2) = 7.609000000 var(3) = 5.980000000 Best fitness = 34.295500976 第 6 页 广西大学 机械学院 人工智能 课程设计 附源代码: #include #include #include #define TRUE 1 #define FALSE 0 #define PMUTATION 0.001 #define MAXGENS 500 #define POPSIZE 100 #define NVARS 4 #define PXOVER 0.8 int generation; int cur_best; FILE *galog; FILE *output; struct genotype 第 7 页 广西大学 机械学院 人工智能 课程设计 { double gene[NVARS]; double fitness; double upper[NVARS]; double lower[NVARS]; double rfitness; double cfitness; }; struct genotype population[POPSIZE+1]; struct genotype newpopulation[POPSIZE+1]; void initialize(void); double randval(double, double); void evaluate(void); void keep_the_best(void); void elitist(void); void select(void); void crossover(void); void Xover(int,int); void swap(double *, double *); void mutate(void); void report(void); void initialize(void) { FILE *infile; int i, j; double lbound, ubound; if ((infile = fopen("gadata.txt","r"))==NULL) { 第 8 页 广西大学 机械学院 人工智能 课程设计 fprintf(galog,"\nCannot open input file!\n"); exit(1); } remove("output.dat"); for (i = 0; i < NVARS; i++) { fscanf(infile, "%lf",&lbound); fscanf(infile, "%lf",&ubound); for (j = 0; j < POPSIZE; j++) { population[j].fitness = 0; population[j].rfitness = 0; population[j].cfitness = 0; population[j].lower[i] = lbound; population[j].upper[i] = ubound; population[j].gene[i] = randval(population[j].lower[i], population[j].upper[i]); } } fclose(infile); } double randval(double low, double high) { double val; val = ((double)(rand()%1000)/1000.0)*(high - low) + low; return(val); } void evaluate(void) { if ((output = fopen("output.dat","a"))==NULL) 第 9 页 广西大学 机械学院 人工智能 课程设计 { exit(1); } int mem; int i; double x[NVARS+1]; double PI = 3.141593; for (mem = 0; mem < POPSIZE; mem++) { for (i = 0; i < NVARS; i++) x[i+1] = population[mem].gene[i]; population[mem].fitness = 21.5+x[1]*sin(4.0*PI*x[1])+x[2]*sin(20.0*PI*x[2]); if (population[mem].fitness <40 && population[mem].fitness>35) { fprintf(output, "\n%5d, %6.9f, %6.9f, %6.9f ", generation, x[1],x[2],population[mem].fitness); } } fclose(output); } void keep_the_best() { int mem; int i; cur_best = 0; for (mem = 0; mem < POPSIZE; mem++) { if (population[mem].fitness > population[POPSIZE].fitness) { 第 10 页 广西大学 机械学院 人工智能 课程设计 cur_best = mem; population[POPSIZE].fitness = population[mem].fitness; } } for (i = 0; i < NVARS; i++) population[POPSIZE].gene[i] = population[cur_best].gene[i]; } void elitist() { int i; double best, worst; int best_mem, worst_mem; best = population[0].fitness; worst = population[0].fitness; for (i = 0; i < POPSIZE - 1; ++i) { if(population[i].fitness > population[i+1].fitness) { if (population[i].fitness >= best) { best = population[i].fitness; best_mem = i; } if (population[i+1].fitness <= worst) { worst = population[i+1].fitness; worst_mem = i + 1; } } else 第 11 页 广西大学 机械学院 人工智能 课程设计 { if (population[i].fitness <= worst) { worst = population[i].fitness; worst_mem = i; } if (population[i+1].fitness >= best) { best = population[i+1].fitness; best_mem = i + 1; } } } if (best >= population[POPSIZE].fitness) { for (i = 0; i < NVARS; i++) population[POPSIZE].gene[i] = population[best_mem].gene[i]; population[POPSIZE].fitness = population[best_mem].fitness; } else { for (i = 0; i < NVARS; i++) population[worst_mem].gene[i] = population[POPSIZE].gene[i]; population[worst_mem].fitness = population[POPSIZE].fitness; } } void select(void) { int mem, i, j, k; double sum = 0; 第 12 页 广西大学 机械学院 人工智能 课程设计 double p; for (mem = 0; mem < POPSIZE; mem++) { sum += population[mem].fitness; } for (mem = 0; mem < POPSIZE; mem++) { population[mem].rfitness = population[mem].fitness/sum; } population[0].cfitness = population[0].rfitness; for (mem = 1; mem < POPSIZE; mem++) { population[mem].cfitness = population[mem-1].cfitness + population[mem].rfitness; } for (i = 0; i < POPSIZE; i++) { p = rand()%1000/1000.0; if (p < population[0].cfitness) newpopulation[i] = population[0]; else { for (j = 0; j < POPSIZE;j++) if (p >= population[j].cfitness && p 1) { if(NVARS == 2) point = 1; else point = (rand() % (NVARS - 1)) + 1; 第 14 页 广西大学 机械学院 人工智能 课程设计 for (i = 0; i < point; i++) swap(&population[one].gene[i], &population[two].gene[i]); } } void swap(double *x, double *y) { double temp; temp = *x; *x = *y; *y = temp; } void mutate(void) { int i, j; double lbound, hbound; double x; for (i = 0; i < POPSIZE; i++) for (j = 0; j < NVARS; j++) { x = rand()%1000/1000.0; if (x < PMUTATION) { lbound = population[i].lower[j]; hbound = population[i].upper[j]; population[i].gene[j] = randval(lbound, hbound); } } } void report(void) { 第 15 页 广西大学 机械学院 人工智能 课程设计 int i; double best_val; double avg; double stddev; double sum_square; double square_sum; double sum; sum = 0.0; sum_square = 0.0; for (i = 0; i < POPSIZE; i++) { sum += population[i].fitness; sum_square += population[i].fitness * population[i].fitness; } avg = sum/(double)POPSIZE; square_sum = avg * avg * POPSIZE; stddev = sqrt((sum_square - square_sum)/(POPSIZE - 1)); best_val = population[POPSIZE].fitness; fprintf(galog, "\n%5d, %6.9f, %6.9f, %6.9f ", generation, best_val, avg, stddev); printf( "\n%5d, %6.9f, %6.9f, %6.9f ", generation, best_val, avg, stddev); } void main(void) { int i; if ((galog = fopen("galog.txt","w"))==NULL) { exit(1); } generation = 0; 第 16 页 广西大学 机械学院 人工智能 课程设计 fprintf(galog, "\n generation best average standard \n"); printf( "\n generation best average standard \n"); fprintf(galog, " number value fitness deviation \n"); printf(" number value fitness deviation \n"); initialize(); evaluate(); keep_the_best(); while(generation