0

首先，我讨厌问这样一个含糊不清的问题，但我到此为止。我正在尝试为旅行商经典 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
4

1 回答 1

2

应用于（对称）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 中添加多样性保护，否则人口可能会很快崩溃到相同的解决方案。遗传局部搜索技术通常仅在它们有显着不同时才接受对种群的新解决方案。

于 2015-12-04T10:33:15.480 回答