001package org.biojavax.ga.functions;
002
003import java.util.Random;
004
005import org.biojava.bio.symbol.Edit;
006import org.biojava.bio.symbol.IllegalAlphabetException;
007import org.biojava.bio.symbol.IllegalSymbolException;
008import org.biojava.bio.symbol.SymbolList;
009import org.biojava.utils.ChangeVetoException;
010import org.biojavax.ga.functions.AbstractMutationFunction;
011
012/**
013 * This class does a sort of mutation by exchanging two positions on the
014 * chromosome. Thus it can be used for implementations where a change of the
015 * amount of one symbol is undesired, e.g. some TSP implementations
016 *
017 * @author Susanne Merz
018 */
019public class SwapMutationFunction extends AbstractMutationFunction {
020
021        /**
022         * Sets the mutation probabilities to the designated values.
023         *
024         * @param probabilities
025         *          An array, which contains the mutation probabilities.
026         */
027        public SwapMutationFunction(double[] probabilities) {
028                this.setMutationProbs(probabilities);
029                // as we don't do a random mutation, but rather a swapping we don't need a
030                // distribution
031                this.setMutationSpectrum(null);
032        }
033
034        /*
035         * (non-Javadoc)
036         *
037         * @see org.biojavax.ga.functions.MutationFunction#mutate(org.biojava.bio.symbol.SymbolList)
038         */
039        public SymbolList mutate(SymbolList seq) throws IllegalAlphabetException,
040            ChangeVetoException, IllegalSymbolException {
041                int[] pos = this.generateMutationPositions(seq.length());
042                if (pos[0] == pos[1] || pos[0] == 0.0) {
043                        return seq;
044                }
045                Edit ed1 = new Edit(pos[0], seq.getAlphabet(), seq.symbolAt(pos[1]));
046                Edit ed2 = new Edit(pos[1], seq.getAlphabet(), seq.symbolAt(pos[0]));
047                seq.edit(ed1);
048                seq.edit(ed2);
049                return seq;
050        }
051
052        /**
053         * generate an array of two positions on the chromosome that get the highest
054         * values in a random choosing relative to their mutationProbability
055         *
056         * @param seqLength
057         *          the legth of the sequence used
058         * @return an int[] of two positions on the sequence used.
059         */
060        private int[] generateMutationPositions(int seqLength) {
061                Random n = new Random();
062                int[] positions = new int[2];
063                // step 1: create an array containing a value for every position
064                // on the chromosome. The higher the number the more likely it
065                // will be choosen as position for a mutation.
066                double[] tempprobs = new double[seqLength];
067                int maxIndex = getMutationProbs().length - 1;
068
069                for (int i = 1; i <= seqLength; i++) {
070                        int index = Math.min(i - 1, maxIndex);
071                        double mutProb = getMutationProbs()[index] - n.nextDouble();
072                        if (mutProb >= 0) {
073                                tempprobs[i - 1] = mutProb;
074                        } else {
075                                tempprobs[i - 1] = 0;
076                        }
077                }
078
079                // step 2 find the two highest numbers and return their positions
080                double highest = 0;
081                double second = 0;
082                for (int j = 0; j < tempprobs.length; j++) {
083                        double current = tempprobs[j];
084                        if (current > second) {
085                                // allways put highest number in pos[1], second in pos[0]
086                                if (current > highest) {
087                                        positions[0] = positions[1];
088                                        second = highest;
089                                        positions[1] = j + 1;
090                                        highest = current;
091                                } else {
092                                        second = current;
093                                        positions[0] = j + 1;
094                                }
095
096                        }
097                }
098                // switch places so the lower number is in pos[0]
099                if (positions[0] > positions[1]) {
100                        int temp = positions[0];
101                        positions[0] = positions[1];
102                        positions[1] = temp;
103                }
104
105                return positions;
106
107        }
108
109}