1 /*
  2 用遗传算法求y=x*sin(10*pi*x)+2的最大值  -1=<x<=2
  3 精确到6位小数
  4 pow(2,21)<3*1000000<pow(2,22)
  5 编码的二进制长度为22 
  6 */
  7 #include <stdio.h>
  8 #include <string.h>
  9 #include <stdlib.h>
 10 #include <ctime>
 11 #include <math.h>
 12 
 13 #define N 3000000
 14 #define PI 3.14159265
 15 #define MAX(a,b) ((a)>(b)?(a):(b))
 16 
 17 #define SIZE  50
 18 #define MAXGEN  50
 19 #define P_CORSS 0.75
 20 #define P_MUTATION 0.05
 21 
 22 #define LEN 22
 23 
 24 typedef struct node
 25 {
 26   char x[LEN];
 27   double fitness,fitsum;
 28 }node;
 29 
 30 node cur[SIZE],next[SIZE],max,min;
 31 
 32 double randd()
 33 {
 34   return (double)rand()/RAND_MAX;
 35 }
 36 int randi(int k)
 37 {
 38   return (int)(randd()*k+0.5);
 39 }
 40 
 41 //计算当前种群中各个个体的适应度 
 42 void cal_fitness()
 43 {
 44   int i,j,k;
 45   double d;
 46   for(i=0;i<SIZE;i++)
 47   {
 48     k=0;
 49     for(j=LEN-1;j>=0;j--) k=(k<<1)+cur[i].x[j];
 50     d=(double)k/N*3-1;
 51     cur[i].fitness=d*sin(10*PI*d)+2;
 52     cur[i].fitsum=i>0?(cur[i].fitness+cur[i-1].fitsum):(cur[0].fitness);
 53   }
 54 }
 55 
 56 void init()
 57 {
 58   int tmp;
 59   for(int i=0;i<SIZE;i++)
 60   {
 61     tmp=randi(N);
 62     for(int j=0;j<LEN;j++)
 63     {
 64       cur[i].x[j]=tmp%2;
 65       tmp=tmp>>1;
 66     }
 67   }
 68   cal_fitness();
 69 }
 70 
 71 int sel()
 72 {
 73   double p=randd();
 74   double sum=cur[SIZE-1].fitsum;
 75   for(int i=0;i<SIZE;i++)
 76   {
 77     if(cur[i].fitsum/sum>p) return i;
 78   }
 79 }
 80 
 81 //换代 
 82 void tran()
 83 {
 84   int i,j,pos;
 85   //找当前种群最优个体 
 86   max=cur[0];
 87   for(i=1;i<SIZE-1;i++)
 88   {
 89     if(cur[i].fitness>max.fitness)  max=cur[i];
 90   }
 91   for(int k=0;k<SIZE;k+=2)
 92   {
 93     //选择交叉个体 
 94     i=sel();
 95     j=sel();
 96     
 97     //选择交叉位置 
 98     pos=randi(LEN-1);
 99     
100     //交叉
101     if(randd()<P_CORSS)
102     {
103       memcpy(next[k].x,cur[i].x,pos);
104       memcpy(next[k].x+pos,cur[j].x+pos,LEN-pos);
105 
106       memcpy(next[k+1].x,cur[j].x,pos);
107       memcpy(next[k+1].x+pos,cur[i].x+pos,LEN-pos);
108     }
109     else
110     {
111       memcpy(next[k].x,cur[i].x,LEN);
112       memcpy(next[k+1].x,cur[j].x,LEN);
113     }
114     //变异
115     if(randd()<P_MUTATION)
116     {
117       pos=randi(LEN-1);
118       next[k].x[pos]^=next[k].x[pos];
119 
120       pos=randi(LEN-1);
121       next[k+1].x[pos]^=next[k+1].x[pos];
122     }
123   }
124   //找下一代的最差个体 
125   min=next[0],j=0;
126   for(i=1;i<SIZE-1;i++)
127   {
128     if(next[i].fitness<min.fitness)  min=next[i],j=i;
129   }
130   //用上一代的最优个体替换下一代的最差个体
131   next[j]=max;
132   
133   memcpy(cur,next,sizeof(cur));
134    
135   
136   cal_fitness();
137 }
138 
139 //打印个体适应度和二进制编码 
140 void print(node tmp)
141 {
142   printf("%.6lf",tmp.fitness);
143   for(int i=0;i<LEN;i++)  printf(" %d",tmp.x[i]);
144   printf("\n");
145 }
146 
147 //打印种群
148 void printcur()
149 {
150   for(int i=0;i<SIZE;i++) print(cur[i]);
151 } 
152 
153 
154 void GA()
155 {
156   int cnt=0;
157   double ans;
158   while(cnt++<MAXGEN)
159   {
160     tran();
161     
162 //    printf("%.6lf\n",max.fitness);
163 //    printcur();
164   }
165   ans=cur[0].fitness;
166   for(int i=1;i<SIZE;i++) ans=MAX(ans,cur[i].fitness);
167   printf("%.6lf\n",ans);
168 }
169 
170 int main()
171 {
172   srand((unsigned)time(NULL));
173   
174   init();
175   GA();
176   
177   system("pause");
178   return 0;
179 }