GA Elitism values strange

[sirlink99]

Hello everyone!

I am writing a GA, and I am trying to implement elitism. My problem is an interesting one. I cannot release too much code because it is an ongoing assignment. I have asked the TA, and he is unable to find the solution as of this moment. The assignment deals with solving the TSP. The elite is always the best value in the population. This elite gets placed from the old generation into the new generation in order to keep track of the best result, and hopefully improve it. There are the steps that I do after I initialize a random population.

The GA loop:
1. replaces old population with generated new population
2. Sort the returned population
3. takes the best value from the new population and stores it if the fitness (length of the path) is lower than the current best.
4: loop

Creating the new population:
1. sort the old population
2. generate the new population in a different list
3. sort the new population
4. replace the worst in the new population with the best in the old population.
5. return the new population to my GA loop.

Of course, there are redundancies with the sorting, but only because of the error I am experiencing. This mysterious error is that if I print out the best from the population, and the best from all of the generations, they are not identical as they should be. Remember, the elite keeps track of the best value for all the generations. My only 2 assumptions at this point are that I am missing something terribly simple with my distance calculation, or that I am messing up with Java objects somehow.

The way my classes are set up is that my populations is made up of "Specimen"s. These Specimens hold "City"s. Each city contains a number, x and y co-ordinate.

This is my distance calculation:
in the Specimen: Does the loop of the cities summing up the distance (using long, but changing to floats doesn't make a difference)

public long getAccurateFitness(){
        long fitness = 0;
        for (int i = 0; i < chromo.length; i++){
            fitness += chromo[i].rootDistance(chromo[(i+1)%chromo.length]);
}
        return fitness;
    }

The city class has the rootDistance function

public long rootDistance (City c){
        return (long)Math.sqrt((Math.pow((x-c.getX()), 2) + Math.pow((y-c.getY()), 2)));
}

I sort my population using Arrays.sort(newPop, new SpecimenComparator()); with the comparator looking like

import java.util.Comparator;

public class SpecimenComparator implements Comparator<Specimen>{

    public int compare(Specimen o1, Specimen o2) {
        return (int)(o1.getAccurateFitness() - o2.getAccurateFitness());
    }   
}

Again, I tried multiplying by 10, 100 and 1000 for this distance to include decimal places in the sort. It did not make a difference.

Since I was worried about changing something from the old population, every time I do anything to any data in the old population I get a new instance of what was there to make sure I don't change it. But taking a new instance didn't seem to help either. Does anyone have any ideas what it could be? I know the code snippets are vague, but if you have any ideas please let me know. If you are curious about something that I didn't mention then please let me know, and I can elaborate.

Edit: I forgot to mention that the difference between the values isn't large. The maximum I saw was about 200. The seed that I am currently using generates two values with a difference of 11

Thank you for your help!

[JamesCherrill]

Without actual code one can only make wild guesses, for example:
When you copy the populations is that a shallow or a deep copy? Maybe its a shallow copy and subsequent changes to members are affecting both copies?

[sirlink99]

I know, but I don't want to provide too much code because like I said, the assignment is still ongoing.

I thought I was doing a deep copy on each individual using the

public Specimen getNewInstance(){
        return new Specimen (chromo);
    }

where chromo is the chromosome of that individual. While thinking about it, I was wondering what if it is because I don't get a copy of the city? But the cities don't change. Then I realized that it is because I don't deep copy the array of chromosomes too, so replacing the above code with

public Specimen getNewInstance(){
        return new Specimen (Arrays.copyOf(chromo, chromo.length));
    }

I think because I didn't deep copy my array, the mutations that I did to a new instance of the individual changed the old copy of the array in certai mulations, changing my answer.

So, the second code seems to fix the issue. Thank you for your help!