【启发式算法】Python实现遗传算法求解TSP问题_tsp启发式算法求解城市巡回路线csdn距离矩阵

遗传算法

算法相关参数

• 种群个体数量：p_num
• 进化代数：gen
• 变异率：pm
• 被选中的概率：mask_list[i]/sum_len（即当前距离差值/距离差值之和）

算法效果分析

1. 种群数量越多，迭代次数越多，搜索次数越多，程序运行越慢，相对来 得到的解更可信
2. 种群中个体的路径长度越短，被选中作为父代的概率越大，即优胜劣汰
3. 算法随机性体现在：父代的随机选取，孩子继承父母的基因序列长度随机（即单点交叉策略），一定概率进行变异，变异中随机选取基因进行交换

算法步骤

1. 数据初始化：计算距离矩阵（dist[i][j]表示i城市与j城市之间的距离）；随机得到初始解（起点为0城市）；编写距离计算函数；初始化第一代的种群
2. 求得当前代时种群中的最优解，并初始化子代矩阵
3. 遗传算法的核心：算法迭代gen次，每次产生p_num个子代。
   3.1 随机选择一对父母（路径越短，选中的概率越大），并选取父母各自一段基因序列进行遗传（基因即路径，长度随机生成）；
   3.2 第一个孩子继承母亲的部分基因序列
   3.3 随机生成概率，判断是否变异
   3.4 将孩子基因放入孩子序列，孩子的数量+1
   3.5 同理第二个孩子继承父亲的基因（见3.2~3.4）
   3.6 计算过所有p_num个子代后，找出当前代的最优解并与全局最优解比较
4. 直到迭代gen次，算法结束

# -*- coding: utf-8 -*-
import numpy as np
import random
import math
import matplotlib.pyplot as plt
import time

"""
Desicribe:遗传算法解TSP问题

"""

# 解决中文显示问题
plt.rcParams['font.sans-serif'] = ['KaiTi'] # 指定默认字体
plt.rcParams['axes.unicode_minus'] = False # 解决保存图像是负号'-'显示为方块的问题

# 原始数据
coordinates = np.array([[565.0, 575.0], [25.0, 185.0], [345.0, 750.0], [945.0, 685.0], [845.0, 655.0],
                        [880.0, 660.0], [25.0, 230.0], [525.0, 1000.0], [580.0, 1175.0], [650.0, 1130.0],
                        [1605.0, 620.0], [1220.0, 580.0], [1465.0, 200.0], [1530.0, 5.0], [845.0, 680.0],
                        [725.0, 370.0], [145.0, 665.0], [415.0, 635.0], [510.0, 875.0], [560.0, 365.0],
                        [300.0, 465.0], [520.0, 585.0], [480.0, 415.0], [835.0, 625.0], [975.0, 580.0],
                        [1215.0, 245.0], [1320.0, 315.0], [1250.0, 400.0], [660.0, 180.0], [410.0, 250.0],
                        [420.0, 555.0], [575.0, 665.0], [1150.0, 1160.0], [700.0, 580.0], [685.0, 595.0],
                        [685.0, 610.0], [770.0, 610.0], [795.0, 645.0], [720.0, 635.0], [760.0, 650.0],
                        [475.0, 960.0], [95.0, 260.0], [875.0, 920.0], [700.0, 500.0], [555.0, 815.0],
                        [830.0, 485.0], [1170.0, 65.0], [830.0, 610.0], [605.0, 625.0], [595.0, 360.0],
                        [1340.0, 725.0], [1740.0, 245.0]])
gl_num = coordinates.shape[0]  # 城市数目
coord_x = coordinates[:, 0]  # 城市横坐标
coord_y = coordinates[:, 1]  # 城市纵坐标
gl_dist = np.zeros((gl_num, gl_num))  # 距离矩阵
gl_route_origin = np.zeros(gl_num)  # 初始解
gl_sumDist_origin = 0.0  # 初始距离
# 遗传算法参数
p_num = 200  # 种群个体数量
gen = 2000  # 进化代数
pm = 0.1  # 变异率


def init():
    """
    初始化解，初始距离和距离矩阵
    :return:
    """
    global gl_dist
    global gl_route_origin
    global gl_sumDist_origin
    global gl_num
    for i in range(gl_num):
        x_i = coord_x[i]
        y_i = coord_y[i]
        for j in range(i, gl_num):
            x_j = coord_x[j]
            y_j = coord_y[j]
            gl_dist[i][j] = gl_dist[j][i] = math.sqrt((x_i - x_j) ** 2 + (y_i - y_j) ** 2)
    # 随机列表  固定起点终点,起点终点均为0
    gl_route_origin = list(range(0, gl_num))
    gl_route_origin = shuffle(gl_route_origin)
    gl_sumDist_origin = getDist(gl_route_origin)
    gl_num = len(gl_route_origin)
    print("路径上城市数:", gl_num)



