算法求解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, "秒")
更多推荐
【进化计算】遗传算法求解gr48数据集
发布评论