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

算法求解gr48数据集"/>

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

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

数据集简介

数据集选用TspLIB中的gr48。
数据集下载：

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

目前最优距离解：

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 

数据集读取

数据集为城市距离的下三角矩阵，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 = 0for 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:breakreturn distance

完整代码

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

import time
import numpy as np
import matplotlib.pyplot as pltplt.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 = 0for 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:breakreturn 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_chdistance[i] = comp_dis(city_num, matrix_distance, rand_ch)  # 这里的适应度其实是距离# 计算每个个体的总距离
def comp_dis(city_num, matrix_distance, one_path):res = 0for 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)breakelif q[j] < r <= q[j + 1]:select_id.append(j + 1)breaknext_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 = r1r1 = r2r2 = tempnext_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] = tempdef main(seed):np.random.seed(seed)# 加载距离矩阵city_num = 48file_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_distancenext_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_pathbest_distance = evbest_distance# 指定10为起始点start_point = 10split_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 = 0for i, j in enumerate(output_path):if j == int(answer[i]):answer_right += 1print("准确的个数为", answer_right)print("当前最佳距离为:", best_distance)if __name__ == '__main__':seed = 68print("编程语言：Python")start_time = time.time()main(seed)print("算法运行时间：", time.time() - start_time, "秒")