【算法】模拟退火

大家好，欢迎来到IT知识分享网。

一、引言

        模拟退火算法（Simulated Annealing, SA）是一种启发式搜索算法，它通过模拟物理中的退火过程来解决优化问题。这种算法能够跳出局部最优解，寻找全局最优解，特别适用于解决复杂的优化问题。

二、算法原理

        模拟退火算法的核心原理是模拟物理中的退火过程，将问题的解状态视为物理系统的状态，目标函数值视为系统的能量。算法从初始温度开始，通过随机扰动当前解产生新解，并根据Metropolis准则决定是否接受新解。随着温度的逐渐降低，系统逐渐趋于稳定，最终在低温下达到全局最优或近似最优解。

        模拟退火算法（Simulated Annealing, SA）也是一种基于概率的优化算法，灵感来源于金属退火过程。金属退火是一个加热和缓慢冷却的过程，目的是提高材料的强度和硬度。模拟退火算法试图从一个初始解出发，逐步搜索其他可能解，以找到全局最优解。

其工作原理如下：

• 随机选择初始解和初始温度。
• 利用当前温度对解进行扰动，产生新解。
• 计算新解与旧解的目标函数值：
  • 如果新解更优，则接受新解。
  • 如果新解不优，则以一定概率接受新解（即存在“跳出局部最优”的可能性），概率依赖于当前温度和解的优劣。
• 随着每次迭代，逐渐降低温度。
• 直到达到终止条件（如达到最大迭代次数或温度降至某个阈值）。

三、数据结构

模拟退火算法主要涉及以下数据结构：

• 解空间：表示所有可能解的集合。
• 当前解：当前迭代中正在考虑的解。
• 新解：通过随机扰动当前解产生的新解。
• 温度参数：控制算法搜索过程的冷却速度。

四、算法使用场景

模拟退火算法适用于多种优化问题，包括但不限于：

• 调度问题：在满足约束条件下，优化任务的执行顺序。
• 神经网络权重优化：调整神经网络的权重和偏置，以提高模型性能,超参数优化等。
• 组合优化问题：如旅行商问题（TSP）、背包问题等。

• N-Queens 问题：寻找 N 皇后问题的解。
• 约束满足问题：如图着色问题。

五、算法实现

• 初始化：选择初始解，并设置初始温度。
• 迭代：在当前解的邻域内生成一个新解。
• 接受准则：如果新解比当前解好，则接受新解；如果新解较差，则根据概率接受新解（这个概率随着温度的降低而减少）。
• 降温：逐步降低温度，使得接受较差解的概率逐渐减小。
• 终止条件：当温度降低到指定值或迭代次数达到上限时，算法停止。

import math import random def simulated_annealing(initial_state, temperature, cooling_rate, max_iterations, objective_function): current_state = initial_state current_energy = objective_function(current_state) for i in range(max_iterations): # 生成新解 new_state = perturb(current_state) # perturb是自定义的新解生成函数 new_energy = objective_function(new_state) # 计算接受概率 if new_energy < current_energy: current_state = new_state current_energy = new_energy else: acceptance_probability = math.exp((current_energy - new_energy) / temperature) if random.random() < acceptance_probability: current_state = new_state current_energy = new_energy # 降温 temperature *= cooling_rate return current_state def perturb(state): # 这里定义扰动操作，比如随机交换两个元素 new_state = state[:] # 复制当前状态 i, j = random.sample(range(len(state)), 2) new_state[i], new_state[j] = new_state[j], new_state[i] return new_state def objective_function(state): # 计算目标函数值，示例计算归并值 return sum(state) # 示例使用 initial_state = [5, 3, 1, 7, 2, 4, 6] temperature = 1000 cooling_rate = 0.95 max_iterations = 1000 best_state = simulated_annealing(initial_state, temperature, cooling_rate, max_iterations, objective_function) print("Best state:", best_state) print("Objective value:", objective_function(best_state))

六、其他同类算法对比

