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