做一个网站怎么做,做网站代理怎么样,网站正在建设页面模板,建站系统网站建设模拟退火算法求解TSP的步骤参考书籍《Matlab智能算法30个案例分析》。
问题描述
TSP问题描述在该书籍的第4章 算法流程 部分实现代码片段
坐标轴转换成两点之间直线距离长度的代码
coordinates np.array([(16.47, 96.10),(16.47, 94.44),(20.09, 92.54),(22.39, 93.37),(2…模拟退火算法求解TSP的步骤参考书籍《Matlab智能算法30个案例分析》。
问题描述
TSP问题描述在该书籍的第4章 算法流程 部分实现代码片段
坐标轴转换成两点之间直线距离长度的代码
coordinates np.array([(16.47, 96.10),(16.47, 94.44),(20.09, 92.54),(22.39, 93.37),(25.23, 97.24),(22.00, 96.05),(20.47, 97.02),(17.20, 96.29),(16.30, 97.38),(14.05, 98.12),(16.53, 97.38),(21.52, 95.59),(19.41, 97.13),(20.09, 92.55),])# 将距离坐标矩阵转换成两点之间实际的直线距离
city_num coordinates.shape[0]def get_distanceGraph(coordinates):# 计算城市间的欧式距离diatance_graph np.zeros((city_num, city_num))# 初始化生成矩阵for i in range(city_num):for j in range(i, city_num):diatance_graph[i][j] diatance_graph[j][i] np.linalg.norm(coordinates[i] - coordinates[j])print(diatance_graph, diatance_graph)return diatance_graph求解TSP问题路径长度的代码
def cal_length(cur_solution, distance_graph):# 计算路线长度total_length 0visited_city_list [cur_solution[0]]for i in range(city_num):visited_city visited_city_list[-1]cur_city cur_solution[i]visited_city_id visited_city - 1cur_city_id cur_city - 1next_city_length distance_graph[visited_city_id][cur_city_id]total_length next_city_lengthvisited_city_list.append(cur_city)print(total_length, total_length)return total_length使用一个路径长度矩阵相对简单可以进行笔算验证解结果的算例验证计算TSP路径长度的代码是可行的
可以笔算验证的算例代码
# 各个节点之间的欧氏距离
distance_list [[0, 4.0, 6.0, 7.5, 9.0, 20.0, 10.0, 16.0, 8.0],[4.0, 0, 6.5, 4.0, 10.0, 5.0, 7.5, 11.0, 10.0],[6.0, 6.5, 0, 7.5, 10.0, 10.0, 7.5, 7.5, 7.5],[7.5, 4.0, 7.5, 0, 10.0, 5.0, 9.0, 9.0, 15.0],[9.0, 10.0, 10.0, 10.0, 0, 10.0, 7.5, 7.5, 10.0],[20.0, 5.0, 10.0, 5.0, 10.0, 0, 7.0, 9.0, 7.5],[10.0, 7.5, 7.5, 9.0, 7.5, 7.0, 0, 7.0, 10.0],[15.0, 11.0, 7.5, 9.0, 7.5, 9.0, 7.0, 0, 10.0],[8.0, 10.0, 7.5, 15.0, 10.0, 7.5, 10.0, 10.0, 0]]
demand_node_num 9
supply_node_num 0
city_num 9
distance_graph np.zeros((demand_node_numsupply_node_num, demand_node_numsupply_node_num))
for i in range(demand_node_numsupply_node_num):distance_graph[i] np.array(distance_list[i])
cur_solution [3, 9, 6, 4, 7, 8, 1, 5, 2]
length cal_length(cur_solution, distance_graph)
print(length, length)Metropolis准则函数
# Metropolis准则函数
def Metropolis_func(cur_solution, new_solution, distance_graph, cur_temp):# 计算新旧解之间的能量之差如果能量降低以概率1接受新解如果能量升高以一定概率接受劣化解dC cal_length(new_solution, distance_graph) - cal_length(cur_solution, distance_graph)if dC 0:cur_solution new_solutioncur_length cal_length(cur_solution, distance_graph)elif pow(math.e, -dC/cur_temp) np.random.rand(): # 大于一个随机生成的数:cur_solution new_solutioncur_length cal_length(cur_solution, distance_graph)else:cur_length cal_length(cur_solution, distance_graph)return cur_solution, cur_length算法迭代图形 算法程序还有待改进空间生成的迭代图形和最优结果和书上的存在差异。
