KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgap > gp > impl > GPPopulation


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 org.jgap.gp.impl;
11
12 import java.io.*;
13 import java.util.*;
14 import org.jgap.*;
15 import org.jgap.gp.*;
16
17 /**
18  * Population for GP programs.
19  *
20  * @author Klaus Meffert
21  * @since 3.0
22  */

23 public class GPPopulation
24     implements Serializable, Comparable JavaDoc {
25   /** String containing the CVS revision. Read out via reflection!*/
26   private final static String JavaDoc CVS_REVISION = "$Revision: 1.14 $";
27
28   /**
29    * The array of GPProgram's that makeup the Genotype's population.
30    */

31   private IGPProgram[] m_programs;
32
33   private transient float[] m_fitnessRank;
34
35   private int m_popSize;
36
37   private transient IGPProgram m_fittestProgram;
38
39   private GPConfiguration m_config;
40
41   /**
42    * Indicates whether at least one of the programs has been changed
43    * (deleted, added, modified).
44    */

45   private boolean m_changed;
46
47   /**
48    * Indicates that the list of GPPrograms has been sorted.
49    */

50   private boolean m_sorted;
51
52   private IGPProgram m_fittestToAdd;
53
54   /*
55    * @param a_config the configuration to use.
56    * @param a_size the maximum size of the population in GPProgram unit
57    * @author Klaus Meffert
58    * @since 3.0
59    */

60   public GPPopulation(GPConfiguration a_config, int a_size)
61       throws InvalidConfigurationException {
62     if (a_config == null) {
63       throw new InvalidConfigurationException("Configuration must not be null!");
64     }
65     m_config = a_config;
66     m_programs = new GPProgram[a_size];
67     m_popSize = a_size;
68     m_fitnessRank = new float[a_size];
69     for (int i = 0; i < a_size; i++) {
70       m_fitnessRank[i] = 0.5f;
71     }
72   }
73
74   /*
75    * @author Klaus Meffert
76    * @since 3.0
77    */

78   public GPPopulation(GPPopulation a_pop)
79       throws InvalidConfigurationException {
80     this(a_pop, false);
81   }
82   public GPPopulation(GPPopulation a_pop, boolean a_keepPrograms)
83       throws InvalidConfigurationException {
84     m_config = a_pop.getGPConfiguration();
85     m_popSize = a_pop.getPopSize();
86     m_programs = new GPProgram[m_popSize];
87     m_fitnessRank = new float[m_popSize];
88     if (a_keepPrograms) {
89       synchronized (m_programs) {
90         for (int i = 0; i < m_popSize; i++) {
91           m_programs[i] = a_pop.getGPProgram(i);
92           m_fitnessRank[i] = a_pop.getFitnessRank(i);
93         }
94       }
95       m_fittestProgram = a_pop.determineFittestProgramComputed();
96       if (m_fittestProgram != null) {
97         m_fittestProgram = (IGPProgram) m_fittestProgram.clone();
98       }
99       setChanged(a_pop.isChanged());
100       if (!m_changed) {
101         m_sorted = true;
102       }
103     }
104     else {
105       for (int i = 0; i < m_popSize; i++) {
106         m_fitnessRank[i] = 0.5f;
107       }
108     }
109   }
110
111   /**
112    * Sorts the population into "ascending" order using some criterion for
113    * "ascending". A Comparator is given which will compare two individuals,
114    * and if one individual compares lower than another individual, the first
115    * individual will appear in the population before the second individual.
116    *
117    * @param c the Comparator to use
118    *
119    * @author Klaus Meffert
120    * @since 3.0
121    */

122   public void sort(Comparator c) {
123     Arrays.sort(m_programs, c);
124     float f = 0;
125     for (int i = 0; i < m_programs.length; i++) {
126       m_fitnessRank[i] = f;
127       f += m_programs[i].getFitnessValue();
128     }
129   }
130
131   /**
132    * Creates a population using the ramped half-and-half method. Adapted from
133    * JGProg.
134    *
135    * @param a_types the type for each chromosome, the length of the array
136    * represents the number of chromosomes
137    * @param a_argTypes the types of the arguments to each chromosome, must be an
138    * array of arrays, the first dimension of which is the number of chromosomes
139    * and the second dimension of which is the number of arguments to the
140    * chromosome
141    * @param a_nodeSets the nodes which are allowed to be used by each chromosome,
142    * must be an array of arrays, the first dimension of which is the number of
143    * chromosomes and the second dimension of which is the number of nodes
144    * @param a_minDepths contains the minimum depth allowed for each chromosome
145    * @param a_maxDepths contains the maximum depth allowed for each chromosome
146    * @param a_maxNodes reserve space for a_maxNodes number of nodes
147    * @param a_fullModeAllowed array of boolean values. For each chromosome there
148    * is one value indicating whether the full mode for creating chromosome
149    * generations during evolution is allowed (true) or not (false)
150    * @throws InvalidConfigurationException
151    *
152    * @author Klaus Meffert
153    * @since 3.0
154    */

155   public void create(Class JavaDoc[] a_types, Class JavaDoc[][] a_argTypes,
156                      CommandGene[][] a_nodeSets, int[] a_minDepths,
157                      int[] a_maxDepths, int a_maxNodes,
158                      boolean[] a_fullModeAllowed)
159       throws InvalidConfigurationException {
160     int divisor;
161     if (m_popSize < 2) {
162       divisor = 1;
163     }
164     else {
165       divisor = m_popSize - 1;
166     }
167     for (int i = 0; i < m_popSize; i++) {
168       IGPProgram program = null;
169         // Vary depth dependent on run index.
170
// ----------------------------------
171
int depth = 2 + (getGPConfiguration().getMaxInitDepth() - 1) * i
172             / divisor;
173         // Create new GP program.
174
// ----------------------
175
int tries = 0;
176         do {
177           try {
178             program = create(a_types, a_argTypes, a_nodeSets,
179                              a_minDepths,
180                              a_maxDepths, depth, (i % 2) == 0,
181                              a_maxNodes,
182                              a_fullModeAllowed);
183             if (i == 0) {
184               // Remember a prototyp of a valid program in case generation
185
// cannot find a valid program within some few tries
186
// --> then clone the prototyp.
187
// Necessary if the maxNodes parameter is chosen too small.
188
// ----------------------------------------------------------
189
getGPConfiguration().setPrototypeProgram(program);
190               /**@todo set prototype to new value after each some evolutions*/
191             }
192             break;
193           } catch (IllegalStateException JavaDoc iex) {
194             tries++;
195             if (tries > getGPConfiguration().getProgramCreationMaxtries()) {
196               ICloneHandler cloner = getGPConfiguration().getJGAPFactory().
197                   getCloneHandlerFor(
198                       getGPConfiguration().getPrototypeProgram(), null);
199               if (cloner != null) {
200                 try {
201                   program = (IGPProgram) cloner.perform(
202                       getGPConfiguration().getPrototypeProgram(), null, null);
203                   break;
204                 } catch (Exception JavaDoc ex) {
205                   ex.printStackTrace();
206                   // Rethrow original error.
207
// -----------------------
208
throw new IllegalStateException JavaDoc(iex.getMessage());
209                 }
210               }
211               throw new IllegalStateException JavaDoc(iex.getMessage());
212             }
213           }
214         } while (true);
215       setGPProgram(i, program);
216     }
217     setChanged(true);
218   }
219
220   /**
221    * Creates a complete, valid ProgramChromosome.
222    *
223    * @param a_types the type of each chromosome, the length
224    * is the number of chromosomes
225    * @param a_argTypes the types of the arguments to each chromosome, must be an
226    * array of arrays, the first dimension of which is the number of chromosomes
227    * and the second dimension of which is the number of arguments to the
228    * chromosome
229    * @param a_nodeSets the nodes which are allowed to be used by each chromosome,
230    * must be an array of arrays, the first dimension of which is the number of
231    * chromosomes and the second dimension of which is the number of nodes
232    * @param a_minDepths contains the minimum depth allowed for each chromosome
233    * @param a_maxDepths contains the maximum depth allowed for each chromosome
234    * @param a_depth the maximum depth of the program to create
235    * @param a_grow true: grow mode, false: full mode
236    * @param a_maxNodes reserve space for a_maxNodes number of nodes
237    * @param a_fullModeAllowed array of boolean values. For each chromosome there
238    * is one value indicating whether the full mode for creating chromosome
239    * generations during evolution is allowed (true) or not (false)
240    * @return ProgramChromosome
241    * @throws InvalidConfigurationException
242    *
243    * @author Klaus Meffert
244    * @since 3.0
245    */

246   public IGPProgram create(Class JavaDoc[] a_types, Class JavaDoc[][] a_argTypes,
247                            CommandGene[][] a_nodeSets, int[] a_minDepths,
248                            int[] a_maxDepths,
249                            int a_depth, boolean a_grow, int a_maxNodes,
250                            boolean[] a_fullModeAllowed)
251       throws InvalidConfigurationException {
252     GPProgram program;
253     // Is there a fit program to be injected?
254
// --------------------------------------
255
if (m_fittestToAdd != null) {
256       ICloneHandler cloner = getGPConfiguration().getJGAPFactory().
257           getCloneHandlerFor(m_fittestToAdd, null);
258       if (cloner == null) {
259         program = (GPProgram)m_fittestToAdd;
260       }
261       else {
262         try {
263           program = (GPProgram) cloner.perform(m_fittestToAdd, null, null);
264         } catch (Exception JavaDoc ex) {
265           ex.printStackTrace();
266           program = (GPProgram)m_fittestToAdd;
267         }
268       }
269       m_fittestToAdd = null;
270     }
271     else {
272       // Create new GP program.
273
// ----------------------
274
program = new GPProgram(getGPConfiguration(), a_types,
275                                         a_argTypes,
276                                         a_nodeSets, a_minDepths, a_maxDepths,
277                                         a_maxNodes);
278       program.growOrFull(a_depth, a_grow, a_maxNodes, a_fullModeAllowed);
279     }
280     return program;
281   }
282
283   /**
284    * @return fixed size of the population
285    *
286    * @author Klaus Meffert
287    * @since 3.0
288    */

289   public int getPopSize() {
290     return m_popSize;
291   }
292
293   /**
294    * @return the GPConfiguration set
295    *
296    * @author Klaus Meffert
297    * @since 3.0
298    */

299   public GPConfiguration getGPConfiguration() {
300     return m_config;
301   }
302
303   /**
304    * Sets the given GPProgram at the given index in the list of GPProgram's.
305    * If the given index is exceeding the list by one, the chromosome is
306    * appended.
307    *
308    * @param a_index the index to set the GPProgram in
309    * @param a_program the GPProgram to be set
310    *
311    * @author Klaus Meffert
312    * @since 3.0
313    */

314   public void setGPProgram(final int a_index, final IGPProgram a_program) {
315     synchronized (m_programs) {
316       m_programs[a_index] = a_program;
317     }
318     setChanged(true);
319   }
320
321   public IGPProgram getGPProgram(int a_index) {
322     return m_programs[a_index];
323   }
324
325   public IGPProgram[] getGPPrograms() {
326     return m_programs;
327   }
328
329   public int size() {
330     return m_programs.length;
331   }
332
333   /**
334    * Determines the fittest GPProgram in the population (the one with the
335    * highest fitness value) and memorizes it. This is an optimized version
336    * compared to calling determineFittesPrograms(1).
337    *
338    * @return the fittest GPProgram of the population
339    *
340    * @author Klaus Meffert
341    * @since 3.0
342    */

343   public IGPProgram determineFittestProgram() {
344     if (!m_changed && m_fittestProgram != null) {
345       return m_fittestProgram;
346     }
347     double bestFitness = -1.0d;
348     IGPFitnessEvaluator evaluator = getGPConfiguration().getGPFitnessEvaluator();
349     double fitness;
350     for (int i = 0; i < m_programs.length && m_programs[i] != null; i++) {
351       IGPProgram program = m_programs[i];
352       fitness = program.getFitnessValue();
353       if (m_fittestProgram == null || evaluator.isFitter(fitness, bestFitness)) {
354         bestFitness = fitness;
355         m_fittestProgram = program;
356       }
357     }
358     setChanged(false);
359     if (m_fittestProgram != null) {
360       ICloneHandler cloner = getGPConfiguration().getJGAPFactory().
361           getCloneHandlerFor(
362               m_fittestProgram, null);
363       if (cloner != null) {
364         try {
365           m_fittestProgram = (IGPProgram) cloner.perform(m_fittestProgram, null, null);
366         } catch (Exception JavaDoc ex) {
367           ; // ignore
368
}
369       }
370     }
371     return m_fittestProgram;
372   }
373
374   /**
375    * Determines the fittest GPProgram in the population, but only considers
376    * programs with already computed fitness value.
377    *
378    * @return the fittest GPProgram of the population
379    *
380    * @author Klaus Meffert
381    * @since 3.2
382    */

383   public IGPProgram determineFittestProgramComputed() {
384     double bestFitness = -1.0d;
385     IGPFitnessEvaluator evaluator = getGPConfiguration().getGPFitnessEvaluator();
386     double fitness;
387     IGPProgram fittest = null;
388     for (int i = 0; i < m_programs.length && m_programs[i] != null; i++) {
389       IGPProgram program = m_programs[i];
390       if (program instanceof GPProgramBase) {
391         GPProgramBase program1 = (GPProgramBase) program;
392         fitness = program1.getFitnessValueDirectly();
393       }
394       else {
395         fitness = program.getFitnessValue();
396       }
397       if (Math.abs(fitness - FitnessFunction.NO_FITNESS_VALUE) >
398           FitnessFunction.DELTA) {
399         if (fittest == null || evaluator.isFitter(fitness, bestFitness)) {
400           fittest = program;
401           bestFitness = fitness;
402         }
403       }
404     }
405     return fittest;
406   }
407
408   /**
409    * Sorts the GPPrograms list and returns the fittest n GPPrograms in
410    * the population.
411    *
412    * @param a_numberOfPrograms number of top performer GPPrograms to be
413    * returned
414    * @return list of the fittest n GPPrograms of the population, or the fittest
415    * x GPPrograms with x = number of GPPrograms in case n > x.
416    *
417    * @author Klaus Meffert
418    * @since 3.0
419    */

420   public List determineFittestChromosomes(final int a_numberOfPrograms) {
421     int numberOfChromosomes = Math.min(a_numberOfPrograms, m_programs.length);
422     if (numberOfChromosomes <= 0) {
423       return null;
424     }
425     if (!m_changed && m_sorted) {
426       return Arrays.asList(m_programs).subList(0, numberOfChromosomes);
427     }
428     // Sort the list of chromosomes using the fitness comparator
429
sortByFitness();
430     // Return the top n chromosomes
431
return Arrays.asList(m_programs).subList(0, numberOfChromosomes);
432   }
433
434   /**
435    * Sorts the programs within the population according to their fitness
436    * value using GPProgramFitnessComparator.
437    *
438    * @author Klaus Meffert
439    * @since 3.0
440    */

441   public void sortByFitness() {
442     // The following construction could be cached but wrt that the
443
// evaluator registered with the configuration could change
444
// --> Don't cache it!
445
sort(new GPProgramFitnessComparator(getGPConfiguration().
446                                         getGPFitnessEvaluator()));
447     setChanged(false);
448     setSorted(true);
449     m_fittestProgram = m_programs[0];
450   }
451
452   public float[] getFitnessRanks() {
453     return m_fitnessRank;
454   }
455
456   public float getFitnessRank(int a_index) {
457     return m_fitnessRank[a_index];
458   }
459
460   /**
461    * Mark that for the population the fittest program may have changed.
462    *
463    * @param a_changed true: population's fittest program may have changed,
464    * false: fittest program evaluated earlier is still valid
465    *
466    * @author Klaus Meffert
467    * @since 3.0
468    */

469   protected void setChanged(final boolean a_changed) {
470     m_changed = a_changed;
471     setSorted(false);
472   }
473
474   /**
475    * @return true: population's programs (maybe) were changed,
476    * false: not changed for sure
477    *
478    * @since 3.0
479    */

480   public boolean isChanged() {
481     return m_changed;
482   }
483
484   /**
485    * Mark the population as sorted.
486    * @param a_sorted true: mark population as sorted
487    *
488    * @author Klaus Meffert
489    * @since 3.0
490    */

491   protected void setSorted(final boolean a_sorted) {
492     m_sorted = a_sorted;
493   }
494
495   /**
496    * This method is not producing symmetric results as -1 is more often returned
497    * than 1 (see description of return value).
498    *
499    * @param a_pop the other population to compare
500    * @return 1: a_pop is null or having fewer programs or equal number
501    * of programs but at least one not contained. 0: both populations
502    * containing exactly the same programs. -1: this population contains fewer
503    * programs than a_pop
504    *
505    * @author Klaus Meffert
506    * @since 2.6
507    */

508   public int compareTo(Object JavaDoc a_pop) {
509     GPPopulation other = (GPPopulation) a_pop;
510     if (a_pop == null) {
511       return 1;
512     }
513     int size1 = size();
514     int size2 = other.size();
515     if (size1 != size2) {
516       if (size1 < size2) {
517         return -1;
518       }
519       else {
520         return 1;
521       }
522     }
523     IGPProgram[] progs2 = other.getGPPrograms();
524     for (int i = 0; i < size1; i++) {
525       if (!containedInArray(progs2, m_programs[i])) {
526         return 1;
527       }
528     }
529     return 0;
530   }
531
532   /**
533    * Checks if a program is contained within an array of programs. Assumes that
534    * in the array no element will follow after the first null element.
535    *
536    * @param a_progs the array to search thru
537    * @param a_prog the program to find
538    * @return true: program found in array via equals-method
539    *
540    * @author Klaus Meffert
541    * @since 3.0
542    */

543   protected boolean containedInArray(IGPProgram[] a_progs, IGPProgram a_prog) {
544     for (int i = 0; i < a_progs.length; i++) {
545       if (a_progs[i] == null) {
546         return false;
547       }
548       if (a_progs[i].equals(a_prog)) {
549         return true;
550       }
551     }
552     return false;
553   }
554
555   /**
556    * The equals-method.
557    *
558    * @param a_pop the population instance to compare with
559    * @return true: given object equal to comparing one
560    *
561    * @author Klaus Meffert
562    * @since 3.0
563    */

564   public boolean equals(Object JavaDoc a_pop) {
565     try {
566       return compareTo(a_pop) == 0;
567     } catch (ClassCastException JavaDoc e) {
568       // If the other object isn't an Population instance
569
// then we're not equal.
570
// ------------------------------------------------
571
return false;
572     }
573   }
574
575   /**
576    * Adds a GP program to this Population. Does nothing when given null.
577    * The injection is actually executed in method create(..)
578    *
579    * @param a_toAdd the program to add
580    *
581    * @author Klaus Meffert
582    * @since 3.2
583    */

584   public void addFittestProgram(final IGPProgram a_toAdd) {
585     if (a_toAdd != null) {
586       m_fittestToAdd = a_toAdd;
587     }
588   }
589 }
590
Popular Tags