#用 GA 算法求解旅行商问题

#问题描述

旅行商问题(Travelling Salesman Problem, 简记 TSP, 亦称货郎担问题): 设有 34 个城市及其对应的经纬度坐标, 则问题是要找出遍访每个城市恰好一次的一条回路并使其路径长度为最短.

#算法设计

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群开始的,而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体,即多个基因的集合,其内部表现(即基因型)是某种基因组合,它决定了个体的形状的外部表现,如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此,在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂,我们往往进行简化,如二进制编码,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度大小选择个体,并借助于自然遗传学的遗传算子进行组合交叉和变异,产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码,可以作为问题近似最优解。[1]

#个体适应性

遗传算法中的适应性在旅行商问题中对应的是走过所有的点的距离之和,距离越小则所代表的适应性越强。

#DNA 编码

编码是应用遗传算法时要解决的首要问题,也是设计遗传算法时的一个关键步骤。编码方法影响到交叉算子、变异算子等遗传算子的运算方法,大很大程度上决定了遗传进化的效率。在旅行商问题中的 DNA 编码方式是二进制编码方式,具体是将坐标分别放入两条 DNA 中,形成xy两条 DNA,如下所示:

1
2
3
4
5
6
7
8
9
x:
[121.47 115.85 117.25 108.93 106.55 112.55 114.52 121.52 108.37 91.13
87.62 106.63 111.73 101.78 119.3 114.3 125.32 116.4 117.2 116.98
118.78 113.62 114.17 113.27 108.37 123.43 120.15 113.55 102.72 104.07
112.93 103.82 106.28 126.53]
y:
[31.23 28.68 31.83 34.27 29.57 37.87 38.05 25.03 22.82 29.65 43.82 26.65
40.83 36.62 26.08 30.6 43.9 39.9 39.12 36.67 32.07 34.75 22.28 23.13
22.82 41.8 30.28 22.19 25.05 30.67 28.23 36.07 38.47 45.8]

#适者生存 (selection)

通过个体适应性来挑选,适应性越高(即距离越小)就越可能被选到。

#交叉配对 (crossover)

在旅行商问题中,交叉配对不能通过简单的从父母的 DNA 中取一半来完成,这样会产生重复点。
替代办法是将父代的 DNA 中选取的点得到后按顺序放置到新 DNA 的前半部,然后再从母代的 DNA 中选取剩下的点,放到新 DNA 的后半部。

#变异 (mutation)

在旅行商问题中,变异只需要随机交换两个点的位置即可。

#程序流程

程序流程如图1所示

图 1 程序流程图

#核心伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 迭代N_GENERATIONS次
for generation in range(N_GENERATIONS):

# 将城市坐标转换为DNA
lx, ly = translateDNA(pop, CITIES)

# 计算个体适应性
fitness, total_distance = get_fitness(lx, ly)

# 适者生存
pop = select(fitness)
pop_copy = pop.copy()

# 对于种群中的每一个父母代
for parent in pop:

# 杂交
child = crossover(parent, pop_copy)

# 变异
child = mutate(child)

# 加入到新种群中
parent[:] = child

#代码运行及测试

选取的参数如表1所示.

参数表
参数名称 参数值
城市数量 34
城市坐标 附录:城市坐标
交叉概率 0.1
变异概率 0.02
种群规模 1000
迭代次数 500

代码运行结果如图2所示.

运行结果图

图 2 运行结果图

#结论

34 个城市的最终结果为16434.4730公里。
总得来说遗传算法解决旅行商问题是由连续问题归纳到组合问题的求解,使得精度受到很大的影响,最终结果有时也容易陷入到局部早熟而导致结果不理想,不过遗传算法还是具有较强的全局搜索能力,在计算精度要求较高时,对计算时间的花费较少。

#参考链接

#附录

#城市坐标

城市坐标表
序号 省份 经度 纬度
01 北京 116.4 39.9
02 天津 117.2 39.12
03 河北 114.52 38.05
04 山西 112.55 37.87
05 内蒙古 111.73 40.83
06 辽宁 123.43 41.8
07 吉林 125.32 43.9
08 黑龙江 126.53 45.8
09 上海 121.47 31.23
10 江苏 118.78 32.07
11 浙江 120.15 30.28
12 安徽 117.25 31.83
13 福建 119.3 26.08
14 江西 115.85 28.68
15 山东 116.98 36.67
16 河南 113.62 34.75
17 湖北 114.3 30.6
18 湖南 112.93 28.23
19 广东 113.27 23.13
20 广西 108.37 22.82
21 海南 108.37 22.82
22 重庆 106.55 29.57
23 四川 104.07 30.67
24 贵州 106.63 26.65
25 云南 102.72 25.05
26 西藏 91.13 29.65
27 陕西 108.93 34.27
28 甘肃 103.82 36.07
29 青海 101.78 36.62
30 宁夏 106.28 38.47
31 新疆 87.62 43.82
32 台北 121.52 25.03
33 香港 114.17 22.28
34 澳门 113.55 22.19

#遗传算法代码

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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# ----------model import----------

import numpy as np
import json
from math import radians, cos, sin, asin, sqrt

# ----------end model import----------


# ----------global variables----------

"""
@param:
CITIES the longitude and the latitude of cities
N_CITIES the number of cities
CROSS_RATE the rate of cross
MUTATE_RATE the rate of mutate
POP_SIZE the size of population
N_GENERATIONS the number of generations
"""

