开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 人工智能/神经网络 > 查看源码
sga.c
资源名称：遗传算法_VC源码.rar　[点击查看]
上传用户：helpmateqq
上传日期：2013-03-23
资源大小：86k
文件大小：25k
源码类别：

人工智能/神经网络

开发平台：

Visual C++

sga.c：源码内容
  1. /********************************************************************/
  2. /*         基于基本遗传算法的分层遗传改进算法函数最优化   SHGA.C    */
  3. /*     A Function Optimizer using Simple Genetic Algorithm          */
  4. /* developed from the Pascal SGA code presented by David E.Goldberg */
  5. /*              华南理工大学电子与信息学院   苏勇          2004年4月*/
  6. /********************************************************************/
  7. #include <stdio.h>
  8. #include <math.h>
  9. /* 全局变量 */
  10. struct individual                       /* 个体*/
  11. {
  12.     unsigned *chrom;                    /* 染色体 */
  13.     double   fitness;                   /* 个体适应度*/
  14.     double   varible;                   /* 个体对应的变量值*/   
  15.     int      xsite;                     /* 低层交叉位置 */
  16. int  xsiteA; /* 高层交叉位置 */
  17.     int      parent[2];                 /* 父个体  */
  18. int  parentA[2]; /* 高层父个体(父代子群) */
  19.     int      *utility;                  /* 特定数据指针变量 */
  20. };
  21. struct bestever                         /* 最佳个体*/
  22. {
  23.     unsigned *chrom;                    /* 低层遗传运算所得最佳个体染色体*/
  24. unsigned *chromA; /* 全局最佳个体染色体 */
  25.     double   fitness;                   /* 最佳个体适应度 */
  26.     double   varible;                   /* 最佳个体对应的变量值 */
  27.     int      generation;                /* 最佳个体生成代 */
  28. int  subpopulation; /* 最佳个体所在子种群 */
  29. };
  30.  struct individual **oldpop;            /* 当前代种群 */
  31.  struct individual **newpop;            /* 新一代种群 */
  32.  struct bestever bestfit;               /* 最佳个体 */
  33.  double sumfitness;                     /* 种群中个体适应度累计 */
  34.  double sumA; /* 所有子群平均适应度累计 */
  35.  double max;                            /* 种群中个体最大适应度 */
  36.  double maxA; /* 全局最佳适应度值 */
  37.  double avg;                            /* 种群中个体平均适应度 */
  38.  double min;                            /* 种群中个体最小适应度 */
  39.  double minA; /* 全局最小适应度值 */
  40.  double *A; /* 子群平均适应度值数组 */
  41.  float  pcross;                         /* 低层交叉概率 */
  42.  float  pcrossA; /* 高层交叉概率 */
  43.  float  pmutation;                      /* 低层变异概率 */
  44.  float  pmutationA; /* 高层变异概率 */
  45.  int    popsize;                        /* 种群大小  */
  46.  int    lchrom;                         /* 染色体长度*/
  47.  int    chromsize;                      /* 存储一染色体所需字节数 */
  48.  int    gen;                            /* 当前世代数 */
  49.  int    maxgen;                         /* 最大世代数   */
  50.  int    run;                            /* 低层遗传当前运行次数 */
  51.  int runA; /* 高层遗传当前运行次数 */
  52.  int    maxruns;                        /* 总运行次数   */
  53.  int    printstrings;                   /* 输出染色体编码的判断，0 -- 不输出, 1 -- 输出 */
  54.  int    nmutation;                      /* 低层当前代变异发生次数 */
  55.  int nmutationA; /* 高层当前代变异发生次数 */
  56.  int    ncross;                         /* 低层当前代交叉发生次数 */
  57.  int ncrossA; /* 高层当前代交叉发生次数 */
  58.  int subpopnum; /* 子种群个数 */
  59.  int subpop; /* 当前子种群 */
  60.  float randomseed; /* 随机数种子 */
  61.  int shu; /* 当前子群 */
  62.  double varibleA; /* 全局最佳染色体对应变量值 */
  63.  int genA; /* 全局最佳染色体所在代数 */
  64. /* 随机数发生器使用的静态变量 */
  65. static double oldrand[55];
  66. static int jrand;
  67. static double rndx2;
  68. static int rndcalcflag;
  69. /* 输出文件指针 */
  70. FILE *outfp ;
  71. /* 函数定义 */
  72. void advance_random();
  73. int flip(float);rnd(int, int);
  74. void randomize();
  75. double randomnormaldeviate();
  76. float randomperc(),rndreal(float,float);
  77. void warmup_random(float);
  78. void initialize(),initdata(),initpop();
  79. void initreport(),generation(),initmalloc();
  80. void freeall(),nomemory(char *),report();
  81. void reportA();
  82. void writepop(),writechrom(unsigned *);
  83. void preselect();
  84. void statistics(struct individual *);
  85. void title(),repchar (FILE *,char *,int);
  86. void skip(FILE *,int);
  87. int select();
  88. void objfunc(struct individual *);
  89. /* 低层交叉变异函数 */
  90. int crossover (unsigned *, unsigned *, unsigned *, unsigned *);
  91. void mutation(unsigned *);
  92. /* 高层交叉变异函数 */
  93. void CMTransA();
  94. int selectA();
  95. void preselectA();
  97. void initialize()      /* 遗传算法初始化 */
  98. {
  99.     /* 键盘输入遗传算法参数 */
  100.     initdata();
  101.     /* 确定染色体的字节长度 */
  102.     chromsize = (lchrom/(8*sizeof(unsigned)));
  103.     if(lchrom%(8*sizeof(unsigned))) chromsize++;
  104.     /*分配给全局数据结构空间 */
  105.     initmalloc();
  106.     initreport();
  107. }
  109. void initdata()           /* 遗传算法参数输入 */
  110. {
  111.    char  answer[2];
  112.    popsize=30;
  113.    if((popsize%2) != 0)
  114.    {
  115.  fprintf(outfp, "种群大小已设置为偶数n");
  116.  popsize++;
  117.    }
  118.    lchrom=22; /* 染色体长度定义为22 */
  119.    printstrings=1;
  120.    maxgen=100; /* 低层运算100代 */
  121.    pcross=0.8; /* 低层交叉概率0.8 */
  122.    pcrossA=0.2; /* 高层交叉概率0.6 */
  123.    pmutation=0.05; /* 低层变异概率0.05 */
  124.    pmutationA=0.05; /* 高层变异概率0.05 */
  125.    genA=maxgen;
  126. }
  128. void initpop()           /* 随机初始化种群 */
  129. {
  130.     int j, j1, k, stop;
  131.     unsigned mask = 1;
  132.     for(j = 0; j < popsize; j++)
  133.     {
  135.         for(k = 0; k < chromsize; k++)
  136.         {
  137.             oldpop[subpop][j].chrom[k] = 0;
  138.             if(k == (chromsize-1))
  139.                 stop = lchrom - (k*(8*sizeof(unsigned)));
  140.             else
  141.                 stop =8*sizeof(unsigned);
  142.             for(j1 = 1; j1 <= stop; j1++)
  143.             {
  144.                oldpop[subpop][j].chrom[k] = oldpop[subpop][j].chrom[k]<<1;
  145.                if(flip(randomseed))
  146.                   oldpop[subpop][j].chrom[k] = oldpop[subpop][j].chrom[k]|mask;
  147.             }
  148.         }
  149.         oldpop[subpop][j].parent[0] = 0;     /* 初始父个体信息 */
  150.         oldpop[subpop][j].parent[1] = 0;
  151. oldpop[subpop][0].parentA[0]= 0;
  152. oldpop[subpop][0].parentA[1]= 0;
  153.         oldpop[subpop][j].xsite = 0;
  154. oldpop[subpop][0].xsiteA= 0;
  155.         objfunc(&(oldpop[subpop][j]));       /* 计算初始适应度*/
  156.     }
  157. if(subpop==0)
  158. {
  159. maxA = oldpop[0][0].fitness;
  160. minA = oldpop[0][0].fitness;
  161. }
  162. }
  164. void initreport()               /* 初始参数输出 */
  165. {
  166.     void   skip();
  167.     skip(outfp,1);
  168.     fprintf(outfp,"             基本遗传算法参数n");
  169.     fprintf(outfp," -------------------------------------------------n");
  170. fprintf(outfp,"    子种群数(subpopnum)   =   %dn",subpopnum);
  171.     fprintf(outfp,"    种群大小(popsize)     =   %dn",popsize);
  172.     fprintf(outfp,"    染色体长度(lchrom)    =   %dn",lchrom);
  173.     fprintf(outfp,"    最大进化代数(maxgen)  =   %dn",maxgen);
  174.     fprintf(outfp,"    交叉概率(pcross)      =   %fn",pcross);
  175.     fprintf(outfp,"    变异概率(pmutation)   =   %fn",pmutation);
  176.     fprintf(outfp," -------------------------------------------------n");
  177.     skip(outfp,1);
  178.     fflush(outfp);
  179. }
  181. void generation()           /* 低层交叉变异 */
  182. {
  183.   int mate1, mate2, jcross, j = 0;
  184.   /*  每代运算前进行预选 */
  185.   preselect();
  186.   /* 选择, 交叉, 变异 */
  187.   do
  188.     {
  189.       /* 挑选交叉配对 */
  190.       mate1 = select();
  191.       mate2 = select();
  192.       /* 交叉和变异 */
  193.       jcross = crossover(oldpop[subpop][mate1].chrom, oldpop[subpop][mate2].chrom, newpop[subpop][j].chrom, newpop[subpop][j+1].chrom);
  194.       mutation(newpop[subpop][j].chrom);
  195.       mutation(newpop[subpop][j+1].chrom);
  196.       /* 解码, 计算适应度 */
  197.       objfunc(&(newpop[subpop][j]));
  198.       /*记录亲子关系和交叉位置 */
  199.       newpop[subpop][j].parent[0] = mate1+1;
  200.       newpop[subpop][j].xsite = jcross;
  201.       newpop[subpop][j].parent[1] = mate2+1;
  202.       objfunc(&(newpop[subpop][j+1]));
  203.       newpop[subpop][j+1].parent[0] = mate1+1;
  204.       newpop[subpop][j+1].xsite = jcross;
  205.       newpop[subpop][j+1].parent[1] = mate2+1;
  206.       j = j + 2;
  207.     }
  208.   while(j < (popsize-1));
  210. }
  212. void CMTransA() /* 高层交叉变异 */
  213. {
  214. int mateA1, mateA2, jcrossA = 0, k, h, m, j1, j=0;
  215. unsigned mask = 1;
  216. int stop;
  217. preselectA();
  218. do
  219. {
  220. /*////////////  高层交叉 ///////////////*/
  221. mateA1 = selectA();
  222. mateA2 = selectA();
  224. if(flip(pcrossA))
  225. {
  226. jcrossA = (int)rnd(1 ,(popsize - 1));
  227. ncrossA++;
  228. for(m = jcrossA; m < popsize; m++)
  229. {
  230. for(k=0;k< chromsize; k++)
  231. {
  232. oldpop[mateA1][m].chrom[k] = newpop[j+1][m].chrom[k];
  233. oldpop[mateA2][m].chrom[k] = newpop[j][m].chrom[k];
  234. }
  235. }
  236. for(m = 0; m < jcrossA; m++)
  237. {
  238. for(k=0;k< chromsize; k++)
  239. {
  240. oldpop[mateA1][m].chrom[k] = newpop[j][m].chrom[k];
  241. oldpop[mateA2][m].chrom[k] = newpop[j+1][m].chrom[k];
  242. }
  243. }
  244. }
  245. else
  246. {
  247. for(m = 0; m< popsize; m++)
  248. {
  249. for(k=0;k<chromsize;k++)
  250. {
  251. oldpop[mateA1][m].chrom[k] = newpop[j][m].chrom[k];
  252. oldpop[mateA2][m].chrom[k] = newpop[j+1][m].chrom[k];
  253. }
  254. }
  255. jcrossA=0;
  256. }
  257. /*////////////  高层变异 ////////////////*/
  258. if(flip(pmutationA))
  259.         {
  260. nmutationA++;
  261. for(h = 0; h < chromsize; h++)
  262. {
  263. newpop[j][m].chrom[h] = 0;
  264. if(h == (chromsize-1))
  265. stop = lchrom - (h*(8*sizeof(unsigned)));
  266. else
  267. stop =8*sizeof(unsigned);
  268. for(j1 = 1; j1 <= stop; j1++)
  269. {
  270. newpop[j][m].chrom[h] = newpop[j][m].chrom[h]<<1;
  271. if(flip(0.5))
  272. newpop[j][m].chrom[h] = newpop[j][m].chrom[h]|mask;
  273. }
  274. }
  275. }
  276. if(flip(pmutation))
  277.         {
  278. nmutationA++;
  279. for(h = 0; h < chromsize; h++)
  280. {
  281. newpop[j+1][m].chrom[h] = 0;
  282. if(h == (chromsize-1))
  283. stop = lchrom - (h*(8*sizeof(unsigned)));
  284. else
  285. stop =8*sizeof(unsigned);
  286. for(j1 = 1; j1 <= stop; j1++)
  287. {
  288. newpop[j+1][m].chrom[h] = newpop[j+1][m].chrom[h]<<1;
  289. if(flip(0.5))
  290. newpop[j+1][m].chrom[h] = newpop[j+1][m].chrom[h]|mask;
  291. }
  292. }
  293. }
  295. /* 解码, 计算适应度 */
  296. for(k = 0; k < popsize; k++)
  297. objfunc(&(newpop[j][k]));
  298. for(k = 0; k < popsize; k++)
  299. objfunc(&(newpop[j+1][k]));
  300. newpop[j+1][0].parentA[0] = mateA1+1;
  301. newpop[j+1][0].xsiteA = jcrossA;
  302. newpop[j+1][0].parentA[1] = mateA2+1;
  303. j = j + 2;
  304. }
  305. while(j<(subpopnum-1));
  306. }
  308. void initmalloc()              /*为全局数据变量分配空间 */
  309. {
  310.   unsigned nbytes;
  311.   char  *malloc();
  312.   int i,j;
  313.   /* 分配给当前代和新一代种群内存空间 */
  314.   if((A = (double *) malloc(subpopnum*sizeof(double))) == NULL)
  315.     nomemory("A");
  316.   nbytes = popsize*sizeof(struct individual);
  317.   if((oldpop = (struct individual **) malloc(subpopnum*4)) == NULL)
  318.     nomemory("oldpop");
  319.   for(j=0; j<subpopnum;j++)
  320.   {
  321. if((oldpop[j] = (struct individual *) malloc(nbytes)) == NULL)
  322. nomemory("oldpop[j]");
  323.   }
  324.   if((newpop = (struct individual **) malloc(subpopnum*4)) == NULL)
  325.     nomemory("newpop");
  326.   for(j=0; j<subpopnum;j++)
  327.   {
  328. if((newpop[j] = (struct individual *) malloc(nbytes)) == NULL)
  329. nomemory("newpop[j]");
  330.   }
  331.   /* 分配给染色体内存空间 */
  332.   nbytes = chromsize*sizeof(unsigned);
  333.   for(j = 0; j < popsize; j++)
  334.     {
  335.   for(i=0;i<subpopnum;i++)
  336.   {
  337. if((oldpop[i][j].chrom = (unsigned *) malloc(nbytes)) == NULL)
  338. nomemory("oldpop[i] chromosomes");
  339. if((newpop[i][j].chrom = (unsigned *) malloc(nbytes)) == NULL)
  340. nomemory("newpop[i] chromosomes");
  341.   }
  342.     }
  343.   if((bestfit.chrom = (unsigned *) malloc(nbytes)) == NULL)
  344.     nomemory("bestfit chromosome");
  345.   if((bestfit.chromA = (unsigned *) malloc(nbytes)) == NULL)
  346.     nomemory("bestfit chromosomeA");
  348. }
  350. void freeall()               /* 释放内存空间 */
  351. {
  352.   int i,j;
  353.    for(i = 0; i < popsize; i++)
  354.     {
  355.    for(j=0;j<subpopnum;j++)
  356.    {
  357. free(oldpop[j][i].chrom);
  358. free(newpop[j][i].chrom);
  359.    }
  360.     }
  361.   free(A);
  362.   for(j=0;j<subpopnum;j++)
  363.   free(oldpop[j]);
  364.   free(oldpop);
  365.   for(j=0;j<subpopnum;j++)
  366.   free(newpop[j]);
  367.   free(newpop);
  368.   free(bestfit.chrom);
  369.   free(bestfit.chromA);
  370. }
  372. void nomemory(string)        /* 内存不足，退出*/
  373.   char *string;
  374. {
  375.   fprintf(outfp,"malloc: out of memory making %s!!n",string);
  376.   exit(-1);
  377. }
  379. void reportA()
  380. {
  381. void   skip();
  382. int i,j,s;
  383. fprintf(outfp,"第1次高层交叉变异统计报告n");
  384. repchar(outfp,"-",80);
  385. skip(outfp,1); 
  386. for(s=0;s<subpopnum-1;s+=2)
  387. {
  388. fprintf(outfp, "   第%d子种群   ", s+1);
  389. repchar(outfp, " ",lchrom-10);
  390. fprintf(outfp, "  适应度值   ");
  391. repchar(outfp, " ",2);
  392. fprintf(outfp, "   第%d子种群   ", s+2);
  393. repchar(outfp, " ",lchrom-6);
  394. fprintf(outfp, "  适应度值   ");
  395. fprintf(outfp, "  父代子群:");
  396. fprintf(outfp, "(%2d,%2d)", newpop[s+1][0].parentA[0],newpop[s+1][0].parentA[1]);
  397. skip(outfp,1); 
  398. for(i=0;i<popsize-1;i++)
  399. {
  400. fprintf(outfp, "%2d) ",i+1);
  401. writechrom((&newpop[s][i])->chrom);
  402. repchar(outfp, " ",2);
  403. fprintf(outfp, "  %f  " ,newpop[s][i].fitness); 
  404. repchar(outfp, " ",5);
  405. fprintf(outfp, "%2d) ",i+1);
  406. writechrom((&newpop[s][i+1])->chrom);
  407. repchar(outfp, " ",2);
  408. fprintf(outfp, "  %f  " ,newpop[s][i+1].fitness); 
  409. skip(outfp,1);
  410. }
  411. repchar(outfp,"-",80);
  412. skip(outfp,1);
  413. fprintf(outfp, "高层交叉次数:  %d  ,  高层变异次数:  %d ",ncrossA,nmutationA);
  414. skip(outfp,1);
  415. }
  416. fprintf(outfp," 迄今发现最佳个体   =>  所在分层: %d 所在子群: %d  所在代数: %d ", runA,bestfit.subpopulation , genA);
  417. fprintf(outfp," 适应度：%f  染色体: ", maxA);
  418. writechrom((&bestfit)->chromA);
  419. fprintf(outfp," 对应的变量值: %f", varibleA);
  420. skip(outfp,1);
  421. fprintf(outfp," 迄今发现最小适应度 => %f ",minA);
  422. skip(outfp,1);
  423. repchar(outfp,"-",80);
  424. skip(outfp,1);  
  425. }
  427. void report()                /* 输出种群统计结果 */
  428. {
  429.     void  repchar(), skip();
  430.     void  writepop(), writestats();
  431.     repchar(outfp,"-",80);
  432.     skip(outfp,1); 
  433.     if(printstrings == 1)
  434.     {
  435.         repchar(outfp," ",((80-17)/2));
  436.         fprintf(outfp,"第%d子种群模拟计算统计报告  n",(subpop+1));
  437.         fprintf(outfp, "世代数 %3d", gen);
  438.         repchar(outfp," ",(80-28));
  439.         fprintf(outfp, "世代数 %3dn", (gen+1));
  440.         fprintf(outfp,"个体  染色体编码");
  441.         repchar(outfp," ",lchrom-5);
  442.         fprintf(outfp,"适应度    父个体 交叉位置  ");
  443.         fprintf(outfp,"染色体编码 ");
  444.         repchar(outfp," ",lchrom-5);
  445.         fprintf(outfp,"适应度n");
  446.         repchar(outfp,"-",80);
  447.         skip(outfp,1);
  448.         writepop(outfp);
  449.         repchar(outfp,"-",80);
  450.         skip(outfp,1);
  451.      }
  452.     fprintf(outfp," 第 %d 代统计: n",gen);
  453.     fprintf(outfp," 总交叉操作次数 = %d, 总变异操作数 = %dn",ncross,nmutation);
  454.     fprintf(outfp," 子群中最小适应度：%f 最大适应度：%f  平均适应度 %fn", min,max,A[subpop]);
  455.     fprintf(outfp," 子群中发现最佳个体 =>  所在代数: %d  ", bestfit.generation);
  456.     fprintf(outfp," 适应度：%f  染色体: ", bestfit.fitness);
  457.     writechrom((&bestfit)->chrom);
  458.     fprintf(outfp," 对应的变量值: %f", bestfit.varible);
  459. skip(outfp,1);
  460. fprintf(outfp," 迄今发现最佳个体   =>  所在分层: %d 所在子群: %d  所在代数: %d ", runA,bestfit.subpopulation,genA);
  461. fprintf(outfp," 适应度：%f  染色体: ", maxA);
  462.     writechrom((&bestfit)->chromA);
  463. fprintf(outfp," 对应的变量值: %f", varibleA);
  464. skip(outfp,1);
  465. fprintf(outfp," 迄今发现最小适应度 => %f ",minA);
  466.     skip(outfp,1);
  467.     repchar(outfp,"-",80);
  468.     skip(outfp,1);  
  469. }
  471. void writepop()
  472. {
  473.     struct individual *pind;
  474.     int j;
  475.     for(j=0; j<popsize; j++)
  476.     {
  477.         fprintf(outfp,"%3d)  ",j+1);
  478.         /* 当前代个体 */
  479.         pind = &(oldpop[subpop][j]);
  480.         writechrom(pind->chrom);
  481.         fprintf(outfp,"  %8f | ", pind->fitness);
  482.         /* 新一代个体 */
  483.         pind = &(newpop[subpop][j]);
  484.         fprintf(outfp,"(%2d,%2d)   %2d   ",
  485.         pind->parent[0], pind->parent[1], pind->xsite);
  486.         writechrom(pind->chrom);
  487.         fprintf(outfp,"  %8fn", pind->fitness);
  488.     }
  489. }
  491. void writechrom(chrom)           /* 输出染色体编码 */
  492. unsigned *chrom;
  493. {
  494.     int j, k, stop;
  495.     unsigned mask = 1, tmp;
  496.     for(k = 0; k < chromsize; k++)
  497.     {
  498.         tmp = chrom[k];
  499.         if(k == (chromsize-1))
  500.             stop = lchrom - (k*(8*sizeof(unsigned)));
  501.         else
  502.             stop =8*sizeof(unsigned);
  503.         for(j = 0; j < stop; j++)
  504.         {
  505.             if(tmp&mask)
  506.                 fprintf(outfp,"1");
  507.             else
  508.                 fprintf(outfp,"0");
  509.             tmp = tmp>>1;
  510.         }
  511.     }
  512. }
  514. void preselect()
  515. {
  516.     int j;
  517.     sumfitness = 0;
  518.     for(j = 0; j < popsize; j++) sumfitness += oldpop[subpop][j].fitness;
  519. }
  521. void preselectA()
  522. {
  523. int j;
  524. sumA = 0.0;
  525. for(j = 0; j< subpopnum; j++) sumA += A[j];
  526. }
  528. int select()                    /* 轮盘赌选择*/
  529. {
  530.     extern float randomperc();
  531.     float sum, pick;
  532.     int i;
  533.     pick = randomperc();
  534.     sum = 0;
  535.     if(sumfitness != 0)
  536.     {
  537.         for(i = 0; (sum < pick) && (i < popsize); i++)
  538.             sum += oldpop[subpop][i].fitness/sumfitness;
  539.     }
  540.     else
  541.         i = rnd(1,popsize);
  542.     return(i-1);
  543. }
  545. int selectA()
  546. {
  547. extern float randomperc();
  548.     double sum;
  549. float pick;
  550.     int i;
  551.     pick = randomperc();
  552.     sum = 0.0;
  553.     if(sumA != 0)
  554.     {
  555.         for(i = 0; (sum < pick) && (i < subpopnum); i++)
  556.             sum += A[i]/sumA;
  557.     }
  558.     else
  559.         i = rnd(1,subpopnum);
  560.     return(i-1);
  561. }
  563. void statistics(pop)  /* 计算种群统计数据 */
  564. struct individual *pop;
  565. {
  566.     int i, j;
  567.     sumfitness = 0.0;
  568.     min = pop[0].fitness;
  569.     max = pop[0].fitness;
  570.     /* 计算最大、最小和累计适应度 */
  571.     for(j = 0; j < popsize; j++)
  572.     {
  573.         sumfitness = sumfitness + pop[j].fitness;            
  574.         if(pop[j].fitness > max) max = pop[j].fitness;        
  575.         if(pop[j].fitness < min) min = pop[j].fitness;
  576.         /* new global best-fit individual */
  577.         if(pop[j].fitness > bestfit.fitness)
  578.   {
  579.    for(i = 0; i < chromsize; i++)
  580.     bestfit.chrom[i]      = pop[j].chrom[i];
  581.             bestfit.fitness    = pop[j].fitness;
  582.             bestfit.varible   = pop[j].varible;  
  583.             bestfit.generation = gen;
  584.   }
  585.       }
  586.     /* 计算平均适应度 */
  587. if(bestfit.fitness>=maxA)
  588. {
  589. maxA=bestfit.fitness;
  590. for(i = 0; i < chromsize; i++)
  591. bestfit.chromA[i] = bestfit.chrom[i];
  592. varibleA = bestfit.varible;
  593. bestfit.subpopulation = subpop+1;
  594. runA=run;
  595. genA=bestfit.generation;
  596. }
  597. if(min<=minA) minA = min;
  598.     avg = sumfitness/popsize;
  599. if(subpop!=(subpopnum-1))
  600. A[subpop]=avg;
  601. }
  603. void title()
  604. {
  605.   printf("SGA Optimizer Jean.Timexn");
  606. }
  608. void repchar (outfp,ch,repcount)
  609. FILE *outfp;
  610. char *ch;
  611. int repcount;
  612. {
  613.     int j;
  614.     for (j = 1; j <= repcount; j++) fprintf(outfp,"%s", ch);
  615. }
  617. void skip(outfp,skipcount)
  618. FILE *outfp;
  619. int skipcount;
  620. {
  621.     int j;
  622.     for (j = 1; j <= skipcount; j++) fprintf(outfp,"n");
  623. }
  625. void objfunc(critter)            /* 计算适应度函数值 */
  626. struct individual *critter;
  627. {
  628.     unsigned mask=1;
  629.     unsigned bitpos;
  630.     unsigned tp;
  631.     double pow(), bitpow ;
  632.     int j, k, stop;
  633.     critter->varible = 0.0;
  634.     for(k = 0; k < chromsize; k++)
  635.     {
  636.         if(k == (chromsize-1))
  637.             stop = lchrom-(k*(8*sizeof(unsigned)));
  638.         else
  639.             stop =8*sizeof(unsigned);
  640.         tp = critter->chrom[k];
  641.         for(j = 0; j < stop; j++)
  642.         {
  643.             bitpos = j + (8*sizeof(unsigned))*k;
  644.             if((tp&mask) == 1)
  645.             {
  646.                 bitpow = pow(2.0,(double) bitpos);
  647.                 critter->varible = critter->varible + bitpow;
  648.             }
  649.             tp = tp>>1;
  650.         }
  651.     }
  652.     critter->varible =-1+critter->varible*3/(pow(2.0,(double)lchrom)-1);
  653.     critter->fitness =critter->varible*sin(critter->varible*10*atan(1)*4)+2.0;
  654. }
  656. void  mutation(unsigned *child)   /*变异操作*/
  657. {
  658.     int j, k, stop;
  659.     unsigned mask, temp = 1;
  660.     for(k = 0; k < chromsize; k++)
  661.     {
  662.         mask = 0;
  663.         if(k == (chromsize-1))
  664.             stop = lchrom - (k*(8*sizeof(unsigned)));
  665.         else
  666.             stop = 8*sizeof(unsigned);
  667.         for(j = 0; j < stop; j++)
  668.         {
  669.             if(flip(pmutation))
  670.             {
  671.                 mask = mask|(temp<<j);
  672.                 nmutation++;
  673.             }
  674.         }
  675.         child[k] = child[k]^mask;
  676.     }
  677. }
  680. int crossover (unsigned *parent1, unsigned *parent2, unsigned *child1, unsigned *child2)
  681. /* 由两个父个体交叉产生两个子个体 */
  682. {
  683.     int j, jcross, k;
  684.     unsigned mask, temp;
  685.     if(flip(pcross))
  686.     {
  687.         jcross = rnd(1 ,(lchrom - 1));/* Cross between 1 and l-1 */
  688.         ncross++;
  689.         for(k = 1; k <= chromsize; k++)
  690.         {
  691.             if(jcross >= (k*(8*sizeof(unsigned))))
  692.             {
  693.                 child1[k-1] = parent1[k-1];
  694.                 child2[k-1] = parent2[k-1];
  695.             }
  696.             else if((jcross < (k*(8*sizeof(unsigned)))) && (jcross > ((k-1)*(8*sizeof(unsigned)))))
  697.             {
  698.                 mask = 1;
  699.                 for(j = 1; j <= (jcross-1-((k-1)*(8*sizeof(unsigned)))); j++)
  700.                 {
  701.                     temp = 1;
  702.                     mask = mask<<1;
  703.                     mask = mask|temp;
  704.                 }
  705.                 child1[k-1] = (parent1[k-1]&mask)|(parent2[k-1]&(~mask));
  706.                 child2[k-1] = (parent1[k-1]&(~mask))|(parent2[k-1]&mask);
  707.             }
  708.             else
  709.             {
  710.                 child1[k-1] = parent2[k-1];
  711.                 child2[k-1] = parent1[k-1];
  712.             }
  713.         }
  714.     }
  715.     else
  716.     {
  717.         for(k = 0; k < chromsize; k++)
  718.         {
  719.             child1[k] = parent1[k];
  720.             child2[k] = parent2[k];
  721.         }
  722.         jcross = 0;
  723.     }
  724.     return(jcross);
  725. }
  727. void advance_random()          /* 产生55个随机数 */
  728. {
  729.     int j1;
  730.     double new_random;
  731.     for(j1 = 0; j1 < 24; j1++)
  732.     {
  733.         new_random = oldrand[j1] - oldrand[j1+31];
  734.         if(new_random < 0.0) new_random = new_random + 1.0;
  735.         oldrand[j1] = new_random;
  736.     }
  737.     for(j1 = 24; j1 < 55; j1++)
  738.     {
  739.         new_random = oldrand [j1] - oldrand [j1-24];
  740.         if(new_random < 0.0) new_random = new_random + 1.0;
  741.         oldrand[j1] = new_random;
  742.     }
  743. }
  745. int flip(float prob)          /* 以一定概率产生0或1 */
  746. {
  747.     float randomperc();
  748.     if(randomperc() <= prob)
  749.         return(1);
  750.     else
  751.         return(0);
  752. }
  754. void randomize()            /* 设定随机数种子并初始化随机数发生器 */
  755. {
  756.     int j1;
  757.     for(j1=0; j1<=54; j1++)
  758.       oldrand[j1] = 0.0;
  759.     jrand=0;
  760.     warmup_random(randomseed);
  761. }
  763. double randomnormaldeviate()         /* 产生随机标准差 */
  764. {
  765.     double sqrt(), log(), sin(), cos();
  766.     float randomperc();
  767.     double t, rndx1;
  768.     if(rndcalcflag)
  769.     {   rndx1 = sqrt(- 2.0*log((double) randomperc()));
  770.         t = 6.2831853072 * (double) randomperc();
  771.         rndx2 = rndx1 * sin(t);
  772.         rndcalcflag = 0;
  773.         return(rndx1 * cos(t));
  774.     }
  775.     else
  776.     {
  777.         rndcalcflag = 1;
  778.         return(rndx2);
  779.     }
  780. }
  782. float randomperc()            /*与库函数random()作用相同, 产生[0,1]之间一个随机数 */
  783. {
  784.     jrand++;
  785.     if(jrand >= 55)
  786.     {
  787.         jrand = 1;
  788.         advance_random();
  789.     }
  790.     return((float) oldrand[jrand]);
  791. }
  793. int rnd(low, high)           /*在整数low和high之间产生一个随机整数*/
  794. int low,high;
  795. {
  796.     int i;
  797.     float randomperc();
  798.     if(low >= high)
  799.         i = low;
  800.     else
  801.     {
  802.         i = (randomperc() * (high - low + 1)) + low;
  803.         if(i > high) i = high;
  804.     }
  805.     return(i);
  806. }
  809. void warmup_random(float random_seed)       /* 初始化随机数发生器*/
  810. {
  811.     int j1, ii;
  812.     double new_random, prev_random;
  814.     oldrand[54] = random_seed;
  815.     new_random = 0.000000001;
  816.     prev_random = random_seed;
  817.     for(j1 = 1 ; j1 <= 54; j1++)
  818.     {
  819.         ii = (21*j1)%54;
  820.         oldrand[ii] = new_random;
  821.         new_random = prev_random-new_random;
  822.         if(new_random<0.0) new_random = new_random + 1.0;
  823.         prev_random = oldrand[ii];
  824.     }
  825.     advance_random();
  826.     advance_random();
  827.     advance_random();
  828.     jrand = 0;
  829. }
  832. main()           /*  主程序  */
  833. {
  834.     struct individual **temp;
  835.     FILE   *fopen();
  836.     void   title();
  837.     char   *malloc();
  838.         if((outfp = fopen("output4.txt","w")) == NULL)
  839.         {
  840.            fprintf(stderr,"Cannot open output file %sn","output4.txt");
  841.             exit(-1);
  842.         }
  843.      title();
  844.      maxruns=2;
  845.    for(run=1; run<=maxruns; run++)
  846.    {
  847.  
  848.  subpopnum=20;
  849.  if(run==1)
  850.  {
  851. initialize();
  852. bestfit.subpopulation = 0;
  853. varibleA = 0;
  854.  }
  855.  randomseed = 0;
  856.  ncross=0;
  857.  nmutation=0;
  858.  for(subpop=0;subpop<subpopnum;subpop++)
  859.  {
  860.         /* 初始化随机数发生器 */
  861. randomseed += (float)(1)/(float)(subpopnum+run);
  862. randomize();
  863.     /* 初始化全局计数变量和一些数值*/
  864. nmutation = 0;
  865. ncross = 0;
  866. bestfit.fitness = 0.0;
  867. bestfit.generation = 0;
  869.     /* 初始化种群，并统计计算结果 */
  870. if(run==1)
  871. initpop();
  872. statistics(oldpop[subpop]);
  873. for(gen=0; gen<maxgen; gen++)
  874. {
  875. generation();
  876.             /* 计算新一代种群的适应度统计数据 */
  877. statistics(newpop[subpop]);
  878. temp = oldpop;
  879. oldpop = newpop;
  880. newpop = temp;
  881. }
  882. report();
  883. if(subpop==(subpopnum-1))
  884. {
  885. ncrossA=0;
  886. nmutationA=0;
  887. fprintf(outfp,"n第 %d / %d 次分层优化n", run,maxruns);
  888. /* 选择交叉变异 */
  889. CMTransA();
  890. /* 计算新一代种群的适应度统计数据 */
  892. for(shu = 0; shu<subpopnum; shu++)
  893. statistics(newpop[shu]);
  894. reportA();
  896. temp = oldpop;
  897. oldpop = newpop;
  898. newpop = temp;
  899. }
  900.  }
  901.    }
  902.  freeall();
  903.  fclose(outfp);
  904. }