yichuan.txt

* 这里是遗传算法的核心框架遗传算法的步骤： * 遗传算法核心部分的算法描述 * 算法步骤： * 1、初始化 * 1.1、生成初始种群编码 * 1.2、计算每个个体的适配值。

遗传算法的实现

// gasample.cpp : Defines the entry point for the console application.
//
#include <stdio.h>
#include "malloc.h"
#include <math.h>
#include "stdlib.h"
/* 全局变量 */
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];
    
     printf("种群大小(50-200)：");
     scanf("%d", &popsize);
      if((popsize%2) != 0)
        {
printf( "种群大小已设置为偶数\n");
popsize++;
        };
   
    printf("染色体长度(64-1000)：");
     scanf("%d", &lchrom);
   
     printf("是否输出染色体编码(y/n)：");
     printstrings=1;
     scanf("%s", answer);
      //if(strncmp(answer,"n",1) == 0) printstrings = 0;
     printf("最大世代数(100-300)：");
     scanf("%d", &maxgen);
   
     printf("交叉率(0.2-0.99)：");
     scanf("%f", &pcross);
  
     printf("变异率(0.01-0.9)：");
     scanf("%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);
      printf("               基本遗传算法参数\n");
      printf(" -------------------------------------------------\n");
      printf("      种群大小(popsize)       =     %d\n",popsize);
      printf("      染色体长度(lchrom)      =     %d\n",lchrom);
      printf("      最大进化代数(maxgen)    =     %d\n",maxgen);
      printf("      交叉概率(pcross)          = %f\n", pcross);
      printf("      变异概率(pmutation)       = %f\n", pmutation);
      printf(" -------------------------------------------------\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].chrom);
      }
    free(oldpop);
    free(newpop);
    free(bestfit.chrom);
     }

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

void report()      /* 输出种群统计结果 */
{
      //void    repchar(), skip();
      //void    writepop(), writestats();
      repchar(outfp,"-",80);
      skip(outfp,1); 
      if(printstrings == 1)
      {
          repchar(outfp," ",((80-17)/2));
          printf("模拟计算统计报告    \n");
          printf( "世代数 %3d", gen);
          repchar(outfp," ",(80-28));
          printf( "世代数 %3d\n", (gen+1));
          printf("个体    染色体编码");
          repchar(outfp," ",lchrom-5);
          printf("适应度      父个体 交叉位置    ");
          printf("染色体编码 ");
          repchar(outfp," ",lchrom-5);
          printf("适应度\n");
          repchar(outfp,"-",80);
          skip(outfp,1);
         // writepop(outfp);
          repchar(outfp,"-",80);
          skip(outfp,1);
       }
      printf("第 %d 代统计: \n",gen);
      printf("总交叉操作次数 = %d, 总变异操作数 = %d\n",ncross,nmutation);
      printf(" 最小适应度：%f 最大适应度：%f    平均适应度 %f\n", min,max,avg);
      printf(" 迄今发现最佳个体 => 所在代数： %d    ", bestfit.generation);
      printf(" 适应度：%f    染色体：", bestfit.fitness);
      writechrom((&bestfit)->chrom);
      printf(" 对应的变量值: %f", bestfit.varible);
      skip(outfp,1);
      repchar(outfp,"-",80);
      skip(outfp,1);  
void writepop()
{
      struct individual *pind;
      int j;
      for(j=0; j<popsize; j++)
      {
          printf("%3d)    ",j+1);
          /* 当前代个体 */
          pind = &(oldpop[j]);
          writechrom(pind->chrom);
         printf("    %8f | ", pind->fitness);
          /* 新一代个体 */
          pind = &(newpop[j]);
          printf("(%2d,%2d)     %2d     ",
          pind->parent[0], pind->parent[1], pind->xsite);
          writechrom(pind->chrom);
          printf("    %8f\n", pind->fitness);
      }
}

void writechrom(unsigned *chrom) /* 输出染色体编码 */
{
      int j, k, stop;
      unsigned mask = 1, tmp;
      for(k = 0; k < chromsize; k++)
      {
          tmp = chrom[k];
          if(k == (chromsize-1))
              stop = lchrom - (k*(8*sizeof(unsigned)));
          else
              stop =8*sizeof(unsigned);
          for(j = 0; j < stop; j++)
          {
              if(tmp&mask)
                  printf("1");
              else
                  printf("0");
              tmp = tmp>>1;
          }
      }
}

void preselect()