sga.c

最近研究遗传算法

/********************************************************************/
/*         基于基本遗传算法的分层遗传改进算法函数最优化   SHGA.C    */
/*     A Function Optimizer using Simple Genetic Algorithm          */
/* developed from the Pascal SGA code presented by David E.Goldberg */
/*              华南理工大学电子与信息学院   苏勇          2004年4月*/
/********************************************************************/
#include <stdio.h>
#include <math.h>
/* 全局变量 */
struct individual                       /* 个体*/
{
    unsigned *chrom;                    /* 染色体 */
    double   fitness;                   /* 个体适应度*/
    double   varible;                   /* 个体对应的变量值*/   
    int      xsite;                     /* 低层交叉位置 */
	int		 xsiteA;					/* 高层交叉位置 */
    int      parent[2];                 /* 父个体  */
	int		 parentA[2];				/* 高层父个体(父代子群) */
    int      *utility;                  /* 特定数据指针变量 */
};
struct bestever                         /* 最佳个体*/
{
    unsigned *chrom;                    /* 低层遗传运算所得最佳个体染色体*/
	unsigned *chromA;					/* 全局最佳个体染色体 */
    double   fitness;                   /* 最佳个体适应度 */
    double   varible;                   /* 最佳个体对应的变量值 */
    int      generation;                /* 最佳个体生成代 */
	int		 subpopulation;				/* 最佳个体所在子种群 */
};
 struct individual **oldpop;            /* 当前代种群 */
 struct individual **newpop;            /* 新一代种群 */
 struct bestever bestfit;               /* 最佳个体 */
 double sumfitness;                     /* 种群中个体适应度累计 */
 double sumA;							/* 所有子群平均适应度累计 */
 double max;                            /* 种群中个体最大适应度 */
 double maxA;							/* 全局最佳适应度值 */
 double avg;                            /* 种群中个体平均适应度 */
 double min;                            /* 种群中个体最小适应度 */
 double minA;							/* 全局最小适应度值 */
 double *A;								/* 子群平均适应度值数组 */
 float  pcross;                         /* 低层交叉概率 */
 float  pcrossA;						/* 高层交叉概率 */
 float  pmutation;                      /* 低层变异概率 */
 float  pmutationA;						/* 高层变异概率 */
 int    popsize;                        /* 种群大小  */
 int    lchrom;                         /* 染色体长度*/
 int    chromsize;                      /* 存储一染色体所需字节数 */
 int    gen;                            /* 当前世代数 */
 int    maxgen;                         /* 最大世代数   */
 int    run;                            /* 低层遗传当前运行次数 */
 int	runA;							/* 高层遗传当前运行次数 */
 int    maxruns;                        /* 总运行次数   */
 int    printstrings;                   /* 输出染色体编码的判断，0 -- 不输出, 1 -- 输出 */
 int    nmutation;                      /* 低层当前代变异发生次数 */
 int	nmutationA;						/* 高层当前代变异发生次数 */
 int    ncross;                         /* 低层当前代交叉发生次数 */
 int	ncrossA;						/* 高层当前代交叉发生次数 */
 int	subpopnum;						/* 子种群个数 */
 int	subpop;							/* 当前子种群 */
 float	randomseed;						/* 随机数种子 */
 int	shu;							/* 当前子群 */
 double varibleA;						/* 全局最佳染色体对应变量值 */
 int	genA;							/* 全局最佳染色体所在代数 */
/* 随机数发生器使用的静态变量 */
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 reportA();
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 CMTransA();
int selectA();
void preselectA();

void initialize()      /* 遗传算法初始化 */
{
    /* 键盘输入遗传算法参数 */
    initdata();
    /* 确定染色体的字节长度 */
    chromsize = (lchrom/(8*sizeof(unsigned)));
    if(lchrom%(8*sizeof(unsigned))) chromsize++;
    /*分配给全局数据结构空间 */
    initmalloc();
    initreport();
}

