C++版遗传算法求解TSP(3)

//扰动操作（产生新种群）
        for (int p = 0; p < POP_SIZE; p++) {
            HeuristicOperator shk;
            vector<int> randPosition = shk.RandPosition(n);
            vector<int> tmpS(n);
            double randShk = rand() / double(RAND_MAX);
            if (randShk < 0.33) {
                tmpS = shk.Swap(Pop[p], randPosition);        //交换操作
            }
            else if (randShk >= 0.67) {
                tmpS = shk.Flip(Pop[p], randPosition);        //翻转操作
            }
            else {
                tmpS = shk.Insert(Pop[p], randPosition);    //插入操作
            }

HeuristicOperator evl;
            if (evl.Eval(tmpS, GA_DM, n) > evl.Eval(Pop[p], GA_DM, n)) {
                newPop[p] = Pop[p];
            }
            else {
                newPop[p] = tmpS;
            }
        }
        Pop = newPop;

//选择操作（轮盘赌）
        vector<double> Cusum(POP_SIZE + 1, 0);        //适用于轮盘赌的累加器Cusum（补充了cus[0]=0;
        for (int i = 0; i < POP_SIZE; i++) {
            Cusum[i + 1] = Cusum[i] + popFit[i];
        }

double Sum = accumulate(popFit.begin(), popFit.end(), 0.0);        //计算各个体被选择的概率（归一化）
        vector<double> cusFit(POP_SIZE + 1);        //放置种群中个个体被选择的概率值
        for (int i = 0; i < POP_SIZE + 1; i++) {
            cusFit[i] = Cusum[i] / Sum;
        }

for (int p = 0; p < POP_SIZE; p++) {        //轮盘赌产生新种群
            double r = rand() / double(RAND_MAX);
            for (int q = 0; q < POP_SIZE; q++) {
                if (r > cusFit[q] && r <= cusFit[q + 1]) {
                    newPop[p] = Pop[q];
                }
            }
        }
        Pop = newPop;
    }

//计时结束
    auto end = system_clock::now();
    auto duration = duration_cast<microseconds>(end - start);
    cout << "花费了"
        << double(duration.count()) * microseconds::period::num / microseconds::period::den
        << "秒" << endl;

//输出结果
    double gs0 = 15377.711;
    cout << "最优解为" << gs[MAX_GEN] << endl;
    double e = (gs[MAX_GEN] - gs0) / gs0;
    cout << "误差为" << e * 100.0 << '%' << endl;
    cout << "最优路径为" << endl;
    for (int i = 0; i < n; i++) {
        cout << bestIndival[i] + 1 << '\t';
    }
   
    while (1)
　　　　{}
}

以上即为C++语言所编写的遗传算法求解TSP示例，运行环境为：Windows10 64位操作系统；CPU：i7-8750H; 内存：8G；Microsoft Visual Studio Community 2017 。求解结果如下：

与已知最优解的误差为1.48%，所用时间约为3.6s. 还可以接受。但值得注意的是：本文实验参数最大迭代次数4000代，而种群规模仅为2，这与一般的遗传算法思想上是没问题的，只是实际参数可能不太符合。当然，对于算法参数这些细节都是可以调节的，不必太过于纠结。

啊哈，这次的利用C++编程遗传算法求解TSP就这些了~~~

Linux公社的RSS地址：https://www.linuxidc.com/rssFeed.aspx