|
1
|
#include <stdlib.h>
|
|
2
|
#include <time.h>
|
|
3
|
#include <math.h>
|
|
4
|
#include <fstream.h>
|
|
5
|
#include "randgen.h"
|
|
6
|
#include "array.h"
|
|
7
|
|
|
8
|
//
|
|
9
|
// BitArray object class for Genetic Algorithm
|
|
10
|
//
|
|
11
|
|
|
12
|
class BitArray: public Array1D<bool>
|
|
13
|
{
|
|
14
|
public:
|
|
15
|
void
Initialize(int n)
|
|
16
|
{
|
|
17
|
Array1D<bool>::Initialize(n);
|
|
18
|
for(int i=0;i<nb;i++)m[i]=0;
|
|
19
|
}
|
|
20
|
void
Randomize(unsigned long seed);
|
|
21
|
void
SetBit(int ndx, bool bit){m[ndx]=bit;}
|
|
22
|
void
SetBits(ifstream &in){for(int i=0;i<nb;i++)in>>m[i];}
|
|
23
|
bool
GetBit(int ndx){return m[ndx];}
|
|
24
|
long
ToDecimal();
|
|
25
|
int
HammingDistance(BitArray &by);
|
|
26
|
void
Print(ofstream& out){for(int
i=0;i<nb;i++)out<<m[i];out<<endl;}
|
|
27
|
void
Print(){for(int i=0;i<nb;i++)cout<<m[i];cout<<endl;}
|
|
28
|
bool
operator==(BitArray &by);
|
|
29
|
};
|
|
30
|
|
|
31
|
void BitArray::Randomize(unsigned long seed)
|
|
32
|
{
|
|
33
|
RanBit32 rbg(seed);
|
|
34
|
for(int i = 0; i<nb; i++) m[i] = rbg.Next();
|
|
35
|
}
|
|
36
|
|
|
37
|
long BitArray::ToDecimal()
|
|
38
|
{
|
|
39
|
long
value = 0;
|
|
40
|
for(int i = 0; i<nb; i++)
|
|
41
|
{
|
|
42
|
if(m[i])value += m[i]<<i;
|
|
43
|
}
|
|
44
|
return
value;
|
|
45
|
}
|
|
46
|
|
|
47
|
int BitArray::HammingDistance(BitArray
&by)
|
|
48
|
{
|
|
49
|
int
dist=0;
|
|
50
|
for(int i=0;i<nb;i++)if(by.m[i]!=m[i])dist++;
|
|
51
|
return
dist;
|
|
52
|
}
|
|
53
|
|
|
54
|
bool BitArray::operator==(BitArray &by)
|
|
55
|
{
|
|
56
|
if(by.nb!=nb)return false;
|
|
57
|
bool
flag=true;
|
|
58
|
for(int i=0;i<nb;i++)if(by.m[i]!=m[i])
|
|
59
|
{
|
|
60
|
flag
= false;
|
|
61
|
break;
|
|
62
|
}
|
|
63
|
return
flag;
|
|
64
|
}
|
|
65
|
|
|
66
|
|
|
67
|
//
|
|
68
|
// object class for Genetic Algorithm :
Evaluator
|
|
69
|
//
|
|
70
|
|
|
71
|
class Evaluator
|
|
72
|
{
|
|
73
|
protected:
|
|
74
|
int
nb_variables;
|
|
75
|
i1D
nb_bits;
|
|
76
|
Array1D<BitArray> BinaryVariable;
|
|
77
|
public:
|
|
78
|
int
GetTotalBits()
|
|
79
|
{
|
|
80
|
int
total_bits=0;
|
|
81
|
for(int i=0;i<nb_variables;i++)total_bits += nb_bits[i];
|
|
82
|
return total_bits;
|
|
83
|
}
|
|
84
|
int
GetNbVariable(){return nb_variables;}
|
|
85
|
void
Decompose(BitArray &bitarray);
|
|
86
|
virtual double Evaluate(BitArray &bitarray,
|
|
87
|
double
(*userfunc)(f1D ¶))=0;
|
|
88
|
virtual f1D& Decoding(BitArray &individ)=0;
|
|
89
|
};
|
|
90
|
|
|
91
|
void Evaluator::Decompose(BitArray
&bitarray)
|
|
92
|
{
|
|
93
|
int
count=0;
|
|
94
|
for(int i=0;i<nb_variables;i++)
|
|
95
|
{
|
|
96
|
for(int j=0;j<nb_bits.m[nb_variables-1-i];j++)
|
|
97
|
{
|
|
98
|
BinaryVariable[nb_variables-1-i].m[j]=bitarray.m[count];
|
|
99
|
count++;
|
|
100
|
}
|
|
101
|
}
|
|
102
|
}
|
|
103
|
|
|
104
|
class NumericEvaluator : public Evaluator
|
|
105
|
{
|
|
106
|
protected:
|
|
107
|
int
total_bits;
|
|
108
|
f1D
min;
|
|
109
|
f1D
max;
|
|
110
|
public:
|
|
111
|
f1D
RealVariable;
|
|
112
|
void
Initialize(ifstream &in);
|
|
113
|
f1D& Decoding(BitArray &individ);
|
|
114
|
double
Evaluate(BitArray &bitarray,
|
|
115
|
double (*userfunc)(f1D
¶));
|
|
116
|
};
|
|
117
|
|
|
118
|
void NumericEvaluator::Initialize(ifstream
&in)
|
|
119
|
{
|
|
120
|
int
required_precision;
|
|
121
|
in>>nb_variables>>required_precision;
|
|
122
|
int
i,j, morder = required_precision-1;
|
|
123
|
max.Initialize(nb_variables);
|
|
124
|
min.Initialize(nb_variables);
|
|
125
|
nb_bits.Initialize(nb_variables);
|
|
126
|
BinaryVariable.Initialize(nb_variables);
|
|
127
|
RealVariable.Initialize(nb_variables);
|
|
128
|
// define by case
|
|
129
|
for(i=0;i<nb_variables;i++)
|
|
130
|
{in>>min[i]>>max[i];}
|
|
131
|
double
*t=new double[nb_variables];
|
|
132
|
for(i=0;i<nb_variables;i++)
|
|
133
|
t[i]
= double(max[i] - min[i])*pow10(morder);
|
|
134
|
for(i=0;i<nb_variables;i++)nb_bits[i]=0;
|
|
135
|
for(i=0;i<nb_variables;i++)
|
|
136
|
{
|
|
137
|
for(j=1;j<32;j++)if((t[i]>pow(2,j-1))&&(t[i]<=pow(2,j)))
|
|
138
|
{nb_bits[i]=j; break;}
|
|
139
|
}
|
|
140
|
delete t;
|
|
141
|
total_bits=0;
|
|
142
|
for(i=0;i<nb_variables;i++)total_bits+=nb_bits[i];
|
|
143
|
for(i=0;i<nb_variables;i++)
|
|
144
|
BinaryVariable[i].Initialize(nb_bits[i]);
|
|
145
|
}
|
|
146
|
|
|
147
|
double NumericEvaluator::Evaluate(BitArray
&bitarray,
|
|
148
|
double (*userfunc)(f1D ¶))
|
|
149
|
{
|
|
150
|
if(bitarray.nb!=total_bits)return double(0.0);
|
|
151
|
Decoding(bitarray);
|
|
152
|
return
userfunc(RealVariable);
|
|
153
|
}
|
|
154
|
|
|
155
|
f1D& NumericEvaluator::Decoding(BitArray
&individ)
|
|
156
|
{
|
|
157
|
Decompose(individ);
|
|
158
|
for(int i=0;i<nb_variables;i++)
|
|
159
|
{
|
|
160
|
RealVariable[i]=BinaryVariable[i].ToDecimal();
|
|
161
|
RealVariable[i]=min.m[i]+RealVariable[i]*(max.m[i]-min.m[i])
|
|
162
|
/(pow(2,nb_bits.m[i])-1.0);
|
|
163
|
}
|
|
164
|
return
RealVariable;
|
|
165
|
}
|
|
166
|
|
|
167
|
//
|
|
168
|
// object class for Genetic Algorithm :
population
|
|
169
|
//
|
|
170
|
|
|
171
|
class Population
|
|
172
|
{
|
|
173
|
protected:
|
|
174
|
int
generation;
|
|
175
|
int
nb_individ;
|
|
176
|
int
nb_bit;
|
|
177
|
int
optimal_individ_ndx;
|
|
178
|
float
CrossoverP;
|
|
179
|
float
MutationP;
|
|
180
|
float
ReserveP;
|
|
181
|
float
total_fitness;
|
|
182
|
Ran32
GlbRan;
|
|
183
|
Array1D<BitArray> individ, individtmp;
|
|
184
|
f1D
Fitness, AccFitness;
|
|
185
|
f1D
ProbaTable;
|
|
186
|
Array1D<bool> Survivor;
|
|
187
|
i1D
ndx;
|
|
188
|
int
NSurvivor;
|
|
189
|
BitArray CrossoverMask;
|
|
190
|
void
IndividCrossOver(BitArray &b1, BitArray &b2, int pos);
|
|
191
|
void
ConvertFitnessByOrder();
|
|
192
|
void
FindNBestIndivids(f1D &fit, int N);
|
|
193
|
public:
|
|
194
|
void
Initialize(int nindivid, int nbit);
|
|
195
|
void
Recording(Evaluator &eva, ofstream &out);
|
|
196
|
|
|
197
|
// Genetic mecanism
|
|
198
|
f1D& Evaluate(Evaluator &eva, double (*userfunc)(f1D
¶));
|
|
199
|
void
Evolution();
|
|
200
|
void
CrossOverOnePointCut();
// one-point-cut crossover
|
|
201
|
void
CrossOverByMask(unsigned long seed);
// mask crossover
|
|
202
|
void
Mutation();
|
|
203
|
void
Selection();
|
|
204
|
|
|
205
|
// User interface
|
|
206
|
void
SetCrossOverProbability(float p){CrossoverP=p;}
|
|
207
|
void
SetMutationProbability(float p){MutationP=p;}
|
|
208
|
int
Get_Nb_Individ(){return nb_individ;}
|
|
209
|
int
Get_Nb_Bit(){return nb_bit;}
|
|
210
|
BitArray& GetIndivid(int index);
|
|
211
|
BitArray& GetOptimalIndivid();
|
|
212
|
double
GetOptimalFitness();
|
|
213
|
double
GetFitness(int index){return Fitness[index];}
|
|
214
|
double
GetTotalFitness(){return total_fitness;}
|
|
215
|
void
Print(ofstream& out);
|
|
216
|
int
GetOptimalIndividIndex(){return optimal_individ_ndx;}
|
|
217
|
};
|
|
218
|
|
|
219
|
void Population::Initialize(int nindivid, int
nbit)
|
|
220
|
{
|
|
221
|
nb_individ=nindivid;
|
|
222
|
nb_bit=nbit;
|
|
223
|
// default values for CrossoverP, MutationP
|
|
224
|
CrossoverP = 0.6;
|
|
225
|
MutationP = 0.005;
|
|
226
|
ReserveP = 0.1;
|
|
227
|
unsigned long seed = (unsigned long)time(0);
|
|
228
|
GlbRan.Reset(seed);
|
|
229
|
for(int i=0;i<GlbRan.Next(0,10000);i++)seed=GlbRan.Next();
|
|
230
|
GlbRan.Reset(seed);
|
|
231
|
individ.Initialize(nb_individ);
|
|
232
|
individtmp.Initialize(nb_individ*ReserveP);
|
|
233
|
Fitness.Initialize(nb_individ);
|
|
234
|
AccFitness.Initialize(nb_individ);
|
|
235
|
ProbaTable.Initialize(nb_individ);
|
|
236
|
Survivor.Initialize(nb_individ);
|
|
237
|
ndx.Initialize(nb_individ);
|
|
238
|
for(int i=0;i<individ.nb;i++)
|
|
239
|
{
|
|
240
|
individ.m[i].Initialize(nb_bit);
|
|
241
|
individtmp.m[i].Initialize(nb_bit);
|
|
242
|
individ.m[i].Randomize(GlbRan.Next());
|
|
243
|
}
|
|
244
|
CrossoverMask.Initialize(nb_bit);
|
|
245
|
CrossoverMask.Randomize(GlbRan.Next());
|
|
246
|
generation=0;
|
|
247
|
}
|
|
248
|
|
|
249
|
void Population::Recording(Evaluator
&evaluator, ofstream &out)
|
|
250
|
{
|
|
251
|
int
i,j;
|
|
252
|
f1D t;
|
|
253
|
out<<endl<<"generation :
"<<generation<<endl;
|
|
254
|
for(i=0;i<nb_individ;i++)
|
|
255
|
{
|
|
256
|
t =
evaluator.Decoding(individ[i]);
|
|
257
|
out<<i<<"\tf(";
|
|
258
|
for(j=0;j<evaluator.GetNbVariable();j++)out<<t[j]<<",
";out<<") = ";
|
|
259
|
out<<Fitness[i]<<endl;
|
|
260
|
}
|
|
261
|
out<<"average fitness :
"<<total_fitness/float(nb_individ)<<endl;
|
|
262
|
out<<"optimal individual is :
"<<optimal_individ_ndx<<endl;
|
|
263
|
t =
evaluator.Decoding(individ.m[optimal_individ_ndx]);
|
|
264
|
out<<"optimal solution : "<<"\tf(";
|
|
265
|
for(j=0;j<evaluator.GetNbVariable();j++)out<<t[j]<<",
";out<<") = ";
|
|
266
|
out<<Fitness[optimal_individ_ndx];out<<endl;
|
|
267
|
}
|
|
268
|
|
|
269
|
void Population::IndividCrossOver(BitArray
&b1, BitArray &b2, int pos)
|
|
270
|
{
|
|
271
|
bool
b;
|
|
272
|
for(int i=0;i<pos;i++)
|
|
273
|
{
|
|
274
|
b=b1.m[i];
|
|
275
|
b1.m[i]=b2.m[i];
|
|
276
|
b2.m[i]=b;
|
|
277
|
}
|
|
278
|
}
|
|
279
|
|
|
280
|
void Population::ConvertFitnessByOrder()
|
|
281
|
{
|
|
282
|
int
i,j;
|
|
283
|
for(i=0;i<nb_individ;i++)
|
|
284
|
{
|
|
285
|
AccFitness.m[i]=0;
|
|
286
|
for(j=0;j<nb_individ;j++)if(Fitness.m[i]>Fitness.m[j])AccFitness.m[i]++;
|
|
287
|
}
|
|
288
|
for(i=0;i<nb_individ;i++)Fitness.m[i]=AccFitness.m[i];
|
|
289
|
}
|
|
290
|
|
|
291
|
void Population::Selection()
|
|
292
|
{
|
|
293
|
int
i,j;
|
|
294
|
float
sum=0.0;
|
|
295
|
ConvertFitnessByOrder();
|
|
296
|
for(i=0;i<nb_individ;i++)sum+=Fitness.m[i];
|
|
297
|
for(i=0;i<nb_individ;i++)AccFitness.m[i]=Fitness.m[i]/sum;
|
|
298
|
for(i=1;i<nb_individ;i++)AccFitness.m[i]+=AccFitness.m[i-1];
|
|
299
|
fRan32
rg(GlbRan.Next());
|
|
300
|
for(i=0;i<nb_individ;i++)ProbaTable.m[i]=rg.Next(0.0, 1.0);
|
|
301
|
NSurvivor=0;
|
|
302
|
for(i=0;i<nb_individ;i++)if(ProbaTable.m[i]<CrossoverP)
|
|
303
|
{
|
|
304
|
Survivor.m[i] = true;
|
|
305
|
ndx.m[NSurvivor] = i;
|
|
306
|
NSurvivor++;
|
|
307
|
}
|
|
308
|
NSurvivor = (NSurvivor/2)*2;
|
|
309
|
}
|
|
310
|
|
|
311
|
void Population::CrossOverOnePointCut()
|
|
312
|
{
|
|
313
|
int
i,n,a,b;
|
|
314
|
Ran32
rg(GlbRan.Next());
|
|
315
|
for(i=0;i<NSurvivor/2;i++)
|
|
316
|
{
|
|
317
|
a =
rg.Next(0,NSurvivor);
|
|
318
|
b =
rg.Next(0,NSurvivor);
|
|
319
|
n=rg.Next(0,nb_bit);
|
|
320
|
IndividCrossOver(individ[ndx[a]],individ[ndx[b]],n);
|
|
321
|
}
|
|
322
|
}
|
|
323
|
|
|
324
|
void Population::CrossOverByMask(unsigned long
seed)
|
|
325
|
{
|
|
326
|
int
i,j,a,b;
|
|
327
|
RanBit32 rbg(seed);
|
|
328
|
for(i
= 0; i< CrossoverMask.nb; i++) CrossoverMask.m[i] = rbg.Next();
|
|
329
|
Ran32
rg(GlbRan.Next());
|
|
330
|
bool
t;
|
|
331
|
for(i=0;i<NSurvivor/2;i++)
|
|
332
|
{
|
|
333
|
a =
rg.Next(0,NSurvivor);
|
|
334
|
b =
rg.Next(0,NSurvivor);
|
|
335
|
for(j=0;j<CrossoverMask.nb;j++)if(CrossoverMask.m[j]==1)
|
|
336
|
{
|
|
337
|
t
= individ[ndx[a]].m[j];
|
|
338
|
individ[ndx[a]].m[j] = individ[ndx[b]].m[j];
|
|
339
|
individ[ndx[b]].m[j] = t;
|
|
340
|
}
|
|
341
|
}
|
|
342
|
}
|
|
343
|
|
|
344
|
void Population::Mutation()
|
|
345
|
{
|
|
346
|
long
length = nb_individ*nb_bit;
|
|
347
|
int x,
xd, xm;
|
|
348
|
int
nb_mt = int(MutationP*float(length)+0.5);
|
|
349
|
for(int i=0;i<nb_mt;i++)
|
|
350
|
{
|
|
351
|
x =
GlbRan.Next(0, length-1);
|
|
352
|
xd =
x/nb_bit;
|
|
353
|
xm =
x%nb_bit;
|
|
354
|
if(individ[xd].m[xm]==0)individ[xd].m[xm]=1;
|
|
355
|
else
individ[xd].m[xm]=0;
|
|
356
|
}
|
|
357
|
}
|
|
358
|
|
|
359
|
f1D& Population::Evaluate(Evaluator
&evaluator, double (*userfunc)(f1D ¶))
|
|
360
|
{
|
|
361
|
int i;
|
|
362
|
for(i=0;i<nb_individ;i++)
|
|
363
|
Fitness.m[i]=evaluator.Evaluate(individ.m[i],
userfunc);
|
|
364
|
float
max=-1e30;
|
|
365
|
for(i=0;i<nb_individ;i++)if(Fitness.m[i]>max)
|
|
366
|
{
|
|
367
|
max=Fitness.m[i];
|
|
368
|
optimal_individ_ndx=i;
|
|
369
|
}
|
|
370
|
total_fitness=0;
|
|
371
|
for(i=0;i<nb_individ;i++)total_fitness += Fitness.m[i];
|
|
372
|
return
Fitness;
|
|
373
|
}
|
|
374
|
|
|
375
|
void Population::FindNBestIndivids(f1D
&fit, int N)
|
|
376
|
{
|
|
377
|
|
|
378
|
}
|
|
379
|
|
|
380
|
void Population::Evolution()
|
|
381
|
{
|
|
382
|
Selection();
|
|
383
|
//
CrossOverByMask(GlbRan.Next());
|
|
384
|
CrossOverOnePointCut();
|
|
385
|
Mutation();
|
|
386
|
generation++;
|
|
387
|
}
|
|
388
|
|
|
389
|
BitArray& Population::GetIndivid(int ndx)
|
|
390
|
{
|
|
391
|
return
individ[ndx];
|
|
392
|
}
|
|
393
|
|
|
394
|
BitArray& Population::GetOptimalIndivid()
|
|
395
|
{
|
|
396
|
return
individ[optimal_individ_ndx];
|
|
397
|
}
|
|
398
|
|
|
399
|
double Population::GetOptimalFitness()
|
|
400
|
{
|
|
401
|
return
Fitness[optimal_individ_ndx];
|
|
402
|
}
|
|
403
|
|
|
404
|
void Population::Print(ofstream& out)
|
|
405
|
{
|
|
406
|
for(int i=0;i<nb_individ;i++)individ[i].Print(out);
|
|
407
|
}
|
|
408
|
|
|
409
|
|
|
410
|
double user_evaluation_function(f1D &v)
|
|
411
|
{
|
|
412
|
return
-(v[0]*v[0] + v[1]*v[1]);
|
|
413
|
}
|
|
|
|
|
|
|
|
|
|
|
414
|
// Testing main program
|
|
415
|
main()
|
|
416
|
{
|
|
417
|
char
key;
|
|
418
|
char
filename[128];
|
|
419
|
cout<<"Input filename of parameter description data :
";
|
|
420
|
cin>>filename;
|
|
421
|
ifstream in(filename);
|
|
422
|
ofstream out("ga.dat");
|
|
423
|
if(!in){cout<<"Cannot open file! Any key to
terminate...";cin>>key;exit(1);}
|
|
424
|
NumericEvaluator evaluator;
|
|
425
|
evaluator.Initialize(in);
|
|
426
|
Population population;
|
|
427
|
SetCrossOverProbability(0.6);
|
|
428
|
SetMutationProbability(0.02);
|
|
429
|
int
generation, nb_individ;
|
|
430
|
cout<<"\nEnter number of individuals in the population :
";cin>>nb_individ;
|
|
431
|
cout<<"\nEnter number of iteration for evolution :
";cin>>generation;
|
|
432
|
population.Initialize(nb_individ, evaluator.GetTotalBits());
|
|
433
|
population.Evaluate(evaluator, user_evaluation_function);
|
|
434
|
for(int i=0;i<generation;i++)
|
|
435
|
{
|
|
436
|
population.Evolution();
|
|
437
|
population.Evaluate(evaluator,user_evaluation_function);
|
|
438
|
population.Recording(evaluator, out);
|
|
439
|
cout<<i<<endl;
|
|
440
|
}
|
|
441
|
cout<<endl<<"The evolution process is saved in
ga.dat"<<endl;
|
|
442
|
cout<<"any key to terminate...";
|
|
443
|
cin>>key;
|
|
444
|
}
|