void initdata()           /* 遗传算法参数输入 */
{
   char  answer[2];
   popsize=30;
   if((popsize%2) != 0)
   {
	 fprintf(outfp, "种群大小已设置为偶数\n");
	 popsize++;
   }
   lchrom=22;			/* 染色体长度定义为22 */
   printstrings=1;
   maxgen=100;			/* 低层运算100代 */
   pcross=0.8;			/* 低层交叉概率0.8 */
   pcrossA=0.2;			/* 高层交叉概率0.6 */
   pmutation=0.05;		/* 低层变异概率0.05 */
   pmutationA=0.05;		/* 高层变异概率0.05 */
   genA=maxgen;			
}

void initpop()           /* 随机初始化种群 */
{
    int j, j1, k, stop;
    unsigned mask = 1;
    for(j = 0; j < popsize; j++)
    {
		
        for(k = 0; k < chromsize; k++)
        {
            oldpop[subpop][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[subpop][j].chrom[k] = oldpop[subpop][j].chrom[k]<<1;
               if(flip(randomseed))
                  oldpop[subpop][j].chrom[k] = oldpop[subpop][j].chrom[k]|mask;
            }
        }
        oldpop[subpop][j].parent[0] = 0;     /* 初始父个体信息 */
        oldpop[subpop][j].parent[1] = 0;
		oldpop[subpop][0].parentA[0]= 0;
		oldpop[subpop][0].parentA[1]= 0;
        oldpop[subpop][j].xsite = 0;
		oldpop[subpop][0].xsiteA= 0;
        objfunc(&(oldpop[subpop][j]));       /* 计算初始适应度*/
    }
	if(subpop==0)
	{
		maxA = oldpop[0][0].fitness;
		minA = oldpop[0][0].fitness;
	}
}

void initreport()               /* 初始参数输出 */
{
    void   skip();
    skip(outfp,1);
    fprintf(outfp,"             基本遗传算法参数\n");
    fprintf(outfp," -------------------------------------------------\n");
	fprintf(outfp,"    子种群数(subpopnum)   =   %d\n",subpopnum);
    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[subpop][mate1].chrom, oldpop[subpop][mate2].chrom, newpop[subpop][j].chrom, newpop[subpop][j+1].chrom);
      mutation(newpop[subpop][j].chrom);
      mutation(newpop[subpop][j+1].chrom);
      /* 解码, 计算适应度 */
      objfunc(&(newpop[subpop][j]));
      /*记录亲子关系和交叉位置 */
      newpop[subpop][j].parent[0] = mate1+1;
      newpop[subpop][j].xsite = jcross;
      newpop[subpop][j].parent[1] = mate2+1;
      objfunc(&(newpop[subpop][j+1]));
      newpop[subpop][j+1].parent[0] = mate1+1;
      newpop[subpop][j+1].xsite = jcross;
      newpop[subpop][j+1].parent[1] = mate2+1;
      j = j + 2;
    }
  while(j < (popsize-1));

}

