【进化计算】遗传算法求解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 = 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完整代码
完整代码如下所示，由于每次运行都容易陷入局部最优，因此，代码中我对每次运行的结果和数据集提供的最优解进行比较，若需要接近最优解，调整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, "秒")本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2023-10-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
