Genotype


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;
11  
12  import java.io.*;
13  import java.util.*;
14  import org.jgap.event.*;
15  
16  /**
17   * Genotypes are fixed-length populations of chromosomes. As an instance of
18   * a Genotype is evolved, all of its Chromosomes are also evolved. A Genotype
19   * may be constructed normally via constructor, or the static
20   * randomInitialGenotype() method can be used to generate a Genotype with a
21   * randomized Chromosome population.
22   * <p>
23   * Please note that among all created Genotype instances there may only be one
24   * configuration (singleton!), used by all Genotype instances
25   *
26   * @author Neil Rotstan
27   * @author Klaus Meffert
28   * @since 1.0
29   */
30  public class Genotype
31      implements Serializable, Runnable   {
32    /** String containing the CVS revision. Read out via reflection!*/
33    private final static String   CVS_REVISION = "$Revision: 1.93 $";
34  
35    /**
36     * The current Configuration instance.
37     * @since 1.0
38     */
39    private transient Configuration m_activeConfiguration;
40  
41    private transient static Configuration m_staticConfiguration;
42  
43    /**
44     * The array of Chromosomes that makeup the Genotype's population.
45     * @since 2.0
46     */
47    private Population m_population;
48  
49    /**
50     * Constructs a new Genotype instance with the given array of Chromosomes and
51     * the given active Configuration instance. Note that the Configuration object
52     * must be in a valid state when this method is invoked, or a
53     * InvalidConfigurationException will be thrown.
54     *
55     * @param a_configuration the Configuration object to use
56     * @param a_initialChromosomes the Chromosome population to be managed by
57     * this Genotype instance
58     * @throws InvalidConfigurationException if the given Configuration object is
59     * in an invalid state
60     *
61     * @author Neil Rotstan
62     * @author Klaus Meffert
63     * @since 1.0
64     * @deprecated use Genotype(Configuration, Population) instead
65     */
66    public Genotype(Configuration a_configuration,
67                    IChromosome[] a_initialChromosomes)
68        throws InvalidConfigurationException {
69      this(a_configuration, new Population(a_configuration, a_initialChromosomes));
70    }
71  
72    /**
73     * Constructs a new Genotype instance with the given array of
74     * Chromosomes and the given active Configuration instance. Note
75     * that the Configuration object must be in a valid state
76     * when this method is invoked, or a InvalidconfigurationException
77     * will be thrown.
78     *
79     * @param a_configuration the Configuration object to use
80     * @param a_population the Chromosome population to be managed by this
81     * Genotype instance
82     * @throws InvalidConfigurationException
83     *
84     * @author Neil Rotstan
85     * @author Klaus Meffert
86     * @since 2.0
87     */
88    public Genotype(Configuration a_configuration, Population a_population)
89        throws InvalidConfigurationException {
90      // Sanity checks: Make sure neither the Configuration, nor the array
91      // of Chromosomes, nor any of the Genes inside the array is null.
92      // -----------------------------------------------------------------
93      if (a_configuration == null) {
94        throw new IllegalArgumentException  (
95            "The Configuration instance may not be null.");
96      }
97      if (a_population == null) {
98        throw new IllegalArgumentException  (
99            "The Population may not be null.");
100     }
101     for (int i = 0; i < a_population.size(); i++) {
102       if (a_population.getChromosome(i) == null) {
103         throw new IllegalArgumentException  (
104             "The Chromosome instance at index " + i + " of the array of " +
105             "Chromosomes is null. No Chromosomes instance in this array " +
106             "may be null.");
107       }
108     }
109     m_population = a_population;
110     // Lock the settings of the configuration object so that it cannot
111     // be altered.
112     // ---------------------------------------------------------------
113     a_configuration.lockSettings();
114     m_activeConfiguration = a_configuration;
115   }
116 
117   /**
118    * Don't use this constructor, it's only for internal use.
119    *
120    * @param a_configuration the configuration to use
121    * @throws InvalidConfigurationException
122    *
123    * @author Klaus Meffert
124    * @since 3.0
125    */
126   public Genotype(Configuration a_configuration)
127       throws InvalidConfigurationException {
128 
129   }
130 
131   /**
132    * Retrieves the array of Chromosomes that make up the population of this
133    * Genotype instance.
134    *
135    * @return the Population of Chromosomes
136    *
137    * @author Neil Rotstan
138    * @author Klaus Meffert
139    * @since 1.0
140    * @deprecated uses getPopulation() instead
141    */
142   public synchronized IChromosome[] getChromosomes() {
143     Iterator it = getPopulation().iterator();
144     IChromosome[] result = new Chromosome[getPopulation().size()];
145     int i = 0;
146     while (it.hasNext()) {
147       result[i++] = (IChromosome) it.next();
148     }
149     return result;
150   }
151 
152   /**
153    * @return the current population of chromosomes
154    *
155    * @author Klaus Meffert
156    * @since 2.1 (?)
157    */
158   public Population getPopulation() {
159     return m_population;
160   }
161 
162   /**
163    * Retrieves the Chromosome in the Population with the highest fitness
164    * value.
165    *
166    * @return the Chromosome with the highest fitness value, or null if there
167    * are no chromosomes in this Genotype
168    *
169    * @author Neil Rotstan
170    * @author Klaus Meffert
171    * @since 1.0
172    */
173   public synchronized IChromosome getFittestChromosome() {
174     return getPopulation().determineFittestChromosome();
175   }
176 
177   /**
178    * Retrieves the Chromosome in the Population with the highest fitness
179    * value within the given indices.
180    *
181    * @param a_startIndex the index to start the determination with
182    * @param a_endIndex the index to end the determination with
183    * @return the Chromosome with the highest fitness value within the given
184    * indices, or null if there are no chromosomes in this Genotype
185    *
186    * @author Klaus Meffert
187    * @since 3.0
188    */
189   public synchronized IChromosome getFittestChromosome(int a_startIndex,
190       int a_endIndex) {
191     return getPopulation().determineFittestChromosome(a_startIndex, a_endIndex);
192   }
193 
194   /**
195    * Retrieves the top n Chromsomes in the population (the ones with the best
196    * fitness values).
197    *
198    * @param a_numberOfChromosomes the number of chromosomes desired
199    * @return the list of Chromosomes with the highest fitness values, or null
200    * if there are no chromosomes in this Genotype
201    *
202    * @author Charles Kevin Hill
203    * @since 2.4
204    */
205   public synchronized List getFittestChromosomes(int a_numberOfChromosomes) {
206     return getPopulation().determineFittestChromosomes(a_numberOfChromosomes);
207   }
208 
209   /**
210    * Evolves the population of Chromosomes within this Genotype. This will
211    * execute all of the genetic operators added to the present active
212    * configuration and then invoke the natural selector to choose which
213    * chromosomes will be included in the next generation population. Note
214    * that the population size not always remains constant (dependent on the
215    * NaturalSelectors used!).<p>
216    * To consecutively call this method, use evolve(int)!!!
217    *
218    * @author Neil Rotstan
219    * @author Klaus Meffert
220    * @since 1.0
221    */
222   public synchronized void evolve() {
223     if (m_activeConfiguration == null) {
224       throw new IllegalStateException  (
225           "The Configuration object must be set on this"
226           + " Genotype prior to evolution.");
227     }
228     // Adjust population size to configured size (if wanted).
229     // Theoretically, this should be done at the end of this method.
230     // But for optimization issues it is not. If it is the last call to
231     // evolve() then the resulting population possibly contains more
232     // chromosomes than the wanted number. But this is no bad thing as
233     // more alternatives mean better chances having a fit candidate.
234     // If it is not the last call to evolve() then the next call will
235     // ensure the correct population size by calling keepPopSizeConstant.
236     // ------------------------------------------------------------------
237     if (m_activeConfiguration.isKeepPopulationSizeConstant()) {
238       keepPopSizeConstant(getPopulation(),
239                           m_activeConfiguration.getPopulationSize());
240     }
241     // Apply certain NaturalSelectors before GeneticOperators will be applied.
242     // -----------------------------------------------------------------------
243     applyNaturalSelectors(true);
244     // Execute all of the Genetic Operators.
245     // -------------------------------------
246     applyGeneticOperators();
247     // Reset fitness value of genetically operated chromosomes.
248     // Normally, this should not be necessary as the Chromosome
249     // class initializes each newly created chromosome with
250     // FitnessFunction.NO_FITNESS_VALUE. But who knows which
251     // Chromosome implementation is used...
252     // --------------------------------------------------------
253     int originalPopSize = m_activeConfiguration.getPopulationSize();
254     int currentPopSize = getPopulation().size();
255     for (int i = originalPopSize; i < currentPopSize; i++) {
256       IChromosome chrom = getPopulation().getChromosome(i);
257       chrom.setFitnessValueDirectly(FitnessFunction.NO_FITNESS_VALUE);
258     }
259     // Apply certain NaturalSelectors after GeneticOperators have been applied.
260     // ------------------------------------------------------------------------
261     applyNaturalSelectors(false);
262     // If a bulk fitness function has been provided, call it.
263     // ------------------------------------------------------
264     BulkFitnessFunction bulkFunction =
265         m_activeConfiguration.getBulkFitnessFunction();
266     if (bulkFunction != null) {
267       bulkFunction.evaluate(getPopulation());
268     }
269     // Fill up population randomly if size dropped below specified percentage
270     // of original size.
271     // ----------------------------------------------------------------------
272     if (m_activeConfiguration.getMinimumPopSizePercent() > 0) {
273       int sizeWanted = m_activeConfiguration.getPopulationSize();
274       int popSize;
275       int minSize = (int) Math.round(sizeWanted *
276                                      (double) getConfiguration().
277                                      getMinimumPopSizePercent()
278                                      / 100);
279       popSize = getPopulation().size();
280       if (popSize < minSize) {
281         IChromosome newChrom;
282 //        try {
283           IChromosome sampleChrom = m_activeConfiguration.getSampleChromosome();
284           Class   sampleChromClass = sampleChrom.getClass();
285           IInitializer chromIniter = m_activeConfiguration.getJGAPFactory().
286               getInitializerFor(sampleChrom, sampleChromClass);
287           while (getPopulation().size() < minSize) {
288             try {
289               newChrom = (IChromosome) chromIniter.perform(sampleChrom,
290                   sampleChromClass, null);
291 //            Chromosome.randomInitialChromosome(m_activeConfiguration);
292               getPopulation().addChromosome(newChrom);
293             }catch (Exception   ex) {
294               throw new RuntimeException  (ex);
295             }
296           }
297 //        }
298 //        catch (InvalidConfigurationException invex) {
299 //          throw new IllegalStateException(invex.getMessage());
300 //        }
301       }
302     }
303     if (m_activeConfiguration.isPreserveFittestIndividual()) {
304       IChromosome fittest = getFittestChromosome(0,
305                                                  m_activeConfiguration.
306                                                  getPopulationSize() - 1);
307       if (m_activeConfiguration.isKeepPopulationSizeConstant()) {
308         keepPopSizeConstant(getPopulation(),
309                             m_activeConfiguration.getPopulationSize());
310       }
311       // Determine the fittest chromosome in the population.
312       // ---------------------------------------------------
313       if (!getPopulation().contains(fittest)) {
314         // Re-add fittest chromosome to current population.
315         // ------------------------------------------------
316         getPopulation().addChromosome(fittest);
317       }
318     }
319     // Increase number of generation.
320     // ------------------------------
321     m_activeConfiguration.incrementGenerationNr();
322     // Fire an event to indicate we've performed an evolution.
323     // -------------------------------------------------------
324     m_activeConfiguration.getEventManager().fireGeneticEvent(
325         new GeneticEvent(GeneticEvent.GENOTYPE_EVOLVED_EVENT, this));
326   }
327 
328   /**
329    * Evolves this Genotype the specified number of times. This is
330    * equivalent to invoking the standard evolve() method the given number
331    * of times in a row.
332    *
333    * @param a_numberOfEvolutions the number of times to evolve this Genotype
334    * before returning
335    *
336    * @author Klaus Meffert
337    * @since 1.1
338    */
339   public void evolve(int a_numberOfEvolutions) {
340     for (int i = 0; i < a_numberOfEvolutions; i++) {
341       evolve();
342     }
343     if (m_activeConfiguration.isKeepPopulationSizeConstant()) {
344       keepPopSizeConstant(getPopulation(),
345                           m_activeConfiguration.getPopulationSize());
346     }
347   }
348 
349   /**
350    * @return string representation of this Genotype instance, useful for display
351    * purposes
352    *
353    * @author Neil Rotstan
354    * @since 1.0
355    */
356   public String   toString() {
357     StringBuffer   buffer = new StringBuffer  ();
358     for (int i = 0; i < getPopulation().size(); i++) {
359       buffer.append(getPopulation().getChromosome(i).toString());
360       buffer.append(" [");
361       buffer.append(getPopulation().getChromosome(i).getFitnessValueDirectly());
362       buffer.append("]\n");
363     }
364     return buffer.toString();
365   }
366 
367   /**
368    * Convenience method that returns a newly constructed Genotype
369    * instance configured according to the given Configuration instance.
370    * The population of Chromosomes will be created according to the setup of
371    * the sample Chromosome in the Configuration object, but the gene values
372    * (alleles) will be set to random legal values.
373    *
374    * @param a_configuration the current active Configuration object
375    * @return a newly constructed Genotype instance
376    *
377    * @throws IllegalArgumentException if the given Configuration object is null
378    * @throws InvalidConfigurationException if the given Configuration
379    * instance is not in a valid state
380    *
381    * @author Neil Rotstan
382    * @author Klaus Meffert
383    * @since 2.3
384    */
385   public static Genotype randomInitialGenotype(Configuration
386                                                a_configuration)
387       throws InvalidConfigurationException {
388     if (a_configuration == null) {
389       throw new IllegalArgumentException  (
390           "The Configuration instance may not be null.");
391     }
392     a_configuration.lockSettings();
393     // Create an array of chromosomes equal to the desired size in the
394     // active Configuration and then populate that array with Chromosome
395     // instances constructed according to the setup in the sample
396     // Chromosome, but with random gene values (alleles). The Chromosome
397     // class randomInitialChromosome() method will take care of that for
398     // us.
399     // ------------------------------------------------------------------
400     int populationSize = a_configuration.getPopulationSize();
401     IChromosome sampleChrom = a_configuration.getSampleChromosome();
402     Population pop = new Population(a_configuration, populationSize);
403     // Do randomized initialization.
404     // -----------------------------
405     Genotype result = new Genotype(a_configuration, pop);
406     result.fillPopulation(populationSize);
407     return result;
408   }
409 
410   /**
411    * Fills up the population with random chromosomes if necessary.
412    *
413    * @param a_num the number of chromosomes to add
414    * @throws InvalidConfigurationException
415    *
416    * @author Klaus Meffert
417    * @since 3.2
418    */
419   public void fillPopulation(final int a_num)
420       throws InvalidConfigurationException {
421     IChromosome sampleChrom = getConfiguration().getSampleChromosome();
422     Class   sampleClass = sampleChrom.getClass();
423     IInitializer chromIniter = getConfiguration().getJGAPFactory().
424         getInitializerFor(sampleChrom, sampleClass);
425     if (chromIniter == null) {
426       throw new InvalidConfigurationException("No initializer found for class "
427                                               + sampleClass);
428     }
429     try {
430       for (int i = 0; i < a_num; i++) {
431         getPopulation().addChromosome( (IChromosome) chromIniter.perform(sampleChrom,
432             sampleClass, null));
433       }
434     }
435     catch (Exception   ex) {
436       throw new IllegalStateException  (ex.getMessage());
437     }
438 
439   }
440 
441   /**
442    * Compares this Genotype against the specified object. The result is true
443    * if the argument is an instance of the Genotype class, has exactly the
444    * same number of chromosomes as the given Genotype, and, for each
445    * Chromosome in this Genotype, there is an equal chromosome in the
446    * given Genotype. The chromosomes do not need to appear in the same order
447    * within the population.
448    *
449    * @param a_other the object to compare against
450    * @return true if the objects are the same, false otherwise
451    *
452    * @author Neil Rotstan
453    * @author Klaus Meffert
454    * @since 1.0
455    */
456   public boolean equals(Object   a_other) {
457     try {
458       // First, if the other Genotype is null, then they're not equal.
459       // -------------------------------------------------------------
460       if (a_other == null) {
461         return false;
462       }
463       Genotype otherGenotype = (Genotype) a_other;
464       // First, make sure the other Genotype has the same number of
465       // chromosomes as this one.
466       // ----------------------------------------------------------
467       if (getPopulation().size() != otherGenotype.getPopulation().size()) {
468         return false;
469       }
470       // Next, prepare to compare the chromosomes of the other Genotype
471       // against the chromosomes of this Genotype. To make this a lot
472       // simpler, we first sort the chromosomes in both this Genotype
473       // and the one we're comparing against. This won't affect the
474       // genetic algorithm (it doesn't care about the order), but makes
475       // it much easier to perform the comparison here.
476       // --------------------------------------------------------------
477       Collections.sort(getPopulation().getChromosomes());
478       Collections.sort(otherGenotype.getPopulation().getChromosomes());
479       for (int i = 0; i < getPopulation().size(); i++) {
480         if (! (getPopulation().getChromosome(i).equals(
481             otherGenotype.getPopulation().getChromosome(i)))) {
482           return false;
483         }
484       }
485       return true;
486     }
487     catch (ClassCastException   e) {
488       return false;
489     }
490   }
491 
492   /**
493    * Applies all NaturalSelectors registered with the Configuration.
494    *
495    * @param a_processBeforeGeneticOperators true apply NaturalSelectors
496    * applicable before GeneticOperators, false: apply the ones applicable
497    * after GeneticOperators
498    *
499    * @author Klaus Meffert
500    * @since 2.0
501    */
502   protected void applyNaturalSelectors(
503       boolean a_processBeforeGeneticOperators) {
504       /**@todo optionally use working pool*/
505     try {
506       // Process all natural selectors applicable before executing the
507       // genetic operators (reproduction, crossing over, mutation...).
508       // -------------------------------------------------------------
509       int selectorSize = m_activeConfiguration.getNaturalSelectorsSize(
510           a_processBeforeGeneticOperators);
511       if (selectorSize > 0) {
512         int m_population_size = m_activeConfiguration.getPopulationSize();
513         int m_single_selection_size;
514         Population m_new_population;
515         m_new_population = new Population(m_activeConfiguration,
516                                           m_population_size);
517         NaturalSelector selector;
518         // Repopulate the population of chromosomes with those selected
519         // by the natural selector. Iterate over all natural selectors.
520         // ------------------------------------------------------------
521         for (int i = 0; i < selectorSize; i++) {
522           selector = m_activeConfiguration.getNaturalSelector(
523               a_processBeforeGeneticOperators, i);
524           if (i == selectorSize - 1 && i > 0) {
525             // Ensure the last NaturalSelector adds the remaining Chromosomes.
526             // ---------------------------------------------------------------
527             m_single_selection_size = m_population_size - getPopulation().size();
528           }
529           else {
530             m_single_selection_size = m_population_size / selectorSize;
531           }
532           // Do selection of Chromosomes.
533           // ----------------------------
534           selector.select(m_single_selection_size, getPopulation(),
535                           m_new_population);
536           // Clean up the natural selector.
537           // ------------------------------
538           selector.empty();
539         }
540         setPopulation(new Population(m_activeConfiguration));
541         getPopulation().addChromosomes(m_new_population);
542       }
543     }
544     catch (InvalidConfigurationException iex) {
545       // This exception should never be reached
546       throw new IllegalStateException  (iex.getMessage());
547     }
548   }
549 
550   /**
551    * Applies all GeneticOperators registered with the Configuration.
552    *
553    * @author Klaus Meffert
554    * @since 3.0
555    */
556   public void applyGeneticOperators() {
557     List geneticOperators = m_activeConfiguration.getGeneticOperators();
558     Iterator operatorIterator = geneticOperators.iterator();
559     while (operatorIterator.hasNext()) {
560       GeneticOperator operator = (GeneticOperator) operatorIterator.next();
561       applyGeneticOperator(operator, getPopulation(),
562                            getPopulation().getChromosomes());
563 
564 //      List workingPool = new Vector();
565 //      applyGeneticOperator(operator, getPopulation(),
566 //                           workingPool);
567     }
568   }
569 
570   /**
571    * @return the configuration to use with the Genetic Algorithm
572    *
573    * @author Klaus Meffert
574    * @since 2.0 (?)
575    */
576   public static Configuration getStaticConfiguration() {
577     return m_staticConfiguration;
578   }
579 
580   /**
581    * Sets the configuration to use with the Genetic Algorithm.
582    * @param a_configuration the configuration to use
583    *
584    * @author Klaus Meffert
585    * @since 2.0 (?)
586    */
587   public static void setStaticConfiguration(Configuration a_configuration) {
588     m_staticConfiguration = a_configuration;
589   }
590 
591   public Configuration getConfiguration() {
592     return m_activeConfiguration;
593   }
594 
595   /***
596    * Hashcode function for the genotype, tries to create a unique hashcode for
597    * the chromosomes within the population. The logic for the hashcode is
598    *
599    * Step  Result
600    * ----  ------
601    *    1  31*0      + hashcode_0 = y(1)
602    *    2  31*y(1)   + hashcode_1 = y(2)
603    *    3  31*y(2)   + hashcode_2 = y(3)
604    *    n  31*y(n-1) + hashcode_n-1 = y(n)
605    *
606    * Each hashcode is a number and the binary equivalent is computed and
607    * returned.
608    *
609    * @return the computed hashcode
610    *
611    * @author vamsi
612    * @since 2.1
613    */
614   public int hashCode() {
615     int i, size = getPopulation().size();
616     IChromosome s;
617     int twopower = 1;
618     // For empty genotype we want a special value different from other hashcode
619     // implementations.
620     // ------------------------------------------------------------------------
621     int localHashCode = -573;
622     for (i = 0; i < size; i++, twopower = 2 * twopower) {
623       s = getPopulation().getChromosome(i);
624       localHashCode = 31 * localHashCode + s.hashCode();
625     }
626     return localHashCode;
627   }
628 
629   protected void setPopulation(Population a_pop) {
630     m_population = a_pop;
631   }
632 
633   /**
634    * Overwritable method that calls a GeneticOperator to operate on a given
635    * population and asks him to store the result in the list of chromosomes.
636    * Override this method if you want to ensure that a_chromosomes is not
637    * part of a_population resp. if you want to use a different list.
638    *
639    * @param a_operator the GeneticOperator to call
640    * @param a_population the population to use
641    * @param a_chromosomes the list of Chromosome objects to return
642    *
643    * @author Klaus Meffert
644    * @since 2.4
645    */
646   protected void applyGeneticOperator(GeneticOperator a_operator,
647                                       Population a_population,
648                                       List a_chromosomes) {
649     a_operator.operate(a_population, a_chromosomes);
650   }
651 
652   /**
653    * Cares that the population size does not exceed the given maximum size.
654    *
655    * @param a_pop the population to keep constant in size
656    * @param a_maxSize the maximum size allowed for the population
657    *
658    * @author Klaus Meffert
659    * @since 2.5
660    */
661   protected void keepPopSizeConstant(Population a_pop, int a_maxSize) {
662     int popSize = a_pop.size();
663     // See request  1213752.
664     // ---------------------
665     while (popSize > a_maxSize) {
666       // Remove a chromosome.
667       // --------------------
668       a_pop.removeChromosome(0);
669       popSize--;
670     }
671   }
672 
673   /**
674    * If used in a Thread: runs the evolution forever.
675    * You have to implement a listener to stop computation sometime. See
676    * examples.simpleBooleanThreaded for a possible implementation of such a
677    * listener.
678    *
679    * @author Klaus Meffert
680    * @since 3.01
681    */
682   public void run() {
683     while (!Thread.currentThread().interrupted()) {
684       evolve();
685     }
686   }
687 }
688
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags