简单遗传算法(SGA)源程序.docx

/* * 简单遗传算法(SGA) * 主要算法模块有:选择 交叉 变异 (三个遗传操作) 和 群体更新 * 以及 随即数发生器 输入 输出 译码 适应度计算 * 选择机制为比例选择 交叉采用单点交叉 变异采用简单的位点变异方式 * 多变量编码采用把各个变量染色体基因交替相连的方式,体现在译码模块中 */* 1999.10.20 增添编码函数,方便输入初值 */ -/ A Simple Genetic Algorithm - SGA / (c) Ding Zhen Yu 1998 / -/ All Rights Reserved / -#include #include #include /#define NeedInputInitialChrom / 如果需要输入初始值,一般是因为上次没有 / 计算完成,可以接着再算 /#define NeedInputData /输入种群中第一个的大小(01.0之间)#undef NeedInputInitialChrom/*NOTICE:modify varnumber and perchrom for each problem.*/#define varnumber 32 /* 变量个数 */#define perchrom 5 /* 单变量染色体长度 */#define popsize 20 /* 群体规模(应为偶数) */#define maxgen 5000 /* 遗传世代数 */#define maxstring varnumber*perchrom /* 多变量总的染色体长度 */#define pcross 0.80 /* 交叉概率0.00,1.00 */#define pmutation 0.001 /* 变异概率0.00,1.00 */extern double Obj_func(double *x);struct pp unsigned int chrommaxstring; double xvarnumber,fitness; unsigned int parent1,parent2,xsite; ;struct pp oldpoppopsize,newpoppopsize,p1popsize;unsigned int lchrom,gen,nmutation,ncross,jcross,maxpp,minpp;double sumfitness,avg,max,min;double coef;long seedl1;double objfunc(double *); /* 目标函数,应该是正的,最小问题要化为最大问题 */void statistics(); /* 群体适应度统计 */int rselect(); /* 赌轮选择 */int flip(double); /* 贝努利测试 */int crossover(); /* 一点交叉操作 */int mutation(unsigned int); /* 变异操作 */void generation(); /* 世代更新 */void initialize(); /* 初始化 */void initpop(); void report(); void initdata();void initreport();void decode(unsigned int *, double *); /* 解码,变量取值在0到1之间 */void encode(unsigned int *, double *); /* 编码,输入变量取值在0到1之间 */double randomd01();int randomi01();int randomi(int,int);/* SGA main program */* xxi will be a double between 0 and 1.0 */void sga(double *xx) long int i,gen,k,j; double oldmax; int oldmaxpp; gen=0; seedl0=-9l; /printf(initializing.n); initialize(); for (i=0; ipopsize; i ) p1i=newpopi; newpopi=oldpopi; report(gen); for (i=0; ipopsize; i ) newpopi=p1i; do gen=gen 1; oldmax=max; oldmaxpp=maxpp; generation(); statistics(newpop); if (maxoldmax) for (j=0; jlchrom; j ) newpopminpp.chromj=oldpopoldmaxpp.chromj; for (j=0; jvarnumber; j ) newpopminpp.xj=oldpopoldmaxpp.xj; newpopminpp.fitness=oldpopoldmaxpp.fitness; statistics(newpop); report(gen); for (i=0; ipopsize; i ) p1i=oldpopi; oldpopi=newpopi; newpopi=p1i; while (genmaxgen); for (i=0; ivarnumber; i ) xxi=oldpopmaxpp.xi; /printf(xx%d=%f ,i,xxi); /printf(n); return;/* calculate individual fitness */double objfunc(double *x) double temp; temp=1.0/Obj_func(x); return temp;/* statistics of the group fitness */void statistics(pop)struct pp *pop; int j; sumfitness=pop0.fitness; min=pop0.fitness; max=pop0.fitness; maxpp=0; minpp=0; for (j=1;jmax) max=popj.fitness; maxpp=j; if (popj.fitnessmin) min=popj.fitness; minpp=j; avg=sumfitness/(double)popsize;/* new group */void generation() unsigned int j,mate1,mate2; j=0; do mate1=rselect(); mate2=rselect(); crossover(oldpopmate1.chrom,oldpopmate2.chrom,j); decode(newpopj.chrom,newpopj.x); newpopj.fitness=objfunc(newpopj.x); newpopj.parent1=mate1; newpopj.parent2=mate2; newpopj.xsite=jcross; decode(newpopj 1.chrom,newpopj 1.x); newpopj 1.fitness=objfunc(newpopj 1.x); newpopj 1.parent1=mate1; newpopj 1.parent2=mate2; newpopj 1.xsite=jcross; j=j 2; while (jpopsize);/* initialize */void initialize() coef=pow(2.00,perchrom)-1.0; initdata(); initpop(); statistics(oldpop); initreport();/* contral parameters input */void initdata() lchrom=perchrom*varnumber; nmutation=0; ncross=0;/* generation of initial group */* 按随机方式产生初始解群,或者直接输入前次结束时的染色体, * 或者按需要输入一个个体 */void initpop() int i,j,j1; /printf(initializing populations.n);#ifdef NeedInputInitialChrom printf(input initial chrom:n);#endif for (j=0;jpopsize;j ) /printf(j=%dn,j); for (j1=0;j1lchrom;j1 ) oldpopj.chromj1=randomi01();#ifdef NeedInputInitialChrom for (j1=0;j1lchrom;j1 ) scanf(,&oldpopj.chromj1); printf(%d in %d has been readed.n,j 1,popsize);#endif decode(oldpopj.chrom,oldpopj.x);#ifdef NeedInputInitialChrom for (j1=0;j1varnumber;j1 ) printf(x%d=%fn,j1,oldpopj.xj1);#endif oldpopj.fitness=objfunc(oldpopj.x); oldpopj.parent1=0; oldpopj.parent2=0; oldpopj.xsite=0; #ifdef NeedInputData printf(input %d initial data(0.01.0):n,varnumber); for (i=0; ivarnumber; i ) scanf(%lf,&oldpop0.xi); encode(oldpop0.chrom,oldpop0.x); oldpop0.fitness=objfunc(oldpop0.x); oldpop0.parent1=0; oldpop0.parent2=0; oldpop0.xsite=0;#endif/* initialization infomation output */void initreport() int j,k; printf(n-n); printf( SGA Parameters n); printf(-nn); printf(Population size (popsize) = %d n,popsize); printf(Chromosome length (lchrom) = %d n,lchrom); printf(Maximum # of generation (maxgen) = %d n,maxgen); printf(Crossover probablity (pcross) = %f n,pcross); printf(Mutation probablity (pmutation) = %f n,pmutation); printf(-nn); printf(Initial Population Maximum Fitness = %f n,max); printf(Initial Population Average Fitness = %f n,avg); printf(Initial Population Minimum Fitness = %f n,min); printf(Initial Population Sum of Fitness = %f n,sumfitness);/* data output */void report(int gen) int k,j,i; for (j=0; j79; j ) printf(*); printf(n); printf(Population Report n); printf(Generation = n,gen); printf(#parents xsite string x fitness n); for (j=0; j79; j ) printf( ); printf(n); for (j=0; jpopsize; j ) for (k=0; klchrom; k ) printf(%d,newpopj.chromk); printf(n); printf(n); /for (j=0; jpopsize; j ) j=maxpp; printf(%d %d ,j,newpopj.parent1); printf(%d %d ,newpopj.parent2,newpopj.xsite); /for (k=0; klchrom; k ) / printf(%d,newpopj.chromk); for (i=0; ivarnumber; i ) printf( %f ,newpopj.xi); printf(fitness=%f n,newpopj.fitness); for (k=0; k79; k ) printf(*); printf(n); printf(RESULT: GEN: %d ,gen); printf(AVG=%f MIN=%f MAX=%f n,avg,min,max); printf(ncross=%d nmutation = %d n,ncross,nmutation); /* decode */void decode(unsigned int *pp,double *x) int i,j; double tt,tt1; for (i=0; i-1 (varnumber-i-1);j-=varnumber) if (ppj) tt=tt tt1; tt1=2.0*tt1; tt=tt/coef;/tt is between 0.0 and 1.0 /change variables value range xi=0.0001 7.0*tt/10.0; /* encode */void encode(unsigned int *pp,double *x) int i,j,dx; double fx; for (i=0; i0.5) dx =1; for (j=lchrom-1-i;j-1 (varnumber-i-1); j-=varnumber) if (dx%2=1) ppj=1; /printf(1); else ppj=0; /printf(0); dx=dx/2; /* select operation */* 几种流行的选择机制:* 1. 赌轮选择(roulette wheel selection)机制; 也叫适应度比例方式(fitness proportional model); 2. 最佳保留(elitist model)选择机制; 3. 期望值模型(expected value model)选择机制; 4. 随机竞争(stochastic tournament)选择机制; 5. 排序(ranking)选择机制; 6. 排挤方法(crowding model);*/ 赌轮选择(roulette wheel selection)机制;int rselect() double rand1,partsum; int j; partsum=0.0; j=0; rand1=randomd01()*sumfitness; do partsum=partsum oldpopj.fitness; j=j 1; while (partsumrand1)&(jpopsize); return j-1;/* mutation operation */int mutation(unsigned int ch) int mutate,j; mutate=flip(pmutation); if (mutate) nmutation=nmutation 1; if (ch) ch=0; else ch=1; if (ch) return 1; else return 0;/* crossover operation */int crossover(unsigned int *parent1,unsigned int *parent2,int k5) int i,j,j1; if (flip(pcross) jcross=randomi(1,lchrom-1); ncross=ncross 1; else jcross=lchrom; if (jcross!=lchrom) for (j=0; jjcross; j ) newpopk5.chromj=mutation(parent1j); newpopk5 1.chromj=mutation(parent2j); for (j=jcross;jlchrom;j ) newpopk5.chromj=mutation(parent2j); newpopk5 1.chromj=mutation(parent1j); else for (j=0; jlchrom; j ) newpopk5.chromj=mutation(parent1j); newpopk5 1.chromj=mutation(parent2j); return 1;/* Bernoulli Trials */int flip(double probability) double ppp; ppp=randomd01(); if (ppp=probability) return 1; else return 0;/* return a double random number between 0.01.0 */double randomd01() int j; long k; static long idum2=1234567