遗传算法求解商旅问题(TSP）代码实现详细注释(c++)

1、问题介绍及算法原理

https://blog.csdn.net/greedystar/article/details/80343841

2、所用数据

北京 116.46 39.92
天津 117.2 39.13
上海 121.48 31.22
重庆 106.54 29.59
拉萨 91.11 29.97
乌鲁木齐 87.68 43.77
银川 106.27 38.47
呼和浩特 111.65 40.82
南宁 108.33 22.84
哈尔滨 126.63 45.75
长春 125.35 43.88
沈阳 123.38 41.8
石家庄 114.48 38.03
太原 112.53 37.87
西宁 101.74 36.56
济南 117 36.65
郑州 113.6 34.76
南京 118.78 32.04
合肥 117.27 31.86
杭州 120.19 30.26
福州 119.3 26.08
南昌 115.89 28.68
长沙 113 28.21
武汉 114.31 30.52
广州 113.23 23.16
台北 121.5 25.05
海口 110.35 20.02
兰州 103.73 36.03
西安 108.95 34.27
成都 104.06 30.67
贵阳 106.71 26.57
昆明 102.73 25.04
香港 114.1 22.2
澳门 113.33 22.13

3、代码实现

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const double FITCHANGE = 500;   //适应度常数

class GeneticAlgorithm {
public:
    struct parameters {
        int populationSize = 1000;  //种群大小
        int maxGeneration = 200;    //最大迭代次数
        double mutationRate = 0.05; //变异概率
        double crossoverRate = 0.4; //交叉概率
        int tournamentSize = 200;   //选择种群大小
        float crossPercent = 0.2;   //交叉百分比
    } param;

    struct individual {
        double fitness;             //适应度
        double culmulateProbability;//累积概率
        vector<int> path;           //路径
    };

    vector<individual> group;       //种群
    vector<individual> crossGroup;  //交叉种群

    int length; //路径长度
    vector<vector<float>> points;
    
    GeneticAlgorithm(vector<vector<float>> &points){
        this->points = points;
        this->length = points.size();
        init();

        for (size_t i = 0; i < param.maxGeneration+1; i++)
        {
            updateGroupFitness();   //更新种群适应度
            calculatePropers();     //计算累积概率   用于轮盘赌
            selectCrossGroup();     //选择交叉种群    轮盘赌
            crossover();            //交叉  顺序交叉
            mutation();             //变异
            selectGroup();          //选择下一代种群
            if(i%20 == 0)
                cout<<"第"<<i<<"代的适应度："<<getResult()<<endl;
        }
        // showGroup();
    }

    void init(){   //初始化种群 随机初始路径
        vector<int> tmp;
        individual tmpIn{0,0,tmp};
        for (size_t i = 1; i <= length; i++)//1-n的数组
            tmp.push_back(i);
        for(int i = 0; i < param.populationSize; i++){
            random_shuffle(tmp.begin()+1,tmp.end());//随机排列
            tmpIn.path = tmp;
            group.emplace_back(tmpIn);
        }
        srand(time(NULL));
    }

    void showGroup(){   //打印种群  用于测试
        int size = group.size();
        for (size_t j = 0; j < size; j++){
            cout << "fit:" << group[j].fitness << " prop:"<< group[j].culmulateProbability << " path:";
            for (size_t i = 0; i < length; i++)
                cout<<group[j].path[i]<<" ";
            cout<<endl;
        }
        cout<<"-------------------------------------"<<endl;
        for (size_t i = 0; i < crossGroup.size(); i++)
        {
            cout << "fit:" << crossGroup[i].fitness << " prop:"<< crossGroup[i].culmulateProbability << " path:";
            for (size_t j = 0; j < length; j++)
                cout<<crossGroup[i].path[j]<<" ";
            cout<<endl;
        }
        cout<<"-------------------------------------"<<endl;
    }

    void updateGroupFitness(){  //更新整个种群的适应度
        for (size_t i = 0; i < param.populationSize; i++)
            calculateFitness(group[i]);
    }

    void calculateFitness(individual &ind){    //计算适应度
        float res = 0;
        for (size_t i = 0; i < length-1; i++)
            res += getDistance(ind.path[i], ind.path[i+1]);
        res += getDistance(ind.path[0],ind.path[length-1]);
        ind.fitness = FITCHANGE/res;
    }

    float getDistance(int p1, int p2){  //计算欧式距离
        float disX = points[p2-1][0] - points[p1-1][0];
        float disY = points[p2-1][1] - points[p1-1][1];
        return pow((disX*disX+disY*disY),0.5);
    }

    void calculatePropers(){  //计算累积概率
        group[0].culmulateProbability = group[0].fitness;
        for (size_t i = 1; i < param.populationSize; i++)
            group[i].culmulateProbability = group[i-1].culmulateProbability + group[i].fitness;
        for (size_t i = 0; i < param.populationSize; i++)
            group[i].culmulateProbability /= group[param.populationSize-1].culmulateProbability;
    }

    void selectCrossGroup(){  //选择交叉种群
        for (size_t i = 0; i < param.crossoverRate*param.populationSize; i++){
            double r = (double)rand()/RAND_MAX;
            if(r < group[0].culmulateProbability){
                crossGroup.emplace_back(group[0]);
                continue;
            }
            for (size_t j = 1; j < param.populationSize; j++){
                if (r >= group[j-1].culmulateProbability && r < group[j].culmulateProbability){
                    crossGroup.emplace_back(group[j]);
                    break;
                }
            }
        }
    }

    void crossover(){  //交叉   核心代码
        vector<bool> isCrossed(param.populationSize,false); //记录是否交叉过
        int crossNum = length*param.crossPercent;//交叉个数
        for (size_t i = 0; i < crossGroup.size()-2; i+=2){
            int r = rand()%(length - crossNum - 1) + 1; //交叉起点
            for (size_t j = r; j < r + crossNum; j++)
                isCrossed[crossGroup[i].path[j]] = true;    //记录交叉过的片段
            int p = 0; //记录交叉点
            for (size_t j = 0; j < length; j++){        //交叉替换到Gi
                if(!isCrossed[crossGroup[i+1].path[j]]){
                    if(p < r)  
                        crossGroup[i].path[p] = crossGroup[i+1].path[j];
                    else
                        crossGroup[i].path[p+crossNum] = crossGroup[i+1].path[j];
                    p++;
                }
            }
            isCrossed.assign(length,false); //重置
            // calculateFitness(crossGroup[i]);//计算适应度
            group.emplace_back(crossGroup[i]);//添加到种群
        }
    }

    void mutation(){  //变异
        for (size_t i = 1; i < group.size(); i++){
            if(rand()%100 < param.mutationRate*100){
                int r1 = rand()%length;
                int r2 = rand()%length;
                int tmp = group[i].path[r1];
                group[i].path[r1] = group[i].path[r2];
                group[i].path[r2] = tmp;
                calculateFitness(group[i]); //更新适应度
            }
        }
    }

    void selectGroup(){  //选择种群
        sort(group.begin(),group.end(),compare);
        group.erase(group.begin()+param.populationSize,group.end());
    }

    //比较函数 用于排序
    static bool compare(individual a, individual b){
        return a.fitness > b.fitness;
    }

    double getResult(){  //获取最优路径
        return FITCHANGE/group[0].fitness;
    }

};

float getDistance(vector<vector<float>> &points ,int p1, int p2){  //计算欧式距离
    float disX = points[p2][0] - points[p1][0];
    float disY = points[p2][1] - points[p1][1];
    return pow((disX*disX+disY*disY),0.5);
}

float getBestResult(vector<vector<float>> &points){   //随机搜索最优路径 用于对比
    srand(time(NULL));
    vector<vector<float>> pointsCopy = points;
    float res = 999999;
    int length = points.size();
    for (size_t i = 0; i < 10000000; i++)
    {
        float now = 0;
        random_shuffle(pointsCopy.begin()+1,pointsCopy.end());
        for (size_t j = 0; j < length-1; j++)
            now += getDistance(pointsCopy,j , j+1);
        now += getDistance(pointsCopy,0,length-1);

        res = min(res, now);
    }
    return res;
}

int main() {
    vector<vector<float>> city = {{114.46,39.92}, {117.2,39.13}, {121.48,31.22}, 
    {106.54,29.59}, {91.11,29.97}, {87.68,43.77}, {106.27,38.47}, {111.65,40.82}, 
    {108.33,22.84}, {126.63,45.75}, {125.35,43.88}, {123.38,41.8}, {114.48,38.03},
     {112.53,37.87}, {101.74,36.56}, {117,36.65}, {113.6,34.76}, {118.78,32.04}, 
     {117.27,31.86}, {120.19,30.26}, {119.3,26.08}, {115.89,28.68}, {113,28.21},
      {114.31,30.52}, {113.23,23.16}, {121.5,25.05}, {110.35,20.02}, {103.73,36.03}, 
      {108.95,34.27}, {104.06,30.67}, {106.71,26.57}, {102.73,25.04}, {114.1,22.2},
       {113.33,22.13}};

    GeneticAlgorithm ob(city);
    // cout<
}

4、运行结果

第0代的适应度：366.876
第20代的适应度：331.165
第40代的适应度：296.491
第60代的适应度：258.766
第80代的适应度：231.551
第100代的适应度：218.176
第120代的适应度：205.759
第140代的适应度：194.666
第160代的适应度：185.43
第180代的适应度：181.359
第200代的适应度：177.293

5、存在的问题

代码运行时候，发现迭代时间随迭代次数增加而增加。
从理论上来说，迭代时间应该是相等的，目前未发现问题在哪。如有错误，欢迎指正。