|
10
|
1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
|
|
|
2
|
|
|
3
|
|
|
4
|
|
|
5
|
|
|
6
|
|
|
7
|
|
|
8
|
|
|
9
|
|
|
10
|
|
|
11
|
|
|
12
|
|
|
13 <html xmlns="http://www.w3.org/1999/xhtml">
|
|
|
14 <head>
|
|
|
15 <title>Math - The Commons Math User Guide - Genetic Algorithms</title>
|
|
|
16 <style type="text/css" media="all">
|
|
|
17 @import url("../css/maven-base.css");
|
|
|
18 @import url("../css/maven-theme.css");
|
|
|
19 @import url("../css/site.css");
|
|
|
20 </style>
|
|
|
21 <link rel="stylesheet" href="../css/print.css" type="text/css" media="print" />
|
|
|
22 <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1" />
|
|
|
23 </head>
|
|
|
24 <body class="composite">
|
|
|
25 <div id="banner">
|
|
|
26 <span id="bannerLeft">
|
|
|
27
|
|
|
28 Commons Math User Guide
|
|
|
29
|
|
|
30 </span>
|
|
|
31 <div class="clear">
|
|
|
32 <hr/>
|
|
|
33 </div>
|
|
|
34 </div>
|
|
|
35 <div id="breadcrumbs">
|
|
|
36
|
|
|
37
|
|
|
38
|
|
|
39
|
|
|
40
|
|
|
41
|
|
|
42
|
|
|
43
|
|
|
44 <div class="xright">
|
|
|
45
|
|
|
46
|
|
|
47
|
|
|
48
|
|
|
49
|
|
|
50
|
|
|
51
|
|
|
52 </div>
|
|
|
53 <div class="clear">
|
|
|
54 <hr/>
|
|
|
55 </div>
|
|
|
56 </div>
|
|
|
57 <div id="leftColumn">
|
|
|
58 <div id="navcolumn">
|
|
|
59
|
|
|
60
|
|
|
61
|
|
|
62
|
|
|
63
|
|
|
64
|
|
|
65
|
|
|
66
|
|
|
67 <h5>User Guide</h5>
|
|
|
68 <ul>
|
|
|
69
|
|
|
70 <li class="none">
|
|
|
71 <a href="../userguide/index.html">Contents</a>
|
|
|
72 </li>
|
|
|
73
|
|
|
74 <li class="none">
|
|
|
75 <a href="../userguide/overview.html">Overview</a>
|
|
|
76 </li>
|
|
|
77
|
|
|
78 <li class="none">
|
|
|
79 <a href="../userguide/stat.html">Statistics</a>
|
|
|
80 </li>
|
|
|
81
|
|
|
82 <li class="none">
|
|
|
83 <a href="../userguide/random.html">Data Generation</a>
|
|
|
84 </li>
|
|
|
85
|
|
|
86 <li class="none">
|
|
|
87 <a href="../userguide/linear.html">Linear Algebra</a>
|
|
|
88 </li>
|
|
|
89
|
|
|
90 <li class="none">
|
|
|
91 <a href="../userguide/analysis.html">Numerical Analysis</a>
|
|
|
92 </li>
|
|
|
93
|
|
|
94 <li class="none">
|
|
|
95 <a href="../userguide/special.html">Special Functions</a>
|
|
|
96 </li>
|
|
|
97
|
|
|
98 <li class="none">
|
|
|
99 <a href="../userguide/utilities.html">Utilities</a>
|
|
|
100 </li>
|
|
|
101
|
|
|
102 <li class="none">
|
|
|
103 <a href="../userguide/complex.html">Complex Numbers</a>
|
|
|
104 </li>
|
|
|
105
|
|
|
106 <li class="none">
|
|
|
107 <a href="../userguide/distribution.html">Distributions</a>
|
|
|
108 </li>
|
|
|
109
|
|
|
110 <li class="none">
|
|
|
111 <a href="../userguide/fraction.html">Fractions</a>
|
|
|
112 </li>
|
|
|
113
|
|
|
114 <li class="none">
|
|
|
115 <a href="../userguide/transform.html">Transform Methods</a>
|
|
|
116 </li>
|
|
|
117
|
|
|
118 <li class="none">
|
|
|
119 <a href="../userguide/geometry.html">3D Geometry</a>
|
|
|
120 </li>
|
|
|
121
|
|
|
122 <li class="none">
|
|
|
123 <a href="../userguide/optimization.html">Optimization</a>
|
|
|
124 </li>
|
|
|
125
|
|
|
126 <li class="none">
|
|
|
127 <a href="../userguide/ode.html">Ordinary Differential Equations</a>
|
|
|
128 </li>
|
|
|
129
|
|
|
130 <li class="none">
|
|
|
131 <strong>Genetic Algorithms</strong>
|
|
|
132 </li>
|
|
|
133 </ul>
|
|
|
134 <a href="http://maven.apache.org/" title="Built by Maven" class="poweredBy">
|
|
|
135 <img alt="Built by Maven" src="../images/logos/maven-feather.png"></img>
|
|
|
136 </a>
|
|
|
137
|
|
|
138
|
|
|
139
|
|
|
140
|
|
|
141
|
|
|
142
|
|
|
143
|
|
|
144
|
|
|
145 </div>
|
|
|
146 </div>
|
|
|
147 <div id="bodyColumn">
|
|
|
148 <div id="contentBox">
|
|
|
149 <div class="section"><h2><a name="a14_Genetic_Algorithms"></a>14 Genetic Algorithms</h2>
|
|
|
150 <div class="section"><h3><a name="a14.1_Overview"></a>14.1 Overview</h3>
|
|
|
151 <p>
|
|
|
152 The genetics package provides a framework and implementations for
|
|
|
153 genetic algorithms.
|
|
|
154 </p>
|
|
|
155 </div>
|
|
|
156 <div class="section"><h3><a name="a14.2_GA_Framework"></a>14.2 GA Framework</h3>
|
|
|
157 <p><a href="../apidocs/org/apache/commons/math/genetics/GeneticAlgorithm.html">
|
|
|
158 org.apache.commons.math.genetic.GeneticAlgorithm</a> provides an
|
|
|
159 execution framework for Genetic Algorithms (GA).
|
|
|
160 <a href="../apidocs/org/apache/commons/math/genetics/Population.html">Populations,</a> consisting
|
|
|
161 of <a href="../apidocs/org/apache/commons/math/genetics/Chromosome.html">
|
|
|
162 Chromosomes</a> are evolved by the <code>GeneticAlgorithm</code> until a
|
|
|
163 <a href="../apidocs/org/apache/commons/math/genetics/StoppingCondition.html">StoppingCondition</a>
|
|
|
164 is reached. Evolution is determined by
|
|
|
165 <a href="../apidocs/org/apache/commons/math/genetics/SelectionPolicy.html">SelectionPolicies</a>,
|
|
|
166 <a href="../apidocs/org/apache/commons/math/genetics/MutationPolicy.html"> MutationPolicies</a>
|
|
|
167 and <a href="../apidocs/org/apache/commons/math/genetics/Fitness.html">Fitness</a>.
|
|
|
168 </p>
|
|
|
169 <p>
|
|
|
170 The GA itself is implemented by the <code>evolve</code> method of the <code>GeneticAlgorithm</code> class,
|
|
|
171 which looks like this:
|
|
|
172 <div class="source"><pre>
|
|
|
173 public Population evolve(Population initial, StoppingCondition condition) {
|
|
|
174 Population current = initial;
|
|
|
175 while (!condition.isSatisfied(current)) {
|
|
|
176 current = nextGeneration(current);
|
|
|
177 }
|
|
|
178 return current;
|
|
|
179 }
|
|
|
180 </pre>
|
|
|
181 </div>
|
|
|
182
|
|
|
183 The <code>nextGeneration</code> method implements the following algorithm:
|
|
|
184 <ol type="1"><li>Get nextGeneration population to fill from <code>current</code>
|
|
|
185 generation, using its nextGeneration method</li>
|
|
|
186 <li>Loop until new generation is filled:</li>
|
|
|
187 <ul><li>Apply configured <code>SelectionPolicy</code> to select a pair of parents
|
|
|
188 from <code>current</code></li>
|
|
|
189 <li>With probability =
|
|
|
190 <a href="../apidocs/org/apache/commons/math/genetics/GeneticAlgorithm.html#getCrossoverRate()">
|
|
|
191 getCrossoverRate()</a>, apply configured <code>CrossoverPolicy</code> to parents</li>
|
|
|
192 <li>With probability =
|
|
|
193 <a href="../apidocs/org/apache/commons/math/genetics/GeneticAlgorithm.html#getMutationRate()">
|
|
|
194 getMutationRate()</a>,
|
|
|
195 apply configured <code>MutationPolicy</code> to each of the offspring</li>
|
|
|
196 <li>Add offspring individually to nextGeneration,
|
|
|
197 space permitting</li>
|
|
|
198 </ul>
|
|
|
199 <li>Return nextGeneration</li>
|
|
|
200 </ol>
|
|
|
201 </p>
|
|
|
202 </div>
|
|
|
203 <div class="section"><h3><a name="a14.3_Implementation"></a>14.3 Implementation</h3>
|
|
|
204 <p>
|
|
|
205 Here is an example GA execution:
|
|
|
206 <div class="source"><pre>
|
|
|
207 // initialize a new genetic algorithm
|
|
|
208 GeneticAlgorithm ga = new GeneticAlgorithm(
|
|
|
209 new OnePointCrossover<Integer>(),
|
|
|
210 1,
|
|
|
211 new RandomKeyMutation(),
|
|
|
212 0.10,
|
|
|
213 new TournamentSelection(TOURNAMENT_ARITY)
|
|
|
214 );
|
|
|
215
|
|
|
216 // initial population
|
|
|
217 Population initial = getInitialPopulation();
|
|
|
218
|
|
|
219 // stopping condition
|
|
|
220 StoppingCondition stopCond = new FixedGenerationCount(NUM_GENERATIONS);
|
|
|
221
|
|
|
222 // run the algorithm
|
|
|
223 Population finalPopulation = ga.evolve(initial, stopCond);
|
|
|
224
|
|
|
225 // best chromosome from the final population
|
|
|
226 Chromosome bestFinal = finalPopulation.getFittestChromosome();
|
|
|
227 </pre>
|
|
|
228 </div>
|
|
|
229
|
|
|
230 The arguments to the <code>GeneticAlgorithm</code> constructor above are: <br />
|
|
|
231 <table class="bodyTable"><tr class="a"><th>Parameter</th>
|
|
|
232 <th>value in example</th>
|
|
|
233 <th>meaning</th>
|
|
|
234 </tr>
|
|
|
235 <tr class="b"><td>crossoverPolicy</td>
|
|
|
236 <td><a href="../apidocs/org/apache/commons/math/genetics/OnePointCrossover.html">OnePointCrossover</a></td>
|
|
|
237 <td>A random crossover point is selected and the first part from each parent is copied to the corresponding
|
|
|
238 child, and the second parts are copied crosswise.</td>
|
|
|
239 </tr>
|
|
|
240 <tr class="a"><td>crossoverRate</td>
|
|
|
241 <td>1</td>
|
|
|
242 <td>Always apply crossover</td>
|
|
|
243 </tr>
|
|
|
244 <tr class="b"><td>mutationPolicy</td>
|
|
|
245 <td><a href="../apidocs/org/apache/commons/math/genetics/RandomKeyMutation.html">RandomKeyMutation</a></td>
|
|
|
246 <td>Changes a randomly chosen element of the array representation to a random value uniformly distributed in [0,1].</td>
|
|
|
247 </tr>
|
|
|
248 <tr class="a"><td>mutationRate</td>
|
|
|
249 <td>.1</td>
|
|
|
250 <td>Apply mutation with probability 0.1 - that is, 10% of the time.</td>
|
|
|
251 </tr>
|
|
|
252 <tr class="b"><td>selectionPolicy</td>
|
|
|
253 <td><a href="../apidocs/org/apache/commons/math/genetics/TournamentSelection.html">TournamentSelection</a></td>
|
|
|
254 <td>Each of the two selected chromosomes is selected based on an n-ary tournament -- this is done by drawing
|
|
|
255 n random chromosomes without replacement from the population, and then selecting the fittest chromosome among them.</td>
|
|
|
256 </tr>
|
|
|
257 </table>
|
|
|
258 <br />
|
|
|
259
|
|
|
260 The algorithm starts with an <code>initial</code> population of <code>Chromosomes.</code> and executes until
|
|
|
261 the specified <a href="../apidocs/org/apache/commons/math/genetics/StoppingCondition.html">StoppingCondition</a>
|
|
|
262 is reached. In the example above, a
|
|
|
263 <a href="../apidocs/org/apache/commons/math/genetics/FixedGenerationCount.html">FixedGenerationCount</a>
|
|
|
264 stopping condition is used, which means the algorithm proceeds through a fixed number of generations.
|
|
|
265 </p>
|
|
|
266 </div>
|
|
|
267 </div>
|
|
|
268
|
|
|
269 </div>
|
|
|
270 </div>
|
|
|
271 <div class="clear">
|
|
|
272 <hr/>
|
|
|
273 </div>
|
|
|
274 <div id="footer">
|
|
|
275 <div class="xright">©
|
|
|
276 2003-2010
|
|
|
277
|
|
|
278
|
|
|
279
|
|
|
280
|
|
|
281
|
|
|
282
|
|
|
283
|
|
|
284
|
|
|
285
|
|
|
286 </div>
|
|
|
287 <div class="clear">
|
|
|
288 <hr/>
|
|
|
289 </div>
|
|
|
290 </div>
|
|
|
291 </body>
|
|
|
292 </html>
|
