C++ 用遗传算法解决TSP问题，旅行商问题
走在IT的路上 2018-11-22
这也是人工智能实验的一个题目
这是一个很简陋的遗传算法版本，只有交叉（交配）
因为种群个体只有2个，所以就抛弃了选择复制
变异暂无
#include<iostream>
#include<fstream>
using namespace std;
float city_dis[4][4];
class individual
{
public:
int gene[5]; //个体基因，5个数字，0xxx0，从城市0开始出发，到0结束
float fitness; //适应度，取20.0/distance （这个20随便取的，重点是distance的倒数）
int distance; //计算当前基因（路线）下的总距离
individual(int gene0,int gene1,int gene2,int gene3,int gene4)
{//初始化基因
gene[0]=gene0;
gene[1]=gene1;
gene[2]=gene2;
gene[3]=gene3;
gene[4]=gene4;
//基因传递后执行update函数（计算fitness和distance）
update_info();
}
void set_new_gene(int *new_gene)
{
for(int i=1;i<4;++i)
{//设置新基因只会改变中间3个基因，所以循环从1到3
this->gene[i] = new_gene[i-1];//gene和传递进来到new_gene开始计数值不同
}
update_info();//更新个体fitness和distance
}
void update_info()
{//更新fitness和distance的函数
int new_dis = 0;
for(int i=0;i<4;++i)
{
new_dis += city_dis[this->gene[i]][this->gene[i+1]];
}
this->distance = new_dis;
this->fitness = 20.0/this->distance;
}
};
class tsp
{
public:
int ROUTE_NUM; //城市数量，用于循环
int generation_counts; //迭代次数，控制循环结束时间
int best_route[5]; //存储目前最好的个体（路线）
int best_distance; //最好个体的路线距离
float best_fitness; //其适应度
individual *father1; //初始个体1（路线1
individual *father2; //初始个体2（路线2
tsp()
{
ROUTE_NUM = 5; //5个城市
generation_counts = 500; //迭代次数500次
memset(best_route,-1,5*sizeof(int));
best_distance = 0;
best_fitness = 0;
load_city_distance(); //从文件加载城市距离
father1 = new individual(0,2,1,3,0); //初始化个体1
//try rand father sequence //取消下面备注则会生成随机的基因给初始个体
// int rand1[3];
// get_random_nums(rand1,3);
// father1->set_new_gene(rand1);
father2 = new individual(0,1,3,2,0); //初始化个体2
// int rand2[3];
// get_random_nums(rand2,3);
// father2->set_new_gene(rand2);
}
~tsp()
{//析构函数
delete father1;
delete father2;
}
void start_generate()
{//迭代总函数
srand(time(NULL)); //取随机数用
while(--generation_counts >= 0) //
{
//cout<<generation_counts<<endl;
get_best_fornow(); //获取当前种群最好个体
switch_part_genes(); //交换两个体的随机2个基因，开始和结束的0基因不参加交换
}
}
void get_best_fornow()
{//判断当前种群是否比已有的best个体更优，有则替换
individual *now_the_best;
if(father1->fitness > father2->fitness)
{//找到两个个体最优，并用指针指向它
now_the_best = father1;
}
else
{
now_the_best = father2;
}
if(now_the_best->fitness > this->best_fitness)
{//better one will replace the original best individual
for(int i=0;i<5;++i)
{
this->best_route[i] = now_the_best->gene[i];//替换基因
}
this->best_distance = now_the_best->distance; //替换distance
this->best_fitness = now_the_best->fitness; //替换fitness
}
}
void switch_part_genes()
{//switch 2 random genes in individual
int gene_place1[2];
int gene_place2[2];
get_random_nums(gene_place1,2);//生成1-3中2个不同随机数给place1
get_random_nums(gene_place2,2);//生成1-3中2个不同随机数给place2
//start to switch
swap_gene(gene_place1,gene_place2);//交换基因
father1->update_info();//更新个体信息
father2->update_info();
}
void swap_gene(int loc1[2],int loc2[2])
{ //loc1 is for father1;loc 2 for father 2
//用loc1中的2个father1基因位置来交换loc2中2个father2基因的位置
// cout<<loc1[0]<<" "<<loc1[1]<<endl;
// cout<<loc2[0]<<" "<<loc2[1]<<endl;
for(int i=0;i<2;++i)
{ //father1[i] <-> father2[i]
int temp_father1_gene = father1->gene[loc1[i]];
father1->gene[loc1[i]] = father2->gene[loc2[i]];
father2->gene[loc2[i]] = temp_father1_gene;
}
clear_conflict(father1);//交换后可能出现冲突 比如01220这种序列，需要处理冲突
clear_conflict(father2);
}
void clear_conflict(individual *ptr)
{
int mapping[4]={0,2,3,1};//mapping映射 0->0 1->2 2->3 3->1 //01220就会映射为01320
int has_Conf_loc = has_conflict(ptr);
while(has_Conf_loc)
{
switch(has_Conf_loc)
{//根据冲突位置用映射消除冲突
case 1:
ptr->gene[1] = mapping[ptr->gene[2]];
break;
case 2:
ptr->gene[1] = mapping[ptr->gene[3]];
break;
case 3:
ptr->gene[3] = mapping[ptr->gene[3]];
break;
}
has_Conf_loc = has_conflict(ptr);
}
return;
}
int has_conflict(individual *one)
{ //可能冲突位置只有123，0和4固定为城市0，只要1和2、1和3、2和3都不冲突，即基因不冲突
//不同返回值用于快速定位冲突位置
if(one->gene[1] == one->gene[2])
return 1;
if(one->gene[1] == one->gene[3])
return 2;
if(one->gene[2] == one->gene[3])
return 3;
return 0;
}
bool get_random_nums(int *nums,int size)
{//给nums数组生成size个不同随机数
if(size <= 0)
{
return false;
}
if(size == 1)
{
nums[0] = rand()%3+1;//range 1-3
return true;
}
//size >= 2;
for(int i=0;i<size;++i)
{//i is the target place
nums[i] = rand()%3+1;
for(int j=0;j<i;++j)
{//j seeking the same number
if(nums[i] == nums[j])
{
nums[i] = rand()%3+1;
j=-1;
}
}
}
return true;
}
void print_best_route()
{
cout<<"BEST ROUTE:";
for(int i=0;i<ROUTE_NUM;++i)
{
cout<<best_route[i]<<" ";
}
cout<<endl;
cout<<"DISTANCE:"<<this->best_distance<<endl;
cout<<"FITNESS:"<<this->best_fitness<<endl;
}
void load_city_distance()
{//从文件读取城市距离信息
char in_data[10];
ifstream in_stream;
in_stream.open("ds.txt",ios::in);
if(!in_stream.is_open())
return;
int j=0;
int k=0;
while(!in_stream.eof())
{
in_stream.getline(in_data,10);
for(int i=0;i<10;++i)
{
if(in_data[i]>= '0' && in_data[i] <= '9')
{
city_dis[j][k++] = in_data[i]-'0';
if(k==4)
{
k=0;
++j;
break;
}
}
}
}
in_stream.close();
}
};
int main()
{
tsp tsp_demo;
tsp_demo.start_generate();
tsp_demo.print_best_route();
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
附测试截图
ds.txt 文件内容
0 1 3 4
1 0 2 5
3 2 0 3
4 5 3 0
