Mercurial > projects > aid
comparison trunk/ga_maze.d @ 0:4b2e8e8a633e
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 + Genetic Algorithm Maze Test + | |
3 + Author: Matt P. + | |
4 + Version: 0.5 + | |
5 + + | |
6 + Runs a genetic algorithm test using a maze generation + | |
7 + and guessing algorithm. + | |
8 + + | |
9 + Usage: ga_maze [options] + | |
10 + Options: + | |
11 + -h + | |
12 + Prints this information. + | |
13 + -v + | |
14 + Turns on verbose output. + | |
15 + -m float + | |
16 + Specifies the mutation rate for each generation. + | |
17 + Default: 0.05 + | |
18 + + | |
19 + -d float + | |
20 + Specifies the survival rate for each generation. + | |
21 + Default: 0.5 + | |
22 + + | |
23 + -p integer + | |
24 + Specifies the population for each generation. + | |
25 + Default: 1000 + | |
26 + + | |
27 + -l integer + | |
28 + Specifies the maximum length of the solution code.+ | |
29 + Default: 20 + | |
30 + + | |
31 + -r integer + | |
32 + Specifies the number of times to repeat the test. + | |
33 + Default: 20 + | |
34 + + | |
35 + -c char + | |
36 + Specifies the crossover type + | |
37 + s / 1 - One point crossover + | |
38 + t / 2 - Two point crossover + | |
39 + u / 3 - Uniform crossover + | |
40 + Default: s + | |
41 + + | |
42 + -s integer integer + | |
43 + Specifies the size of the maze + | |
44 + Default: 7 7 + | |
45 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/ | |
46 | |
47 | |
48 module ga_maze; | |
49 | |
50 import aid.ga; | |
51 import tango.math.Random; | |
52 import tango.math.Math; | |
53 import tango.io.Stdout; | |
54 //import tango.text.String; | |
55 import Float = tango.text.convert.Float; | |
56 import Integer = tango.text.convert.Integer; | |
57 | |
58 import bcd.sys.times; | |
59 | |
60 char[] chars = "NESW"; | |
61 | |
62 //int numChars = 20; | |
63 int stringLen = 28; | |
64 | |
65 bool[][] maze; | |
66 int w = 7; | |
67 int h = 7; | |
68 | |
69 double average(double[] array){ | |
70 double avg = 0; | |
71 foreach (double v; array) | |
72 avg += v; | |
73 avg /= array.length; | |
74 return avg; | |
75 } | |
76 | |
77 double stdDev(double[] array){ | |
78 double avg = average(array); | |
79 double stddev = 0; | |
80 foreach (double v; array){ | |
81 stddev += (v - avg) * (v - avg); | |
82 } | |
83 stddev = sqrt(stddev/array.length); | |
84 return stddev; | |
85 } | |
86 | |
87 bool[][] generateMaze(uint width, uint height){ | |
88 bool[][] maze; | |
89 | |
90 maze.length = width; | |
91 | |
92 for (auto i = 0; i < width; i++){ | |
93 maze[i].length = height; | |
94 } | |
95 | |
96 bool rowStart = true; | |
97 bool vertical; | |
98 for (auto i = 1; i < width; i+=2){ | |
99 vertical = rowStart; | |
100 rowStart = !rowStart; | |
101 | |
102 for (auto j = 1; j < height; j+=2){ | |
103 maze[i][j] = true; | |
104 if (vertical) | |
105 maze[i + ((Random.shared.next(2)-1)?-1:1)][j] = true; | |
106 else | |
107 maze[i][j + ((Random.shared.next(2)-1)?-1:1)] = true; | |
108 vertical = !vertical; | |
109 } | |
110 } | |
111 | |
112 return maze; | |
113 } | |
114 | |
115 void printMaze(bool[][] m, bool[][] trail = null,char e = '.', char f = 'X', bool outline = true){ | |
116 if (outline){ | |
117 Stdout("+"); | |
118 for (auto j = 0; j < m[0].length; j++){ | |
119 Stdout("-"); | |
120 } | |
121 Stdout("+").newline; | |
122 } | |
123 | |
124 for (auto i = 0; i < m.length; i++){ | |
125 if (outline) Stdout("|"); | |
126 for (auto j = 0; j < m[i].length; j++){ | |
127 if(m[i][j]) Stdout(""~f); | |
128 else if(trail && trail[i][j]) Stdout("+"); | |
129 else Stdout(""~e); | |
130 } | |
131 if (outline) Stdout("|").newline; | |
132 } | |
133 if (outline){ | |
134 Stdout("+"); | |
135 for (auto j = 0; j < m[0].length; j++){ | |
136 Stdout("-"); | |
137 } | |
138 Stdout("+").newline; | |
139 } | |
140 } | |
141 | |
142 /++++++++++++++++++++++++++ Foo ++++++++++++++++++++++++++++++/ | |
143 | |
144 class Foo { | |
145 int count = 0; | |
146 public double calculateFitness(char[] gene){ | |
147 | |
148 bool canMove(int x, int y){ | |
149 return ((x >= 0) && (x < w) && (y >= 0) && (y < h) && (!maze[x][y])); | |
150 } | |
151 | |
152 double square(int v){ | |
153 return v*v; | |
154 } | |
155 | |
156 /*bool[][] trail; | |
157 | |
158 trail.length = w; | |
159 for(uint i = 0; i < w; i++){ | |
160 trail[i].length = h; | |
161 }*/ | |
162 | |
163 double fitness=0; | |
164 int x = 0; | |
165 int y = 0; | |
166 for (uint i = 0; i < gene.length; i++){ | |
167 //trail[x][y] = true; | |
168 //Stdout(""~gene[i]); | |
169 if(gene[i] == 'N' && canMove(x,y-1)) y--; | |
170 if(gene[i] == 'E' && canMove(x+1,y)) x++; | |
171 if(gene[i] == 'S' && canMove(x,y+1)) y++; | |
172 if(gene[i] == 'W' && canMove(x-1,y)) x--; | |
173 | |
174 if (x == w-1 && y == h-1){ | |
175 return 100; | |
176 } | |
177 } | |
178 | |
179 fitness = 100 - sqrt(square(x-(w-1)) + square(y-(h-1))); | |
180 /*if(count < 20){ | |
181 Stdout.format("{} {:.4}",gene,fitness).newline; | |
182 //printMaze(maze,trail); | |
183 count++; | |
184 }*/ | |
185 return fitness; | |
186 } | |
187 | |
188 public char[] getRandomGenotype(){ | |
189 char[] t; | |
190 t.length = stringLen; | |
191 for (int i = 0; i < stringLen; i++){ | |
192 t[i] = chars[Random.shared.next(chars.length)]; | |
193 } | |
194 return t; | |
195 } | |
196 | |
197 public char getRandomChar(uint index){ | |
198 return chars[Random.shared.next(chars.length)]; | |
199 } | |
200 } | |
201 | |
202 /++++++++++++++++++++++ End Foo ++++++++++++++++++++++++++++++/ | |
203 | |
204 void usage(){ | |
205 auto s = | |
206 "Usage: ga_maze [options] \n" | |
207 "Options: \n" | |
208 "-h \n" | |
209 " Prints this information. \n" | |
210 "-v \n" | |
211 " Turns on verbose output. \n" | |
212 "-m float \n" | |
213 " Specifies the mutation rate for each generation. \n" | |
214 " Default: 0.05 \n" | |
215 " \n" | |
216 "-d float \n" | |
217 " Specifies the survival rate for each generation. \n" | |
218 " Default: 0.5 \n" | |
219 " \n" | |
220 "-p integer \n" | |
221 " Specifies the population for each generation. \n" | |
222 " Default: 1000 \n" | |
223 " \n" | |
224 "-l integer \n" | |
225 " Specifies the maximum length of the solution code.\n" | |
226 " Default: 20 \n" | |
227 " \n" | |
228 "-n integer \n" | |
229 " Specifies how many possibilities there are for \n" | |
230 " each character of the code string. \n" | |
231 " Default: 20 \n" | |
232 " \n" | |
233 "-r integer \n" | |
234 " Specifies the number of times to repeat the test. \n" | |
235 " Default: 20 \n" | |
236 " \n" | |
237 "-c char \n" | |
238 " Specifies the crossover type \n" | |
239 " s / 1 - One point crossover \n" | |
240 " t / 2 - Two point crossover \n" | |
241 " u / 3 - Uniform crossover \n" | |
242 " Default: s "; | |
243 Stdout(s).newline; | |
244 } | |
245 | |
246 void main(char[][] args){ | |
247 Foo f = new Foo(); | |
248 GeneticAlgorithm ga = new GeneticAlgorithm(); | |
249 ga.calculateFitness = &f.calculateFitness; | |
250 ga.getRandomGenotype = &f.getRandomGenotype; | |
251 ga.getRandomChar = &f.getRandomChar; | |
252 ga.fitnessThreshold = 100; | |
253 int rep = 20; | |
254 bool dotime = true; | |
255 | |
256 | |
257 for (auto i = 1; i < args.length; i++){ | |
258 char[] arg = args[i]; | |
259 switch (arg){ | |
260 case "-h": | |
261 usage(); | |
262 return; | |
263 case "-m": | |
264 ga.mutationRate = Float.parse(args[++i]); | |
265 break; | |
266 case "-d": | |
267 ga.survivalRate = Float.parse(args[++i]); | |
268 break; | |
269 case "-p": | |
270 ga.startPopulation = Integer.parse(args[++i]); | |
271 break; | |
272 case "-l": | |
273 stringLen = Integer.parse(args[++i]); | |
274 //ga.fitnessThreshold = stringLen; | |
275 break; | |
276 case "-r": | |
277 rep = Integer.parse(args[++i]); | |
278 break; | |
279 case "-v": | |
280 ga.verbose = true; | |
281 break; | |
282 case "-s": | |
283 w = Integer.parse(args[++i]); | |
284 h = Integer.parse(args[++i]); | |
285 stringLen = 2*(w+h); | |
286 break; | |
287 case "-c": | |
288 auto t = args[++i]; | |
289 switch (t){ | |
290 case "s","1": | |
291 ga.crossoverType = 1; | |
292 break; | |
293 case "t","2": | |
294 ga.crossoverType = 2; | |
295 break; | |
296 default: | |
297 ga.crossoverType = 3; | |
298 } | |
299 break; | |
300 case "-b": | |
301 ga.bailout = Integer.parse(args[++i]); | |
302 break; | |
303 case "-t": | |
304 dotime = false; | |
305 break; | |
306 default: | |
307 Stdout.format("Unknown parameter: {}",arg).newline; | |
308 usage(); | |
309 return; | |
310 } | |
311 } | |
312 | |
313 double[] time; | |
314 double[] gens; | |
315 long start,end; | |
316 double generations; | |
317 | |
318 for(auto i = 0; i < rep; i++){ | |
319 maze=generateMaze(w,h); | |
320 | |
321 if(dotime) start = iutime(); | |
322 generations = ga.run(); | |
323 if(dotime) end = iutime() - start; | |
324 | |
325 if(dotime) time ~= end; | |
326 gens ~= generations; | |
327 } | |
328 | |
329 if(dotime) Stdout.format("{0}, {1:.5}, {2}, {3:.5}", average(gens),stdDev(gens),average(time),stdDev(time)).newline; | |
330 else Stdout.format("{0}, {1:.5}", average(gens),stdDev(gens)).newline; //", {2}, {3:.5}" ,average(time),stdDev(time) | |
331 } |