001 package org.jaga.masterAlgorithm;
002
003 import java.util.ArrayList;
004 import java.util.Iterator;
005
006 import org.jaga.definitions.*;
007 import org.jaga.util.*;
008 import org.jaga.hooks.*;
009
010 /**
011 * TODO: Complete these comments.
012 *
013 * <p><u>Project:</u> JAGA - Java API for Genetic Algorithms.</p>
014 *
015 * <p><u>Company:</u> University College London and JAGA.Org
016 * (<a href="http://www.jaga.org" target="_blank">http://www.jaga.org</a>).
017 * </p>
018 *
019 * <p><u>Copyright:</u> (c) 2004 by G. Paperin.<br/>
020 * This program is free software; you can redistribute it and/or modify
021 * it under the terms of the GNU General Public License as published by
022 * the Free Software Foundation, ONLY if you include a note of the original
023 * author(s) in any redistributed/modified copy.<br/>
024 * This program is distributed in the hope that it will be useful,
025 * but WITHOUT ANY WARRANTY; without even the implied warranty of
026 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
027 * GNU General Public License for more details.<br/>
028 * You should have received a copy of the GNU General Public License
029 * along with this program; if not, write to the Free Software
030 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
031 * or see http://www.gnu.org/licenses/gpl.html</p>
032 *
033 * @author Greg Paperin (greg@jaga.org)
034 *
035 * @version JAGA public release 1.0 beta
036 */
037
038 public class SimpleGA implements GeneticAlgorithm {
039
040 private ArrayList hooks = null;
041
042 public SimpleGA() {}
043
044 public GAResult exec(GAParameterSet params) {
045
046 if (null == params)
047 throw new NullPointerException("Parameters to a GA may not be null");
048
049 int age = 0;
050 Population pop = createInitialPopulation(params);
051 FittestIndividualResult result = (FittestIndividualResult) createResult();
052 for (int i = 0; i < pop.getSize(); updateIndividualFitness(pop.getMember(i++), pop, age, params));
053 checkForBetterResult(result, pop, params);
054 notifyInitialisationDone(pop, age, result, params);
055
056 while (! terminationConditionApplies(pop, age, result, params)) {
057
058 Individual best = result.getFittestIndividual();
059
060 Population nextPop = generateNextPopulation(pop, age, result, params);
061
062 pop = nextPop;
063 age++;
064 notifyGenerationChanged(pop, age, result, params);
065
066 if (result.getFittestIndividual() != best)
067 notifyFoundNewResult(pop, age, result, params);
068
069 }
070
071 notifyTerminationConditionApplies(pop, age, result, params);
072
073 return result;
074 }
075
076 protected Population generateNextPopulation(Population oldPop, int age,
077 GAResult result, GAParameterSet params) {
078 FittestIndividualResult res = (FittestIndividualResult) result;
079 Population newPop = createEmptyPopulation(params);
080 while (newPop.getSize() < params.getPopulationSize()) {
081
082 Individual [] parents = selectForReproduction(oldPop, age, params);
083 notifySelectedForReproduction(parents, oldPop, age, result, params);
084
085 Individual [] children = haveSex(parents, params);
086 for (int i = 0; i < children.length; i++) {
087 if (null != children[i].getFitness())
088 continue;
089 updateIndividualFitness(children[i], oldPop, age, params);
090 if (children[i].getFitness().isBetter(res.getBestFitness()))
091 res.setFittestIndividual(children[i]);
092 }
093
094 notifyReproduced(children, parents, oldPop, age, result, params);
095 newPop.addAll(children);
096 }
097
098 return newPop;
099 }
100
101 protected GAResult createResult() {
102 return new FittestIndividualResult();
103 }
104
105 protected boolean checkForBetterResult(GAResult oldResult, Population newPop, GAParameterSet params) {
106
107 FittestIndividualResult result = (FittestIndividualResult) oldResult;
108 Fitness best = result.getBestFitness();
109
110 final int size = newPop.getSize();
111 for (int i = 0; i < size; i++) {
112 Fitness f = newPop.getMember(i).getFitness();
113 if (f.isBetter(best)) {
114 best = f;
115 result.setFittestIndividual(newPop.getMember(i));
116 }
117 }
118
119 return (result.getBestFitness() != best);
120 }
121
122 protected Population createInitialPopulation(GAParameterSet params) {
123 Population pop = createEmptyPopulation(params);
124 while (pop.getSize() < params.getPopulationSize()) {
125 Individual ind;
126 ind = params.getIndividualsFactory().createRandomIndividual(params);
127 pop.add(ind);
128 }
129 return pop;
130 }
131
132 protected Population createEmptyPopulation(GAParameterSet params) {
133 Population pop = new SimpleCollectionOfIndividuals();
134 return pop;
135 }
136
137 protected boolean terminationConditionApplies(Population pop, int genNum,
138 GAResult result, GAParameterSet params) {
139 return genNum >= params.getMaxGenerationNumber();
140 }
141
142 protected Individual [] selectForReproduction(Population pop, int age, GAParameterSet params) {
143
144 int selCount = params.getReproductionAlgorithm().getRequiredNumberOfParents();
145 if (0 > selCount)
146 selCount = 2;
147
148 SelectionAlgorithm selector = params.getSelectionAlgorithm();
149 Individual [] selection = selector.select(pop, selCount, age, params);
150
151 return selection;
152 }
153
154 protected Individual [] haveSex(Individual [] parents, GAParameterSet params) {
155 ReproductionAlgorithm cosyPlace = params.getReproductionAlgorithm();
156 Individual [] oops = cosyPlace.reproduce(parents, params);
157 return oops;
158 }
159
160 protected void updateIndividualFitness(Individual indiv, Population pop,
161 int genNum, GAParameterSet params) {
162 FitnessEvaluationAlgorithm tester = params.getFitnessEvaluationAlgorithm();
163 Fitness fitness = tester.evaluateFitness(indiv, genNum, pop, params);
164 indiv.setFitness(fitness);
165 updateFitnessCalculated(indiv, pop, genNum, params);
166 }
167
168 public boolean addHook(SimpleGAHook hook) {
169 if (null == hook)
170 return false;
171 else if (null == this.hooks)
172 this.hooks = new ArrayList();
173 else if (this.hooks.contains(hook))
174 return false;
175 this.hooks.add(hook);
176 return true;
177 }
178
179 public boolean removeHook(SimpleGAHook hook) {
180 if (null == hook)
181 return false;
182 else if (null == this.hooks)
183 return false;
184 else if (!this.hooks.contains(hook))
185 return false;
186 this.hooks.remove(hook);
187 if (0 == this.hooks.size())
188 this.hooks = null;
189 return true;
190 }
191
192 protected void notifyInitialisationDone(Population pop, int age,
193 GAResult result, GAParameterSet params) {
194 if (!params.getUseMainAlgorithmHooks())
195 return;
196 if (null == hooks)
197 return;
198 for (Iterator hook = hooks.iterator(); hook.hasNext();
199 ((SimpleGAHook) hook.next()).initialisationDone(this, pop, age, result, params)
200 );
201 }
202
203 protected void notifyFoundNewResult(Population pop, int age,
204 GAResult result, GAParameterSet params) {
205 if (!params.getUseMainAlgorithmHooks())
206 return;
207 if (null == hooks)
208 return;
209 for (Iterator hook = hooks.iterator(); hook.hasNext();
210 ((SimpleGAHook) hook.next()).foundNewResult(this, pop, age, result, params)
211 );
212 }
213
214 protected void notifyGenerationChanged(Population pop, int age,
215 GAResult result, GAParameterSet params) {
216 if (!params.getUseMainAlgorithmHooks())
217 return;
218 if (null == hooks)
219 return;
220 for (Iterator hook = hooks.iterator(); hook.hasNext();
221 ((SimpleGAHook) hook.next()).generationChanged(this, pop, age, result, params)
222 );
223 }
224
225 protected void notifyTerminationConditionApplies(Population pop, int age,
226 GAResult result, GAParameterSet params) {
227 if (!params.getUseMainAlgorithmHooks())
228 return;
229 if (null == hooks)
230 return;
231 for (Iterator hook = hooks.iterator(); hook.hasNext();
232 ((SimpleGAHook) hook.next()).terminationConditionApplies(this, pop, age, result, params)
233 );
234 }
235
236 protected void notifySelectedForReproduction(Individual [] selectedParents, Population pop,
237 int age, GAResult result, GAParameterSet params) {
238 if (!params.getUseMainAlgorithmHooks())
239 return;
240 if (null == hooks)
241 return;
242 for (Iterator hook = hooks.iterator(); hook.hasNext();
243 ((SimpleGAHook) hook.next()).selectedForReproduction(this, selectedParents,
244 pop, age, result, params)
245 );
246 }
247
248 protected void notifyReproduced(Individual [] children, Individual [] parents, Population pop,
249 int age, GAResult result, GAParameterSet params) {
250 if (!params.getUseMainAlgorithmHooks())
251 return;
252 if (null == hooks)
253 return;
254 for (Iterator hook = hooks.iterator(); hook.hasNext();
255 ((SimpleGAHook) hook.next()).reproduced(this, children, parents,
256 pop, age, result, params)
257 );
258 }
259
260 protected void updateFitnessCalculated(Individual updated, Population pop,
261 int age, GAParameterSet params) {
262 if (!params.getUseMainAlgorithmHooks())
263 return;
264 if (null == hooks)
265 return;
266 for (Iterator hook = hooks.iterator(); hook.hasNext();
267 ((SimpleGAHook) hook.next()).fitnessCalculated(this, updated,
268 pop, age, params)
269 );
270 }
271 }