001: /*
002: * This file is part of JGAP.
003: *
004: * JGAP offers a dual license model containing the LGPL as well as the MPL.
005: *
006: * For licensing information please see the file license.txt included with JGAP
007: * or have a look at the top of class org.jgap.Chromosome which representatively
008: * includes the JGAP license policy applicable for any file delivered with JGAP.
009: */
010: package examples.gp.anttrail;
011:
012: import java.io.*;
013: import java.util.*;
014: import org.jgap.*;
015: import org.jgap.event.*;
016: import org.jgap.gp.*;
017: import org.jgap.gp.function.*;
018: import org.jgap.gp.impl.*;
019: import org.jgap.util.*;
020: import org.jgap.util.tree.*;
021:
022: /**
023: * The ant trail problem.
024: *
025: * @author Klaus Meffert
026: * @since 3.01
027: */
028: public class AntTrailProblem extends GPProblem {
029: /** String containing the CVS revision. Read out via reflection!*/
030: private final static String CVS_REVISION = "$Revision: 1.15 $";
031:
032: private int[][] m_map;
033:
034: private static int foodAvail;
035:
036: private static int m_maxx;
037:
038: private static int m_maxy;
039:
040: private static int totalFood;
041:
042: /**
043: * Maximum number of moves allowed.
044: */
045: private static int m_maxMoves = 400;
046:
047: public AntTrailProblem(GPConfiguration a_conf)
048: throws InvalidConfigurationException {
049: super (a_conf);
050: }
051:
052: /**
053: * Sets up the functions to use and other parameters. Then creates the
054: * initial genotype.
055: *
056: * @return the genotype created
057: * @throws InvalidConfigurationException
058: *
059: * @author Klaus Meffert
060: * @since 3.0
061: */
062: public GPGenotype create() throws InvalidConfigurationException {
063: Class[] types = { CommandGene.VoidClass };
064: Class[][] argTypes = { {} };
065: int[] minDepths = new int[] { 6 };
066: int[] maxDepths = new int[] { 9 };
067: GPConfiguration conf = getGPConfiguration();
068: CommandGene[][] nodeSets = { {
069: new SubProgram(conf, new Class[] {
070: CommandGene.VoidClass, CommandGene.VoidClass,
071: CommandGene.VoidClass }),
072: new SubProgram(conf, new Class[] {
073: CommandGene.VoidClass, //nonclassic
074: CommandGene.VoidClass, CommandGene.VoidClass,
075: CommandGene.VoidClass }), new Left(conf),
076: new Right(conf), new Move(conf), new Move(conf, 3), //nonclassic
077: new IfFoodAheadElse(conf), new IfFoodAheadLeft(conf), //nonclassic
078: new IfFoodAheadRight(conf), //nonclassic
079: new Loop(conf, CommandGene.IntegerClass, 3), //nonclassic
080: new TurnToFood(conf), //nonclassic
081: } };
082: // Create genotype with initial population.
083: // ----------------------------------------
084: return GPGenotype.randomInitialGenotype(conf, types, argTypes,
085: nodeSets, minDepths, maxDepths, 5000,
086: new boolean[] { true }, true);
087: }
088:
089: private int[][] readTrail(String a_filename) throws Exception {
090: LineNumberReader lnr;
091: try {
092: lnr = new LineNumberReader(new FileReader(a_filename));
093: } catch (FileNotFoundException fex) {
094: throw new FileNotFoundException("File not found: "
095: + new File(".").getAbsolutePath() + a_filename);
096: }
097: // Read dimensions of trail.
098: // -------------------------
099: try {
100: StringTokenizer st = new StringTokenizer(lnr.readLine());
101: m_maxx = Integer.parseInt(st.nextToken());
102: m_maxy = Integer.parseInt(st.nextToken());
103: int[][] result = new int[m_maxx][m_maxy];
104: int y;
105: foodAvail = 0;
106: for (y = 0; y < m_maxy; y++) {
107: String s = lnr.readLine();
108: if (s == null) {
109: throw new RuntimeException(
110: "Ant trail file ended prematurely");
111: }
112: int x;
113: for (x = 0; x < s.length(); x++) {
114: if (s.charAt(x) == ' ') {
115: result[x][y] = AntMap.EMPTY;
116: } else if (s.charAt(x) == '#') {
117: result[x][y] = AntMap.FOOD;
118: foodAvail++;
119: } else if (s.charAt(x) == '.') {
120: result[x][y] = AntMap.TRAIL;
121: } else {
122: throw new RuntimeException("Bad character '"
123: + s.charAt(x) + "' on line number "
124: + lnr.getLineNumber()
125: + " of the Ant trail file.");
126: }
127: }
128: // fill out rest of X's
129: for (int z = x; z < m_maxx; z++) {
130: result[z][y] = AntMap.EMPTY;
131: }
132: }
133: // fill out rest of Y's
134: for (int z = y; z < m_maxy; z++) {
135: for (int x = 0; x < m_maxx; x++) {
136: result[x][z] = AntMap.EMPTY;
137: }
138: }
139: return result;
140: } catch (NumberFormatException e) {
141: throw new RuntimeException(
142: "The Ant trail file does not begin with x and y integer values.");
143: } catch (IOException e) {
144: throw new RuntimeException(
145: "The Ant trail file could not be read due to an IOException:\n"
146: + e);
147: }
148: }
149:
150: /**
151: * Starts the example.
152: *
153: * @param args ignored
154: * @throws Exception
155: *
156: * @author Klaus Meffert
157: * @since 3.0
158: */
159: public static void main(String[] args) {
160: try {
161: System.out.println("Ant trail problem");
162: GPConfiguration config = new GPConfiguration();
163: config.setGPFitnessEvaluator(new DeltaGPFitnessEvaluator());
164: int popSize = 500;
165: String filename;
166: if (args.length == 1) {
167: filename = args[0];
168: } else {
169: filename = "santafe.trail";
170: }
171: System.out.println("Using population size of " + popSize);
172: System.out.println("Using map " + filename);
173: config.setMaxInitDepth(7);
174: config.setPopulationSize(popSize);
175: final AntTrailProblem problem = new AntTrailProblem(config);
176: GPFitnessFunction func = problem.createFitFunc();
177: config.setFitnessFunction(func);
178: config.setCrossoverProb(0.9f);
179: config.setReproductionProb(0.1f);
180: config.setNewChromsPercent(0.3f);
181: config.setStrictProgramCreation(true);
182: config.setUseProgramCache(true);
183: // Read the trail from file.
184: // -------------------------
185: problem.m_map = problem.readTrail(filename);
186: AntMap antmap = new AntMap(problem.m_map, m_maxMoves);
187: totalFood = countFood(antmap);
188: System.out.println("Food to consume by ant: " + totalFood);
189: GPGenotype gp = problem.create();
190: gp.setVerboseOutput(true);
191: // Simple implementation of running evolution in a thread.
192: // -------------------------------------------------------
193: final Thread t = new Thread(gp);
194: config.getEventManager().addEventListener(
195: GeneticEvent.GPGENOTYPE_EVOLVED_EVENT,
196: new GeneticEventListener() {
197: public void geneticEventFired(
198: GeneticEvent a_firedEvent) {
199: GPGenotype genotype = (GPGenotype) a_firedEvent
200: .getSource();
201: int evno = genotype.getGPConfiguration()
202: .getGenerationNr();
203: double freeMem = SystemKit
204: .getFreeMemoryMB();
205: if (evno % 100 == 0) {
206: double bestFitness = genotype
207: .getFittestProgram()
208: .getFitnessValue();
209: System.out
210: .println("Evolving generation "
211: + evno
212: + ", best fitness: "
213: + bestFitness
214: + ", memory free: "
215: + freeMem + " MB");
216: }
217: if (evno > 500000) {
218: t.stop();
219: } else {
220: try {
221: // Collect garbage if memory low.
222: // ------------------------------
223: if (freeMem < 50) {
224: System.gc();
225: t.sleep(500);
226: } else {
227: // Avoid 100% CPU load.
228: // --------------------
229: t.sleep(30);
230: }
231: } catch (InterruptedException iex) {
232: iex.printStackTrace();
233: System.exit(1);
234: }
235: }
236: }
237: });
238:
239: GeneticEventListener myGeneticEventListener = new GeneticEventListener() {
240: /**
241: * New best solution found.
242: *
243: * @param a_firedEvent GeneticEvent
244: */
245: public void geneticEventFired(GeneticEvent a_firedEvent) {
246: GPGenotype genotype = (GPGenotype) a_firedEvent
247: .getSource();
248: int evno = genotype.getGPConfiguration()
249: .getGenerationNr();
250: String indexString = "" + evno;
251: while (indexString.length() < 5) {
252: indexString = "0" + indexString;
253: }
254: String filename = "anttrail_best" + indexString
255: + ".png";
256: IGPProgram best = genotype.getAllTimeBest();
257: try {
258: // Create graphical tree of GPProgram.
259: // -----------------------------------
260: TreeBranchRenderer antBranchRenderer = new AntTreeBranchRenderer();
261: TreeNodeRenderer antNodeRenderer = new AntTreeNodeRenderer();
262: problem.showTree(best, filename,
263: antBranchRenderer, antNodeRenderer);
264: // Display solution's trail.
265: // -------------------------
266: AntMap antmap = (AntMap) best
267: .getApplicationData();
268: problem.displaySolution(antmap.getMovements());
269: System.out.println(" Number of moves: "
270: + antmap.getMoveCount());
271: System.out.println(" Food taken: "
272: + antmap.getFoodTaken());
273: } catch (InvalidConfigurationException iex) {
274: iex.printStackTrace();
275: }
276: double bestFitness = genotype.getFittestProgram()
277: .getFitnessValue();
278: if (bestFitness < 0.001) {
279: genotype.outputSolution(best);
280: t.stop();
281: System.exit(0);
282: }
283: }
284: };
285:
286: config.getEventManager().addEventListener(
287: GeneticEvent.GPGENOTYPE_NEW_BEST_SOLUTION,
288: myGeneticEventListener);
289: t.start();
290: } catch (Exception ex) {
291: ex.printStackTrace();
292: System.exit(1);
293: }
294: }
295:
296: /**
297: * Display ant trail as found by GP.
298: *
299: * @param a_antmap the map containing the trail
300: */
301: private void displaySolution(int[][] a_antmap) {
302: for (int y = 0; y < m_maxy; y++) {
303: for (int x = 0; x < m_maxx; x++) {
304: char toPrint;
305: int c = a_antmap[x][y];
306: if (c < 32) {
307: switch (c) {
308: case AntMap.FOOD:
309: toPrint = '#';
310: break;
311: case AntMap.TRAIL:
312: toPrint = '.';
313: break;
314: default:
315: toPrint = ' ';
316: }
317: } else {
318: toPrint = (char) c;
319: }
320: System.out.print(toPrint);
321: }
322: System.out.println();
323: }
324: }
325:
326: private GPFitnessFunction createFitFunc() {
327: return new AntFitnessFunction();
328: }
329:
330: // static class MyGeneticEventListener implements GeneticEventListener {
331: //
332: // private Thread m_t;
333: // private AntTrailProblem m_problem;
334: //
335: // public MyGeneticEventListener(Thread a_t, AntTrailProblem a_problem) {
336: // m_t = a_t;
337: // m_problem =a_problem;
338: // }
339:
340: class AntFitnessFunction extends GPFitnessFunction {
341: private static final int VALUE1 = 100;
342:
343: protected double evaluate(final IGPProgram a_subject) {
344: return computeRawFitness(a_subject);
345: }
346:
347: public double computeRawFitness(final IGPProgram a_program) {
348: double error = 0.0f;
349: Object[] noargs = new Object[0];
350: // Initialize local stores.
351: // ------------------------
352: a_program.getGPConfiguration().clearStack();
353: a_program.getGPConfiguration().clearMemory();
354: AntMap antmap = new AntMap(m_map, m_maxMoves);
355: a_program.setApplicationData(antmap);
356: try {
357: // Execute the program.
358: // --------------------
359: a_program.execute_void(0, noargs);
360: // Determine success of individual.
361: // --------------------------------
362: antmap = (AntMap) a_program.getApplicationData();
363: // The remaining food is the defect rate here.
364: // -------------------------------------------
365: int foodTaken = antmap.getFoodTaken(); // countFood(antmap);
366: error = (VALUE1 + totalFood - foodTaken) * 4;
367: if (a_program.getGPConfiguration().stackSize() > 0) {
368: error = GPFitnessFunction.MAX_FITNESS_VALUE;
369: }
370: if (error < 0.000001) {
371: error = 0.0d;
372: } else if (error < GPFitnessFunction.MAX_FITNESS_VALUE) {
373: // Add penalty for longer trails.
374: // ------------------------------
375: int moves = antmap.getMoveCount();
376: error = error + moves * 1.5;
377: }
378: } catch (IllegalStateException iex) {
379: error = GPFitnessFunction.MAX_FITNESS_VALUE;
380: }
381: return error;
382: }
383: }
384:
385: private static int countFood(AntMap a_map) {
386: int result = 0;
387: for (int x = 0; x < m_maxx; x++) {
388: for (int y = 0; y < m_maxy; y++) {
389: if (a_map.getFromMap(x, y) == AntMap.FOOD) {
390: result++;
391: }
392: }
393: }
394: return result;
395: }
396: }
397: /*
398: abcd
399: e
400: f abcdef
401: g Z g
402: h Y h
403: ijklmnopqr TUVWX i
404: s S j
405: t R k
406: u Q l
407: v P m
408: w O n
409: x N o
410: y M p
411: z L q
412: A K xwvutsr
413: B FGHIJ y
414: C E z
415: D D A
416: E C BC
417: F B
418: G A
419: H z
420: I y
421: J x
422: VUTSRQPONMLK w
423: W v
424: X u
425: Y klmnopqrst
426: Z j
427: a i
428: bcdefgh
429:
430: Number of moves: 193
431: Best solution fitness: 3.0
432: 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 }) })]) }) }) }
433: Depth of chromosome: 6
434:
435: */
|