首页 / 算法 / 遗传算法解决旅行商问题GA_TSP
遗传算法解决旅行商问题GA_TSP
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了遗传算法解决旅行商问题GA_TSP，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含9501字，纯文字阅读大概需要14分钟。
内容图文
心血来潮把GA_TSP问题用C++封装起来搞了一遍，期间真是收益不小。
主要是用STL中的vector和list，结构体赋值中遇到了一些难点，原谅我自己是一棵白菜。
选择方法：用种群前面最优的20%代替后面的20%进行淘汰(当然这个比例可以自己拟定，修改代码中得pm_即可)。
变异方法：交换一个路径上随机产生的两个城市。
交叉方法：三交换启发交叉(THGA)。
genticTsp.h 代码如下：
1
#ifndef GENTIC_TSP_H_
2
#define GENTIC_TSP_H_
3 #include <iostream>
4 #include <vector>
5 #include <string>
6#define CITIES 99
7#define UNITS 50
8#define MAX_GEN 15
91011struct city{
12int id;
13int x;
14int y;
15};
1617struct unit{
18double length;
19 std::vector<int> path;
20booloperator<(conststruct unit &other) const21 {
22return length < other.length;
23 }
24};
252627class GenticTSP{
28public:
29 GenticTSP();
30void initMatrix(const std::string &filename);//file to matrix31void initGroup();//shuffle a group32double lenOfUnit(unit &p);//
33int searchCity(unit &, int id);//search a city‘s id for cross34void selectGroup();
35void crossUnits(unit &p, unit &q, unit &r);
36void mutateGroup();
37void evoluteGroup();
38void printBestUnit();
39 ~GenticTSP();
40private:
41 unit bestUnit_;
42double pm_;// mutate probability43double ps_;//save probability4445};
4647#endif /*GENTIC_TSP_H_*/
genticTsp.cpp代码如下：
1 #include "GenticTSP.h" 2 #include <iostream>
3 #include <fstream>
4 #include <string>
5 #include <vector>
6 #include <list>
7 #include <algorithm>
8 #include <math.h>
9 #include <time.h>
10 #include <string.h>
11 12usingnamespace std;
13 14city cities[CITIES];
15unit group[UNITS];
16double cityMatrix[CITIES][CITIES];
17 18GenticTSP::GenticTSP()
19 :pm_(0.2), ps_(0.8)
20{
21 22}
23 24 GenticTSP::~GenticTSP()
25{
26 27}
28 29void GenticTSP::initMatrix(conststring &filename)
30{
31int i, j;
32 ifstream in(filename);
33for(i = 0; i < CITIES; ++i)
34 {
35 36in >> cities[i].id >> cities[i].x >> cities[i].y;
37 }
38 39for(i = 0; i < CITIES; ++i)
40 {
41 cityMatrix[i][i] = 0;
42for(j = i + 1; j < CITIES; ++j)
43 {
44 cityMatrix[i][j] = sqrt((cities[i].x - cities[j].x) * (cities[i].x - cities[j].x) + (cities[i].y - cities[j].y) * (cities[i].y - cities[j].y));
45 cityMatrix[j][i] = cityMatrix[i][j];
46 }
47 48 }
49}
50 51 52//calculate the path-lenght of each path 53double GenticTSP::lenOfUnit(unit &unit)
54{
55 unit.length = 0;
56for(int j = 0; j < CITIES - 1; ++j)
57 {
58 unit.length += cityMatrix[unit.path[j]][unit.path[j + 1]];
59 }
60 61//回到起始城市 62 unit.length += cityMatrix[unit.path[0] ][unit.path[CITIES - 1] ];
63 64return unit.length;
65}
66 67 68//init group of various paths 69void GenticTSP::initGroup()
70{
71 vector<int> tmp;
72for(int i = 0; i < CITIES; ++i)
73 tmp.push_back(i);
74 75for(int i = 0; i < UNITS; ++i)
76 {
77 random_shuffle(tmp.begin(),tmp.end());
78 group[i].path = tmp;
79 group[i].length = lenOfUnit(group[i]);
80 }
81}
82 83//for test 84void printlist(list<int> &path)
85{
86for(list<int>::iterator it = path.begin(); it != path.end(); ++it){
87 cout << *it << "";
88 }
89 cout << endl;
90}
91 92void rightRotateList(list<int> &path, list<int>::iterator ptr, list<int>::iterator res)
93{
94 path.insert(ptr, res, path.end());
95 path.erase(res, path.end());
96}
97 98 99void GenticTSP::selectGroup()
100{
101int selected = UNITS * ps_;
102int non_selected = UNITS - selected; //防止取整丢失，所以直接采用减去selected103for(int i = 0; i < UNITS; ++i)
104 {
105 group[i].length = lenOfUnit(group[i]);
106 }
107 sort(group, group + UNITS);
108109/*群体规模保持不变
110 *被淘汰的个体数目为non_selected
111 *用被选择的前non_seleted个个体替代之
112*/113for(int i = 0; i < non_selected; ++i)
114 {
115 group[UNITS-1-i].path = group[i].path;
116 group[UNITS-1-i].length = group[i].length;
117118/* WARNING:
119 * error:memcpy(&group[UNITS-1-i], &group[i], sizeof(unit));
120 * 不能用memcpy
121 * 因为unit是自定义的结构体
122 * 其中的vector类型也不是原生的数据类型
123 * 如若使用，需要自定义构造函数
124*/125 }
126}
127128129void GenticTSP::evoluteGroup()
130{
131for(int i = 0; i < MAX_GEN; ++i)
132 {
133 selectGroup();
134135for(int j = 0; j < UNITS-2;)
136 {
137 crossUnits(group[j], group[j+1], group[j+2]);
138 j += 2;
139 }
140141 mutateGroup();
142 }
143144}
145146147void GenticTSP::mutateGroup()
148{
149 srand(time(NULL));
150int num;
151int pos1, pos2;
152int tmp;
153int sum = UNITS * pm_; //变异的总数= 群体数 * 变异概率154while(sum--)
155 {
156//随机选取一个发生变异的unit157 num = rand() % UNITS;
158//随机选取两个path上变异的城市，采用交换两个城市的方法进行变异159 pos1 = rand() % CITIES;
160 pos2 = rand() % CITIES;
161162//如果相同则不能算是变异，这里用while确保变异163while(pos1 == pos2)
164 pos2 = rand() % CITIES;
165166 tmp = group[num].path[pos1];
167 group[num].path[pos1] = group[num].path[pos2];
168 group[num].path[pos2] = tmp;
169170//更新该变异后path的长度171 lenOfUnit(group[num]);
172 }
173}
174175176177178void GenticTSP::crossUnits(unit &u1, unit &u2, unit &u3)
179{
180//将路径存储在list类型的容器中便于后面的插入操作181 list<int> path1(u1.path.begin(), u1.path.end());
182 list<int> path2(u2.path.begin(), u2.path.end());
183 list<int> path3(u3.path.begin(), u3.path.end());
184//随机产生起始城市的id， 并将位置默认为第一个位置185 srand((int)time(0));
186int cityID = rand() % CITIES;
187 list<int>::iterator res1, res2, res3;
188 res1 = find(path1.begin(), path1.end(), cityID);
189 res2 = find(path2.begin(), path2.end(), cityID);
190 res3 = find(path3.begin(), path3.end(), cityID);
191if(res1 == path1.end() || res2 == path2.end() || res3 == path3.end())
192 {
193 cout << "city not found" << endl;
194 }
195196//将以随机选取的城市及其后面的城市右旋到序列首部197 rightRotateList(path1, path1.begin(), res1);
198 rightRotateList(path2, path2.begin(), res2);
199 rightRotateList(path3, path3.begin(), res3);
200201 list<int>::iterator ptr1, ptr2, ptr3;
202 ptr1 = path1.begin();
203 ptr2 = path2.begin();
204 ptr3 = path3.begin();
205206/*CITIES个城市
207 *第一个城市在循环体外已经确定
208 *循环体内只要再执行CITIES - 2 次即可
209 *因为当执行倒数第二次后，最后一个也就是仅剩的一个也无需再循环了
210*/211for(int k = 1; k < CITIES-1; ++k)
212 {
213// cout << "______" << k<< "______" << endl;214int h1 = *ptr1;
215double len1 = cityMatrix[h1][*(++ptr1)];
216int h2 = *ptr2;
217double len2 = cityMatrix[h2][*(++ptr2)];
218int h3 = *ptr3;
219double len3 = cityMatrix[h3][*(++ptr3)];
220221//找出前两个城市距离最小的那个path中得第一个城市的编号222double len = (len1 <= len2) ? len1 : len2;
223 len = (len < len3) ? len : len3;
224if(len == len1){
225 cityID = *ptr1;
226 }elseif(len == len2){
227 cityID = *ptr2;
228 }else{
229 cityID = *ptr3;
230 }
231232//与当前城市距离最小的下一个城市编号为cityID233 res1 = find(ptr1, path1.end(), cityID);
234 res2 = find(ptr2, path2.end(), cityID);
235 res3 = find(ptr3, path3.end(), cityID);
236if(res1 == path1.end() || res2 == path2.end() || res3 == path3.end())
237 {
238 cout << "city not found in loop" << endl;
239 }
240 rightRotateList(path1, ptr1, res1);
241 rightRotateList(path2, ptr2, res2);
242 rightRotateList(path3, ptr3, res3);
243244//指针失效，需要重新定位245 ptr1 = find(path1.begin(), path1.end(), cityID);
246 ptr2 = find(path2.begin(), path2.end(), cityID);
247 ptr3 = find(path3.begin(), path3.end(), cityID);
248 }
249250251/*为了避免三个路径相同，所以这里在不改变路径的情况下替换起点城市，有利于接下来的交叉*/252 cityID = (rand() % CITIES);
253 res2 = find(path2.begin(), path2.end(), cityID);
254 rightRotateList(path2, path2.begin(), res2);
255256 cityID = (rand() % CITIES);
257 res3 = find(path3.begin(), path3.end(), cityID);
258 rightRotateList(path3, path3.begin(), res3);
259260//交叉完之后再赋值给vector类型261 u1.path.assign(path1.begin(), path1.end());
262 u2.path.assign(path2.begin(), path2.end());
263 u3.path.assign(path3.begin(), path3.end());
264}
265266267//print top5 paths with length268void GenticTSP::printBestUnit()
269{
270for(int i = 0; i < 5; ++i)
271 {
272 cout << "Path" << i << ": ";
273for(vector<int>::iterator it = group[i].path.begin(); it != group[i].path.end(); ++it){
274 cout << *it << "";
275 }
276 cout << endl << "length: " << group[i].length << endl;
277 }
278 }
maintest.cpp
1 #include <iostream>
2 #include <string>
3 #include <vector>
4 #include <fstream>
5 #include "GenticTSP.h" 6usingnamespace std;
7 8 9int main(int argc, constchar *argv[])
10{
11 GenticTSP genticTsp;
12 genticTsp.initMatrix("city.txt");
13 genticTsp.initGroup();
14 genticTsp.evoluteGroup();
15 genticTsp.selectGroup(); //进化后需要再一次选择，从而排序出最优序列16 genticTsp.printBestUnit ();
1718return0;
19 }
city.txt
1
6
4
2
15
15
3
24
18
4
33
12
5
48
12
6
57
14
7
67
10
8
77
10
9
86
15
10
6
21
11
17
26
12
23
25
13
32
35
14
43
23
15
55
35
16
65
36
17
78
39
18
87
35
19
3
53
20
12
44
21
28
53
22
33
49
23
47
46
24
55
52
25
64
50
26
71
57
27
87
57
28
4
72
29
15
78
30
22
70
31
34
71
32
42
79
33
54
77
34
66
79
35
78
67
36
87
73
37
7
81
38
17
95
39
26
98
40
32
97
41
43
88
42
57
89
43
64
85
44
78
83
45
83
98
46
5
109
47
13
111
48
25
102
49
38
119
50
46
107
51
58
110
52
67
110
53
74
113
54
88
110
55
2
124
56
17
134
57
23
129
58
36
131
59
42
137
60
53
123
61
63
135
62
72
134
63
87
129
64
2
146
65
16
147
66
25
153
67
38
155
68
42
158
69
57
154
70
66
151
71
73
151
72
86
149
73
5
177
74
13
162
75
25
169
76
35
177
77
46
172
78
54
166
79
65
174
80
73
161
81
86
162
82
2
195
83
14
196
84
28
189
85
38
187
86
46
195
87
57
194
88
63
188
89
77
193
90
85
194
91
8
211
92
12
217
93
22
210
94
34
216
95
47
203
96
58
213
97
66
206
98
78
210
99
85
204
用的city.txt这里的数据，据说最优路径代价是1100+，可是我用我的选择，变异，交叉方法目前来看最小代价只能达到1500+。
原文：http://www.cnblogs.com/beatrice7/p/4142568.html
内容总结
以上是互联网集市为您收集整理的遗传算法解决旅行商问题GA_TSP全部内容，希望文章能够帮你解决遗传算法解决旅行商问题GA_TSP所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】