ga_sin.cpp
上传用户:fyx129
上传日期:2013-05-22
资源大小:150k
文件大小:17k
源码类别:

控制台编程

开发平台:

Visual C++

  1. #include <stdio.h>
  2. #include "malloc.h"
  3. #include <math.h>
  4. #include "stdlib.h"
  5. /* 全局变量 */
  6. struct individual                       /* 个体*/
  7. {
  8.     unsigned *chrom;                    /* 染色体 */
  9.     double   fitness;                   /* 个体适应度*/
  10.     double   varible;                   /* 个体对应的变量值*/
  11.     int      xsite;                     /* 交叉位置 */
  12.     int      parent[2];                 /* 父个体  */
  13.     int      *utility;                  /* 特定数据指针变量 */
  14. };
  15. struct bestever                         /* 最佳个体*/
  16. {
  17.     unsigned *chrom;                    /* 最佳个体染色体*/
  18.     double   fitness;                   /* 最佳个体适应度 */
  19.     double   varible;                   /* 最佳个体对应的变量值 */
  20.     int      generation;                /* 最佳个体生成代 */
  21. };
  22.  struct individual *oldpop;             /* 当前代种群 */
  23.  struct individual *newpop;             /* 新一代种群 */
  24.  struct bestever bestfit;               /* 最佳个体 */
  25.  double sumfitness;                     /* 种群中个体适应度累计 */
  26.  double max;                            /* 种群中个体最大适应度 */
  27.  double avg;                            /* 种群中个体平均适应度 */
  28.  double min;                            /* 种群中个体最小适应度 */
  29.  float  pcross;                         /* 交叉概率 */
  30.  float  pmutation;                      /* 变异概率 */
  31.  int    popsize;                        /* 种群大小  */
  32.  int    lchrom;                         /* 染色体长度*/
  33.  int    chromsize;                      /* 存储一染色体所需字节数 */
  34.  int    gen;                            /* 当前世代数 */
  35.  int    maxgen;                         /* 最大世代数   */
  36.  int    run;                            /* 当前运行次数 */
  37.  int    maxruns;                        /* 总运行次数   */
  38.  int    printstrings;                   /* 输出染色体编码的判断,0 -- 不输出, 1 -- 输出 */
  39.  int    nmutation;                      /* 当前代变异发生次数 */
  40.  int    ncross;                         /* 当前代交叉发生次数 */
  41. /* 随机数发生器使用的静态变量 */
  42. static double oldrand[55];
  43. static int jrand;
  44. static double rndx2;
  45. static int rndcalcflag;
  46. /* 输出文件指针 */
  47. FILE *outfp ;
  48. /* 函数定义 */
  49. void advance_random();
  50. int flip(float);rnd(int, int);
  51. void randomize();
  52. double randomnormaldeviate();
  53. float randomperc(),rndreal(float,float);
  54. void warmup_random(float);
  55. void initialize(),initdata(),initpop();
  56. void initreport(),generation(),initmalloc();
  57. void freeall(),nomemory(char *),report();
  58. void writepop(),writechrom(unsigned *);
  59. void preselect();
  60. void statistics(struct individual *);
  61. void title(),repchar (FILE *,char *,int);
  62. void skip(FILE *,int);
  63. int select();
  64. void objfunc(struct individual *);
  65. int crossover (unsigned *, unsigned *, unsigned *, unsigned *);
  66. void mutation(unsigned *);
  67. void initialize()  /* 遗传算法初始化 */
  68. {
  69.     /* 键盘输入遗传算法参数 */
  70.     initdata();
  71.     /* 确定染色体的字节长度 */
  72.     chromsize = (lchrom/(8*sizeof(unsigned)));
  73.     if(lchrom%(8*sizeof(unsigned))) chromsize++;
  74.     /*分配给全局数据结构空间 */
  75.     initmalloc();
  76.     /* 初始化随机数发生器 */
  77.     randomize();
  78.     /* 初始化全局计数变量和一些数值*/
  79.     nmutation = 0;
  80.     ncross = 0;
  81.     bestfit.fitness = 0.0;
  82.     bestfit.generation = 0;
  83.     /* 初始化种群,并统计计算结果 */
  84.     initpop();
  85.     statistics(oldpop);
  86.     initreport();
  87. }
  88. void initdata()   /* 遗传算法参数输入 */
  89. {
  90.    char  answer[2];
  91.     
  92.    printf("种群大小(50-200):");
  93.    scanf("%d", &popsize);
  94.     if((popsize%2) != 0)
  95.       {
  96. printf( "种群大小已设置为偶数n");
  97. popsize++;
  98.       };
  99.    
  100.   printf("染色体长度(8-1000):");
  101.    scanf("%d", &lchrom);
  102.    
  103.    printf("是否输出染色体编码(y/n):");
  104.    printstrings=1;
  105.    scanf("%s", answer);
  106.     //if(strncmp(answer,"n",1) == 0) printstrings = 0;
  107.    printf("最大世代数(50-300):");
  108.    scanf("%d", &maxgen);
  109.    
  110.    printf("交叉率(0.2-0.99):");
  111.    scanf("%f", &pcross);
  112.   
  113.    printf("变异率(0.01-0.9):");
  114.    scanf("%f", &pmutation);
  115. }
  116. void initpop()  /* 随机初始化种群 */
  117. {
  118.     int j, j1, k, stop;
  119.     unsigned mask = 1;
  120.     for(j = 0; j < popsize; j++)
  121.     {
  122.         for(k = 0; k < chromsize; k++)
  123.         {
  124.             oldpop[j].chrom[k] = 0;
  125.             if(k == (chromsize-1))
  126.                 stop = lchrom - (k*(8*sizeof(unsigned)));
  127.             else
  128.                 stop =8*sizeof(unsigned);
  129.             for(j1 = 1; j1 <= stop; j1++)
  130.             {
  131.                oldpop[j].chrom[k] = oldpop[j].chrom[k]<<1;
  132.                if(flip(0.5))
  133.                   oldpop[j].chrom[k] = oldpop[j].chrom[k]|mask;
  134.             }
  135.         }
  136.         oldpop[j].parent[0] = 0; /* 初始父个体信息 */
  137.         oldpop[j].parent[1] = 0;
  138.         oldpop[j].xsite = 0;
  139.         objfunc(&(oldpop[j]));  /* 计算初始适应度*/
  140.     }
  141. }
  142. void initreport()  /* 初始参数输出 */
  143. {
  144.    // void   skip();
  145.     skip(outfp,1);
  146.     printf("             基本遗传算法参数n");
  147.     printf(" -------------------------------------------------n");
  148.     printf("    种群大小(popsize)     =   %dn",popsize);
  149.     printf("    染色体长度(lchrom)    =   %dn",lchrom);
  150.     printf("    最大进化代数(maxgen)  =   %dn",maxgen);
  151.     printf("    交叉概率(pcross)        = %fn", pcross);
  152.     printf("    变异概率(pmutation)     = %fn", pmutation);
  153.     printf(" -------------------------------------------------n");
  154.     skip(outfp,1);
  155.     fflush(outfp);
  156. }
  157. void generation()
  158. {
  159.   int mate1, mate2, jcross, j = 0;
  160.   /*  每代运算前进行预选 */
  161.   preselect();
  162.   /* 选择, 交叉, 变异 */
  163.   do
  164.     {
  165.       /* 挑选交叉配对 */
  166.       mate1 = select();
  167.       mate2 = select();
  168.       /* 交叉和变异 */
  169.       jcross = crossover(oldpop[mate1].chrom, oldpop[mate2].chrom, newpop[j].chrom, newpop[j+1].chrom);
  170.       mutation(newpop[j].chrom);
  171.       mutation(newpop[j+1].chrom);
  172.       /* 解码, 计算适应度 */
  173.       objfunc(&(newpop[j]));
  174.       /*记录亲子关系和交叉位置 */
  175.       newpop[j].parent[0] = mate1+1;
  176.       newpop[j].xsite = jcross;
  177.       newpop[j].parent[1] = mate2+1;
  178.       objfunc(&(newpop[j+1]));
  179.       newpop[j+1].parent[0] = mate1+1;
  180.       newpop[j+1].xsite = jcross;
  181.       newpop[j+1].parent[1] = mate2+1;
  182.       j = j + 2;
  183.     }
  184.   while(j < (popsize-1));
  185. }
  186. void initmalloc()     /*为全局数据变量分配空间 */
  187. {
  188.   unsigned nbytes;
  189.   //char  *malloc();
  190.   int j;
  191.   /* 分配给当前代和新一代种群内存空间 */
  192.   nbytes = popsize*sizeof(struct individual);
  193.   if((oldpop = (struct individual *) malloc(nbytes)) == NULL)
  194.     nomemory("oldpop");
  195.   if((newpop = (struct individual *) malloc(nbytes)) == NULL)
  196.     nomemory("newpop");
  197.   /* 分配给染色体内存空间 */
  198.   nbytes = chromsize*sizeof(unsigned);
  199.   for(j = 0; j < popsize; j++)
  200.     {
  201.       if((oldpop[j].chrom = (unsigned *) malloc(nbytes)) == NULL)
  202. nomemory("oldpop chromosomes");
  203.       if((newpop[j].chrom = (unsigned *) malloc(nbytes)) == NULL)
  204. nomemory("newpop chromosomes");
  205.     }
  206.   if((bestfit.chrom = (unsigned *) malloc(nbytes)) == NULL)
  207.     nomemory("bestfit chromosome");
  208. }
  209. void freeall()    /* 释放内存空间 */
  210. {
  211.   int i;
  212.    for(i = 0; i < popsize; i++)
  213.     {
  214.       free(oldpop[i].chrom);
  215.       free(newpop[i].chrom);
  216.     }
  217.   free(oldpop);
  218.   free(newpop);
  219.   free(bestfit.chrom);
  220.    }
  221. void nomemory(char *string) /* 内存不足,退出*/
  222. {
  223.   printf("malloc: out of memory making %s!!n",string);
  224.   exit(-1);
  225. }
  226. void report()    /* 输出种群统计结果 */
  227. {
  228.     //void  repchar(), skip();
  229.     //void  writepop(), writestats();
  230.     repchar(outfp,"-",80);
  231.     skip(outfp,1); 
  232.     if(printstrings == 1)
  233.     {
  234.         repchar(outfp," ",((80-17)/2));
  235.         printf("模拟计算统计报告  n");
  236.         printf( "世代数 %3d", gen);
  237.         repchar(outfp," ",(80-28));
  238.         printf( "世代数 %3dn", (gen+1));
  239.         printf("个体  染色体编码");
  240.         repchar(outfp," ",lchrom-5);
  241.         printf("适应度    父个体 交叉位置  ");
  242.         printf("染色体编码 ");
  243.         repchar(outfp," ",lchrom-5);
  244.         printf("适应度n");
  245.         repchar(outfp,"-",80);
  246.         skip(outfp,1);
  247.        // writepop(outfp);
  248.         repchar(outfp,"-",80);
  249.         skip(outfp,1);
  250.      }
  251.     printf("第 %d 代统计: n",gen);
  252.     printf("总交叉操作次数 = %d, 总变异操作数 = %dn",ncross,nmutation);
  253.     printf(" 最小适应度:%f 最大适应度:%f  平均适应度 %fn", min,max,avg);
  254.     printf(" 迄今发现最佳个体 => 所在代数: %d  ", bestfit.generation);
  255.     printf(" 适应度:%f  染色体:", bestfit.fitness);
  256.     writechrom((&bestfit)->chrom);
  257.     printf(" 对应的变量值: %f", bestfit.varible);
  258.     skip(outfp,1);
  259.     repchar(outfp,"-",80);
  260.     skip(outfp,1);  
  261. }
  262. void writepop()
  263. {
  264.     struct individual *pind;
  265.     int j;
  266.     for(j=0; j<popsize; j++)
  267.     {
  268.         printf("%3d)  ",j+1);
  269.         /* 当前代个体 */
  270.         pind = &(oldpop[j]);
  271.         writechrom(pind->chrom);
  272.        printf("  %8f | ", pind->fitness);
  273.         /* 新一代个体 */
  274.         pind = &(newpop[j]);
  275.         printf("(%2d,%2d)   %2d   ",
  276.         pind->parent[0], pind->parent[1], pind->xsite);
  277.         writechrom(pind->chrom);
  278.         printf("  %8fn", pind->fitness);
  279.     }
  280. }
  281. void writechrom(unsigned *chrom) /* 输出染色体编码 */
  282. {
  283.     int j, k, stop;
  284.     unsigned mask = 1, tmp;
  285.     for(k = 0; k < chromsize; k++)
  286.     {
  287.         tmp = chrom[k];
  288.         if(k == (chromsize-1))
  289.             stop = lchrom - (k*(8*sizeof(unsigned)));
  290.         else
  291.             stop =8*sizeof(unsigned);
  292.         for(j = 0; j < stop; j++)
  293.         {
  294.             if(tmp&mask)
  295.                 printf("1");
  296.             else
  297.                 printf("0");
  298.             tmp = tmp>>1;
  299.         }
  300.     }
  301. }
  302. void preselect()
  303. {
  304. int i=0;
  305. sumfitness=0;
  306. for(i=0;i<popsize;i++)
  307. sumfitness+=oldpop[i].fitness;
  308.    
  309. }
  310. int select()  /* 轮盘赌选择*/////////////////////////////////////////////////////////////
  311. {
  312.     
  313.     float sum,r;
  314. int i,tag=0;
  315.     
  316.     sum = 0;
  317. r=randomperc();
  318.        for(i = 0; i < popsize; i++)
  319.    {sum+=oldpop[i].fitness/sumfitness;
  320.    if(sum>r)  {tag=i; break;}
  321.    }
  322.    return tag;
  323. }
  324. void statistics(struct individual *pop)  /* 计算种群统计数据 */
  325. {
  326.     int i, j;
  327.     sumfitness = 0.0;
  328.     min = pop[0].fitness;
  329.     max = pop[0].fitness;
  330.     /* 计算最大、最小和累计适应度 */
  331.     for(j = 0; j < popsize; j++)
  332.     {
  333.         sumfitness = sumfitness + pop[j].fitness;            
  334.         if(pop[j].fitness > max) max = pop[j].fitness;        
  335.         if(pop[j].fitness < min) min = pop[j].fitness;         
  336.         /* new global best-fit individual */
  337.         if(pop[j].fitness > bestfit.fitness)
  338.   {
  339.    for(i = 0; i < chromsize; i++)
  340.     bestfit.chrom[i]      = pop[j].chrom[i];
  341.             bestfit.fitness    = pop[j].fitness;
  342.             bestfit.varible   = pop[j].varible;
  343.             bestfit.generation = gen;
  344.   }
  345.       }
  346.     /* 计算平均适应度 */
  347.     avg = sumfitness/popsize;
  348. }
  349. void title()
  350. {
  351.   
  352.   printf("SGA Optimizer");
  353.   
  354.   printf("基本遗传算法");
  355. }
  356. void repchar (FILE *outfp,char *ch,int repcount)
  357. {
  358.     int j;
  359.     for (j = 1; j <= repcount; j++) printf("%s", ch);
  360. }
  361. void skip(FILE *outfp,int skipcount)
  362. {
  363.     int j;
  364.     for (j = 1; j <= skipcount; j++) printf("n");
  365. }
  366. void objfunc(struct individual *critter)  /* 计算适应度函数值 */
  367. {
  368.     unsigned mask=1;
  369.     unsigned bitpos;
  370.     unsigned tp;
  371.     double  bitpow ;
  372.     int i,j, k, stop,x;
  373.     critter->varible = 0.0;
  374.     for(k = 0; k < chromsize; k++)
  375.     {
  376.         if(k == (chromsize-1))
  377.             stop = lchrom-(k*(8*sizeof(unsigned)));
  378.         else
  379.             stop =8*sizeof(unsigned);
  380.         tp = critter->chrom[k];
  381.         for(j = 0; j < stop; j++)
  382.         {
  383.             bitpos = j + (8*sizeof(unsigned))*k;
  384.             if((tp&mask) == 1)
  385.             {
  386. bitpow=1;
  387.                 for(x=1;x<=bitpos+1;x++)
  388.    bitpow = bitpow*0.5;
  389.                 critter->varible = critter->varible + bitpow;
  390.             }
  391.             tp = tp>>1;
  392.         }
  393.     }
  394.     critter->varible =(critter->varible)*5*3.141593;
  395.     critter->fitness =sin(critter->varible);
  396. for(i=1;i<6;i++)
  397. critter->fitness*=critter->fitness;
  398. }
  399. void  mutation(unsigned *child)   /*变异操作*/
  400. {
  401.     int j, k, stop;
  402.     unsigned mask, temp = 1;
  403.     for(k = 0; k < chromsize; k++)
  404.     {
  405.         mask = 0;
  406.         if(k == (chromsize-1))
  407.             stop = lchrom - (k*(8*sizeof(unsigned)));
  408.         else
  409.             stop = 8*sizeof(unsigned);
  410.         for(j = 0; j < stop; j++)
  411.         {
  412.             if(flip(pmutation))
  413.             {
  414.                 mask = mask|(temp<<j);
  415.                 nmutation++;
  416.             }
  417.         }
  418.         child[k] = child[k]^mask;
  419.     }
  420. }
  421. int crossover (unsigned *parent1, unsigned *parent2, unsigned *child1, unsigned *child2)
  422. /* 由两个父个体交叉产生两个子个体 */
  423. {
  424.     int j, jcross, k;
  425.     unsigned mask, temp;
  426.     if(flip(pcross))
  427.     {
  428.         jcross = rnd(1 ,(lchrom - 1));/* Cross between 1 and l-1 */
  429.         ncross++;
  430.         for(k = 1; k <= chromsize; k++)
  431.         {
  432.             if(jcross >= (k*32))
  433.             {
  434.                 child1[k-1] = parent1[k-1];
  435.                 child2[k-1] = parent2[k-1];
  436.             }
  437.             else if((jcross < (k*32)) && (jcross > ((k-1)*32)))
  438.             {
  439.                 mask = 1;
  440.                 for(j = 1; j <= (jcross-1-((k-1)*32)); j++)
  441.                 {
  442.                     temp = 1;
  443.                     mask = mask<<1;
  444.                     mask = mask|temp;
  445.                 }
  446.                 child1[k-1] = (parent1[k-1]&mask)|(parent2[k-1]&(~mask));
  447.                 child2[k-1] = (parent1[k-1]&(~mask))|(parent2[k-1]&mask);
  448.             }
  449.             else
  450.             {
  451.                 child1[k-1] = parent2[k-1];
  452.                 child2[k-1] = parent1[k-1];
  453.             }
  454.         }
  455.     }
  456.     else
  457.     {
  458.         for(k = 0; k < chromsize; k++)
  459.         {
  460.             child1[k] = parent1[k];
  461.             child2[k] = parent2[k];
  462.         }
  463.         jcross = 0;
  464.     }
  465.     return(jcross);
  466. }
  467. void advance_random()  /* 产生55个随机数 */
  468. {
  469.     int j1;
  470.     double new_random;
  471.     for(j1 = 0; j1 < 24; j1++)
  472.     {
  473.         new_random = oldrand[j1] - oldrand[j1+31];
  474.         if(new_random < 0.0) new_random = new_random + 1.0;
  475.         oldrand[j1] = new_random;
  476.     }
  477.     for(j1 = 24; j1 < 55; j1++)
  478.     {
  479.         new_random = oldrand [j1] - oldrand [j1-24];
  480.         if(new_random < 0.0) new_random = new_random + 1.0;
  481.         oldrand[j1] = new_random;
  482.     }
  483. }
  484. int flip(float prob) /* 以一定概率产生0或1 */
  485. {
  486.     float randomperc();
  487.     if(randomperc() <= prob)
  488.         return(1);
  489.     else
  490.         return(0);
  491. }
  492. void randomize()  /* 设定随机数种子并初始化随机数发生器 */
  493. {
  494.     float randomseed;
  495.     int j1;
  496.     for(j1=0; j1<=54; j1++)
  497.       oldrand[j1] = 0.0;
  498.     jrand=0;
  499.       do
  500.         {
  501.             
  502.              printf("随机数种子[0-1]:");
  503.               scanf("%f", &randomseed);
  504.          }
  505.         while((randomseed < 0.0) || (randomseed > 1.0));
  506.     warmup_random(randomseed);
  507. }
  508. double randomnormaldeviate() /* 产生随机标准差 */
  509. {
  510.     //double sqrt(), log(), sin(), cos();
  511.     float randomperc();
  512.     double t, rndx1;
  513.     if(rndcalcflag)
  514.     {   rndx1 = sqrt(- 2.0*log((double) randomperc()));
  515.         t = 6.2831853072 * (double) randomperc();
  516.         rndx2 = rndx1 * sin(t);
  517.         rndcalcflag = 0;
  518.         return(rndx1 * cos(t));
  519.     }
  520.     else
  521.     {
  522.         rndcalcflag = 1;
  523.         return(rndx2);
  524.     }
  525. }
  526. float randomperc() /*与库函数random()作用相同, 产生[0,1]之间一个随机数 */
  527. {
  528.     jrand++;
  529.     if(jrand >= 55)
  530.     {
  531.         jrand = 1;
  532.         advance_random();
  533.     }
  534.     return((float) oldrand[jrand]);
  535. }
  536. int rnd(int low, int high) /*在整数low和high之间产生一个随机整数*/
  537. {
  538.     int i;
  539.     float randomperc();
  540.     if(low >= high)
  541.         i = low;
  542.     else
  543.     {
  544.         i =(int)((randomperc() * (high - low + 1)) + low);
  545.         if(i > high) i = high;
  546.     }
  547.     return(i);
  548. }
  549. void warmup_random(float random_seed)  /* 初始化随机数发生器*/
  550. {
  551.     int j1, ii;
  552.     double new_random, prev_random;
  553.     oldrand[54] = random_seed;
  554.     new_random = 0.000000001;
  555.     prev_random = random_seed;
  556.     for(j1 = 1 ; j1 <= 54; j1++)
  557.     {
  558.         ii = (21*j1)%54;
  559.         oldrand[ii] = new_random;
  560.         new_random = prev_random-new_random;
  561.         if(new_random<0.0) new_random = new_random + 1.0;
  562.         prev_random = oldrand[ii];
  563.     }
  564.     advance_random();
  565.     advance_random();
  566.     advance_random();
  567.     jrand = 0;
  568. }
  569. void main(int argc,char *argv[])    /*  主程序  */
  570. {
  571.     struct individual *temp;
  572.    // FILE   *fopen();
  573.     void   title();
  574.     char   *malloc();
  575.        /* if((outfp = fopen(argv[1],"w")) == NULL)
  576.         {
  577.            printf("Cannot open output file %sn",argv[1]);
  578.             exit(-1);
  579.         }*/
  580.      
  581.      title();
  582.      printf("输入遗传算法执行次数(1-5):");
  583.      scanf("%d",&maxruns);
  584.      for(run=1; run<=maxruns; run++)
  585.     {
  586.         initialize();
  587.         for(gen=0; gen<maxgen; gen++)
  588.         {
  589.          printf("n第 %d / %d 次运行: 当前代为 %d, 共 %d 代n", run,maxruns,gen,maxgen);
  590.             /* 产生新一代 */
  591.             generation();
  592.             /* 计算新一代种群的适应度统计数据 */
  593.             statistics(newpop);
  594.             /* 输出新一代统计数据 */
  595.             report();
  596.             temp = oldpop;
  597.             oldpop = newpop;
  598.             newpop = temp;
  599.         }
  600.         freeall();
  601.     }
  602. }