c - 为什么我的遗传算法不会收敛，或者至少不会变得更好一点？

Question

首先，我不想问这样一个含糊不清的问题，但我已经无计可施了。我正在尝试为旅行商经典 CS 问题制作遗传算法。

我已尝试很好地注释我的代码，以使每个步骤都清楚地表明我正在尝试做什么。

我有一个包含城市索引和 x,y 坐标的结构节点对象。我正在从文件中读取城市列表，并将结构节点的数组和它们的数量传递给我的函数。

如有任何疑问，欢迎提问。 gui 每大约 1000 次迭代更新一次，它肯定会发生变化，但似乎永远不会变得更好，即使我运行了很长时间的世代数也是如此!

此外，如果您感到困惑，我将距离作为 uint64_t 返回，以获得比 double 更好的准确性和可移植性，但在执行适应度函数时我将它们转换为 double 类型。 (这一切都有效，我已经验证过了)

关于为什么它不会变得更好，你能找出任何错误吗？

void GeneticAlgorithm(struct Node *cities, uint64_t *count)
{
    //1 - pick initial random permutations for the population size
    int populationSize =(*count)>10? ((*count)/5) : *count;
    fprintf(stderr, "Population Size: %d\n", populationSize);

    //population consists of populationSize elements (an element being a path)
    struct Node population[populationSize][*count];
    srand (time(NULL));
    //Get Initial Paths
    uint64_t i;
    //iterate over pop. size
    for(i=0; i<populationSize; i++){
        //fill out path for each population
        int j;
        for(j=0; j<*count; j++){
            int element = rand() % (int)(*count);     // 0-count
            while(hasBeenVisited(&cities[element]) == 0){
                element = rand() % (int)(*count);
            }
            memcpy ( &(population[i][j]), &(cities[element]), sizeof(struct Node) );
            setVisited(&cities[element]);

        }
        for(j=0;j<*count; j++){
            (&cities[j])->visited = 0;
        }

    }

    int j;



    //Now, we have our population of randomly selected paths

    struct Node children[populationSize][*count];
    int generation, crossover;

    uint64_t Distances[populationSize];
    uint64_t TotalDistance = 0;
    srand(time(NULL));


    //Iterate over each generation. Basic idea is to do fitness function, generate
    //probability for each, do selection and fill up children array until it has
    //the same populationSize elements as original population, perhaps do a mutation,
    //and replace population array.
    for(generation=0; generation < 5; generation++){



        /*  Get Distance of Each Path and Total Sum of Distances   */
        TotalDistance = 0;
        for(j=0; j<populationSize; j++){
            Distances[j] = 0;
            for(i=0; i<*count; i++){
                if(i==((*count)-1)){
                    Distances[j] += distance(&(population[j][0]), &(population[j][i]));
                }
                else{
                    Distances[j] += distance(&(population[j][i]), &(population[j][i+1]));
                }

            }
            TotalDistance += Distances[j];
        }



        /*  FITNESS FUNCTION    */

        //Evaluate each of the population according to the fitness function (distance through the path)
        double probability[*count];
        double sumProbabilities = 0.0;
        char tempDistanceString[32];
        trimUintDigits(&TotalDistance);
        uintcharf(tempDistanceString, TotalDistance);

        double dTotalDistance = strtod(tempDistanceString, NULL);

        for(i=0; i<populationSize; i++){
            char buf[32];

            //Distances are uint64_t, need to ensure 7 decimal place accuracy (trimuint does this)
            //and uintcharf converts to a decimal representation in a string
            trimUintDigits(&Distances[i]);
            uintcharf(buf, Distances[i]);
            double individualDistance = strtod(buf, NULL);

            probability[i] = sumProbabilities + (individualDistance / totalDistance);
            sumProbabilities += probability[i];
        }
        //set children to all 0 (will replace population)
        memset(&children, 0, sizeof(struct Node)*populationSize*(*count));
        double r;
        int numChildren = 0;

        //Iterate until number of children = current population size
        while(numChildren < populationSize){

            //0 <= r <=1
            r = ((double) rand() / (RAND_MAX));

            if(r>0.7){ //Doesn't always crossover!
                memcpy(&children[numChildren], &population[numChildren], sizeof(struct Node) * (*count));
                numChildren++;
                continue;
            }

            r = ((double) rand() / (RAND_MAX));
            r *= sumProbabilities;
            double nextProb = 0;

            //Pick the two parents for procreation, according to the roulette wheel probability

            int par1=-1, par2=-1;
            while(par1==-1){

                for(i=0; i<populationSize; i++){
                    if(i==populationSize-1){
                        nextProb=probability[0];
                    }
                    else{
                        nextProb = probability[i+1];
                    }

                    if((r > probability[i]) && (r < nextProb)){
                        par1 = i;
                        break;
                    }
                }
                r = ((double) rand() / (RAND_MAX));
                r *= sumProbabilities;
            }

            r = ((double) rand() / (RAND_MAX));
            r*= sumProbabilities;

            while(par2==-1){
                for(i=0; i<populationSize; i++){
                    if(i==populationSize-1){
                        nextProb=probability[0];
                    }
                    else{
                        nextProb = probability[i+1];
                    }

                    if((par1 !=i) && (r > probability[i]) && (r < nextProb)){
                        par2 = i;
                        break;
                    }
                }
                r = ((double) rand() / (RAND_MAX));
                r*= sumProbabilities;
            }



            //Pick my two parents
            struct Node *parentOne = &(population[par1]);
            struct Node *parentTwo = &(population[par2]);

            //Picking a random number of genes from parent two, add them to the child.
            //Then, iterate through parent 1 and add missing nodes to the child
            int GenesFromParentTwo = rand() % (*count-1) + 1;

            if(GenesFromParentTwo < 0 || GenesFromParentTwo > *count){
                GenesFromParentTwo = 1;
            }


            //Copy First 'GenesFromParentTwo' Nodes From Parent 2 to Child
            memcpy(&children[numChildren], &parentTwo[0], sizeof(struct Node)*GenesFromParentTwo);
            int indicesContained[GenesFromParentTwo];
            for(i=0; i<GenesFromParentTwo; i++){
                indicesContained[i] = (int)children[numChildren][i].index;
            }


            //Copy Remaining Missing nodes from Parent 1 to Child
            int numInsertions = 0;
            for(i=*count; i>0; i--){
                if(isContained(indicesContained, &parentOne[i], &GenesFromParentTwo)){
                    continue;
                }
                numInsertions++;
                memcpy(&children[numChildren][GenesFromParentTwo-1+numInsertions], &parentOne[i], sizeof(struct Node));
            }

            numChildren++;
        } //End crossover


        //Replace Population with Children
        for(i=0; i<populationSize; i++){
            memcpy(&population[i], &children[i], sizeof(struct Node) * (*count));
        }


        //Mutate?
        for(i=0; i<populationSize; i++){

            for(j=0; j<*count; j++){

                r = ((double) rand() / (RAND_MAX));
                r *= 100;
                //0 <= r <= 100
                if(r <= 0.001 ){
                    //Mutate!
                    if(j==*count-1){
                        struct Node temp;
                        memcpy(&temp, &population[i][j], sizeof(struct Node));
                        memcpy(&population[i][j], &population[i][0], sizeof(struct Node));
                        memcpy(&population[i][0],  &temp, sizeof(struct Node));
                    }
                    else{
                        struct Node temp;
                        memcpy(&temp, &population[i][j], sizeof(struct Node));
                        memcpy(&population[i][j], &population[i][j+1], sizeof(struct Node));
                        memcpy(&population[i][j+1],  &temp, sizeof(struct Node));
                    }
                }

            }

        }


        //After crossing over each generation, pick the best and send to GUI

        if(generation % 10000 == 0)
        {

            uint64_t shortestGenDistance = UINT64_MAX;
            int elShortest = -0;
            for (j = 0; j < populationSize; j++)
            {
                uint64_t tempDistance = 0;
                for (i = 0; i < *count; i++)
                {
                    if (i == *count - 1)
                    {
                        tempDistance += distance(&(population[j][0]), &(population[j][i]));
                    }
                    else
                    {
                        tempDistance += distance(&(population[j][i]), &(population[j][i + 1]));
                    }
                }
                if (tempDistance < shortestGenDistance)
                {
                    shortestGenDistance = tempDistance;
                    elShortest = j;
                }
            }


            char buffer[8192];
            push_node_array_to_json(buffer, &population[elShortest][0], count, generation + 1);
            push(buffer);
        }



    } //End Generations
} //End algorithm

