C++遗传算法类文件实例分析

时间:2021-09-18 06:24:44

本文所述为C++实现的遗传算法的类文件实例。一般来说遗传算法可以解决许多问题,希望本文所述的C++遗传算法类文件,可帮助你解决更多问题,并且代码中为了便于读者更好的理解,而加入了丰富的注释内容,是新手学习遗传算法不可多得的参考代码。

具体代码如下所示:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
#include "stdafx.h"
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>//把日期和时间转换为字符串
using namespace std;
//Parametes setting          
#define POPSIZE 200   //population size
#define MAXGENS 1000  //max number of generation
#define NVARS 2     //no of problem variables
#define PXOVER  0.75 //probalility of crossover
#define PMUTATION 0.15 //probalility of mutation
#define TRUE 1
#define FALSE 0
#define LBOUND 0   
#define UBOUND 12  
#define STOP 0.001
int generation;     //current generation no
int cur_best;      //best individual
double diff;     
FILE *galog;      //an output file
struct genotype
{
   double gene[NVARS];   //a string of variables基因变量
   double upper[NVARS];  //individual's variables upper bound 基因变量取值上确界
   double lower[NVARS];  //individual's batiables lower bound 基因变量取值下确界
   double fitness;     //individual's fitness个体适应值
   double rfitness;    //relative fitness个体适应值占种群适应值比例
   double cfitness;    //curmulation fitness个体适应值的累加比例
 };
struct genotype population[POPSIZE+1];
//population 当前种群 population[POPSIZE]用于存放个体最优值并假设最优个体能存活下去
//在某些遗传算法中最优值个体并不一定能够存活下去
struct genotype newpopulation[POPSIZE+1]; //new population replaces the old generation 子种群
 /*Declaration of procedures used by the gentic algorithm*/
 void initialize(void);          //初始化函数
 double randval(double,double);      //随机函数
 double funtion(double x1,double x2);  //目标函数
 void evaluate(void);          //评价函数
 void keep_the_best(void);        //保留最优个体
 void elitist(void);            //当前种群与子代种群最优值比较
 void select(void);
 void crossover(void);          //基因重组函数
 void swap(double *,double *);      //交换函数
 void mutate(void);            //基因突变函数
 double report(void);          //数据记录函数
void initialize(void)
 {
  int i,j;
   for(i=0;i<NVARS;i++)
   {
    for(j=0;j<POPSIZE+1;j++)
    {
       if(!i)
       {
        population[j].fitness=0;
        population[j].rfitness=0;
        population[j].cfitness=0;
       }
      population[j].lower[i]=LBOUND;
      population[j].upper[i]=UBOUND;
      population[j].gene[i]=randval(population[j].lower[i],population[j].upper[i]);
     }
   }
 }
//***************************************************************************
//Random value generator:generates a value within bounds
//***************************************************************************
 double randval(double low,double high)
 {
   double val;
   val=((double)(rand()%10000)/10000)*(high-low)+low;
  return val;
 }
//目标函数
 double funtion(double x,double y)
{
  double result1=sqrt(x*x+y*y)+sqrt((x-12)*(x-12)+y*y)+sqrt((x-8)*(x-8)+(y-6)*(y-6));
  return result1;
}
 //***************************************************************************
 //Evaluation function:evaluate the individual's fitness.评价函数给出个体适应值
//Each time the function is changes,the code has to be recompl
 //***************************************************************************
 void evaluate(void)
 {
  int mem;
  int i;
  double x[NVARS];
  for(mem=0;mem<POPSIZE;mem++)
   {
 
    for(i=0;i<NVARS;i++)
    x[i]=population[mem].gene[i];
    population[mem].fitness=funtion(x[0],x[1]);//将目标函数值作为适应值
  }
 }
 //***************************************************************************************
 //Keep_the_best function:This function keeps track of the best member of the population.
