模拟退火的旅行商问题
satsp的Python项目详细描述
模拟退火的旅行商问题
该软件包利用模拟退火（sa）方法解决了旅行商问题（tsp）。
所需库
- 努比
- 熊猫
- matplotlib
- 数学
安装
可以使用pip安装satsp包：
pip install satsp
用法
基本用法：
from satsp import solver
cities = [[1, 6.0, 7.0],
[2, 4.0, 9.0],
[3, 7.0, 1.0]]
solver.Solve(cities)
solver.PrintSolution()
城市中的三列表示id、x坐标和y坐标。
高级用法：
solver.Solve(city_list = None, dist_matrix = None, start_temp = None, \
stop_temp = None, alpha = None, epochs = None, epoch_length = None, \
epoch_length_factor = 1.00, stopping_count = 100, screen_output = True)
solver.Solve()函数的参数：
city_list：一个n*3矩阵，包含表示n个城市的id、x坐标和y坐标的三列。可以是None。
dist_matrix：包含n个城市之间距离的n*n矩阵。如果通过None并通过Nonecity_list，程序将计算城市之间的eclide距离。如果city_list和dist_matrix都是None，那么将解决一个包含48个城市的测试实例。
start_temp：SA的初始温度。如果没有通过，程序将使用数据中的小样本估计初始温度。
stop_temp：SA的停止温度。可以是None。
alpha：sa的冷却速率。如果None通过，程序将在给定stop_temp和epochs时计算alpha。否则alpha设置为0.99。
epochs：sa的epochs数目。算法运行时间的决定因素。程序将在这段时间后终止。如果通过了None，并且给出了stop_temp和alpha，则程序将计算历元数。否则，在经过一定数量的时间段后，停止条件将切换为“无改善”，时间段的数量由stopping_count决定。
epoch_length：每个epoch中的迭代次数。默认值为min（100，n*（n-1）/2）。
历元长度因子：历元长度在每个历元处增加的速率。应大于或等于1。默认值为1.00。对于大型实例，建议使用较小的值。
stopping_count：如果没有任何改进，程序将在此后停止的时间段数。只有当用户既不指定总里程数，也不能由程序计算总里程数时，才会激活此停止条件。默认值为100。
屏幕输出：如果设置为^{True。
solver提供的其他功能：
solver.GetBestDist()：返回最佳tsp旅行的总距离
solver.GetBestTour()：返回最佳tsp旅游城市列表
solver.PrintBestTour()：输出一张画出最佳tsp旅游的图片
solver.PrintConvergence()：绘制每个历元结束时距离的收敛性
算法
该软件包实现了求解tsp问题的模拟退火（sa）元启发式算法。算法概述如下：
- 生成一个随机的初始巡更，并设置一个初始温度。
- 为要执行的迭代设置一个数字，由纪元长度确定。
- 在巡演中随机选择两个城市并执行“2-opt”操作，即在两个城市之间反转巡演。
- 如果获得距离较短的旅行，请接受新的旅行。否则，以一定的概率接受新的旅行，概率取决于新旧距离和当前温度的差异。
- 对2中确定的迭代次数重复3-4次。
- 如果满足停止条件，则终止。否则转到7。
- 降低温度，重复2-5次。
参考文献
柯克帕特里克、斯科特、C丹尼尔·格拉特和马里奥·P·ve“CCHI。”模拟退火优化〉，《科学》220.4598（1983）：671-680。
朴智星、月圆和杨大金。”模拟退火算法中参数设定的系统程序〉，《计算机与运筹学》25.3（1998）：207-217。
欢迎加入QQ群-->： 979659372
