【进化计算】遗传算法求解gr48数据集

本文是研究生课程《进化计算》的作业题，和我之前的博文遗传算法求解TSP问题基本类似，在数据加载部分略有区别，这里留作备份。

数据集简介

数据集选用TspLIB中的gr48。
数据集下载：https://github.com/zstar1003/Dataset

注：数据集中包含每一组的最优解和最优解城市编码。

目前最优距离解：

rand50 : 5553
rand75 : 7054
rand100 : 7891
rand200 : 10649
rand300 : 11865
rand400 : 14722
rand400b : 144595
a280 : 2579 
ali535 : 202339 
att48 : 33522 
att532 : 86729 
bayg29 : 1610 
bays29 : 2020 
berlin52 : 7542 
bier127 : 118282 
brazil58 : 25395 
brd14051 : 469385 
brg180 : 1950 
burma14 : 3323
chn31 : 15377 
ch130 : 6110 
ch150 : 6528 
d198 : 15780 
d493 : 35002 
d657 : 48912 
d1291 : 50801 
d1655 : 62128 
d2103 : 80450 
d15112 : 1573084 
d18512 : 645238
dantzig42 : 699 
dsj1000 : 18659688
dsj1000 : 18660188
eil51 : 426 
eil76 : 538 
eil101 : 629 
fl417 : 11861 
fl1400 : 20127 
fl1577 : 22249 
fl3795 : 28772 
fnl4461 : 182566 
fri26 : 937 
gil262 : 2378 
gr17 : 2085 
gr21 : 2707 
gr24 : 1272 
gr48 : 5046 
gr96 : 55209 
gr120 : 6942 
gr137 : 69853 
gr202 : 40160 
gr229 : 134602 
gr431 : 171414 
gr666 : 294358 
hk48 : 11461 
kroA100 : 21282 
kroB100 : 22141 
kroC100 : 20749 
kroD100 : 21294 
kroE100 : 22068 
kroA150 : 26524 
kroB150 : 26130 
kroA200 : 29368 
kroB200 : 29437 
lin105 : 14379 
lin318 : 42029 
linhp318 : 41345 
nrw1379 : 56638 
oliver30 : 420
p654 : 34643 
pa561 : 2763 
pcb442 : 50778 
pcb1173 : 56892 
pcb3038 : 137694 
pla7397 : 23260728 
pla33810 : 66048945 
pla85900 : 142382641 
pr76 : 108159 
pr107 : 44303 
pr124 : 59030 
pr136 : 96772 
pr144 : 58537 
pr152 : 73682 
pr226 : 80369 
pr264 : 49135 
pr299 : 48191 
pr439 : 107217 
pr1002 : 259045 
pr2392 : 378032 
rat99 : 1211 
rat195 : 2323 
rat575 : 6773 
rat783 : 8806 
rd100 : 7910 
rd400 : 15281 
rl1304 : 252948 
rl1323 : 270199 
rl1889 : 316536 
rl5915 : 565530 
rl5934 : 556045 
rl11849 : 923288 
si175 : 21407 
si535 : 48450 
si1032 : 92650 
st70 : 675 
swiss42 : 1273 
ts225 : 126643 
tsp225 : 3916 
u159 : 42080 
u574 : 36905 
u724 : 41910 
u1060 : 224094 
u1432 : 152970 
u1817 : 57201 
u2152 : 64253 
u2319 : 234256 
ulysses16 : 72
ulysses22 : 74 
usa13509 : 19982859 
vm1084 : 239297 
vm1748 : 336556 
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

数据集读取

数据集为城市距离的下三角矩阵，0表示对角线上的数据。

读取思路是先根据换行符进行换行，然后根据0的位置对距离矩阵相应位置进行填充，读取代码如下：

def load_data(cityNum, file_path):
    with open(file_path, 'r', encoding='utf-8') as f:
        context = f.read()
        # print(context)
        # 根据换行进行分隔
        row_list = context.splitlines()
        data_list = []
        for row in row_list:
            for i in row.strip().split(" "):
                data_list.append(int(i))
    distance = np.zeros([cityNum, cityNum])
    # 遍历data[]，填入distance[][]
    p = 0
    for i in range(cityNum):
        for j in range(cityNum):
            distance[i][j] = data_list[p]
            distance[j][i] = data_list[p]
            p += 1
            # 每行读到"0"跳出列循环，到下一行
            if data_list[p - 1] == 0:
                break
    return distance
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

