Нахождение наименее подходящих членов в генетическом алгоритме эффективно

Question

Я реализовал генетический алгоритм в Java, чтобы решить задачу коммивояжера для моего класса. Кажется, работает довольно хорошо, но медленно. Я представляю человека, которого я называю экземпляром "Tour", как ArrayList of Integers, который представляет заказ на путешествие. (т. е. [1,5,4,3,2,0] означало бы перейти в город 1,5,4,3,2,0,1 по порядку. Каждое поколение выполняет следующие шаги ...

1. Сортировка населения по возрастанию (большинство подходящих членов имеют наименьшее количество баллов)
2. Выбирает 20% населения для размножения на основе выбора колеса рулетки, так что члены с более высокой физической подготовкой будут иметь больше шансов на размножение
3. Используйте эти 20%, чтобы 10% детей использовали жадный кроссовер
4. Случайно жадные мутации 5% детей
5. Удалить 10% населения и заменить его детьми (первые 90% массива все равно будут отсортированы после слов)
6. Повторите 50000 раз

Я подозреваю, что сортировочная часть является узким местом, так как я прочитал, что метод Collections.sort использует MergeSort, который копирует весь массив. В моем случае это, вероятно, очень неэффективно, так как это будет копирование массива или туров (которые сами являются массивами), когда все, что я хочу, - это сортировка на основе пригодности. Есть ли лучший способ получить самые низкие 10% массива в Java, кроме сортировки? Или, может быть, сортировка на месте? Спасибо за любые предложения!

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 Population();
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;
}

}

}

Answer 1

Если вы «подозреваете», что что-то является проблемой, то ваше первое действие должно состоять в том, чтобы выяснить, так ли это или нет.Профилируйте код.Тогда вы будете знать, где медленные биты.Вы можете сделать это с помощью инструмента профилирования или просто бросив вызовы System.nanoTime () в ключевые моменты и сохранив некоторые итоги.Сделайте это прежде, чем выполнять какую-либо оптимизацию!

Теперь, интересная вещь о массиве, который вы сортируете, в том, что он обычно «в основном отсортирован».Первые 90% из них - это выжившие из предыдущего раунда, которые отсортированы.Вы можете использовать это в своих интересах, используя адаптивную сортировку , которая меньше работает с такими в основном отсортированными массивами.Существует несколько известных адаптивных сортов, но хорошим универсальным является Timsort .Это на самом деле станет стандартной сортировкой в ​​Java 7 - сноски к статье в Википедии об этом содержат ссылку на код в OpenJDK, который будет использоваться, который вы можете просто украсть.

Даже лучше, чем применять адаптивныйСортировка состояла бы в том, чтобы сначала отсортировать новых детей (используя адаптивную сортировку, так как вы сначала выводите наиболее подходящих родителей и, следовательно, ожидаете, что сначала появятся наиболее подходящие дети), а затем объединить их в уже отсортированные.список родителей.Вы можете объединить их сразу за O (n), пройдя параллельно родительский и дочерний массивы и вставив дочерние массивы, где это необходимо.Вы можете посмотреть на использование LinkedList здесь, так как в противном случае вы могли бы потратить много времени в System.arrayCopy ().

Кроме того, в getBreedingArray () вы говорите breedingArray.contains(i) - для массива,это операция O (n).Вы, вероятно, должны использовать LinkedHashSet вместо массива здесь.Поцарапайте это - используйте BitSet.

Answer 2

На шаге (5) может быть быстрее выполнить частичную сортировку. Простой алгоритм: сделать популяцию кучей , а затем вытолкнуть эту кучу .1 * n раз. (Это частичный heapsort ; более качественные алгоритмы доступны в литературе , включая алгоритм под названием " quickselsort ".)