发信人: chinese (我选择●我考研), 信区: arithmetic
标 题: 简单遗传算法(SGA)源程序
发信站: 幽幽黄桷兰 (2001年07月26日11:44:08 星期四), 站内信件
发信人: dzy (散发弄扁舟), 信区: Algorithm
标 题: 简单遗传算法(SGA)源程序
发信站: 武汉白云黄鹤站 (Wed May 31 11:33:33 2000), 转信
/************************************************************************
* 简单遗传算法(SGA) *
* 主要算法模块有:选择 交叉 变异 (三个遗传操作) 和 群体更新 *
* 以及 随即数发生器 输入 输出 译码 适应度计算 *
* 选择机制为比例选择 交叉采用单点交叉 变异采用简单的位点变异方式 *
* 多变量编码采用把各个变量染色体基因交替相连的方式,体现在译码模块中 *
************************************************************************/
/* 1999.10.20 增添编码函数,方便输入初值 */
// ------------------------------------------------------
// A Simple Genetic Algorithm - SGA
// (c) Ding Zhen Yu 1998
// ------------------------------------------------------
// All Rights Reserved
// ------------------------------------------------------
#include
#include
#include
//#define NeedInputInitialChrom // 如果需要输入初始值,一般是因为上次没有
// 计算完成,可以接着再算
//#define NeedInputData //输入种群中第一个的大小(0~1.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 chrom[maxstring];
double x[varnumber],fitness;
unsigned int parent1,parent2,xsite;
};
struct pp oldpop[popsize],newpop[popsize],p1[popsize];
unsigned int lchrom,gen,nmutation,ncross,jcross,maxpp,minpp;
double sumfitness,avg,max,min;
double coef;
long seedl[1];
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 */
/* xx[i] 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;
seedl[0]=-9l;
//printf("initializing..........\n");
initialize();
for (i=0; i {
p1[i]=newpop[i];
newpop[i]=oldpop[i];
}
report(gen);
for (i=0; i do {
gen=gen+1;
oldmax=max;
oldmaxpp=maxpp;
generation();
statistics(newpop);
if (max {
for (j=0; j newpop[minpp].chrom[j]=oldpop[oldmaxpp].chrom[j];
for (j=0; j newpop[minpp].x[j]=oldpop[oldmaxpp].x[j];
newpop[minpp].fitness=oldpop[oldmaxpp].fitness;
statistics(newpop);
}
report(gen);
for (i=0; i {
p1[i]=oldpop[i];
oldpop[i]=newpop[i];
newpop[i]=p1[i];
}
} while (gen for (i=0; i {
xx[i]=oldpop[maxpp].x[i];
//printf("xx[%d]=%f ",i,xx[i]);
}
//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=pop[0].fitness;
min=pop[0].fitness;
max=pop[0].fitness;
maxpp=0;
minpp=0;
for (j=1;j {
sumfitness=sumfitness+pop[j].fitness;
if (pop[j].fitness>max)
{
max=pop[j].fitness;
maxpp=j;
}
if (pop[j].fitness {
min=pop[j].fitness;
minpp=j;
}
}
avg=sumfitness/(double)popsize;
}
/* new group */
void generation()
{
unsigned int j,mate1,mate2;
j=0;
do {
mate1=rselect();
mate2=rselect();
crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,j);
decode(newpop[j].chrom,newpop[j].x);
newpop[j].fitness=objfunc(newpop[j].x);
newpop[j].parent1=mate1;
newpop[j].parent2=mate2;
newpop[j].xsite=jcross;
decode(newpop[j+1].chrom,newpop[j+1].x);
newpop[j+1].fitness=objfunc(newpop[j+1].x);
newpop[j+1].parent1=mate1;
newpop[j+1].parent2=mate2;
newpop[j+1].xsite=jcross;
j=j+2;
} while (j }
/* 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;j {
//printf("j=%d\n",j);
for (j1=0;j1 oldpop[j].chrom[j1]=randomi01();
#ifdef NeedInputInitialChrom
for (j1=0;j1 scanf("%1d",&oldpop[j].chrom[j1]);
printf("%d in %d has been readed.\n",j+1,popsize);
#endif
decode(oldpop[j].chrom,oldpop[j].x);
#ifdef NeedInputInitialChrom
for (j1=0;j1 printf("x[%d]=%f\n",j1,oldpop[j].x[j1]);
#endif
oldpop[j].fitness=objfunc(oldpop[j].x);
oldpop[j].parent1=0;
oldpop[j].parent2=0;
oldpop[j].xsite=0;
}
#ifdef NeedInputData
printf("input %d initial data(0.0~1.0):\n",varnumber);
for (i=0; i scanf("%lf",&oldpop[0].x[i]);
encode(oldpop[0].chrom,oldpop[0].x);
oldpop[0].fitness=objfunc(oldpop[0].x);
oldpop[0].parent1=0;
oldpop[0].parent2=0;
oldpop[0].xsite=0;
#endif
}
/* initialization infomation output */
void initreport()
{
int j,k;
printf("\n--------------------------------------------------------------\
n");
printf(" SGA Parameters \n");
printf("--------------------------------------------------------------\n\
n");
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("------------------------------------------\n\n");
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; j printf("\n");
printf("Population Report \n");
printf("Generation %3d \n",gen);
printf("#parents xsite string x fitness \n");
for (j=0; j printf("\n");
for (j=0; j {
for (k=0; k printf("%d",newpop[j].chrom[k]);
printf("\n");
}
printf("\n");
//for (j=0; j j=maxpp;
{
printf("%d %d ",j,newpop[j].parent1);
printf("%d %d ",newpop[j].parent2,newpop[j].xsite);
//for (k=0; k // printf("%d",newpop[j].chrom[k]);
for (i=0; i printf(" %f ",newpop[j].x[i]);
printf("fitness=%f \n",newpop[j].fitness);
}
for (k=0; k 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 {
tt1=1.0;
tt=0.0;
for (j=lchrom-1-i;j>-1+(varnumber-i-1);j-=varnumber)
{
if (pp[j]) tt=tt+tt1;
tt1=2.0*tt1;
}
tt=tt/coef;//tt is between 0.0 and 1.0
//change variable's value range
x[i]=0.0001+7.0*tt/10.0;
}
}
/* encode */
void encode(unsigned int *pp,double *x)
{
int i,j,dx;
double fx;
for (i=0; i {
// 注意编码和解码相对应
fx=(x[i]-0.0001)*10.0/7.0;
fx=fx*coef;
dx=(int)(fx);
if ((fx-dx)>0.5) dx+=1;
for (j=lchrom-1-i;j>-1+(varnumber-i-1); j-=varnumber)
{
if (dx%2==1)
{
pp[j]=1;
//printf("1");
}
else
{
pp[j]=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+oldpop[j].fitness;
j=j+1;
} while ((partsum 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; j {
newpop[k5].chrom[j]=mutation(parent1[j]);
newpop[k5+1].chrom[j]=mutation(parent2[j]);
}
for (j=jcross;j {
newpop[k5].chrom[j]=mutation(parent2[j]);
newpop[k5+1].chrom[j]=mutation(parent1[j]);
}
}
else
{
for (j=0; j {
newpop[k5].chrom[j]=mutation(parent1[j]);
newpop[k5+1].chrom[j]=mutation(parent2[j]);
}
}
return 1;
}
/* Bernoulli Trials */
int flip(double probability)
{
double ppp;
ppp=randomd01();
if (ppp return 1;
else
return 0;
}
/* return a double random number between 0.0~1.0 */
double randomd01()
{
int j;
long k;
static long idum2=123456789L;
static long iy=0L;
static long iv[32];
double temp;
if (seedl[0] if (-seedl[0] < 1L) seedl[0] = 1L;
else seedl[0] = -seedl[0];
idum2 = seedl[0];
for (j=32+7;j>=0;j--) {
k = seedl[0]/53668L;
seedl[0] = 40014L * (seedl[0]-k*53668L)-k*12211L;
if (seedl[0] < 0L) seedl[0] += 2147483563L;
if (j < 32) iv[j] = seedl[0];
}
iy=iv[0];
}
k = seedl[0]/53668L;
seedl[0] = 40014L*(seedl[0]-k*53668L)-k*12211L;
if (seedl[0] < 0L) seedl[0] += 2147483563L;
k = idum2/52774L;
idum2 = 40692L*(idum2-k*52774L)-k*3791L;
if (idum2 < 0L) idum2 += 2147483399L;
j = (int)(iy/(1L+2147483562L/32L)) ;
iy = iv[j]-idum2;
iv[j] = seedl[0];
if (iy < 1L) iy += 2147483562L;
if ((temp=(double)(iy)/(double)(2147483563L)) > (1.0-1.2e-7 ))
return (1.0-1.2e-7) ;
else return temp;
}
/* return a integer random number between 0 and 1 */
int randomi01()
{
if (randomd01()>0.5) return 1;
else return 0;
}
/* return a interger random number amang 1 and lchrom-1 */
int randomi(int low, int high)
{
int i;
if (low>=high)
i=low;
else
{
i=(int)(randomd01()*lchrom);
if (i>high) i=high;
}
return i;
}
10
20
30
40
50
60
70
80
--
i'm the best,so i will do the best!