def getDist(route):
    """
    计算距离,注意计算返回起点的路径长度
    :param route: 传递路径
    :return: 距离
    """
    dist = 0.0
    for i in range(0, gl_num - 1):
        dist += gl_dist[route[i]][route[i + 1]]
    dist += gl_dist[route[gl_num - 1]][0]
    return dist


def shuffle(my_list):
    """
    对可行解进行排列组合，除去起点
    :param my_list: 可行解
    :return:
    """
    temp_list = my_list[1:]  # 数据切片，左闭右开，获取除起点以外的所有元素
    np.random.shuffle(temp_list)
    shuffle_list = my_list[:1] + temp_list   # 切片的拼接
    return shuffle_list


def path_len_probability(my_list):
    """
    求解当前代中的最优解和概率
    :param my_list:种群
    :return:my_list[gen_best_length_index]当前种群中的最优路径
            gen_best_length当前种群中的最优解（最短距离）
            path_len_pro_list路径_距离_概率的集合
    """
    len_list = []  # 路径解长度列表
    pro_list = []  # 概率列表
    path_len_pro_list = []  # 路径_距离_概率
    for path in my_list:
        len_list.append(getDist(path))  # 对每个路径解求长度
    max_len = max(len_list) + 1e-10  # 最长距离
    gen_best_length = min(len_list)  # 最短距离，即当前最优解
    gen_best_length_index = len_list.index(gen_best_length)  # 最优解下标索引位置
    mask_list = np.ones(p_num) * max_len - np.array(len_list)  # 求解距离的最大值与当前距离之差
    sum_len = np.sum(mask_list)  # 对距离差值求和
    # print(gen_best_length)
    # print(gen_best_length_index)
    # print(sum_len)

    # 计算概率值(轮盘赌法),概率值的标准是路径距离越短，被选中的概率越高，即择优
    for i in range(p_num):
        if i == 0:  # 第一个概率
            pro_list.append(mask_list[i] / sum_len)  # 差值i/差值之和，路径越短，计算出的比值越大
        elif i == p_num - 1:  # 最后一个概率
            pro_list.append(1)  # 概率为1
        else:  # 中间的概率
            pro_list.append(pro_list[i - 1] + mask_list[i] / sum_len)  # i-1的概率 + 差值i / 差值之和
    for i in  range(p_num):
        path_len_pro_list.append([my_list[i], len_list[i], pro_list[i]])
    return my_list[gen_best_length_index], gen_best_length, path_len_pro_list


def choose_cross(population):
    """
    以一定概率选取parents进行交配函数
    jump:随机跳跃值
    通过二分搜索，找到随机跳跃值所在的概率范围，并返回对应索引下标
    :param population:
    :return:
    """
    jump = np.random.random()  # 生成(0,1)之间的随机数
    if jump < population[0][2]:  # population[0]的概率最小
        return 0
    # 二分搜索，high，low代表个体种群的下标
    low = 1
    high = p_num
    mid = int((low + high) / 2)
    while low < high:
        if jump > population[mid][2]:
            low = mid
            mid = int((low + high) / 2)
        elif jump < population[mid - 1][2]:
            high = mid
            mid = int((low + high) / 2)
        else:
            return mid


def variation(my_list):
    """
    变异函数
    :param my_list:
    :return:
    """
    ver1 = np.random.randint(1, gl_num - 1)
    ver2 = np.random.randint(1, gl_num - 1)
    # 如果随机产生数相同，则再次进行随机取数
    while ver2 == ver1:
        ver2 = np.random.randint(1, gl_num - 1)
    my_list[ver1], my_list[ver2] = my_list[ver2], my_list[ver1]
    return my_list


