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<Genotype<BitGene>> gtf = Genotype.of(
0054 * BitChromosome.of(10, 0.5)
0055 * );
0056 * final Function<Genotype<BitGene> Double> ff = ...
0057 * final GeneticAlgorithm<BitGene, Double>
0058 * ga = new GeneticAlgorithm<>(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<BitGene>());
0088 * ga.setAlterers(
0089 * new SinglePointCrossover<BitGene>(0.1),
0090 * new Mutator<BitGene>(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<DoubleGene, Double> population =
0122 * (Population<DoubleGene, Double>)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 — <em>$Date: 2014-04-12 $</em>
0138 */
0139 public class GeneticAlgorithm<
0140 G extends Gene<?, G>,
0141 C 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<DoubleGene, Double> ga = ...
0713 * final Function<GeneticAlgorithm<?, ?>, Boolean> 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() &&
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<?, ?> statistics = ga.getStatistic();
0750 * final Function<?, ?> 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<Genotype<DoubleGene>, Double> {
0791 * public Double apply(final Genotype<DoubleGene> 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<Double, Double> {
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 }
|