Mercurial > hg > de.mpg.mpiwg.itgroup.digilib.plugin

comparison libs/commons-math-2.1/docs/apidocs/src-html/org/apache/commons/math/genetics/GeneticAlgorithm.html @ 13:cbf34dd4d7e6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
commons-math-2.1 added
author dwinter
date Tue, 04 Jan 2011 10:02:07 +0100
parents
children
comparison
equal deleted inserted replaced
12:970d26a94fb7 13:cbf34dd4d7e6
1 <HTML>
2 <BODY BGCOLOR="white">
3 <PRE>
4 <FONT color="green">001</FONT> /*<a name="line.1"></a>
5 <FONT color="green">002</FONT> * Licensed to the Apache Software Foundation (ASF) under one or more<a name="line.2"></a>
6 <FONT color="green">003</FONT> * contributor license agreements. See the NOTICE file distributed with<a name="line.3"></a>
7 <FONT color="green">004</FONT> * this work for additional information regarding copyright ownership.<a name="line.4"></a>
8 <FONT color="green">005</FONT> * The ASF licenses this file to You under the Apache License, Version 2.0<a name="line.5"></a>
9 <FONT color="green">006</FONT> * (the "License"); you may not use this file except in compliance with<a name="line.6"></a>
10 <FONT color="green">007</FONT> * the License. You may obtain a copy of the License at<a name="line.7"></a>
11 <FONT color="green">008</FONT> *<a name="line.8"></a>
12 <FONT color="green">009</FONT> * http://www.apache.org/licenses/LICENSE-2.0<a name="line.9"></a>
13 <FONT color="green">010</FONT> *<a name="line.10"></a>
14 <FONT color="green">011</FONT> * Unless required by applicable law or agreed to in writing, software<a name="line.11"></a>
15 <FONT color="green">012</FONT> * distributed under the License is distributed on an "AS IS" BASIS,<a name="line.12"></a>
16 <FONT color="green">013</FONT> * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.<a name="line.13"></a>
17 <FONT color="green">014</FONT> * See the License for the specific language governing permissions and<a name="line.14"></a>
18 <FONT color="green">015</FONT> * limitations under the License.<a name="line.15"></a>
19 <FONT color="green">016</FONT> */<a name="line.16"></a>
20 <FONT color="green">017</FONT> package org.apache.commons.math.genetics;<a name="line.17"></a>
21 <FONT color="green">018</FONT> <a name="line.18"></a>
22 <FONT color="green">019</FONT> import org.apache.commons.math.random.RandomGenerator;<a name="line.19"></a>
23 <FONT color="green">020</FONT> import org.apache.commons.math.random.JDKRandomGenerator;<a name="line.20"></a>
24 <FONT color="green">021</FONT> <a name="line.21"></a>
25 <FONT color="green">022</FONT> /**<a name="line.22"></a>
26 <FONT color="green">023</FONT> * Implementation of a genetic algorithm. All factors that govern the operation<a name="line.23"></a>
27 <FONT color="green">024</FONT> * of the algorithm can be configured for a specific problem.<a name="line.24"></a>
28 <FONT color="green">025</FONT> *<a name="line.25"></a>
29 <FONT color="green">026</FONT> * @since 2.0<a name="line.26"></a>
30 <FONT color="green">027</FONT> * @version $Revision: 925812 $ $Date: 2010-03-21 11:49:31 -0400 (Sun, 21 Mar 2010) $<a name="line.27"></a>
31 <FONT color="green">028</FONT> */<a name="line.28"></a>
32 <FONT color="green">029</FONT> public class GeneticAlgorithm {<a name="line.29"></a>
33 <FONT color="green">030</FONT> <a name="line.30"></a>
34 <FONT color="green">031</FONT> /**<a name="line.31"></a>
35 <FONT color="green">032</FONT> * Static random number generator shared by GA implementation classes.<a name="line.32"></a>
36 <FONT color="green">033</FONT> * Set the randomGenerator seed to get reproducible results.<a name="line.33"></a>
37 <FONT color="green">034</FONT> * Use {@link #setRandomGenerator(RandomGenerator)} to supply an alternative<a name="line.34"></a>
38 <FONT color="green">035</FONT> * to the default JDK-provided PRNG.<a name="line.35"></a>
39 <FONT color="green">036</FONT> */<a name="line.36"></a>
40 <FONT color="green">037</FONT> //@GuardedBy("this")<a name="line.37"></a>
41 <FONT color="green">038</FONT> private static RandomGenerator randomGenerator = new JDKRandomGenerator();<a name="line.38"></a>
42 <FONT color="green">039</FONT> <a name="line.39"></a>
43 <FONT color="green">040</FONT> /** the crossover policy used by the algorithm. */<a name="line.40"></a>
44 <FONT color="green">041</FONT> private final CrossoverPolicy crossoverPolicy;<a name="line.41"></a>
45 <FONT color="green">042</FONT> <a name="line.42"></a>
46 <FONT color="green">043</FONT> /** the rate of crossover for the algorithm. */<a name="line.43"></a>
47 <FONT color="green">044</FONT> private final double crossoverRate;<a name="line.44"></a>
48 <FONT color="green">045</FONT> <a name="line.45"></a>
49 <FONT color="green">046</FONT> /** the mutation policy used by the algorithm. */<a name="line.46"></a>
50 <FONT color="green">047</FONT> private final MutationPolicy mutationPolicy;<a name="line.47"></a>
51 <FONT color="green">048</FONT> <a name="line.48"></a>
52 <FONT color="green">049</FONT> /** the rate of mutation for the algorithm. */<a name="line.49"></a>
53 <FONT color="green">050</FONT> private final double mutationRate;<a name="line.50"></a>
54 <FONT color="green">051</FONT> <a name="line.51"></a>
55 <FONT color="green">052</FONT> /** the selection policy used by the algorithm. */<a name="line.52"></a>
56 <FONT color="green">053</FONT> private final SelectionPolicy selectionPolicy;<a name="line.53"></a>
57 <FONT color="green">054</FONT> <a name="line.54"></a>
58 <FONT color="green">055</FONT> /** the number of generations evolved to reach {@link StoppingCondition} in the last run. */<a name="line.55"></a>
59 <FONT color="green">056</FONT> private int generationsEvolved = 0;<a name="line.56"></a>
60 <FONT color="green">057</FONT> <a name="line.57"></a>
61 <FONT color="green">058</FONT> /**<a name="line.58"></a>
62 <FONT color="green">059</FONT> * @param crossoverPolicy The {@link CrossoverPolicy}<a name="line.59"></a>
63 <FONT color="green">060</FONT> * @param crossoverRate The crossover rate as a percentage (0-1 inclusive)<a name="line.60"></a>
64 <FONT color="green">061</FONT> * @param mutationPolicy The {@link MutationPolicy}<a name="line.61"></a>
65 <FONT color="green">062</FONT> * @param mutationRate The mutation rate as a percentage (0-1 inclusive)<a name="line.62"></a>
66 <FONT color="green">063</FONT> * @param selectionPolicy The {@link SelectionPolicy}<a name="line.63"></a>
67 <FONT color="green">064</FONT> */<a name="line.64"></a>
68 <FONT color="green">065</FONT> public GeneticAlgorithm(<a name="line.65"></a>
69 <FONT color="green">066</FONT> CrossoverPolicy crossoverPolicy, double crossoverRate,<a name="line.66"></a>
70 <FONT color="green">067</FONT> MutationPolicy mutationPolicy, double mutationRate,<a name="line.67"></a>
71 <FONT color="green">068</FONT> SelectionPolicy selectionPolicy) {<a name="line.68"></a>
72 <FONT color="green">069</FONT> if (crossoverRate &lt; 0 || crossoverRate &gt; 1) {<a name="line.69"></a>
73 <FONT color="green">070</FONT> throw new IllegalArgumentException("crossoverRate must be between 0 and 1");<a name="line.70"></a>
74 <FONT color="green">071</FONT> }<a name="line.71"></a>
75 <FONT color="green">072</FONT> if (mutationRate &lt; 0 || mutationRate &gt; 1) {<a name="line.72"></a>
76 <FONT color="green">073</FONT> throw new IllegalArgumentException("mutationRate must be between 0 and 1");<a name="line.73"></a>
77 <FONT color="green">074</FONT> }<a name="line.74"></a>
78 <FONT color="green">075</FONT> this.crossoverPolicy = crossoverPolicy;<a name="line.75"></a>
79 <FONT color="green">076</FONT> this.crossoverRate = crossoverRate;<a name="line.76"></a>
80 <FONT color="green">077</FONT> this.mutationPolicy = mutationPolicy;<a name="line.77"></a>
81 <FONT color="green">078</FONT> this.mutationRate = mutationRate;<a name="line.78"></a>
82 <FONT color="green">079</FONT> this.selectionPolicy = selectionPolicy;<a name="line.79"></a>
83 <FONT color="green">080</FONT> }<a name="line.80"></a>
84 <FONT color="green">081</FONT> <a name="line.81"></a>
85 <FONT color="green">082</FONT> /**<a name="line.82"></a>
86 <FONT color="green">083</FONT> * Set the (static) random generator.<a name="line.83"></a>
87 <FONT color="green">084</FONT> *<a name="line.84"></a>
88 <FONT color="green">085</FONT> * @param random random generator<a name="line.85"></a>
89 <FONT color="green">086</FONT> */<a name="line.86"></a>
90 <FONT color="green">087</FONT> public static synchronized void setRandomGenerator(RandomGenerator random) {<a name="line.87"></a>
91 <FONT color="green">088</FONT> randomGenerator = random;<a name="line.88"></a>
92 <FONT color="green">089</FONT> }<a name="line.89"></a>
93 <FONT color="green">090</FONT> <a name="line.90"></a>
94 <FONT color="green">091</FONT> /**<a name="line.91"></a>
95 <FONT color="green">092</FONT> * Returns the (static) random generator.<a name="line.92"></a>
96 <FONT color="green">093</FONT> *<a name="line.93"></a>
97 <FONT color="green">094</FONT> * @return the static random generator shared by GA implementation classes<a name="line.94"></a>
98 <FONT color="green">095</FONT> */<a name="line.95"></a>
99 <FONT color="green">096</FONT> public static synchronized RandomGenerator getRandomGenerator() {<a name="line.96"></a>
100 <FONT color="green">097</FONT> return randomGenerator;<a name="line.97"></a>
101 <FONT color="green">098</FONT> }<a name="line.98"></a>
102 <FONT color="green">099</FONT> <a name="line.99"></a>
103 <FONT color="green">100</FONT> /**<a name="line.100"></a>
104 <FONT color="green">101</FONT> * Evolve the given population. Evolution stops when the stopping condition<a name="line.101"></a>
105 <FONT color="green">102</FONT> * is satisfied. Updates the {@link #getGenerationsEvolved() generationsEvolved}<a name="line.102"></a>
106 <FONT color="green">103</FONT> * property with the number of generations evolved before the StoppingCondition<a name="line.103"></a>
107 <FONT color="green">104</FONT> * is satisfied.<a name="line.104"></a>
108 <FONT color="green">105</FONT> *<a name="line.105"></a>
109 <FONT color="green">106</FONT> * @param initial the initial, seed population.<a name="line.106"></a>
110 <FONT color="green">107</FONT> * @param condition the stopping condition used to stop evolution.<a name="line.107"></a>
111 <FONT color="green">108</FONT> * @return the population that satisfies the stopping condition.<a name="line.108"></a>
112 <FONT color="green">109</FONT> */<a name="line.109"></a>
113 <FONT color="green">110</FONT> public Population evolve(Population initial, StoppingCondition condition) {<a name="line.110"></a>
114 <FONT color="green">111</FONT> Population current = initial;<a name="line.111"></a>
115 <FONT color="green">112</FONT> generationsEvolved = 0;<a name="line.112"></a>
116 <FONT color="green">113</FONT> while (!condition.isSatisfied(current)) {<a name="line.113"></a>
117 <FONT color="green">114</FONT> current = nextGeneration(current);<a name="line.114"></a>
118 <FONT color="green">115</FONT> generationsEvolved++;<a name="line.115"></a>
119 <FONT color="green">116</FONT> }<a name="line.116"></a>
120 <FONT color="green">117</FONT> return current;<a name="line.117"></a>
121 <FONT color="green">118</FONT> }<a name="line.118"></a>
122 <FONT color="green">119</FONT> <a name="line.119"></a>
123 <FONT color="green">120</FONT> /**<a name="line.120"></a>
124 <FONT color="green">121</FONT> * &lt;p&gt;Evolve the given population into the next generation.&lt;/p&gt;<a name="line.121"></a>
125 <FONT color="green">122</FONT> * &lt;p&gt;&lt;ol&gt;<a name="line.122"></a>
126 <FONT color="green">123</FONT> * &lt;li&gt;Get nextGeneration population to fill from &lt;code&gt;current&lt;/code&gt;<a name="line.123"></a>
127 <FONT color="green">124</FONT> * generation, using its nextGeneration method&lt;/li&gt;<a name="line.124"></a>
128 <FONT color="green">125</FONT> * &lt;li&gt;Loop until new generation is filled:&lt;/li&gt;<a name="line.125"></a>
129 <FONT color="green">126</FONT> * &lt;ul&gt;&lt;li&gt;Apply configured SelectionPolicy to select a pair of parents<a name="line.126"></a>
130 <FONT color="green">127</FONT> * from &lt;code&gt;current&lt;/code&gt;&lt;/li&gt;<a name="line.127"></a>
131 <FONT color="green">128</FONT> * &lt;li&gt;With probability = {@link #getCrossoverRate()}, apply<a name="line.128"></a>
132 <FONT color="green">129</FONT> * configured {@link CrossoverPolicy} to parents&lt;/li&gt;<a name="line.129"></a>
133 <FONT color="green">130</FONT> * &lt;li&gt;With probability = {@link #getMutationRate()}, apply<a name="line.130"></a>
134 <FONT color="green">131</FONT> * configured {@link MutationPolicy} to each of the offspring&lt;/li&gt;<a name="line.131"></a>
135 <FONT color="green">132</FONT> * &lt;li&gt;Add offspring individually to nextGeneration,<a name="line.132"></a>
136 <FONT color="green">133</FONT> * space permitting&lt;/li&gt;<a name="line.133"></a>
137 <FONT color="green">134</FONT> * &lt;/ul&gt;<a name="line.134"></a>
138 <FONT color="green">135</FONT> * &lt;li&gt;Return nextGeneration&lt;/li&gt;<a name="line.135"></a>
139 <FONT color="green">136</FONT> * &lt;/ol&gt;<a name="line.136"></a>
140 <FONT color="green">137</FONT> * &lt;/p&gt;<a name="line.137"></a>
141 <FONT color="green">138</FONT> *<a name="line.138"></a>
142 <FONT color="green">139</FONT> * @param current the current population.<a name="line.139"></a>
143 <FONT color="green">140</FONT> * @return the population for the next generation.<a name="line.140"></a>
144 <FONT color="green">141</FONT> */<a name="line.141"></a>
145 <FONT color="green">142</FONT> public Population nextGeneration(Population current) {<a name="line.142"></a>
146 <FONT color="green">143</FONT> Population nextGeneration = current.nextGeneration();<a name="line.143"></a>
147 <FONT color="green">144</FONT> <a name="line.144"></a>
148 <FONT color="green">145</FONT> RandomGenerator randGen = getRandomGenerator();<a name="line.145"></a>
149 <FONT color="green">146</FONT> <a name="line.146"></a>
150 <FONT color="green">147</FONT> while (nextGeneration.getPopulationSize() &lt; nextGeneration.getPopulationLimit()) {<a name="line.147"></a>
151 <FONT color="green">148</FONT> // select parent chromosomes<a name="line.148"></a>
152 <FONT color="green">149</FONT> ChromosomePair pair = getSelectionPolicy().select(current);<a name="line.149"></a>
153 <FONT color="green">150</FONT> <a name="line.150"></a>
154 <FONT color="green">151</FONT> // crossover?<a name="line.151"></a>
155 <FONT color="green">152</FONT> if (randGen.nextDouble() &lt; getCrossoverRate()) {<a name="line.152"></a>
156 <FONT color="green">153</FONT> // apply crossover policy to create two offspring<a name="line.153"></a>
157 <FONT color="green">154</FONT> pair = getCrossoverPolicy().crossover(pair.getFirst(), pair.getSecond());<a name="line.154"></a>
158 <FONT color="green">155</FONT> }<a name="line.155"></a>
159 <FONT color="green">156</FONT> <a name="line.156"></a>
160 <FONT color="green">157</FONT> // mutation?<a name="line.157"></a>
161 <FONT color="green">158</FONT> if (randGen.nextDouble() &lt; getMutationRate()) {<a name="line.158"></a>
162 <FONT color="green">159</FONT> // apply mutation policy to the chromosomes<a name="line.159"></a>
163 <FONT color="green">160</FONT> pair = new ChromosomePair(<a name="line.160"></a>
164 <FONT color="green">161</FONT> getMutationPolicy().mutate(pair.getFirst()),<a name="line.161"></a>
165 <FONT color="green">162</FONT> getMutationPolicy().mutate(pair.getSecond()));<a name="line.162"></a>
166 <FONT color="green">163</FONT> }<a name="line.163"></a>
167 <FONT color="green">164</FONT> <a name="line.164"></a>
168 <FONT color="green">165</FONT> // add the first chromosome to the population<a name="line.165"></a>
169 <FONT color="green">166</FONT> nextGeneration.addChromosome(pair.getFirst());<a name="line.166"></a>
170 <FONT color="green">167</FONT> // is there still a place for the second chromosome?<a name="line.167"></a>
171 <FONT color="green">168</FONT> if (nextGeneration.getPopulationSize() &lt; nextGeneration.getPopulationLimit()) {<a name="line.168"></a>
172 <FONT color="green">169</FONT> // add the second chromosome to the population<a name="line.169"></a>
173 <FONT color="green">170</FONT> nextGeneration.addChromosome(pair.getSecond());<a name="line.170"></a>
174 <FONT color="green">171</FONT> }<a name="line.171"></a>
175 <FONT color="green">172</FONT> }<a name="line.172"></a>
176 <FONT color="green">173</FONT> <a name="line.173"></a>
177 <FONT color="green">174</FONT> return nextGeneration;<a name="line.174"></a>
178 <FONT color="green">175</FONT> }<a name="line.175"></a>
179 <FONT color="green">176</FONT> <a name="line.176"></a>
180 <FONT color="green">177</FONT> /**<a name="line.177"></a>
181 <FONT color="green">178</FONT> * Returns the crossover policy.<a name="line.178"></a>
182 <FONT color="green">179</FONT> * @return crossover policy<a name="line.179"></a>
183 <FONT color="green">180</FONT> */<a name="line.180"></a>
184 <FONT color="green">181</FONT> public CrossoverPolicy getCrossoverPolicy() {<a name="line.181"></a>
185 <FONT color="green">182</FONT> return crossoverPolicy;<a name="line.182"></a>
186 <FONT color="green">183</FONT> }<a name="line.183"></a>
187 <FONT color="green">184</FONT> <a name="line.184"></a>
188 <FONT color="green">185</FONT> /**<a name="line.185"></a>
189 <FONT color="green">186</FONT> * Returns the crossover rate.<a name="line.186"></a>
190 <FONT color="green">187</FONT> * @return crossover rate<a name="line.187"></a>
191 <FONT color="green">188</FONT> */<a name="line.188"></a>
192 <FONT color="green">189</FONT> public double getCrossoverRate() {<a name="line.189"></a>
193 <FONT color="green">190</FONT> return crossoverRate;<a name="line.190"></a>
194 <FONT color="green">191</FONT> }<a name="line.191"></a>
195 <FONT color="green">192</FONT> <a name="line.192"></a>
196 <FONT color="green">193</FONT> /**<a name="line.193"></a>
197 <FONT color="green">194</FONT> * Returns the mutation policy.<a name="line.194"></a>
198 <FONT color="green">195</FONT> * @return mutation policy<a name="line.195"></a>
199 <FONT color="green">196</FONT> */<a name="line.196"></a>
200 <FONT color="green">197</FONT> public MutationPolicy getMutationPolicy() {<a name="line.197"></a>
201 <FONT color="green">198</FONT> return mutationPolicy;<a name="line.198"></a>
202 <FONT color="green">199</FONT> }<a name="line.199"></a>
203 <FONT color="green">200</FONT> <a name="line.200"></a>
204 <FONT color="green">201</FONT> /**<a name="line.201"></a>
205 <FONT color="green">202</FONT> * Returns the mutation rate.<a name="line.202"></a>
206 <FONT color="green">203</FONT> * @return mutation rate<a name="line.203"></a>
207 <FONT color="green">204</FONT> */<a name="line.204"></a>
208 <FONT color="green">205</FONT> public double getMutationRate() {<a name="line.205"></a>
209 <FONT color="green">206</FONT> return mutationRate;<a name="line.206"></a>
210 <FONT color="green">207</FONT> }<a name="line.207"></a>
211 <FONT color="green">208</FONT> <a name="line.208"></a>
212 <FONT color="green">209</FONT> /**<a name="line.209"></a>
213 <FONT color="green">210</FONT> * Returns the selection policy.<a name="line.210"></a>
214 <FONT color="green">211</FONT> * @return selection policy<a name="line.211"></a>
215 <FONT color="green">212</FONT> */<a name="line.212"></a>
216 <FONT color="green">213</FONT> public SelectionPolicy getSelectionPolicy() {<a name="line.213"></a>
217 <FONT color="green">214</FONT> return selectionPolicy;<a name="line.214"></a>
218 <FONT color="green">215</FONT> }<a name="line.215"></a>
219 <FONT color="green">216</FONT> <a name="line.216"></a>
220 <FONT color="green">217</FONT> /**<a name="line.217"></a>
221 <FONT color="green">218</FONT> * Returns the number of generations evolved to<a name="line.218"></a>
222 <FONT color="green">219</FONT> * reach {@link StoppingCondition} in the last run.<a name="line.219"></a>
223 <FONT color="green">220</FONT> *<a name="line.220"></a>
224 <FONT color="green">221</FONT> * @return number of generations evolved<a name="line.221"></a>
225 <FONT color="green">222</FONT> * @since 2.1<a name="line.222"></a>
226 <FONT color="green">223</FONT> */<a name="line.223"></a>
227 <FONT color="green">224</FONT> public int getGenerationsEvolved() {<a name="line.224"></a>
228 <FONT color="green">225</FONT> return generationsEvolved;<a name="line.225"></a>
229 <FONT color="green">226</FONT> }<a name="line.226"></a>
230 <FONT color="green">227</FONT> <a name="line.227"></a>
231 <FONT color="green">228</FONT> }<a name="line.228"></a>
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292 </PRE>
293 </BODY>
294 </HTML>