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