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