CITIES = np.array([[116.4, 39.9],
[117.2, 39.12],
[114.52, 38.05],
[112.55, 37.87],
[111.73, 40.83],
[123.43, 41.8],
[125.32, 43.9],
[126.53, 45.8],
[121.47, 31.23],
[118.78, 32.07],
[120.15, 30.28],
[117.25, 31.83],
[119.3, 26.08],
[115.85, 28.68],
[116.98, 36.67],
[113.62, 34.75],
[114.3, 30.6],
[112.93, 28.23],
[113.27, 23.13],
[108.37, 22.82],
[108.37, 22.82],
[106.55, 29.57],
[104.07, 30.67],
[106.63, 26.65],
[102.72, 25.05],
[91.13, 29.65],
[108.93, 34.27],
[103.82, 36.07],
[101.78, 36.62],
[106.28, 38.47],
[87.62, 43.82],
[121.52, 25.03],
[114.17, 22.28],
[113.55, 22.19]])
N_CITIES = CITIES.shape[0]
CROSS_RATE = 0.1
MUTATE_RATE = 0.02
POP_SIZE = 1000
N_GENERATIONS = 500

# ----------end global variables----------


# ----------function definition----------

"""
Calculate the great circle distance between two points
on the earth (specified in decimal degrees)
@param:
lon1 Longitude of the first point
lat1 Latitude of the first point
lon2 Longitude of the second point
lat2 Latitude of the second point
"""


def haversine(lon1, lat1, lon2, lat2):
lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])
dlon = lon2 - lon1
dlat = lat2 - lat1
a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2
c = 2 * asin(sqrt(a))
r = 6378.137
return c * r

# ----------end function definition----------


# ----------class definition----------

class GA(object):
def __init__(self, DNA_size, cross_rate, mutation_rate, pop_size, ):
self.DNA_size = DNA_size
self.cross_rate = cross_rate
self.mutate_rate = mutation_rate
self.pop_size = pop_size

self.pop = np.vstack([np.random.permutation(DNA_size)
for _ in range(pop_size)])

def translateDNA(self, DNA, city_position): # get cities' coord in order
line_x = np.empty_like(DNA, dtype=np.float64)
line_y = np.empty_like(DNA, dtype=np.float64)

for i, d in enumerate(DNA):

city_coord = city_position[d]
line_x[i, :] = city_coord[:, 0]
line_y[i, :] = city_coord[:, 1]
return line_x, line_y

def get_fitness(self, line_x, line_y):
total_distance = np.zeros((line_x.shape[0],), dtype=np.float64)
for i in range(line_x.shape[0]):
for j in range(line_x.shape[1]-1):
total_distance[i] += haversine(line_x[i][j],
line_y[i][j], line_x[i][j+1], line_y[i][j+1])
total_distance[i] += haversine(line_x[i][0], line_y[i][0],
line_x[i][line_x.shape[1]-1], line_y[i][line_x.shape[1]-1])

fitness = np.exp(self.DNA_size * 20000 / total_distance)

return fitness, total_distance

def select(self, fitness):
idx = np.random.choice(np.arange(
self.pop_size), size=self.pop_size, replace=True, p=fitness / fitness.sum())
return self.pop[idx]

def crossover(self, parent, pop):
if np.random.rand() < self.cross_rate:
# select another individual from pop
i_ = np.random.randint(0, self.pop_size, size=1)
# choose crossover points
cross_points = np.random.randint(
0, 2, self.DNA_size).astype(np.bool)
# find the city number
keep_city = parent[~cross_points]
swap_city = pop[i_, np.in1d(
pop[i_].ravel(), keep_city, invert=True)]
parent[:] = np.concatenate((keep_city, swap_city))
return parent

def mutate(self, child):
for point in range(self.DNA_size):
if np.random.rand() < self.mutate_rate:
swap_point = np.random.randint(0, self.DNA_size)
swapA, swapB = child[point], child[swap_point]
child[point], child[swap_point] = swapB, swapA
return child

def evolve(self, fitness):
pop = self.select(fitness)
pop_copy = pop.copy()
# for every parent
for parent in pop:
child = self.crossover(parent, pop_copy)
child = self.mutate(child)
parent[:] = child
self.pop = pop

# ----------end class definition----------


# ----------main function----------

if __name__ == "__main__":
ga = GA(DNA_size=N_CITIES, cross_rate=CROSS_RATE,
mutation_rate=MUTATE_RATE, pop_size=POP_SIZE)

path_list = []
for generation in range(N_GENERATIONS):
lx, ly = ga.translateDNA(ga.pop, CITIES)
fitness, total_distance = ga.get_fitness(lx, ly)
ga.evolve(fitness)
best_idx = np.argmax(fitness)
print('Gen:', generation, '| total distance: %.4f' %
total_distance[best_idx],)

path_x = np.array(list(lx[best_idx]) + [lx[best_idx][0]])
path_y = np.array(list(ly[best_idx]) + [ly[best_idx][0]])
path = np.stack((path_x, path_y))
path = path.transpose(1, 0)
path_list.append(path.tolist())

f = open('data.json', 'w')
f.write(json.dumps(path_list))
f.close()

# ----------end main function----------

#相关链接


  1. 遗传算法_百度百科 ↩︎