完整代码

完整代码如下所示，由于每次运行都容易陷入局部最优，因此，代码中我对每次运行的结果和数据集提供的最优解进行比较，若需要接近最优解，调整random.seed即可。

import time
import numpy as np
import matplotlib.pyplot as plt

plt.rcParams['font.sans-serif'] = ["SimHei"]

# 载入数据
def load_data(cityNum, file_path):
    with open(file_path, 'r', encoding='utf-8') as f:
        context = f.read()
        # print(context)
        # 根据换行进行分隔
        row_list = context.splitlines()
        data_list = []
        for row in row_list:
            for i in row.strip().split(" "):
                data_list.append(int(i))
    distance = np.zeros([cityNum, cityNum])
    # 遍历data[]，填入distance[][]
    p = 0
    for i in range(cityNum):
        for j in range(cityNum):
            distance[i][j] = data_list[p]
            distance[j][i] = data_list[p]
            p += 1
            # 每行读到"0"跳出列循环，到下一行
            if data_list[p - 1] == 0:
                break
    return distance

# 初始化种群
def rand_pop(city_num, pop_num, pop, distance, matrix_distance):
    rand_ch = np.array(range(city_num))
    for i in range(pop_num):
        np.random.shuffle(rand_ch)
        pop[i, :] = rand_ch
        distance[i] = comp_dis(city_num, matrix_distance, rand_ch)  # 这里的适应度其实是距离

# 计算每个个体的总距离
def comp_dis(city_num, matrix_distance, one_path):
    res = 0
    for i in range(city_num - 1):
        res += matrix_distance[one_path[i], one_path[i + 1]]
    res += matrix_distance[one_path[-1], one_path[0]]  # 最后一个城市和第一个城市的距离，需单独处理
    return res

# 打印最优城市编码
def print_path(city_num, one_path):
    bm = [str(one_path[0] + 1)]
    for i in range(1, city_num):
        bm.append(str(one_path[i] + 1))
    print("最优解城市编码为：")
    print(bm)

# 轮盘赌的方式选择子代
def select_sub(pop_num, pop, distance):
    fit = 1. / distance  # 适应度函数
    p = fit / sum(fit)
    q = p.cumsum()  # 累积概率
    select_id = []
    for i in range(pop_num):
        r = np.random.rand()  # 产生一个[0,1)的随机数
        for j in range(pop_num):
            if r < q[0]:
                select_id.append(0)
                break
            elif q[j] < r <= q[j + 1]:
                select_id.append(j + 1)
                break
    next_gen = pop[select_id, :]
    return next_gen

# 交叉操作-每个个体对的某一位置进行交叉
def cross_sub(city_num, pop_num, next_gen, cross_prob, evbest_path):
    for i in range(0, pop_num):
        best_gen = evbest_path.copy()
        if cross_prob >= np.random.rand():
            next_gen[i, :], best_gen = intercross(city_num, next_gen[i, :], best_gen)

# 具体的交叉方式：部分映射交叉(Partial-Mapped Crossover)
def intercross(city_num, ind_a, ind_b):
    r1 = np.random.randint(city_num)
    r2 = np.random.randint(city_num)
    while r2 == r1:
        r2 = np.random.randint(city_num)
    left, right = min(r1, r2), max(r1, r2)
    ind_a1 = ind_a.copy()
    ind_b1 = ind_b.copy()
    for i in range(left, right + 1):
        ind_a2 = ind_a.copy()
        ind_b2 = ind_b.copy()
        ind_a[i] = ind_b1[i]
        ind_b[i] = ind_a1[i]
        # 每个个体包含的城市序号是唯一的，因此交叉时若两个不相同，就会产生冲突
        x = np.argwhere(ind_a == ind_a[i])
        y = np.argwhere(ind_b == ind_b[i])
        # 产生冲突，将不是交叉区间的数据换成换出去的原数值，保证城市序号唯一
        if len(x) == 2:
            ind_a[x[x != i]] = ind_a2[i]
        if len(y) == 2:
            ind_b[y[y != i]] = ind_b2[i]
    return ind_a, ind_b

