KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > examples > gp > anttrail > AntTrailProblem


1 /*
2  * This file is part of JGAP.
3  *
4  * JGAP offers a dual license model containing the LGPL as well as the MPL.
5  *
6  * For licencing information please see the file license.txt included with JGAP
7  * or have a look at the top of class org.jgap.Chromosome which representatively
8  * includes the JGAP license policy applicable for any file delivered with JGAP.
9  */
10 package examples.gp.anttrail;
11
12 import java.io.*;
13 import java.util.*;
14 import org.jgap.*;
15 import org.jgap.event.*;
16 import org.jgap.gp.*;
17 import org.jgap.gp.function.*;
18 import org.jgap.gp.impl.*;
19 import org.jgap.util.*;
20 import org.jgap.util.tree.*;
21
22 /**
23  * The ant trail problem.
24  *
25  * @author Klaus Meffert
26  * @since 3.01
27  */
28 public class AntTrailProblem
29     extends GPProblem {
30   /** String containing the CVS revision. Read out via reflection!*/
31   private final static String JavaDoc CVS_REVISION = "$Revision: 1.13 $";
32
33   private int[][] m_map;
34
35   private static int foodAvail;
36
37   private static int m_maxx;
38
39   private static int m_maxy;
40
41   private static int totalFood;
42
43   /**
44    * Maximum number of moves allowed.
45    */
46   private static int m_maxMoves = 400;
47
48   public AntTrailProblem(GPConfiguration a_conf)
49       throws InvalidConfigurationException {
50     super(a_conf);
51   }
52
53   /**
54    * Sets up the functions to use and other parameters. Then creates the
55    * initial genotype.
56    *
57    * @return the genotype created
58    * @throws InvalidConfigurationException
59    *
60    * @author Klaus Meffert
61    * @since 3.0
62    */
63   public GPGenotype create()
64       throws InvalidConfigurationException {
65     Class JavaDoc[] types = {CommandGene.VoidClass};
66     Class JavaDoc[][] argTypes = { {}
67     };
68     int[] minDepths = new int[] {6};
69     int[] maxDepths = new int[] {9};
70     GPConfiguration conf = getGPConfiguration();
71     CommandGene[][] nodeSets = { {
72         new SubProgram(conf, new Class JavaDoc[] {CommandGene.VoidClass,
73                        CommandGene.VoidClass, CommandGene.VoidClass}),
74         new SubProgram(conf, new Class JavaDoc[] {CommandGene.VoidClass, //nonclassic
75 CommandGene.VoidClass, CommandGene.VoidClass,
76                        CommandGene.VoidClass}),
77         new Left(conf),
78         new Right(conf),
79         new Move(conf),
80         new Move(conf, 3), //nonclassic
81 new IfFoodAheadElse(conf),
82         new IfFoodAheadLeft(conf), //nonclassic
83 new IfFoodAheadRight(conf), //nonclassic
84 new Loop(conf, CommandGene.IntegerClass, 3), //nonclassic
85 new TurnToFood(conf), //nonclassic
86 }
87     };
88     // Create genotype with initial population.
89 // ----------------------------------------
90 return GPGenotype.randomInitialGenotype(conf, types, argTypes, nodeSets,
91         minDepths, maxDepths, 5000, new boolean[] {true}, true);
92   }
93
94   private int[][] readTrail(String JavaDoc a_filename)
95       throws Exception JavaDoc {
96     LineNumberReader lnr;
97     try {
98       lnr = new LineNumberReader(new FileReader(a_filename));
99     } catch (FileNotFoundException fex) {
100       throw new FileNotFoundException("File not found: " +
101                                       new File(".").getAbsolutePath() +
102                                       a_filename);
103     }
104     // Read dimensions of trail.
105 // -------------------------
106 try {
107       StringTokenizer st = new StringTokenizer(lnr.readLine());
108       m_maxx = Integer.parseInt(st.nextToken());
109       m_maxy = Integer.parseInt(st.nextToken());
110       int[][] result = new int[m_maxx][m_maxy];
111       int y;
112       foodAvail = 0;
113       for (y = 0; y < m_maxy; y++) {
114         String JavaDoc s = lnr.readLine();
115         if (s == null) {
116           throw new RuntimeException JavaDoc("Ant trail file ended prematurely");
117         }
118         int x;
119         for (x = 0; x < s.length(); x++) {
120           if (s.charAt(x) == ' ') {
121             result[x][y] = AntMap.EMPTY;
122           }
123           else if (s.charAt(x) == '#') {
124             result[x][y] = AntMap.FOOD;
125             foodAvail++;
126           }
127           else if (s.charAt(x) == '.') {
128             result[x][y] = AntMap.TRAIL;
129           }
130           else {
131             throw new RuntimeException JavaDoc("Bad character '" + s.charAt(x) +
132                                        "' on line number " + lnr.getLineNumber() +
133                                        " of the Ant trail file.");
134           }
135         }
136         // fill out rest of X's
137 for (int z = x; z < m_maxx; z++) {
138           result[z][y] = AntMap.EMPTY;
139         }
140       }
141       // fill out rest of Y's
142 for (int z = y; z < m_maxy; z++) {
143         for (int x = 0; x < m_maxx; x++) {
144           result[x][z] = AntMap.EMPTY;
145         }
146       }
147       return result;
148     } catch (NumberFormatException JavaDoc e) {
149       throw new RuntimeException JavaDoc(
150           "The Ant trail file does not begin with x and y integer values.");
151     } catch (IOException e) {
152       throw new RuntimeException JavaDoc(
153           "The Ant trail file could not be read due to an IOException:\n" + e);
154     }
155   }
156
157   /**
158    * Starts the example.
159    *
160    * @param args ignored
161    * @throws Exception
162    *
163    * @author Klaus Meffert
164    * @since 3.0
165    */
166   public static void main(String JavaDoc[] args) {
167     try {
168       System.out.println("Ant trail problem");
169       GPConfiguration config = new GPConfiguration();
170       config.setGPFitnessEvaluator(new DeltaGPFitnessEvaluator());
171       int popSize = 500;
172       String JavaDoc filename;
173       if (args.length == 1) {
174         filename = args[0];
175       }
176       else {
177         filename = "santafe.trail";
178       }
179       System.out.println("Using population size of " + popSize);
180       System.out.println("Using map " + filename);
181       config.setMaxInitDepth(7);
182       config.setPopulationSize(popSize);
183       final AntTrailProblem problem = new AntTrailProblem(config);
184       GPFitnessFunction func = problem.createFitFunc();
185       config.setFitnessFunction(func);
186       config.setCrossoverProb(0.9f);
187       config.setReproductionProb(0.1f);
188       config.setNewChromsPercent(0.3f);
189       config.setStrictProgramCreation(true);
190       config.setUseProgramCache(true);
191       GPGenotype gp = problem.create();
192       gp.setVerboseOutput(true);
193       // Read the trail from file.
194 // -------------------------
195 problem.m_map = problem.readTrail(filename);
196       AntMap antmap = new AntMap(problem.m_map, m_maxMoves);
197       totalFood = countFood(antmap);
198       System.out.println("Food to consume by ant: " + totalFood);
199       // Simple implementation of running evolution in a thread.
200 // -------------------------------------------------------
201 final Thread JavaDoc t = new Thread JavaDoc(gp);
202       config.getEventManager().addEventListener(GeneticEvent.
203           GPGENOTYPE_EVOLVED_EVENT, new GeneticEventListener() {
204         public void geneticEventFired(GeneticEvent a_firedEvent) {
205           GPGenotype genotype = (GPGenotype) a_firedEvent.getSource();
206           int evno = genotype.getGPConfiguration().getGenerationNr();
207           double freeMem = SystemKit.getFreeMemoryMB();
208           if (evno % 100 == 0) {
209             double bestFitness = genotype.getFittestProgram().
210                 getFitnessValue();
211             System.out.println("Evolving generation " + evno
212                                + ", best fitness: " + bestFitness
213                                + ", memory free: " + freeMem + " MB");
214           }
215           if (evno > 500000) {
216             t.stop();
217           }
218           else {
219             try {
220               // Collect garbage if memory low.
221 // ------------------------------
222 if (freeMem < 50) {
223                 System.gc();
224                 t.sleep(500);
225               }
226               else {
227                 // Avoid 100% CPU load.
228 // --------------------
229 t.sleep(30);
230               }
231             } catch (InterruptedException JavaDoc iex) {
232               iex.printStackTrace();
233               System.exit(1);
234             }
235           }
236         }
237       });
238
239       GeneticEventListener myGeneticEventListener =
240       new GeneticEventListener() {
241         /**
242          * New best solution found.
243          *
244          * @param a_firedEvent GeneticEvent
245          */
246         public void geneticEventFired(GeneticEvent a_firedEvent) {
247           GPGenotype genotype = (GPGenotype) a_firedEvent.getSource();
248           int evno = genotype.getGPConfiguration().getGenerationNr();
249           String JavaDoc indexString = "" + evno;
250           while (indexString.length() < 5) {
251             indexString = "0" + indexString;
252           }
253           String JavaDoc filename = "anttrail_best" + indexString + ".png";
254           IGPProgram best = genotype.getAllTimeBest();
255           try {
256             // Create graphical tree of GPProgram.
257 // -----------------------------------
258 TreeBranchRenderer antBranchRenderer = new AntTreeBranchRenderer();
259             TreeNodeRenderer antNodeRenderer = new AntTreeNodeRenderer();
260             problem.showTree(best, filename, antBranchRenderer, antNodeRenderer);
261             // Display solution's trail.
262 // -------------------------
263 AntMap antmap = (AntMap) best.getApplicationData();
264             problem.displaySolution(antmap.getMovements());
265             System.out.println(" Number of moves: " + antmap.getMoveCount());
266             System.out.println(" Food taken: " + antmap.getFoodTaken());
267           } catch (InvalidConfigurationException iex) {
268             iex.printStackTrace();
269           }
270           double bestFitness = genotype.getFittestProgram().
271               getFitnessValue();
272           if (bestFitness < 0.001) {
273             genotype.outputSolution(best);
274             t.stop();
275             System.exit(0);
276           }
277         }
278       };
279
280       config.getEventManager().addEventListener(GeneticEvent.
281           GPGENOTYPE_NEW_BEST_SOLUTION, myGeneticEventListener);
282       t.start();
283     } catch (Exception JavaDoc ex) {
284       ex.printStackTrace();
285       System.exit(1);
286     }
287   }
288
289   /**
290    * Display ant trail as found by GP.
291    *
292    * @param a_antmap the map containing the trail
293    */
294   private void displaySolution(int[][] a_antmap) {
295     for (int y = 0; y < m_maxy; y++) {
296       for (int x = 0; x < m_maxx; x++) {
297         char toPrint;
298         int c = a_antmap[x][y];
299         if (c < 32) {
300           switch (c) {
301             case AntMap.FOOD:
302               toPrint = '#';
303               break;
304             case AntMap.TRAIL:
305               toPrint = '.';
306               break;
307             default:
308               toPrint = ' ';
309           }
310         }
311         else {
312           toPrint = (char) c;
313         }
314         System.out.print(toPrint);
315       }
316       System.out.println();
317     }
318   }
319
320   private GPFitnessFunction createFitFunc() {
321     return new AntFitnessFunction();
322   }
323
324 // static class MyGeneticEventListener implements GeneticEventListener {
325 //
326 // private Thread m_t;
327 // private AntTrailProblem m_problem;
328 //
329 // public MyGeneticEventListener(Thread a_t, AntTrailProblem a_problem) {
330 // m_t = a_t;
331 // m_problem =a_problem;
332 // }
333
334   class AntFitnessFunction
335       extends GPFitnessFunction {
336     private static final int VALUE1 = 100;
337
338     protected double evaluate(final IGPProgram a_subject) {
339       return computeRawFitness(a_subject);
340     }
341
342     public double computeRawFitness(final IGPProgram a_program) {
343       double error = 0.0f;
344       Object JavaDoc[] noargs = new Object JavaDoc[0];
345       // Initialize local stores.
346 // ------------------------
347 a_program.getGPConfiguration().clearStack();
348       a_program.getGPConfiguration().clearMemory();
349       AntMap antmap = new AntMap(m_map, m_maxMoves);
350       a_program.setApplicationData(antmap);
351       try {
352         // Execute the program.
353 // --------------------
354 a_program.execute_void(0, noargs);
355         // Determine success of individual.
356 // --------------------------------
357 antmap = (AntMap) a_program.getApplicationData();
358         // The remaining food is the defect rate here.
359 // -------------------------------------------
360 int foodTaken = antmap.getFoodTaken(); // countFood(antmap);
361 error = (VALUE1 + totalFood - foodTaken) * 4;
362         if (a_program.getGPConfiguration().stackSize() > 0) {
363           error = GPFitnessFunction.MAX_FITNESS_VALUE;
364         }
365         if (error < 0.000001) {
366           error = 0.0d;
367         }
368         else if (error < GPFitnessFunction.MAX_FITNESS_VALUE) {
369           // Add penalty for longer trails.
370 // ------------------------------
371 int moves = antmap.getMoveCount();
372           error = error + moves * 1.5;
373         }
374       } catch (IllegalStateException JavaDoc iex) {
375         error = GPFitnessFunction.MAX_FITNESS_VALUE;
376       }
377       return error;
378     }
379   }
380   private static int countFood(AntMap a_map) {
381     int result = 0;
382     for (int x = 0; x < m_maxx; x++) {
383       for (int y = 0; y < m_maxy; y++) {
384         if (a_map.getFromMap(x, y) == AntMap.FOOD) {
385           result++;
386         }
387       }
388     }
389     return result;
390   }
391 }
392 /*
393  abcd
394     e
395     f abcdef
396     g Z g
397     h Y h
398     ijklmnopqr TUVWX i
399              s S j
400              t R k
401              u Q l
402              v P m
403              w O n
404              x N o
405              y M p
406              z L q
407              A K xwvutsr
408              B FGHIJ y
409              C E z
410              D D A
411              E C BC
412              F B
413              G A
414              H z
415              I y
416              J x
417   VUTSRQPONMLK w
418   W v
419   X u
420   Y klmnopqrst
421   Z j
422   a i
423   bcdefgh
424
425   Number of moves: 193
426   Best solution fitness: 3.0
427   Best solution: loop(3, (loop(3, (loop(3, (sub[(sub[right --> left --> move --> turn-to-food]) --> (if-food (left) else (move)) --> (loop(3, turn-to-food }) --> (loop(3, (loop(3, turn-to-food }) })]) }) }) }
428   Depth of chromosome: 6
429
430  */
431
Popular Tags