Answer 1

应用于(对称)TSP 的遗传算法通常使用 EdgeRecombinationCrossover (ERX)、基于锦标赛的选择(而不是适应度比例选择)和 2-opt 突变(你似乎使用了相当具有破坏性的交换突变)工作得很好在 TSP 上)。对于 50 到 1000 个城市之间的问题实例，人口规模在 100 到 1000 之间，锦标赛组规模在 2 到 10 之间，你应该在 200-500 代内得到合理的结果。我觉得你的变异概率太低了，我会用1-5%。

求解 TSP 的遗传算法可能如下所示(C# 伪代码):

const uint seed = 0;
const int popSize = 100;
const int generations = 500;
const double mutationRate = 0.05;

var tsp = new TravelingSalesmanProblem(/*...*/);
var random = new Random(seed);
var population = new int[popSize];
var qualities = new double[popSize];
var nextGen = new int[popSize];
var nextQual = new double[popSize];

for (int i = 0; i < popSize; i++) {
  population[i] = Enumerable.Range(0, tsp.Cities).Shuffle().ToArray();
  qualities[i] = tsp.Evaluate(population[i]);
}
var bestQuality = qualities.Min();
var bestQualityGeneration = 0;

for (int g = 0; g < generations; g++) {  
  var parents = population.SampleTournament(random, 2 * popSize, qualities, groupSize: 3).ToArray();
  for (int i = 0; i < popSize; i++) {
    nextGen[i] = EdgeRecombinationCrossover.Apply(random, parents[i * 2], parents[i * 2 + 1]);
    if (random.NextDouble() < mutationRate) TwoOptManipulator.Apply(random, nextGen[i]);
    nextQual[i] = tsp.Evaluate(nextGen[i]);
    if (nextQual[i] < bestQuality) {
      bestQuality = nextQual[i];
      bestQualityGeneration = g;
    }
  }
  Array.Copy(nextGen, population, popSize);
  Array.Copy(nextQual, qualities, popSize);
}

但一般来说，GA 并不是解决 TSP 的首选算法。 TSP 通常可以通过使用 2-opt 移动的局部搜索很好地解决。如果您通常使用使用 k-opt 移动的可变邻居下降，则可以进一步提高质量。 Lin-kerninghan 是一个非常先进的解决 TSP 的软件，它们确实使用遗传算法作为元级优化器来交叉和变异使用 k-opt 局部搜索获得的局部最优值。应用于局部最优的 GA 比应用于整个解决方案空间更有效。但是，您需要确保将多样性保护添加到 GA 中，否则人口可能会迅速崩溃到相同的解决方案。遗传局部搜索技术通常仅在它们有很大不同时才接受对种群的新解决方案。