0001 /*
0002 * Java Genetic Algorithm Library (jenetics-3.5.0).
0003 * Copyright (c) 2007-2016 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.engine;
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.Population.toPopulation;
0026 import static org.jenetics.internal.util.require.probability;
0027
0028 import java.time.Clock;
0029 import java.util.Iterator;
0030 import java.util.Objects;
0031 import java.util.concurrent.CompletableFuture;
0032 import java.util.concurrent.Executor;
0033 import java.util.concurrent.ForkJoinPool;
0034 import java.util.function.Function;
0035 import java.util.function.Predicate;
0036 import java.util.stream.Stream;
0037 import java.util.stream.StreamSupport;
0038
0039 import org.jenetics.internal.util.Concurrency;
0040 import org.jenetics.internal.util.require;
0041
0042 import org.jenetics.Alterer;
0043 import org.jenetics.Chromosome;
0044 import org.jenetics.Gene;
0045 import org.jenetics.Genotype;
0046 import org.jenetics.Mutator;
0047 import org.jenetics.Optimize;
0048 import org.jenetics.Phenotype;
0049 import org.jenetics.Population;
0050 import org.jenetics.Selector;
0051 import org.jenetics.SinglePointCrossover;
0052 import org.jenetics.TournamentSelector;
0053 import org.jenetics.util.Copyable;
0054 import org.jenetics.util.Factory;
0055 import org.jenetics.util.NanoClock;
0056
0057 /**
0058 * Genetic algorithm <em>engine</em> which is the main class. The following
0059 * example shows the main steps in initializing and executing the GA.
0060 *
0061 * <pre>{@code
0062 * public class RealFunction {
0063 * // Definition of the fitness function.
0064 * private static Double eval(final Genotype<DoubleGene> gt) {
0065 * final double x = gt.getGene().doubleValue();
0066 * return cos(0.5 + sin(x)) * cos(x);
0067 * }
0068 *
0069 * public static void main(String[] args) {
0070 * // Create/configuring the engine via its builder.
0071 * final Engine<DoubleGene, Double> engine = Engine
0072 * .builder(
0073 * RealFunction::eval,
0074 * DoubleChromosome.of(0.0, 2.0*PI))
0075 * .populationSize(500)
0076 * .optimize(Optimize.MINIMUM)
0077 * .alterers(
0078 * new Mutator<>(0.03),
0079 * new MeanAlterer<>(0.6))
0080 * .build();
0081 *
0082 * // Execute the GA (engine).
0083 * final Phenotype<DoubleGene, Double> result = engine.stream()
0084 * // Truncate the evolution stream if no better individual could
0085 * // be found after 5 consecutive generations.
0086 * .limit(bySteadyFitness(5))
0087 * // Terminate the evolution after maximal 100 generations.
0088 * .limit(100)
0089 * .collect(toBestPhenotype());
0090 * }
0091 * }
0092 * }</pre>
0093 *
0094 * The architecture allows to decouple the configuration of the engine from the
0095 * execution. The {@code Engine} is configured via the {@code Engine.Builder}
0096 * class and can't be changed after creation. The actual <i>evolution</i> is
0097 * performed by the {@link EvolutionStream}, which is created by the
0098 * {@code Engine}.
0099 * <p>
0100 * <em>
0101 * <b>This class is thread safe:</b>
0102 * No mutable state is maintained by the engine. Therefore it is save to
0103 * create multiple evolution streams with one engine, which may be actually
0104 * used in different threads.
0105 * </em>
0106 *
0107 * @see Engine.Builder
0108 * @see EvolutionStart
0109 * @see EvolutionResult
0110 * @see EvolutionStream
0111 * @see EvolutionStatistics
0112 * @see Codec
0113 *
0114 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
0115 * @since 3.0
0116 * @version 3.2
0117 */
0118 public final class Engine<
0119 G extends Gene<?, G>,
0120 C extends Comparable<? super C>
0121 >
0122 implements Function<EvolutionStart<G, C>, EvolutionResult<G, C>>
0123 {
0124
0125 // Needed context for population evolving.
0126 private final Function<? super Genotype<G>, ? extends C> _fitnessFunction;
0127 private final Function<? super C, ? extends C> _fitnessScaler;
0128 private final Factory<Genotype<G>> _genotypeFactory;
0129 private final Selector<G, C> _survivorsSelector;
0130 private final Selector<G, C> _offspringSelector;
0131 private final Alterer<G, C> _alterer;
0132 private final Predicate<? super Phenotype<G, C>> _validator;
0133 private final Optimize _optimize;
0134 private final int _offspringCount;
0135 private final int _survivorsCount;
0136 private final long _maximalPhenotypeAge;
0137
0138 // Execution context for concurrent execution of evolving steps.
0139 private final TimedExecutor _executor;
0140 private final Clock _clock;
0141
0142 // Additional parameters.
0143 private final int _individualCreationRetries;
0144
0145
0146 /**
0147 * Create a new GA engine with the given parameters.
0148 *
0149 * @param genotypeFactory the genotype factory this GA is working with.
0150 * @param fitnessFunction the fitness function this GA is using.
0151 * @param fitnessScaler the fitness scaler this GA is using.
0152 * @param survivorsSelector the selector used for selecting the survivors
0153 * @param offspringSelector the selector used for selecting the offspring
0154 * @param alterer the alterer used for altering the offspring
0155 * @param validator phenotype validator which can override the default
0156 * implementation the {@link Phenotype#isValid()} method.
0157 * @param optimize the kind of optimization (minimize or maximize)
0158 * @param offspringCount the number of the offspring individuals
0159 * @param survivorsCount the number of the survivor individuals
0160 * @param maximalPhenotypeAge the maximal age of an individual
0161 * @param executor the executor used for executing the single evolve steps
0162 * @param clock the clock used for calculating the timing results
0163 * @param individualCreationRetries the maximal number of attempts for
0164 * creating a valid individual.
0165 * @throws NullPointerException if one of the arguments is {@code null}
0166 * @throws IllegalArgumentException if the given integer values are smaller
0167 * than one.
0168 */
0169 Engine(
0170 final Function<? super Genotype<G>, ? extends C> fitnessFunction,
0171 final Function<? super C, ? extends C> fitnessScaler,
0172 final Factory<Genotype<G>> genotypeFactory,
0173 final Selector<G, C> survivorsSelector,
0174 final Selector<G, C> offspringSelector,
0175 final Alterer<G, C> alterer,
0176 final Predicate<? super Phenotype<G, C>> validator,
0177 final Optimize optimize,
0178 final int offspringCount,
0179 final int survivorsCount,
0180 final long maximalPhenotypeAge,
0181 final Executor executor,
0182 final Clock clock,
0183 final int individualCreationRetries
0184 ) {
0185 _fitnessFunction = requireNonNull(fitnessFunction);
0186 _fitnessScaler = requireNonNull(fitnessScaler);
0187 _genotypeFactory = requireNonNull(genotypeFactory);
0188 _survivorsSelector = requireNonNull(survivorsSelector);
0189 _offspringSelector = requireNonNull(offspringSelector);
0190 _alterer = requireNonNull(alterer);
0191 _validator = requireNonNull(validator);
0192 _optimize = requireNonNull(optimize);
0193
0194 _offspringCount = require.nonNegative(offspringCount);
0195 _survivorsCount = require.nonNegative(survivorsCount);
0196 _maximalPhenotypeAge = require.positive(maximalPhenotypeAge);
0197
0198 _executor = new TimedExecutor(requireNonNull(executor));
0199 _clock = requireNonNull(clock);
0200
0201 if (individualCreationRetries < 0) {
0202 throw new IllegalArgumentException(format(
0203 "Retry count must not be negative: %d",
0204 individualCreationRetries
0205 ));
0206 }
0207 _individualCreationRetries = individualCreationRetries;
0208 }
0209
0210 /**
0211 * Perform one evolution step with the given {@code population} and
0212 * {@code generation}. New phenotypes are created with the fitness function
0213 * and fitness scaler defined by this <em>engine</em>
0214 * <p>
0215 * <em>This method is thread-safe.</em>
0216 *
0217 * @see #evolve(EvolutionStart)
0218 *
0219 * @param population the population to evolve
0220 * @param generation the current generation; used for calculating the
0221 * phenotype age.
0222 * @return the evolution result
0223 * @throws java.lang.NullPointerException if the given {@code population} is
0224 * {@code null}
0225 * @throws IllegalArgumentException if the given {@code generation} is
0226 * smaller then one
0227 */
0228 public EvolutionResult<G, C> evolve(
0229 final Population<G, C> population,
0230 final long generation
0231 ) {
0232 return evolve(EvolutionStart.of(population, generation));
0233 }
0234
0235 /**
0236 * Perform one evolution step with the given evolution {@code start} object
0237 * New phenotypes are created with the fitness function and fitness scaler
0238 * defined by this <em>engine</em>
0239 * <p>
0240 * <em>This method is thread-safe.</em>
0241 *
0242 * @since 3.1
0243 * @see #evolve(org.jenetics.Population, long)
0244 *
0245 * @param start the evolution start object
0246 * @return the evolution result
0247 * @throws java.lang.NullPointerException if the given evolution
0248 * {@code start} is {@code null}
0249 */
0250 public EvolutionResult<G, C> evolve(final EvolutionStart<G, C> start) {
0251 final Timer timer = Timer.of().start();
0252
0253 final Population<G, C> startPopulation = start.getPopulation();
0254
0255 // Initial evaluation of the population.
0256 final Timer evaluateTimer = Timer.of(_clock).start();
0257 evaluate(startPopulation);
0258 evaluateTimer.stop();
0259
0260 // Select the offspring population.
0261 final CompletableFuture<TimedResult<Population<G, C>>> offspring =
0262 _executor.async(() ->
0263 selectOffspring(startPopulation),
0264 _clock
0265 );
0266
0267 // Select the survivor population.
0268 final CompletableFuture<TimedResult<Population<G, C>>> survivors =
0269 _executor.async(() ->
0270 selectSurvivors(startPopulation),
0271 _clock
0272 );
0273
0274 // Altering the offspring population.
0275 final CompletableFuture<TimedResult<AlterResult<G, C>>> alteredOffspring =
0276 _executor.thenApply(offspring, p ->
0277 alter(p.result, start.getGeneration()),
0278 _clock
0279 );
0280
0281 // Filter and replace invalid and to old survivor individuals.
0282 final CompletableFuture<TimedResult<FilterResult<G, C>>> filteredSurvivors =
0283 _executor.thenApply(survivors, pop ->
0284 filter(pop.result, start.getGeneration()),
0285 _clock
0286 );
0287
0288 // Filter and replace invalid and to old offspring individuals.
0289 final CompletableFuture<TimedResult<FilterResult<G, C>>> filteredOffspring =
0290 _executor.thenApply(alteredOffspring, pop ->
0291 filter(pop.result.population, start.getGeneration()),
0292 _clock
0293 );
0294
0295 // Combining survivors and offspring to the new population.
0296 final CompletableFuture<Population<G, C>> population =
0297 filteredSurvivors.thenCombineAsync(filteredOffspring, (s, o) -> {
0298 final Population<G, C> pop = s.result.population;
0299 pop.addAll(o.result.population);
0300 return pop;
0301 },
0302 _executor.get()
0303 );
0304
0305 // Evaluate the fitness-function and wait for result.
0306 final TimedResult<Population<G, C>> result = population
0307 .thenApply(TimedResult.of(this::evaluate, _clock))
0308 .join();
0309
0310 final EvolutionDurations durations = EvolutionDurations.of(
0311 offspring.join().duration,
0312 survivors.join().duration,
0313 alteredOffspring.join().duration,
0314 filteredOffspring.join().duration,
0315 filteredSurvivors.join().duration,
0316 result.duration.plus(evaluateTimer.getTime()),
0317 timer.stop().getTime()
0318 );
0319
0320 final int killCount =
0321 filteredOffspring.join().result.killCount +
0322 filteredSurvivors.join().result.killCount;
0323
0324 final int invalidCount =
0325 filteredOffspring.join().result.invalidCount +
0326 filteredSurvivors.join().result.invalidCount;
0327
0328 return EvolutionResult.of(
0329 _optimize,
0330 result.result,
0331 start.getGeneration(),
0332 durations,
0333 killCount,
0334 invalidCount,
0335 alteredOffspring.join().result.alterCount
0336 );
0337 }
0338
0339 /**
0340 * This method is an <i>alias</i> for the {@link #evolve(EvolutionStart)}
0341 * method.
0342 *
0343 * @since 3.1
0344 */
0345 @Override
0346 public EvolutionResult<G, C> apply(final EvolutionStart<G, C> start) {
0347 return evolve(start);
0348 }
0349
0350 // Selects the survivors population. A new population object is returned.
0351 private Population<G, C> selectSurvivors(final Population<G, C> population) {
0352 return _survivorsCount > 0
0353 ?_survivorsSelector.select(population, _survivorsCount, _optimize)
0354 : Population.empty();
0355 }
0356
0357 // Selects the offspring population. A new population object is returned.
0358 private Population<G, C> selectOffspring(final Population<G, C> population) {
0359 return _offspringCount > 0
0360 ? _offspringSelector.select(population, _offspringCount, _optimize)
0361 : Population.empty();
0362 }
0363
0364 // Filters out invalid and to old individuals. Filtering is done in place.
0365 private FilterResult<G, C> filter(
0366 final Population<G, C> population,
0367 final long generation
0368 ) {
0369 int killCount = 0;
0370 int invalidCount = 0;
0371
0372 for (int i = 0, n = population.size(); i < n; ++i) {
0373 final Phenotype<G, C> individual = population.get(i);
0374
0375 if (!_validator.test(individual)) {
0376 population.set(i, newPhenotype(generation));
0377 ++invalidCount;
0378 } else if (individual.getAge(generation) > _maximalPhenotypeAge) {
0379 population.set(i, newPhenotype(generation));
0380 ++killCount;
0381 }
0382 }
0383
0384 return new FilterResult<>(population, killCount, invalidCount);
0385 }
0386
0387 // Create a new and valid phenotype
0388 private Phenotype<G, C> newPhenotype(final long generation) {
0389 int count = 0;
0390 Phenotype<G, C> phenotype;
0391 do {
0392 phenotype = Phenotype.of(
0393 _genotypeFactory.newInstance(),
0394 generation,
0395 _fitnessFunction,
0396 _fitnessScaler
0397 );
0398 } while (++count < _individualCreationRetries &&
0399 !_validator.test(phenotype));
0400
0401 return phenotype;
0402 }
0403
0404 // Alters the given population. The altering is done in place.
0405 private AlterResult<G, C> alter(
0406 final Population<G,C> population,
0407 final long generation
0408 ) {
0409 return new AlterResult<>(
0410 population,
0411 _alterer.alter(population, generation)
0412 );
0413 }
0414
0415 // Evaluates the fitness function of the give population concurrently.
0416 private Population<G, C> evaluate(final Population<G, C> population) {
0417 try (Concurrency c = Concurrency.with(_executor.get())) {
0418 c.execute(population);
0419 }
0420 return population;
0421 }
0422
0423 /**
0424 * Create a new <b>infinite</b> evolution iterator with a newly created
0425 * population. This is an alternative way for evolution. It lets the user
0426 * start, stop and resume the evolution process whenever desired.
0427 *
0428 * @return a new <b>infinite</b> evolution iterator
0429 */
0430 public Iterator<EvolutionResult<G, C>> iterator() {
0431 return new EvolutionIterator<>(
0432 this::evolve,
0433 this::evolutionStart
0434 );
0435 }
0436
0437 /**
0438 * Create a new <b>infinite</b> evolution stream with a newly created
0439 * population.
0440 *
0441 * @return a new evolution stream.
0442 */
0443 public EvolutionStream<G, C> stream() {
0444 return EvolutionStream.of(this::evolutionStart, this::evolve);
0445 }
0446
0447 private EvolutionStart<G, C> evolutionStart() {
0448 final int generation = 1;
0449 final int size = _offspringCount + _survivorsCount;
0450
0451 final Population<G, C> population = new Population<G, C>(size)
0452 .fill(() -> newPhenotype(generation), size);
0453
0454 return EvolutionStart.of(population, generation);
0455 }
0456
0457 /**
0458 * Create a new <b>infinite</b> evolution stream with the given initial
0459 * individuals. If an empty {@code Iterable} is given, the engines genotype
0460 * factory is used for creating the population.
0461 *
0462 * @param genotypes the initial individuals used for the evolution stream.
0463 * Missing individuals are created and individuals not needed are
0464 * skipped.
0465 * @return a new evolution stream.
0466 * @throws java.lang.NullPointerException if the given {@code genotypes} is
0467 * {@code null}.
0468 */
0469 public EvolutionStream<G, C> stream(
0470 final Iterable<Genotype<G>> genotypes
0471 ) {
0472 requireNonNull(genotypes);
0473
0474 return EvolutionStream.of(
0475 () -> evolutionStart(genotypes, 1),
0476 this::evolve
0477 );
0478 }
0479
0480 /**
0481 * Create a new <b>infinite</b> evolution iterator with the given initial
0482 * individuals. If an empty {@code Iterable} is given, the engines genotype
0483 * factory is used for creating the population.
0484 *
0485 * @param genotypes the initial individuals used for the evolution iterator.
0486 * Missing individuals are created and individuals not needed are
0487 * skipped.
0488 * @return a new <b>infinite</b> evolution iterator
0489 * @throws java.lang.NullPointerException if the given {@code genotypes} is
0490 * {@code null}.
0491 */
0492 public Iterator<EvolutionResult<G, C>> iterator(
0493 final Iterable<Genotype<G>> genotypes
0494 ) {
0495 requireNonNull(genotypes);
0496
0497 return new EvolutionIterator<>(
0498 this::evolve,
0499 () -> evolutionStart(genotypes, 1)
0500 );
0501 }
0502
0503 private EvolutionStart<G, C> evolutionStart(
0504 final Iterable<Genotype<G>> genotypes,
0505 final long generation
0506 ) {
0507 final Stream<Phenotype<G, C>> stream = Stream.concat(
0508 StreamSupport.stream(genotypes.spliterator(), false)
0509 .map(gt -> Phenotype.of(
0510 gt, generation, _fitnessFunction, _fitnessScaler)),
0511 Stream.generate(() -> newPhenotype(generation))
0512 );
0513
0514 final Population<G, C> population = stream
0515 .limit(getPopulationSize())
0516 .collect(toPopulation());
0517
0518 return EvolutionStart.of(population, generation);
0519 }
0520
0521 /**
0522 * Create a new <b>infinite</b> evolution stream with the given initial
0523 * population. If an empty {@code Population} is given, the engines genotype
0524 * factory is used for creating the population. The given population might
0525 * be the result of an other engine and this method allows to start the
0526 * evolution with the outcome of an different engine. The fitness function
0527 * and the fitness scaler are replaced by the one defined for this engine.
0528 *
0529 * @param population the initial individuals used for the evolution stream.
0530 * Missing individuals are created and individuals not needed are
0531 * skipped.
0532 * @param generation the generation the stream starts from; must be greater
0533 * than zero.
0534 * @return a new evolution stream.
0535 * @throws java.lang.NullPointerException if the given {@code population} is
0536 * {@code null}.
0537 * @throws IllegalArgumentException if the given {@code generation} is smaller
0538 * then one
0539 */
0540 public EvolutionStream<G, C> stream(
0541 final Population<G, C> population,
0542 final long generation
0543 ) {
0544 requireNonNull(population);
0545 require.positive(generation);
0546
0547 return EvolutionStream.of(
0548 () -> evolutionStart(population, generation),
0549 this::evolve
0550 );
0551 }
0552
0553 /**
0554 * Create a new <b>infinite</b> evolution iterator with the given initial
0555 * population. If an empty {@code Population} is given, the engines genotype
0556 * factory is used for creating the population. The given population might
0557 * be the result of an other engine and this method allows to start the
0558 * evolution with the outcome of an different engine. The fitness function
0559 * and the fitness scaler are replaced by the one defined for this engine.
0560 *
0561 * @param population the initial individuals used for the evolution iterator.
0562 * Missing individuals are created and individuals not needed are
0563 * skipped.
0564 * @param generation the generation the iterator starts from; must be greater
0565 * than zero.
0566 * @return a new <b>infinite</b> evolution iterator
0567 * @throws java.lang.NullPointerException if the given {@code population} is
0568 * {@code null}.
0569 * @throws IllegalArgumentException if the given {@code generation} is smaller
0570 * then one
0571 */
0572 public Iterator<EvolutionResult<G, C>> iterator(
0573 final Population<G, C> population,
0574 final long generation
0575 ) {
0576 requireNonNull(population);
0577 require.positive(generation);
0578
0579 return new EvolutionIterator<>(
0580 this::evolve,
0581 () -> evolutionStart(population, generation)
0582 );
0583 }
0584
0585 private EvolutionStart<G, C> evolutionStart(
0586 final Population<G, C> population,
0587 final long generation
0588 ) {
0589 final Stream<Phenotype<G, C>> stream = Stream.concat(
0590 population.stream()
0591 .map(p -> p.newInstance(
0592 p.getGeneration(),
0593 _fitnessFunction,
0594 _fitnessScaler)),
0595 Stream.generate(() -> newPhenotype(generation))
0596 );
0597
0598 final Population<G, C> pop = stream
0599 .limit(getPopulationSize())
0600 .collect(toPopulation());
0601
0602 return EvolutionStart.of(pop, generation);
0603 }
0604
0605
0606
0607 /* *************************************************************************
0608 * Property access methods.
0609 **************************************************************************/
0610
0611 /**
0612 * Return the fitness function of the GA engine.
0613 *
0614 * @return the fitness function
0615 */
0616 public Function<? super Genotype<G>, ? extends C> getFitnessFunction() {
0617 return _fitnessFunction;
0618 }
0619
0620 /**
0621 * Return the fitness scaler of the GA engine.
0622 *
0623 * @return the fitness scaler
0624 */
0625 public Function<? super C, ? extends C> getFitnessScaler() {
0626 return _fitnessScaler;
0627 }
0628
0629 /**
0630 * Return the used genotype {@link Factory} of the GA. The genotype factory
0631 * is used for creating the initial population and new, random individuals
0632 * when needed (as replacement for invalid and/or died genotypes).
0633 *
0634 * @return the used genotype {@link Factory} of the GA.
0635 */
0636 public Factory<Genotype<G>> getGenotypeFactory() {
0637 return _genotypeFactory;
0638 }
0639
0640 /**
0641 * Return the used survivor {@link Selector} of the GA.
0642 *
0643 * @return the used survivor {@link Selector} of the GA.
0644 */
0645 public Selector<G, C> getSurvivorsSelector() {
0646 return _survivorsSelector;
0647 }
0648
0649 /**
0650 * Return the used offspring {@link Selector} of the GA.
0651 *
0652 * @return the used offspring {@link Selector} of the GA.
0653 */
0654 public Selector<G, C> getOffspringSelector() {
0655 return _offspringSelector;
0656 }
0657
0658 /**
0659 * Return the used {@link Alterer} of the GA.
0660 *
0661 * @return the used {@link Alterer} of the GA.
0662 */
0663 public Alterer<G, C> getAlterer() {
0664 return _alterer;
0665 }
0666
0667 /**
0668 * Return the number of selected offsprings.
0669 *
0670 * @return the number of selected offsprings
0671 */
0672 public int getOffspringCount() {
0673 return _offspringCount;
0674 }
0675
0676 /**
0677 * The number of selected survivors.
0678 *
0679 * @return the number of selected survivors
0680 */
0681 public int getSurvivorsCount() {
0682 return _survivorsCount;
0683 }
0684
0685 /**
0686 * Return the number of individuals of a population.
0687 *
0688 * @return the number of individuals of a population
0689 */
0690 public int getPopulationSize() {
0691 return _offspringCount + _survivorsCount;
0692 }
0693
0694 /**
0695 * Return the maximal allowed phenotype age.
0696 *
0697 * @return the maximal allowed phenotype age
0698 */
0699 public long getMaximalPhenotypeAge() {
0700 return _maximalPhenotypeAge;
0701 }
0702
0703 /**
0704 * Return the optimization strategy.
0705 *
0706 * @return the optimization strategy
0707 */
0708 public Optimize getOptimize() {
0709 return _optimize;
0710 }
0711
0712 /**
0713 * Return the {@link Clock} the engine is using for measuring the execution
0714 * time.
0715 *
0716 * @return the clock used for measuring the execution time
0717 */
0718 public Clock getClock() {
0719 return _clock;
0720 }
0721
0722 /**
0723 * Return the {@link Executor} the engine is using for executing the
0724 * evolution steps.
0725 *
0726 * @return the executor used for performing the evolution steps
0727 */
0728 public Executor getExecutor() {
0729 return _executor.get();
0730 }
0731
0732
0733 /* *************************************************************************
0734 * Builder methods.
0735 **************************************************************************/
0736
0737 /**
0738 * Create a new evolution {@code Engine.Builder} initialized with the values
0739 * of the current evolution {@code Engine}. With this method, the evolution
0740 * engine can serve as a template for an new one.
0741 *
0742 * @return a new engine builder
0743 */
0744 public Builder<G, C> builder() {
0745 return new Builder<>(_genotypeFactory, _fitnessFunction)
0746 .alterers(_alterer)
0747 .clock(_clock)
0748 .executor(_executor.get())
0749 .fitnessScaler(_fitnessScaler)
0750 .maximalPhenotypeAge(_maximalPhenotypeAge)
0751 .offspringFraction((double)_offspringCount/(double)getPopulationSize())
0752 .offspringSelector(_offspringSelector)
0753 .optimize(_optimize)
0754 .phenotypeValidator(_validator)
0755 .populationSize(getPopulationSize())
0756 .survivorsSelector(_survivorsSelector)
0757 .individualCreationRetries(_individualCreationRetries);
0758 }
0759
0760 /**
0761 * Create a new evolution {@code Engine.Builder} for the given
0762 * {@link Problem}.
0763 *
0764 * @since 3.4
0765 *
0766 * @param problem the problem to be solved by the evolution {@code Engine}
0767 * @param <T> the (<i>native</i>) argument type of the problem fitness function
0768 * @param <G> the gene type the evolution engine is working with
0769 * @param <C> the result type of the fitness function
0770 * @return Create a new evolution {@code Engine.Builder}
0771 */
0772 public static <T, G extends Gene<?, G>, C extends Comparable<? super C>>
0773 Builder<G, C> builder(final Problem<T, G, C> problem) {
0774 return builder(problem.fitness(), problem.codec());
0775 }
0776
0777 /**
0778 * Create a new evolution {@code Engine.Builder} with the given fitness
0779 * function and genotype factory.
0780 *
0781 * @param ff the fitness function
0782 * @param genotypeFactory the genotype factory
0783 * @param <G> the gene type
0784 * @param <C> the fitness function result type
0785 * @return a new engine builder
0786 * @throws java.lang.NullPointerException if one of the arguments is
0787 * {@code null}.
0788 */
0789 public static <G extends Gene<?, G>, C extends Comparable<? super C>>
0790 Builder<G, C> builder(
0791 final Function<? super Genotype<G>, ? extends C> ff,
0792 final Factory<Genotype<G>> genotypeFactory
0793 ) {
0794 return new Builder<>(genotypeFactory, ff);
0795 }
0796
0797 /**
0798 * Create a new evolution {@code Engine.Builder} with the given fitness
0799 * function and chromosome templates.
0800 *
0801 * @param ff the fitness function
0802 * @param chromosome the first chromosome
0803 * @param chromosomes the chromosome templates
0804 * @param <G> the gene type
0805 * @param <C> the fitness function result type
0806 * @return a new engine builder
0807 * @throws java.lang.NullPointerException if one of the arguments is
0808 * {@code null}.
0809 */
0810 @SafeVarargs
0811 public static <G extends Gene<?, G>, C extends Comparable<? super C>>
0812 Builder<G, C> builder(
0813 final Function<? super Genotype<G>, ? extends C> ff,
0814 final Chromosome<G> chromosome,
0815 final Chromosome<G>... chromosomes
0816 ) {
0817 return new Builder<>(Genotype.of(chromosome, chromosomes), ff);
0818 }
0819
0820 /**
0821 * Create a new evolution {@code Engine.Builder} with the given fitness
0822 * function and problem {@code codec}.
0823 *
0824 * @since 3.2
0825 *
0826 * @param ff the fitness function
0827 * @param codec the problem codec
0828 * @param <T> the fitness function input type
0829 * @param <C> the fitness function result type
0830 * @param <G> the gene type
0831 * @return a new engine builder
0832 * @throws java.lang.NullPointerException if one of the arguments is
0833 * {@code null}.
0834 */
0835 public static <T, G extends Gene<?, G>, C extends Comparable<? super C>>
0836 Builder<G, C> builder(
0837 final Function<? super T, ? extends C> ff,
0838 final Codec<T, G> codec
0839 ) {
0840 return builder(ff.compose(codec.decoder()), codec.encoding());
0841 }
0842
0843
0844 /* *************************************************************************
0845 * Inner classes
0846 **************************************************************************/
0847
0848 /**
0849 * Builder class for building GA {@code Engine} instances.
0850 *
0851 * @see Engine
0852 *
0853 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
0854 * @since 3.0
0855 * @version 3.0
0856 */
0857 public static final class Builder<
0858 G extends Gene<?, G>,
0859 C extends Comparable<? super C>
0860 >
0861 implements Copyable<Builder<G, C>>
0862 {
0863
0864 // No default values for this properties.
0865 private Function<? super Genotype<G>, ? extends C> _fitnessFunction;
0866 private Factory<Genotype<G>> _genotypeFactory;
0867
0868 // This are the properties which default values.
0869 private Function<? super C, ? extends C> _fitnessScaler = a -> a;
0870 private Selector<G, C> _survivorsSelector = new TournamentSelector<>(3);
0871 private Selector<G, C> _offspringSelector = new TournamentSelector<>(3);
0872 private Alterer<G, C> _alterer = Alterer.of(
0873 new SinglePointCrossover<G, C>(0.2),
0874 new Mutator<>(0.15)
0875 );
0876 private Predicate<? super Phenotype<G, C>> _validator = Phenotype::isValid;
0877 private Optimize _optimize = Optimize.MAXIMUM;
0878 private double _offspringFraction = 0.6;
0879 private int _populationSize = 50;
0880 private long _maximalPhenotypeAge = 70;
0881
0882 private Executor _executor = ForkJoinPool.commonPool();
0883 private Clock _clock = NanoClock.systemUTC();
0884
0885 private int _individualCreationRetries = 10;
0886
0887 private Builder(
0888 final Factory<Genotype<G>> genotypeFactory,
0889 final Function<? super Genotype<G>, ? extends C> fitnessFunction
0890 ) {
0891 _genotypeFactory = requireNonNull(genotypeFactory);
0892 _fitnessFunction = requireNonNull(fitnessFunction);
0893 }
0894
0895 /**
0896 * Set the fitness function of the evolution {@code Engine}.
0897 *
0898 * @param function the fitness function to use in the GA {@code Engine}
0899 * @return {@code this} builder, for command chaining
0900 */
0901 public Builder<G, C> fitnessFunction(
0902 Function<? super Genotype<G>, ? extends C> function
0903 ) {
0904 _fitnessFunction = requireNonNull(function);
0905 return this;
0906 }
0907
0908 /**
0909 * Set the fitness scaler of the evolution {@code Engine}. <i>Default
0910 * value is set to the identity function.</i>
0911 *
0912 * @param scaler the fitness scale to use in the GA {@code Engine}
0913 * @return {@code this} builder, for command chaining
0914 */
0915 public Builder<G, C> fitnessScaler(
0916 final Function<? super C, ? extends C> scaler
0917 ) {
0918 _fitnessScaler = requireNonNull(scaler);
0919 return this;
0920 }
0921
0922 /**
0923 * The genotype factory used for creating new individuals.
0924 *
0925 * @param genotypeFactory the genotype factory for creating new
0926 * individuals.
0927 * @return {@code this} builder, for command chaining
0928 */
0929 public Builder<G, C> genotypeFactory(
0930 final Factory<Genotype<G>> genotypeFactory
0931 ) {
0932 _genotypeFactory = requireNonNull(genotypeFactory);
0933 return this;
0934 }
0935
0936 /**
0937 * The selector used for selecting the offspring population. <i>Default
0938 * values is set to {@code TournamentSelector<>(3)}.</i>
0939 *
0940 * @param selector used for selecting the offspring population
0941 * @return {@code this} builder, for command chaining
0942 */
0943 public Builder<G, C> offspringSelector(
0944 final Selector<G, C> selector
0945 ) {
0946 _offspringSelector = requireNonNull(selector);
0947 return this;
0948 }
0949
0950 /**
0951 * The selector used for selecting the survivors population. <i>Default
0952 * values is set to {@code TournamentSelector<>(3)}.</i>
0953 *
0954 * @param selector used for selecting survivors population
0955 * @return {@code this} builder, for command chaining
0956 */
0957 public Builder<G, C> survivorsSelector(
0958 final Selector<G, C> selector
0959 ) {
0960 _survivorsSelector = requireNonNull(selector);
0961 return this;
0962 }
0963
0964 /**
0965 * The selector used for selecting the survivors and offspring
0966 * population. <i>Default values is set to
0967 * {@code TournamentSelector<>(3)}.</i>
0968 *
0969 * @param selector used for selecting survivors and offspring population
0970 * @return {@code this} builder, for command chaining
0971 */
0972 public Builder<G, C> selector(final Selector<G, C> selector) {
0973 _offspringSelector = requireNonNull(selector);
0974 _survivorsSelector = requireNonNull(selector);
0975 return this;
0976 }
0977
0978 /**
0979 * The alterers used for alter the offspring population. <i>Default
0980 * values is set to {@code new SinglePointCrossover<>(0.2)} followed by
0981 * {@code new Mutator<>(0.15)}.</i>
0982 *
0983 * @param first the first alterer used for alter the offspring
0984 * population
0985 * @param rest the rest of the alterers used for alter the offspring
0986 * population
0987 * @return {@code this} builder, for command chaining
0988 * @throws java.lang.NullPointerException if one of the alterers is
0989 * {@code null}.
0990 */
0991 @SafeVarargs
0992 public final Builder<G, C> alterers(
0993 final Alterer<G, C> first,
0994 final Alterer<G, C>... rest
0995 ) {
0996 requireNonNull(first);
0997 Stream.of(rest).forEach(Objects::requireNonNull);
0998
0999 _alterer = rest.length == 0 ?
1000 first :
1001 Alterer.of(rest).compose(first);
1002
1003 return this;
1004 }
1005
1006 /**
1007 * The phenotype validator used for detecting invalid individuals.
1008 * Alternatively it is also possible to set the genotype validator with
1009 * {@link #genotypeFactory(Factory)}, which will replace any
1010 * previously set phenotype validators.
1011 *
1012 * <p><i>Default value is set to {@code Phenotype::isValid}.</i></p>
1013 *
1014 * @since 3.1
1015 *
1016 * @see #genotypeValidator(Predicate)
1017 *
1018 * @param validator the {@code validator} used for validating the
1019 * individuals (phenotypes).
1020 * @return {@code this} builder, for command chaining
1021 * @throws java.lang.NullPointerException if the {@code validator} is
1022 * {@code null}.
1023 */
1024 public Builder<G, C> phenotypeValidator(
1025 final Predicate<? super Phenotype<G, C>> validator
1026 ) {
1027 _validator = requireNonNull(validator);
1028 return this;
1029 }
1030
1031 /**
1032 * The genotype validator used for detecting invalid individuals.
1033 * Alternatively it is also possible to set the phenotype validator with
1034 * {@link #phenotypeValidator(Predicate)}, which will replace any
1035 * previously set genotype validators.
1036 *
1037 * <p><i>Default value is set to {@code Genotype::isValid}.</i></p>
1038 *
1039 * @since 3.1
1040 *
1041 * @see #phenotypeValidator(Predicate)
1042 *
1043 * @param validator the {@code validator} used for validating the
1044 * individuals (genotypes).
1045 * @return {@code this} builder, for command chaining
1046 * @throws java.lang.NullPointerException if the {@code validator} is
1047 * {@code null}.
1048 */
1049 public Builder<G, C> genotypeValidator(
1050 final Predicate<? super Genotype<G>> validator
1051 ) {
1052 requireNonNull(validator);
1053
1054 _validator = pt -> validator.test(pt.getGenotype());
1055 return this;
1056 }
1057
1058 /**
1059 * The optimization strategy used by the engine. <i>Default values is
1060 * set to {@code Optimize.MAXIMUM}.</i>
1061 *
1062 * @param optimize the optimization strategy used by the engine
1063 * @return {@code this} builder, for command chaining
1064 */
1065 public Builder<G, C> optimize(final Optimize optimize) {
1066 _optimize = requireNonNull(optimize);
1067 return this;
1068 }
1069
1070 /**
1071 * Set to a fitness maximizing strategy.
1072 *
1073 * @since 3.4
1074 *
1075 * @return {@code this} builder, for command chaining
1076 */
1077 public Builder<G, C> maximizing() {
1078 return optimize(Optimize.MAXIMUM);
1079 }
1080
1081 /**
1082 * Set to a fitness minimizing strategy.
1083 *
1084 * @since 3.4
1085 *
1086 * @return {@code this} builder, for command chaining
1087 */
1088 public Builder<G, C> minimizing() {
1089 return optimize(Optimize.MINIMUM);
1090 }
1091
1092 /**
1093 * The offspring fraction. <i>Default values is set to {@code 0.6}.</i>
1094 *
1095 * @param fraction the offspring fraction
1096 * @return {@code this} builder, for command chaining
1097 * @throws java.lang.IllegalArgumentException if the fraction is not
1098 * within the range [0, 1].
1099 */
1100 public Builder<G, C> offspringFraction(final double fraction) {
1101 _offspringFraction = probability(fraction);
1102 return this;
1103 }
1104
1105 /**
1106 * The number of individuals which form the population. <i>Default
1107 * values is set to {@code 50}.</i>
1108 *
1109 * @param size the number of individuals of a population
1110 * @return {@code this} builder, for command chaining
1111 * @throws java.lang.IllegalArgumentException if {@code size < 1}
1112 */
1113 public Builder<G, C> populationSize(final int size) {
1114 if (size < 1) {
1115 throw new IllegalArgumentException(format(
1116 "Population size must be greater than zero, but was %s.", size
1117 ));
1118 }
1119 _populationSize = size;
1120 return this;
1121 }
1122
1123 /**
1124 * The maximal allowed age of a phenotype. <i>Default values is set to
1125 * {@code 70}.</i>
1126 *
1127 * @param age the maximal phenotype age
1128 * @return {@code this} builder, for command chaining
1129 * @throws java.lang.IllegalArgumentException if {@code age < 1}
1130 */
1131 public Builder<G, C> maximalPhenotypeAge(final long age) {
1132 if (age < 1) {
1133 throw new IllegalArgumentException(format(
1134 "Phenotype age must be greater than one, but was %s.", age
1135 ));
1136 }
1137 _maximalPhenotypeAge = age;
1138 return this;
1139 }
1140
1141 /**
1142 * The executor used by the engine.
1143 *
1144 * @param executor the executor used by the engine
1145 * @return {@code this} builder, for command chaining
1146 */
1147 public Builder<G, C> executor(final Executor executor) {
1148 _executor = requireNonNull(executor);
1149 return this;
1150 }
1151
1152 /**
1153 * The clock used for calculating the execution durations.
1154 *
1155 * @param clock the clock used for calculating the execution durations
1156 * @return {@code this} builder, for command chaining
1157 */
1158 public Builder<G, C> clock(final Clock clock) {
1159 _clock = requireNonNull(clock);
1160 return this;
1161 }
1162
1163 /**
1164 * The maximal number of attempt before the {@code Engine} gives up
1165 * creating a valid individual ({@code Phenotype}). <i>Default values is
1166 * set to {@code 10}.</i>
1167 *
1168 * @since 3.1
1169 *
1170 * @param retries the maximal retry count
1171 * @throws IllegalArgumentException if the given retry {@code count} is
1172 * smaller than zero.
1173 * @return {@code this} builder, for command chaining
1174 */
1175 public Builder<G, C> individualCreationRetries(final int retries) {
1176 if (retries < 0) {
1177 throw new IllegalArgumentException(format(
1178 "Retry count must not be negative: %d",
1179 retries
1180 ));
1181 }
1182 _individualCreationRetries = retries;
1183 return this;
1184 }
1185
1186 /**
1187 * Builds an new {@code Engine} instance from the set properties.
1188 *
1189 * @return an new {@code Engine} instance from the set properties
1190 */
1191 public Engine<G, C> build() {
1192 return new Engine<>(
1193 _fitnessFunction,
1194 _fitnessScaler,
1195 _genotypeFactory,
1196 _survivorsSelector,
1197 _offspringSelector,
1198 _alterer,
1199 _validator,
1200 _optimize,
1201 getOffspringCount(),
1202 getSurvivorsCount(),
1203 _maximalPhenotypeAge,
1204 _executor,
1205 _clock,
1206 _individualCreationRetries
1207 );
1208 }
1209
1210 private int getSurvivorsCount() {
1211 return _populationSize - getOffspringCount();
1212 }
1213
1214 private int getOffspringCount() {
1215 return (int)round(_offspringFraction*_populationSize);
1216 }
1217
1218 /**
1219 * Return the used {@link Alterer} of the GA.
1220 *
1221 * @return the used {@link Alterer} of the GA.
1222 */
1223 public Alterer<G, C> getAlterers() {
1224 return _alterer;
1225 }
1226
1227 /**
1228 * Return the {@link Clock} the engine is using for measuring the execution
1229 * time.
1230 *
1231 * @since 3.1
1232 *
1233 * @return the clock used for measuring the execution time
1234 */
1235 public Clock getClock() {
1236 return _clock;
1237 }
1238
1239 /**
1240 * Return the {@link Executor} the engine is using for executing the
1241 * evolution steps.
1242 *
1243 * @since 3.1
1244 *
1245 * @return the executor used for performing the evolution steps
1246 */
1247 public Executor getExecutor() {
1248 return _executor;
1249 }
1250
1251 /**
1252 * Return the fitness function of the GA engine.
1253 *
1254 * @since 3.1
1255 *
1256 * @return the fitness function
1257 */
1258 public Function<? super Genotype<G>, ? extends C> getFitnessFunction() {
1259 return _fitnessFunction;
1260 }
1261
1262 /**
1263 * Return the fitness scaler of the GA engine.
1264 *
1265 * @since 3.1
1266 *
1267 * @return the fitness scaler
1268 */
1269 public Function<? super C, ? extends C> getFitnessScaler() {
1270 return _fitnessScaler;
1271 }
1272
1273 /**
1274 * Return the used genotype {@link Factory} of the GA. The genotype factory
1275 * is used for creating the initial population and new, random individuals
1276 * when needed (as replacement for invalid and/or died genotypes).
1277 *
1278 * @since 3.1
1279 *
1280 * @return the used genotype {@link Factory} of the GA.
1281 */
1282 public Factory<Genotype<G>> getGenotypeFactory() {
1283 return _genotypeFactory;
1284 }
1285
1286 /**
1287 * Return the maximal allowed phenotype age.
1288 *
1289 * @since 3.1
1290 *
1291 * @return the maximal allowed phenotype age
1292 */
1293 public long getMaximalPhenotypeAge() {
1294 return _maximalPhenotypeAge;
1295 }
1296
1297 /**
1298 * Return the offspring fraction.
1299 *
1300 * @return the offspring fraction.
1301 */
1302 public double getOffspringFraction() {
1303 return _offspringFraction;
1304 }
1305
1306 /**
1307 * Return the used offspring {@link Selector} of the GA.
1308 *
1309 * @since 3.1
1310 *
1311 * @return the used offspring {@link Selector} of the GA.
1312 */
1313 public Selector<G, C> getOffspringSelector() {
1314 return _offspringSelector;
1315 }
1316
1317 /**
1318 * Return the used survivor {@link Selector} of the GA.
1319 *
1320 * @since 3.1
1321 *
1322 * @return the used survivor {@link Selector} of the GA.
1323 */
1324 public Selector<G, C> getSurvivorsSelector() {
1325 return _survivorsSelector;
1326 }
1327
1328 /**
1329 * Return the optimization strategy.
1330 *
1331 * @since 3.1
1332 *
1333 * @return the optimization strategy
1334 */
1335 public Optimize getOptimize() {
1336 return _optimize;
1337 }
1338
1339 /**
1340 * Return the number of individuals of a population.
1341 *
1342 * @since 3.1
1343 *
1344 * @return the number of individuals of a population
1345 */
1346 public int getPopulationSize() {
1347 return _populationSize;
1348 }
1349
1350 /**
1351 * Return the maximal number of attempt before the {@code Engine} gives
1352 * up creating a valid individual ({@code Phenotype}).
1353 *
1354 * @since 3.1
1355 *
1356 * @return the maximal number of {@code Phenotype} creation attempts
1357 */
1358 public int getIndividualCreationRetries() {
1359 return _individualCreationRetries;
1360 }
1361
1362 /**
1363 * Create a new builder, with the current configuration.
1364 *
1365 * @since 3.1
1366 *
1367 * @return a new builder, with the current configuration
1368 */
1369 @Override
1370 public Builder<G, C> copy() {
1371 return new Builder<>(_genotypeFactory, _fitnessFunction)
1372 .alterers(_alterer)
1373 .clock(_clock)
1374 .executor(_executor)
1375 .fitnessScaler(_fitnessScaler)
1376 .maximalPhenotypeAge(_maximalPhenotypeAge)
1377 .offspringFraction(_offspringFraction)
1378 .offspringSelector(_offspringSelector)
1379 .phenotypeValidator(_validator)
1380 .optimize(_optimize)
1381 .populationSize(_populationSize)
1382 .survivorsSelector(_survivorsSelector)
1383 .individualCreationRetries(_individualCreationRetries);
1384 }
1385
1386 }
1387 }
|