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
|
/* ----------------------------------------------------------------------------
bitstr.C
mbwall 13sep95
Copyright 1995 Massachusetts Institute of Technology
This code can be freely distributed and modified under the terms of the GNU
public license. See the COPYING file for details.
DESCRIPTION:
Source file for the BitString genome (derived from the GNU BitString object).
---------------------------------------------------------------------------- */
#include <ga/random.h>
#include "bitstr.h"
// Set all the initial values to zero. We do NOT call the initialize method at
// this point - initialization must be done explicitly by the user of the
// genome (eg when the population is created or reset). If we called the
// initializer routine here then we could end up with multiple initializations
// and/or calls to dummy initializers (for example when the genome is
// created with a dummy initializer and the initializer is assigned later on).
BitStringGenome::
BitStringGenome(unsigned int l, GAGenome::Evaluator f, void * u) :
GAGenome(UniformInitializer, UniformMutator, Comparator),
BitString() {
crossover(UniformCrossover); evaluator(f); ud=u;
for(int i=0; i<l; i++)
*this += 1;
}
// This is the class-specific copy method. It will get called by the super
// class since the superclass operator= is set up to call ccopy (and that is
// what we define here - a virtual function). We should check to be sure that
// both genomes are the same class.
void
BitStringGenome::copy(const GAGenome & orig) {
if(&orig == this) return;
if(!sameClass(orig)){
GAErr(GA_LOC, className(), "copy", gaErrObjectTypeMismatch);
return;
}
GAGenome::copy(orig);
BitStringGenome &bsg = (BitStringGenome &)orig;
BitString::operator=(bsg._substr(0,bsg.length()));
}
// The clone method basically does the same thing as the copy method, but here
// we return a pointer to a completely new genome (the copy method just fills
// the current genome with the copied contents). It is the responsibility of
// the caller to free the memory returned by this routine.
// This implementation does not make use of the clone method flag.
GAGenome *
BitStringGenome::clone(GAGenome::CloneMethod) const {
return new BitStringGenome(*this);
}
// These are the default operators used by the BitStringGenome.
// The random initializer sets the bits in the bit string randomly to 0 or 1.
// It uses the GARandomBit function to do this (GARandomBit is pretty efficient
// in terms of its calls to your system's random function).
void
BitStringGenome::UniformInitializer(GAGenome & c) {
BitStringGenome &genome=(BitStringGenome &)c;
for(int i=genome.length()-1; i>=0; i--)
genome.gene(i, GARandomBit());
}
// Randomly pick bits in the bit string then flip their values. We try to be
// smart about the number of times we have to call any random functions. If
// the requested likliehood is small enough (relative to the number of bits in
// the genome) then we must do a weighted coin toss on each bit in the genome.
// Otherwise, we just do the expected number of flips (note that this will not
// guarantee the requested mutation rate, but it will come close when the
// length of the bit string is long enough).
int
BitStringGenome::UniformMutator(GAGenome & c, float pmut) {
BitStringGenome &genome=(BitStringGenome &)c;
register int n, i;
if(pmut <= 0.0) return(0);
float nMut = pmut * (float)(genome.length());
if(nMut < 1.0){ // we have to do a flip test on each bit
nMut = 0;
for(i=genome.length()-1; i>=0; i--){
if(GAFlipCoin(pmut)){
genome.gene(i, genome.gene(i) ? 0 : 1);
nMut++;
}
}
}
else{ // only flip the number of bits we need to flip
for(n=1; n<nMut; n++){
i = GARandomInt(0, genome.length()-1); // the index of the bit to flip
genome.gene(i, genome.gene(i) ? 0 : 1);
}
}
return (int)nMut;
}
// The comparator returns a number between 0 and 1 to indicate how similar
// two genomes are. A 0 indicates that they are identical (zero diversity)
// whereas a 1 indicates completely different.
// This implementation assumes that the genomes are the same size.
float
BitStringGenome::Comparator(const GAGenome& a, const GAGenome& b) {
BitStringGenome& sis = (BitStringGenome&)a;
BitStringGenome& bro = (BitStringGenome&)b;
float count=0;
for(int i=sis.length()-1; i>=0; i--)
if(sis.gene(i) == bro.gene(i)) count += 1.0;
return count / sis.length();
}
// This is a an implementation of a uniform crossover for the binary string.
// It assumes that the the genomes are all the same length.
int
BitStringGenome::UniformCrossover(const GAGenome& a, const GAGenome& b,
GAGenome* c, GAGenome* d) {
BitStringGenome& mom=(BitStringGenome &)a;
BitStringGenome& dad=(BitStringGenome &)b;
int n = 0;
if(c && d){
BitStringGenome& sis=(BitStringGenome &)*c;
BitStringGenome& bro=(BitStringGenome &)*d;
for(int i=sis.length()-1; i>=0; i--){
if(GARandomBit()){
sis.gene(i, mom.gene(i));
bro.gene(i, dad.gene(i));
}
else{
sis.gene(i, dad.gene(i));
bro.gene(i, mom.gene(i));
}
}
n = 2;
}
else {
BitStringGenome& sis = (c ? (BitStringGenome&)*c : (BitStringGenome&)*d);
for(int i=sis.length()-1; i>=0; i--)
sis.gene(i, (GARandomBit() ? mom.gene(i) : dad.gene(i)));
n = 1;
}
return n;
}
|
