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