GeneticAlgorithm.java
0001 /*
0002  * Java Genetic Algorithm Library (jenetics-2.0.2).
0003  * Copyright (c) 2007-2014 Franz Wilhelmstötter
0004  *
0005  * Licensed under the Apache License, Version 2.0 (the "License");
0006  * you may not use this file except in compliance with the License.
0007  * You may obtain a copy of the License at
0008  *
0009  *      http://www.apache.org/licenses/LICENSE-2.0
0010  *
0011  * Unless required by applicable law or agreed to in writing, software
0012  * distributed under the License is distributed on an "AS IS" BASIS,
0013  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0014  * See the License for the specific language governing permissions and
0015  * limitations under the License.
0016  *
0017  * Author:
0018  *    Franz Wilhelmstötter (franz.wilhelmstoetter@gmx.at)
0019  */
0020 package org.jenetics;
0021 
0022 import static java.lang.Math.round;
0023 import static java.lang.String.format;
0024 import static java.util.Objects.requireNonNull;
0025 import static org.jenetics.internal.util.object.NonNull;
0026 import static org.jenetics.internal.util.object.checkProbability;
0027 import static org.jenetics.util.arrays.forEach;
0028 
0029 import java.util.Collection;
0030 import java.util.concurrent.Executor;
0031 import java.util.concurrent.atomic.AtomicInteger;
0032 import java.util.concurrent.locks.Lock;
0033 import java.util.concurrent.locks.ReentrantLock;
0034 
0035 import org.jenetics.internal.util.Concurrency;
0036 
0037 import org.jenetics.util.Array;
0038 import org.jenetics.util.Factory;
0039 import org.jenetics.util.Function;
0040 import org.jenetics.util.Timer;
0041 import org.jenetics.util.functions;
0042 
0043 /**
0044  <h3>Getting started</h3>
0045  *
0046  * The minimum GA setup needs a genotype factory, {@code Factory<Genotype<?>>},
0047  * and a fitness {@link Function}. The {@link Genotype} implements the
0048  {@link Factory} interface and can therefore be used as prototype for creating
0049  * the initial Population and for creating new random Genotypes.
0050  *
0051  * [code]
0052  * public static void main(final String[] args) {
0053  *     final Factory&lt;Genotype&lt;BitGene&gt;&gt; gtf = Genotype.of(
0054  *         BitChromosome.of(10, 0.5)
0055  *     );
0056  *     final Function&lt;Genotype&lt;BitGene&gt; Double&gt; ff = ...
0057  *     final GeneticAlgorithm&lt;BitGene, Double&gt;
0058  *     ga = new GeneticAlgorithm&lt;&gt;(gtf, ff, Optimize.MAXIMUM);
0059  *
0060  *     ga.setup();
0061  *     ga.evolve(100);
0062  *     System.out.println(ga.getBestPhenotype());
0063  * }
0064  * [/code]
0065  *
0066  <p>
0067  * The genotype factory, {@code gtf}, in the example above will create genotypes
0068  * which consists of one {@link BitChromosome} with length 10. The one to zero
0069  * probability of the newly created genotypes is set to 0.5. The fitness function
0070  * is parametrized with a {@link BitGene} and a {@link Double}. That means
0071  * that the fitness function is calculating the fitness value as {@link Double}.
0072  * The return type of the fitness function must be at least a {@link Comparable}.
0073  * The {@code GeneticAlgorithm} object is then created with the genotype factory
0074  * and the fitness function. In this example the GA tries to maximize the fitness
0075  * function. If you want to find the minimal value you have to change the optimize
0076  * parameter from {@code Optimize.MAXIMUM} to {@code Optimize.MINIMUM}. The
0077  * {@code ga.setup()} call creates the initial population and calculates its
0078  * fitness value. Then the GA evolves 100 generations ({@code ga.evolve(100)})
0079  * an prints the best phenotype found so far onto the console.
0080  </p>
0081  * In a more advanced setup you may want to change the default mutation and/or
0082  * selection strategies.
0083  *
0084  * [code]
0085  * public static void main(final String[] args) {
0086  *     ...
0087  *     ga.setSelectors(new RouletteWheelSelector&lt;BitGene&gt;());
0088  *     ga.setAlterers(
0089  *         new SinglePointCrossover&lt;BitGene&gt;(0.1),
0090  *         new Mutator&lt;BitGene&gt;(0.01)
0091  *     );
0092  *
0093  *     ga.setup();
0094  *     ga.evolve(100);
0095  *     System.out.println(ga.getBestPhenotype());
0096  * }
0097  * [/code]
0098  *
0099  * The selection strategy for offspring and survivors are set to the
0100  * roulette-wheel selector. It is also possible to set the selector for
0101  * offspring and survivors independently with the {@code setOffspringSelector}
0102  * and {@code setSurvivorSelector} methods. The alterers are concatenated, at
0103  * first the crossover (with probability 0.1) is performed and then the
0104  * chromosomes are mutated (with probability 0.01).
0105  *
0106  <h3>Serialization</h3>
0107  *
0108  * With the serialization mechanism you can write a population to disk and load
0109  * it into an GA at a later time. It can also be used to transfer populations to
0110  * GAs, running on different hosts, over a network link. The IO class, located
0111  * in the {@code org.jenetics.util} package, supports native Java serialization
0112  * and XML serialization. For XML marshaling <em>Jenetics</em> internally uses
0113  * the XML support from the Javolution project.
0114  *
0115  * [code]
0116  * // Writing the population to disk.
0117  * final File file = new File("population.xml");
0118  * IO.jaxb.write(ga.getPopulation(), file);
0119  *
0120  * // Reading the population from disk.
0121  * Population&lt;DoubleGene, Double&gt; population =
0122  *     (Population&lt;DoubleGene, Double&gt;)IO.jaxb.read(file);
0123  * ga.setPopulation(population);
0124  * [/code]
0125  *
0126  @see <a href="http://en.wikipedia.org/wiki/Genetic_algorithm">
0127  *          Wikipedia: Genetic algorithm
0128  *      </a>
0129  @see Alterer
0130  @see Selector
0131  *
0132  @param <G> The gene type this GA evaluates,
0133  @param <C> The result type (of the fitness function).
0134  *
0135  @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
0136  @since 1.0
0137  @version 2.0 &mdash; <em>$Date: 2014-04-12 $</em>
0138  */
0139 public class GeneticAlgorithm<
0140     extends Gene<?, G>,
0141     extends Comparable<? super C>
0142 >
0143 {
0144 
0145     /**
0146      * The default population size used by this GA.
0147      */
0148     public static final int DEFAULT_POPULATION_SIZE = 50;
0149 
0150     /**
0151      * The default maximal phenotype age of this GA:
0152      */
0153     public static final int DEFAULT_MAXIMAL_PHENOTYPE_AGE = 70;
0154 
0155     /**
0156      * The default offspring fraction used by this GA.
0157      */
0158     public static final double DEFAULT_OFFSPRING_FRACTION = 0.6;
0159 
0160 
0161     private final Lock _lock = new ReentrantLock(true);
0162 
0163     private final Optimize _optimization;
0164     private final Executor _executor;
0165 
0166     private final Factory<Genotype<G>> _genotypeFactory;
0167     private final Factory<Phenotype<G, C>> _phenotypeFactory;
0168     private final Function<? super Genotype<G>, ? extends C> _fitnessFunction;
0169     private Function<? super C, ? extends C> _fitnessScaler;
0170 
0171     private double _offspringFraction = DEFAULT_OFFSPRING_FRACTION;
0172 
0173     // Alterers
0174     private Alterer<G> _alterer = CompositeAlterer.of(
0175         new SinglePointCrossover<G>(0.1),
0176         new Mutator<G>(0.05)
0177     );
0178 
0179     // Selectors
0180     private Selector<G, C> _survivorSelector = new TournamentSelector<>(3);
0181     private Selector<G, C> _offspringSelector = new TournamentSelector<>(3);
0182 
0183     // Population
0184     private int _populationSize = DEFAULT_POPULATION_SIZE;
0185     private Population<G, C> _population = new Population<>(_populationSize);
0186     private int _maximalPhenotypeAge = DEFAULT_MAXIMAL_PHENOTYPE_AGE;
0187     private volatile int _generation = 0;
0188 
0189     // Statistics
0190     private Statistics.Calculator<G, C> _calculator = new Statistics.Calculator<>();
0191     private Statistics<G, C> _bestStatistics = null;
0192     private Statistics<G, C> _statistics = null;
0193     private final AtomicInteger _killed = new AtomicInteger(0);
0194     private final AtomicInteger _invalid = new AtomicInteger(0);
0195 
0196     //Some performance measure.
0197     private final Timer _executionTimer = new Timer("Execution time");
0198     private final Timer _selectTimer = new Timer("Select time");
0199     private final Timer _alterTimer = new Timer("Alter time");
0200     private final Timer _combineTimer = new Timer("Combine survivors and offspring time");
0201     private final Timer _statisticTimer = new Timer("Statistic time");
0202     private final Timer _evaluateTimer = new Timer("Evaluate time");
0203 
0204 
0205     /**
0206      * Create a new genetic algorithm.
0207      *
0208      @param genotypeFactory the genotype factory this GA is working with.
0209      @param fitnessFunction the fitness function this GA is using.
0210      @param fitnessScaler the fitness scaler this GA is using.
0211      @param optimization Determine whether this GA maximize or minimize the
0212      *        fitness function.
0213      @param executor the {@link java.util.concurrent.Executor} used for
0214      *        executing the parallelizable parts of the code.
0215      @throws NullPointerException if one of the arguments is {@code null}.
0216      */
0217     public GeneticAlgorithm(
0218         final Factory<Genotype<G>> genotypeFactory,
0219         final Function<? super Genotype<G>, ? extends C> fitnessFunction,
0220         final Function<? super C, ? extends C> fitnessScaler,
0221         final Optimize optimization,
0222         final Executor executor
0223     ) {
0224         _genotypeFactory = requireNonNull(genotypeFactory, "GenotypeFactory");
0225         _fitnessFunction = requireNonNull(fitnessFunction, "FitnessFunction");
0226         _fitnessScaler = requireNonNull(fitnessScaler, "FitnessScaler");
0227         _optimization = requireNonNull(optimization, "Optimization");
0228         _executor = requireNonNull(executor, "Executor");
0229 
0230         _phenotypeFactory = new Factory<Phenotype<G, C>>() {
0231             @Override public Phenotype<G, C> newInstance() {
0232                 return Phenotype.of(
0233                     _genotypeFactory.newInstance(),
0234                     _fitnessFunction,
0235                     _fitnessScaler,
0236                     _generation
0237                 );
0238             }
0239         };
0240     }
0241 
0242     /**
0243      * Create a new genetic algorithm.
0244      *
0245      @param genotypeFactory the genotype factory this GA is working with.
0246      @param fitnessFunction the fitness function this GA is using.
0247      @param fitnessScaler the fitness scaler this GA is using.
0248      @param optimization Determine whether this GA maximize or minimize the
0249      *        fitness function.
0250      @throws NullPointerException if one of the arguments is {@code null}.
0251      */
0252     public GeneticAlgorithm(
0253         final Factory<Genotype<G>> genotypeFactory,
0254         final Function<? super Genotype<G>, ? extends C> fitnessFunction,
0255         final Function<? super C, ? extends C> fitnessScaler,
0256         final Optimize optimization
0257     ) {
0258         this(
0259             genotypeFactory,
0260             fitnessFunction,
0261             fitnessScaler,
0262             optimization,
0263             Concurrency.commonPool()
0264         );
0265     }
0266 
0267     /**
0268      * Create a new genetic algorithm.
0269      *
0270      @param genotypeFactory the genotype factory this GA is working with.
0271      @param fitnessFunction the fitness function this GA is using.
0272      @param optimization Determine whether this GA maximize or minimize the
0273      *        fitness function.
0274      @param executor the {@link java.util.concurrent.Executor} used for
0275      *        executing the parallelizable parts of the code.
0276      @throws NullPointerException if one of the arguments is {@code null}.
0277      */
0278     public GeneticAlgorithm(
0279         final Factory<Genotype<G>> genotypeFactory,
0280         final Function<? super Genotype<G>, ? extends C> fitnessFunction,
0281         final Optimize optimization,
0282         final Executor executor
0283     ) {
0284         this(
0285             genotypeFactory,
0286             fitnessFunction,
0287             functions.<C>Identity(),
0288             optimization,
0289             executor
0290         );
0291     }
0292 
0293     /**
0294      * Create a new genetic algorithm.
0295      *
0296      @param genotypeFactory the genotype factory this GA is working with.
0297      @param fitnessFunction the fitness function this GA is using.
0298      @param optimization Determine whether this GA maximize or minimize the
0299      *        fitness function.
0300      @throws NullPointerException if one of the arguments is {@code null}.
0301      */
0302     public GeneticAlgorithm(
0303         final Factory<Genotype<G>> genotypeFactory,
0304         final Function<? super Genotype<G>, ? extends C> fitnessFunction,
0305         final Optimize optimization
0306     ) {
0307         this(
0308             genotypeFactory,
0309             fitnessFunction,
0310             functions.<C>Identity(),
0311             optimization,
0312             Concurrency.commonPool()
0313         );
0314     }
0315 
0316     /**
0317      * Create a new genetic algorithm. By default the GA tries to maximize the
0318      * fitness function.
0319      *
0320      @param genotypeFactory the genotype factory this GA is working with.
0321      @param fitnessFunction the fitness function this GA is using.
0322      @param executor the {@link java.util.concurrent.Executor} used for
0323      *        executing the parallelizable parts of the code.
0324      @throws NullPointerException if one of the arguments is {@code null}.
0325      */
0326     public GeneticAlgorithm(
0327         final Factory<Genotype<G>> genotypeFactory,
0328         final Function<? super Genotype<G>, ? extends C> fitnessFunction,
0329         final Executor executor
0330     ) {
0331         this(
0332             genotypeFactory,
0333             fitnessFunction,
0334             functions.<C>Identity(),
0335             Optimize.MAXIMUM,
0336             executor
0337         );
0338     }
0339 
0340     /**
0341      * Create a new genetic algorithm. By default the GA tries to maximize the
0342      * fitness function.
0343      *
0344      @param genotypeFactory the genotype factory this GA is working with.
0345      @param fitnessFunction the fitness function this GA is using.
0346      @throws NullPointerException if one of the arguments is {@code null}.
0347      */
0348     public GeneticAlgorithm(
0349         final Factory<Genotype<G>> genotypeFactory,
0350         final Function<? super Genotype<G>, ? extends C> fitnessFunction
0351     ) {
0352         this(
0353             genotypeFactory,
0354             fitnessFunction,
0355             functions.<C>Identity(),
0356             Optimize.MAXIMUM,
0357             Concurrency.commonPool()
0358         );
0359     }
0360 
0361     /**
0362      * Create a new genetic algorithm. By default the GA tries to maximize the
0363      * fitness function.
0364      *
0365      @param genotypeFactory the genotype factory this GA is working with.
0366      @param fitnessFunction the fitness function this GA is using.
0367      @param fitnessScaler the fitness scaler this GA is using.
0368      @param executor the {@link java.util.concurrent.Executor} used for
0369      *        executing the parallelizable parts of the code.
0370      @throws NullPointerException if one of the arguments is {@code null}.
0371      */
0372     public GeneticAlgorithm(
0373         final Factory<Genotype<G>> genotypeFactory,
0374         final Function<? super Genotype<G>, ? extends C> fitnessFunction,
0375         final Function<? super C, ? extends C> fitnessScaler,
0376         final Executor executor
0377     ) {
0378         this(
0379             genotypeFactory,
0380             fitnessFunction,
0381             fitnessScaler,
0382             Optimize.MAXIMUM,
0383             executor
0384         );
0385     }
0386 
0387     /**
0388      * Create a new genetic algorithm. By default the GA tries to maximize the
0389      * fitness function.
0390      *
0391      @param genotypeFactory the genotype factory this GA is working with.
0392      @param fitnessFunction the fitness function this GA is using.
0393      @param fitnessScaler the fitness scaler this GA is using.
0394      @throws NullPointerException if one of the arguments is {@code null}.
0395      */
0396     public GeneticAlgorithm(
0397         final Factory<Genotype<G>> genotypeFactory,
0398         final Function<? super Genotype<G>, ? extends C> fitnessFunction,
0399         final Function<? super C, ? extends C> fitnessScaler
0400     ) {
0401         this(
0402             genotypeFactory,
0403             fitnessFunction,
0404             fitnessScaler,
0405             Optimize.MAXIMUM,
0406             null
0407         );
0408     }
0409 
0410     /**
0411      * Create the initial population of the GA. Subsequent calls to this
0412      * method throw IllegalStateException. If no initial population has been
0413      * set (with {@link #setPopulation(Collection)} or
0414      {@link #setGenotypes(Collection)}) a random population is generated.
0415      *
0416      @throws IllegalStateException if called more than once.
0417      */
0418     public void setup() {
0419         _lock.lock();
0420         try {
0421             prepareSetup();
0422             _population.fill(
0423                 _phenotypeFactory,
0424                 _populationSize - _population.size()
0425             );
0426             finishSetup();
0427         finally {
0428             _lock.unlock();
0429         }
0430     }
0431 
0432     /**
0433      * Setting up the {@code GeneticAlgorithm} with the given initial
0434      * population. Subsequent calls to this method throw an IllegalStateException.
0435      * This method is similar to the {@link #setGenotypes(Collection)} and
0436      {@link #setPopulation(Collection)} methods, but this method is required
0437      * to be called only once and before starting evaluation. It also calculates
0438      * the timing statistics when (calculating the fitness values for the given
0439      * genotypes.
0440      *
0441      @see #setGenotypes(Collection)
0442      @see #setPopulation(Collection)
0443      @param genotypes the initial population.
0444      @throws IllegalStateException if called more than once.
0445      */
0446     public void setup(final Collection<Genotype<G>> genotypes) {
0447         _lock.lock();
0448         try {
0449             prepareSetup();
0450             setGenotypes(genotypes);
0451             finishSetup();
0452         finally {
0453             _lock.unlock();
0454         }
0455     }
0456 
0457     private void prepareSetup() {
0458         if (_generation > 0) {
0459             throw new IllegalStateException(
0460                 "The method GeneticAlgorithm.setup() must be called only once."
0461             );
0462         }
0463 
0464         ++_generation;
0465         _executionTimer.start();
0466     }
0467 
0468     private void finishSetup() {
0469         //Evaluate the fitness.
0470         evaluate();
0471 
0472         //First valuation of the initial population.
0473         _statisticTimer.start();
0474         _statistics = _calculator.evaluate(
0475             _executor, _population, _generation, _optimization
0476         ).build();
0477 
0478         _bestStatistics = _statistics;
0479         _statisticTimer.stop();
0480 
0481         _executionTimer.stop();
0482 
0483         setTimes(_statistics);
0484     }
0485 
0486     /**
0487      * Evolve one generation.
0488      *
0489      @throws IllegalStateException if the {@link GeneticAlgorithm#setup()}
0490      *         method was not called first.
0491      */
0492     public void evolve() {
0493         _lock.lock();
0494         try {
0495             // Check the setup state.
0496             if (_generation == 0) {
0497                 throw new IllegalStateException(
0498                     "Call the GeneticAlgorithm.setup() method before " +
0499                     "calling GeneticAlgorithm.evolve()."
0500                 );
0501             }
0502 
0503             //Start the overall execution timer.s
0504             _executionTimer.start();
0505 
0506             //Increment the generation and the generation.
0507             ++_generation;
0508 
0509             //Select the survivors and the offspring.
0510             _selectTimer.start();
0511             final Array<Population<G, C>> selection = select();
0512             final Population<G, C> survivors = selection.get(0);
0513             final Population<G, C> offsprings = selection.get(1);
0514             _selectTimer.stop();
0515 
0516             //Alter the offspring (Recombination, Mutation ...).
0517             _alterTimer.start();
0518             _alterer.alter(offsprings, _generation);
0519             _alterTimer.stop();
0520 
0521             // Combining the new population (containing the survivors and the
0522             // altered offspring).
0523             _combineTimer.start();
0524             final int killed = _killed.get();
0525             final int invalid = _invalid.get();
0526             _population = combine(survivors, offsprings);
0527             _combineTimer.stop();
0528 
0529             //Evaluate the fitness
0530             evaluate();
0531 
0532             //Evaluate the statistic
0533             _statisticTimer.start();
0534             final Statistics.Builder<G, C> builder = _calculator.evaluate(
0535                     _executor, _population, _generation, _optimization
0536                 );
0537             builder.killed(_killed.get() - killed);
0538             builder.invalid(_invalid.get() - invalid);
0539             _statistics = builder.build();
0540 
0541             final int comp = _optimization.compare(
0542                 _statistics.getBestPhenotype(),
0543                 _bestStatistics.getBestPhenotype()
0544             );
0545 
0546             if (comp > 0) {
0547                 _bestStatistics = _statistics;
0548             }
0549 
0550             _statisticTimer.stop();
0551 
0552             _executionTimer.stop();
0553 
0554             setTimes(_statistics);
0555         finally {
0556             _lock.unlock();
0557         }
0558     }
0559 
0560     private void setTimes(final Statistics<?, ?> statistic) {
0561         statistic.getTime().execution.set(_executionTimer.getInterimTime());
0562         statistic.getTime().selection.set(_selectTimer.getInterimTime());
0563         statistic.getTime().alter.set(_alterTimer.getInterimTime());
0564         statistic.getTime().combine.set(_combineTimer.getInterimTime());
0565         statistic.getTime().evaluation.set(_evaluateTimer.getInterimTime());
0566         statistic.getTime().statistics.set(_statisticTimer.getInterimTime());
0567     }
0568 
0569     private void evaluate() {
0570         _evaluateTimer.start();
0571         try (Concurrency c = Concurrency.with(_executor)) {
0572             c.execute(_population);
0573         }
0574         _evaluateTimer.stop();
0575     }
0576 
0577     /**
0578      * Evolve the given number of {@code generations}
0579      *
0580      @param generations the number of {@code generations} to evolve.
0581      */
0582     public void evolve(final int generations) {
0583         for (int i = 0; i < generations; ++i) {
0584             evolve();
0585         }
0586     }
0587 
0588     /**
0589      * Evolve the GA as long the given {@link Function} returns {@code true}.
0590      *
0591      @see termination
0592      *
0593      @param until the predicate which defines the termination condition.
0594      @throws NullPointerException if the given predicate is {@code null}.
0595      */
0596     public void evolve(final Function<? super Statistics<G, C>, Boolean> until) {
0597         requireNonNull(until, "Termination condition");
0598         while (until.apply(getStatistics())) {
0599             evolve();
0600         }
0601     }
0602 
0603     private Array<Population<G, C>> select() {
0604         final Array<Population<G, C>> selection = new Array<>(2);
0605         final int numberOfSurvivors = getNumberOfSurvivors();
0606         final int numberOfOffspring = getNumberOfOffsprings();
0607         assert (numberOfSurvivors + numberOfOffspring == _populationSize);
0608 
0609         try (Concurrency c = Concurrency.with(_executor)) {
0610             c.execute(new Runnable() {
0611                 @Override
0612                 public void run() {
0613                     final Population<G, C> survivors = _survivorSelector.select(
0614                         _population, numberOfSurvivors, _optimization
0615                     );
0616 
0617                     assert (survivors.size() == numberOfSurvivors);
0618                     selection.set(0, survivors);
0619                 }
0620             });
0621 
0622             final Population<G, C> offsprings = _offspringSelector.select(
0623                 _population, numberOfOffspring, _optimization
0624             );
0625 
0626             assert (offsprings.size() == numberOfOffspring);
0627             selection.set(1, offsprings);
0628         }
0629 
0630         return selection;
0631     }
0632 
0633     private Population<G, C> combine(
0634         final Population<G, C> survivors,
0635         final Population<G, C> offsprings
0636     ) {
0637         assert (survivors.size() + offsprings.size() == _populationSize);
0638         final Population<G, C> population = new Population<>(_populationSize);
0639 
0640         try (Concurrency c = Concurrency.with(_executor)) {
0641             // Kill survivors which are to old and replace it with new one.
0642             c.execute(new Runnable() {
0643                 @Override
0644                 public void run() {
0645                     for (int i = 0, n = survivors.size(); i < n; ++i) {
0646                         final Phenotype<G, C> survivor = survivors.get(i);
0647 
0648                         final boolean isTooOld =
0649                             survivor.getAge(_generation> _maximalPhenotypeAge;
0650 
0651                         final boolean isInvalid = isTooOld || !survivor.isValid();
0652 
0653                         // Sorry, too old or not valid.
0654                         if (isInvalid) {
0655                             survivors.set(i, _phenotypeFactory.newInstance());
0656                         }
0657 
0658                         if (isTooOld) {
0659                             _killed.incrementAndGet();
0660                         else if (isInvalid) {
0661                             _invalid.incrementAndGet();
0662                         }
0663                     }
0664                 }
0665             });
0666 
0667             // In the mean time we can add the offsprings.
0668             population.addAll(offsprings);
0669         }
0670 
0671         population.addAll(survivors);
0672 
0673         return population;
0674     }
0675 
0676     private int getNumberOfSurvivors() {
0677         return _populationSize - getNumberOfOffsprings();
0678     }
0679 
0680     private int getNumberOfOffsprings() {
0681         return (int)round(
0682             _offspringFraction*_populationSize
0683         );
0684     }
0685 
0686     /**
0687      * Return {@code true} if the {@link #setup()} method has already been called,
0688      * {@code false} otherwise.
0689      *
0690      @return {@code true} if the {@link #setup()} method has already been called,
0691      *         {@code false} otherwise.
0692      */
0693     public boolean isInitialized() {
0694         _lock.lock();
0695         try {
0696             return _generation > 0;
0697         finally {
0698             _lock.unlock();
0699         }
0700     }
0701 
0702     /**
0703      <p>
0704      * If you are using the {@code GeneticAlgorithm} in an threaded environment
0705      * and you want to change some of the GAs parameters you can use the returned
0706      {@link Lock} to synchronize your parameter changes. The GA acquires the
0707      * lock at the begin of the {@link #setup()} and the {@link #evolve()}
0708      * methods and releases it at the end of these methods.
0709      </p>
0710      * To set one ore more GA parameter you will write code like this:
0711      * [code]
0712      * final GeneticAlgorithm&lt;DoubleGene, Double&gt; ga = ...
0713      * final Function&lt;GeneticAlgorithm&lt;?, ?&gt;, Boolean&gt; until = ...
0714      *
0715      * //Starting the GA in separate thread.
0716      * final Thread thread = new Thread(new Runnable() {
0717      *     public void run() {
0718      *         while (!Thread.currentThread().isInterrupted() &amp;&amp;
0719      *                !until.apply(ga))
0720      *         {
0721      *             if (ga.getGeneration() == 0) {
0722      *                 ga.setup();
0723      *             } else {
0724      *                 ga.evolve();
0725      *             }
0726      *         }
0727      *     }
0728      * });
0729      * thread.start();
0730      *
0731      *  //Changing the GA parameters outside the evolving thread. All parameters
0732      *  //are changed before the next evolve step.
0733      * ga.getLock().lock();
0734      * try {
0735      *     ga.setAlterer(new Mutation(0.02));
0736      *     ga.setPopulationSize(55);
0737      *     ga.setMaximalPhenotypeAge(30);
0738      * } finally {
0739      *     ga.getLock().unlock();
0740      * }
0741      * [/code]
0742      *
0743      * You can use the same lock if you want get a consistent state of the used
0744      * parameters, if they where changed within an other thread.
0745      *
0746      * [code]
0747      * ga.getLock().lock();
0748      * try {
0749      *     final Statistics&lt;?, ?&gt; statistics = ga.getStatistic();
0750      *     final Function&lt;?, ?&gt; scaler = ga.getFitnessScaler();
0751      * } finally {
0752      *     ga.getLock().unlock();
0753      * }
0754      * [/code]
0755      *
0756      * The code above ensures that the returned {@code statistics} and
0757      * {@code scaler} where used together within the same {@link #evolve()} step.
0758      *
0759      @return the lock acquired in the {@link #setup()} and the {@link #evolve()}
0760      *         method.
0761      */
0762     public Lock getLock() {
0763         return _lock;
0764     }
0765 
0766     /**
0767      * Return the used genotype {@link Factory} of the GA. The genotype factory
0768      * is used for creating the initial population and new, random individuals
0769      * when needed (as replacement for invalid and/or died genotypes).
0770      *
0771      @return the used genotype {@link Factory} of the GA.
0772      */
0773     public Factory<Genotype<G>> getGenotypeFactory() {
0774         return _genotypeFactory;
0775     }
0776 
0777     /**
0778      <p>
0779      * Return the used fitness {@link Function} of the GA. The fitness function
0780      * is also an important part when modeling the GA. It takes a genotype as
0781      * argument and returns, at least, a Comparable object as result---the
0782      * fitness value. This allows the GA, respectively the selection operators,
0783      * to select the offspring- and survivor population. Some selectors have
0784      * stronger requirements to the fitness value than a Comparable, but this
0785      * constraints is checked by the Java type system at compile time.
0786      </p>
0787      * The following example shows the simplest possible fitness function. It's
0788      * the identity function and returns the allele of an 1x1  float genotype.
0789      * [code]
0790      * class Id implements Function&lt;Genotype&lt;DoubleGene&gt;, Double&gt; {
0791      *     public Double apply(final Genotype&lt;DoubleGene&gt; genotype) {
0792      *         return genotype.getGene().getAllele();
0793      *     }
0794      * }
0795      * [/code]
0796      * The first type parameter of the {@link Function} defines the kind of
0797      * genotype from which the fitness value is calculated and the second type
0798      * parameter determines the return type. As already mentioned, the return
0799      * type must implement the {@link Comparable} interface.
0800      *
0801      @return the used fitness {@link Function} of the GA.
0802      */
0803     public Function<? super Genotype<G>, ? extends C> getFitnessFunction() {
0804         return _fitnessFunction;
0805     }
0806 
0807     /**
0808      * Set the currently used fitness scaler. The fitness value, calculated by
0809      * the fitness function, is the raw-fitness of an individual. The
0810      <em>Jenetics</em> library allows you to apply an additional scaling
0811      * function on the raw-fitness to form the fitness value which is used by
0812      * the selectors. This can be useful when using probability selectors, where
0813      * the actual amount of the fitness value influences the selection
0814      * probability. In such cases, the fitness scaler gives you additional
0815      * flexibility when selecting offspring and survivors. In the default
0816      * configuration the raw-fitness is equal to the actual fitness value, that
0817      * means, the used fitness scaler is the identity function.
0818      * [code]
0819      * class Sqrt extends Function&lt;Double, Double&gt; {
0820      *     public Double apply(final Double value) {
0821      *         return sqrt(value);
0822      *     }
0823      * }
0824      * [/code]
0825      *
0826      <p>
0827      * The listing above shows a fitness scaler which reduces the the raw-fitness
0828      * to its square root. This gives weaker individuals a greater changes being
0829      * selected and weakens the influence of super-individuals.
0830      </p>
0831      * When using a fitness scaler you have to take care, that your scaler
0832      * doesn't destroy your fitness value. This can be the case when your
0833      * fitness value is negative and your fitness scaler squares the value.
0834      * Trying to find the minimum will not work in this configuration.
0835      *
0836      @param scaler The fitness scaler.
0837      @throws NullPointerException if the scaler is {@code null}.
0838      */
0839     public void setFitnessScaler(final Function<? super C, ? extends C> scaler) {
0840         _fitnessScaler = requireNonNull(scaler, "FitnessScaler");
0841     }
0842 
0843     /**
0844      * Return the currently used fitness scaler {@link Function} of the GA.
0845      *
0846      @return the currently used fitness scaler {@link Function} of the GA.
0847      */
0848     public Function<? super C, ? extends C> getFitnessScaler() {
0849         return _fitnessScaler;
0850     }
0851 
0852     /**
0853      * Return the currently used offspring fraction of the GA.
0854      *
0855      @return the currently used offspring fraction of the GA.
0856      */
0857     public double getOffspringFraction() {
0858         return _offspringFraction;
0859     }
0860 
0861     /**
0862      * Return the currently used offspring {@link Selector} of the GA.
0863      *
0864      @return the currently used offspring {@link Selector} of the GA.
0865      */
0866     public Selector<G, C> getOffspringSelector() {
0867         return _offspringSelector;
0868     }
0869 
0870     /**
0871      * Return the currently used survivor {@link Selector} of the GA.
0872      *
0873      @return the currently used survivor {@link Selector} of the GA.
0874      */
0875     public Selector<G, C> getSurvivorSelector() {
0876         return _survivorSelector;
0877     }
0878 
0879     /**
0880      * Return the currently used {@link Alterer} of the GA.
0881      *
0882      @return the currently used {@link Alterer} of the GA.
0883      */
0884     public Alterer<G> getAlterer() {
0885         return _alterer;
0886     }
0887 
0888     /**
0889      * Return the current overall generation.
0890      *
0891      @return the current overall generation.
0892      */
0893     public int getGeneration() {
0894         return _generation;
0895     }
0896 
0897     /**
0898      * Return the maximal age of the {@link Phenotype}s.
0899      *
0900      @return the maximal age of the {@link Phenotype}s.
0901      */
0902     public int getMaximalPhenotypeAge() {
0903         return _maximalPhenotypeAge;
0904     }
0905 
0906     /**
0907      * Return the best {@link Phenotype} so far or {@code null} if the GA hasn't
0908      * been initialized yet.
0909      *
0910      @return the best {@link Phenotype} so far or {@code null} if the GA hasn't
0911      *         been initialized yet.
0912      */
0913     public Phenotype<G, C> getBestPhenotype() {
0914         return _bestStatistics != null ? _bestStatistics.getBestPhenotype() null;
0915     }
0916 
0917     /**
0918      * Return the current {@link Population} {@link Statistics} or {@code null}
0919      * if the GA hasn't been initialized yet.
0920      *
0921      @return the current {@link Population} {@link Statistics} or {@code null}
0922      *         if the GA hasn't been initialized yet.
0923      */
0924     public Statistics<G, C> getStatistics() {
0925         return _statistics;
0926     }
0927 
0928     /**
0929      * Set the offspring selector.
0930      *
0931      @param selector The offspring selector.
0932      @throws NullPointerException if the given selector is null.
0933      */
0934     public void setOffspringSelector(final Selector<G, C> selector) {
0935         _offspringSelector = requireNonNull(selector, "Offspring selector");
0936     }
0937 
0938     /**
0939      * Set the survivor selector.
0940      *
0941      @param selector The survivor selector.
0942      @throws NullPointerException if the given selector is null.
0943      */
0944     public void setSurvivorSelector(final Selector<G, C> selector) {
0945         _survivorSelector = requireNonNull(selector, "Survivor selector");
0946     }
0947 
0948     /**
0949      * Set both, the offspring selector and the survivor selector.
0950      *
0951      @param selector The selector for the offspring and the survivors.
0952      @throws NullPointerException if the {@code selector} is {@code null}
0953      */
0954     public void setSelectors(final Selector<G, C> selector) {
0955         setOffspringSelector(selector);
0956         setSurvivorSelector(selector);
0957     }
0958 
0959     /**
0960      * Set the offspring fraction.
0961      *
0962      @param offspringFraction The offspring fraction.
0963      @throws IllegalArgumentException if the offspring fraction is out of
0964      *         range.
0965      */
0966     public void setOffspringFraction(final double offspringFraction) {
0967         _offspringFraction = checkProbability(offspringFraction);
0968     }
0969 
0970     /**
0971      * Set the alterer.
0972      *
0973      @param alterer The alterer.
0974      @throws NullPointerException if the alterer is null.
0975      */
0976     public void setAlterer(final Alterer<G> alterer) {
0977         _alterer = requireNonNull(alterer, "Alterer");
0978     }
0979 
0980     /**
0981      * Set the given alterers.
0982      *
0983      @param alterers the alterers to set.
0984      @throws NullPointerException if the alterers are null.
0985      */
0986     @SafeVarargs
0987     public final void setAlterers(final Alterer<G>... alterers) {
0988         setAlterer(CompositeAlterer.of(alterers));
0989     }
0990 
0991     /**
0992      * Set the maximum age of the phenotypes in the population.
0993      *
0994      @param age Maximal phenotype age.
0995      @throws IllegalArgumentException if the age is smaller then one.
0996      */
0997     public void setMaximalPhenotypeAge(final int age) {
0998         if (age < 1) {
0999             throw new IllegalArgumentException(format(
1000                 "Phenotype age must be greater than one, but was %s.", age
1001             ));
1002         }
1003         _maximalPhenotypeAge = age;
1004     }
1005 
1006     /**
1007      * Set the desired population size.
1008      *
1009      @param size The population size.
1010      @throws IllegalArgumentException if the population size is smaller than
1011      *         one.
1012      */
1013     public void setPopulationSize(final int size) {
1014         if (size < 1) {
1015             throw new IllegalArgumentException(format(
1016                 "Population size must be greater than zero, but was %s.", size
1017             ));
1018         }
1019         _populationSize = size;
1020     }
1021 
1022     /**
1023      * Set the (initial) population in form of a list of phenotypes. The fitness
1024      * function and fitness scaler of the phenotypes will be changed with the
1025      * current one of this GA. The fitness values are calculated as needed by
1026      * the next <i>evolve</i> step. <em>This method doesn't acquire the GA lock.
1027      * When used from another thread, the lock must be acquired from outside.</em>
1028      *
1029      @see #setGenotypes(Collection)
1030      @see #setup(Collection)
1031      @param population The list of phenotypes to set. The population size is
1032      *        set to {@code phenotype.size()}.
1033      @throws NullPointerException if the population, or one of its element, is
1034      *         {@code null}.
1035      @throws IllegalArgumentException it the population size is smaller than
1036      *         one.
1037      */
1038     public void setPopulation(final Collection<Phenotype<G, C>> population) {
1039         forEach(population, NonNull);
1040         if (population.size() 1) {
1041             throw new IllegalArgumentException(format(
1042                 "Population size must be greater than zero, but was %s.",
1043                 population.size()
1044             ));
1045         }
1046 
1047         final Population<G, C> pop = new Population<>(population.size());
1048         for (Phenotype<G, C> phenotype : population) {
1049             pop.add(phenotype.newInstance(
1050                 _fitnessFunction, _fitnessScaler, _generation
1051             ));
1052         }
1053 
1054         _population = pop;
1055         _populationSize = population.size();
1056     }
1057 
1058     /**
1059      * Set/change the population in form of a list of genotypes. The fitness
1060      * function and fitness scaler will not be changed. The fitness values are
1061      * calculated as needed by the next <i>evolve</i> step. <em>This method
1062      * doesn't acquire the GA lock. When used from another thread, the lock must
1063      * be acquired from outside.</em>
1064      *
1065      @see #setPopulation(Collection)
1066      @see #setup(Collection)
1067      @param genotypes The list of genotypes to set. The population size is set
1068      *        to {@code genotypes.size()}.
1069      @throws NullPointerException if the population, or one of its elements,
1070      *         is {@code null}s.
1071      @throws IllegalArgumentException it the population size is smaller than
1072      *         one.
1073      */
1074     public void setGenotypes(final Collection<Genotype<G>> genotypes) {
1075         forEach(genotypes, NonNull);
1076         if (genotypes.size() 1) {
1077             throw new IllegalArgumentException(
1078                 "Genotype size must be greater than zero, but was " +
1079                 genotypes.size() ". "
1080             );
1081         }
1082 
1083         final Population<G, C> population = new Population<>(genotypes.size());
1084         for (Genotype<G> genotype : genotypes) {
1085             population.add(Phenotype.of(
1086                 genotype,
1087                 _fitnessFunction,
1088                 _fitnessScaler,
1089                 _generation
1090             ));
1091         }
1092 
1093         _population = population;
1094         _populationSize = genotypes.size();
1095     }
1096 
1097     /**
1098      * Return a copy of the current population.
1099      *
1100      @return The copy of the current population.
1101      */
1102     public Population<G, C> getPopulation() {
1103         return new Population<>(_population);
1104     }
1105 
1106     /**
1107      * Return the desired population size of the GA.
1108      *
1109      @return the desired population size of the GA.
1110      */
1111     public int getPopulationSize() {
1112         return _populationSize;
1113     }
1114 
1115     /**
1116      * Return the statistics of the best phenotype. The returned statistics is
1117      * {@code null} if the algorithms hasn't been initialized.
1118      *
1119      @return the statistics of the best phenotype, or {@code null} if the GA
1120      *         hasn't been initialized yet.
1121      */
1122     public Statistics<G, C> getBestStatistics() {
1123         return _bestStatistics;
1124     }
1125 
1126     /**
1127      * Return the number of killed phenotypes, so far.
1128      *
1129      @return the number of killed phenotypes
1130      */
1131     public int getNumberOfKilledPhenotypes() {
1132         return _killed.get();
1133     }
1134 
1135     /**
1136      * Return the number of invalid phenotypes, so far.
1137      *
1138      @return the number of invalid phenotypes
1139      */
1140     public int getNumberOfInvalidPhenotypes() {
1141         return _invalid.get();
1142     }
1143 
1144     /**
1145      * Set the statistic calculator for this genetic algorithm instance.
1146      *
1147      @param calculator the new statistic calculator.
1148      @throws NullPointerException if the given {@code calculator} is
1149      *         {@code null}.
1150      */
1151     public void setStatisticsCalculator(
1152         final Statistics.Calculator<G, C> calculator
1153     ) {
1154         _calculator = requireNonNull(calculator, "Statistic calculator");
1155     }
1156 
1157     /**
1158      * Return the current statistics calculator.
1159      *
1160      @return the current statistics calculator.
1161      */
1162     public Statistics.Calculator<G, C> getStatisticsCalculator() {
1163         return _calculator;
1164     }
1165 
1166     /**
1167      * Return the current time statistics of the GA. This method acquires the
1168      * lock to ensure that the returned values are consistent.
1169      *
1170      @return the current time statistics.
1171      */
1172     public Statistics.Time getTimeStatistics() {
1173         _lock.lock();
1174         try {
1175             final Statistics.Time time = new Statistics.Time();
1176             time.alter.set(_alterTimer.getTime());
1177             time.combine.set(_combineTimer.getTime());
1178             time.evaluation.set(_evaluateTimer.getTime());
1179             time.execution.set(_executionTimer.getTime());
1180             time.selection.set(_selectTimer.getTime());
1181             time.statistics.set(_statisticTimer.getTime());
1182             return time;
1183         finally {
1184             _lock.unlock();
1185         }
1186     }
1187 
1188     /**
1189      * This method acquires the lock to ensure that the returned value is
1190      * consistent.
1191      */
1192     @Override
1193     public String toString() {
1194         Phenotype<G, C> phenotype = null;
1195         int generation = 0;
1196 
1197         _lock.lock();
1198         try {
1199             generation = _generation;
1200             phenotype = getStatistics().getBestPhenotype();
1201         finally {
1202             _lock.unlock();
1203         }
1204 
1205         return format("%4d: (best) %s", generation, phenotype);
1206     }
1207 
1208 }