|
0
|
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 } |
