首页 / 算法 / 遗传算法 商旅问题 c++ GA tsp
遗传算法 商旅问题 c++ GA tsp
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了遗传算法 商旅问题 c++ GA tsp，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含21035字，纯文字阅读大概需要31分钟。
内容图文
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "math.h"
#include "time.h"
#define CITY_NUM 38 //城市数，城市编号是0~CITY_NUM-1
#define POPSIZE 300 //种群个体数
#define MAXVALUE 10000000 //路径最大值上限
#define N 100000//需要根据实际求得的路径值修正
unsigned seed = (unsigned)time(0);
double Hash[CITY_NUM + 1];
typedef struct CityPosition
{
double x;
double y;
}CityPosition;
CityPosition CityPos[38] = {
{11003.611100,42102.500000},{11108.611100,42373.888900},{11133.333300,42885.833300},{11155.833300,42712.500000},{11183.333300,42933.333300},{11297.500000,42853.333300},{11310.277800,42929.444400},{11416.666700,42983.333300},{11423.888900,43000.277800},{11438.333300,42057.222200},{11461.111100,43252.777800},{11485.555600,43187.222200},{11503.055600,42855.277800},{11511.388900,42106.388900},{11522.222200,42841.944400},{11569.444400,43136.666700},{11583.333300,43150.000000},{11595.000000,43148.055600},{11600.000000,43150.000000},{11690.555600,42686.666700},{11715.833300,41836.111100},{11751.111100,42814.444400},{11770.277800,42651.944400},{11785.277800,42884.444400},{11822.777800,42673.611100},{11846.944400,42660.555600},{11963.055600,43290.555600},{11973.055600,43026.111100},{12058.333300,42195.555600},{12149.444400,42477.500000},{12286.944400,43355.555600},{12300.000000,42433.333300},{12355.833300,43156.388900},{12363.333300,43189.166700},{12372.777800,42711.388900},{12386.666700,43334.722200},{12421.666700,42895.555600},{12645.000000,42973.333300}
};
double CityDistance[CITY_NUM][CITY_NUM];//城市距离词典
typedef struct {
int colony[POPSIZE][CITY_NUM + 1];//城市种群,默认出发城市编号为0，则城市编号的最后一个城市还应该为0
double fitness[POPSIZE];// 每个个体的适应值，即1/Distance[POPSIZE]
double Distance[POPSIZE];//每个个体的总路径
int BestRooting[CITY_NUM + 1];//最优城市路径序列
double BestFitness;//最优路径适应值
double BestValue;//最优路径长度
int BestNum;
}TSP, * PTSP;
/*计算城市距离词典CityDistance[i][j]*/
void CalculatDist()
{
int i, j;
double temp1, temp2;
for (i = 0; i < CITY_NUM; i++) {
for (j = 0; j <= CITY_NUM; j++) {//最后一个城市还应该返回到出发节点
temp1 = CityPos[j].x - CityPos[i].x;
temp2 = CityPos[j].y - CityPos[i].y;
CityDistance[i][j] = sqrt(temp1 * temp1 + temp2 * temp2);
}
}
}
/*数组复制*/
void copy(int a[], int b[])
{
int i = 0;
for (i = 0; i < CITY_NUM + 1; i++)
{
a[i] = b[i];
}
}
/*用来检查新生成的节点是否在当前群体中，0号节点是默认出发节点和终止节点*/
bool check(TSP& city, int pop, int num, int k)
{
int i;
for (i = 0; i <= num; i++) {
if (k == city.colony[pop][i])
return true;//新生成节点存在于已经生成的路径中
}
return false;//新生成节点没有存在于已经生成的路径中
}
/****************种群初始化，即为city.colony[i][j]赋值****************/
void InitColony(TSP& city)
{
int i, j, r;
for (i = 0; i < POPSIZE; i++) {
city.colony[i][0] = 0;
city.colony[i][CITY_NUM] = 0;
city.BestValue = MAXVALUE;
city.BestFitness = 0;//适应值越大越好
}
for (i = 0; i < POPSIZE; i++)
{
for (j = 1; j < CITY_NUM; j++)
{
r = rand() % (CITY_NUM - 1) + 1;//产生1～CITY_NUM-1之间的随机数
while (check(city, i, j, r))//随机产生城市序号，即为city.colony[i][j]赋值
{
r = rand() % (CITY_NUM - 1) + 1;
}
city.colony[i][j] = r;
}
}
}
/*计算适应值,考虑应该在这里面把最优选出来*/
void CalFitness(TSP& city)
{
int i, j;
int start, end;
int Best = 0;
for (i = 0; i < POPSIZE; i++) {//求每个个体的总路径，适应值
city.Distance[i] = 0;
for (j = 1; j <= CITY_NUM; j++) {
start = city.colony[i][j - 1]; end = city.colony[i][j];
city.Distance[i] = city.Distance[i] + CityDistance[start][end];//city.Distance[i]每个个体的总路径
}
city.fitness[i] = N / city.Distance[i];
if (city.fitness[i] > city.fitness[Best])//选出最大的适应值，即选出所有个体中的最短路径
Best = i;
}
copy(city.BestRooting, city.colony[Best]);//将最优个体拷贝给city.BestRooting
city.BestFitness = city.fitness[Best];
city.BestValue = city.Distance[Best];
city.BestNum = Best;
}
/****************选择算子：轮盘赌法****************/
void Select(TSP& city)
{
int TempColony[POPSIZE][CITY_NUM + 1];
int i, j, t;
double s;
double GaiLv[POPSIZE];
double SelectP[POPSIZE + 1];
double avg;
double sum = 0;
for (i = 0; i < POPSIZE; i++)
{
sum += city.fitness[i];
}
for (i = 0; i < POPSIZE; i++)
{
GaiLv[i] = city.fitness[i] / sum;
}
SelectP[0] = 0;
for (i = 0; i < POPSIZE; i++)
{
SelectP[i + 1] = SelectP[i] + GaiLv[i] * RAND_MAX;
}
memcpy(TempColony[0], city.colony[city.BestNum], sizeof(TempColony[0]));//void *memcpy(void *dest, const void *src, size_t n)从源src所指的内存地址的起始位置开始拷贝n个字节到目标dest所指的内存地址的起始位置中
for (t = 1; t < POPSIZE; t++)
{
double ran = rand() % RAND_MAX + 1;
s = (double)ran / 100.0;
for (i = 1; i < POPSIZE; i++)
{
if (SelectP[i] >= s)
break;
}
memcpy(TempColony[t], city.colony[i - 1], sizeof(TempColony[t]));
}
for (i = 0; i < POPSIZE; i++)
{
memcpy(city.colony[i], TempColony[i], sizeof(TempColony[i]));
}
}
/****************交叉：头尾不变，中间打乱顺序交叉****************/
void Cross(TSP& city, double pc)//交叉概率是pc
{
int i, j, t, l;
int a, b, ca, cb;
int Temp1[CITY_NUM + 1], Temp2[CITY_NUM + 1];
for (i = 0; i < POPSIZE; i++)
{
double s = ((double)(rand() % RAND_MAX)) / RAND_MAX;
if (s < pc)
{
cb = rand() % POPSIZE;
ca = cb;
if (ca == city.BestNum || cb == city.BestNum)//如果遇到最优则直接进行下次循环
continue;
l = rand() % 19 + 1; //1-19
a = rand() % (CITY_NUM - l) + 1; //1-37
memset(Hash, 0, sizeof(Hash));//void *memset(void *s, int ch, size_t n);将s中当前位置后面的n个字节 用 ch 替换并返回 s 。
Temp1[0] = Temp1[CITY_NUM] = 0;
for (j = 1; j <= l; j++)//打乱顺序即随机，选出来的通过Hash标记为1
{
Temp1[j] = city.colony[cb][a + j - 1]; //a+L=2~38 20~38
Hash[Temp1[j]] = 1;
}
for (t = 1; t < CITY_NUM; t++)
{
if (Hash[city.colony[ca][t]] == 0)
{
Temp1[j++] = city.colony[ca][t];
Hash[city.colony[ca][t]] = 1;
}
}
memcpy(city.colony[ca], Temp1, sizeof(Temp1));
}
}
}
/****************变异****************/
double GetFittness(int a[CITY_NUM + 1])
{
int i, start, end;
double Distance = 0;
for (i = 0; i < CITY_NUM; i++)
{
start = a[i]; end = a[i + 1];
Distance += CityDistance[start][end];
}
return N / Distance;
}
/*对换变异*/
void Mutation(TSP& city, double pm)//变异概率是pm
{
int i, k, m;
int Temp[CITY_NUM + 1];
for (k = 0; k < POPSIZE; k++)
{
double s = ((double)(rand() % RAND_MAX)) / RAND_MAX;//随机产生概率0~1间
i = rand() % POPSIZE;//随机产生0~POPSIZE之间的数
if (s < pm && i != city.BestNum)//i!=city.BestNum，即保证最优的个体不变异
{
int a, b, t;
a = (rand() % (CITY_NUM - 1)) + 1;
b = (rand() % (CITY_NUM - 1)) + 1;
copy(Temp, city.colony[i]);
if (a > b)//保证让b>=a
{
t = a;
a = b;
b = t;
}
for (m = a; m < (a + b) / 2; m++)
{
t = Temp[m];
Temp[m] = Temp[a + b - m];
Temp[a + b - m] = t;
}
if (GetFittness(Temp) < GetFittness(city.colony[i]))
{
a = (rand() % (CITY_NUM - 1)) + 1;
b = (rand() % (CITY_NUM - 1)) + 1;
//copy(Temp,city.colony[i]);
memcpy(Temp, city.colony[i], sizeof(Temp));
if (a > b)
{
t = a;
a = b;
b = t;
}
for (m = a; m < (a + b) / 2; m++)
{
t = Temp[m];
Temp[m] = Temp[a + b - m];
Temp[a + b - m] = t;
}
if (GetFittness(Temp) < GetFittness(city.colony[i]))
{
a = (rand() % (CITY_NUM - 1)) + 1;
b = (rand() % (CITY_NUM - 1)) + 1;
//copy(Temp,city.colony[i]);
memcpy(Temp, city.colony[i], sizeof(Temp));
if (a > b)
{
t = a;
a = b;
b = t;
}
for (m = a; m < (a + b) / 2; m++)
{
t = Temp[m];
Temp[m] = Temp[a + b - m];
Temp[a + b - m] = t;
}
}
}
memcpy(city.colony[i], Temp, sizeof(Temp));
}
}
}
void OutPut(TSP& city)
{
int i, j;
printf("最佳路径为:\n");
for (i = 0; i <= CITY_NUM; i++)
printf("%5d", city.BestRooting[i]);
printf("\n最佳路径值为：%f\n", (city.BestValue));
}
int main()
{
TSP city;
double pcross, pmutation;//交叉概率和变异概率
int MaxEpoc;//最大迭代次数
int i;
srand(seed);
MaxEpoc = 30000;
pcross = 0.5; pmutation = 0.05;
CalculatDist();//计算城市距离词典
InitColony(city);//生成初始种群
CalFitness(city);//计算适应值,考虑应该在这里面把最优选出来
for (i = 0; i < MaxEpoc; i++)
{
Select(city);//选择(复制)：轮盘赌法
Cross(city, pcross);//交叉
Mutation(city, pmutation);//变异
CalFitness(city);//计算适应值
OutPut(city);
}
OutPut(city);//输出
return 0;
}
读取txt，txt里面的文本格式如下，第一行表示城市数量，最后的1,2,3表示地点的性质，1:capital, 2:regional, 3:country
表示两两地点的每公里多少元，就是距离还要乘以单价等于花费。
100
70 66 3
53 861 2
291 58 1
342 637 3
908 601 2
528 783 3
647 119 1
151 878 3
322 675 1
125 710 3
139 617 1
857 422 2
977 357 2
164 408 3
136 503 1
468 288 2
211 150 1
876 881 3
697 281 2
404 157 2
758 678 3
337 944 1
536 9 1
192 696 3
440 505 2
617 166 3
230 532 2
336 294 2
519 939 2
726 393 2
654 59 3
243 670 2
954 151 1
469 562 2
106 665 2
530 335 1
256 465 1
792 42 2
87 828 2
554 359 3
187 155 2
713 205 1
。。。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "math.h"
#include "time.h"
#include<vector>
#include<iostream>
#include<fstream>
using namespace std;
#define MAXVALUE 10000000 //路径最大值上限
#define MaxEpoc 900000
#define pcross 0.65 //0.5
#define pmutation 0.09 //0.05
#define POPSIZE 4000 //500
#define N 100000//需要根据实际求得的路径值修正
unsigned seed = (unsigned)time(0);
vector<double> Hash;
int city_num_t = 0;
int CITY_NUM;
double cost_matrix[3][3] = {10,7.5,5,
7.5,5,2.5,
5,2.5,1};
typedef struct CityPosition
{
double x;
double y;
int type;
}CityPosition;
vector<CityPosition> CityPos;
//城市距离词典
vector<vector<double>>CityDistance;
typedef struct {
vector<vector<int>>colony;//int colony[POPSIZE][CITY_NUM + 1];//城市种群,默认出发城市编号为0，则城市编号的最后一个城市还应该为0
double fitness[POPSIZE];// 每个个体的适应值，即1/Distance[POPSIZE]
double Distance[POPSIZE];//每个个体的总路径
vector<int>BestRooting;//int BestRooting[CITY_NUM + 1];//最优城市路径序列
double BestFitness;//最优路径适应值
double BestValue;//最优路径长度
int BestNum;
}TSP, * PTSP;
/*计算城市距离词典CityDistance[i][j]*/
void CalculatDist()
{
int i, j;
double temp1, temp2;
for (i = 0; i < CITY_NUM; i++) {
vector<double> v_tmp;
for (j = 0; j < CITY_NUM; j++) {//最后一个城市还应该返回到出发节点
temp1 = CityPos[j].x - CityPos[i].x;
temp2 = CityPos[j].y - CityPos[i].y;
int type_city_i = CityPos[i].type;
int type_city_j = CityPos[j].type;
double per_cost = cost_matrix[type_city_i][type_city_j];
v_tmp.push_back((sqrt(temp1 * temp1 + temp2 * temp2) * per_cost));
}
CityDistance.push_back(v_tmp);
}
}
/*数组复制*/
void copy(int a[], int b[])
{
int i = 0;
for (i = 0; i < CITY_NUM + 1; i++)
{
a[i] = b[i];
}
}
/*数组复制*/
void copy(vector<int>&a, vector<int>b)
{
a = b;
}
/*用来检查新生成的节点是否在当前群体中，0号节点是默认出发节点和终止节点*/
bool check(TSP& city, int pop, int num, int k)
{
int i;
for (i = 0; i <= num; i++) {
if (k == city.colony[pop][i])
return true;//新生成节点存在于已经生成的路径中
}
return false;//新生成节点没有存在于已经生成的路径中
}
/****************种群初始化，即为city.colony[i][j]赋值****************/
void InitColony(TSP& city)
{
int i, j, r;
for (i = 0; i < POPSIZE; i++) {
city.colony[i][0] = 0;
city.colony[i][CITY_NUM] = 0;
city.BestValue = MAXVALUE;
city.BestFitness = 0;//适应值越大越好
}
for (i = 0; i < POPSIZE; i++)
{
for (j = 1; j < CITY_NUM; j++)
{
r = rand() % (CITY_NUM - 1) + 1;//产生1～CITY_NUM-1之间的随机数
while (check(city, i, j, r))//随机产生城市序号，即为city.colony[i][j]赋值
{
r = rand() % (CITY_NUM - 1) + 1;
}
city.colony[i][j] = r;
}
}
}
/*计算适应值,考虑应该在这里面把最优选出来*/
void CalFitness(TSP& city)
{
int i, j;
int start, end;
int Best = 0;
for (i = 0; i < POPSIZE; i++) {//求每个个体的总路径，适应值
city.Distance[i] = 0;
for (j = 1; j <= CITY_NUM; j++) {
start = city.colony[i][j - 1]; end = city.colony[i][j];
city.Distance[i] = city.Distance[i] + CityDistance[start][end];//city.Distance[i]每个个体的总路径
}
city.fitness[i] = N / city.Distance[i];
if (city.fitness[i] > city.fitness[Best])//选出最大的适应值，即选出所有个体中的最短路径
Best = i;
}
copy(city.BestRooting, city.colony[Best]);//将最优个体拷贝给city.BestRooting
city.BestFitness = city.fitness[Best];
city.BestValue = city.Distance[Best];
city.BestNum = Best;
}
/****************选择算子：轮盘赌法****************/
void Select(TSP& city)
{
vector<vector<int>>TempColony;
TempColony.resize(POPSIZE);
for(int i=0;i<POPSIZE;i++)
{
TempColony[i].resize(CITY_NUM + 1);
}
int i, j, t;
double s;
double GaiLv[POPSIZE];
double SelectP[POPSIZE + 1];
double avg;
double sum = 0;
for (i = 0; i < POPSIZE; i++)
{
sum += city.fitness[i];
}
for (i = 0; i < POPSIZE; i++)
{
GaiLv[i] = city.fitness[i] / sum;
}
SelectP[0] = 0;
for (i = 0; i < POPSIZE; i++)
{
SelectP[i + 1] = SelectP[i] + GaiLv[i] * RAND_MAX;
}
TempColony[0] = city.colony[city.BestNum];
// memcpy(TempColony[0], city.colony[city.BestNum], sizeof(TempColony[0]));//void *memcpy(void *dest, const void *src, size_t n)从源src所指的内存地址的起始位置开始拷贝n个字节到目标dest所指的内存地址的起始位置中
for (t = 1; t < POPSIZE; t++)
{
double ran = rand() % RAND_MAX + 1;
s = (double)ran / 100.0;
for (i = 1; i < POPSIZE; i++)
{
if (SelectP[i] >= s)
break;
}
TempColony[t] = city.colony[i - 1];
//memcpy(TempColony[t], city.colony[i - 1], sizeof(TempColony[t]));
}
for (i = 0; i < POPSIZE; i++)
{
city.colony[i] = TempColony[i];
// memcpy(city.colony[i], TempColony[i], sizeof(TempColony[i]));
}
}
/****************交叉：头尾不变，中间打乱顺序交叉****************/
void Cross(TSP& city, double pc)//交叉概率是pc
{
int i, j, t, l;
int a, b, ca, cb;
vector<int>Temp1;
Temp1.resize(CITY_NUM + 1);
vector<int>Temp2;
Temp2.resize(CITY_NUM + 1);
// int Temp1[CITY_NUM + 1], Temp2[CITY_NUM + 1];
for (i = 0; i < POPSIZE; i++)
{
double s = ((double)(rand() % RAND_MAX)) / RAND_MAX;
if (s < pc)
{
cb = rand() % POPSIZE;
ca = cb;
if (ca == city.BestNum || cb == city.BestNum)//如果遇到最优则直接进行下次循环
continue;
l = rand() % 19 + 1; //1-19
a = rand() % (CITY_NUM - l) + 1; //1-37
vector<double> abc(CITY_NUM);
Hash = abc;
// memset(Hash, 0, sizeof(Hash));//void *memset(void *s, int ch, size_t n);将s中当前位置后面的n个字节 用 ch 替换并返回 s 。
Temp1[0] = Temp1[CITY_NUM] = 0;
for (j = 1; j <= l; j++)//打乱顺序即随机，选出来的通过Hash标记为1
{
Temp1[j] = city.colony[cb][a + j - 1]; //a+L=2~38 20~38
Hash[Temp1[j]] = 1;
}
for (t = 1; t < CITY_NUM; t++)
{
if (Hash[city.colony[ca][t]] == 0)
{
Temp1[j++] = city.colony[ca][t];
Hash[city.colony[ca][t]] = 1;
}
}
city.colony[ca] = Temp1;
// memcpy(city.colony[ca], Temp1, sizeof(Temp1));
}
}
}
/****************变异****************/
double GetFittness(int a[])
{
int i, start, end;
double Distance = 0;
for (i = 0; i < CITY_NUM; i++)
{
start = a[i]; end = a[i + 1];
Distance += CityDistance[start][end];
}
return N / Distance;
}
double GetFittness(vector<int>a)
{
int i, start, end;
double Distance = 0;
for (i = 0; i < CITY_NUM; i++)
{
start = a[i]; end = a[i + 1];
Distance += CityDistance[start][end];
}
return N / Distance;
}
/*对换变异*/
void Mutation(TSP& city, double pm)//变异概率是pm
{
int i, k, m;
vector<int> Temp;
Temp.resize(CITY_NUM + 1);
// int Temp[CITY_NUM + 1];
for (k = 0; k < POPSIZE; k++)
{
double s = ((double)(rand() % RAND_MAX)) / RAND_MAX;//随机产生概率0~1间
i = rand() % POPSIZE;//随机产生0~POPSIZE之间的数
if (s < pm && i != city.BestNum)//i!=city.BestNum，即保证最优的个体不变异
{
int a, b, t;
a = (rand() % (CITY_NUM - 1)) + 1;
b = (rand() % (CITY_NUM - 1)) + 1;
copy(Temp, city.colony[i]);
if (a > b)//保证让b>=a
{
t = a;
a = b;
b = t;
}
for (m = a; m < (a + b) / 2; m++)
{
t = Temp[m];
Temp[m] = Temp[a + b - m];
Temp[a + b - m] = t;
}
if (GetFittness(Temp) < GetFittness(city.colony[i]))
{
a = (rand() % (CITY_NUM - 1)) + 1;
b = (rand() % (CITY_NUM - 1)) + 1;
//copy(Temp,city.colony[i]);
Temp = city.colony[i];
// memcpy(Temp, city.colony[i], sizeof(Temp));
if (a > b)
{
t = a;
a = b;
b = t;
}
for (m = a; m < (a + b) / 2; m++)
{
t = Temp[m];
Temp[m] = Temp[a + b - m];
Temp[a + b - m] = t;
}
if (GetFittness(Temp) < GetFittness(city.colony[i]))
{
a = (rand() % (CITY_NUM - 1)) + 1;
b = (rand() % (CITY_NUM - 1)) + 1;
//copy(Temp,city.colony[i]);
Temp = city.colony[i];
// memcpy(Temp, city.colony[i], sizeof(Temp));
if (a > b)
{
t = a;
a = b;
b = t;
}
for (m = a; m < (a + b) / 2; m++)
{
t = Temp[m];
Temp[m] = Temp[a + b - m];
Temp[a + b - m] = t;
}
}
}
city.colony[i] = Temp;
// memcpy(city.colony[i], Temp, sizeof(Temp));
}
}
}
void OutPut(TSP& city)
{
int i, j;
printf("best path:\n");
for (i = 0; i <= CITY_NUM; i++)
printf("%5d", city.BestRooting[i]);
printf("\nbest path cost：%f\n", (city.BestValue));
}
CityPosition split(const string& str, const string delim) {
CityPosition city_tmp;
vector<int> res;
if("" == str) return city_tmp;
//先将要切割的字符串从string类型转换为char*类型
char * strs = new char[str.length() + 1] ; //不要忘了
strcpy(strs, str.c_str());
char * d = new char[delim.length() + 1];
strcpy(d, delim.c_str());
char *p = strtok(strs, d);
while(p) {
string s = p; //分割得到的字符串转换为string类型
int num = atoi(s.c_str());
res.push_back(num); //存入结果数组
p = strtok(NULL, d);
}
city_tmp = {res[0],res[1],res[2]};
return city_tmp;
}
bool Init(string path_txt,vector<CityPosition> &v_city_pos)
{
fstream infile(path_txt);
string txt_content;
int cnt = 0;
while(getline(infile,txt_content))
{
if(0 == cnt)
{
city_num_t = stoi(txt_content);
}else
{
CityPosition city_tmp = split(txt_content," ");
v_city_pos.push_back(city_tmp);
}
cnt += 1;
}
if(cnt < 2)
{
return false;
}
CITY_NUM = city_num_t;
Hash.resize(CITY_NUM);
return true;
}
int main()
{
// string path_txt = "/data_2/tsp200.txt";
string path_txt;
cout<<"Please enter the path:"<<endl;
getline(cin,path_txt);
cout<<"path="<<path_txt<<endl;
Init(path_txt,CityPos);
TSP city;
city.colony.resize(POPSIZE);
for(int i=0;i<POPSIZE;i++)
{
city.colony[i].resize(CITY_NUM + 1);
}
city.BestRooting.resize(CITY_NUM + 1);
int i;
srand(seed);
// double pcross, pmutation;//交叉概率和变异概率
// int MaxEpoc;//最大迭代次数
// MaxEpoc = 1000000;//30000;
// pcross = 0.5;
// pmutation = 0.05;
CalculatDist();//计算城市距离词典
InitColony(city);//生成初始种群
CalFitness(city);//计算适应值,考虑应该在这里面把最优选出来
for (i = 0; i < MaxEpoc; i++)
{
Select(city);//选择(复制)：轮盘赌法
Cross(city, pcross);//交叉
Mutation(city, pmutation);//变异
CalFitness(city);//计算适应值
if(i % 2000 == 0)
{
cout<<"step="<<i<<endl;
OutPut(city);
}
}
cout<<"Here's the best---Here's the best---Here's the best--Here's the best"<<endl;
OutPut(city);//输出
return 0;
}
程序会打印：
step=174000
best path:
0 47 24 16 117 17 116 123 27 188 109 171 105 175 48 153 194 125 26 198 30 145 139 83 181 41 72 150 154 12 112 80 118 134 166 20 131 98 121 60 132 69 4 7 183 193 58 167 88 29 73 197 82 100 89 62 76 155 122 162 10 99 35 8 196 13 191 101 110 173 106 52 90 104 28 157 160 135 146 61 38 103 138 9 143 54 79 64 199 133 55 168 78 25 14 37 51 115 53 152 136 59 96 2 178 119 45 5 15 128 31 111 65 50 129 130 19 68 84 113 159 34 33 120 127 187 23 91 149 179 75 85 141 107 151 93 42 148 18 74 176 158 142 56 11 94 163 140 40 71 3 92 6 114 95 156 174 124 137 144 126 66 87 184 36 185 67 43 57 70 189 177 39 147 172 169 165 44 108 170 180 190 77 32 102 22 81 195 97 63 186 164 192 21 49 161 46 86 1 182 0
best path cost：10332.477128
step=176000
best path:
0 47 24 16 117 178 119 45 17 116 88 29 73 197 82 100 89 62 76 155 122 162 5 15 139 83 181 41 72 150 154 12 112 80 142 56 11 26 198 30 145 92 118 134 166 20 131 98 121 66 87 184 36 185 67 60 132 69 4 7 183 55 168 78 25 14 37 51 115 53 152 136 59 96 2 94 163 140 40 71 3 123 27 188 109 171 105 175 48 153 194 125 193 58 167 10 99 35 8 196 13 191 101 110 173 106 52 90 104 28 157 160 135 146 61 38 103 138 9 143 54 79 64 199 133 128 31 111 65 50 129 130 19 68 84 113 159 34 33 120 127 187 23 91 149 179 75 85 141 107 151 93 42 148 18 74 176 158 6 114 95 156 174 124 137 144 126 43 57 70 189 177 39 147 172 169 165 44 108 170 180 190 77 32 102 22 81 195 97 63 186 164 192 21 49 161 46 86 1 182 0
best path cost：10079.972115
step=178000
best path:
0 47 173 106 52 90 104 28 157 160 135 146 61 38 103 138 9 143 54 79 64 24 16 117 178 119 45 17 116 88 29 73 197 82 100 89 62 76 155 122 162 5 15 139 83 181 41 72 150 154 12 112 80 142 56 11 26 198 30 145 92 118 134 166 20 131 98 121 66 87 184 36 185 67 60 132 69 4 7 183 55 168 78 25 14 37 51 115 53 152 136 59 96 2 94 163 140 40 71 3 123 27 188 109 171 105 175 48 153 194 125 193 58 167 10 99 35 8 196 13 191 101 110 199 133 128 31 111 65 50 129 130 19 68 84 113 159 34 33 120 127 187 23 91 149 179 75 85 141 107 151 93 42 148 18 74 176 158 6 114 95 156 174 124 137 144 126 43 57 70 189 177 39 147 172 169 165 44 108 170 180 190 77 32 102 22 81 195 97 63 186 164 192 21 49 161 46 86 1 182 0
best path cost：10079.972115
我还看到中间的best path cost会小于新出来的，可能代码哪里有点儿小问题。
内容总结
以上是互联网集市为您收集整理的遗传算法 商旅问题 c++ GA tsp全部内容，希望文章能够帮你解决遗传算法 商旅问题 c++ GA tsp所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】