001/* 002 * Java Genetic Algorithm Library (jenetics-3.5.0). 003 * Copyright (c) 2007-2016 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@gmx.at) 019 */ 020package org.jenetics.engine; 021 022import static java.lang.Math.round; 023import static java.lang.String.format; 024import static java.util.Objects.requireNonNull; 025import static org.jenetics.Population.toPopulation; 026import static org.jenetics.internal.util.require.probability; 027 028import java.time.Clock; 029import java.util.Iterator; 030import java.util.Objects; 031import java.util.concurrent.CompletableFuture; 032import java.util.concurrent.Executor; 033import java.util.concurrent.ForkJoinPool; 034import java.util.function.Function; 035import java.util.function.Predicate; 036import java.util.stream.Stream; 037import java.util.stream.StreamSupport; 038 039import org.jenetics.internal.util.Concurrency; 040import org.jenetics.internal.util.require; 041 042import org.jenetics.Alterer; 043import org.jenetics.Chromosome; 044import org.jenetics.Gene; 045import org.jenetics.Genotype; 046import org.jenetics.Mutator; 047import org.jenetics.Optimize; 048import org.jenetics.Phenotype; 049import org.jenetics.Population; 050import org.jenetics.Selector; 051import org.jenetics.SinglePointCrossover; 052import org.jenetics.TournamentSelector; 053import org.jenetics.util.Copyable; 054import org.jenetics.util.Factory; 055import org.jenetics.util.NanoClock; 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 * <p> 100 * <em> 101 * <b>This class is thread safe:</b> 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 * </em> 106 * 107 * @see Engine.Builder 108 * @see EvolutionStart 109 * @see EvolutionResult 110 * @see EvolutionStream 111 * @see EvolutionStatistics 112 * @see Codec 113 * 114 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a> 115 * @since 3.0 116 * @version 3.2 117 */ 118public final class Engine< 119 G extends Gene<?, G>, 120 C extends Comparable<? super C> 121> 122 implements Function<EvolutionStart<G, C>, EvolutionResult<G, C>> 123{ 124 125 // Needed context for population evolving. 126 private final Function<? super Genotype<G>, ? extends C> _fitnessFunction; 127 private final Function<? super C, ? extends C> _fitnessScaler; 128 private final Factory<Genotype<G>> _genotypeFactory; 129 private final Selector<G, C> _survivorsSelector; 130 private final Selector<G, C> _offspringSelector; 131 private final Alterer<G, C> _alterer; 132 private final Predicate<? super Phenotype<G, C>> _validator; 133 private final Optimize _optimize; 134 private final int _offspringCount; 135 private final int _survivorsCount; 136 private final long _maximalPhenotypeAge; 137 138 // Execution context for concurrent execution of evolving steps. 139 private final TimedExecutor _executor; 140 private final Clock _clock; 141 142 // Additional parameters. 143 private final int _individualCreationRetries; 144 145 146 /** 147 * Create a new GA engine with the given parameters. 148 * 149 * @param genotypeFactory the genotype factory this GA is working with. 150 * @param fitnessFunction the fitness function this GA is using. 151 * @param fitnessScaler the fitness scaler this GA is using. 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 validator phenotype validator which can override the default 156 * implementation the {@link Phenotype#isValid()} method. 157 * @param optimize the kind of optimization (minimize or maximize) 158 * @param offspringCount the number of the offspring individuals 159 * @param survivorsCount the number of the survivor individuals 160 * @param maximalPhenotypeAge the maximal age of an individual 161 * @param executor the executor used for executing the single evolve steps 162 * @param clock the clock used for calculating the timing results 163 * @param individualCreationRetries the maximal number of attempts for 164 * creating a valid individual. 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 Function<? super Genotype<G>, ? extends C> fitnessFunction, 171 final Function<? super C, ? extends C> fitnessScaler, 172 final Factory<Genotype<G>> genotypeFactory, 173 final Selector<G, C> survivorsSelector, 174 final Selector<G, C> offspringSelector, 175 final Alterer<G, C> alterer, 176 final Predicate<? super Phenotype<G, C>> validator, 177 final Optimize optimize, 178 final int offspringCount, 179 final int survivorsCount, 180 final long maximalPhenotypeAge, 181 final Executor executor, 182 final Clock clock, 183 final int individualCreationRetries 184 ) { 185 _fitnessFunction = requireNonNull(fitnessFunction); 186 _fitnessScaler = requireNonNull(fitnessScaler); 187 _genotypeFactory = requireNonNull(genotypeFactory); 188 _survivorsSelector = requireNonNull(survivorsSelector); 189 _offspringSelector = requireNonNull(offspringSelector); 190 _alterer = requireNonNull(alterer); 191 _validator = requireNonNull(validator); 192 _optimize = requireNonNull(optimize); 193 194 _offspringCount = require.nonNegative(offspringCount); 195 _survivorsCount = require.nonNegative(survivorsCount); 196 _maximalPhenotypeAge = require.positive(maximalPhenotypeAge); 197 198 _executor = new TimedExecutor(requireNonNull(executor)); 199 _clock = requireNonNull(clock); 200 201 if (individualCreationRetries < 0) { 202 throw new IllegalArgumentException(format( 203 "Retry count must not be negative: %d", 204 individualCreationRetries 205 )); 206 } 207 _individualCreationRetries = individualCreationRetries; 208 } 209 210 /** 211 * Perform one evolution step with the given {@code population} and 212 * {@code generation}. New phenotypes are created with the fitness function 213 * and fitness scaler defined by this <em>engine</em> 214 * <p> 215 * <em>This method is thread-safe.</em> 216 * 217 * @see #evolve(EvolutionStart) 218 * 219 * @param population the population to evolve 220 * @param generation the current generation; used for calculating the 221 * phenotype age. 222 * @return the evolution result 223 * @throws java.lang.NullPointerException if the given {@code population} is 224 * {@code null} 225 * @throws IllegalArgumentException if the given {@code generation} is 226 * smaller then one 227 */ 228 public EvolutionResult<G, C> evolve( 229 final Population<G, C> population, 230 final long generation 231 ) { 232 return evolve(EvolutionStart.of(population, generation)); 233 } 234 235 /** 236 * Perform one evolution step with the given evolution {@code start} object 237 * New phenotypes are created with the fitness function and fitness scaler 238 * defined by this <em>engine</em> 239 * <p> 240 * <em>This method is thread-safe.</em> 241 * 242 * @since 3.1 243 * @see #evolve(org.jenetics.Population, long) 244 * 245 * @param start the evolution start object 246 * @return the evolution result 247 * @throws java.lang.NullPointerException if the given evolution 248 * {@code start} is {@code null} 249 */ 250 public EvolutionResult<G, C> evolve(final EvolutionStart<G, C> start) { 251 final Timer timer = Timer.of().start(); 252 253 final Population<G, C> startPopulation = start.getPopulation(); 254 255 // Initial evaluation of the population. 256 final Timer evaluateTimer = Timer.of(_clock).start(); 257 evaluate(startPopulation); 258 evaluateTimer.stop(); 259 260 // Select the offspring population. 261 final CompletableFuture<TimedResult<Population<G, C>>> offspring = 262 _executor.async(() -> 263 selectOffspring(startPopulation), 264 _clock 265 ); 266 267 // Select the survivor population. 268 final CompletableFuture<TimedResult<Population<G, C>>> survivors = 269 _executor.async(() -> 270 selectSurvivors(startPopulation), 271 _clock 272 ); 273 274 // Altering the offspring population. 275 final CompletableFuture<TimedResult<AlterResult<G, C>>> alteredOffspring = 276 _executor.thenApply(offspring, p -> 277 alter(p.result, start.getGeneration()), 278 _clock 279 ); 280 281 // Filter and replace invalid and to old survivor individuals. 282 final CompletableFuture<TimedResult<FilterResult<G, C>>> filteredSurvivors = 283 _executor.thenApply(survivors, pop -> 284 filter(pop.result, start.getGeneration()), 285 _clock 286 ); 287 288 // Filter and replace invalid and to old offspring individuals. 289 final CompletableFuture<TimedResult<FilterResult<G, C>>> filteredOffspring = 290 _executor.thenApply(alteredOffspring, pop -> 291 filter(pop.result.population, start.getGeneration()), 292 _clock 293 ); 294 295 // Combining survivors and offspring to the new population. 296 final CompletableFuture<Population<G, C>> population = 297 filteredSurvivors.thenCombineAsync(filteredOffspring, (s, o) -> { 298 final Population<G, C> pop = s.result.population; 299 pop.addAll(o.result.population); 300 return pop; 301 }, 302 _executor.get() 303 ); 304 305 // Evaluate the fitness-function and wait for result. 306 final TimedResult<Population<G, C>> result = population 307 .thenApply(TimedResult.of(this::evaluate, _clock)) 308 .join(); 309 310 final EvolutionDurations durations = EvolutionDurations.of( 311 offspring.join().duration, 312 survivors.join().duration, 313 alteredOffspring.join().duration, 314 filteredOffspring.join().duration, 315 filteredSurvivors.join().duration, 316 result.duration.plus(evaluateTimer.getTime()), 317 timer.stop().getTime() 318 ); 319 320 final int killCount = 321 filteredOffspring.join().result.killCount + 322 filteredSurvivors.join().result.killCount; 323 324 final int invalidCount = 325 filteredOffspring.join().result.invalidCount + 326 filteredSurvivors.join().result.invalidCount; 327 328 return EvolutionResult.of( 329 _optimize, 330 result.result, 331 start.getGeneration(), 332 durations, 333 killCount, 334 invalidCount, 335 alteredOffspring.join().result.alterCount 336 ); 337 } 338 339 /** 340 * This method is an <i>alias</i> for the {@link #evolve(EvolutionStart)} 341 * method. 342 * 343 * @since 3.1 344 */ 345 @Override 346 public EvolutionResult<G, C> apply(final EvolutionStart<G, C> start) { 347 return evolve(start); 348 } 349 350 // Selects the survivors population. A new population object is returned. 351 private Population<G, C> selectSurvivors(final Population<G, C> population) { 352 return _survivorsCount > 0 353 ?_survivorsSelector.select(population, _survivorsCount, _optimize) 354 : Population.empty(); 355 } 356 357 // Selects the offspring population. A new population object is returned. 358 private Population<G, C> selectOffspring(final Population<G, C> population) { 359 return _offspringCount > 0 360 ? _offspringSelector.select(population, _offspringCount, _optimize) 361 : Population.empty(); 362 } 363 364 // Filters out invalid and to old individuals. Filtering is done in place. 365 private FilterResult<G, C> filter( 366 final Population<G, C> population, 367 final long generation 368 ) { 369 int killCount = 0; 370 int invalidCount = 0; 371 372 for (int i = 0, n = population.size(); i < n; ++i) { 373 final Phenotype<G, C> individual = population.get(i); 374 375 if (!_validator.test(individual)) { 376 population.set(i, newPhenotype(generation)); 377 ++invalidCount; 378 } else if (individual.getAge(generation) > _maximalPhenotypeAge) { 379 population.set(i, newPhenotype(generation)); 380 ++killCount; 381 } 382 } 383 384 return new FilterResult<>(population, killCount, invalidCount); 385 } 386 387 // Create a new and valid phenotype 388 private Phenotype<G, C> newPhenotype(final long generation) { 389 int count = 0; 390 Phenotype<G, C> phenotype; 391 do { 392 phenotype = Phenotype.of( 393 _genotypeFactory.newInstance(), 394 generation, 395 _fitnessFunction, 396 _fitnessScaler 397 ); 398 } while (++count < _individualCreationRetries && 399 !_validator.test(phenotype)); 400 401 return phenotype; 402 } 403 404 // Alters the given population. The altering is done in place. 405 private AlterResult<G, C> alter( 406 final Population<G,C> population, 407 final long generation 408 ) { 409 return new AlterResult<>( 410 population, 411 _alterer.alter(population, generation) 412 ); 413 } 414 415 // Evaluates the fitness function of the give population concurrently. 416 private Population<G, C> evaluate(final Population<G, C> population) { 417 try (Concurrency c = Concurrency.with(_executor.get())) { 418 c.execute(population); 419 } 420 return population; 421 } 422 423 /** 424 * Create a new <b>infinite</b> evolution iterator with a newly created 425 * population. This is an alternative way for evolution. It lets the user 426 * start, stop and resume the evolution process whenever desired. 427 * 428 * @return a new <b>infinite</b> evolution iterator 429 */ 430 public Iterator<EvolutionResult<G, C>> iterator() { 431 return new EvolutionIterator<>( 432 this::evolve, 433 this::evolutionStart 434 ); 435 } 436 437 /** 438 * Create a new <b>infinite</b> evolution stream with a newly created 439 * population. 440 * 441 * @return a new evolution stream. 442 */ 443 public EvolutionStream<G, C> stream() { 444 return EvolutionStream.of(this::evolutionStart, this::evolve); 445 } 446 447 private EvolutionStart<G, C> evolutionStart() { 448 final int generation = 1; 449 final int size = _offspringCount + _survivorsCount; 450 451 final Population<G, C> population = new Population<G, C>(size) 452 .fill(() -> newPhenotype(generation), size); 453 454 return EvolutionStart.of(population, generation); 455 } 456 457 /** 458 * Create a new <b>infinite</b> evolution stream with the given initial 459 * individuals. If an empty {@code Iterable} is given, the engines genotype 460 * factory is used for creating the population. 461 * 462 * @param genotypes the initial individuals used for the evolution stream. 463 * Missing individuals are created and individuals not needed are 464 * skipped. 465 * @return a new evolution stream. 466 * @throws java.lang.NullPointerException if the given {@code genotypes} is 467 * {@code null}. 468 */ 469 public EvolutionStream<G, C> stream( 470 final Iterable<Genotype<G>> genotypes 471 ) { 472 requireNonNull(genotypes); 473 474 return EvolutionStream.of( 475 () -> evolutionStart(genotypes, 1), 476 this::evolve 477 ); 478 } 479 480 /** 481 * Create a new <b>infinite</b> evolution iterator with the given initial 482 * individuals. If an empty {@code Iterable} is given, the engines genotype 483 * factory is used for creating the population. 484 * 485 * @param genotypes the initial individuals used for the evolution iterator. 486 * Missing individuals are created and individuals not needed are 487 * skipped. 488 * @return a new <b>infinite</b> evolution iterator 489 * @throws java.lang.NullPointerException if the given {@code genotypes} is 490 * {@code null}. 491 */ 492 public Iterator<EvolutionResult<G, C>> iterator( 493 final Iterable<Genotype<G>> genotypes 494 ) { 495 requireNonNull(genotypes); 496 497 return new EvolutionIterator<>( 498 this::evolve, 499 () -> evolutionStart(genotypes, 1) 500 ); 501 } 502 503 private EvolutionStart<G, C> evolutionStart( 504 final Iterable<Genotype<G>> genotypes, 505 final long generation 506 ) { 507 final Stream<Phenotype<G, C>> stream = Stream.concat( 508 StreamSupport.stream(genotypes.spliterator(), false) 509 .map(gt -> Phenotype.of( 510 gt, generation, _fitnessFunction, _fitnessScaler)), 511 Stream.generate(() -> newPhenotype(generation)) 512 ); 513 514 final Population<G, C> population = stream 515 .limit(getPopulationSize()) 516 .collect(toPopulation()); 517 518 return EvolutionStart.of(population, generation); 519 } 520 521 /** 522 * Create a new <b>infinite</b> evolution stream with the given initial 523 * population. If an empty {@code Population} is given, the engines genotype 524 * factory is used for creating the population. The given population might 525 * be the result of an other engine and this method allows to start the 526 * evolution with the outcome of an different engine. The fitness function 527 * and the fitness scaler are replaced by the one defined for this engine. 528 * 529 * @param population the initial individuals used for the evolution stream. 530 * Missing individuals are created and individuals not needed are 531 * skipped. 532 * @param generation the generation the stream starts from; must be greater 533 * than zero. 534 * @return a new evolution stream. 535 * @throws java.lang.NullPointerException if the given {@code population} is 536 * {@code null}. 537 * @throws IllegalArgumentException if the given {@code generation} is smaller 538 * then one 539 */ 540 public EvolutionStream<G, C> stream( 541 final Population<G, C> population, 542 final long generation 543 ) { 544 requireNonNull(population); 545 require.positive(generation); 546 547 return EvolutionStream.of( 548 () -> evolutionStart(population, generation), 549 this::evolve 550 ); 551 } 552 553 /** 554 * Create a new <b>infinite</b> evolution iterator with the given initial 555 * population. If an empty {@code Population} is given, the engines genotype 556 * factory is used for creating the population. The given population might 557 * be the result of an other engine and this method allows to start the 558 * evolution with the outcome of an different engine. The fitness function 559 * and the fitness scaler are replaced by the one defined for this engine. 560 * 561 * @param population the initial individuals used for the evolution iterator. 562 * Missing individuals are created and individuals not needed are 563 * skipped. 564 * @param generation the generation the iterator starts from; must be greater 565 * than zero. 566 * @return a new <b>infinite</b> evolution iterator 567 * @throws java.lang.NullPointerException if the given {@code population} is 568 * {@code null}. 569 * @throws IllegalArgumentException if the given {@code generation} is smaller 570 * then one 571 */ 572 public Iterator<EvolutionResult<G, C>> iterator( 573 final Population<G, C> population, 574 final long generation 575 ) { 576 requireNonNull(population); 577 require.positive(generation); 578 579 return new EvolutionIterator<>( 580 this::evolve, 581 () -> evolutionStart(population, generation) 582 ); 583 } 584 585 private EvolutionStart<G, C> evolutionStart( 586 final Population<G, C> population, 587 final long generation 588 ) { 589 final Stream<Phenotype<G, C>> stream = Stream.concat( 590 population.stream() 591 .map(p -> p.newInstance( 592 p.getGeneration(), 593 _fitnessFunction, 594 _fitnessScaler)), 595 Stream.generate(() -> newPhenotype(generation)) 596 ); 597 598 final Population<G, C> pop = stream 599 .limit(getPopulationSize()) 600 .collect(toPopulation()); 601 602 return EvolutionStart.of(pop, generation); 603 } 604 605 606 607 /* ************************************************************************* 608 * Property access methods. 609 **************************************************************************/ 610 611 /** 612 * Return the fitness function of the GA engine. 613 * 614 * @return the fitness function 615 */ 616 public Function<? super Genotype<G>, ? extends C> getFitnessFunction() { 617 return _fitnessFunction; 618 } 619 620 /** 621 * Return the fitness scaler of the GA engine. 622 * 623 * @return the fitness scaler 624 */ 625 public Function<? super C, ? extends C> getFitnessScaler() { 626 return _fitnessScaler; 627 } 628 629 /** 630 * Return the used genotype {@link Factory} of the GA. The genotype factory 631 * is used for creating the initial population and new, random individuals 632 * when needed (as replacement for invalid and/or died genotypes). 633 * 634 * @return the used genotype {@link Factory} of the GA. 635 */ 636 public Factory<Genotype<G>> getGenotypeFactory() { 637 return _genotypeFactory; 638 } 639 640 /** 641 * Return the used survivor {@link Selector} of the GA. 642 * 643 * @return the used survivor {@link Selector} of the GA. 644 */ 645 public Selector<G, C> getSurvivorsSelector() { 646 return _survivorsSelector; 647 } 648 649 /** 650 * Return the used offspring {@link Selector} of the GA. 651 * 652 * @return the used offspring {@link Selector} of the GA. 653 */ 654 public Selector<G, C> getOffspringSelector() { 655 return _offspringSelector; 656 } 657 658 /** 659 * Return the used {@link Alterer} of the GA. 660 * 661 * @return the used {@link Alterer} of the GA. 662 */ 663 public Alterer<G, C> getAlterer() { 664 return _alterer; 665 } 666 667 /** 668 * Return the number of selected offsprings. 669 * 670 * @return the number of selected offsprings 671 */ 672 public int getOffspringCount() { 673 return _offspringCount; 674 } 675 676 /** 677 * The number of selected survivors. 678 * 679 * @return the number of selected survivors 680 */ 681 public int getSurvivorsCount() { 682 return _survivorsCount; 683 } 684 685 /** 686 * Return the number of individuals of a population. 687 * 688 * @return the number of individuals of a population 689 */ 690 public int getPopulationSize() { 691 return _offspringCount + _survivorsCount; 692 } 693 694 /** 695 * Return the maximal allowed phenotype age. 696 * 697 * @return the maximal allowed phenotype age 698 */ 699 public long getMaximalPhenotypeAge() { 700 return _maximalPhenotypeAge; 701 } 702 703 /** 704 * Return the optimization strategy. 705 * 706 * @return the optimization strategy 707 */ 708 public Optimize getOptimize() { 709 return _optimize; 710 } 711 712 /** 713 * Return the {@link Clock} the engine is using for measuring the execution 714 * time. 715 * 716 * @return the clock used for measuring the execution time 717 */ 718 public Clock getClock() { 719 return _clock; 720 } 721 722 /** 723 * Return the {@link Executor} the engine is using for executing the 724 * evolution steps. 725 * 726 * @return the executor used for performing the evolution steps 727 */ 728 public Executor getExecutor() { 729 return _executor.get(); 730 } 731 732 733 /* ************************************************************************* 734 * Builder methods. 735 **************************************************************************/ 736 737 /** 738 * Create a new evolution {@code Engine.Builder} initialized with the values 739 * of the current evolution {@code Engine}. With this method, the evolution 740 * engine can serve as a template for an new one. 741 * 742 * @return a new engine builder 743 */ 744 public Builder<G, C> builder() { 745 return new Builder<>(_genotypeFactory, _fitnessFunction) 746 .alterers(_alterer) 747 .clock(_clock) 748 .executor(_executor.get()) 749 .fitnessScaler(_fitnessScaler) 750 .maximalPhenotypeAge(_maximalPhenotypeAge) 751 .offspringFraction((double)_offspringCount/(double)getPopulationSize()) 752 .offspringSelector(_offspringSelector) 753 .optimize(_optimize) 754 .phenotypeValidator(_validator) 755 .populationSize(getPopulationSize()) 756 .survivorsSelector(_survivorsSelector) 757 .individualCreationRetries(_individualCreationRetries); 758 } 759 760 /** 761 * Create a new evolution {@code Engine.Builder} for the given 762 * {@link Problem}. 763 * 764 * @since 3.4 765 * 766 * @param problem the problem to be solved by the evolution {@code Engine} 767 * @param <T> the (<i>native</i>) argument type of the problem fitness function 768 * @param <G> the gene type the evolution engine is working with 769 * @param <C> the result type of the fitness function 770 * @return Create a new evolution {@code Engine.Builder} 771 */ 772 public static <T, G extends Gene<?, G>, C extends Comparable<? super C>> 773 Builder<G, C> builder(final Problem<T, G, C> problem) { 774 return builder(problem.fitness(), problem.codec()); 775 } 776 777 /** 778 * Create a new evolution {@code Engine.Builder} with the given fitness 779 * function and genotype factory. 780 * 781 * @param ff the fitness function 782 * @param genotypeFactory the genotype factory 783 * @param <G> the gene type 784 * @param <C> the fitness function result type 785 * @return a new engine builder 786 * @throws java.lang.NullPointerException if one of the arguments is 787 * {@code null}. 788 */ 789 public static <G extends Gene<?, G>, C extends Comparable<? super C>> 790 Builder<G, C> builder( 791 final Function<? super Genotype<G>, ? extends C> ff, 792 final Factory<Genotype<G>> genotypeFactory 793 ) { 794 return new Builder<>(genotypeFactory, ff); 795 } 796 797 /** 798 * Create a new evolution {@code Engine.Builder} with the given fitness 799 * function and chromosome templates. 800 * 801 * @param ff the fitness function 802 * @param chromosome the first chromosome 803 * @param chromosomes the chromosome templates 804 * @param <G> the gene type 805 * @param <C> the fitness function result type 806 * @return a new engine builder 807 * @throws java.lang.NullPointerException if one of the arguments is 808 * {@code null}. 809 */ 810 @SafeVarargs 811 public static <G extends Gene<?, G>, C extends Comparable<? super C>> 812 Builder<G, C> builder( 813 final Function<? super Genotype<G>, ? extends C> ff, 814 final Chromosome<G> chromosome, 815 final Chromosome<G>... chromosomes 816 ) { 817 return new Builder<>(Genotype.of(chromosome, chromosomes), ff); 818 } 819 820 /** 821 * Create a new evolution {@code Engine.Builder} with the given fitness 822 * function and problem {@code codec}. 823 * 824 * @since 3.2 825 * 826 * @param ff the fitness function 827 * @param codec the problem codec 828 * @param <T> the fitness function input type 829 * @param <C> the fitness function result type 830 * @param <G> the gene type 831 * @return a new engine builder 832 * @throws java.lang.NullPointerException if one of the arguments is 833 * {@code null}. 834 */ 835 public static <T, G extends Gene<?, G>, C extends Comparable<? super C>> 836 Builder<G, C> builder( 837 final Function<? super T, ? extends C> ff, 838 final Codec<T, G> codec 839 ) { 840 return builder(ff.compose(codec.decoder()), codec.encoding()); 841 } 842 843 844 /* ************************************************************************* 845 * Inner classes 846 **************************************************************************/ 847 848 /** 849 * Builder class for building GA {@code Engine} instances. 850 * 851 * @see Engine 852 * 853 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a> 854 * @since 3.0 855 * @version 3.0 856 */ 857 public static final class Builder< 858 G extends Gene<?, G>, 859 C extends Comparable<? super C> 860 > 861 implements Copyable<Builder<G, C>> 862 { 863 864 // No default values for this properties. 865 private Function<? super Genotype<G>, ? extends C> _fitnessFunction; 866 private Factory<Genotype<G>> _genotypeFactory; 867 868 // This are the properties which default values. 869 private Function<? super C, ? extends C> _fitnessScaler = a -> a; 870 private Selector<G, C> _survivorsSelector = new TournamentSelector<>(3); 871 private Selector<G, C> _offspringSelector = new TournamentSelector<>(3); 872 private Alterer<G, C> _alterer = Alterer.of( 873 new SinglePointCrossover<G, C>(0.2), 874 new Mutator<>(0.15) 875 ); 876 private Predicate<? super Phenotype<G, C>> _validator = Phenotype::isValid; 877 private Optimize _optimize = Optimize.MAXIMUM; 878 private double _offspringFraction = 0.6; 879 private int _populationSize = 50; 880 private long _maximalPhenotypeAge = 70; 881 882 private Executor _executor = ForkJoinPool.commonPool(); 883 private Clock _clock = NanoClock.systemUTC(); 884 885 private int _individualCreationRetries = 10; 886 887 private Builder( 888 final Factory<Genotype<G>> genotypeFactory, 889 final Function<? super Genotype<G>, ? extends C> fitnessFunction 890 ) { 891 _genotypeFactory = requireNonNull(genotypeFactory); 892 _fitnessFunction = requireNonNull(fitnessFunction); 893 } 894 895 /** 896 * Set the fitness function of the evolution {@code Engine}. 897 * 898 * @param function the fitness function to use in the GA {@code Engine} 899 * @return {@code this} builder, for command chaining 900 */ 901 public Builder<G, C> fitnessFunction( 902 Function<? super Genotype<G>, ? extends C> function 903 ) { 904 _fitnessFunction = requireNonNull(function); 905 return this; 906 } 907 908 /** 909 * Set the fitness scaler of the evolution {@code Engine}. <i>Default 910 * value is set to the identity function.</i> 911 * 912 * @param scaler the fitness scale to use in the GA {@code Engine} 913 * @return {@code this} builder, for command chaining 914 */ 915 public Builder<G, C> fitnessScaler( 916 final Function<? super C, ? extends C> scaler 917 ) { 918 _fitnessScaler = requireNonNull(scaler); 919 return this; 920 } 921 922 /** 923 * The genotype factory used for creating new individuals. 924 * 925 * @param genotypeFactory the genotype factory for creating new 926 * individuals. 927 * @return {@code this} builder, for command chaining 928 */ 929 public Builder<G, C> genotypeFactory( 930 final Factory<Genotype<G>> genotypeFactory 931 ) { 932 _genotypeFactory = requireNonNull(genotypeFactory); 933 return this; 934 } 935 936 /** 937 * The selector used for selecting the offspring population. <i>Default 938 * values is set to {@code TournamentSelector<>(3)}.</i> 939 * 940 * @param selector used for selecting the offspring population 941 * @return {@code this} builder, for command chaining 942 */ 943 public Builder<G, C> offspringSelector( 944 final Selector<G, C> selector 945 ) { 946 _offspringSelector = requireNonNull(selector); 947 return this; 948 } 949 950 /** 951 * The selector used for selecting the survivors population. <i>Default 952 * values is set to {@code TournamentSelector<>(3)}.</i> 953 * 954 * @param selector used for selecting survivors population 955 * @return {@code this} builder, for command chaining 956 */ 957 public Builder<G, C> survivorsSelector( 958 final Selector<G, C> selector 959 ) { 960 _survivorsSelector = requireNonNull(selector); 961 return this; 962 } 963 964 /** 965 * The selector used for selecting the survivors and offspring 966 * population. <i>Default values is set to 967 * {@code TournamentSelector<>(3)}.</i> 968 * 969 * @param selector used for selecting survivors and offspring population 970 * @return {@code this} builder, for command chaining 971 */ 972 public Builder<G, C> selector(final Selector<G, C> selector) { 973 _offspringSelector = requireNonNull(selector); 974 _survivorsSelector = requireNonNull(selector); 975 return this; 976 } 977 978 /** 979 * The alterers used for alter the offspring population. <i>Default 980 * values is set to {@code new SinglePointCrossover<>(0.2)} followed by 981 * {@code new Mutator<>(0.15)}.</i> 982 * 983 * @param first the first alterer used for alter the offspring 984 * population 985 * @param rest the rest of the alterers used for alter the offspring 986 * population 987 * @return {@code this} builder, for command chaining 988 * @throws java.lang.NullPointerException if one of the alterers is 989 * {@code null}. 990 */ 991 @SafeVarargs 992 public final Builder<G, C> alterers( 993 final Alterer<G, C> first, 994 final Alterer<G, C>... rest 995 ) { 996 requireNonNull(first); 997 Stream.of(rest).forEach(Objects::requireNonNull); 998 999 _alterer = rest.length == 0 ? 1000 first : 1001 Alterer.of(rest).compose(first); 1002 1003 return this; 1004 } 1005 1006 /** 1007 * The phenotype validator used for detecting invalid individuals. 1008 * Alternatively it is also possible to set the genotype validator with 1009 * {@link #genotypeFactory(Factory)}, which will replace any 1010 * previously set phenotype validators. 1011 * 1012 * <p><i>Default value is set to {@code Phenotype::isValid}.</i></p> 1013 * 1014 * @since 3.1 1015 * 1016 * @see #genotypeValidator(Predicate) 1017 * 1018 * @param validator the {@code validator} used for validating the 1019 * individuals (phenotypes). 1020 * @return {@code this} builder, for command chaining 1021 * @throws java.lang.NullPointerException if the {@code validator} is 1022 * {@code null}. 1023 */ 1024 public Builder<G, C> phenotypeValidator( 1025 final Predicate<? super Phenotype<G, C>> validator 1026 ) { 1027 _validator = requireNonNull(validator); 1028 return this; 1029 } 1030 1031 /** 1032 * The genotype validator used for detecting invalid individuals. 1033 * Alternatively it is also possible to set the phenotype validator with 1034 * {@link #phenotypeValidator(Predicate)}, which will replace any 1035 * previously set genotype validators. 1036 * 1037 * <p><i>Default value is set to {@code Genotype::isValid}.</i></p> 1038 * 1039 * @since 3.1 1040 * 1041 * @see #phenotypeValidator(Predicate) 1042 * 1043 * @param validator the {@code validator} used for validating the 1044 * individuals (genotypes). 1045 * @return {@code this} builder, for command chaining 1046 * @throws java.lang.NullPointerException if the {@code validator} is 1047 * {@code null}. 1048 */ 1049 public Builder<G, C> genotypeValidator( 1050 final Predicate<? super Genotype<G>> validator 1051 ) { 1052 requireNonNull(validator); 1053 1054 _validator = pt -> validator.test(pt.getGenotype()); 1055 return this; 1056 } 1057 1058 /** 1059 * The optimization strategy used by the engine. <i>Default values is 1060 * set to {@code Optimize.MAXIMUM}.</i> 1061 * 1062 * @param optimize the optimization strategy used by the engine 1063 * @return {@code this} builder, for command chaining 1064 */ 1065 public Builder<G, C> optimize(final Optimize optimize) { 1066 _optimize = requireNonNull(optimize); 1067 return this; 1068 } 1069 1070 /** 1071 * Set to a fitness maximizing strategy. 1072 * 1073 * @since 3.4 1074 * 1075 * @return {@code this} builder, for command chaining 1076 */ 1077 public Builder<G, C> maximizing() { 1078 return optimize(Optimize.MAXIMUM); 1079 } 1080 1081 /** 1082 * Set to a fitness minimizing strategy. 1083 * 1084 * @since 3.4 1085 * 1086 * @return {@code this} builder, for command chaining 1087 */ 1088 public Builder<G, C> minimizing() { 1089 return optimize(Optimize.MINIMUM); 1090 } 1091 1092 /** 1093 * The offspring fraction. <i>Default values is set to {@code 0.6}.</i> 1094 * 1095 * @param fraction the offspring fraction 1096 * @return {@code this} builder, for command chaining 1097 * @throws java.lang.IllegalArgumentException if the fraction is not 1098 * within the range [0, 1]. 1099 */ 1100 public Builder<G, C> offspringFraction(final double fraction) { 1101 _offspringFraction = probability(fraction); 1102 return this; 1103 } 1104 1105 /** 1106 * The number of individuals which form the population. <i>Default 1107 * values is set to {@code 50}.</i> 1108 * 1109 * @param size the number of individuals of a population 1110 * @return {@code this} builder, for command chaining 1111 * @throws java.lang.IllegalArgumentException if {@code size < 1} 1112 */ 1113 public Builder<G, C> populationSize(final int size) { 1114 if (size < 1) { 1115 throw new IllegalArgumentException(format( 1116 "Population size must be greater than zero, but was %s.", size 1117 )); 1118 } 1119 _populationSize = size; 1120 return this; 1121 } 1122 1123 /** 1124 * The maximal allowed age of a phenotype. <i>Default values is set to 1125 * {@code 70}.</i> 1126 * 1127 * @param age the maximal phenotype age 1128 * @return {@code this} builder, for command chaining 1129 * @throws java.lang.IllegalArgumentException if {@code age < 1} 1130 */ 1131 public Builder<G, C> maximalPhenotypeAge(final long age) { 1132 if (age < 1) { 1133 throw new IllegalArgumentException(format( 1134 "Phenotype age must be greater than one, but was %s.", age 1135 )); 1136 } 1137 _maximalPhenotypeAge = age; 1138 return this; 1139 } 1140 1141 /** 1142 * The executor used by the engine. 1143 * 1144 * @param executor the executor used by the engine 1145 * @return {@code this} builder, for command chaining 1146 */ 1147 public Builder<G, C> executor(final Executor executor) { 1148 _executor = requireNonNull(executor); 1149 return this; 1150 } 1151 1152 /** 1153 * The clock used for calculating the execution durations. 1154 * 1155 * @param clock the clock used for calculating the execution durations 1156 * @return {@code this} builder, for command chaining 1157 */ 1158 public Builder<G, C> clock(final Clock clock) { 1159 _clock = requireNonNull(clock); 1160 return this; 1161 } 1162 1163 /** 1164 * The maximal number of attempt before the {@code Engine} gives up 1165 * creating a valid individual ({@code Phenotype}). <i>Default values is 1166 * set to {@code 10}.</i> 1167 * 1168 * @since 3.1 1169 * 1170 * @param retries the maximal retry count 1171 * @throws IllegalArgumentException if the given retry {@code count} is 1172 * smaller than zero. 1173 * @return {@code this} builder, for command chaining 1174 */ 1175 public Builder<G, C> individualCreationRetries(final int retries) { 1176 if (retries < 0) { 1177 throw new IllegalArgumentException(format( 1178 "Retry count must not be negative: %d", 1179 retries 1180 )); 1181 } 1182 _individualCreationRetries = retries; 1183 return this; 1184 } 1185 1186 /** 1187 * Builds an new {@code Engine} instance from the set properties. 1188 * 1189 * @return an new {@code Engine} instance from the set properties 1190 */ 1191 public Engine<G, C> build() { 1192 return new Engine<>( 1193 _fitnessFunction, 1194 _fitnessScaler, 1195 _genotypeFactory, 1196 _survivorsSelector, 1197 _offspringSelector, 1198 _alterer, 1199 _validator, 1200 _optimize, 1201 getOffspringCount(), 1202 getSurvivorsCount(), 1203 _maximalPhenotypeAge, 1204 _executor, 1205 _clock, 1206 _individualCreationRetries 1207 ); 1208 } 1209 1210 private int getSurvivorsCount() { 1211 return _populationSize - getOffspringCount(); 1212 } 1213 1214 private int getOffspringCount() { 1215 return (int)round(_offspringFraction*_populationSize); 1216 } 1217 1218 /** 1219 * Return the used {@link Alterer} of the GA. 1220 * 1221 * @return the used {@link Alterer} of the GA. 1222 */ 1223 public Alterer<G, C> getAlterers() { 1224 return _alterer; 1225 } 1226 1227 /** 1228 * Return the {@link Clock} the engine is using for measuring the execution 1229 * time. 1230 * 1231 * @since 3.1 1232 * 1233 * @return the clock used for measuring the execution time 1234 */ 1235 public Clock getClock() { 1236 return _clock; 1237 } 1238 1239 /** 1240 * Return the {@link Executor} the engine is using for executing the 1241 * evolution steps. 1242 * 1243 * @since 3.1 1244 * 1245 * @return the executor used for performing the evolution steps 1246 */ 1247 public Executor getExecutor() { 1248 return _executor; 1249 } 1250 1251 /** 1252 * Return the fitness function of the GA engine. 1253 * 1254 * @since 3.1 1255 * 1256 * @return the fitness function 1257 */ 1258 public Function<? super Genotype<G>, ? extends C> getFitnessFunction() { 1259 return _fitnessFunction; 1260 } 1261 1262 /** 1263 * Return the fitness scaler of the GA engine. 1264 * 1265 * @since 3.1 1266 * 1267 * @return the fitness scaler 1268 */ 1269 public Function<? super C, ? extends C> getFitnessScaler() { 1270 return _fitnessScaler; 1271 } 1272 1273 /** 1274 * Return the used genotype {@link Factory} of the GA. The genotype factory 1275 * is used for creating the initial population and new, random individuals 1276 * when needed (as replacement for invalid and/or died genotypes). 1277 * 1278 * @since 3.1 1279 * 1280 * @return the used genotype {@link Factory} of the GA. 1281 */ 1282 public Factory<Genotype<G>> getGenotypeFactory() { 1283 return _genotypeFactory; 1284 } 1285 1286 /** 1287 * Return the maximal allowed phenotype age. 1288 * 1289 * @since 3.1 1290 * 1291 * @return the maximal allowed phenotype age 1292 */ 1293 public long getMaximalPhenotypeAge() { 1294 return _maximalPhenotypeAge; 1295 } 1296 1297 /** 1298 * Return the offspring fraction. 1299 * 1300 * @return the offspring fraction. 1301 */ 1302 public double getOffspringFraction() { 1303 return _offspringFraction; 1304 } 1305 1306 /** 1307 * Return the used offspring {@link Selector} of the GA. 1308 * 1309 * @since 3.1 1310 * 1311 * @return the used offspring {@link Selector} of the GA. 1312 */ 1313 public Selector<G, C> getOffspringSelector() { 1314 return _offspringSelector; 1315 } 1316 1317 /** 1318 * Return the used survivor {@link Selector} of the GA. 1319 * 1320 * @since 3.1 1321 * 1322 * @return the used survivor {@link Selector} of the GA. 1323 */ 1324 public Selector<G, C> getSurvivorsSelector() { 1325 return _survivorsSelector; 1326 } 1327 1328 /** 1329 * Return the optimization strategy. 1330 * 1331 * @since 3.1 1332 * 1333 * @return the optimization strategy 1334 */ 1335 public Optimize getOptimize() { 1336 return _optimize; 1337 } 1338 1339 /** 1340 * Return the number of individuals of a population. 1341 * 1342 * @since 3.1 1343 * 1344 * @return the number of individuals of a population 1345 */ 1346 public int getPopulationSize() { 1347 return _populationSize; 1348 } 1349 1350 /** 1351 * Return the maximal number of attempt before the {@code Engine} gives 1352 * up creating a valid individual ({@code Phenotype}). 1353 * 1354 * @since 3.1 1355 * 1356 * @return the maximal number of {@code Phenotype} creation attempts 1357 */ 1358 public int getIndividualCreationRetries() { 1359 return _individualCreationRetries; 1360 } 1361 1362 /** 1363 * Create a new builder, with the current configuration. 1364 * 1365 * @since 3.1 1366 * 1367 * @return a new builder, with the current configuration 1368 */ 1369 @Override 1370 public Builder<G, C> copy() { 1371 return new Builder<>(_genotypeFactory, _fitnessFunction) 1372 .alterers(_alterer) 1373 .clock(_clock) 1374 .executor(_executor) 1375 .fitnessScaler(_fitnessScaler) 1376 .maximalPhenotypeAge(_maximalPhenotypeAge) 1377 .offspringFraction(_offspringFraction) 1378 .offspringSelector(_offspringSelector) 1379 .phenotypeValidator(_validator) 1380 .optimize(_optimize) 1381 .populationSize(_populationSize) 1382 .survivorsSelector(_survivorsSelector) 1383 .individualCreationRetries(_individualCreationRetries); 1384 } 1385 1386 } 1387}