//找出种群中的个体最优值并将其移动到最后
//***************************************************************************************
 void keep_the_best()
 {
   int mem;
   int i;
   cur_best=0;
   for(mem=0;mem<POPSIZE;mem++)//找出最高适应值个体
  {
     if(population[mem].fitness<population[cur_best].fitness)
     {
       cur_best=mem;     
    }
  }
  //将最优个体复制至population[POSIZE]
   if(population[cur_best].fitness<=population[POPSIZE].fitness||population[POPSIZE].fitness<1)//防止出现种群基因退化 故保留历史最优个体
  {
    population[POPSIZE].fitness=population[cur_best].fitness;
    for(i=0;i<NVARS;i++)
    population[POPSIZE].gene[i]=population[cur_best].gene[i];
  
}
 //***************************************************************************
 //last in the array.If the best individual from the new populatin is better
//than the best individual from the previous population ,then copy the best
 //from the new population;else replace the worst individual from the current
 //population with the best one from the previous generation.防止种群最优值退化
//***************************************************************************
 void elitist()
{
   int i;
  double best,worst;//适应值
  int best_mem,worst_mem;//序号
  best_mem=worst_mem=0;
  best=population[best_mem].fitness;//最高适应值初始化
  worst=population[worst_mem].fitness;//最低适应值初始化
  for(i=1;i<POPSIZE;i++)//找出最高和最低适应值 算法有待改进
   {   
     if(population[i].fitness<best)
     {
       best=population[i].fitness;
      best_mem=i;
     }
    if(population[i].fitness>worst)
     {
       worst=population[i].fitness;
      worst_mem=i;
    
   }
  if(best<=population[POPSIZE].fitness)//赋值
   {
    for(i=0;i<NVARS;i++)
       population[POPSIZE].gene[i]=population[best_mem].gene[i];
    population[POPSIZE].fitness=population[best_mem].fitness;
   }
   else
  {
     for(i=0;i<NVARS;i++)
       population[worst_mem].gene[i]=population[POPSIZE].gene[i];
     population[worst_mem].fitness=population[POPSIZE].fitness;
   }
}
 //***************************************************************************
 //Select function:Standard proportional selection for maximization problems
//incorporating elitist model--makes sure that the best member survives.筛选函数并产生子代
//***************************************************************************
 void select(void)
 {
   int mem,i,j;
   double sum=0;
   double p;
   for(mem=0;mem<POPSIZE;mem++)//所有适应值求和
  {
     sum+=population[mem].fitness;
   }
   for(mem=0;mem<POPSIZE;mem++)
   {
    population[mem].rfitness=population[mem].fitness/sum;//个人认为还不如建一个种群类 把sum看成类成员
  }
  population[0].cfitness=population[0].rfitness;
  for(mem=1;mem<POPSIZE;mem++)
  {
    population[mem].cfitness=population[mem-1].cfitness+population[mem].rfitness;
  }
   for(i=0;i<POPSIZE;i++)
  {
     p=rand()%1000/1000.0;
     if(p<population[0].cfitness)
    {
       newpopulation[i]=population[0];
     }
     else
    {
      for(j=0;j<POPSIZE;j++)
         if(p>=population[j].cfitness&&p<population[j+1].cfitness)
           newpopulation[i]=population[j+1];
     }
   }
   for(i=0;i<POPSIZE;i++)//子代变父代
     population[i]=newpopulation[i];
}
//***************************************************************************
 //Crossover:performs crossover of the selected parents.
 //***************************************************************************
void Xover(int one,int two)//基因重组函数
{
   int i;
  int point;
  if(NVARS>1)
  {
     if(NVARS==2)
      point=1;
    else
      point=(rand()%(NVARS-1))+1;//两个都重组吗?
    for(i=0;i<point;i++)//只有第一个基因发生重组有待改进
      swap(&population[one].gene[i],&population[two].gene[i]);
   }
 }
//***************************************************************************
//Swapp: a swap procedure the helps in swappling 2 variables
//***************************************************************************
 void swap(double *x,double *y)
 {
  double temp;
  temp=*x;
  *x=*y;
  *y=temp;
}
 //***************************************************************************
 //Crossover function:select two parents that take part in the crossover.
 //Implements a single point corssover.杂交函数
 //***************************************************************************
void crossover(void)
 {
   int mem,one;
   int first=0;
   double x;
  for(mem=0;mem<POPSIZE;++mem)
  {
    x=rand()%1000/1000.0;
    if(x<PXOVER)
     {
       ++first;
      if(first%2==0)//选择杂交的个体对 杂交有待改进 事实上往往是强者与强者杂交 这里没有考虑雌雄与杂交对象的选择
        Xover(one,mem);
      else
         one=mem;
 }
  }
 }
//***************************************************************************
 //Mutation function:Random uniform mutation.a variable selected for mutation
 //变异函数 事实基因的变异往往具有某种局部性
 //is replaced by a random value between lower and upper bounds of the variables.
 //***************************************************************************
 void mutate(void)
 {
   int i,j;
   double lbound,hbound;
   double x;
   for(i=0;i<POPSIZE;i++)
     for(j=0;j<NVARS;j++)
     {
       x=rand()%1000/1000.0;
       if(x<PMUTATION)
      {
         lbound=population[i].lower[j];
         hbound=population[i].upper[j];
         population[i].gene[j]=randval(lbound,hbound);
       }
     }
 }
//***************************************************************************
 //Report function:Reports progress of the simulation.
 //***************************************************************************
 double report(void)
 {
  int i;
  double best_val;//种群内最优适应值
  double avg;//平均个体适应值
   //double stddev;
  double sum_square;//种群内个体适应值平方和
  //double square_sum;
  double sum;//种群适应值
  sum=0.0;
  sum_square=0.0;
  for(i=0;i<POPSIZE;i++)
   {
     sum+=population[i].fitness;
     sum_square+=population[i].fitness*population[i].fitness;
   }
  avg=sum/(double)POPSIZE;
   //square_sum=avg*avg*(double)POPSIZE;
   //stddev=sqrt((sum_square-square_sum)/(POPSIZE-1));
  best_val=population[POPSIZE].fitness;
  fprintf(galog,"%6d %6.3f %6.3f %6.3f %6.3f %6.3f\n",generation,best_val,population[POPSIZE].gene[0],population[POPSIZE].gene[1],avg,sum);
  return avg;
 }
 //***************************************************************************
//main function:Each generation involves selecting the best members,performing
 //crossover & mutation and then evaluating the resulting population,until the
//terminating condition is satisfied.
 //***************************************************************************
 void main(void)
 {
   int i;
   double temp;
   double temp1;
   if((galog=fopen("data.txt","w"))==NULL)
  {
    exit(1);
   }
  generation=1;
  srand(time(NULL));//产生随机数
  fprintf(galog,"number value  x1   x2   avg   sum_value\n");
  printf("generation best average standard\n");
  initialize();
  evaluate();
  keep_the_best();
  temp=report();//记录,暂存上一代个体平均适应值 
   do
   {     
     select();//筛选
     crossover();//杂交
     mutate();//变异
     evaluate();//评价
     keep_the_best();//elitist();
     temp1=report();
     diff=fabs(temp-temp1);//求浮点数x的绝对值
     temp=temp1;
     generation++;
   }while(generation<MAXGENS&&diff>=STOP);
   //fprintf(galog,"\n\n Simulation completed\n");
   //fprintf(galog,"\n Best member:\n");
   printf("\nBest member:\ngeneration:%d\n",generation);
   for(i=0;i<NVARS;i++)
   {
     //fprintf(galog,"\n var(%d)=%3.3f",i,population[POPSIZE].gene[i]);
     printf("X%d=%3.3f\n",i,population[POPSIZE].gene[i]);
   }
   //fprintf(galog,"\n\n Best fitness=%3.3f",population[POPSIZE].fitness);
   fclose(galog);
   printf("\nBest fitness=%3.3f\n",population[POPSIZE].fitness);
 }

感兴趣的读者可以动手测试一下代码,希望对大家学习C++算法能有所帮助。