Finding the least fit members in a genetic algorithm effeciently

I've implemented a genetic algorithm in java to solve the traveling salesman problem for a class of mine. It seems to work pretty well but is slow. I represent an individual which I call an instance of "Tour" as an ArrayList of Integers that represents the order to travel. (ie [1,5,4,3,2,0] would mean go to city 1,5,4,3,2,0,1 in order. Each generation does the following steps...

1. Sorts the population in increasing order (most fit members have lowest score)
2. Picks 20% of the population to breed based off of Roulette wheel selection so that the higher fitness members will have an increased chance of breeding
3. Use that 20% to make 10% of children using a greedy crossover
4. Randomly greedy mutate 5% of children
5. Remove lowest 10% of population and replace with children (First 90% of array would still be sorted afterwords)
6. Repeat 50,000 times

I suspect that the sorting part is the bottleneck since I've read that Collections.sort method uses a MergeSort that copies the entire array. In my case this is probably very ineffecient since it would be copying an array or Tours (which are themselves arrays) when all I want is to sort based off of fitness. Is there a better way of getting the lowest 10% of an array in Java besides sorting? Or maybe an in-place sort? Thanks for any suggestions!

package assignment3;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class Tsp {

private static int MAX_GENERATIONS = 50000;
private static int MUTATION_CHANCE = 5;

private Cities cityList;
private Population population = new Population();

public Tsp(Cities cityList) {
this.cityList = cityList;
this.population.createRandomPopulation(cityList);
}

public void clearTours() {
this.population.createRandomPopulation(cityList);
}

public Tour getBestTour() {
Collections.sort(this.population);
return this.population.get(0);
}

public void start() {
for (int generation = 0; generation < MAX_GENERATIONS; generation++) {
    Collections.sort(this.population);
    evolve();

}
}

private void evolve() {
// Sum all the fitnesses
// Update the breeding chance for each tour
// create a breeding array of ints that is 20% size of the population to
// be used to determine how to make the 10% children
// if array is odd add an index
// While the array size is too small
// loop through the population
// if array correct size exit loop
// compare random number with tour breeding chance
// make sure tour isn't in breeding array
// if pass random and not in breeding array
// add to breeding array
// end while

// loop through breeding array
// breed one parent with next
// store child in temp array

// For each child if randomly selected perform mutation

// remove 10% of worst children from population
// Add new children to population



ArrayList<Integer> breedingArray = getBreedingArray();
Population children = new Po开发者_如何学运维pulation();
for (int i = 0; i < breedingArray.size(); i += 2) {
    Tour parent1 = population.get(i);
    Tour parent2 = population.get(i + 1);
    children.add(parent1.performCrossover(cityList, parent2));
}

for (Tour t : children) {
    Random r = new Random();
    if (MUTATION_CHANCE >= r.nextInt(100)) {
    t.performGreedyMutation(cityList);
    }
}

int start = (population.size() - 1) - children.size();
int endIndex = population.size() - 1;

population.subList(start, endIndex).clear();
population.addAll(children);
}

private ArrayList<Integer> getBreedingArray( ) {
updateBreedingChance();

int breedingArraySize = (int) (this.population.size() * 0.2);
if (breedingArraySize % 2 != 0) {
    breedingArraySize += 1;
}

Random r = new Random();
ArrayList<Integer> breedingArray = new ArrayList<Integer>();
while (breedingArray.size() != breedingArraySize) {
    for (int i = 0; i < this.population.size(); i++) {
    if (breedingArray.size() == breedingArraySize) {
        break;
    }
    Tour check = this.population.get(i);
    boolean passesRandomSelection = r.nextDouble() < check.breadingChance;
    boolean notAlreadySelected = !breedingArray.contains(i);

    if (passesRandomSelection && notAlreadySelected) {
        breedingArray.add(i);
    }

    }
}
return breedingArray;
}

private void updateBreedingChance() {
double totalFitness = 0;
for (Tour t : this.population) {
    if (t.fitness == 0) {
    throw new RuntimeException("Fitness cannot be zero");
    }
    totalFitness += t.fitness;
}

double totalInverseFitness = 0;
for (Tour t : this.population) {
    totalInverseFitness += totalFitness / t.fitness;
}

for (Tour t : this.population) {
    t.breadingChance = (totalFitness / t.fitness) / totalInverseFitness;
}

}

}

---

If you 'suspect' that something is the problem, then your first action must be to find out whether it is or not. Profile the code. Then you'll know where the slow bits are. You can do this with a profiling tool, or just by throwing calls to System.nanoTime() in at key points and keeping some totals. Do this before doing any optimisation!

Now, an interesting thing about the array you are sorting is that it is normally 'mostly sorted'. The first 90% of it is the survivors from the previous round, who are sorted. You can use this to your advantage by using an adaptive sort, which does less work on such mostly-sorted arrays. There are several known adaptive sorts, but a good general-purpose one is Timsort. This will actually become the standard sort in Java 7 - the footnotes to the Wikipedia article about it include a link to the code in OpenJDK that will be used, which you can simply steal.

Even better than applying an adaptive sort would be to sort the new children first (using an adaptive sort, as you are breeding the fittest parents first, and so would expect to have, on average, the fittest children appear first), then to merge them into the already-sorted list of parents. You can merge them straightforwardly in O(n) time by walking the parent and child arrays in parallel and inserting children where needed. You could look at using a LinkedList here, as you might otherwise spend a lot of time in System.arrayCopy().

Also, in getBreedingArray(), you're saying breedingArray.contains(i) - for an array, that's an O(n) operation. You should probably use a LinkedHashSet instead of an array here. Scratch that - use a BitSet.

---

It might be faster to do a partial sort in step (5). Simple algorithm: make the population a heap, then pop off this heap .1 * n times. (This is partial heapsort; better algorithms are available in the literature, including one called "quickselsort".)