0001 /*
0002 * Java Genetic Algorithm Library (jenetics-1.6.0).
0003 * Copyright (c) 2007-2014 Franz Wilhelmstötter
0004 *
0005 * Licensed under the Apache License, Version 2.0 (the "License");
0006 * you may not use this file except in compliance with the License.
0007 * You may obtain a copy of the License at
0008 *
0009 * http://www.apache.org/licenses/LICENSE-2.0
0010 *
0011 * Unless required by applicable law or agreed to in writing, software
0012 * distributed under the License is distributed on an "AS IS" BASIS,
0013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0014 * See the License for the specific language governing permissions and
0015 * limitations under the License.
0016 *
0017 * Author:
0018 * Franz Wilhelmstötter (franz.wilhelmstoetter@gmx.at)
0019 */
0020 package org.jenetics;
0021
0022 import static java.lang.Math.round;
0023 import static java.lang.String.format;
0024 import static java.util.Objects.requireNonNull;
0025 import static org.jenetics.internal.util.object.NonNull;
0026 import static org.jenetics.internal.util.object.checkProbability;
0027 import static org.jenetics.util.arrays.forEach;
0028
0029 import java.util.Collection;
0030 import java.util.concurrent.atomic.AtomicInteger;
0031 import java.util.concurrent.locks.Lock;
0032 import java.util.concurrent.locks.ReentrantLock;
0033
0034 import org.jenetics.util.Array;
0035 import org.jenetics.util.Concurrency;
0036 import org.jenetics.util.Factory;
0037 import org.jenetics.util.Function;
0038 import org.jenetics.util.Timer;
0039 import org.jenetics.util.functions;
0040
0041 /**
0042 * <h3>Getting started</h3>
0043 *
0044 * The minimum GA setup needs a genotype factory, {@code Factory<Genotype<?>>},
0045 * and a fitness {@link Function}. The {@link Genotype} implements the
0046 * {@link Factory} interface and can therefore be used as prototype for creating
0047 * the initial Population and for creating new random Genotypes.
0048 *
0049 * [code]
0050 * public static void main(final String[] args) {
0051 * final Factory〈Genotype〈BitGene〉〉 gtf = Genotype.of(
0052 * BitChromosome.of(10, 0.5)
0053 * );
0054 * final Function〈Genotype〈BitGene〉 Double〉 ff = ...
0055 * final GeneticAlgorithm〈BitGene, Double〉
0056 * ga = new GeneticAlgorithm〈〉(gtf, ff, Optimize.MAXIMUM);
0057 *
0058 * ga.setup();
0059 * ga.evolve(100);
0060 * System.out.println(ga.getBestPhenotype());
0061 * }
0062 * [/code]
0063 *
0064 * <p>
0065 * The genotype factory, {@code gtf}, in the example above will create genotypes
0066 * which consists of one {@link BitChromosome} with length 10. The one to zero
0067 * probability of the newly created genotypes is set to 0.5. The fitness function
0068 * is parametrized with a {@link BitGene} and a {@link Double}. That means
0069 * that the fitness function is calculating the fitness value as {@link Double}.
0070 * The return type of the fitness function must be at least a {@link Comparable}.
0071 * The {@code GeneticAlgorithm} object is then created with the genotype factory
0072 * and the fitness function. In this example the GA tries to maximize the fitness
0073 * function. If you want to find the minimal value you have to change the optimize
0074 * parameter from {@code Optimize.MAXIMUM} to {@code Optimize.MINIMUM}. The
0075 * {@code ga.setup()} call creates the initial population and calculates its
0076 * fitness value. Then the GA evolves 100 generations ({@code ga.evolve(100)})
0077 * an prints the best phenotype found so far onto the console.
0078 * </p>
0079 * In a more advanced setup you may want to change the default mutation and/or
0080 * selection strategies.
0081 *
0082 * [code]
0083 * public static void main(final String[] args) {
0084 * ...
0085 * ga.setSelectors(new RouletteWheelSelector〈BitGene〉());
0086 * ga.setAlterers(
0087 * new SinglePointCrossover〈BitGene〉(0.1),
0088 * new Mutator〈BitGene〉(0.01)
0089 * );
0090 *
0091 * ga.setup();
0092 * ga.evolve(100);
0093 * System.out.println(ga.getBestPhenotype());
0094 * }
0095 * [/code]
0096 *
0097 * The selection strategy for offspring and survivors are set to the
0098 * roulette-wheel selector. It is also possible to set the selector for
0099 * offspring and survivors independently with the {@code setOffspringSelector}
0100 * and {@code setSurvivorSelector} methods. The alterers are concatenated, at
0101 * first the crossover (with probability 0.1) is performed and then the
0102 * chromosomes are mutated (with probability 0.01).
0103 * <p/>
0104 *
0105 * <h3>Serialization</h3>
0106 *
0107 * With the serialization mechanism you can write a population to disk and load
0108 * it into an GA at a later time. It can also be used to transfer populations to
0109 * GAs, running on different hosts, over a network link. The IO class, located
0110 * in the {@code org.jenetics.util} package, supports native Java serialization
0111 * and XML serialization. For XML marshaling <em>Jenetics</em> internally uses
0112 * the XML support from the Javolution project.
0113 *
0114 * [code]
0115 * // Writing the population to disk.
0116 * final File file = new File("population.xml");
0117 * IO.jaxb.write(ga.getPopulation(), file);
0118 *
0119 * // Reading the population from disk.
0120 * Population〈DoubleGene, Double〉 population =
0121 * (Population〈DoubleGene, Double〉)IO.jaxb.read(file);
0122 * ga.setPopulation(population);
0123 * [/code]
0124 *
0125 * @see <a href="http://en.wikipedia.org/wiki/Genetic_algorithm">
0126 * Wikipedia: Genetic algorithm
0127 * </a>
0128 * @see Alterer
0129 * @see Selector
0130 *
0131 * @param <G> The gene type this GA evaluates,
0132 * @param <C> The result type (of the fitness function).
0133 *
0134 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
0135 * @since 1.0
0136 * @version 1.0 — <em>$Date: 2014-03-05 $</em>
0137 */
0138 public class GeneticAlgorithm<
0139 G extends Gene<?, G>,
0140 C extends Comparable<? super C>
0141 >
0142 {
0143
0144 /**
0145 * The default population size used by this GA.
0146 */
0147 public static final int DEFAULT_POPULATION_SIZE = 50;
0148
0149 /**
0150 * The default maximal phenotype age of this GA:
0151 */
0152 public static final int DEFAULT_MAXIMAL_PHENOTYPE_AGE = 70;
0153
0154 /**
0155 * The default offspring fraction used by this GA.
0156 */
0157 public static final double DEFAULT_OFFSPRING_FRACTION = 0.6;
0158
0159
0160 private final Lock _lock = new ReentrantLock(true);
0161
0162 private final Optimize _optimization;
0163
0164 private final Factory<Genotype<G>> _genotypeFactory;
0165 private final Factory<Phenotype<G, C>> _phenotypeFactory;
0166 private final Function<? super Genotype<G>, ? extends C> _fitnessFunction;
0167 private Function<? super C, ? extends C> _fitnessScaler;
0168
0169 private double _offspringFraction = DEFAULT_OFFSPRING_FRACTION;
0170
0171 // Alterers
0172 private Alterer<G> _alterer = CompositeAlterer.of(
0173 new SinglePointCrossover<G>(0.1),
0174 new Mutator<G>(0.05)
0175 );
0176
0177 // Selectors
0178 private Selector<G, C> _survivorSelector = new TournamentSelector<>(3);
0179 private Selector<G, C> _offspringSelector = new TournamentSelector<>(3);
0180
0181 // Population
0182 private int _populationSize = DEFAULT_POPULATION_SIZE;
0183 private Population<G, C> _population = new Population<>(_populationSize);
0184 private int _maximalPhenotypeAge = DEFAULT_MAXIMAL_PHENOTYPE_AGE;
0185 private volatile int _generation = 0;
0186
0187 // Statistics
0188 private Statistics.Calculator<G, C> _calculator = new Statistics.Calculator<>();
0189 private Statistics<G, C> _bestStatistics = null;
0190 private Statistics<G, C> _statistics = null;
0191 private final AtomicInteger _killed = new AtomicInteger(0);
0192 private final AtomicInteger _invalid = new AtomicInteger(0);
0193
0194 //Some performance measure.
0195 private final Timer _executionTimer = new Timer("Execution time");
0196 private final Timer _selectTimer = new Timer("Select time");
0197 private final Timer _alterTimer = new Timer("Alter time");
0198 private final Timer _combineTimer = new Timer("Combine survivors and offspring time");
0199 private final Timer _statisticTimer = new Timer("Statistic time");
0200 private final Timer _evaluateTimer = new Timer("Evaluate time");
0201
0202
0203 /**
0204 * Create a new genetic algorithm.
0205 *
0206 * @param genotypeFactory the genotype factory this GA is working with.
0207 * @param fitnessFunction the fitness function this GA is using.
0208 * @param fitnessScaler the fitness scaler this GA is using.
0209 * @param optimization Determine whether this GA maximize or minimize the
0210 * fitness function.
0211 * @throws NullPointerException if one of the arguments is {@code null}.
0212 */
0213 public GeneticAlgorithm(
0214 final Factory<Genotype<G>> genotypeFactory,
0215 final Function<? super Genotype<G>, ? extends C> fitnessFunction,
0216 final Function<? super C, ? extends C> fitnessScaler,
0217 final Optimize optimization
0218 ) {
0219 _genotypeFactory = requireNonNull(genotypeFactory, "GenotypeFactory");
0220 _fitnessFunction = requireNonNull(fitnessFunction, "FitnessFunction");
0221 _fitnessScaler = requireNonNull(fitnessScaler, "FitnessScaler");
0222 _optimization = requireNonNull(optimization, "Optimization");
0223
0224 _phenotypeFactory = new Factory<Phenotype<G, C>>() {
0225 @Override public Phenotype<G, C> newInstance() {
0226 return Phenotype.of(
0227 _genotypeFactory.newInstance(),
0228 _fitnessFunction,
0229 _fitnessScaler,
0230 _generation
0231 );
0232 }
0233 };
0234 }
0235
0236 /**
0237 * Create a new genetic algorithm. By default the GA tries to maximize the
0238 * fitness function.
0239 *
0240 * @param genotypeFactory the genotype factory this GA is working with.
0241 * @param fitnessFunction the fitness function this GA is using.
0242 * @throws NullPointerException if one of the arguments is {@code null}.
0243 */
0244 public GeneticAlgorithm(
0245 final Factory<Genotype<G>> genotypeFactory,
0246 final Function<? super Genotype<G>, ? extends C> fitnessFunction
0247 ) {
0248 this(
0249 genotypeFactory,
0250 fitnessFunction,
0251 functions.<C>Identity(),
0252 Optimize.MAXIMUM
0253 );
0254 }
0255
0256 /**
0257 * Create a new genetic algorithm.
0258 *
0259 * @param genotypeFactory the genotype factory this GA is working with.
0260 * @param fitnessFunction the fitness function this GA is using.
0261 * @param optimization Determine whether this GA maximize or minimize the
0262 * fitness function.
0263 * @throws NullPointerException if one of the arguments is {@code null}.
0264 */
0265 public GeneticAlgorithm(
0266 final Factory<Genotype<G>> genotypeFactory,
0267 final Function<? super Genotype<G>, ? extends C> fitnessFunction,
0268 final Optimize optimization
0269 ) {
0270 this(
0271 genotypeFactory,
0272 fitnessFunction,
0273 functions.<C>Identity(),
0274 optimization
0275 );
0276 }
0277
0278 /**
0279 * Create a new genetic algorithm. By default the GA tries to maximize the
0280 * fitness function.
0281 *
0282 * @param genotypeFactory the genotype factory this GA is working with.
0283 * @param fitnessFunction the fitness function this GA is using.
0284 * @param fitnessScaler the fitness scaler this GA is using.
0285 * @throws NullPointerException if one of the arguments is {@code null}.
0286 */
0287 public GeneticAlgorithm(
0288 final Factory<Genotype<G>> genotypeFactory,
0289 final Function<? super Genotype<G>, ? extends C> fitnessFunction,
0290 final Function<? super C, ? extends C> fitnessScaler
0291 ) {
0292 this(
0293 genotypeFactory,
0294 fitnessFunction,
0295 fitnessScaler,
0296 Optimize.MAXIMUM
0297 );
0298 }
0299
0300 /**
0301 * Create the initial population of the GA. Subsequent calls to this
0302 * method throw IllegalStateException. If no initial population has been
0303 * set (with {@link #setPopulation(Collection)} or
0304 * {@link #setGenotypes(Collection)}) a random population is generated.
0305 *
0306 * @throws IllegalStateException if called more than once.
0307 */
0308 public void setup() {
0309 _lock.lock();
0310 try {
0311 prepareSetup();
0312 _population.fill(
0313 _phenotypeFactory,
0314 _populationSize - _population.size()
0315 );
0316 finishSetup();
0317 } finally {
0318 _lock.unlock();
0319 }
0320 }
0321
0322 /**
0323 * Setting up the {@code GeneticAlgorithm} with the given initial
0324 * population. Subsequent calls to this method throw an IllegalStateException.
0325 * This method is similar to the {@link #setGenotypes(Collection)} and
0326 * {@link #setPopulation(Collection)} methods, but this method is required
0327 * to be called only once and before starting evaluation. It also calculates
0328 * the timing statistics when (calculating the fitness values for the given
0329 * genotypes.
0330 *
0331 * @see #setGenotypes(Collection)
0332 * @see #setPopulation(Collection)
0333 * @param genotypes the initial population.
0334 * @throws IllegalStateException if called more than once.
0335 */
0336 public void setup(final Collection<Genotype<G>> genotypes) {
0337 _lock.lock();
0338 try {
0339 prepareSetup();
0340 setGenotypes(genotypes);
0341 finishSetup();
0342 } finally {
0343 _lock.unlock();
0344 }
0345 }
0346
0347 private void prepareSetup() {
0348 if (_generation > 0) {
0349 throw new IllegalStateException(
0350 "The method GeneticAlgorithm.setup() must be called only once."
0351 );
0352 }
0353
0354 ++_generation;
0355 _executionTimer.start();
0356 }
0357
0358 private void finishSetup() {
0359 //Evaluate the fitness.
0360 evaluate();
0361
0362 //First valuation of the initial population.
0363 _statisticTimer.start();
0364 _statistics = _calculator.evaluate(
0365 _population, _generation, _optimization
0366 ).build();
0367
0368 _bestStatistics = _statistics;
0369 _statisticTimer.stop();
0370
0371 _executionTimer.stop();
0372
0373 setTimes(_statistics);
0374 }
0375
0376 /**
0377 * Evolve one generation.
0378 *
0379 * @throws IllegalStateException if the {@link GeneticAlgorithm#setup()}
0380 * method was not called first.
0381 */
0382 public void evolve() {
0383 _lock.lock();
0384 try {
0385 // Check the setup state.
0386 if (_generation == 0) {
0387 throw new IllegalStateException(
0388 "Call the GeneticAlgorithm.setup() method before " +
0389 "calling GeneticAlgorithm.evolve()."
0390 );
0391 }
0392
0393 //Start the overall execution timer.s
0394 _executionTimer.start();
0395
0396 //Increment the generation and the generation.
0397 ++_generation;
0398
0399 //Select the survivors and the offspring.
0400 _selectTimer.start();
0401 final Array<Population<G, C>> selection = select();
0402 final Population<G, C> survivors = selection.get(0);
0403 final Population<G, C> offsprings = selection.get(1);
0404 _selectTimer.stop();
0405
0406 //Alter the offspring (Recombination, Mutation ...).
0407 _alterTimer.start();
0408 _alterer.alter(offsprings, _generation);
0409 _alterTimer.stop();
0410
0411 // Combining the new population (containing the survivors and the
0412 // altered offspring).
0413 _combineTimer.start();
0414 final int killed = _killed.get();
0415 final int invalid = _invalid.get();
0416 _population = combine(survivors, offsprings);
0417 _combineTimer.stop();
0418
0419 //Evaluate the fitness
0420 evaluate();
0421
0422 //Evaluate the statistic
0423 _statisticTimer.start();
0424 final Statistics.Builder<G, C> builder = _calculator.evaluate(
0425 _population, _generation, _optimization
0426 );
0427 builder.killed(_killed.get() - killed);
0428 builder.invalid(_invalid.get() - invalid);
0429 _statistics = builder.build();
0430
0431 final int comp = _optimization.compare(
0432 _statistics.getBestPhenotype(),
0433 _bestStatistics.getBestPhenotype()
0434 );
0435
0436 if (comp > 0) {
0437 _bestStatistics = _statistics;
0438 }
0439
0440 _statisticTimer.stop();
0441
0442 _executionTimer.stop();
0443
0444 setTimes(_statistics);
0445 } finally {
0446 _lock.unlock();
0447 }
0448 }
0449
0450 private void setTimes(final Statistics<?, ?> statistic) {
0451 statistic.getTime().execution.set(_executionTimer.getInterimTime());
0452 statistic.getTime().selection.set(_selectTimer.getInterimTime());
0453 statistic.getTime().alter.set(_alterTimer.getInterimTime());
0454 statistic.getTime().combine.set(_combineTimer.getInterimTime());
0455 statistic.getTime().evaluation.set(_evaluateTimer.getInterimTime());
0456 statistic.getTime().statistics.set(_statisticTimer.getInterimTime());
0457 }
0458
0459 private void evaluate() {
0460 _evaluateTimer.start();
0461 try (Concurrency c = Concurrency.start()) {
0462 for (int i = _population.size(); --i >= 0;) {
0463 c.execute(_population.get(i));
0464 }
0465 }
0466 _evaluateTimer.stop();
0467 }
0468
0469 /**
0470 * Evolve the given number of {@code generations}
0471 *
0472 * @param generations the number of {@code generations} to evolve.
0473 */
0474 public void evolve(final int generations) {
0475 for (int i = 0; i < generations; ++i) {
0476 evolve();
0477 }
0478 }
0479
0480 /**
0481 * Evolve the GA as long the given {@link Function} returns {@code true}.
0482 *
0483 * @see termination
0484 *
0485 * @param until the predicate which defines the termination condition.
0486 * @throws NullPointerException if the given predicate is {@code null}.
0487 */
0488 public void evolve(final Function<? super Statistics<G, C>, Boolean> until) {
0489 requireNonNull(until, "Termination condition");
0490 while (until.apply(getStatistics())) {
0491 evolve();
0492 }
0493 }
0494
0495 private Array<Population<G, C>> select() {
0496 final Array<Population<G, C>> selection = new Array<>(2);
0497 final int numberOfSurvivors = getNumberOfSurvivors();
0498 final int numberOfOffspring = getNumberOfOffsprings();
0499 assert (numberOfSurvivors + numberOfOffspring == _populationSize);
0500
0501 try (Concurrency c = Concurrency.start()) {
0502 c.execute(new Runnable() { @Override public void run() {
0503 final Population<G, C> survivors = _survivorSelector.select(
0504 _population, numberOfSurvivors, _optimization
0505 );
0506
0507 assert (survivors.size() == numberOfSurvivors);
0508 selection.set(0, survivors);
0509 }});
0510
0511 final Population<G, C> offsprings = _offspringSelector.select(
0512 _population, numberOfOffspring, _optimization
0513 );
0514
0515 assert (offsprings.size() == numberOfOffspring);
0516 selection.set(1, offsprings);
0517 }
0518
0519 return selection;
0520 }
0521
0522 private Population<G, C> combine(
0523 final Population<G, C> survivors,
0524 final Population<G, C> offsprings
0525 ) {
0526 assert (survivors.size() + offsprings.size() == _populationSize);
0527 final Population<G, C> population = new Population<>(_populationSize);
0528
0529 try (Concurrency c = Concurrency.start()) {
0530 // Kill survivors which are to old and replace it with new one.
0531 c.execute(new Runnable() { @Override public void run() {
0532 for (int i = 0, n = survivors.size(); i < n; ++i) {
0533 final Phenotype<G, C> survivor = survivors.get(i);
0534
0535 final boolean isTooOld =
0536 survivor.getAge(_generation) > _maximalPhenotypeAge;
0537
0538 final boolean isInvalid = isTooOld || !survivor.isValid();
0539
0540 // Sorry, too old or not valid.
0541 if (isInvalid) {
0542 survivors.set(i, _phenotypeFactory.newInstance());
0543 }
0544
0545 if (isTooOld) {
0546 _killed.incrementAndGet();
0547 } else if (isInvalid) {
0548 _invalid.incrementAndGet();
0549 }
0550 }
0551 }});
0552
0553 // In the mean time we can add the offsprings.
0554 population.addAll(offsprings);
0555 }
0556
0557 population.addAll(survivors);
0558
0559 return population;
0560 }
0561
0562 private int getNumberOfSurvivors() {
0563 return _populationSize - getNumberOfOffsprings();
0564 }
0565
0566 private int getNumberOfOffsprings() {
0567 return (int)round(
0568 _offspringFraction*_populationSize
0569 );
0570 }
0571
0572 /**
0573 * Return {@code true} if the {@link #setup()} method has already been called,
0574 * {@code false} otherwise.
0575 *
0576 * @return {@code true} if the {@link #setup()} method has already been called,
0577 * {@code false} otherwise.
0578 */
0579 public boolean isInitialized() {
0580 _lock.lock();
0581 try {
0582 return _generation > 0;
0583 } finally {
0584 _lock.unlock();
0585 }
0586 }
0587
0588 /**
0589 * <p>
0590 * If you are using the {@code GeneticAlgorithm} in an threaded environment
0591 * and you want to change some of the GAs parameters you can use the returned
0592 * {@link Lock} to synchronize your parameter changes. The GA acquires the
0593 * lock at the begin of the {@link #setup()} and the {@link #evolve()}
0594 * methods and releases it at the end of these methods.
0595 * </p>
0596 * To set one ore more GA parameter you will write code like this:
0597 * [code]
0598 * final GeneticAlgorithm〈DoubleGene, Double〉 ga = ...
0599 * final Function〈GeneticAlgorithm〈?, ?〉, Boolean〉 until = ...
0600 *
0601 * //Starting the GA in separate thread.
0602 * final Thread thread = new Thread(new Runnable() {
0603 * public void run() {
0604 * while (!Thread.currentThread().isInterrupted() &&
0605 * !until.apply(ga))
0606 * {
0607 * if (ga.getGeneration() == 0) {
0608 * ga.setup();
0609 * } else {
0610 * ga.evolve();
0611 * }
0612 * }
0613 * }
0614 * });
0615 * thread.start();
0616 *
0617 * //Changing the GA parameters outside the evolving thread. All parameters
0618 * //are changed before the next evolve step.
0619 * ga.getLock().lock();
0620 * try {
0621 * ga.setAlterer(new Mutation(0.02);
0622 * ga.setPopulationSize(55);
0623 * ga.setMaximalPhenotypeAge(30);
0624 * } finally {
0625 * ga.getLock().unlock();
0626 * }
0627 * [/code]
0628 *
0629 * You can use the same lock if you want get a consistent state of the used
0630 * parameters, if they where changed within an other thread.
0631 *
0632 * [code]
0633 * ga.getLock().lock();
0634 * try {
0635 * final Statistics〈?, ?〉 statistics = ga.getStatistic();
0636 * final Function〈?, ?〉 scaler = ga.getFitnessScaler();
0637 * } finally {
0638 * ga.getLock().unlock();
0639 * }
0640 * [/code]
0641 *
0642 * The code above ensures that the returned {@code statistics} and
0643 * {@code scaler} where used together within the same {@link #evolve()} step.
0644 *
0645 * @return the lock acquired in the {@link #setup()} and the {@link #evolve()}
0646 * method.
0647 */
0648 public Lock getLock() {
0649 return _lock;
0650 }
0651
0652 /**
0653 * Return the used genotype {@link Factory} of the GA. The genotype factory
0654 * is used for creating the initial population and new, random individuals
0655 * when needed (as replacement for invalid and/or died genotypes).
0656 *
0657 * @return the used genotype {@link Factory} of the GA.
0658 */
0659 public Factory<Genotype<G>> getGenotypeFactory() {
0660 return _genotypeFactory;
0661 }
0662
0663 /**
0664 * <p>
0665 * Return the used fitness {@link Function} of the GA. The fitness function
0666 * is also an important part when modeling the GA. It takes a genotype as
0667 * argument and returns, at least, a Comparable object as result---the
0668 * fitness value. This allows the GA, respectively the selection operators,
0669 * to select the offspring- and survivor population. Some selectors have
0670 * stronger requirements to the fitness value than a Comparable, but this
0671 * constraints is checked by the Java type system at compile time.
0672 * </p>
0673 * The following example shows the simplest possible fitness function. It's
0674 * the identity function and returns the allele of an 1x1 float genotype.
0675 * [code]
0676 * class Id implements Function〈Genotype〈DoubleGene〉, Double〉 {
0677 * public Double apply(final Genotype〈DoubleGene〉 genotype) {
0678 * return genotype.getGene().getAllele();
0679 * }
0680 * }
0681 * [/code]
0682 * The first type parameter of the {@link Function} defines the kind of
0683 * genotype from which the fitness value is calculated and the second type
0684 * parameter determines the return type. As already mentioned, the return
0685 * type must implement the {@link Comparable} interface.
0686 *
0687 * @return the used fitness {@link Function} of the GA.
0688 */
0689 public Function<? super Genotype<G>, ? extends C> getFitnessFunction() {
0690 return _fitnessFunction;
0691 }
0692
0693 /**
0694 * Set the currently used fitness scaler. The fitness value, calculated by
0695 * the fitness function, is the raw-fitness of an individual. The
0696 * <em>Jenetics</em> library allows you to apply an additional scaling
0697 * function on the raw-fitness to form the fitness value which is used by
0698 * the selectors. This can be useful when using probability selectors, where
0699 * the actual amount of the fitness value influences the selection
0700 * probability. In such cases, the fitness scaler gives you additional
0701 * flexibility when selecting offspring and survivors. In the default
0702 * configuration the raw-fitness is equal to the actual fitness value, that
0703 * means, the used fitness scaler is the identity function.
0704 * [code]
0705 * class Sqrt extends Function〈Double, Double〉 {
0706 * public Double apply(final Double value) {
0707 * return sqrt(value);
0708 * }
0709 * }
0710 * [/code]
0711 *
0712 * <p>
0713 * The listing above shows a fitness scaler which reduces the the raw-fitness
0714 * to its square root. This gives weaker individuals a greater changes being
0715 * selected and weakens the influence of super-individuals.
0716 * </p>
0717 * When using a fitness scaler you have to take care, that your scaler
0718 * doesn't destroy your fitness value. This can be the case when your
0719 * fitness value is negative and your fitness scaler squares the value.
0720 * Trying to find the minimum will not work in this configuration.</b>
0721 *
0722 * @param scaler The fitness scaler.
0723 * @throws NullPointerException if the scaler is {@code null}.
0724 */
0725 public void setFitnessScaler(final Function<? super C, ? extends C> scaler) {
0726 _fitnessScaler = requireNonNull(scaler, "FitnessScaler");
0727 }
0728
0729 /**
0730 * Return the currently used fitness scaler {@link Function} of the GA.
0731 *
0732 * @return the currently used fitness scaler {@link Function} of the GA.
0733 */
0734 public Function<? super C, ? extends C> getFitnessScaler() {
0735 return _fitnessScaler;
0736 }
0737
0738 /**
0739 * Return the currently used offspring fraction of the GA.
0740 *
0741 * @return the currently used offspring fraction of the GA.
0742 */
0743 public double getOffspringFraction() {
0744 return _offspringFraction;
0745 }
0746
0747 /**
0748 * Return the currently used offspring {@link Selector} of the GA.
0749 *
0750 * @return the currently used offspring {@link Selector} of the GA.
0751 */
0752 public Selector<G, C> getOffspringSelector() {
0753 return _offspringSelector;
0754 }
0755
0756 /**
0757 * Return the currently used survivor {@link Selector} of the GA.
0758 *
0759 * @return the currently used survivor {@link Selector} of the GA.
0760 */
0761 public Selector<G, C> getSurvivorSelector() {
0762 return _survivorSelector;
0763 }
0764
0765 /**
0766 * Return the currently used {@link Alterer} of the GA.
0767 *
0768 * @return the currently used {@link Alterer} of the GA.
0769 */
0770 public Alterer<G> getAlterer() {
0771 return _alterer;
0772 }
0773
0774 /**
0775 * Return the current overall generation.
0776 *
0777 * @return the current overall generation.
0778 */
0779 public int getGeneration() {
0780 return _generation;
0781 }
0782
0783 /**
0784 * Return the maximal age of the {@link Phenotype}s.
0785 *
0786 * @return the maximal age of the {@link Phenotype}s.
0787 */
0788 public int getMaximalPhenotypeAge() {
0789 return _maximalPhenotypeAge;
0790 }
0791
0792 /**
0793 * Return the best {@link Phenotype} so far or {@code null} if the GA hasn't
0794 * been initialized yet.
0795 *
0796 * @return the best {@link Phenotype} so far or {@code null} if the GA hasn't
0797 * been initialized yet.
0798 */
0799 public Phenotype<G, C> getBestPhenotype() {
0800 return _bestStatistics != null ? _bestStatistics.getBestPhenotype() : null;
0801 }
0802
0803 /**
0804 * Return the current {@link Population} {@link Statistics} or {@code null}
0805 * if the GA hasn't been initialized yet.
0806 *
0807 * @return the current {@link Population} {@link Statistics} or {@code null}
0808 * if the GA hasn't been initialized yet.
0809 */
0810 public Statistics<G, C> getStatistics() {
0811 return _statistics;
0812 }
0813
0814 /**
0815 * Set the offspring selector.
0816 *
0817 * @param selector The offspring selector.
0818 * @throws NullPointerException, if the given selector is null.
0819 */
0820 public void setOffspringSelector(final Selector<G, C> selector) {
0821 _offspringSelector = requireNonNull(selector, "Offspring selector");
0822 }
0823
0824 /**
0825 * Set the survivor selector.
0826 *
0827 * @param selector The survivor selector.
0828 * @throws NullPointerException, if the given selector is null.
0829 */
0830 public void setSurvivorSelector(final Selector<G, C> selector) {
0831 _survivorSelector = requireNonNull(selector, "Survivor selector");
0832 }
0833
0834 /**
0835 * Set both, the offspring selector and the survivor selector.
0836 *
0837 * @param selector The selector for the offspring and the survivors.
0838 * @throws NullPointerException if the {@code selector} is {@code null}
0839 */
0840 public void setSelectors(final Selector<G, C> selector) {
0841 setOffspringSelector(selector);
0842 setSurvivorSelector(selector);
0843 }
0844
0845 /**
0846 * Set the offspring fraction.
0847 *
0848 * @param offspringFraction The offspring fraction.
0849 * @throws IllegalArgumentException if the offspring fraction is out of
0850 * range.
0851 */
0852 public void setOffspringFraction(final double offspringFraction) {
0853 _offspringFraction = checkProbability(offspringFraction);
0854 }
0855
0856 /**
0857 * Set the alterer.
0858 *
0859 * @param alterer The alterer.
0860 * @throws NullPointerException if the alterer is null.
0861 */
0862 public void setAlterer(final Alterer<G> alterer) {
0863 _alterer = requireNonNull(alterer, "Alterer");
0864 }
0865
0866 /**
0867 * Set the given alterers.
0868 *
0869 * @param alterers the alterers to set.
0870 * @throws NullPointerException if the alterers are null.
0871 */
0872 @SafeVarargs
0873 public final void setAlterers(final Alterer<G>... alterers) {
0874 setAlterer(CompositeAlterer.of(alterers));
0875 }
0876
0877 /**
0878 * Set the maximum age of the phenotypes in the population.
0879 *
0880 * @param age Maximal phenotype age.
0881 * @throws IllegalArgumentException if the age is smaller then one.
0882 */
0883 public void setMaximalPhenotypeAge(final int age) {
0884 if (age < 1) {
0885 throw new IllegalArgumentException(format(
0886 "Phenotype age must be greater than one, but was %s.", age
0887 ));
0888 }
0889 _maximalPhenotypeAge = age;
0890 }
0891
0892 /**
0893 * Set the desired population size.
0894 *
0895 * @param size The population size.
0896 * @throws IllegalArgumentException if the population size is smaller than
0897 * one.
0898 */
0899 public void setPopulationSize(final int size) {
0900 if (size < 1) {
0901 throw new IllegalArgumentException(format(
0902 "Population size must be greater than zero, but was %s.", size
0903 ));
0904 }
0905 _populationSize = size;
0906 }
0907
0908 /**
0909 * Set the (initial) population in form of a list of phenotypes. The fitness
0910 * function and fitness scaler of the phenotypes will be changed with the
0911 * current one of this GA. The fitness values are calculated as needed by
0912 * the next <i>evolve</i> step. <em>This method doesn't acquire the GA lock.
0913 * When used from another thread, the lock must be acquired from outside.</em>
0914 *
0915 * @see #setGenotypes(Collection)
0916 * @see #setup(Collection)
0917 * @param population The list of phenotypes to set. The population size is
0918 * set to {@code phenotype.size()}.
0919 * @throws NullPointerException if the population, or one of its element, is
0920 * {@code null}.
0921 * @throws IllegalArgumentException it the population size is smaller than
0922 * one.
0923 */
0924 public void setPopulation(final Collection<Phenotype<G, C>> population) {
0925 forEach(population, NonNull);
0926 if (population.size() < 1) {
0927 throw new IllegalArgumentException(format(
0928 "Population size must be greater than zero, but was %s.",
0929 population.size()
0930 ));
0931 }
0932
0933 final Population<G, C> pop = new Population<>(population.size());
0934 for (Phenotype<G, C> phenotype : population) {
0935 pop.add(phenotype.newInstance(
0936 _fitnessFunction, _fitnessScaler, _generation
0937 ));
0938 }
0939
0940 _population = pop;
0941 _populationSize = population.size();
0942 }
0943
0944 /**
0945 * Set/change the population in form of a list of genotypes. The fitness
0946 * function and fitness scaler will not be changed. The fitness values are
0947 * calculated as needed by the next <i>evolve</i> step. <em>This method
0948 * doesn't acquire the GA lock. When used from another thread, the lock must
0949 * be acquired from outside.</em>
0950 *
0951 * @see #setPopulation(Collection)
0952 * @see #setup(Collection)
0953 * @param genotypes The list of genotypes to set. The population size is set
0954 * to {@code genotypes.size()}.
0955 * @throws NullPointerException if the population, or one of its elements,
0956 * is {@code null}s.
0957 * @throws IllegalArgumentException it the population size is smaller than
0958 * one.
0959 */
0960 public void setGenotypes(final Collection<Genotype<G>> genotypes) {
0961 forEach(genotypes, NonNull);
0962 if (genotypes.size() < 1) {
0963 throw new IllegalArgumentException(
0964 "Genotype size must be greater than zero, but was " +
0965 genotypes.size() + ". "
0966 );
0967 }
0968
0969 final Population<G, C> population = new Population<>(genotypes.size());
0970 for (Genotype<G> genotype : genotypes) {
0971 population.add(Phenotype.of(
0972 genotype,
0973 _fitnessFunction,
0974 _fitnessScaler,
0975 _generation
0976 ));
0977 }
0978
0979 _population = population;
0980 _populationSize = genotypes.size();
0981 }
0982
0983 /**
0984 * Return a copy of the current population.
0985 *
0986 * @return The copy of the current population.
0987 */
0988 public Population<G, C> getPopulation() {
0989 return new Population<>(_population);
0990 }
0991
0992 /**
0993 * Return the desired population size of the GA.
0994 *
0995 * @return the desired population size of the GA.
0996 */
0997 public int getPopulationSize() {
0998 return _populationSize;
0999 }
1000
1001 /**
1002 * Return the statistics of the best phenotype. The returned statistics is
1003 * {@code null} if the algorithms hasn't been initialized.
1004 *
1005 * @return the statistics of the best phenotype, or {@code null} if the GA
1006 * hasn't been initialized yet.
1007 */
1008 public Statistics<G, C> getBestStatistics() {
1009 return _bestStatistics;
1010 }
1011
1012 /**
1013 * Return the number of killed phenotypes, so far.
1014 *
1015 * @return the number of killed phenotypes
1016 */
1017 public int getNumberOfKilledPhenotypes() {
1018 return _killed.get();
1019 }
1020
1021 /**
1022 * Return the number of invalid phenotypes, so far.
1023 *
1024 * @return the number of invalid phenotypes
1025 */
1026 public int getNumberOfInvalidPhenotypes() {
1027 return _invalid.get();
1028 }
1029
1030 /**
1031 * Set the statistic calculator for this genetic algorithm instance.
1032 *
1033 * @param calculator the new statistic calculator.
1034 * @throws NullPointerException if the given {@code calculator} is
1035 * {@code null}.
1036 */
1037 public void setStatisticsCalculator(
1038 final Statistics.Calculator<G, C> calculator
1039 ) {
1040 _calculator = requireNonNull(calculator, "Statistic calculator");
1041 }
1042
1043 /**
1044 * Return the current statistics calculator.
1045 *
1046 * @return the current statistics calculator.
1047 */
1048 public Statistics.Calculator<G, C> getStatisticsCalculator() {
1049 return _calculator;
1050 }
1051
1052 /**
1053 * Return the current time statistics of the GA. This method acquires the
1054 * lock to ensure that the returned values are consistent.
1055 *
1056 * @return the current time statistics.
1057 */
1058 public Statistics.Time getTimeStatistics() {
1059 _lock.lock();
1060 try {
1061 final Statistics.Time time = new Statistics.Time();
1062 time.alter.set(_alterTimer.getTime());
1063 time.combine.set(_combineTimer.getTime());
1064 time.evaluation.set(_evaluateTimer.getTime());
1065 time.execution.set(_executionTimer.getTime());
1066 time.selection.set(_selectTimer.getTime());
1067 time.statistics.set(_statisticTimer.getTime());
1068 return time;
1069 } finally {
1070 _lock.unlock();
1071 }
1072 }
1073
1074 /**
1075 * This method acquires the lock to ensure that the returned value is
1076 * consistent.
1077 */
1078 @Override
1079 public String toString() {
1080 Phenotype<G, C> phenotype = null;
1081 int generation = 0;
1082
1083 _lock.lock();
1084 try {
1085 generation = _generation;
1086 phenotype = getStatistics().getBestPhenotype();
1087 } finally {
1088 _lock.unlock();
1089 }
1090
1091 return format("%4d: (best) %s", generation, phenotype);
1092 }
1093
1094 }
|