# 变异方式：翻转变异
def mutation_sub(city_num, pop_num, next_gen, mut_prob):
    for i in range(pop_num):
        if mut_prob >= np.random.rand():
            r1 = np.random.randint(city_num)
            r2 = np.random.randint(city_num)
            while r2 == r1:
                r2 = np.random.randint(city_num)
            if r1 > r2:
                temp = r1
                r1 = r2
                r2 = temp
            next_gen[i, r1:r2] = next_gen[i, r1:r2][::-1]

# 局部搜索:随机找两个点位交换
def local_search(city_num, pop_num, next_gen):
    for i in range(pop_num):
        r1 = np.random.randint(city_num)
        r2 = np.random.randint(city_num)
        while r2 == r1:
            r2 = np.random.randint(city_num)
        if r1 > r2:
            temp = next_gen[i, r1]
            next_gen[i, r1] = next_gen[i, r2]
            next_gen[i, r2] = temp

def main(seed):
    np.random.seed(seed)
    # 加载距离矩阵
    city_num = 48
    file_path = 'dataset/gr48.txt'
    matrix_distance = load_data(city_num, file_path)

    pop_num = 1000  # 群体个数
    cross_prob = 0.99  # 交叉概率
    mut_prob = 0.99  # 变异概率
    iteration = 100000  # 迭代代数

    # 初始化初代种群和距离，个体为整数，距离为浮点数
    pop = np.array([0] * pop_num * city_num).reshape(pop_num, city_num)
    distance = np.zeros(pop_num)
    # 初始化种群
    rand_pop(city_num, pop_num, pop, distance, matrix_distance)
    evbest_path = pop[0]
    evbest_distance = float("inf")
    best_path_list = []
    best_distance_list = []

    answer = ['10', '12', '31', '5', '33', '8', '22', '21', '17', '27', '32', '9', '14', '6', '26', '36', '11', '16', '48', '13', '1', '29', '7', '28', '44', '41', '46', '18', '34', '23', '25', '3', '19', '4', '30', '38', '20', '35', '42', '39', '40', '2', '45', '43', '47', '37', '24', '15']

    # 循环迭代遗传过程
    for i in range(iteration):
        # 选择
        next_gen = select_sub(pop_num, pop, distance)
        # 交叉
        cross_sub(city_num, pop_num, next_gen, cross_prob, evbest_path)
        # 变异
        mutation_sub(city_num, pop_num, next_gen, mut_prob)
        # 局部搜索(在每个个体附近领域寻找局部最优解)
        local_search(city_num, pop_num, next_gen)

        # 计算每个个体适应度
        for j in range(pop_num):
            distance[j] = comp_dis(city_num, matrix_distance, next_gen[j, :])
        index = distance.argmin()  # index 记录最小总路程

        # 为了防止曲线波动，每次记录最优值，如迭代后出现退化，则将当前最好的个体回退替换为历史最佳
        if distance[index] <= evbest_distance:
            evbest_distance = distance[index]
            evbest_path = next_gen[index, :]
        else:
            distance[index] = evbest_distance
            next_gen[index, :] = evbest_path

        # 存储每一步的最优路径(个体)及距离
        best_path_list.append(evbest_path)
        best_distance_list.append(evbest_distance)

        if i % 1000 == 0:
            print(i, "最佳距离为:", evbest_distance)

    best_path = evbest_path
    best_distance = evbest_distance

    # 指定10为起始点
    start_point = 10
    split_index = int(np.argwhere(best_path == start_point - 1))
    best_path = np.hstack((best_path[split_index:], (best_path[:split_index])))

    # 迭代完成，打印出最佳路径
    print_path(city_num, best_path)
    output_path = [i+1 for i in best_path]
    answer_right = 0
    for i, j in enumerate(output_path):
        if j == int(answer[i]):
            answer_right += 1
    print("准确的个数为", answer_right)
    print("当前最佳距离为:", best_distance)


if __name__ == '__main__':
    seed = 68
    print("编程语言：Python")
    start_time = time.time()
    main(seed)
    print("算法运行时间：", time.time() - start_time, "秒")
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