|
0
|
1 /***********************************
|
|
|
2 * Provides a set of classes *
|
|
|
3 * for using Genetic Algorithms. *
|
|
|
4 * *
|
|
|
5 * Author: Matt P. *
|
|
|
6 * Version: 0.1 *
|
|
|
7 ***********************************/
|
|
|
8
|
|
|
9 module aid.ga;
|
|
|
10
|
|
|
11 import tango.math.Random;
|
|
|
12 import tango.io.Stdout;
|
|
|
13
|
|
|
14 void removeIndex(Gene[] array, uint index){
|
|
|
15 //scope(failure) Stdout.format("E: removeIndex {}", index).newline;
|
|
|
16 if (index == 0)
|
|
|
17 array = array[1..$];
|
|
|
18 else if (index == array.length)
|
|
|
19 array = array[0..$-1];
|
|
|
20 else
|
|
|
21 array = array[0..index-1] ~ array[index+1..$];
|
|
|
22 }
|
|
|
23
|
|
|
24 class Gene {
|
|
|
25 char[] geneSequence;
|
|
|
26 private double fit = -1; // Save the fitness value so that it doesn't have to be calculated more than once.
|
|
|
27 private GeneticAlgorithm* ga;
|
|
|
28
|
|
|
29 this(GeneticAlgorithm* a){
|
|
|
30 ga = a;
|
|
|
31 }
|
|
|
32
|
|
|
33 this(Gene g, GeneticAlgorithm* a){
|
|
|
34 scope(failure) Stdout("E: Gene clone").newline;
|
|
|
35 geneSequence = g.geneSequence.dup;
|
|
|
36 this(a);
|
|
|
37 }
|
|
|
38
|
|
|
39 double fitness(){ // Get property
|
|
|
40 if (fit == -1){
|
|
|
41 fit = ga.calculateFitness(geneSequence);
|
|
|
42 }
|
|
|
43 return fit;
|
|
|
44 }
|
|
|
45
|
|
|
46 Gene[] crossover(Gene other){
|
|
|
47 Gene gene1 = new Gene(this,ga),gene2 = new Gene(other,ga);
|
|
|
48 auto r = Random.shared;
|
|
|
49 auto len = geneSequence.length;
|
|
|
50 char[] temp;
|
|
|
51
|
|
|
52 //scope(failure) Stdout.format("E: crossover {}").newline;
|
|
|
53
|
|
|
54 if (ga.crossoverType == 2){
|
|
|
55 //Stdout("1").flush;
|
|
|
56 uint point1 = r.next(len-2)+1;
|
|
|
57 uint point2 = r.next(len-2)+1;
|
|
|
58 while (point1 == point2)
|
|
|
59 point2 = r.next(len);
|
|
|
60 if (point2 < point1){
|
|
|
61 scope uint t = point1;
|
|
|
62 point1 = point2;
|
|
|
63 point2 = t;
|
|
|
64 }
|
|
|
65 //Stdout("2").newline;
|
|
|
66 scope(failure) Stdout.format("Ed: {},{}",point1,point2).newline;
|
|
|
67 //Stdout(point1)(", ")(point2).newline;
|
|
|
68 temp = gene1.geneSequence[point1..point2].dup;
|
|
|
69 //Stdout("4").flush;
|
|
|
70 gene1.geneSequence[point1..point2] = gene2.geneSequence[point1..point2].dup;
|
|
|
71 //Stdout("5").flush;
|
|
|
72 gene2.geneSequence[point1..point2] = temp;
|
|
|
73 //Stdout("6").flush;
|
|
|
74 } else if (ga.crossoverType == 1) {
|
|
|
75 uint point = r.next(len-2)+1;
|
|
|
76 temp = gene1.geneSequence[point..$].dup;
|
|
|
77 gene1.geneSequence[point..$] = gene2.geneSequence[point..$];
|
|
|
78 gene2.geneSequence[point..$] = temp;
|
|
|
79 } else { // Uniform crossover
|
|
|
80 for (int i = 0; i < len / 2; i++){
|
|
|
81 uint point = r.next(len);
|
|
|
82
|
|
|
83 auto t = gene1.geneSequence[point];
|
|
|
84 gene1.geneSequence[point] = gene2.geneSequence[point];
|
|
|
85 gene2.geneSequence[point] = t;
|
|
|
86 }
|
|
|
87 }
|
|
|
88 return [gene1,gene2];
|
|
|
89 }
|
|
|
90
|
|
|
91 Gene mutate(){
|
|
|
92 Gene g = new Gene(this,ga);
|
|
|
93 uint i = Random.shared.next(g.geneSequence.length);
|
|
|
94 g.geneSequence[i] = ga.getRandomChar(i);
|
|
|
95 return g;
|
|
|
96 }
|
|
|
97 }
|
|
|
98
|
|
|
99 class Generation {
|
|
|
100 private Gene[] genes;
|
|
|
101 private uint population;
|
|
|
102 private GeneticAlgorithm* ga;
|
|
|
103
|
|
|
104 public this(GeneticAlgorithm* g, bool generate = false){
|
|
|
105 ga = g;
|
|
|
106 population = ga.startPopulation;
|
|
|
107 if (generate) generateGenes();
|
|
|
108 }
|
|
|
109
|
|
|
110 public this(Generation gen){
|
|
|
111 genes = gen.genes;
|
|
|
112 ga = gen.ga;
|
|
|
113 }
|
|
|
114
|
|
|
115 public Generation evolve(){
|
|
|
116 Generation newGen = new Generation(ga);
|
|
|
117
|
|
|
118 // Use tournament selection to create a new Generation
|
|
|
119 uint livingPop = cast(uint)(population * ga.survivalRate);
|
|
|
120 newGen.population = population;
|
|
|
121 newGen.genes.length = population;
|
|
|
122 for (auto i = 0; i < livingPop; i++){
|
|
|
123 uint t = tournamentSelect();
|
|
|
124 newGen.genes[i] = genes[t];
|
|
|
125 //genes.removeIndex(t);
|
|
|
126 }
|
|
|
127
|
|
|
128 // Cross over the left over genes
|
|
|
129 for (auto i = livingPop; i < population; i+=2){
|
|
|
130 uint i1 = tournamentSelect(), i2 = tournamentSelect();
|
|
|
131 while (i1 == i2)
|
|
|
132 i2 = tournamentSelect();
|
|
|
133 Gene g1 = genes[i1], g2 = genes[i2];
|
|
|
134
|
|
|
135 Gene[] gs = g1.crossover(g2);
|
|
|
136
|
|
|
137 newGen.genes[i..i+2] = gs[];
|
|
|
138 if (ga.deleteOnCrossover){
|
|
|
139 genes.removeIndex(i1);
|
|
|
140 genes.removeIndex(i2);
|
|
|
141 }
|
|
|
142 }
|
|
|
143
|
|
|
144 // Mutate a small amount of genes
|
|
|
145 for (auto i = 0; i < population * ga.mutationRate; i++){
|
|
|
146 uint index = Random.shared.next(newGen.genes.length);
|
|
|
147 newGen.genes[index] = newGen.genes[index].mutate();
|
|
|
148 }
|
|
|
149
|
|
|
150 return newGen;
|
|
|
151 }
|
|
|
152
|
|
|
153 private void generateGenes(){
|
|
|
154 scope(failure) Stdout("E: generateGenes").newline;
|
|
|
155 genes.length = population;
|
|
|
156 for (uint i = 0; i < population; i++){
|
|
|
157 Gene t = new Gene(ga);
|
|
|
158 t.geneSequence = ga.getRandomGenotype();
|
|
|
159 genes[i] = t;
|
|
|
160 }
|
|
|
161 }
|
|
|
162
|
|
|
163 private uint tournamentSelect(){
|
|
|
164 Gene[4] gens;
|
|
|
165 uint[4] indices;
|
|
|
166 scope(failure) Stdout("E: tournamentSelect").newline;
|
|
|
167 for (uint i = 0; i < 4; i++){
|
|
|
168 indices[i] = Random.shared.next(genes.length);
|
|
|
169 gens[i] = genes[indices[i]];
|
|
|
170 }
|
|
|
171 double max = gens[0].fitness;
|
|
|
172 uint index = indices[0];
|
|
|
173 foreach (i,g; gens){
|
|
|
174 if (g.fitness > max){
|
|
|
175 max = g.fitness;
|
|
|
176 index = indices[i];
|
|
|
177 }
|
|
|
178 }
|
|
|
179 return index;
|
|
|
180 }
|
|
|
181 }
|
|
|
182
|
|
|
183 class GeneticAlgorithm {
|
|
|
184 public double delegate(char[]) calculateFitness; // Set these before you do anything with the library
|
|
|
185 public char[] delegate() getRandomGenotype;
|
|
|
186 public char delegate(uint index) getRandomChar;
|
|
|
187 public double survivalRate = 0.5;
|
|
|
188 public double mutationRate = 0.05;
|
|
|
189 public bool deleteOnCrossover = true;
|
|
|
190 public int crossoverType = 1; // 1 point crossover
|
|
|
191 public uint startPopulation = 1000;
|
|
|
192 public bool verbose = false;
|
|
|
193 public uint bailout = 1000;
|
|
|
194
|
|
|
195 public double fitnessThreshold;
|
|
|
196
|
|
|
197 public uint run(){
|
|
|
198 //Stdout("t").flush;
|
|
|
199 Generation currGen = new Generation(&this,true);
|
|
|
200 //Stdout("test").flush;
|
|
|
201 bool stop = false;
|
|
|
202 uint generation = 1;
|
|
|
203 double average;
|
|
|
204 double max;
|
|
|
205 while (true){
|
|
|
206 if (verbose) max = 0;
|
|
|
207 if (verbose) average = 0;
|
|
|
208 foreach (Gene g; currGen.genes){
|
|
|
209 if (verbose) average += g.fitness;
|
|
|
210
|
|
|
211 if (verbose) if (g.fitness > max) max = g.fitness;
|
|
|
212 if (g.fitness >= fitnessThreshold){
|
|
|
213 stop = true;
|
|
|
214 }
|
|
|
215 }
|
|
|
216 if (verbose) average /= currGen.genes.length;
|
|
|
217 if (verbose) Stdout.formatln("Gen: {} Avg: {:.4} Max: {:.4}",generation, average, max);
|
|
|
218 if (stop || generation >= bailout) return generation;
|
|
|
219 currGen = currGen.evolve();
|
|
|
220 generation++;
|
|
|
221 }
|
|
|
222 }
|
|
|
223 }
|
|
|
224
|
|
|
225
|
|
|
226
|
