模拟退火算法 Simulated Annealing

本文主要是介绍模拟退火算法 Simulated Annealing，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

模拟退火算法 Simulated Annealing

1. 介绍

模拟退火算法（Simulated Annealing, SA）是一种启发式的优化算法。它适用于在大型离散或连续复杂问题中寻找全局最优解，例如组合优化，约束优化，图问题等。模拟退火是一种随机（概率性）搜索算法，基于物理中固体晶体退火过程的模拟。退火过程中，晶体内部由高能状态向低能状态演化，最终在足够低的温度时稳定在能量最低的状态。

模拟退火算法的主要思想是在搜索过程中接受比当前解差的解，以跳出局部最优。具体来说，模拟退火算法过程如下：

初始化设置：设置初始解、初始温度、温度衰减系数，最低温度等参数。
在当前温度下，随机选取一个邻近解并计算其能量变化量。
如果能量降低（对于最小化问题），则接受该解作为当前解；如果能量增加，则以一定的概率（通常依赖于温度和能量变化量）接受该解。
更新温度（通常为当前温度乘以衰减系数）。
重复步骤2-4，直到温度降至最低温度并稳定。
输出最佳解。

模拟退火算法的关键在于选择合适的初始温度、衰减系数和结束条件，以及针对问题的邻近解生成策略和概率接受函数。

2. 经典应用

接下来，我们将以三个经典问题为例，展示如何使用模拟退火算法求解。

2.1 旅行商问题（TSP）

旅行商问题即求解在给定城市、距离的情况下，找到一条道路，使得从起点出发，经过所有城市后回到起点，且总距离最短。

import random
import math
import numpy as np# 计算路径长度
def calculate_distance(path, distance_matrix):distance = 0for i in range(len(path)-1):distance += distance_matrix[path[i]][path[i+1]]distance += distance_matrix[path[-1]][path[0]]return distance# 邻近解生成策略：交换两个城市的位置
def generate_neighbor(path):new_path = path.copy()i, j = random.sample(range(len(path)), 2)new_path[i], new_path[j] = new_path[j], new_path[i]return new_path# 模拟退火算法求解TSP问题
def simulated_annealing_tsp(distance_matrix, initial_temperature, min_temperature, cooling_factor, max_iteration):n = len(distance_matrix)current_path = list(range(n))random.shuffle(current_path)current_distance = calculate_distance(current_path, distance_matrix)temperature = initial_temperaturebest_path = current_path[:]best_distance = current_distancefor it in range(max_iteration):if temperature < min_temperature:breaknew_path = generate_neighbor(current_path)new_distance = calculate_distance(new_path, distance_matrix)delta_distance = new_distance - current_distanceif delta_distance < 0:current_path = new_pathcurrent_distance = new_distanceif new_distance < best_distance:best_path = new_path[:]best_distance = new_distanceelse:prob = math.exp(-delta_distance / temperature)if random.random() < prob:current_path = new_pathcurrent_distance = new_distancetemperature *= cooling_factorreturn best_path, best_distance# 用随机距离矩阵测试
n = 10
distance_matrix = np.random.randint(1, 100, size=(n, n))
initial_temperature = 1000
min_temperature = 1e-6
cooling_factor = 0.99
max_iteration = 10000best_path, best_distance = simulated_annealing_tsp(distance_matrix, initial_temperature, min_temperature, cooling_factor, max_iteration)
print('Best path:', best_path)
print('Best distance:', best_distance)

2.2 函数寻优

给定一个连续空间的实数函数f(x)，求解其在给定区间上的最小值。

import random
import math# 定义函数
def f(x):return x * x - 4 * x + 4def generate_neighbor(x, step):return x + random.uniform(-step, step)def simulated_annealing_function_optimization(f, initial_temperature, min_temperature, cooling_factor, max_iteration, search_interval, neighbor_step):current_x = random.uniform(search_interval[0], search_interval[1])current_y = f(current_x)temperature = initial_temperaturebest_x = current_xbest_y = current_yfor it in range(max_iteration):if temperature < min_temperature:breaknew_x = generate_neighbor(current_x, neighbor_step)if new_x < search_interval[0] or new_x > search_interval[1]:continuenew_y = f(new_x)delta_y = new_y - current_yif delta_y < 0:current_x = new_xcurrent_y = new_yif new_y < best_y:best_x = new_xbest_y = new_yelse:prob = math.exp(-delta_y / temperature)if random.random() < prob:current_x = new_xcurrent_y = new_ytemperature *= cooling_factorreturn best_x, best_yinitial_temperature = 1000
min_temperature = 1e-6
cooling_factor = 0.99
max_iteration = 10000
search_interval = [0, 5]
neighbor_step = 0.1best_x, best_y = simulated_annealing_function_optimization(f, initial_temperature, min_temperature, cooling_factor, max_iteration, search_interval, neighbor_step)
print('Best x:', best_x)
print('Best y:', best_y)

2.3 定点覆盖问题

给定一个二维平面，有若干个点和一定数量的覆盖盒。要求通过移动覆盖盒的位置使得尽可能多的点被覆盖。覆盖盒的形状为边长为1的正方形。

import random
import mathdef point_covered(points, box):# 判断点是否在覆盖盒内return sum([1 for p in points if box[0] <= p[0] <= box[0]+1 and box[1] <= p[1] <= box[1]+1])def generate_neighbor(box, step):# 随机生成一个相邻覆盖盒return (box[0] + random.uniform(-step, step), box[1] + random.uniform(-step, step))def simulated_annealing_point_cover(points, n_boxes, initial_temperature, min_temperature, cooling_factor, max_iteration, neighbor_step):boxes = [(random.uniform(0, 5), random.uniform(0, 5)) for _ in range(n_boxes)]temperature = initial_temperature# 当前解：覆盖的点数量和覆盖盒集合current_cover = sum([point_covered(points, box) for box in boxes])current_boxes = boxes# 迭代过程for it in range(max_iteration):if temperature < min_temperature:break# 随机选择一个覆盖盒生成相邻解idx = random.randrange(len(boxes))new_box = generate_neighbor(boxes[idx], neighbor_step)new_boxes = boxes[:]new_boxes[idx] = new_boxnew_cover = sum([point_covered(points, box) for box in new_boxes])delta_cover = new_cover - current_coverif delta_cover > 0:current_boxes = new_boxescurrent_cover = new_coverelse:prob = math.exp(delta_cover / temperature)if random.random() < prob:current_boxes = new_boxescurrent_cover = new_covertemperature *= cooling_factorreturn current_boxes# 生成点集
points = [(random.uniform(0, 5), random.uniform(0, 5)) for _ in range(50)]
n_boxes = 5initial_temperature = 1000
min_temperature = 1e-6
cooling_factor = 0.99
max_iteration = 10000
neighbor_step = 0.1result = simulated_annealing_point_cover(points, n_boxes, initial_temperature, min_temperature, cooling_factor, max_iteration, neighbor_step)
print(result)