Engine.java
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     extends Gene<?, G>,
0119     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         extends Gene<?, G>,
0713         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 }