SGA源程序.rar_SGA_基本遗传算法源程序_遗传算法

/******************************************************************/ /* 基于基本遗传算法的函数最优化 SGA.C */ /* A Function Optimizer using Simple Genetic Algorithm */ /* developed from the Pascal SGA code presented by David E.Goldberg */ /* 同济大学计算机系 王小平 2000年5月 */ /******************************************************************/ #include <stdio.h> #include<graphics.h> #include <math.h> #include "graph.c" /* 全局变量 */ struct individual /* 个体*/ { unsigned *chrom; /* 染色体 */ double fitness; /* 个体适应度*/ double varible; /* 个体对应的变量值*/ int xsite; /* 交叉位置 */ int parent[2]; /* 父个体 */ int *utility; /* 特定数据指针变量 */ }; struct bestever /* 最佳个体*/ { unsigned *chrom; /* 最佳个体染色体*/ double fitness; /* 最佳个体适应度 */ double varible; /* 最佳个体对应的变量值 */ int generation; /* 最佳个体生成代 */ }; struct individual *oldpop; /* 当前代种群 */ struct individual *newpop; /* 新一代种群 */ struct bestever bestfit; /* 最佳个体 */ double sumfitness; /* 种群中个体适应度累计 */ double max; /* 种群中个体最大适应度 */ double avg; /* 种群中个体平均适应度 */ double min; /* 种群中个体最小适应度 */ float pcross; /* 交叉概率 */ float pmutation; /* 变异概率 */ int popsize; /* 种群大小 */ int lchrom; /* 染色体长度*/ int chromsize; /* 存储一染色体所需字节数 */ int gen; /* 当前世代数 */ int maxgen; /* 最大世代数 */ int run; /* 当前运行次数 */ int maxruns; /* 总运行次数 */ int printstrings; /* 输出染色体编码的判断，0 -- 不输出, 1 -- 输出 */ int nmutation; /* 当前代变异发生次数 */ int ncross; /* 当前代交叉发生次数 */ /* 随机数发生器使用的静态变量 */ static double oldrand[55]; static int jrand; static double rndx2; static int rndcalcflag; /* 输出文件指针 */ FILE *outfp ; /* 函数定义 */ void advance_random(); int flip(float);rnd(int, int); void randomize(); double randomnormaldeviate(); float randomperc(),rndreal(float,float); void warmup_random(float); void initialize(),initdata(),initpop(); void initreport(),generation(),initmalloc(); void freeall(),nomemory(char *),report(); void writepop(),writechrom(unsigned *); void preselect(); void statistics(struct individual *); void title(),repchar (FILE *,char *,int); void skip(FILE *,int); int select(); void objfunc(struct individual *); int crossover (unsigned *, unsigned *, unsigned *, unsigned *); void mutation(unsigned *); void initialize() /* 遗传算法初始化 */ { /* 键盘输入遗传算法参数 */ initdata(); /* 确定染色体的字节长度 */ chromsize = (lchrom/(8*sizeof(unsigned))); if(lchrom%(8*sizeof(unsigned))) chromsize++; /*分配给全局数据结构空间 */ initmalloc(); /* 初始化随机数发生器 */ randomize(); /* 初始化全局计数变量和一些数值*/ nmutation = 0; ncross = 0; bestfit.fitness = 0.0; bestfit.generation = 0; /* 初始化种群，并统计计算结果 */ initpop(); statistics(oldpop); initreport(); } void initdata() /* 遗传算法参数输入 */ { char answer[2]; setcolor(9); disp_hz16("种群大小(20-100)：",100,150,20); gscanf(320,150,9,15,4,"%d", &popsize); if((popsize%2) != 0) { fprintf(outfp, "种群大小已设置为偶数\n"); popsize++; }; setcolor(9); disp_hz16("染色体长度(8-40)：",100,180,20); gscanf(320,180,9,15,4,"%d", &lchrom); setcolor(9); disp_hz16("是否输出染色体编码(y/n)：",100,210,20); printstrings=1; gscanf(320,210,9,15,4,"%s", answer); if(strncmp(answer,"n",1) == 0) printstrings = 0; setcolor(9); disp_hz16("最大世代数(100-300)：",100,240,20); gscanf(320,240,9,15,4,"%d", &maxgen); setcolor(9); disp_hz16("交叉率(0.2-0.9)：",100,270,20); gscanf(320,270,9,15,5,"%f", &pcross); setcolor(9); disp_hz16("变异率(0.01-0.1)：",100,300,20); gscanf(320,300,9,15,5,"%f", &pmutation); } void initpop() /* 随机初始化种群 */ { int j, j1, k, stop; unsigned mask = 1; for(j = 0; j < popsize; j++) { for(k = 0; k < chromsize; k++) { oldpop[j].chrom[k] = 0; if(k == (chromsize-1)) stop = lchrom - (k*(8*sizeof(unsigned))); else stop =8*sizeof(unsigned); for(j1 = 1; j1 <= stop; j1++) { oldpop[j].chrom[k] = oldpop[j].chrom[k]<<1; if(flip(0.5)) oldpop[j].chrom[k] = oldpop[j].chrom[k]|mask; } } oldpop[j].parent[0] = 0; /* 初始父个体信息 */ oldpop[j].parent[1] = 0; oldpop[j].xsite = 0; objfunc(&(oldpop[j])); /* 计算初始适应度*/ } } void initreport() /* 初始参数输出 */ { void skip(); skip(outfp,1); fprintf(outfp," 基本遗传算法参数\n"); fprintf(outfp," -------------------------------------------------\n"); fprintf(outfp," 种群大小(popsize) = %d\n",popsize); fprintf(outfp," 染色体长度(lchrom) = %d\n",lchrom); fprintf(outfp," 最大进化代数(maxgen) = %d\n",maxgen); fprintf(outfp," 交叉概率(pcross) = %f\n", pcross); fprintf(outfp," 变异概率(pmutation) = %f\n", pmutation); fprintf(outfp," -------------------------------------------------\n"); skip(outfp,1); fflush(outfp); } void generation() { int mate1, mate2, jcross, j = 0; /* 每代运算前进行预选 */ preselect(); /* 选择, 交叉, 变异 */ do { /* 挑选交叉配对 */ mate1 = select(); mate2 = select(); /* 交叉和变异 */ jcross = crossover(oldpop[mate1].chrom, oldpop[mate2].chrom, newpop[j].chrom, newpop[j+1].chrom); mutation(newpop[j].chrom); mutation(newpop[j+1].chrom); /* 解码, 计算适应度 */ objfunc(&(newpop[j])); /*记录亲子关系和交叉位置 */ newpop[j].parent[0] = mate1+1; newpop[j].xsite = jcross; newpop[j].parent[1] = mate2+1; objfunc(&(newpop[j+1])); newpop[j+1].parent[0] = mate1+1; newpop[j+1].xsite = jcross; newpop[j+1].parent[1] = mate2+1; j = j + 2; } while(j < (popsize-1)); } void initmalloc() /*为全局数据变量分配空间 */ { unsigned nbytes; char *malloc(); int j; /* 分配给当前代和新一代种群内存空间 */ nbytes = popsize*sizeof(struct individual); if((oldpop = (struct individual *) malloc(nbytes)) == NULL) nomemory("oldpop"); if((newpop = (struct individual *) malloc(nbytes)) == NULL) nomemory("newpop"); /* 分配给染色体内存空间 */ nbytes = chromsize*sizeof(unsigned); for(j = 0; j < popsize; j++) { if((oldpop[j].chrom = (unsigned *) malloc(nbytes)) == NULL) nomemory("oldpop chromosomes"); if((newpop[j].chrom = (unsigned *) malloc(nbytes)) == NULL) nomemory("newpop chromosomes"); } if((bestfit.chrom = (unsigned *) malloc(nbytes)) == NULL) nomemory("bestfit chromosome"); } void freeall() /* 释放内存空间 */ { int i; for(i = 0; i < popsize; i++) { free(oldpop[i].chrom); free(newpop[i].chr