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 org.jgap;
011:
012: import java.io.*;
013: import java.util.*;
014:
015: import org.jgap.distr.*;
016: import org.jgap.impl.job.*;
017:
018: /**
019: * Genotypes are fixed-length populations of chromosomes. As an instance of
020: * a Genotype is evolved, all of its Chromosomes are also evolved. A Genotype
021: * may be constructed normally via constructor, or the static
022: * randomInitialGenotype() method can be used to generate a Genotype with a
023: * randomized Chromosome population.
024: * <p>
025: * Please note that among all created Genotype instances there may only be one
026: * configuration, used by all Genotype instances.
027: *
028: * @author Neil Rotstan
029: * @author Klaus Meffert
030: * @since 1.0
031: */
032: public class Genotype implements Serializable, Runnable {
033: /** String containing the CVS revision. Read out via reflection!*/
034: private final static String CVS_REVISION = "$Revision: 1.103 $";
035:
036: /**
037: * The current Configuration instance.
038: * @since 1.0
039: */
040: private Configuration m_activeConfiguration;
041:
042: private transient static Configuration m_staticConfiguration;
043:
044: /**
045: * The array of Chromosomes that make-up the Genotype's population.
046: * @since 2.0
047: */
048: private Population m_population;
049:
050: /**
051: * Constructs a new Genotype instance with the given array of Chromosomes and
052: * the given active Configuration instance. Note that the Configuration object
053: * must be in a valid state when this method is invoked, or a
054: * InvalidConfigurationException will be thrown.
055: *
056: * @param a_configuration the Configuration object to use
057: * @param a_initialChromosomes the Chromosome population to be managed by
058: * this Genotype instance
059: * @throws InvalidConfigurationException if the given Configuration object is
060: * in an invalid state
061: *
062: * @author Neil Rotstan
063: * @author Klaus Meffert
064: * @since 1.0
065: * @deprecated use Genotype(Configuration, Population) instead
066: */
067: public Genotype(Configuration a_configuration,
068: IChromosome[] a_initialChromosomes)
069: throws InvalidConfigurationException {
070: this (a_configuration, new Population(a_configuration,
071: a_initialChromosomes));
072: }
073:
074: /**
075: * Constructs a new Genotype instance with the given array of
076: * Chromosomes and the given active Configuration instance. Note
077: * that the Configuration object must be in a valid state
078: * when this method is invoked, or a InvalidconfigurationException
079: * will be thrown.
080: *
081: * @param a_configuration the Configuration object to use
082: * @param a_population the Chromosome population to be managed by this
083: * Genotype instance
084: * @throws InvalidConfigurationException
085: *
086: * @author Neil Rotstan
087: * @author Klaus Meffert
088: * @since 2.0
089: */
090: public Genotype(Configuration a_configuration,
091: Population a_population)
092: throws InvalidConfigurationException {
093: // Sanity checks: Make sure neither the Configuration, nor the array
094: // of Chromosomes, nor any of the Genes inside the array is null.
095: // -----------------------------------------------------------------
096: if (a_configuration == null) {
097: throw new IllegalArgumentException(
098: "The Configuration instance may not be null.");
099: }
100: if (a_population == null) {
101: throw new IllegalArgumentException(
102: "The Population may not be null.");
103: }
104: for (int i = 0; i < a_population.size(); i++) {
105: if (a_population.getChromosome(i) == null) {
106: throw new IllegalArgumentException(
107: "The Chromosome instance at index "
108: + i
109: + " of the array of "
110: + "Chromosomes is null. No Chromosomes instance in this array "
111: + "may be null.");
112: }
113: }
114: m_population = a_population;
115: // Lock the settings of the configuration object so that it cannot
116: // be altered.
117: // ---------------------------------------------------------------
118: a_configuration.lockSettings();
119: m_activeConfiguration = a_configuration;
120: }
121:
122: /**
123: * Don't use this constructor, it's only for internal use.
124: *
125: * @param a_configuration not used here!
126: * @throws InvalidConfigurationException
127: *
128: * @author Klaus Meffert
129: * @since 3.0
130: */
131: public Genotype(Configuration a_configuration)
132: throws InvalidConfigurationException {
133: }
134:
135: /**
136: * Retrieves the array of Chromosomes that make up the population of this
137: * Genotype instance.
138: *
139: * @return the Population of Chromosomes
140: *
141: * @author Neil Rotstan
142: * @author Klaus Meffert
143: * @since 1.0
144: * @deprecated uses getPopulation() instead
145: */
146: public synchronized IChromosome[] getChromosomes() {
147: Iterator it = getPopulation().iterator();
148: IChromosome[] result = new Chromosome[getPopulation().size()];
149: int i = 0;
150: while (it.hasNext()) {
151: result[i++] = (IChromosome) it.next();
152: }
153: return result;
154: }
155:
156: /**
157: * @return the current population of chromosomes
158: *
159: * @author Klaus Meffert
160: * @since 2.1
161: */
162: public Population getPopulation() {
163: return m_population;
164: }
165:
166: /**
167: * Retrieves the Chromosome in the Population with the highest fitness
168: * value.
169: *
170: * @return the Chromosome with the highest fitness value, or null if there
171: * are no chromosomes in this Genotype
172: *
173: * @author Neil Rotstan
174: * @author Klaus Meffert
175: * @since 1.0
176: */
177: public synchronized IChromosome getFittestChromosome() {
178: return getPopulation().determineFittestChromosome();
179: }
180:
181: /**
182: * Retrieves the Chromosome in the Population with the highest fitness
183: * value within the given indices.
184: *
185: * @param a_startIndex the index to start the determination with
186: * @param a_endIndex the index to end the determination with
187: * @return the Chromosome with the highest fitness value within the given
188: * indices, or null if there are no chromosomes in this Genotype
189: *
190: * @author Klaus Meffert
191: * @since 3.0
192: */
193: public synchronized IChromosome getFittestChromosome(
194: int a_startIndex, int a_endIndex) {
195: return getPopulation().determineFittestChromosome(a_startIndex,
196: a_endIndex);
197: }
198:
199: /**
200: * Retrieves the top n Chromsomes in the population (the ones with the best
201: * fitness values).
202: *
203: * @param a_numberOfChromosomes the number of chromosomes desired
204: * @return the list of Chromosomes with the highest fitness values, or null
205: * if there are no chromosomes in this Genotype
206: *
207: * @author Charles Kevin Hill
208: * @since 2.4
209: */
210: public synchronized List getFittestChromosomes(
211: int a_numberOfChromosomes) {
212: return getPopulation().determineFittestChromosomes(
213: a_numberOfChromosomes);
214: }
215:
216: /**
217: * Evolves the population of Chromosomes within this Genotype. This will
218: * execute all of the genetic operators added to the present active
219: * configuration and then invoke the natural selector to choose which
220: * chromosomes will be included in the next generation population. Note
221: * that the population size not always remains constant (dependent on the
222: * NaturalSelectors used!).
223: * To consecutively call this method, use evolve(int)!!!
224: *
225: * @author Neil Rotstan
226: * @author Klaus Meffert
227: * @since 1.0
228: */
229: public synchronized void evolve() {
230: IBreeder breeder = getConfiguration().getBreeder();
231: Population newPop = breeder.evolve(getPopulation(),
232: getConfiguration());
233: setPopulation(newPop);
234: }
235:
236: /**
237: * Evolves this Genotype the specified number of times. This is
238: * equivalent to invoking the standard evolve() method the given number
239: * of times in a row.
240: *
241: * @param a_numberOfEvolutions the number of times to evolve this Genotype
242: * before returning
243: *
244: * @author Klaus Meffert
245: * @since 1.1
246: */
247: public void evolve(int a_numberOfEvolutions) {
248: for (int i = 0; i < a_numberOfEvolutions; i++) {
249: evolve();
250: }
251: if (m_activeConfiguration.isKeepPopulationSizeConstant()) {
252: keepPopSizeConstant(getPopulation(), m_activeConfiguration
253: .getPopulationSize());
254: }
255: }
256:
257: /**
258: * @return string representation of this Genotype instance, useful for display
259: * purposes
260: *
261: * @author Neil Rotstan
262: * @since 1.0
263: */
264: public String toString() {
265: StringBuffer buffer = new StringBuffer();
266: for (int i = 0; i < getPopulation().size(); i++) {
267: buffer.append(getPopulation().getChromosome(i).toString());
268: buffer.append(" [");
269: buffer.append(getPopulation().getChromosome(i)
270: .getFitnessValueDirectly());
271: buffer.append("]\n");
272: }
273: return buffer.toString();
274: }
275:
276: /**
277: * Convenience method that returns a newly constructed Genotype
278: * instance configured according to the given Configuration instance.
279: * The population of Chromosomes will be created according to the setup of
280: * the sample Chromosome in the Configuration object, but the gene values
281: * (alleles) will be set to random legal values.
282: *
283: * @param a_configuration the current active Configuration object
284: * @return a newly constructed Genotype instance
285: *
286: * @throws IllegalArgumentException if the given Configuration object is null
287: * @throws InvalidConfigurationException if the given Configuration
288: * instance is not in a valid state
289: *
290: * @author Neil Rotstan
291: * @author Klaus Meffert
292: * @since 2.3
293: */
294: public static Genotype randomInitialGenotype(
295: Configuration a_configuration)
296: throws InvalidConfigurationException {
297: if (a_configuration == null) {
298: throw new IllegalArgumentException(
299: "The Configuration instance may not be null.");
300: }
301: a_configuration.lockSettings();
302: // Create an array of chromosomes equal to the desired size in the
303: // active Configuration and then populate that array with Chromosome
304: // instances constructed according to the setup in the sample
305: // Chromosome, but with random gene values (alleles). The Chromosome
306: // class randomInitialChromosome() method will take care of that for
307: // us.
308: // ------------------------------------------------------------------
309: int populationSize = a_configuration.getPopulationSize();
310: Population pop = new Population(a_configuration, populationSize);
311: // Do randomized initialization.
312: // -----------------------------
313: Genotype result = new Genotype(a_configuration, pop);
314: result.fillPopulation(populationSize);
315: return result;
316: }
317:
318: /**
319: * Fills up the population with random chromosomes if necessary.
320: *
321: * @param a_num the number of chromosomes to add
322: * @throws InvalidConfigurationException
323: *
324: * @author Klaus Meffert
325: * @since 3.2
326: */
327: public void fillPopulation(final int a_num)
328: throws InvalidConfigurationException {
329: IChromosome sampleChrom = getConfiguration()
330: .getSampleChromosome();
331: Class sampleClass = sampleChrom.getClass();
332: IInitializer chromIniter = getConfiguration().getJGAPFactory()
333: .getInitializerFor(sampleChrom, sampleClass);
334: if (chromIniter == null) {
335: throw new InvalidConfigurationException(
336: "No initializer found for class " + sampleClass);
337: }
338: try {
339: for (int i = 0; i < a_num; i++) {
340: getPopulation().addChromosome(
341: (IChromosome) chromIniter.perform(sampleChrom,
342: sampleClass, null));
343: }
344: } catch (Exception ex) {
345: // Try to propagate exception, see "bug" 1661635.
346: // ----------------------------------------------
347: if (ex.getCause() != null) {
348: throw new IllegalStateException(ex.getCause()
349: .toString());
350: } else {
351: throw new IllegalStateException(ex.getMessage());
352: }
353: }
354: }
355:
356: /**
357: * Compares this Genotype against the specified object. The result is true
358: * if the argument is an instance of the Genotype class, has exactly the
359: * same number of chromosomes as the given Genotype, and, for each
360: * Chromosome in this Genotype, there is an equal chromosome in the
361: * given Genotype. The chromosomes do not need to appear in the same order
362: * within the population.
363: *
364: * @param a_other the object to compare against
365: * @return true if the objects are the same, false otherwise
366: *
367: * @author Neil Rotstan
368: * @author Klaus Meffert
369: * @since 1.0
370: */
371: public boolean equals(Object a_other) {
372: try {
373: // First, if the other Genotype is null, then they're not equal.
374: // -------------------------------------------------------------
375: if (a_other == null) {
376: return false;
377: }
378: Genotype otherGenotype = (Genotype) a_other;
379: // First, make sure the other Genotype has the same number of
380: // chromosomes as this one.
381: // ----------------------------------------------------------
382: if (getPopulation().size() != otherGenotype.getPopulation()
383: .size()) {
384: return false;
385: }
386: // Next, prepare to compare the chromosomes of the other Genotype
387: // against the chromosomes of this Genotype. To make this a lot
388: // simpler, we first sort the chromosomes in both this Genotype
389: // and the one we're comparing against. This won't affect the
390: // genetic algorithm (it doesn't care about the order), but makes
391: // it much easier to perform the comparison here.
392: // --------------------------------------------------------------
393: Collections.sort(getPopulation().getChromosomes());
394: Collections.sort(otherGenotype.getPopulation()
395: .getChromosomes());
396: for (int i = 0; i < getPopulation().size(); i++) {
397: if (!(getPopulation().getChromosome(i)
398: .equals(otherGenotype.getPopulation()
399: .getChromosome(i)))) {
400: return false;
401: }
402: }
403: return true;
404: } catch (ClassCastException e) {
405: return false;
406: }
407: }
408:
409: /**
410: * Applies all NaturalSelectors registered with the Configuration.
411: *
412: * @param a_processBeforeGeneticOperators true apply NaturalSelectors
413: * applicable before GeneticOperators, false: apply the ones applicable
414: * after GeneticOperators
415: *
416: * @author Klaus Meffert
417: * @since 2.0
418: */
419: protected void applyNaturalSelectors(
420: boolean a_processBeforeGeneticOperators) {
421: /**@todo optionally use working pool*/
422: try {
423: // Process all natural selectors applicable before executing the
424: // genetic operators (reproduction, crossing over, mutation...).
425: // -------------------------------------------------------------
426: int selectorSize = m_activeConfiguration
427: .getNaturalSelectorsSize(a_processBeforeGeneticOperators);
428: if (selectorSize > 0) {
429: int population_size = m_activeConfiguration
430: .getPopulationSize();
431: if (a_processBeforeGeneticOperators) {
432: // Only select part of the previous population into this generation.
433: // -----------------------------------------------------------------
434: population_size = (int) Math
435: .round(population_size
436: * getConfiguration()
437: .getSelectFromPrevGen());
438: }
439: int single_selection_size;
440: Population new_population;
441: new_population = new Population(m_activeConfiguration,
442: population_size);
443: NaturalSelector selector;
444: // Repopulate the population of chromosomes with those selected
445: // by the natural selector. Iterate over all natural selectors.
446: // ------------------------------------------------------------
447: for (int i = 0; i < selectorSize; i++) {
448: selector = m_activeConfiguration
449: .getNaturalSelector(
450: a_processBeforeGeneticOperators, i);
451: if (i == selectorSize - 1 && i > 0) {
452: // Ensure the last NaturalSelector adds the remaining Chromosomes.
453: // ---------------------------------------------------------------
454: single_selection_size = population_size
455: - getPopulation().size();
456: } else {
457: single_selection_size = population_size
458: / selectorSize;
459: }
460: // Do selection of Chromosomes.
461: // ----------------------------
462: selector.select(single_selection_size,
463: getPopulation(), new_population);
464: // Clean up the natural selector.
465: // ------------------------------
466: selector.empty();
467: }
468: setPopulation(new Population(m_activeConfiguration));
469: getPopulation().addChromosomes(new_population);
470: }
471: } catch (InvalidConfigurationException iex) {
472: // This exception should never be reached
473: throw new IllegalStateException(iex.getMessage());
474: }
475: }
476:
477: /**
478: * Applies all GeneticOperators registered with the Configuration.
479: *
480: * @author Klaus Meffert
481: * @since 3.0
482: */
483: public void applyGeneticOperators() {
484: List geneticOperators = m_activeConfiguration
485: .getGeneticOperators();
486: Iterator operatorIterator = geneticOperators.iterator();
487: while (operatorIterator.hasNext()) {
488: GeneticOperator operator = (GeneticOperator) operatorIterator
489: .next();
490: applyGeneticOperator(operator, getPopulation(),
491: getPopulation().getChromosomes());
492: // List workingPool = new Vector();
493: // applyGeneticOperator(operator, getPopulation(),
494: // workingPool);
495: }
496: }
497:
498: /**
499: * @return the configuration to use with the Genetic Algorithm
500: *
501: * @author Klaus Meffert
502: * @since 2.0
503: */
504: public static Configuration getStaticConfiguration() {
505: return m_staticConfiguration;
506: }
507:
508: /**
509: * Sets the configuration to use with the Genetic Algorithm.
510: * @param a_configuration the configuration to use
511: *
512: * @author Klaus Meffert
513: * @since 2.0
514: */
515: public static void setStaticConfiguration(
516: Configuration a_configuration) {
517: m_staticConfiguration = a_configuration;
518: }
519:
520: public Configuration getConfiguration() {
521: return m_activeConfiguration;
522: }
523:
524: /***
525: * Hashcode function for the genotype, tries to create a unique hashcode for
526: * the chromosomes within the population. The logic for the hashcode is
527: *
528: * Step Result
529: * ---- ------
530: * 1 31*0 + hashcode_0 = y(1)
531: * 2 31*y(1) + hashcode_1 = y(2)
532: * 3 31*y(2) + hashcode_2 = y(3)
533: * n 31*y(n-1) + hashcode_n-1 = y(n)
534: *
535: * Each hashcode is a number and the binary equivalent is computed and
536: * returned.
537: *
538: * @return the computed hashcode
539: *
540: * @author vamsi
541: * @since 2.1
542: */
543: public int hashCode() {
544: int i, size = getPopulation().size();
545: IChromosome s;
546: int twopower = 1;
547: // For empty genotype we want a special value different from other hashcode
548: // implementations.
549: // ------------------------------------------------------------------------
550: int localHashCode = -573;
551: for (i = 0; i < size; i++, twopower = 2 * twopower) {
552: s = getPopulation().getChromosome(i);
553: localHashCode = 31 * localHashCode + s.hashCode();
554: }
555: return localHashCode;
556: }
557:
558: protected void setPopulation(Population a_pop) {
559: m_population = a_pop;
560: }
561:
562: /**
563: * Overwritable method that calls a GeneticOperator to operate on a given
564: * population and asks him to store the result in the list of chromosomes.
565: * Override this method if you want to ensure that a_chromosomes is not
566: * part of a_population resp. if you want to use a different list.
567: *
568: * @param a_operator the GeneticOperator to call
569: * @param a_population the population to use
570: * @param a_chromosomes the list of Chromosome objects to return
571: *
572: * @author Klaus Meffert
573: * @since 2.4
574: */
575: protected void applyGeneticOperator(GeneticOperator a_operator,
576: Population a_population, List a_chromosomes) {
577: a_operator.operate(a_population, a_chromosomes);
578: }
579:
580: /**
581: * Cares that the population size does not exceed the given maximum size.
582: *
583: * @param a_pop the population to keep constant in size
584: * @param a_maxSize the maximum size allowed for the population
585: *
586: * @author Klaus Meffert
587: * @since 2.5
588: */
589: protected void keepPopSizeConstant(Population a_pop, int a_maxSize) {
590: /**@todo use StandardPostSelector instead?*/
591: int popSize = a_pop.size();
592: // See request 1213752.
593: // ---------------------
594: while (popSize > a_maxSize) {
595: // Remove a chromosome.
596: // --------------------
597: a_pop.removeChromosome(0);
598: popSize--;
599: }
600: }
601:
602: /**
603: * If used in a Thread: runs the evolution forever.
604: * You have to implement a listener to stop computation sometime. See
605: * examples.simpleBooleanThreaded for a possible implementation of such a
606: * listener.
607: *
608: * @author Klaus Meffert
609: * @since 3.01
610: */
611: public void run() {
612: while (!Thread.currentThread().interrupted()) {
613: evolve();
614: }
615: }
616:
617: public List getEvolves(IPopulationSplitter a_splitter)
618: throws Exception {
619: // We return a list of IEvolveJob instances.
620: // -----------------------------------------
621: List result = new Vector();
622: Population[] pops = a_splitter.split(getPopulation());
623: // Feed the population chunks into different evolve jobs.
624: // ------------------------------------------------------
625: for (int i = 0; i < pops.length; i++) {
626: Configuration newConf = (Configuration) getConfiguration()
627: .clone();
628: EvolveData data = new EvolveData(newConf);
629: if (pops[i] == null) {
630: throw new IllegalStateException(
631: "Population must no be null" + " (Index: " + i
632: + ", Splitter: "
633: + a_splitter.getClass().getName() + ")");
634: }
635: data.setPopulation(pops[i]);
636: data.setBreeder(newConf.getBreeder());
637: IEvolveJob evolver = new EvolveJob(data);
638: result.add(evolver);
639: }
640: getPopulation().clear();
641: return result;
642: }
643:
644: public void mergeResults(IPopulationMerger a_merger,
645: EvolveResult[] a_results) throws Exception {
646: int size = a_results.length;
647: Population target = new Population(getConfiguration());
648: for (int i = 0; i < size; i++) {
649: EvolveResult singleResult = a_results[i];
650: if (singleResult == null) {
651: throw new IllegalStateException(
652: "Single result is null!");
653: }
654: Population pop = singleResult.getPopulation();
655: /**@todo use/enhance IPopulationMerger*/
656: // a_merger.mergePopulations()
657: List goodOnes = pop.determineFittestChromosomes(3);
658: for (int j = 0; j < goodOnes.size(); j++) {
659: IChromosome goodOne = (IChromosome) goodOnes.get(j);
660: target.addChromosome(goodOne);
661: }
662: }
663: setPopulation(target);
664: }
665: }
|