标签：roo ack reg poc 组复制 int start clu cross data
#include
#include
#include
#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.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 = s)
break;
}
memcpy(TempColony[t], city.colony[i - 1], sizeof(TempColony[t]));
}
for (i = 0; i b)//保证让b>=a
{
t = a;
a = b;
b = t;
}
for (m = a; m b)
{
t = a;
a = b;
b = t;
}
for (m = a; m b)
{
t = a;
a = b;
b = t;
}
for (m = a; m
读取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
#include
#include
#include "math.h"
#include "time.h"
#include
#include
#include
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 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 CityPos;
//城市距离词典
vector>CityDistance;
typedef struct {
vector>colony;//int colony[POPSIZE][CITY_NUM + 1];//城市种群,默认出发城市编号为0，则城市编号的最后一个城市还应该为0
double fitness[POPSIZE];// 每个个体的适应值，即1/Distance[POPSIZE]
double Distance[POPSIZE];//每个个体的总路径
vectorBestRooting;//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 v_tmp;
for (j = 0; j &a, vectorb)
{
a = b;
}
/*用来检查新生成的节点是否在当前群体中，0号节点是默认出发节点和终止节点*/
bool check(TSP& city, int pop, int num, int k)
{
int i;
for (i = 0; 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>TempColony;
TempColony.resize(POPSIZE);
for(int i=0;i= s)
break;
}
TempColony[t] = city.colony[i - 1];
//memcpy(TempColony[t], city.colony[i - 1], sizeof(TempColony[t]));
}
for (i = 0; i Temp1;
Temp1.resize(CITY_NUM + 1);
vectorTemp2;
Temp2.resize(CITY_NUM + 1);
// int Temp1[CITY_NUM + 1], Temp2[CITY_NUM + 1];
for (i = 0; i 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 a)
{
int i, start, end;
double Distance = 0;
for (i = 0; i Temp;
Temp.resize(CITY_NUM + 1);
// int Temp[CITY_NUM + 1];
for (k = 0; k b)//保证让b>=a
{
t = a;
a = b;
b = t;
}
for (m = a; m b)
{
t = a;
a = b;
b = t;
}
for (m = a; m b)
{
t = a;
a = b;
b = t;
}
for (m = a; m 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 &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
程序会打印：
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
标签：roo ack reg poc 组复制 int start clu cross data
原文地址：https://www.cnblogs.com/yanghailin/p/12781840.html