void CMTransA()					/* 高层交叉变异 */
{
	int mateA1, mateA2, jcrossA = 0, k, h, m, j1, j=0;
	unsigned mask = 1;
	int stop;
	preselectA();
	do
	{
		/*////////////  高层交叉 ///////////////*/
		mateA1 = selectA();
		mateA2 = selectA();
		
		if(flip(pcrossA))
		{
			jcrossA = (int)rnd(1 ,(popsize - 1));
			ncrossA++;
			for(m = jcrossA; m < popsize; m++)
			{
				for(k=0;k< chromsize; k++)
				{
					oldpop[mateA1][m].chrom[k] = newpop[j+1][m].chrom[k];
					oldpop[mateA2][m].chrom[k] = newpop[j][m].chrom[k];
				}
			}
			for(m = 0; m < jcrossA; m++)
			{
				for(k=0;k< chromsize; k++)
				{
					oldpop[mateA1][m].chrom[k] = newpop[j][m].chrom[k];
					oldpop[mateA2][m].chrom[k] = newpop[j+1][m].chrom[k];
				}
			}
		}
		else
		{
			for(m = 0; m< popsize; m++)
			{
				for(k=0;k<chromsize;k++)
				{
					oldpop[mateA1][m].chrom[k] = newpop[j][m].chrom[k];
					oldpop[mateA2][m].chrom[k] = newpop[j+1][m].chrom[k];
				}
			}
			jcrossA=0;
		}
		/*////////////  高层变异 ////////////////*/
		if(flip(pmutationA))
        {
			nmutationA++;
			for(h = 0; h < chromsize; h++)
			{
				newpop[j][m].chrom[h] = 0;
				if(h == (chromsize-1))
					stop = lchrom - (h*(8*sizeof(unsigned)));
				else
					stop =8*sizeof(unsigned);
				for(j1 = 1; j1 <= stop; j1++)
				{
					newpop[j][m].chrom[h] = newpop[j][m].chrom[h]<<1;
					if(flip(0.5))
						newpop[j][m].chrom[h] = newpop[j][m].chrom[h]|mask;
				}
			}
		}
		if(flip(pmutation))
        {
			nmutationA++;
			for(h = 0; h < chromsize; h++)
			{
				newpop[j+1][m].chrom[h] = 0;
				if(h == (chromsize-1))
					stop = lchrom - (h*(8*sizeof(unsigned)));
				else
					stop =8*sizeof(unsigned);
				for(j1 = 1; j1 <= stop; j1++)
				{
					newpop[j+1][m].chrom[h] = newpop[j+1][m].chrom[h]<<1;
					if(flip(0.5))
						newpop[j+1][m].chrom[h] = newpop[j+1][m].chrom[h]|mask;
				}
			}
		}

		/* 解码, 计算适应度 */
		for(k = 0; k < popsize; k++)
			objfunc(&(newpop[j][k]));
		for(k = 0; k < popsize; k++)
			objfunc(&(newpop[j+1][k]));
		newpop[j+1][0].parentA[0] = mateA1+1;
		newpop[j+1][0].xsiteA = jcrossA;
		newpop[j+1][0].parentA[1] = mateA2+1;
		j = j + 2;
	}
	while(j<(subpopnum-1));
}

void initmalloc()              /*为全局数据变量分配空间 */
{
  unsigned nbytes;
  char  *malloc();
  int i,j;
  /* 分配给当前代和新一代种群内存空间 */
  if((A = (double *) malloc(subpopnum*sizeof(double))) == NULL)
    nomemory("A");
  nbytes = popsize*sizeof(struct individual);
  if((oldpop = (struct individual **) malloc(subpopnum*4)) == NULL)
    nomemory("oldpop");
  for(j=0; j<subpopnum;j++)
  {
	if((oldpop[j] = (struct individual *) malloc(nbytes)) == NULL)
		nomemory("oldpop[j]");
  }
  if((newpop = (struct individual **) malloc(subpopnum*4)) == NULL)
    nomemory("newpop");
  for(j=0; j<subpopnum;j++)
  {
	if((newpop[j] = (struct individual *) malloc(nbytes)) == NULL)
		nomemory("newpop[j]");
  }
  /* 分配给染色体内存空间 */
  nbytes = chromsize*sizeof(unsigned);
  for(j = 0; j < popsize; j++)
    {
	  for(i=0;i<subpopnum;i++)
	  {
		if((oldpop[i][j].chrom = (unsigned *) malloc(nbytes)) == NULL)
			nomemory("oldpop[i] chromosomes");
		if((newpop[i][j].chrom = (unsigned *) malloc(nbytes)) == NULL)
			nomemory("newpop[i] chromosomes");
	  }
    }
  if((bestfit.chrom = (unsigned *) malloc(nbytes)) == NULL)
    nomemory("bestfit chromosome");
  if((bestfit.chromA = (unsigned *) malloc(nbytes)) == NULL)
    nomemory("bestfit chromosomeA");

}

