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