001package org.biojavax.ga.functions;
002
003import java.util.Iterator;
004import java.util.LinkedList;
005import java.util.Random;
006
007import org.biojava.bio.BioError;
008import org.biojava.utils.ChangeVetoException;
009import org.biojavax.ga.GeneticAlgorithm;
010import org.biojavax.ga.Organism;
011import org.biojavax.ga.Population;
012import org.biojavax.ga.exception.IllegalOrganismException;
013import org.biojavax.ga.functions.SelectionFunction;
014import org.biojavax.ga.impl.SimplePopulation;
015
016/**
017 * Tournament Selection chooses the best organisms from n random subsets of a
018 * given population. Currently it assumes a maximization problem. Perhaps this
019 * could be selected depending on the Genetic Algorithm utilized.
020 *
021 * @author Susanne Merz
022 */
023
024public class TournamentSelection implements SelectionFunction {
025
026        private int     selpressure;
027
028        /**
029         * Default constructor: sets the selection pressure to the value of 10.
030         */
031        public TournamentSelection() {
032                this.setSelectionPressure(10);
033        };
034
035        /**
036         * sets the parameter controlling selection pressure
037         *
038         * @param numberOfIndividuals
039         *          the number of Individuals the best is selected from, ranges from 1
040         *          (random selection) to the size of the population (elitism)
041         */
042        public void setSelectionPressure(int numberOfIndividuals) {
043                selpressure = numberOfIndividuals;
044        }
045
046        /**
047         * Standard call to select organisms, will select a number of Organisms
048         * corresponding to 75 % of the population.
049         *
050         * @see org.biojavax.ga.functions.SelectionFunction#select(org.biojavax.ga.Population, org.biojavax.ga.GeneticAlgorithm)
051         */
052        public Population select(Population pop, GeneticAlgorithm genAlg)
053            throws ChangeVetoException {
054                return selectNIndividuals(pop, genAlg, pop.size());
055
056        }
057
058        /**
059         * This method selects n Organism from the population it is given, using the
060         * tournament selection method
061         *
062         * @param pop
063         *          the population to select from
064         * @param ga
065         *          the <code>GeneticAlgorithm</code> this selection belongs to
066         * @param n
067         *          number of individuals to be selected.
068         * @return nextgen a <code>Population</code> containing the selected
069         *         Organisms
070         */
071        public Population selectNIndividuals(Population pop, GeneticAlgorithm ga,
072            int n) {
073
074                SimplePopulation nextgen = new SimplePopulation();
075                if (selpressure <= 0) {
076                        System.out.println("Sorry can't select with a selection pressure <= 0");
077                        return null;
078                }
079                int q = selpressure;
080
081                Random r = new Random();
082                // choose n individuals
083                for (int i = 0; i < n; i++) {
084                        // need to check that the size of the set we want
085                        // to choose from does not exceed the populations size
086                        if (q > pop.size()) {
087                                q = pop.size();
088                        }
089                        // Maximization Problem
090                        double bestvalue = Double.MIN_VALUE;
091                        Organism best = null;
092                        // create a List of Organisms, simulating a subpopulation of size q
093                        LinkedList<Organism> subpopulation = new LinkedList<Organism>();
094                        while (subpopulation.size() < q) {
095                                Iterator<Organism> it = pop.organisms();
096                                int pos = r.nextInt(pop.size());
097                                Organism current = it.next();
098                                while (pos > 0) {
099                                        current = it.next();
100                                        pos--;
101                                }
102                                // if the subpopulation already contains the choosen
103                                // element, we pick the next that isn't contained
104                                while (subpopulation.contains(current)) {
105                                        // run in circles ;)
106                                        if (!it.hasNext()) {
107                                                it = pop.organisms();
108                                        }
109                                        current = it.next();
110                                }
111                                // while we already have a handle on the organism
112                                // we want save which one is the best so far in the
113                                // subpopulation
114                                double value[] = current.getFitness();
115                                if ((value[0] >= bestvalue)) {
116                                        best = current;
117                                        bestvalue = value[0];
118                                }
119
120                                subpopulation.add(current);
121
122                        }
123
124                        // finished creating subpopulation, add best organism
125                        // from the subpopulation to the next generation
126
127                        try {
128                                if (best != null) {
129                                        String namesprefix = best.getName().split(":")[0];
130                                        Organism o = best.replicate(namesprefix + ":" + i);
131                                        nextgen.addOrganism(o);
132                                        // pop.removeOrganism(best);
133                                }
134                        } catch (IllegalOrganismException e) {
135                                e.printStackTrace();
136                        }
137                }
138                pop.removeAllOrganisms();
139                for (Iterator it = nextgen.organisms(); it.hasNext();) {
140                        try {
141                                pop.addOrganism((Organism) it.next());
142                        } catch (ChangeVetoException e) {
143
144                                e.printStackTrace();
145                        } catch (IllegalOrganismException ex) {
146                                throw new BioError("A previously legal organism is now illegal??", ex);
147                        }
148
149                }
150                pop = nextgen;
151                return nextgen;
152        }
153
154}