基于改进大洪水算法求解TSP问题

article/2025/9/18 14:20:12

from function import get_distances, get_value, result_plot, get_neighbors
from random import randintdef r_opt(route):"""利用2-opt算法对route进行改进,对当前路径所有不相邻的两点进行边边交换"""new_route = route[:]value = get_value(new_route, distances)for k1 in range(city_number):for k2 in range(k1 + 1, city_number):new_route = route[:]for j in range(city_number):if k1 < j <= k2:new_route[j] = route[k1 + k2 - j + 1]new_value = get_value(new_route, distances)if new_value < value:route = new_route[:]value = new_valuereturn route, valueif __name__ == '__main__':# 算法参数N = 1000  # 迭代次数nb = 5  # 邻居城市个数# 城市坐标数据,城市序号为0,1，2,3...city_coordinates = [(41, 94), (37, 84), (54, 67), (25, 62), (7, 64), (2, 99), (68, 58), (71, 44), (54, 62),(83, 69),(64, 60), (18, 54), (22, 60), (83, 46), (91, 38), (25, 38), (24, 42), (58, 69), (71, 71),(74, 78),(87, 76), (18, 40), (13, 40), (82, 7), (62, 32), (58, 35), (45, 21), (41, 26), (4, 35), (4, 50)]city_number = len(city_coordinates)  # 城市数量distances = get_distances(city_coordinates)# 计算每个城市的邻居城市neighbors = get_neighbors(city_number, distances)# 随机生成初始解path = list(range(city_number))value = get_value(path, distances)water_level = valuebest_value = value  # 较大的初始值，存储最优解best_path = path[:]  # 存储最优路径# 进行迭代iterate_result = []for n in range(N):print(f"当前迭代次数为：{n},最优值为：{best_value}")# 使用2-opt算法对当前路径进行改进path, value = r_opt(path)# 进行城市子排列反序for k in range(nb):for i in range(city_number):city = neighbors[i][k]  # 距离城市i第k近的城市# 对城市i与城市city进行边边交换，生成新的路径index1 = path.index(i)index2 = path.index(city)index1, index2 = min(index1, index2), max(index1, index2)new_path = path[:]for j in range(city_number):if index1 < j <= index2:new_path[j] = path[index1 + index2 - j + 1]new_value = get_value(new_path, distances)if new_value < water_level:path = new_path[:]up = (water_level - new_value) / 500if up < 0.01:up = 0.01water_level = water_level - up# 当前最佳值if new_value < best_value:best_value = new_valuebest_path = new_path[:]# 随机搜索new_path = best_path[:]index1, index2 = randint(0, city_number - 1), randint(0, city_number - 1)new_path[index1], new_path[index2] = best_path[index2], best_path[index1]new_value = get_value(new_path, distances)if new_value < best_value:best_value = new_valuebest_path = new_path[:]iterate_result.append(best_value)print(best_path)print(get_value(best_path, distances))result_plot(iterate_result)