对应的HeuristicOperator.cpp类文件比较容易实现,在此不再赘述。本文所用算例为31城市的TSP问题,与Java版遗传算法求解TSP求解算例一致,具体数据如下:
1304 2312
3639 1315
4177 2244
3712 1399
3488 1535
3326 1556
3238 1229
4196 1004
4312 790
4386 570
3007 1970
2562 1756
2788 1491
2381 1676
1332 695
3715 1678
3918 2179
4061 2370
3780 2212
3676 2578
4029 2838
4263 2931
3429 1908
3507 2367
3394 2643
3439 3201
2935 3240
3140 3550
2545 2357
2778 2826
2370 2975
以下为遗传算法的主函数:
/*
文件名:CppGATSP
作者:Alex Xu
地址:Dalian Maritime University
描述:利用遗传算法求解TSP问题
创建时间:2018年12月10日11点27分
*/
#include<iostream>
#include<vector>
#include<numeric> //accumulate
#include<chrono> //time
#include "HeuristicOperator.h"
using namespace std;
using namespace chrono;
//设置算法参数
# define POP_SIZE 2
# define MAX_GEN 4000
int main() {
//计时开始
auto start = system_clock::now();
//生成距离矩阵
HeuristicOperator ga_dm;
vector<vector<double>> GA_DM;
GA_DM = ga_dm.getDM(ga_dm.getCoord());
int n = int(GA_DM[0].size()); //城市规模
//初始化算法
vector<vector<int>> initPop(POP_SIZE, vector<int>(n)); //初始种群
vector<vector<int>> Pop(POP_SIZE, vector<int>(n)); //当前种群
vector<vector<int>> newPop(POP_SIZE, vector<int>(n)); //新种群
vector<double> popFit(POP_SIZE); //记录种群适应度值
vector<int> bestIndival(n); //最优个体
vector<double> gs(MAX_GEN + 1); //记录全局最优解
gs[0] = 1e9;
unsigned int seed = (unsigned)std::chrono::system_clock::now().time_since_epoch().count();
//生成初始种群
HeuristicOperator s0;
for (int i = 0; i < POP_SIZE; i++) {
initPop[i] = s0.getInitS(n);
}
Pop = initPop;
//开始进化
for (int gen = 1; gen <= MAX_GEN; gen++) {
HeuristicOperator eval; //计算种群的适应度值(这里直接用路径长度表示)
for (int i = 0; i < POP_SIZE; i++) {
popFit[i] = eval.Eval(Pop[i], GA_DM, n);
}
HeuristicOperator bestEI; //找出种群中个体的最优适应度值并记录相应的个体编号
vector<double> bestEvalIndex(2);
bestEvalIndex = bestEI.bestS(popFit, POP_SIZE);
double bestEval = bestEvalIndex[0]; //最优适应度值
int bestIndex = int(bestEvalIndex[1]); //最优适应度值对应的个体编号
//最优解的更新
if (bestEval < gs[gen - 1]) { //比上一代优秀则更新
gs[gen] = bestEval;
bestIndival = Pop[bestIndex];
}
else { //不比上一代优秀则不更新
gs[gen] = gs[gen - 1];
}
if (gen % 100 == 0) {
cout << "第" << gen << "次迭代时全局最优评价值为" << gs[gen] << endl;
}