package-info.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-1.6.0).
003  * Copyright (c) 2007-2014 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  */
020 
021 /**
022  <h3>Introduction</h3>
023  *
024  * The <em>Jenetics</em> project provides a
025  * <a href="http://en.wikipedia.org/wiki/Genetic_algorithm" >Genetic Algorithm</a>
026  * (GA) implementation. The project has very few dependencies to other libraries.
027  * At runtime it only depends on the <em>Jenetics</em> library.
028  <p>
029  * The order of the single execution steps of genetic algorithms may slightly
030  * differ from implementation to implementation. The following pseudo-code shows
031  * the <em>Jenetics</em> genetic algorithm steps.
032  *
033  <img width="556" align="BOTTOM" border="0" alt="Genetic algorithm"
034  *      src="doc-files/genetic-algorithm.png" >
035  *
036  <p>
037  * Line (1) creates the initial population and the line (2) calculates the
038  * fitness value of the individuals. (This is done by the
039  * {@code GeneticAlgorithm.setup()} method.) Line (4) increases the generation
040  * number and line (5) and (6) selects the survivor and the offspring population.
041  * The offspring/survivor fraction is determined by the {@code offspringFraction}
042  * property of the GA. The selected offspring are altered in line (7). The next
043  * line combines the survivor population and the altered offspring population--
044  * after removing the died individuals--to the new population. The steps from
045  * line (4) to (9) are repeated until a given termination criterion is fulfilled.
046  *
047  *
048  <h3>Data structures</h3>
049  <p><img alt="Structure Diagram" src="doc-files/StructureClassDiagram.svg" ></p>
050  *
051  * The diagram above shows the main data structures of the GA implementation.
052  * The {@link org.jenetics.Gene} is the base of the building block. Genes are
053  * aggregated in {@link org.jenetics.Chromosome}s. One to n Chromosomes are
054  * aggregated in {@link org.jenetics.Genotype}s. A Genotype and a fitness
055  {@link org.jenetics.util.Function} form the {@link org.jenetics.Phenotype}.
056  * Phenotypes are collected into a {@link org.jenetics.Population}.
057  *
058  <h3>Getting started</h3>
059  *
060  * The minimum GA setup needs a genotype factory, {@code Factory<Genotype<?>>},
061  * and a fitness {@code Function}. The {@code Genotype} implements the
062  * {@code Factory} interface and can therefore be used as prototype for creating
063  * the initial Population and for creating new random Genotypes.
064  *
065  * [code]
066  * public static void main(final String[] args) {
067  *     final Factory〈Genotype〈BitGene〉〉 gtf = Genotype.of(
068  *         BitChromosome.of(10, 0.5)
069  *     );
070  *     final Function〈Genotype〈BitGene〉 Double〉 ff = ...
071  *     final GeneticAlgorithm〈BitGene, Double〉
072  *     ga = new GeneticAlgorithm〈〉(gtf, ff, Optimize.MAXIMUM)
073  *
074  *     ga.setup();
075  *     ga.evolve(100);
076  *     System.out.println(ga.getBestPhenotype());
077  * }
078  * [/code]
079  *
080  <p>
081  * The genotype factory, {@code gtf}, in the example above will create genotypes
082  * which consists of one {@code BitChromosome} with length 10. The one to zero
083  * probability of the newly created genotypes is set to 0.5. The fitness function
084  * is parameterized with a {@code BitGene} and a {@code Double}. That means
085  * that the fitness function is calculating the fitness value as {@code Double}.
086  * The return type of the fitness function must be at least a {@code Comparable}.
087  * The {@code GeneticAlgorithm} object is then created with the genotype factory
088  * and the fitness function. In this example the GA tries to maximize the fitness
089  * function. If you want to find the minimal value you have to change the optimize
090  * parameter from {@code Optimize.MAXIMUM} to {@code Optimize.MINIMUM}. The
091  * {@code ga.setup()} call creates the initial population and calculates its
092  * fitness value. Then the GA evolves 100 generations ({@code ga.evolve(100)})
093  * an prints the best phenotype found so far onto the console.
094  </p>
095  * In a more advanced setup you may want to change the default mutation and/or
096  * selection strategies.
097  *
098  * [code]
099  * public static void main(final String[] args) {
100  *     ...
101  *     ga.setSelectors(new RouletteWheelSelector〈BitGene〉());
102  *     ga.setAlterers(
103  *         new SinglePointCrossover〈BitGene〉(0.1),
104  *         new Mutator〈BitGene〉(0.01)
105  *     );
106  *
107  *     ga.setup();
108  *     ga.evolve(100);
109  *     System.out.println(ga.getBestPhenotype());
110  * }
111  * [/code]
112  *
113  <p>
114  * The selection strategy for offspring and survivors are set to the
115  * roulette-wheel selector. It is also possible to set the selector for
116  * offspring and survivors independently with the {@code setOffspringSelector}
117  * and {@code setSurvivorSelector} methods. The alterers are concatenated, at
118  * first the crossover (with probability 0.1) is performed and then the
119  * chromosomes are mutated (with probability 0.01).
120  </p>
121  *
122  <h3>Serialization</h3>
123  *
124  * With the serialization mechanism you can write a population to disk and load
125  * it into an GA at a later time. It can also be used to transfer populations to
126  * GAs, running on different hosts, over a network link. The IO class, located
127  * in the {@code org.jenetics.util} package, supports native Java serialization
128  * and XML serialization. For XML marshaling <em>Jenetics</em> internally uses
129  * the XML support from the Javolution project.
130  *
131  * [code]
132  * // Writing the population to disk.
133  * final File file = new File("population.xml");
134  * IO.jaxb.write(ga.getPopulation(), file);
135  *
136  * // Reading the population from disk.
137  * final Population〈DoubleGene,Double〉 population =
138  *     (Population〈DoubleGene, Double〉)IO.jaxb.read(file);
139  * ga.setPopulation(population);
140  * [/code]
141  *
142  *
143  <h3>Examples</h3>
144  *
145  <h4>Ones Counting</h4>
146  * Ones counting is one of the simplest model-problem. It uses a binary
147  * chromosome and forms a classic genetic algorithm. In the classic genetic
148  * algorithm the problem is a maximization problem and the fitness function is
149  * positive. The domain of the fitness function is a bit-chromosome. The fitness
150  * of a Genotype is proportional to the number of ones.
151  *
152  * [code]
153  * import org.jenetics.BitChromosome;
154  * import org.jenetics.BitGene;
155  * import org.jenetics.GeneticAlgorithm;
156  * import org.jenetics.Genotype;
157  * import org.jenetics.Mutator;
158  * import org.jenetics.NumberStatistics;
159  * import org.jenetics.Optimize;
160  * import org.jenetics.RouletteWheelSelector;
161  * import org.jenetics.SinglePointCrossover;
162  * import org.jenetics.util.Factory;
163  * import org.jenetics.util.Function;
164  *
165  * final class OneCounter
166  *     implements Function〈Genotype〈BitGene〉, Integer〉
167  * {
168  *     \@Override
169  *     public Integer apply(final Genotype〈BitGene〉 genotype) {
170  *         return ((BitChromosome)genotype.getChromosome()).bitCount();
171  *     }
172  * }
173  *
174  * public class OnesCounting {
175  *     public static void main(String[] args) {
176  *         final Factory〈Genotype〈BitGene〉〉 gtf = Genotype.of(
177  *             BitChromosome.of(20, 0.15)
178  *         );
179  *         final Function〈Genotype〈BitGene〉, Integer〉 ff = new OneCounter();
180  *         final GeneticAlgorithm〈BitGene, Integer〉 ga =
181  *             new GeneticAlgorithm〈〉(gtf, ff, Optimize.MAXIMUM);
182  *
183  *         ga.setStatisticsCalculator(
184  *             new NumberStatistics.Calculator〈BitGene, Integer〉()
185  *         );
186  *         ga.setPopulationSize(50);
187  *         ga.setSelectors(
188  *             new RouletteWheelSelector〈BitGene, Integer〉()
189  *         );
190  *         ga.setAlterers(
191  *             new Mutator〈BitGene〉(0.55),
192  *             new SinglePointCrossover〈BitGene〉(0.06)
193  *         );
194  *
195  *         ga.setup();
196  *         ga.evolve(100);
197  *         System.out.println(ga.getBestStatistics());
198  *     }
199  * }
200  * [/code]
201  *
202  * The genotype in this example consists of one BitChromosome with a ones
203  * probability of 0.15. The altering of the offspring population is performed
204  * by mutation, with mutation probability of 0.55, and then by a single-point
205  * crossover, with crossover probability of 0.06. After creating the initial
206  * population, with the ga.setup() call, 100 generations are evolved. The
207  * tournament selector is used for both, the offspring- and the survivor
208  * selection---this is the default selector.
209  *
210  *
211  <h4>Traveling Salesman</h4>
212  *
213  * The Traveling Salesman problem is one of the classical problems in
214  * computational mathematics and it is the most notorious NP-complete problem.
215  * The goal is to find the shortest distance, or the path, with the least costs,
216  * between N  different cities. Testing all possible path for N  cities would
217  * lead to N!  checks to find the shortest one.
218  * The following example uses a path where the cities are lying on a circle.
219  * That means, the optimal path will be a polygon. This makes it easier to check
220  * the quality of the found solution.
221  *
222  * [code]
223  * import static java.lang.Math.PI;
224  * import static java.lang.Math.abs;
225  * import static java.lang.Math.sin;
226  *
227  * import org.jenetics.Chromosome;
228  * import org.jenetics.EnumGene;
229  * import org.jenetics.GeneticAlgorithm;
230  * import org.jenetics.Genotype;
231  * import org.jenetics.NumberStatistics.Calculator;
232  * import org.jenetics.Optimize;
233  * import org.jenetics.PartiallyMatchedCrossover;
234  * import org.jenetics.PermutationChromosome;
235  * import org.jenetics.SwapMutator;
236  * import org.jenetics.util.Factory;
237  * import org.jenetics.util.Function;
238  *
239  * class FF
240  *     implements Function〈Genotype〈EnumGene<Integer〉〉, Double〉
241  * {
242  *     private final double[][] _adjacence;
243  *     public FF(final double[][] adjacence) {
244  *         _adjacence = adjacence;
245  *     }
246  *
247  *     \@Override
248  *     public Double apply(final Genotype〈EnumGene〈Integer〉〉 genotype) {
249  *         final Chromosome〈EnumGene〈Integer〉〉 path =
250  *             genotype.getChromosome();
251  *
252  *         double length = 0.0;
253  *         for (int i = 0, n = path.length(); i 〈 n; ++i) {
254  *             final int from = path.getGene(i).getAllele();
255  *             final int to = path.getGene((i + 1)%n).getAllele();
256  *             length += _adjacence[from][to];
257  *         }
258  *         return length;
259  *     }
260  * }
261  *
262  * public class TravelingSalesman {
263  *
264  *     public static void main(String[] args) {
265  *         final int stops = 20;
266  *
267  *         final Function〈Genotype〈EnumGene〈Integer〉〉, Double〉 ff =
268  *             new FF(adjacencyMatrix(stops));
269  *         final Factory〈Genotype〈EnumGene〈Integer〉〉〉 gt = Genotype.of(
270  *             PermutationChromosome.ofInteger(stops)
271  *         );
272  *         final GeneticAlgorithm〈EnumGene〈Integer〉, Double〉
273  *             ga = new GeneticAlgorithm〈〉(gt, ff, Optimize.MINIMUM);
274  *         ga.setStatisticsCalculator(
275  *             new Calculator〈EnumGene〈Integer〉, Double〉()
276  *         );
277  *         ga.setPopulationSize(300);
278  *         ga.setAlterers(
279  *             new SwapMutator〈EnumGene〈Integer〉〉(0.2),
280  *             new PartiallyMatchedCrossover〈Integer〉(0.3)
281  *         );
282  *
283  *         ga.setup();
284  *         ga.evolve(700);
285  *         System.out.println(ga.getBestStatistics());
286  *         System.out.println(ga.getBestPhenotype());
287  *     }
288  *
289  *     private static double[][] adjacencyMatrix(int stops) {
290  *         double[][] matrix = new double[stops][stops];
291  *         for (int i = 0; i 〈 stops; ++i) {
292  *             for (int j = 0; j 〈 stops; ++j) {
293  *                 matrix[i][j] = chord(stops, abs(i - j), RADIUS);
294  *             }
295  *         }
296  *         return matrix;
297  *     }
298  *     private static double chord(int stops, int i, double r) {
299  *         return 2.0*r*abs(sin((PI*i)/stops));
300  *     }
301  *     private static double RADIUS = 10.0;
302  * }
303  * [/code]
304  *
305  * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
306  @since 1.0
307  @version 1.6 &mdash; <em>$Date: 2014-03-05 $</em>
308  */
309 package org.jenetics;