• 遗传算法：基于自然选择和遗传机制，适合大规模复杂的优化问题，相比之下计算开销大。
• 粒子群优化：通过群体智能进行搜索，适合多维和非线性问题，通常收敛速度较快。
• 蚁群算法：通过模拟蚂蚁觅食行为进行优化，适合图论中的路径问题。

七、多语言代码实现

Java

import java.util.Random; public class SimulatedAnnealing { private static double objectiveFunction(int[] state) { double sum = 0; for (int i : state) { sum += i; } return sum; } private static int[] perturb(int[] state) { Random rand = new Random(); int[] newState = state.clone(); int i = rand.nextInt(state.length); int j = rand.nextInt(state.length); // 交换元素 int temp = newState[i]; newState[i] = newState[j]; newState[j] = temp; return newState; } public static int[] simulatedAnnealing(int[] initialState, double temperature, double coolingRate, int maxIterations) { int[] currentState = initialState; double currentEnergy = objectiveFunction(currentState); for (int i = 0; i < maxIterations; i++) { int[] newState = perturb(currentState); double newEnergy = objectiveFunction(newState); if (newEnergy < currentEnergy) { currentState = newState; currentEnergy = newEnergy; } else { double acceptanceProbability = Math.exp((currentEnergy - newEnergy) / temperature); if (Math.random() < acceptanceProbability) { currentState = newState; currentEnergy = newEnergy; } } // 降温 temperature *= coolingRate; } return currentState; } public static void main(String[] args) { int[] initialState = {5, 3, 1, 7, 2, 4, 6}; double temperature = 1000.0; double coolingRate = 0.95; int maxIterations = 1000; int[] bestState = simulatedAnnealing(initialState, temperature, coolingRate, maxIterations); System.out.println("Best state: " + java.util.Arrays.toString(bestState)); System.out.println("Objective value: " + objectiveFunction(bestState)); } }

C++

#include <iostream> #include <vector> #include <cmath> #include <random> #include <algorithm> double objectiveFunction(const std::vector<int>& state) { return std::accumulate(state.begin(), state.end(), 0.0); } std::vector<int> perturb(const std::vector<int>& state) { std::vector<int> newState = state; std::swap(newState[rand() % state.size(), rand() % state.size()]); return newState; } std::vector<int> simulatedAnnealing(std::vector<int> initialState, double temperature, double coolingRate, int maxIterations) { std::vector<int> currentState = initialState; double currentEnergy = objectiveFunction(currentState); for (int i = 0; i < maxIterations; i++) { auto newState = perturb(currentState); double newEnergy = objectiveFunction(newState); if (newEnergy < currentEnergy) { currentState = newState; currentEnergy = newEnergy; } else { double acceptanceProbability = exp((currentEnergy - newEnergy) / temperature); if ((static_cast<double>(rand()) / RAND_MAX) < acceptanceProbability) { currentState = newState; currentEnergy = newEnergy; } } temperature *= coolingRate; } return currentState; } int main() { std::vector<int> initialState = {5, 3, 1, 7, 2, 4, 6}; double temperature = 1000.0; double coolingRate = 0.95; int maxIterations = 1000; auto bestState = simulatedAnnealing(initialState, temperature, coolingRate, maxIterations); std::cout << "Best state: "; for (const auto& val : bestState) { std::cout << val << " "; } std::cout << "\nObjective value: " << objectiveFunction(bestState) << std::endl; return 0; }

Python

import math import random class SimulatedAnnealing: def __init__(self, cooling_rate=0.99): self.temperature = 1000 self.cooling_rate = cooling_rate def find_solution(self, distances): current = self.initialize_solution(len(distances)) best = current.copy() while self.temperature > 1: next = self.perturb_solution(current) delta = self.calculate_cost(distances, next) - self.calculate_cost(distances, current) if self.accept(delta): current = next if self.is_better(current, best): best = current.copy() self.temperature *= self.cooling_rate return best def accept(self, delta): return math.exp(-delta / self.temperature) > random.random()

Go

package main import ( "fmt" "math" "math/rand" "time" ) func objectiveFunction(state []int) float64 { sum := 0 for _, v := range state { sum += v } return float64(sum) } func perturb(state []int) []int { newState := make([]int, len(state)) copy(newState, state) i, j := rand.Intn(len(state)), rand.Intn(len(state)) newState[i], newState[j] = newState[j], newState[i] return newState } func simulatedAnnealing(initialState []int, temperature, coolingRate float64, maxIterations int) []int { currentState := initialState currentEnergy := objectiveFunction(currentState) for i := 0; i < maxIterations; i++ { newState := perturb(currentState) newEnergy := objectiveFunction(newState) if newEnergy < currentEnergy { currentState = newState currentEnergy = newEnergy } else { acceptanceProbability := math.Exp((currentEnergy - newEnergy) / temperature) if rand.Float64() < acceptanceProbability { currentState = newState currentEnergy = newEnergy } } temperature *= coolingRate } return currentState } func main() { rand.Seed(time.Now().UnixNano()) initialState := []int{5, 3, 1, 7, 2, 4, 6} temperature := 1000.0 coolingRate := 0.95 maxIterations := 1000 bestState := simulatedAnnealing(initialState, temperature, coolingRate, maxIterations) fmt.Println("Best state:", bestState) fmt.Println("Objective value:", objectiveFunction(bestState)) }

八、实际服务应用场景的代码框架

        在物流配送系统中，模拟退火算法可以用于优化配送路径，减少配送时间和成本。系统会根据实时交通数据、配送点位置等信息，不断调整配送路径，以达到最优配送效果。

        为一个无线网络调度问题应用模拟退火算法，整个代码框架示例：

wireless_network_optimization/ ├── main.py # 主程序入口 ├── optimization.py # 模拟退火算法实现 ├── network.py # 网络相关数据结构及功能实现 └── utils.py # 其他辅助函数

main.py 实现

from optimization import SimulatedAnnealing from network import Network def main(): network = Network() initial_configuration = network.get_initial_configuration() best_configuration = SimulatedAnnealing.run( initial_configuration, temperature=1000, cooling_rate=0.95, max_iterations=1000, objective_function=network.objective_function ) print("最优配置:", best_configuration) print("最优目标值:", network.objective_function(best_configuration)) if __name__ == "__main__": main()

optimization.py 实现

import math import random class SimulatedAnnealing: @staticmethod def run(initial_state, temperature, cooling_rate, max_iterations, objective_function): current_state = initial_state current_energy = objective_function(current_state) for i in range(max_iterations): new_state = SimulatedAnnealing.perturb(current_state) new_energy = objective_function(new_state) if new_energy < current_energy: current_state = new_state current_energy = new_energy else: acceptance_probability = math.exp((current_energy - new_energy) / temperature) if random.random() < acceptance_probability: current_state = new_state current_energy = new_energy temperature *= cooling_rate return current_state @staticmethod def perturb(state): # 定义扰动逻辑 pass

network.py 实现

class Network: def __init__(self): # 初始化网络相关参数 pass def get_initial_configuration(self): # 获取初始配置 pass def objective_function(self, configuration): # 计算目标函数 pass

utils.py 实现

# 辅助函数，可能包含数据处理等 def load_data(file_path): # 加载数据 pass def save_results(results, file_path): # 保存结果 pass

        模拟退火算法（Simulated Annealing, SA）是一种启发式全局优化算法，灵感来源于固体退火原理。在冶金学中，退火是将金属加热到一定温度，再缓慢冷却以消除内部应力，使金属结构达到稳定状态。在优化问题中，模拟退火算法通过接受一定概率的“坏解”（即解质量下降的情况），以跳出局部最优，最终逼近全局最优解。

        模拟退火算法是一种强大并且灵活的优化算法，适合多种应用场景。