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;
011:
012: import org.jgap.*;
013: import org.jgap.event.*;
014: import org.jgap.gp.*;
015: import org.jgap.gp.impl.*;
016: import org.jgap.gp.function.*;
017: import org.jgap.gp.terminal.*;
018: import org.jgap.util.*;
019:
020: /**
021: * Example demonstrating Genetic Programming (GP) capabilities of JGAP.<p>
022: * Here, the Fibonacci sequence is calculated (only integers are used).<p>
023: * Please note: We try to find a program that computes Fibonacci iteratively.<p>
024: * This example utilizes a INodeValidator (see FibonacciNodeValidator).<p>
025: * Each new best solution found will be displayed as a graphical tree
026: * representing the GP. The tree is written to a PNG-imagefile onto harddisk.
027: *
028: * @author Klaus Meffert
029: * @since 3.0
030: */
031: public class Fibonacci extends GPProblem {
032: /** String containing the CVS revision. Read out via reflection!*/
033: private final static String CVS_REVISION = "$Revision: 1.28 $";
034:
035: static Variable vx;
036:
037: static Variable va;
038:
039: private final static int NUMFIB = 10;
040:
041: static Integer[] x = new Integer[NUMFIB];
042:
043: static int[] y = new int[NUMFIB];
044:
045: public Fibonacci(GPConfiguration a_conf)
046: throws InvalidConfigurationException {
047: super (a_conf);
048: }
049:
050: /**
051: * Sets up the functions to use and other parameters. Then creates the
052: * initial genotype.
053: *
054: * @return the genotype created
055: * @throws InvalidConfigurationException
056: *
057: * @author Klaus Meffert
058: * @since 3.0
059: */
060: public GPGenotype create() throws InvalidConfigurationException {
061: Class[] types = { CommandGene.VoidClass, CommandGene.VoidClass,
062: CommandGene.IntegerClass };
063: Class[][] argTypes = { {}, {}, {} };
064: int[] minDepths = new int[] { 2, 3, 1 };
065: int[] maxDepths = new int[] { 2, 9, 1 };
066: GPConfiguration conf = getGPConfiguration();
067: /**@todo allow to optionally preset a static program in each chromosome*/
068: CommandGene[][] nodeSets = {
069: {
070: new SubProgram(conf, new Class[] {
071: CommandGene.VoidClass,
072: CommandGene.VoidClass }),
073: // new Constant(conf, CommandGene.IntegerClass, new Integer(1)),
074: new StoreTerminal(conf, "mem0",
075: CommandGene.IntegerClass),
076: new StoreTerminal(conf, "mem1",
077: CommandGene.IntegerClass),
078: new Increment(conf, CommandGene.IntegerClass),
079: new NOP(conf),
080: new Terminal(conf, CommandGene.IntegerClass,
081: 0.0, 10.0), },
082: {
083: vx = Variable.create(conf, "X",
084: CommandGene.IntegerClass),
085: new AddAndStore(conf, CommandGene.IntegerClass,
086: "mem2"),
087: new ForLoop(conf, CommandGene.IntegerClass, 1,
088: NUMFIB),
089: new Increment(conf, CommandGene.IntegerClass,
090: -1),
091: new TransferMemory(conf, "mem2", "mem1"),
092: new TransferMemory(conf, "mem1", "mem0"),
093: new ReadTerminal(conf,
094: CommandGene.IntegerClass, "mem0"),
095: new ReadTerminal(conf,
096: CommandGene.IntegerClass, "mem1"),
097: new SubProgram(conf, new Class[] {
098: CommandGene.VoidClass,
099: CommandGene.VoidClass,
100: CommandGene.VoidClass }), }, {
101: // Commands will be added programmatically, see below.
102: // ---------------------------------------------------
103: } };
104: // Add commands working with internal memory.
105: // ------------------------------------------
106: nodeSets[2] = CommandFactory.createReadOnlyCommands(
107: nodeSets[2], conf, CommandGene.IntegerClass, "mem", 1,
108: 2, !true);
109: // Randomly initialize function data (X-Y table) for Fib(x).
110: // ---------------------------------------------------------
111: for (int i = 0; i < NUMFIB; i++) {
112: int index = i;
113: x[i] = new Integer(index);
114: y[i] = fib_iter(index);
115: System.out.println(i + ") " + x[i] + " " + y[i]);
116: }
117: // Create genotype with initial population.
118: // ----------------------------------------
119: return GPGenotype.randomInitialGenotype(conf, types, argTypes,
120: nodeSets, minDepths, maxDepths, 10, new boolean[] {
121: !true, !true, false }, true);
122: }
123:
124: //(Sort of) This is what we would like to (and can) find via GP:
125: private static int fib_iter(int a_index) {
126: // 1
127: if (a_index == 0 || a_index == 1) {
128: return 1;
129: }
130: // 2
131: int a = 1; //Store("mem0", Constant(1))
132: int b = 1; //Store("mem1", Constant(1))
133: int x = 0; //Store("mem2", Constant(0))
134: // 3
135: for (int i = 2; i <= a_index; i++) { //FORX (Subprogram(A;B;C))
136: x = a + b; // A: AddAndStore(Read("mem0"),Read("mem1"),"mem2")
137: a = b; //B: TransferMemory("mem1","mem0")
138: b = x; //C: TransferMemory("mem2","mem1")
139: }
140: return x; //Read("mem2")
141: }
142:
143: //(Sort of) This is what we would like to find via GP:
144: private int fib_array(int a_index) {
145: // 1
146: if (a_index == 0 || a_index == 1) {
147: return 1;
148: }
149: // 2
150: int[] numbers = new int[a_index + 1];
151: numbers[0] = numbers[1] = 1;
152: // 3
153: for (int i = 2; i <= a_index; i++) {
154: numbers[i] = numbers[i - 1] + numbers[i - 2];
155: }
156: return numbers[a_index];
157: }
158:
159: //(Sort of) This is what we would like to (but cannot) find via GP:
160: private static int fib(int a_index) {
161: if (a_index == 0 || a_index == 1) {
162: return 1;
163: }
164: return fib(a_index - 1) + fib(a_index - 2);
165: }
166:
167: /**
168: * Starts the example.
169: *
170: * @param args ignored
171: * @throws Exception
172: *
173: * @author Klaus Meffert
174: * @since 3.0
175: */
176: public static void main(String[] args) {
177: try {
178: System.out.println("Program to discover: Fibonacci(x)");
179: GPConfiguration config = new GPConfiguration();
180: config.setGPFitnessEvaluator(new DeltaGPFitnessEvaluator());
181: config.setSelectionMethod(new TournamentSelector(4));
182: int popSize;
183: if (args.length == 1) {
184: popSize = Integer.parseInt(args[0]);
185: } else {
186: popSize = 600;
187: }
188: System.out.println("Using population size of " + popSize);
189: config.setMaxInitDepth(6);
190: config.setPopulationSize(popSize);
191: config
192: .setFitnessFunction(new Fibonacci.FormulaFitnessFunction());
193: config.setStrictProgramCreation(false);
194: config.setProgramCreationMaxTries(3);
195: config.setMaxCrossoverDepth(5);
196: // Set a node validator to demonstrate speedup when something is known
197: // about the solution (see FibonacciNodeValidator).
198: // -------------------------------------------------------------------
199: config.setNodeValidator(new FibonacciNodeValidator());
200: // Activate caching og GP programs --> Fitness values will be cached
201: // for programs equal to previously evolved ones.
202: // -----------------------------------------------------------------
203: config.setUseProgramCache(true);
204: final GPProblem problem = new Fibonacci(config);
205: GPGenotype gp = problem.create();
206: gp.setVerboseOutput(true);
207: final Thread t = new Thread(gp);
208: // Simple implementation of running evolution in a thread.
209: // -------------------------------------------------------
210: config.getEventManager().addEventListener(
211: GeneticEvent.GPGENOTYPE_EVOLVED_EVENT,
212: new GeneticEventListener() {
213: public void geneticEventFired(
214: GeneticEvent a_firedEvent) {
215: GPGenotype genotype = (GPGenotype) a_firedEvent
216: .getSource();
217: int evno = genotype.getGPConfiguration()
218: .getGenerationNr();
219: double freeMem = SystemKit
220: .getFreeMemoryMB();
221: if (evno % 50 == 0) {
222: double allBestFitness = genotype
223: .getAllTimeBest()
224: .getFitnessValue();
225: System.out
226: .println("Evolving generation "
227: + evno
228: + ", all-time-best fitness: "
229: + allBestFitness
230: + ", memory free: "
231: + freeMem + " MB");
232: }
233: if (evno > 3000) {
234: t.stop();
235: } else {
236: try {
237: // Collect garbage if memory low.
238: // ------------------------------
239: if (freeMem < 50) {
240: System.gc();
241: t.sleep(500);
242: } else {
243: // Avoid 100% CPU load.
244: // --------------------
245: t.sleep(30);
246: }
247: } catch (InterruptedException iex) {
248: iex.printStackTrace();
249: System.exit(1);
250: }
251: }
252: }
253: });
254: config.getEventManager().addEventListener(
255: GeneticEvent.GPGENOTYPE_NEW_BEST_SOLUTION,
256: new GeneticEventListener() {
257: /**
258: * New best solution found.
259: *
260: * @param a_firedEvent GeneticEvent
261: */
262: public void geneticEventFired(
263: GeneticEvent a_firedEvent) {
264: GPGenotype genotype = (GPGenotype) a_firedEvent
265: .getSource();
266: int evno = genotype.getGPConfiguration()
267: .getGenerationNr();
268: String indexString = "" + evno;
269: while (indexString.length() < 5) {
270: indexString = "0" + indexString;
271: }
272: String filename = "fibonacci_best"
273: + indexString + ".png";
274: IGPProgram best = genotype.getAllTimeBest();
275: try {
276: problem.showTree(best, filename);
277: } catch (InvalidConfigurationException iex) {
278: iex.printStackTrace();
279: }
280: double bestFitness = genotype
281: .getFittestProgram()
282: .getFitnessValue();
283: if (bestFitness < 0.001) {
284: genotype.outputSolution(best);
285: t.stop();
286: System.exit(0);
287: }
288: }
289: });
290: t.start();
291: } catch (Exception ex) {
292: ex.printStackTrace();
293: System.exit(1);
294: }
295: }
296:
297: public static class FormulaFitnessFunction extends
298: GPFitnessFunction {
299: protected double evaluate(final IGPProgram a_subject) {
300: return computeRawFitness(a_subject);
301: }
302:
303: public double computeRawFitness(final IGPProgram a_program) {
304: double error = 0.0f;
305: Object[] noargs = new Object[0];
306: // Initialize local stores.
307: // ------------------------
308: a_program.getGPConfiguration().clearStack();
309: a_program.getGPConfiguration().clearMemory();
310: // Compute fitness for each program.
311: // ---------------------------------
312: /**@todo check if program valid, i.e. worth evaluating*/
313: for (int i = 2; i < NUMFIB; i++) {
314: for (int j = 0; j < a_program.size(); j++) {
315: vx.set(x[i]);
316: try {
317: try {
318: // Init. params (a_program.getTypes()) distinguish program flow.
319: // This could be coded dynamically but that would slow down
320: // things a lot.
321: // -------------------------------------------------------------
322: if (j == a_program.size() - 1) {
323: // Only evaluate after whole GP program was run.
324: // ---------------------------------------------
325: double result = a_program.execute_int(
326: j, noargs);
327: error += Math.abs(result - y[i]);
328: } else {
329: // Execute memory manipulating subprograms.
330: // ----------------------------------------
331: a_program.execute_void(j, noargs);
332: }
333: } catch (IllegalStateException iex) {
334: error = GPFitnessFunction.MAX_FITNESS_VALUE;
335: break;
336: }
337: } catch (ArithmeticException ex) {
338: System.out.println("x = " + x[i].intValue());
339: System.out.println(a_program.getChromosome(j));
340: throw ex;
341: }
342: }
343: }
344: if (a_program.getGPConfiguration().stackSize() > 0) {
345: error = GPFitnessFunction.MAX_FITNESS_VALUE;
346: }
347: if (error < 0.000001) {
348: error = 0.0d;
349: } else if (error < GPFitnessFunction.MAX_FITNESS_VALUE) {
350: /**@todo add penalty for longer solutions*/
351: }
352: return error;
353: }
354: }
355: }
|