使用优化后的退火算法对att48求解最优路径并绘图python代码
时间: 2024-02-06 07:02:05 浏览: 198
aco.rar_aco tsp_att48_att48 tsp matlab_tsp and aco matlab_蚁群算法at
以下是使用优化后的退火算法对att48求解最优路径并绘图的Python 代码,其中部分代码参考了其他开源项目:
```python
import math
import random
import matplotlib.pyplot as plt
# 定义城市坐标
city_coordinates = [
(6734, 1453), (2233, 10), (5530, 1424), (401, 841), (3082, 1644),
(7608, 4458), (7573, 3716), (7265, 1268), (6898, 1885), (1112, 2049),
(5468, 2606), (5989, 2873), (4706, 2674), (4612, 2035), (6347, 2683),
(6107, 669), (7611, 5184), (7462, 3590), (7732, 4723), (5900, 3561),
(4483, 3369), (6101, 1110), (5199, 2182), (1633, 2809), (4307, 2322),
(675, 1006), (7555, 4819), (7541, 3981), (3177, 756), (7352, 4506),
(7545, 2801), (3245, 3305), (6426, 3173), (4608, 1198), (23, 2216),
(7248, 3779), (7762, 4595), (7392, 2244), (3484, 2829), (6271, 2135),
(4985, 140), (1916, 1569), (7280, 4899), (7509, 3239), (10, 2676),
(6807, 2993), (5185, 3258)
]
# 定义距离矩阵
def distance_matrix(city_coordinates):
n = len(city_coordinates)
matrix = [[0] * n for i in range(n)]
for i in range(n):
for j in range(n):
if i != j:
x1, y1 = city_coordinates[i]
x2, y2 = city_coordinates[j]
matrix[i][j] = math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
return matrix
distance = distance_matrix(city_coordinates)
# 邻域结构:交换两个城市的位置
def swap_cities(path):
n = len(path)
i, j = random.sample(range(n), 2)
new_path = path[:]
new_path[i], new_path[j] = new_path[j], new_path[i]
return new_path
# 计算路径长度
def path_length(path, distance):
return sum([distance[path[i-1]][path[i]] for i in range(len(path))])
# 优化后的退火算法
def simulated_annealing(distance, max_iterations=50000, start_temperature=10000, cooling_rate=0.99):
n = len(distance)
current_path = random.sample(range(n), n)
current_length = path_length(current_path, distance)
best_path = current_path[:]
best_length = current_length
temperature = start_temperature
for i in range(max_iterations):
new_path = swap_cities(current_path)
new_length = path_length(new_path, distance)
delta = new_length - current_length
if delta < 0 or random.random() < math.exp(-delta/temperature):
current_path = new_path[:]
current_length = new_length
if current_length < best_length:
best_path = current_path[:]
best_length = current_length
temperature *= cooling_rate
return best_path, best_length
# 绘制最优路径
def plot_path(city_coordinates, path):
x = [city_coordinates[path[i]][0] for i in range(len(path))]
y = [city_coordinates[path[i]][1] for i in range(len(path))]
x.append(city_coordinates[path[0]][0])
y.append(city_coordinates[path[0]][1])
plt.plot(x, y, marker='o')
plt.show()
# 求解最优路径
best_path, best_length = simulated_annealing(distance)
print('最优路径:', best_path)
print('最短距离:', best_length)
# 绘制最优路径
plot_path(city_coordinates, best_path)
```
运行代码后,会输出最优路径和最短距离,并绘制最优路径的图像。
阅读全文