if __name__ == '__main__':
    start = time.time()

    init()
    print("初始解：", gl_route_origin)
    print("初始距离：", gl_sumDist_origin)
    population = [0] * p_num  # 初始化种群矩阵
    # 建立初始第一代的种群
    population[0] = gl_route_origin
    for i in range(1, p_num):
        population[i] = shuffle(gl_route_origin)

    # 建立初始化种群获得的最优路径和最优路径长度，并初始化son
    gen_best, gen_best_length, population = path_len_probability(population)
    # print(population)  #这个列表的每一项中有三项，第一项是路径，第二项是长度，第三项是使用时转盘的概率
    son_list = [0] * p_num  # 初始化子代矩阵，子代规模与父代规模相同
    best_path = gen_best  # 最优路径初始化
    best_path_length = gen_best_length  # 最优路径长度

    # 记录每一代中的最优解，便于画图
    every_gen_best = list()  # every_gen_best = []会有波浪线
    every_gen_best.append(gen_best_length)

    # 迭代gen代
    for i in range(gen):
        son_num = 0
        while son_num < p_num:  # 产生p_num数量的子代，杂交变异
            # choose_cross随机选择一对父母（双亲的下标）进行交配
            father_index = choose_cross(population)
            mother_index = choose_cross(population)
            # 获取双亲的基因即路径
            father = population[father_index][0]
            mother = population[mother_index][0]

            # 父母变成下一代的父母（孩子继承父母的基因）
            son1 = father.copy()
            son2 = mother.copy()
            # 随机数据product_set表示双亲将哪些基因传给孩子
            product_set = np.random.randint(1, gl_num)  # 随机生成要遗传的基因序列的长度
            # 父亲中的某一段基因和母亲中的某一段基因
            father_cross_set = set(father[1:product_set])  # 除去起点
            mother_cross_set = set(mother[1:product_set])
            # 第一个son继承母亲的基因
            cross_complete = 1
            for j in range(1, gl_num - 1):
                if son1[j] in mother_cross_set:
                    son1[j] = mother[cross_complete]  # 母亲的基因遗传给孩子
                    cross_complete += 1
                    if cross_complete > product_set:  # 遗传的基因个数超过基因序列，则跳出循环
                        break
            # 第一个son基因变异
            if np.random.random() < pm:
                son1 = variation(son1)
            son_list[son_num] = son1
            son_num += 1
            if son_num == p_num:
                break

            # 第二个孩子继承父亲基因
            cross_complete = 1
            for j in range(1, gl_num - 1):
                if son2[j] in father_cross_set:
                    son2[j] = father[cross_complete]
                    cross_complete += 1
                    if cross_complete > product_set:
                        break
            # 第二个son基因变异
            if np.random.random() < pm:
                son2 = variation(son2)
            son_list[son_num] = son2
            son_num += 1
        # 找最优解，当前代的最优解与全局最优解进行比较
        gen_best, gen_best_length, population = path_len_probability(son_list)
        if gen_best_length < best_path_length:
            best_path = gen_best
            best_path_length = gen_best_length
        every_gen_best.append(gen_best_length)
    end = time.time()

    x = []
    y = []
    for point in best_path:
        x.append(coordinates[point][0])
        y.append(coordinates[point][1])
    print(gen_best)  # 最后一代最优路径
    print(gen_best_length)  # 最后一代最优路径长度
    print(best_path)  # 最优路径
    print(best_path_length)  # 最优路径长度
    # 绘图
    plt.figure(1)
    plt.subplots_adjust(hspace=0.4, wspace=0.4)
    plt.subplot(211)
    plt.title("每代最短路径")
    plt.plot(every_gen_best)
    plt.subplot(212)
    plt.title("最优路径")
    plt.scatter(x, y)
    plt.plot(x, y)
    plt.grid()
    plt.show()

    print('Running time: %s Seconds' % (end - start))

"""
[0, 21, 29, 22, 20, 30, 17, 16, 2, 18, 40, 7, 8, 44, 31, 48, 36, 37, 33, 43, 45, 15, 28, 19, 49, 34, 35, 38, 39, 4, 5, 23, 47, 14, 3, 24, 42, 32, 50, 11, 10, 27, 26, 12, 51, 13, 25, 46, 41, 1, 6, 21, 0]
10112.612313214102
[0, 21, 19, 49, 28, 29, 22, 20, 30, 17, 16, 2, 18, 40, 7, 8, 44, 31, 48, 39, 36, 37, 23, 47, 45, 15, 43, 33, 34, 35, 38, 14, 5, 4, 24, 3, 42, 32, 50, 10, 11, 27, 26, 12, 51, 13, 25, 46, 41, 1, 6, 21, 0]
9600.890171898773
[0, 21, 22, 19, 49, 15, 28, 29, 20, 30, 17, 16, 2, 18, 40, 7, 8, 44, 31, 48, 35, 38, 37, 23, 47, 45, 43, 33, 34, 39, 36, 14, 5, 4, 24, 3, 42, 32, 50, 10, 11, 27, 26, 12, 51, 13, 25, 46, 41, 1, 6, 6, 0]
9494.64650869738
[0, 21, 22, 19, 49, 15, 28, 29, 20, 30, 17, 16, 2, 18, 40, 7, 8, 44, 31, 48, 35, 38, 36, 23, 47, 45, 43, 33, 34, 39, 37, 14, 5, 4, 24, 3, 42, 32, 50, 10, 11, 27, 26, 12, 51, 13, 25, 46, 41, 1, 6, 6, 0]
9449.437077391805
[0, 21, 22, 19, 49, 15, 28, 29, 20, 30, 17, 16, 2, 18, 40, 7, 8, 44, 31, 48, 35, 38, 36, 23, 47, 45, 43, 33, 34, 39, 37, 14, 4, 5, 24, 3, 42, 32, 50, 10, 11, 27, 26, 12, 51, 13, 25, 46, 41, 1, 6, 20, 0]
9416.094900698994
"""

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
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282