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    }