我已经在Java中实现了遗传算法,以解决一类我的旅行推销员问题.它似乎工作得很好,但速度很慢.我代表一个人,我称其为“旅行”的实例为表示旅行顺序的整数数组列表. (即[1,5,4,3,2,0]表示依次前往城市1,5,4,3,2,0,1.每一代人都执行以下步骤…

>按升序对总体进行排序(最适合的成员得分最低)
>根据轮盘赌轮的选择,选择20％的人口进行育种,以便更高健身的成员有更多的繁殖机会
>用那20％的人使用贪婪的交叉来使10％的孩子
>贪婪的儿童随机变异了5％
>删除人口中最低的10％,并替换为子项(数组的前90％仍会以后缀排序)
>重复50,000次

我怀疑排序部分是瓶颈,因为我已经阅读到Collections.sort方法使用了MergeSort来复制整个数组.在我的情况下,这可能效率很低,因为当我想要的只是根据适应性排序时,它将复制一个数组或Tours(本身就是数组).除了排序之外,还有没有更好的方法来获取Java中数组的最低10％？还是就地排序？感谢您的任何建议！

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;
}

}

}

解决方法:

如果您“怀疑”某事是问题,那么您的第一个行动必须是找出是否存在问题.分析代码.然后,您将知道慢速比特在哪里.您可以使用概要分析工具来执行此操作,也可以仅在关键点处对System.nanoTime()进行调用并保留总计.在进行任何优化之前,请先执行此操作！

现在,有关您要排序的数组的一件有趣的事情是它通常是“大部分已排序”的.其中的前90％是来自前一轮的幸存者,他们进行了排序.您可以通过使用adaptive sort来发挥其优势,它在此类大多数排序的阵列上的工作量较少.有几种已知的自适应排序,但是一个很好的通用排序是Timsort.它实际上将成为Java 7中的标准排序-Wikipedia文章的脚注包括将要使用的OpenJDK中的代码的链接.你可以简单地偷.

比应用适应性排序更好的方法是先对新子进行排序(使用适应性排序,因为您首先繁殖最适合的父母,因此平均而言,期望最适合的孩子首先出现),然后合并将他们纳入已经排序的父母名单.您可以通过并行遍历父数组和子数组并在需要的地方插入子元素,从而在O(n)时间内直接合并它们.您可以在此处使用LinkedList进行查看,否则您可能会在System.arrayCopy()中花费大量时间.

另外,在getBreedingArray()中,您说的是breedingArray.contains(i)-对于数组,这是O(n)操作.您可能应该在这里使用LinkedHashSet而不是数组.从头开始-使用BitSet.