模拟退火算法解决TSP问题
发布时间
阅读量：
阅读量
GitHub地址：https://github.com/Poe2016/Combinatorial_optimization_methods
1、TSP问题描述
TSP问题（Traveling Salesman Problem），也被称为Traveling Salesperson Problem或Tour Guide Problem，在运筹学领域具有重要意义。该问题是寻找一条经过给定所有城市的闭合回路路径，并且使得总路程最短。具体而言，在图论领域中被抽象为一个特定的问题：给定一个包含n个节点的完全加权图，在满足每个节点仅访问一次的前提下找到一条经过所有节点并最终返回起点的回路路径，并使得该路径的总长度最小化。
旅行商问题是NP完全问题。随着n的增大,无法通过精确算法求得最优解;此时必须采用近似算法来获得接近最优的解决方案。
2、模拟退火算法简述
模拟退火算法源于上世纪八十年代初，在理论研究与应用实践方面均取得了重要进展。原始论文是该领域的重要文献之一，请有需要的朋友可以上网查阅：https://pdfs.semanticscholar.org/e893/4a942f06ee91940ab57732953ec6a24b3f00.pdf
3、使用模拟退火算法解决TSP问题
读取问题件函数，返回一个列表，列表中存储了城市
def load_data(path):
f_open = open(path)
lines = f_open.readlines()
f_open.close()
point_list = []
for line in lines[6:len(lines)-1]:
line_list = line.strip().split()
point_list.append(Point(line_list[1], line_list[2]))
return point_list计算两个城市之间距离的函数，返回一个二维列表
# return the distance matrix of every two cities
def dist_matrix(point_list):
num = len(point_list)
dist = [[0]*num for i in range(num)]
for i in range(num):
for j in range(num):
dist[i][j] = round(math.sqrt(math.pow(point_list[i].x-point_list[j].x, 2) + math.pow(point_list[i].y-point_list[j].y, 2)), 2) if i != j else 0
return dist模拟退火算法实现函数
def simulated_annealing(t, t_min, factor, point_list, dist):
num = len(point_list)
total_cost = 0
# the initial sequence of cities
init_seq = [i for i in range(num)]
selected_seq = []
selected_city = 0
while len(selected_seq) < num:
if len(selected_seq) == 0:
selected_city = choice(init_seq)
init_seq.remove(selected_city)
selected_seq.append(selected_city)
continue
if len(selected_seq) == num:
break
left_num = len(init_seq)
sample_num = left_num // 10 if left_num >= 10 else left_num % 10
# select cities by random sampling
sample_list = sample(init_seq, sample_num)
curr_city = selected_seq[-1]
cost = sys.maxsize
sample_city = 0
t_sample = t
for city in sample_list:
t_sample *= factor
if dist[curr_city][city] < cost:
cost = dist[curr_city][city]
sample_city = city
else:
r = uniform(0, 1)
if dist[curr_city][city] > cost and t_sample > t_min and math.exp(dist[curr_city][city] - cost)/t_sample > r:
sample_city = city
cost = dist[curr_city][city]
break
init_seq.remove(sample_city)
selected_seq.append(sample_city)
total_cost += cost
print '模拟退火得最小开销：', total_cost
print '选择路径为：', selected_seq全部评论 (0)
还没有任何评论哟~