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