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 — <em>$Date: 2014-03-05 $</em>
308 */
309 package org.jenetics;
|