遗传算法(GA) - 求解 - 旅行商问题(TSP)

#!/usr/bin/env python
# coding: utf-8from matplotlib import pyplot as plt
import numpy as np
import pandas as pd
import time# 生成城市坐标
def gen_city(filename, city_num):name = ["city's name"] * city_num  # 这个并没什么用，但是不要省，省了的话还要修改代码x = [np.random.randint(0, 100) for _ in range(city_num)]y = [np.random.randint(0, 100) for _ in range(city_num)]x[0] = 0y[0] = 0with open(filename, "w") as f:for i in range(city_num):name[i] = f'city{i}'f.write(name[i] + "," + str(x[i]) + "," + str(y[i]) + "\n")f.write(name[0] + "," + str(x[0]) + "," + str(y[0]) + "\n")  # 最后一个节点即为起点# 打印城市的坐标position = pd.read_csv("cities.csv", names=['ind', 'lat', 'lon'])plt.scatter(x=position['lon'], y=position['lat'])plt.show()position.head()def create_init_list(filename):data = pd.read_csv(filename, names=['index', 'lat', 'lon'])  # lat->纬度 lon->经度data_list = []for i in range(len(data)):data_list.append([float(data.iloc[i]['lon']), float(data.iloc[i]['lat'])])return data_listdef distance_matrix(coordinate_list, size):  # 生成距离矩阵，邻接矩阵d = np.zeros((size + 2, size + 2))for i in range(size + 1):x1 = coordinate_list[i][0]y1 = coordinate_list[i][1]for j in range(size + 1):if (i == j) or (d[i][j] != 0):continuex2 = coordinate_list[j][0]y2 = coordinate_list[j][1]distance = np.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)if (i == 0):  # 起点与终点是同一城市d[i][j] = d[j][i] = d[size + 1][j] = d[j][size + 1] = distanceelse:d[i][j] = d[j][i] = distancereturn ddef path_length(d_matrix, path_list, size):  # 计算路径长度length = 0for i in range(size + 1):length += d_matrix[path_list[i]][path_list[i + 1]]return lengthdef shuffle(my_list):  # 起点和终点不能打乱temp_list = my_list[1:-1]np.random.shuffle(temp_list)shuffle_list = my_list[:1] + temp_list + my_list[-1:]return shuffle_listdef product_len_probability(my_list, d_matrix, size, p_num):  # population, d, size,p_numlen_list = []  # 种群中每个个体（路径）的路径长度pro_list = []path_len_pro = []for path in my_list:len_list.append(path_length(d_matrix, path, size))max_len = max(len_list) + 1e-10gen_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)  # mask_list列表元素的和for i in range(p_num):if (i == 0):pro_list.append(mask_list[i] / sum_len)elif (i == p_num - 1):pro_list.append(1)else:pro_list.append(pro_list[i - 1] + mask_list[i] / sum_len)for i in range(p_num):# 路径列表 路径长度 概率path_len_pro.append([my_list[i], len_list[i], pro_list[i]])# 返回 最优路径 最优路径的长度 每条路径的概率return my_list[gen_best_length_index], gen_best_length, path_len_prodef choose_cross(population, p_num):  # 随机产生交配者的索引，越优的染色体被选择几率越大jump = np.random.random()  # 随机生成0-1之间的小数if jump < population[0][2]:return 0low = 1high = p_nummid = int((low + high) / 2)# 二分搜索# 如果jump在population[mid][2]和population[mid-1][2]之间，那么返回midwhile (low < high):if jump > population[mid][2]:low = midmid = (low + high) // 2elif jump < population[mid - 1][2]:  # 注意这里一定是mid-1high = midmid = (low + high) // 2else:return middef product_offspring(size, parent_1, parent_2, pm):  # 产生后代son = parent_1.copy()product_set = np.random.randint(1, size + 1)parent_cross_set = set(parent_2[1:product_set])  # 交叉序列集合cross_complete = 1for j in range(1, size + 1):if son[j] in parent_cross_set:son[j] = parent_2[cross_complete]cross_complete += 1if cross_complete > product_set:breakif np.random.random() < pm:  # 变异son = veriation(son, size, pm)return sondef veriation(my_list, size, pm):  # 变异，随机调换两城市位置ver_1 = np.random.randint(1, size + 1)ver_2 = np.random.randint(1, size + 1)while ver_2 == ver_1:  # 直到ver_2与ver_1不同ver_2 = np.random.randint(1, size + 1)my_list[ver_1], my_list[ver_2] = my_list[ver_2], my_list[ver_1]return my_listdef main(filepath, p_num, gen, pm):start = time.time()coordinate_list = create_init_list(filepath)size = len(coordinate_list) - 2  # 除去了起点和终点d = distance_matrix(coordinate_list, size)  # 各城市之间的邻接矩阵path_list = list(range(size + 2))  # 初始路径# 随机打乱初始路径以建立初始种群路径population = [shuffle(path_list) for i in range(p_num)]# 初始种群population以及它的最优路径和最短长度gen_best, gen_best_length, population = product_len_probability(population, d, size, p_num)# 现在的population中每一元素有三项，第一项是路径，第二项是长度，第三项是使用时转盘的概率son_list = [0] * p_num  # 后代列表best_path = gen_best  # 最好路径初始化best_path_length = gen_best_length  # 最好路径长度初始化every_gen_best = [gen_best_length]  # 每一代的最优值for i in range(gen):  # 迭代gen代son_num = 0while son_num < p_num:  # 循环产生后代，一组父母亲产生两个后代father_index = choose_cross(population, p_num)  # 获得父母索引mother_index = choose_cross(population, p_num)father = population[father_index][0]  # 获得父母的染色体mother = population[mother_index][0]son_list[son_num] = product_offspring(size, father, mother, pm)  # 产生后代加入到后代列表中son_num += 1if son_num == p_num:breakson_list[son_num] = product_offspring(size, mother, father, pm)  # 产生后代加入到后代列表中son_num += 1# 在新一代个体中找到最优路径和最优值gen_best, gen_best_length, population = product_len_probability(son_list, d, size, p_num)if (gen_best_length < best_path_length):  # 这一代的最优值比有史以来的最优值更优best_path = gen_bestbest_path_length = gen_best_lengthevery_gen_best.append(gen_best_length)end = time.time()print(f"迭代用时：{(end - start)}s")print("史上最优路径:", best_path, sep=" ")  # 史上最优路径print("史上最短路径长度:", best_path_length, sep=" ")  # 史上最优路径长度# 打印各代最优值和最优路径x = [coordinate_list[point][0] for point in best_path]  # 最优路径各节点经度y = [coordinate_list[point][1] for point in best_path]  # 最优路径各节点纬度plt.figure(figsize=(8, 10))plt.subplot(211)plt.plot(every_gen_best)  # 画每一代中最优路径的路径长度plt.subplot(212)plt.scatter(x, y)  # 画点plt.plot(x, y)  # 画点之间的连线plt.grid()  # 给画布添加网格plt.show()if __name__ == '__main__':city_num = 10  # 城市数量filepath = 'cities.csv'# gen_city(filepath, city_num)p_num = 100  # 种群个体数量gen = 1000  # 进化代数pm = 0.4  # 变异率main(filepath, p_num, gen, pm)