void freeall()               /* 释放内存空间 */
{
  int i,j;
   for(i = 0; i < popsize; i++)
    {
	   for(j=0;j<subpopnum;j++)
	   {
		free(oldpop[j][i].chrom);
		free(newpop[j][i].chrom);
	   }
    }
  free(A);
  for(j=0;j<subpopnum;j++)
  free(oldpop[j]);
  free(oldpop);
  for(j=0;j<subpopnum;j++)
  free(newpop[j]);
  free(newpop);
  free(bestfit.chrom);
  free(bestfit.chromA);
}

void nomemory(string)        /* 内存不足，退出*/
  char *string;
{
  fprintf(outfp,"malloc: out of memory making %s!!\n",string);
  exit(-1);
}

void reportA()
{
	void   skip();
	int i,j,s;
	fprintf(outfp,"第1次高层交叉变异统计报告\n");
	repchar(outfp,"-",80);
	skip(outfp,1); 
	for(s=0;s<subpopnum-1;s+=2)
	{
		fprintf(outfp, "   第%d子种群   ", s+1);
		repchar(outfp, " ",lchrom-10);
		fprintf(outfp, "  适应度值   ");
		repchar(outfp, " ",2);
		fprintf(outfp, "   第%d子种群   ", s+2);
		repchar(outfp, " ",lchrom-6);
		fprintf(outfp, "  适应度值   ");
		fprintf(outfp, "  父代子群:");
		fprintf(outfp, "(%2d,%2d)", newpop[s+1][0].parentA[0],newpop[s+1][0].parentA[1]);
		skip(outfp,1); 
		for(i=0;i<popsize-1;i++)
		{
			fprintf(outfp, "%2d) ",i+1);
			writechrom((&newpop[s][i])->chrom);
			repchar(outfp, " ",2);
			fprintf(outfp, "  %f  " ,newpop[s][i].fitness); 
			repchar(outfp, " ",5);
			fprintf(outfp, "%2d) ",i+1);
			writechrom((&newpop[s][i+1])->chrom);
			repchar(outfp, " ",2);
			fprintf(outfp, "  %f  " ,newpop[s][i+1].fitness); 
			skip(outfp,1);
		}
		repchar(outfp,"-",80);
		skip(outfp,1);
		fprintf(outfp, "高层交叉次数:  %d  ,  高层变异次数:  %d ",ncrossA,nmutationA);
		skip(outfp,1);
	}
	fprintf(outfp," 迄今发现最佳个体   =>  所在分层: %d 所在子群: %d  所在代数: %d ", runA,bestfit.subpopulation , genA);
	fprintf(outfp," 适应度：%f  染色体: ", maxA);
	writechrom((&bestfit)->chromA);
	fprintf(outfp," 对应的变量值: %f", varibleA);
	skip(outfp,1);
	fprintf(outfp," 迄今发现最小适应度 => %f ",minA);
	skip(outfp,1);
	repchar(outfp,"-",80);
	skip(outfp,1);  
}

void report()                /* 输出种群统计结果 */
{
    void  repchar(), skip();
    void  writepop(), writestats();
    repchar(outfp,"-",80);
    skip(outfp,1); 
    if(printstrings == 1)
    {
        repchar(outfp," ",((80-17)/2));
        fprintf(outfp,"第%d子种群模拟计算统计报告  \n",(subpop+1));
        fprintf(outfp, "世代数 %3d", gen);
        repchar(outfp," ",(80-28));
        fprintf(outfp, "世代数 %3d\n", (gen+1));
        fprintf(outfp,"个体  染色体编码");
        repchar(outfp," ",lchrom-5);
        fprintf(outfp,"适应度    父个体 交叉位置  ");
        fprintf(outfp,"染色体编码 ");
        repchar(outfp," ",lchrom-5);
        fprintf(outfp,"适应度\n");
        repchar(outfp,"-",80);
        skip(outfp,1);
        writepop(outfp);
        repchar(outfp,"-",80);
        skip(outfp,1);
     }
    fprintf(outfp," 第 %d 代统计: \n",gen);
    fprintf(outfp," 总交叉操作次数 = %d, 总变异操作数 = %d\n",ncross,nmutation);