001/**
002 *
003 */
004package org.biojavax.ga.functions;
005
006import java.util.Iterator;
007import java.util.Random;
008
009import org.biojava.bio.symbol.Alphabet;
010import org.biojava.bio.symbol.Edit;
011import org.biojava.bio.symbol.IllegalAlphabetException;
012import org.biojava.bio.symbol.PointLocation;
013import org.biojava.bio.symbol.SymbolList;
014import org.biojava.utils.ChangeVetoException;
015import org.biojavax.ga.functions.AbstractCrossOverFunction;
016import org.biojavax.ga.functions.GACrossResult;
017import org.biojavax.ga.functions.SimpleGACrossResult;
018
019/**
020 * This does a 2-point-crossover on two chromosomes keeping the Symbols in each
021 * chromosome constant. The method is commonly named OX - operator
022 *
023 * @author Susanne Merz
024 */
025public class OrderCrossover extends AbstractCrossOverFunction {
026
027        /**
028         * Sets the maximal number of crossover points to two and the crossover
029         * probability to 0.5 and initializes this object.
030         */
031        public OrderCrossover() {
032                this.setMaxCrossOvers(2);
033                double[] pro = {0.5};
034                this.setCrossOverProbs(pro);
035        }
036
037        /*
038         * (non-Javadoc)
039         *
040         * @see org.biojavax.ga.functions.CrossOverFunction#performCrossOver(org.biojava.bio.symbol.SymbolList,
041         *      org.biojava.bio.symbol.SymbolList)
042         */
043        public GACrossResult performCrossOver(SymbolList chromA, SymbolList chromB)
044            throws ChangeVetoException {
045                int[] crosslocations = this.generateCrossoverLocations(chromA.length());
046                // only do a chrossover if there are valid positions.
047                if (crosslocations[1] != 0.0) {
048                        // if we found only one crossover position, we assume the
049                        // second position to be the end of teh chromosome
050                        if (crosslocations[0] == 0.0) {
051                                crosslocations[0] = crosslocations[1];
052                                crosslocations[1] = chromA.length();
053                        }
054                        Alphabet alphA = chromA.getAlphabet();
055                        Alphabet alphB = chromB.getAlphabet();
056                        SymbolList snipA = chromA.subList(crosslocations[0], crosslocations[1]);
057                        SymbolList snipB = chromB.subList(crosslocations[0], crosslocations[1]);
058                        SymbolList snipAwoB = snipA.subList(1, snipA.length());
059                        SymbolList snipBwoA = snipB.subList(1, snipB.length());
060                        // remove all elements of snipA from snipBwoA and vice versa
061                        for (int i = 1; i <= snipB.length(); i++) {
062                                int j = 1;
063                                Iterator it = snipAwoB.iterator();
064                                boolean notfound = true;
065                                while (it.hasNext() && notfound) {
066
067                                        if (it.next().equals(snipB.symbolAt(i))) {
068                                                try {
069                                                        snipAwoB.edit(new Edit(j, 1, SymbolList.EMPTY_LIST));
070                                                } catch (Exception e) {
071                                                        e.printStackTrace();
072                                                }
073                                                break;
074                                        }
075                                        j++;
076                                }
077                                Iterator it2 = snipBwoA.iterator();
078                                j = 1;
079                                while (it2.hasNext()) {
080                                        if (it2.next().equals(snipA.symbolAt(i))) {
081                                                try {
082                                                        snipBwoA.edit(new Edit(j, 1, SymbolList.EMPTY_LIST));
083                                                        break;
084                                                } catch (Exception e) {
085                                                        e.printStackTrace();
086                                                }
087                                        }
088                                        j++;
089                                }
090                        }
091                        // remove all elements of snipA and snipB from both chromsomes
092                        int sniplength = (crosslocations[1] - crosslocations[0]) + 1;
093                        try {
094                                // remove snipA from chromB and snipB from chromB
095                                chromA.edit(new Edit(crosslocations[0], sniplength,
096                                    SymbolList.EMPTY_LIST));
097                                chromB.edit(new Edit(crosslocations[0], sniplength,
098                                    SymbolList.EMPTY_LIST));
099                                // remove elements of snipA from chromB
100                                Iterator it1 = snipA.iterator();
101                                while (it1.hasNext()) {
102                                        Object current = it1.next();
103                                        Iterator it2 = chromB.iterator();
104                                        Iterator it3 = chromA.iterator();
105                                        int position = 1;
106                                        while (it2.hasNext()) {
107                                                if (it2.next().equals(current)) {
108                                                        chromB.edit(new Edit(position, 1, SymbolList.EMPTY_LIST));
109                                                        break;
110                                                }
111                                                position++;
112                                        }
113                                }
114                                // remove elements of snipB from chromA
115                                it1 = snipB.iterator();
116                                while (it1.hasNext()) {
117                                        Object current = it1.next();
118                                        Iterator it2 = chromA.iterator();
119                                        Iterator it3 = chromB.iterator();
120                                        int position = 1;
121                                        boolean notfound = true;
122                                        while (it2.hasNext() && notfound) {
123                                                if (it2.next().equals(current)) {
124                                                        chromA.edit(new Edit(position, 1, SymbolList.EMPTY_LIST));
125                                                        notfound = false;
126                                                        break;
127                                                }
128                                                position++;
129                                        }
130                                }
131                        } catch (IllegalAlphabetException e) {
132                                System.out.println("Sorry, you used an illegal alphabet");
133                                e.printStackTrace();
134                        }
135                        // put parts together in the order snipXwoY-snipY-X
136                        try {
137                                chromA.edit(new Edit(1, 0, snipB));
138                                chromA.edit(new Edit(1, 0, snipAwoB));
139                                chromB.edit(new Edit(1, 0, snipA));
140                                chromB.edit(new Edit(1, 0, snipBwoA));
141                        } catch (IllegalAlphabetException e) {
142                                e.printStackTrace();
143                        }
144                        // if the chromosomes are not cycle-invariant we need to
145                        // adjust positions
146                        int newposition = 1;
147                        Iterator it = chromA.iterator();
148                        while (it.hasNext()) {
149                                if (it.next().equals(snipB.symbolAt(1))) {
150                                        // newposition++;
151                                        break;
152                                }
153                                newposition++;
154                        }
155                        int versatz = crosslocations[0] - newposition;
156
157                        if (versatz < 0) {
158                                versatz = Math.abs(versatz);
159                                // remove from front and add to end
160                                try {
161                                        SymbolList temp = chromA.subList(1, versatz);
162                                        chromA.edit(new Edit(1, versatz, SymbolList.EMPTY_LIST));
163                                        chromA.edit(new Edit(chromA.length() + 1, 0, temp));
164                                        temp = chromB.subList(1, versatz);
165                                        chromB.edit(new Edit(1, versatz, SymbolList.EMPTY_LIST));
166                                        chromB.edit(new Edit(chromB.length() + 1, 0, temp));
167
168                                } catch (IllegalAlphabetException e) {
169                                        e.printStackTrace();
170                                }
171                        }
172
173                        else if (versatz > 0) {
174                                // remove from end and add to front
175                                try {
176                                        versatz--;
177                                        int start = chromA.length() - versatz;
178                                        SymbolList temp = chromA.subList(start, chromA.length());
179                                        chromA.edit(new Edit(start, chromA.length() - (start - 1),
180                                            SymbolList.EMPTY_LIST));
181                                        chromA.edit(new Edit(1, 0, temp));
182                                        temp = chromB.subList(start, chromB.length());
183                                        chromB.edit(new Edit(start, chromB.length() - (start - 1),
184                                            SymbolList.EMPTY_LIST));
185                                        chromB.edit(new Edit(1, 0, temp));
186
187                                } catch (IllegalAlphabetException e) {
188                                        e.printStackTrace();
189                                }
190                        }
191
192                        PointLocation[] points = {new PointLocation(crosslocations[0]),
193                            new PointLocation(crosslocations[1])};
194                        GACrossResult result = new SimpleGACrossResult(points, new SymbolList[] {
195                            chromA, chromB});
196
197                        return result;
198                } else return null;
199        }
200
201        /**
202         * generate a pair of locations where the crossover should be made do this in
203         * two steps for retracabilities sake. the location array will always list the
204         * earlier position first.
205         *
206         * @param chromlength
207         *          the lenghth of the chromosomes, needed to decide if the
208         *          probabilityarray needs to be extended.
209         * @return an int[] containing two positions on the chomosome
210         */
211        private synchronized int[] generateCrossoverLocations(int chromlength) {
212                Random n = new Random();
213                int[] locations = new int[2];
214                // step 1 create an array containing a value for every position
215                // on the chromosome. The higher the number the more likely it
216                // will be choosen as crossoverposition.
217                double[] crosses = new double[chromlength];
218                int maxIndex = getCrossOverProbs().length - 1;
219
220                for (int i = 1; i <= chromlength; i++) {
221                        int index = Math.min(i - 1, maxIndex);
222                        double crossProb = getCrossOverProbs()[index] - n.nextDouble();
223                        if (crossProb >= 0) {
224                                crosses[i - 1] = crossProb;
225                        } else {
226                                crosses[i - 1] = 0;
227                        }
228                }
229
230                // step 2 find the two highest numbers and return their positions
231                double highest = 0;
232                double second = 0;
233                for (int j = 0; j < crosses.length; j++) {
234                        double current = crosses[j];
235                        if (current > second) {
236                                // allways put highest number in pos[1], second in pos[0]
237                                if (current > highest) {
238                                        locations[0] = locations[1];
239                                        second = highest;
240                                        locations[1] = j + 1;
241                                        highest = current;
242                                } else {
243                                        second = current;
244                                        locations[0] = j + 1;
245                                }
246
247                        }
248                }
249                // switch places so the lower number is in pos[0]
250                if (locations[0] > locations[1]) {
251                        int temp = locations[0];
252                        locations[0] = locations[1];
253                        locations[1] = temp;
254                }
255
256                return locations;
257        }
258
259}