Fibonacci


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;
11  
12  import org.jgap.*;
13  import org.jgap.event.*;
14  import org.jgap.gp.*;
15  import org.jgap.gp.impl.*;
16  import org.jgap.gp.function.*;
17  import org.jgap.gp.terminal.*;
18  import org.jgap.util.*;
19  
20  /**
21   * Example demonstrating Genetic Programming (GP) capabilities of JGAP.<p>
22   * Here, the Fibonacci sequence is calculated (only integers are used).<p>
23   * Please note: We try to find a program that computes Fibonacci iteratively.<p>
24   * This example utilizes a INodeValidator (see FibonacciNodeValidator).<p>
25   * Each new best solution found will be displayed as a graphical tree
26   * representing the GP. The tree is written to a PNG-imagefile onto harddisk.
27   *
28   * @author Klaus Meffert
29   * @since 3.0
30   */
31  public class Fibonacci
32      extends GPProblem {
33    /** String containing the CVS revision. Read out via reflection!*/
34    private final static String   CVS_REVISION = "$Revision: 1.27 $";
35  
36    static Variable vx;
37  
38    static Variable va;
39  
40    private final static int NUMFIB = 10;
41  
42    static Integer  [] x = new Integer  [NUMFIB];
43  
44    static int[] y = new int[NUMFIB];
45  
46    public Fibonacci(GPConfiguration a_conf)
47        throws InvalidConfigurationException {
48      super(a_conf);
49    }
50  
51    /**
52     * Sets up the functions to use and other parameters. Then creates the
53     * initial genotype.
54     *
55     * @return the genotype created
56     * @throws InvalidConfigurationException
57     *
58     * @author Klaus Meffert
59     * @since 3.0
60     */
61    public GPGenotype create()
62        throws InvalidConfigurationException {
63      Class  [] types = {
64          CommandGene.VoidClass, CommandGene.VoidClass, CommandGene.IntegerClass};
65      Class  [][] argTypes = { {}, {}, {}
66      };
67      int[] minDepths = new int[] {2, 3, 1};
68      int[] maxDepths = new int[] {2, 9, 1};
69      GPConfiguration conf = getGPConfiguration();
70      /**@todo allow to optionally preset a static program in each chromosome*/
71      CommandGene[][] nodeSets = { {
72          new SubProgram(conf, new Class  [] {CommandGene.VoidClass,
73                         CommandGene.VoidClass}),
74          new Constant(conf, CommandGene.IntegerClass, new Integer  (1)),
75          new StoreTerminal(conf, "mem0", CommandGene.IntegerClass),
76          new StoreTerminal(conf, "mem1", CommandGene.IntegerClass),
77          new Increment(conf, CommandGene.IntegerClass),
78          new NOP(conf),
79      }, {
80          vx = Variable.create(conf, "X", CommandGene.IntegerClass),
81          new AddAndStore(conf, CommandGene.IntegerClass, "mem2"),
82          new ForLoop(conf, CommandGene.IntegerClass, 1, NUMFIB),
83          new Increment(conf, CommandGene.IntegerClass, -1),
84          new TransferMemory(conf, "mem2", "mem1"),
85          new TransferMemory(conf, "mem1", "mem0"),
86          new ReadTerminal(conf, CommandGene.IntegerClass, "mem0"),
87          new ReadTerminal(conf, CommandGene.IntegerClass, "mem1"),
88          new SubProgram(conf, new Class  [] {CommandGene.VoidClass,
89                         CommandGene.VoidClass, CommandGene.VoidClass}),
90      }, {
91          // Commands will be added programmatically, see below.
92          // ---------------------------------------------------
93      }
94      };
95      // Add commands working with internal memory.
96      // ------------------------------------------
97      nodeSets[2] = CommandFactory.createReadOnlyCommands(nodeSets[2], conf,
98          CommandGene.IntegerClass, "mem", 1, 2, !true);
99      // Randomly initialize function data (X-Y table) for Fib(x).
100     // ---------------------------------------------------------
101     for (int i = 0; i < NUMFIB; i++) {
102       int index = i;
103       x[i] = new Integer  (index);
104       y[i] = fib_iter(index);
105       System.out.println(i + ") " + x[i] + "   " + y[i]);
106     }
107     // Create genotype with initial population.
108     // ----------------------------------------
109     return GPGenotype.randomInitialGenotype(conf, types, argTypes, nodeSets,
110         minDepths, maxDepths, 10, new boolean[] {!true, !true, false}, true);
111   }
112 
113   //(Sort of) This is what we would like to (and can) find via GP:
114   private static int fib_iter(int a_index) {
115     // 1
116     if (a_index == 0 || a_index == 1) {
117       return 1;
118     }
119     // 2
120     int a = 1; //Store("mem0", Constant(1))
121     int b = 1; //Store("mem1", Constant(1))
122     int x = 0; //Store("mem2", Constant(0))
123     // 3
124     for (int i = 2; i <= a_index; i++) { //FORX (Subprogram(A;B;C))
125       x = a + b; // A: AddAndStore(Read("mem0"),Read("mem1"),"mem2")
126       a = b; //B: TransferMemory("mem1","mem0")
127       b = x; //C: TransferMemory("mem2","mem1")
128     }
129     return x; //Read("mem2")
130   }
131 
132   //(Sort of) This is what we would like to find via GP:
133   private int fib_array(int a_index) {
134     // 1
135     if (a_index == 0 || a_index == 1) {
136       return 1;
137     }
138     // 2
139     int[] numbers = new int[a_index + 1];
140     numbers[0] = numbers[1] = 1;
141     // 3
142     for (int i = 2; i <= a_index; i++) {
143       numbers[i] = numbers[i - 1] + numbers[i - 2];
144     }
145     return numbers[a_index];
146   }
147 
148   //(Sort of) This is what we would like to (but cannot) find via GP:
149   private static int fib(int a_index) {
150     if (a_index == 0 || a_index == 1) {
151       return 1;
152     }
153     return fib(a_index - 1) + fib(a_index - 2);
154   }
155 
156   /**
157    * Starts the example.
158    *
159    * @param args ignored
160    * @throws Exception
161    *
162    * @author Klaus Meffert
163    * @since 3.0
164    */
165   public static void main(String  [] args) {
166     try {
167       System.out.println("Program to discover: Fibonacci(x)");
168       GPConfiguration config = new GPConfiguration();
169       config.setGPFitnessEvaluator(new DeltaGPFitnessEvaluator());
170       config.setSelectionMethod(new TournamentSelector(4));
171       int popSize;
172       if (args.length == 1) {
173         popSize = Integer.parseInt(args[0]);
174       }
175       else {
176         popSize = 600;
177       }
178       System.out.println("Using population size of " + popSize);
179       config.setMaxInitDepth(6);
180       config.setPopulationSize(popSize);
181       config.setFitnessFunction(new Fibonacci.FormulaFitnessFunction());
182       config.setStrictProgramCreation(false);
183       config.setProgramCreationMaxTries(3);
184       config.setMaxCrossoverDepth(5);
185       // Set a node validator to demonstrate speedup when something is known
186       // about the solution (see FibonacciNodeValidator).
187       // -------------------------------------------------------------------
188       config.setNodeValidator(new FibonacciNodeValidator());
189       // Activate caching og GP programs --> Fitness values will be cached
190       // for programs equal to previously evolved ones.
191       // -----------------------------------------------------------------
192       config.setUseProgramCache(true);
193       final GPProblem problem = new Fibonacci(config);
194       GPGenotype gp = problem.create();
195       gp.setVerboseOutput(true);
196       final Thread   t = new Thread  (gp);
197       // Simple implementation of running evolution in a thread.
198       // -------------------------------------------------------
199       config.getEventManager().addEventListener(GeneticEvent.
200           GPGENOTYPE_EVOLVED_EVENT, new GeneticEventListener() {
201         public void geneticEventFired(GeneticEvent a_firedEvent) {
202           GPGenotype genotype = (GPGenotype) a_firedEvent.getSource();
203           int evno = genotype.getGPConfiguration().getGenerationNr();
204           double freeMem = SystemKit.getFreeMemoryMB();
205           if (evno % 50 == 0) {
206             double allBestFitness = genotype.getAllTimeBest().getFitnessValue();
207             System.out.println("Evolving generation " + evno
208                                + ", all-time-best fitness: " + allBestFitness
209                                + ", memory free: " + freeMem + " MB");
210           }
211           if (evno > 3000) {
212             t.stop();
213           }
214           else {
215             try {
216               // Collect garbage if memory low.
217               // ------------------------------
218               if (freeMem < 50) {
219                 System.gc();
220                 t.sleep(500);
221               }
222               else {
223                 // Avoid 100% CPU load.
224                 // --------------------
225                 t.sleep(30);
226               }
227             } catch (InterruptedException   iex) {
228               iex.printStackTrace();
229               System.exit(1);
230             }
231           }
232         }
233       });
234       config.getEventManager().addEventListener(GeneticEvent.
235           GPGENOTYPE_NEW_BEST_SOLUTION, new GeneticEventListener() {
236         /**
237          * New best solution found.
238          *
239          * @param a_firedEvent GeneticEvent
240          */
241         public void geneticEventFired(GeneticEvent a_firedEvent) {
242           GPGenotype genotype = (GPGenotype) a_firedEvent.getSource();
243           int evno = genotype.getGPConfiguration().getGenerationNr();
244           String   indexString = "" + evno;
245           while (indexString.length() < 5) {
246             indexString = "0" + indexString;
247           }
248           String   filename = "fibonacci_best" + indexString + ".png";
249           IGPProgram best = genotype.getAllTimeBest();
250           try {
251             problem.showTree(best, filename);
252           } catch (InvalidConfigurationException iex) {
253             iex.printStackTrace();
254           }
255           double bestFitness = genotype.getFittestProgram().
256               getFitnessValue();
257           if (bestFitness < 0.001) {
258             genotype.outputSolution(best);
259             t.stop();
260             System.exit(0);
261           }
262         }
263       });
264       t.start();
265     } catch (Exception   ex) {
266       ex.printStackTrace();
267       System.exit(1);
268     }
269   }
270 
271   public static class FormulaFitnessFunction
272       extends GPFitnessFunction {
273     protected double evaluate(final IGPProgram a_subject) {
274       return computeRawFitness(a_subject);
275     }
276 
277     public double computeRawFitness(final IGPProgram a_program) {
278       double error = 0.0f;
279       Object  [] noargs = new Object  [0];
280       // Initialize local stores.
281       // ------------------------
282       a_program.getGPConfiguration().clearStack();
283       a_program.getGPConfiguration().clearMemory();
284       // Compute fitness for each program.
285       // ---------------------------------
286       /**@todo check if program valid, i.e. worth evaluating*/
287       for (int i = 2; i < NUMFIB; i++) {
288         for (int j = 0; j < a_program.size(); j++) {
289           vx.set(x[i]);
290           try {
291             try {
292               // Init. params (a_program.getTypes()) distinguish program flow.
293               // This could be coded dynamically but that would slow down
294               // things a lot.
295               // -------------------------------------------------------------
296               if (j == a_program.size() - 1) {
297                 // Only evaluate after whole GP program was run.
298                 // ---------------------------------------------
299                 double result = a_program.execute_int(j, noargs);
300                 error += Math.abs(result - y[i]);
301               }
302               else {
303                 // Execute memory manipulating subprograms.
304                 // ----------------------------------------
305                 a_program.execute_void(j, noargs);
306               }
307             } catch (IllegalStateException   iex) {
308               error = GPFitnessFunction.MAX_FITNESS_VALUE;
309               break;
310             }
311           } catch (ArithmeticException   ex) {
312             System.out.println("x = " + x[i].intValue());
313             System.out.println(a_program.getChromosome(j));
314             throw ex;
315           }
316         }
317       }
318       if (a_program.getGPConfiguration().stackSize() > 0) {
319         error = GPFitnessFunction.MAX_FITNESS_VALUE;
320       }
321       if (error < 0.000001) {
322         error = 0.0d;
323       }
324       else if (error < GPFitnessFunction.MAX_FITNESS_VALUE) {
325         /**@todo add penalty for longer solutions*/
326       }
327       return error;
328     }
329   }
330 }
331
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags