Genetic Algorithm - Java Crossover

Question

With my GA's crossover method, I keep getting an ArrayOutOfBounds Exception while concatenating the mother's second half to the father's first half. The ArrayList's are all the same size. Why does my mother keep trying to access the 10th element in my list of objects? MyPair is an object with a random direction and random number of steps.

We are currently learning this topic in my A.I. class, so I'm not an expert in GA's yet. Any additional commentary on my crossover algorithm is welcomed.

public static class Chromosome{

        public ArrayList<MyPair> pairs;
        private double x, y;
        public double cost;

        public Chromosome(){
            this.pairs = new ArrayList<MyPair>();
            this.x = 100.0; this.y = 100.0;

//          not sure if I should do this or not
            for(int numPairs = 0; numPairs < 10; numPairs++)
                this.addToChromosome();
        }

        public void addToChromosome(){
            MyPair myPair = new MyPair();
            this.pairs.add(myPair);
        }

        public ArrayList<MyPair> getPairsList(){
            return this.pairs;
        }

        public Chromosome crossOver(Chromosome father, Chromosome mother){

            Chromosome replacement = new Chromosome();
            int pos1 = r.nextInt(father.getPairsList().size());

            while(pos1 >= 10)
                pos1 = r.nextInt(father.getPairsList().size());

            for(int i = 0; i < pos1; i++){
                MyPair tempPair = father.getPairsList().get(i);
                replacement.getPairsList().set(i, tempPair);
            }           

            for(int i = pos1; i < mother.getPairsList().size() - 1; i++){
                MyPair tempPair = mother.getPairsList().get(i);

                // ArrayList keeps trying to set out of bounds here
                replacement.getPairsList().set(i, tempPair);
            }

            return replacement;
        }

Answer 1

The problem appears to be that you are constructing chromosomes including replacement to have 10 pairs, and then you are setting the element in position i, when i may be 10 or greater.

This has multiple effects you might not have intended. If you splice together a mother and father so that the mother has fewer than 10 pairs, you end up with 10 pairs anyway, with the last ones being just new pairs. If the mother has more than 10 pairs, you are trying to set elements of the arraylist that don't exist, hence you are getting an exception. Another thing you might not have encountered yet is that you haven't copied the information in the pair, you copied the reference to the pair. This means if you give the mother a mutation later by changing the information in the pair rather than replacing a pair, it will affect the child and the child's descendants, which probably is not what you intended.

Instead, start the chromosome with an empty list of pairs, and then add copies of the pairs from the father, and then add copies of pairs from the mother.

Untested code:

public Chromosome crossOver(Chromosome father, Chromosome mother){

    Chromosome replacement = new Chromosome();
    replacement.getPairsList().clear(); // get rid of the original 10 pairs

    int pos1 = r.nextInt(father.getPairsList().size());

    while(pos1 >= 10)
        pos1 = r.nextInt(father.getPairsList().size());

        for(int i = 0; i < pos1; i++){
            MyPair tempPair = father.getPairsList().get(i);
            replacement.getPairsList().add(tempPair.makeCopy()); // appended copy instead of setting ith
        }           

        for(int i = pos1; i < mother.getPairsList().size() - 1; i++){
            MyPair tempPair = mother.getPairsList().get(i);

            // ArrayList keeps trying to set out of bounds here
            replacement.getPairsList().add(tempPair.makeCopy()); // append copy instead of setting ith
        }

        return replacement;
    }

You have to make a makeCopy method in your Pair class that returns a Pair with the same information. There are other ways to do this.