模拟退火算法（Simulated Annealing, SA）是一种启发式搜索算法，用于在一个大的搜索空间中寻找问题的近似全局最优解。它受到物理退火过程的启发，通过模拟物理退火过程中的冷却来逐步减少搜索空间，并在一定概率下接受劣解，从而避免局部最优解，最终趋向全局最优解。
### 模拟退火算法的基本步骤：
1. **初始化**：选择一个初始解，并计算其目标函数值。
2. **迭代**：在每次迭代中，对当前解进行小的随机扰动，生成一个新的解。
3. **评估**：计算新解的目标函数值。
4. **接受准则**：根据一个概率函数（通常是一个温度函数）来决定是否接受新解作为当前解。
5. **冷却计划**：随着算法的进行，逐渐降低温度，减小接受劣解的概率。
6. **终止条件**：当达到某个终止条件时（如温度降低到某个阈值，或迭代次数达到预设值），算法结束。
### Python实现模拟退火算法的示例代码：
```python
import random
import math
def objective_function(x):
# 目标函数，这里以简单的Ackley函数为例
return -20 - math.exp(1 - 0.2 * math.sqrt(1 / 32 * sum([x[i]**2 for i in range(32)])) - math.cos(2 * math.pi * [x[i] for i in range(32)])/32)
def simulated_annealing(objective, initial_temp, cooling_rate, min_temp, max_iterations):
current_solution = [random.uniform(-5, 5) for _ in range(32)] # 初始解
current_score = objective(current_solution)
best_solution = current_solution.copy()
best_score = current_score
temperature = initial_temp
for _ in range(max_iterations):
new_solution = [current_solution[i] + random.uniform(-0.05, 0.05) for i in range(32)]
new_score = objective(new_solution)
if new_score > current_score:
current_solution = new_solution
current_score = new_score
else:
if random.random() < math.exp((current_score - new_score) / temperature):
current_solution = new_solution
current_score = new_score
if current_score > best_score:
best_solution = current_solution.copy()
best_score = current_score
if temperature > min_temp:
temperature *= cooling_rate
if temperature < min_temp:
break
return best_solution, best_score
# 参数设置
initial_temp = 1000 # 初始温度
cooling_rate = 0.95 # 冷却速率
min_temp = 1 # 最低温度
max_iterations = 5000 # 最大迭代次数
# 执行模拟退火算法
best_solution, best_score = simulated_annealing(objective_function, initial_temp, cooling_rate, min_temp, max_iterations)
print("Best solution:", best_solution)
print("Best score:", best_score)
```
在这个示例中，我们使用了一个简单的32维Ackley函数作为目标函数，并设置了初始温度、冷却速率、最低温度和最大迭代次数。算法开始时，随机生成一个初始解，并在每次迭代中生成一个新的解。根据接受准则，算法可能会接受新解或保持当前解。随着温度的降低，算法逐渐减少接受劣解的概率，最终趋向全局最优解。
请注意，模拟退火算法的性能和结果受到初始参数设置的影响，可能需要根据具体问题进行调整。此外，模拟退火算法适用于解决连续和离散的优化问题。在实际应用中，可能需要根据问题的特性来设计目标函数和参数。