之前我在这篇博文中介绍了解决MTSP问题的相关思路，并附上了GitHub上的相关源码。在这篇文章中，我将详细介绍如何使用SA智能优化算法进行编程
1. SA算法的核心思路：
SA（Simulated Annealing）——模拟退火算法。
SA快速入门视频推荐：https://www.bilibili.com/video/BV1j64y1Y7FB
SA算法的核心是要理解 T 在优化过程的作用。
- T越大，越包容，可以接受看似不那么优的结果，从而跳出局部最优情况；
- T越小，越局限，只能接受比自己更优的结果，从而更快达到最优解。
在SA算法进行的过程中 T 会逐渐变小（例如以这种形式： T = 0.95 * T）。可以理解为：SA算法进行的过程是：从”跳出局部最优解”优先；到”求解最优解”优先。
2. 是否接收不那么优的解？
#（伪代码）
p_accept = math.exp(-(new - current) / T) //接受概率
p = random.random() //生成随机值
if p < p_accept:
solution = new
以上代码实现了，对较差解的一个选择评估。其依赖的函数如下，对应上方代码的第一句：
3. 使用SA求解MTSP问题的代码实现
- 初始化—— 固定温度最优解， 全局最优解
- 开始进行模拟退火，每个温度下循环一定次数（300次）
- 如果更优直接更新当前值；如果更差按照公式取概率判断是否更新。
- 更新温度，进入下一次退火
- 更新 固定温度最优解与 *全局最优解
SA的详细过程如下（作为SA类中的函数），理解即可，不必纠结每个函数的实现。
def sa_process_iterator(self, solution, get_distance_func):
while self.T > self.T_end:
# 每个温度下最优解都要赋值
self.per_iter_solution = solution
# 在每个温度下迭代
for _ in range(self.Lk):
# 当前解的目标函数值
current_solu_obj = self.object_func(solution)
# 产生新解
new_solu = self.generate_new_solu(solution)
# 新解目标函数值
new_solu_obj = self.object_func(new_solu)
# 新解更优，接受新解
if new_solu_obj < current_solu_obj:
solution = new_solu
# Metropolis准则
else:
prob_accept = math.exp(-(new_solu_obj - current_solu_obj) / self.T)
p = random.random()
if p < prob_accept:
solution = new_solu
# 该温度下迭代完成
solu_obj = self.object_func(solution)
# 解和该温度下最优解比较
if solu_obj < self.object_func(self.per_iter_solution):
self.per_iter_solution = solution
# 解和全局最优解比较
if solu_obj < self.object_func(self.best_solution):
self.best_solution = solution
# 记录每个温度下最优解和全局最优解
self.all_per_iter_solution.append(self.per_iter_solution)
self.all_best_solution.append(self.best_solution)
per_iter_solu_path, per_iter_solu_dis = get_distance_func(self.per_iter_solution)
best_solu_path, best_solu_dis = get_distance_func(self.best_solution)
# *******************有关参数更新****************************
self.T_list.append(self.T)
self.T = self.T * self.alpha
Original: https://www.cnblogs.com/litecdows/p/16563473.html
Author: litecdows
Title: SA算法：从MTSP问题出发
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/609964/
转载文章受原作者版权保护。转载请注明原作者出处！