001/* 002 * Java Genetic Algorithm Library (jenetics-5.0.0). 003 * Copyright (c) 2007-2019 Franz Wilhelmstötter 004 * 005 * Licensed under the Apache License, Version 2.0 (the "License"); 006 * you may not use this file except in compliance with the License. 007 * You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 * 017 * Author: 018 * Franz Wilhelmstötter (franz.wilhelmstoetter@gmail.com) 019 */ 020package io.jenetics.engine; 021 022import static java.lang.Math.round; 023import static java.lang.String.format; 024import static java.util.Objects.requireNonNull; 025import static java.util.concurrent.CompletableFuture.supplyAsync; 026import static java.util.concurrent.ForkJoinPool.commonPool; 027import static io.jenetics.internal.util.require.probability; 028 029import java.time.Clock; 030import java.util.Objects; 031import java.util.concurrent.CompletableFuture; 032import java.util.concurrent.Executor; 033import java.util.function.Function; 034import java.util.function.Supplier; 035import java.util.function.UnaryOperator; 036import java.util.stream.Stream; 037 038import io.jenetics.Alterer; 039import io.jenetics.AltererResult; 040import io.jenetics.Chromosome; 041import io.jenetics.Gene; 042import io.jenetics.Genotype; 043import io.jenetics.Mutator; 044import io.jenetics.Optimize; 045import io.jenetics.Phenotype; 046import io.jenetics.Selector; 047import io.jenetics.SinglePointCrossover; 048import io.jenetics.TournamentSelector; 049import io.jenetics.internal.util.require; 050import io.jenetics.util.Copyable; 051import io.jenetics.util.Factory; 052import io.jenetics.util.ISeq; 053import io.jenetics.util.MSeq; 054import io.jenetics.util.NanoClock; 055import io.jenetics.util.Seq; 056 057/** 058 * Genetic algorithm <em>engine</em> which is the main class. The following 059 * example shows the main steps in initializing and executing the GA. 060 * 061 * <pre>{@code 062 * public class RealFunction { 063 * // Definition of the fitness function. 064 * private static Double eval(final Genotype<DoubleGene> gt) { 065 * final double x = gt.getGene().doubleValue(); 066 * return cos(0.5 + sin(x))*cos(x); 067 * } 068 * 069 * public static void main(String[] args) { 070 * // Create/configuring the engine via its builder. 071 * final Engine<DoubleGene, Double> engine = Engine 072 * .builder( 073 * RealFunction::eval, 074 * DoubleChromosome.of(0.0, 2.0*PI)) 075 * .populationSize(500) 076 * .optimize(Optimize.MINIMUM) 077 * .alterers( 078 * new Mutator<>(0.03), 079 * new MeanAlterer<>(0.6)) 080 * .build(); 081 * 082 * // Execute the GA (engine). 083 * final Phenotype<DoubleGene, Double> result = engine.stream() 084 * // Truncate the evolution stream if no better individual could 085 * // be found after 5 consecutive generations. 086 * .limit(bySteadyFitness(5)) 087 * // Terminate the evolution after maximal 100 generations. 088 * .limit(100) 089 * .collect(toBestPhenotype()); 090 * } 091 * } 092 * }</pre> 093 * 094 * The architecture allows to decouple the configuration of the engine from the 095 * execution. The {@code Engine} is configured via the {@code Engine.Builder} 096 * class and can't be changed after creation. The actual <i>evolution</i> is 097 * performed by the {@link EvolutionStream}, which is created by the 098 * {@code Engine}. 099 * 100 * @implNote 101 * This class is thread safe: 102 * No mutable state is maintained by the engine. Therefore it is save to 103 * create multiple evolution streams with one engine, which may be actually 104 * used in different threads. 105 * 106 * @see Engine.Builder 107 * @see EvolutionStart 108 * @see EvolutionResult 109 * @see EvolutionStream 110 * @see EvolutionStatistics 111 * @see Codec 112 * 113 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a> 114 * @since 3.0 115 * @version 5.0 116 */ 117public final class Engine< 118 G extends Gene<?, G>, 119 C extends Comparable<? super C> 120> 121 implements 122 Function<EvolutionStart<G, C>, EvolutionResult<G, C>>, 123 EvolutionStreamable<G, C> 124{ 125 126 // Problem definition. 127 private final Evaluator<G, C> _evaluator; 128 private final Factory<Genotype<G>> _genotypeFactory; 129 130 // Evolution parameters. 131 private final Selector<G, C> _survivorsSelector; 132 private final Selector<G, C> _offspringSelector; 133 private final Alterer<G, C> _alterer; 134 private final Optimize _optimize; 135 private final int _offspringCount; 136 private final int _survivorsCount; 137 private final long _maximalPhenotypeAge; 138 139 // Execution context for concurrent execution of evolving steps. 140 private final Executor _executor; 141 private final Clock _clock; 142 143 // Additional parameters. 144 private final Constraint<G, C> _constraint; 145 private final UnaryOperator<EvolutionResult<G, C>> _mapper; 146 147 148 /** 149 * Create a new GA engine with the given parameters. 150 * 151 * @param genotypeFactory the genotype factory this GA is working with. 152 * @param survivorsSelector the selector used for selecting the survivors 153 * @param offspringSelector the selector used for selecting the offspring 154 * @param alterer the alterer used for altering the offspring 155 * @param constraint phenotype constraint which can override the default 156 * implementation the {@link Phenotype#isValid()} method and repairs 157 * invalid phenotypes when needed. 158 * @param optimize the kind of optimization (minimize or maximize) 159 * @param offspringCount the number of the offspring individuals 160 * @param survivorsCount the number of the survivor individuals 161 * @param maximalPhenotypeAge the maximal age of an individual 162 * @param executor the executor used for executing the single evolve steps 163 * @param evaluator the population fitness evaluator 164 * @param clock the clock used for calculating the timing results 165 * @throws NullPointerException if one of the arguments is {@code null} 166 * @throws IllegalArgumentException if the given integer values are smaller 167 * than one. 168 */ 169 Engine( 170 final Evaluator<G, C> evaluator, 171 final Factory<Genotype<G>> genotypeFactory, 172 final Selector<G, C> survivorsSelector, 173 final Selector<G, C> offspringSelector, 174 final Alterer<G, C> alterer, 175 final Constraint<G, C> constraint, 176 final Optimize optimize, 177 final int offspringCount, 178 final int survivorsCount, 179 final long maximalPhenotypeAge, 180 final Executor executor, 181 final Clock clock, 182 final UnaryOperator<EvolutionResult<G, C>> mapper 183 ) { 184 _evaluator = requireNonNull(evaluator); 185 _genotypeFactory = requireNonNull(genotypeFactory); 186 _survivorsSelector = requireNonNull(survivorsSelector); 187 _offspringSelector = requireNonNull(offspringSelector); 188 _alterer = requireNonNull(alterer); 189 _constraint = requireNonNull(constraint); 190 _optimize = requireNonNull(optimize); 191 192 _offspringCount = require.nonNegative(offspringCount); 193 _survivorsCount = require.nonNegative(survivorsCount); 194 _maximalPhenotypeAge = require.positive(maximalPhenotypeAge); 195 196 _executor = requireNonNull(executor); 197 _clock = requireNonNull(clock); 198 _mapper = requireNonNull(mapper); 199 } 200 201 /** 202 * This method is an <i>alias</i> for the {@link #evolve(EvolutionStart)} 203 * method. 204 * 205 * @since 3.1 206 */ 207 @Override 208 public EvolutionResult<G, C> apply(final EvolutionStart<G, C> start) { 209 return evolve(start); 210 } 211 212 /** 213 * Perform one evolution step with the given {@code population} and 214 * {@code generation}. New phenotypes are created with the fitness function 215 * and fitness scaler defined by this <em>engine</em> 216 * <p> 217 * <em>This method is thread-safe.</em> 218 * 219 * @see #evolve(EvolutionStart) 220 * 221 * @param population the population to evolve 222 * @param generation the current generation; used for calculating the 223 * phenotype age. 224 * @return the evolution result 225 * @throws java.lang.NullPointerException if the given {@code population} is 226 * {@code null} 227 * @throws IllegalArgumentException if the given {@code generation} is 228 * smaller then one 229 */ 230 public EvolutionResult<G, C> evolve( 231 final ISeq<Phenotype<G, C>> population, 232 final long generation 233 ) { 234 return evolve(EvolutionStart.of(population, generation)); 235 } 236 237 /** 238 * Perform one evolution step with the given evolution {@code start} object 239 * New phenotypes are created with the fitness function and fitness scaler 240 * defined by this <em>engine</em> 241 * <p> 242 * <em>This method is thread-safe.</em> 243 * 244 * @since 3.1 245 * @see #evolve(ISeq, long) 246 * 247 * @param start the evolution start object 248 * @return the evolution result 249 * @throws java.lang.NullPointerException if the given evolution 250 * {@code start} is {@code null} 251 */ 252 public EvolutionResult<G, C> evolve(final EvolutionStart<G, C> start) { 253 final EvolutionTiming timing = new EvolutionTiming(_clock); 254 timing.evolve.start(); 255 256 // Initial evaluation of the population. 257 final ISeq<Phenotype<G, C>> evaluated = timing.evaluation.timing(() -> 258 evaluate(start.getPopulation()) 259 ); 260 261 // Select the offspring population. 262 final CompletableFuture<ISeq<Phenotype<G, C>>> offspring = 263 supplyAsync(() -> 264 timing.offspringSelection.timing(() -> 265 selectOffspring(evaluated) 266 ), 267 _executor 268 ); 269 270 // Select the survivor population. 271 final CompletableFuture<ISeq<Phenotype<G, C>>> survivors = 272 supplyAsync(() -> 273 timing.survivorsSelection.timing(() -> 274 selectSurvivors(evaluated) 275 ), 276 _executor 277 ); 278 279 // Altering the offspring population. 280 final CompletableFuture<AltererResult<G, C>> alteredOffspring = 281 offspring.thenApplyAsync(off -> 282 timing.offspringAlter.timing(() -> 283 _alterer.alter(off, start.getGeneration()) 284 ), 285 _executor 286 ); 287 288 // Filter and replace invalid and old survivor individuals. 289 final CompletableFuture<FilterResult<G, C>> filteredSurvivors = 290 survivors.thenApplyAsync(sur -> 291 timing.survivorFilter.timing(() -> 292 filter(sur, start.getGeneration()) 293 ), 294 _executor 295 ); 296 297 // Filter and replace invalid and old offspring individuals. 298 final CompletableFuture<FilterResult<G, C>> filteredOffspring = 299 alteredOffspring.thenApplyAsync(off -> 300 timing.offspringFilter.timing(() -> 301 filter(off.getPopulation(), start.getGeneration()) 302 ), 303 _executor 304 ); 305 306 // Combining survivors and offspring to the new population. 307 final CompletableFuture<ISeq<Phenotype<G, C>>> population = 308 filteredSurvivors.thenCombineAsync( 309 filteredOffspring, 310 (s, o) -> ISeq.of(s.population.append(o.population)), 311 _executor 312 ); 313 314 // Evaluate the fitness-function and wait for result. 315 final ISeq<Phenotype<G, C>> pop = population.join(); 316 final ISeq<Phenotype<G, C>> result = timing.evaluation.timing(() -> 317 evaluate(pop) 318 ); 319 320 final int killCount = 321 filteredOffspring.join().killCount + 322 filteredSurvivors.join().killCount; 323 324 final int invalidCount = 325 filteredOffspring.join().invalidCount + 326 filteredSurvivors.join().invalidCount; 327 328 final int alterationCount = alteredOffspring.join().getAlterations(); 329 330 EvolutionResult<G, C> er = EvolutionResult.of( 331 _optimize, 332 result, 333 start.getGeneration(), 334 timing.toDurations(), 335 killCount, 336 invalidCount, 337 alterationCount 338 ); 339 if (!UnaryOperator.identity().equals(_mapper)) { 340 final EvolutionResult<G, C> mapped = _mapper.apply(er); 341 er = er.with(timing.evaluation.timing(() -> 342 evaluate(mapped.getPopulation()) 343 )); 344 } 345 346 timing.evolve.stop(); 347 return er.with(timing.toDurations()); 348 } 349 350 // Selects the survivors population. A new population object is returned. 351 private ISeq<Phenotype<G, C>> 352 selectSurvivors(final ISeq<Phenotype<G, C>> population) { 353 return _survivorsCount > 0 354 ?_survivorsSelector.select(population, _survivorsCount, _optimize) 355 : ISeq.empty(); 356 } 357 358 // Selects the offspring population. A new population object is returned. 359 private ISeq<Phenotype<G, C>> 360 selectOffspring(final ISeq<Phenotype<G, C>> population) { 361 return _offspringCount > 0 362 ? _offspringSelector.select(population, _offspringCount, _optimize) 363 : ISeq.empty(); 364 } 365 366 // Filters out invalid and old individuals. Filtering is done in place. 367 private FilterResult<G, C> filter( 368 final Seq<Phenotype<G, C>> population, 369 final long generation 370 ) { 371 int killCount = 0; 372 int invalidCount = 0; 373 374 final MSeq<Phenotype<G, C>> pop = MSeq.of(population); 375 for (int i = 0, n = pop.size(); i < n; ++i) { 376 final Phenotype<G, C> individual = pop.get(i); 377 378 if (!_constraint.test(individual)) { 379 pop.set(i, _constraint.repair(individual, generation)); 380 ++invalidCount; 381 } else if (individual.getAge(generation) > _maximalPhenotypeAge) { 382 pop.set(i, Phenotype.of(_genotypeFactory.newInstance(), generation)); 383 ++killCount; 384 } 385 } 386 387 return new FilterResult<>(pop.toISeq(), killCount, invalidCount); 388 } 389 390 391 /* ************************************************************************* 392 * Evaluation methods. 393 **************************************************************************/ 394 395 /** 396 * Evaluates the fitness function of the given population with the configured 397 * {@link Evaluator} of this engine and returns a new population 398 * with its fitness value assigned. 399 * 400 * @since 5.0 401 * 402 * @see Evaluator 403 * @see Evaluator#eval(Seq) 404 * 405 * @param population the population to evaluate 406 * @return a new population with assigned fitness values 407 * @throws IllegalStateException if the configured fitness function doesn't 408 * return a population with the same size as the input population. 409 * This exception is also thrown if one of the populations 410 * phenotype has no fitness value assigned. 411 */ 412 public ISeq<Phenotype<G, C>> evaluate(final Seq<Phenotype<G, C>> population) { 413 final ISeq<Phenotype<G, C>> evaluated = _evaluator.eval(population); 414 415 if (population.size() != evaluated.size()) { 416 throw new IllegalStateException(format( 417 "Expected %d individuals, but got %d. " + 418 "Check your evaluator function.", 419 population.size(), evaluated.size() 420 )); 421 } 422 if (!evaluated.forAll(Phenotype::isEvaluated)) { 423 throw new IllegalStateException( 424 "Some phenotypes have no assigned fitness value. " + 425 "Check your evaluator function." 426 ); 427 } 428 429 return evaluated; 430 } 431 432 433 /* ************************************************************************* 434 * Evolution Stream creation. 435 **************************************************************************/ 436 437 @Override 438 public EvolutionStream<G, C> 439 stream(final Supplier<EvolutionStart<G, C>> start) { 440 return EvolutionStream.of(evolutionStart(start), this::evolve); 441 } 442 443 @Override 444 public EvolutionStream<G, C> stream(final EvolutionInit<G> init) { 445 return stream(evolutionStart(init)); 446 } 447 448 private Supplier<EvolutionStart<G, C>> 449 evolutionStart(final Supplier<EvolutionStart<G, C>> start) { 450 return () -> { 451 final EvolutionStart<G, C> es = start.get(); 452 final ISeq<Phenotype<G, C>> population = es.getPopulation(); 453 final long gen = es.getGeneration(); 454 455 final Stream<Phenotype<G, C>> stream = Stream.concat( 456 population.stream(), 457 _genotypeFactory.instances().map(gt -> Phenotype.of(gt, gen)) 458 ); 459 460 final ISeq<Phenotype<G, C>> pop = stream 461 .limit(getPopulationSize()) 462 .collect(ISeq.toISeq()); 463 464 return EvolutionStart.of(pop, gen); 465 }; 466 } 467 468 private Supplier<EvolutionStart<G, C>> 469 evolutionStart(final EvolutionInit<G> init) { 470 return evolutionStart(() -> EvolutionStart.of( 471 init.getPopulation() 472 .map(gt -> Phenotype.of(gt, init.getGeneration())), 473 init.getGeneration()) 474 ); 475 } 476 477 /* ************************************************************************* 478 * Property access methods. 479 **************************************************************************/ 480 481 /** 482 * Return the used genotype {@link Factory} of the GA. The genotype factory 483 * is used for creating the initial population and new, random individuals 484 * when needed (as replacement for invalid and/or died genotypes). 485 * 486 * @return the used genotype {@link Factory} of the GA. 487 */ 488 public Factory<Genotype<G>> getGenotypeFactory() { 489 return _genotypeFactory; 490 } 491 492 /** 493 * Return the constraint of the evolution problem. 494 * 495 * @since 5.0 496 * 497 * @return the constraint of the evolution problem 498 */ 499 public Constraint<G, C> getConstraint() { 500 return _constraint; 501 } 502 503 /** 504 * Return the used survivor {@link Selector} of the GA. 505 * 506 * @return the used survivor {@link Selector} of the GA. 507 */ 508 public Selector<G, C> getSurvivorsSelector() { 509 return _survivorsSelector; 510 } 511 512 /** 513 * Return the used offspring {@link Selector} of the GA. 514 * 515 * @return the used offspring {@link Selector} of the GA. 516 */ 517 public Selector<G, C> getOffspringSelector() { 518 return _offspringSelector; 519 } 520 521 /** 522 * Return the used {@link Alterer} of the GA. 523 * 524 * @return the used {@link Alterer} of the GA. 525 */ 526 public Alterer<G, C> getAlterer() { 527 return _alterer; 528 } 529 530 /** 531 * Return the number of selected offsprings. 532 * 533 * @return the number of selected offsprings 534 */ 535 public int getOffspringCount() { 536 return _offspringCount; 537 } 538 539 /** 540 * The number of selected survivors. 541 * 542 * @return the number of selected survivors 543 */ 544 public int getSurvivorsCount() { 545 return _survivorsCount; 546 } 547 548 /** 549 * Return the number of individuals of a population. 550 * 551 * @return the number of individuals of a population 552 */ 553 public int getPopulationSize() { 554 return _offspringCount + _survivorsCount; 555 } 556 557 /** 558 * Return the maximal allowed phenotype age. 559 * 560 * @return the maximal allowed phenotype age 561 */ 562 public long getMaximalPhenotypeAge() { 563 return _maximalPhenotypeAge; 564 } 565 566 /** 567 * Return the optimization strategy. 568 * 569 * @return the optimization strategy 570 */ 571 public Optimize getOptimize() { 572 return _optimize; 573 } 574 575 /** 576 * Return the {@link Clock} the engine is using for measuring the execution 577 * time. 578 * 579 * @return the clock used for measuring the execution time 580 */ 581 public Clock getClock() { 582 return _clock; 583 } 584 585 /** 586 * Return the {@link Executor} the engine is using for executing the 587 * evolution steps. 588 * 589 * @return the executor used for performing the evolution steps 590 */ 591 public Executor getExecutor() { 592 return _executor; 593 } 594 595 /** 596 * Return the evolution result mapper. 597 * 598 * @since 4.0 599 * 600 * @return the evolution result mapper 601 */ 602 public UnaryOperator<EvolutionResult<G, C>> getMapper() { 603 return _mapper; 604 } 605 606 /** 607 * Create a new evolution {@code Engine.Builder} initialized with the values 608 * of the current evolution {@code Engine}. With this method, the evolution 609 * engine can serve as a template for a new one. 610 * 611 * @return a new engine builder 612 */ 613 public Builder<G, C> builder() { 614 return new Builder<>(_evaluator, _genotypeFactory) 615 .alterers(_alterer) 616 .clock(_clock) 617 .executor(_executor) 618 .maximalPhenotypeAge(_maximalPhenotypeAge) 619 .offspringFraction((double)_offspringCount/(double)getPopulationSize()) 620 .offspringSelector(_offspringSelector) 621 .optimize(_optimize) 622 .constraint(_constraint) 623 .populationSize(getPopulationSize()) 624 .survivorsSelector(_survivorsSelector) 625 .mapping(_mapper); 626 } 627 628 629 /* ************************************************************************* 630 * Static Builder methods. 631 **************************************************************************/ 632 633 /** 634 * Create a new evolution {@code Engine.Builder} with the given fitness 635 * function and genotype factory. 636 * 637 * @param ff the fitness function 638 * @param gtf the genotype factory 639 * @param <G> the gene type 640 * @param <C> the fitness function result type 641 * @return a new engine builder 642 * @throws java.lang.NullPointerException if one of the arguments is 643 * {@code null}. 644 */ 645 public static <G extends Gene<?, G>, C extends Comparable<? super C>> 646 Builder<G, C> builder( 647 final Function<? super Genotype<G>, ? extends C> ff, 648 final Factory<Genotype<G>> gtf 649 ) { 650 return new Builder<>(Evaluators.concurrent(ff, commonPool()), gtf); 651 } 652 653 /** 654 * Create a new evolution {@code Engine.Builder} with the given fitness 655 * function and problem {@code codec}. 656 * 657 * @since 3.2 658 * 659 * @param ff the fitness evaluator 660 * @param codec the problem codec 661 * @param <T> the fitness function input type 662 * @param <C> the fitness function result type 663 * @param <G> the gene type 664 * @return a new engine builder 665 * @throws java.lang.NullPointerException if one of the arguments is 666 * {@code null}. 667 */ 668 public static <T, G extends Gene<?, G>, C extends Comparable<? super C>> 669 Builder<G, C> builder( 670 final Function<? super T, ? extends C> ff, 671 final Codec<T, G> codec 672 ) { 673 return builder(ff.compose(codec.decoder()), codec.encoding()); 674 } 675 676 /** 677 * Create a new evolution {@code Engine.Builder} for the given 678 * {@link Problem}. 679 * 680 * @since 3.4 681 * 682 * @param problem the problem to be solved by the evolution {@code Engine} 683 * @param <T> the (<i>native</i>) argument type of the problem fitness function 684 * @param <G> the gene type the evolution engine is working with 685 * @param <C> the result type of the fitness function 686 * @return Create a new evolution {@code Engine.Builder} 687 */ 688 public static <T, G extends Gene<?, G>, C extends Comparable<? super C>> 689 Builder<G, C> builder(final Problem<T, G, C> problem) { 690 return builder(problem.fitness(), problem.codec()); 691 } 692 693 /** 694 * Create a new evolution {@code Engine.Builder} with the given fitness 695 * function and chromosome templates. 696 * 697 * @param ff the fitness function 698 * @param chromosome the first chromosome 699 * @param chromosomes the chromosome templates 700 * @param <G> the gene type 701 * @param <C> the fitness function result type 702 * @return a new engine builder 703 * @throws java.lang.NullPointerException if one of the arguments is 704 * {@code null}. 705 */ 706 @SafeVarargs 707 public static <G extends Gene<?, G>, C extends Comparable<? super C>> 708 Builder<G, C> builder( 709 final Function<? super Genotype<G>, ? extends C> ff, 710 final Chromosome<G> chromosome, 711 final Chromosome<G>... chromosomes 712 ) { 713 return builder(ff, Genotype.of(chromosome, chromosomes)); 714 } 715 716 717 /* ************************************************************************* 718 * Inner classes 719 **************************************************************************/ 720 721 722 /** 723 * Builder class for building GA {@code Engine} instances. 724 * 725 * @see Engine 726 * 727 * @param <G> the gene type 728 * @param <C> the fitness function result type 729 * 730 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a> 731 * @since 3.0 732 * @version 5.0 733 */ 734 public static final class Builder< 735 G extends Gene<?, G>, 736 C extends Comparable<? super C> 737 > 738 implements Copyable<Builder<G, C>> 739 { 740 741 // No default values for this properties. 742 private final Evaluator<G, C> _evaluator; 743 private final Factory<Genotype<G>> _genotypeFactory; 744 745 // This are the properties which default values. 746 private Selector<G, C> _survivorsSelector = new TournamentSelector<>(3); 747 private Selector<G, C> _offspringSelector = new TournamentSelector<>(3); 748 private Alterer<G, C> _alterer = Alterer.of( 749 new SinglePointCrossover<G, C>(0.2), 750 new Mutator<>(0.15) 751 ); 752 private Constraint<G, C> _constraint; 753 private Optimize _optimize = Optimize.MAXIMUM; 754 private double _offspringFraction = 0.6; 755 private int _populationSize = 50; 756 private long _maximalPhenotypeAge = 70; 757 758 // Engine execution environment. 759 private Executor _executor = commonPool(); 760 private Clock _clock = NanoClock.systemUTC(); 761 762 private UnaryOperator<EvolutionResult<G, C>> _mapper = UnaryOperator.identity(); 763 764 /** 765 * Create a new evolution {@code Engine.Builder} with the given fitness 766 * evaluator and genotype factory. This is the most general way for 767 * creating an engine builder. 768 * 769 * @since 5.0 770 * 771 * @see Engine#builder(Function, Codec) 772 * @see Engine#builder(Function, Factory) 773 * @see Engine#builder(Problem) 774 * @see Engine#builder(Function, Chromosome, Chromosome[]) 775 * 776 * @param evaluator the fitness evaluator 777 * @param genotypeFactory the genotype factory 778 * @throws NullPointerException if one of the arguments is {@code null}. 779 */ 780 public Builder( 781 final Evaluator<G, C> evaluator, 782 final Factory<Genotype<G>> genotypeFactory 783 ) { 784 _genotypeFactory = requireNonNull(genotypeFactory); 785 _evaluator = requireNonNull(evaluator); 786 } 787 788 /** 789 * The selector used for selecting the offspring population. <i>Default 790 * values is set to {@code TournamentSelector<>(3)}.</i> 791 * 792 * @param selector used for selecting the offspring population 793 * @return {@code this} builder, for command chaining 794 */ 795 public Builder<G, C> offspringSelector( 796 final Selector<G, C> selector 797 ) { 798 _offspringSelector = requireNonNull(selector); 799 return this; 800 } 801 802 /** 803 * The selector used for selecting the survivors population. <i>Default 804 * values is set to {@code TournamentSelector<>(3)}.</i> 805 * 806 * @param selector used for selecting survivors population 807 * @return {@code this} builder, for command chaining 808 */ 809 public Builder<G, C> survivorsSelector( 810 final Selector<G, C> selector 811 ) { 812 _survivorsSelector = requireNonNull(selector); 813 return this; 814 } 815 816 /** 817 * The selector used for selecting the survivors and offspring 818 * population. <i>Default values is set to 819 * {@code TournamentSelector<>(3)}.</i> 820 * 821 * @param selector used for selecting survivors and offspring population 822 * @return {@code this} builder, for command chaining 823 */ 824 public Builder<G, C> selector(final Selector<G, C> selector) { 825 _offspringSelector = requireNonNull(selector); 826 _survivorsSelector = requireNonNull(selector); 827 return this; 828 } 829 830 /** 831 * The alterers used for alter the offspring population. <i>Default 832 * values is set to {@code new SinglePointCrossover<>(0.2)} followed by 833 * {@code new Mutator<>(0.15)}.</i> 834 * 835 * @param first the first alterer used for alter the offspring 836 * population 837 * @param rest the rest of the alterers used for alter the offspring 838 * population 839 * @return {@code this} builder, for command chaining 840 * @throws java.lang.NullPointerException if one of the alterers is 841 * {@code null}. 842 */ 843 @SafeVarargs 844 public final Builder<G, C> alterers( 845 final Alterer<G, C> first, 846 final Alterer<G, C>... rest 847 ) { 848 requireNonNull(first); 849 Stream.of(rest).forEach(Objects::requireNonNull); 850 851 _alterer = rest.length == 0 852 ? first 853 : Alterer.of(rest).compose(first); 854 855 return this; 856 } 857 858 /** 859 * The phenotype constraint is used for detecting invalid individuals 860 * and repairing them. 861 * 862 * <p><i>Default implementation uses {@code Phenotype::isValid} for 863 * validating the phenotype.</i></p> 864 * 865 * @since 5.0 866 * 867 * @param constraint phenotype constraint which can override the default 868 * implementation the {@link Phenotype#isValid()} method and repairs 869 * invalid phenotypes when needed. 870 * @return {@code this} builder, for command chaining 871 * @throws java.lang.NullPointerException if the {@code validator} is 872 * {@code null}. 873 */ 874 public Builder<G, C> constraint(final Constraint<G, C> constraint) { 875 _constraint = requireNonNull(constraint); 876 return this; 877 } 878 879 /** 880 * The optimization strategy used by the engine. <i>Default values is 881 * set to {@code Optimize.MAXIMUM}.</i> 882 * 883 * @param optimize the optimization strategy used by the engine 884 * @return {@code this} builder, for command chaining 885 */ 886 public Builder<G, C> optimize(final Optimize optimize) { 887 _optimize = requireNonNull(optimize); 888 return this; 889 } 890 891 /** 892 * Set to a fitness maximizing strategy. 893 * 894 * @since 3.4 895 * 896 * @return {@code this} builder, for command chaining 897 */ 898 public Builder<G, C> maximizing() { 899 return optimize(Optimize.MAXIMUM); 900 } 901 902 /** 903 * Set to a fitness minimizing strategy. 904 * 905 * @since 3.4 906 * 907 * @return {@code this} builder, for command chaining 908 */ 909 public Builder<G, C> minimizing() { 910 return optimize(Optimize.MINIMUM); 911 } 912 913 /** 914 * The offspring fraction. <i>Default values is set to {@code 0.6}.</i> 915 * This method call is equivalent to 916 * {@code survivorsFraction(1 - offspringFraction)} and will override 917 * any previously set survivors-fraction. 918 * 919 * @see #survivorsFraction(double) 920 * 921 * @param fraction the offspring fraction 922 * @return {@code this} builder, for command chaining 923 * @throws java.lang.IllegalArgumentException if the fraction is not 924 * within the range [0, 1]. 925 */ 926 public Builder<G, C> offspringFraction(final double fraction) { 927 _offspringFraction = probability(fraction); 928 return this; 929 } 930 931 /** 932 * The survivors fraction. <i>Default values is set to {@code 0.4}.</i> 933 * This method call is equivalent to 934 * {@code offspringFraction(1 - survivorsFraction)} and will override 935 * any previously set offspring-fraction. 936 * 937 * @since 3.8 938 * 939 * @see #offspringFraction(double) 940 * 941 * @param fraction the survivors fraction 942 * @return {@code this} builder, for command chaining 943 * @throws java.lang.IllegalArgumentException if the fraction is not 944 * within the range [0, 1]. 945 */ 946 public Builder<G, C> survivorsFraction(final double fraction) { 947 _offspringFraction = 1.0 - probability(fraction); 948 return this; 949 } 950 951 /** 952 * The number of offspring individuals. 953 * 954 * @since 3.8 955 * 956 * @param size the number of offspring individuals. 957 * @return {@code this} builder, for command chaining 958 * @throws java.lang.IllegalArgumentException if the size is not 959 * within the range [0, population-size]. 960 */ 961 public Builder<G, C> offspringSize(final int size) { 962 if (size < 0) { 963 throw new IllegalArgumentException(format( 964 "Offspring size must be greater or equal zero, but was %s.", 965 size 966 )); 967 } 968 969 return offspringFraction((double)size/(double)_populationSize); 970 } 971 972 /** 973 * The number of survivors. 974 * 975 * @since 3.8 976 * 977 * @param size the number of survivors. 978 * @return {@code this} builder, for command chaining 979 * @throws java.lang.IllegalArgumentException if the size is not 980 * within the range [0, population-size]. 981 */ 982 public Builder<G, C> survivorsSize(final int size) { 983 if (size < 0) { 984 throw new IllegalArgumentException(format( 985 "Survivors must be greater or equal zero, but was %s.", 986 size 987 )); 988 } 989 990 return survivorsFraction((double)size/(double)_populationSize); 991 } 992 993 /** 994 * The number of individuals which form the population. <i>Default 995 * values is set to {@code 50}.</i> 996 * 997 * @param size the number of individuals of a population 998 * @return {@code this} builder, for command chaining 999 * @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}