Mercurial > projects > aid

comparison trunk/aid/ga.d @ 0:4b2e8e8a633e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Repository setup.
author revcompgeek
date Mon, 03 Mar 2008 19:28:10 -0700
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:4b2e8e8a633e
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