# 模擬退火
## 簡介
模擬退火（Simulated Annealing，簡稱SA）是一種基於隨機搜尋的全局優化演算法，靈感來自金屬退火過程。退火是金屬在高溫下加熱後，再緩慢降溫，使其結構達到最穩定狀態的過程。模擬退火將這一過程應用於解決組合優化問題。
## 基本思路:
**1.隨機選擇初始解:** 演算法從一個隨機選擇的解開始
**2.隨機探索鄰域解:** 在每一步，根據某種規則隨機選擇一個鄰域解
**3.決定是否接受新解：** 如果新解比當前解更好，則接受新解。如果新解較差，則以一定的概率接受新解，這樣可以避免陷入局部最優解。
**4.逐步降低「溫度」:** 隨著迭代次數的增加，「溫度」逐漸降低，接受較差解的概率也隨之減少，最終收斂到全局最優解
**5.設定關鍵參數**
(i)**初始溫度**:決定出示階段能接受較差解的可能性
(ii)**冷卻速率**:溫度下降的速度，通常設計為逐步減小，最終達到某個低溫停止
(iii)**鄰域解的生成方式**:如何在當前解的基礎上生成鄰域解
**流程圖**
## 小結:
模擬退火特別適用於求解那些解空間較大且不易用傳統方法找到全局最優解的問題，如旅行推銷員問題、排程問題、機器學習中的超參數優化
## 例題:旅行推銷員問題（traveling salesman problem, TSP）
### 題目簡述:
旅行推銷員必需到N個地方，每個地方只經過一次，然後回到起始點。問題是找最適解（最短時間、最短行程、或最少花費……）
### 使用模擬退火解TSP的步驟
**1.初始化：**
* 隨機生成一個城市的訪問順序（即隨機的初始解），這個順序代表了旅行推銷員要拜訪的城市順序。
* 設定初始溫度（T0）和冷卻速率（alpha），通常溫度越高，演算法能夠接受較差的解的機會越大。
* 設定停止條件，例如溫度降至某個閾值或達到最大迭代次數。
**2.定義鄰域結構：**
* 在每一個迭代中，通過對當前解進行某種小變化來生成鄰域解。對於TSP問題，常見的鄰域結構是兩兩交換，即隨機選擇兩個城市，交換它們的順序，從而生成新的解。
**3.計算成本（能量）**
* 對每一個解，計算其總旅行距離，這是解的“成本”。總距離越短，解越好
**4.接受新解的機制**
* 比較當前解和鄰域解的總距離。如果鄰域解的距離較短，則接受這個新解。
如果鄰域解的距離較長，則以一定的概率接受這個解。這個概率通常依賴於當前溫度 T 和解的距離差：$P=e^{−ΔE/T}$
其中，ΔE 是鄰域解和當前解的距離差。如果 ΔE 為正（即新解更差），接受新解的概率會隨著溫度下降而降低。
**5.溫度更新：**
* 隨著每次迭代，將溫度按照預設的冷卻速率 alpha 降低：T=α⋅T
通常，alpha 的值略小於 1（如 0.99），表示每次迭代溫度下降。
**6.停止條件:**
* 當溫度降到預定的最小值，或者當解的改善停止時，算法終止。
### 程式碼
#### 計算距離
```cpp=
double total_distance(const vector<int>& tour, const vector<vector<double>>& distance_matrix) {
double dist = 0;
for (size_t i = 0;i < tour.size()-1; ++i) {
dist += distance_matrix[tour[i]][tour[i + 1]];
}
dist += distance_matrix[tour[tour.size() - 1]][tour[0]];
return dist;
}
```
#### 生成鄰域解（隨機交換兩個城市）
```cpp=
vector<int> swap(const vector<int>& tour) {
vector<int> new_tour = tour;
int i = rand()%tour.size();
int j = rand()%tour.size();
swap(new_tour[i], new_tour[j]);
return new_tour;
}
```
#### 模擬退火算法
```cpp=
pair<vector<int>, double> simulated_annealing(const vector<vector<double>>& distance_matrix, double initial_temperature, double cooling_rate, int max_iterations) {
int n = distance_matrix.size();
// 隨機初始化一個解
vector<int> current_solution(n);
for(int i=0; i<n; ++i) current_solution[i] = i;
random_shuffle(current_solution.begin(), current_solution.end());
double current_distance = total_distance(current_solution, distance_matrix);
double temperature = initial_temperature;
vector<int> best_solution = current_solution;
double best_distance = current_distance;
// 主迴圈，根據最大迭代次數進行
for (int iteration = 0; iteration < max_iterations; ++iteration) {
vector<int> new_solution = swap(current_solution);
double new_distance = total_distance(new_solution, distance_matrix);
// 計算能量差
double delta_energy = new_distance - current_distance;
// 判斷是否接受新解
if (delta_energy < 0 || ((rand() / double(RAND_MAX)) < exp(-delta_energy / temperature))) {
current_solution = new_solution;
current_distance = new_distance;
// 更新最優解
if (current_distance < best_distance) {
best_solution = current_solution;
best_distance = current_distance;
}
}
// 降低溫度
temperature *= cooling_rate;
}
return {best_solution, best_distance};
}
```
:::success
模擬退火實作起來較為龐大，不適合在比賽中使用
:::
### 總程式碼
```cpp=
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <utility>
using namespace std;
// 計算旅程的總距離
double total_distance(const vector<int>& tour, const vector<vector<double>>& distance_matrix) {
double dist = 0;
for (size_t i = 0; i < tour.size() - 1; ++i) {
dist += distance_matrix[tour[i]][tour[i + 1]];
}
dist += distance_matrix[tour[tour.size() - 1]][tour[0]]; // 回到起點
return dist;
}
// 隨機交換兩個城市以產生新解
vector<int> swap(const vector<int>& tour) {
vector<int> new_tour = tour;
int i = rand() % tour.size();
int j = rand() % tour.size();
std::swap(new_tour[i], new_tour[j]);
return new_tour;
}
// 模擬退火演算法
pair<vector<int>, double> simulated_annealing(const vector<vector<double>>& distance_matrix,
double initial_temperature,
double cooling_rate,
int max_iterations) {
int n = distance_matrix.size();
// 隨機初始化一個解
vector<int> current_solution(n);
for (int i = 0; i < n; ++i) current_solution[i] = i;
random_shuffle(current_solution.begin(), current_solution.end());
double current_distance = total_distance(current_solution, distance_matrix);
double temperature = initial_temperature;
vector<int> best_solution = current_solution;
double best_distance = current_distance;
// 主迴圈
for (int iteration = 0; iteration < max_iterations; ++iteration) {
vector<int> new_solution = swap(current_solution);
double new_distance = total_distance(new_solution, distance_matrix);
// 計算能量差
double delta_energy = new_distance - current_distance;
// 判斷是否接受新解
if (delta_energy < 0 || ((rand() / double(RAND_MAX)) < exp(-delta_energy / temperature))) {
current_solution = new_solution;
current_distance = new_distance;
// 更新最優解
if (current_distance < best_distance) {
best_solution = current_solution;
best_distance = current_distance;
}
}
// 降低溫度
temperature *= cooling_rate;
}
return {best_solution, best_distance};
}
// 主程式
int main() {
srand(time(0)); // 初始化隨機數生成器
// 測試用距離矩陣 (對稱矩陣)
vector<vector<double>> distance_matrix = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
double initial_temperature = 1000.0; // 初始溫度
double cooling_rate = 0.95; // 降溫率
int max_iterations = 1000; // 最大迭代次數
// 執行模擬退火演算法
auto result = simulated_annealing(distance_matrix, initial_temperature, cooling_rate, max_iterations);
// 輸出結果
cout << "最短距離: " << result.second << endl;
cout << "最佳旅程: ";
for (int city : result.first) {
cout << city << " ";
}
cout << endl;
return 0;
}
```
## 結論:
模擬退火通過隨機探索解空間，並根據溫度逐步降低的策略，能夠有效地尋找旅行推銷員問題的近似最優解。儘管該方法無法保證找到全局最優解，但它能在合理的時間內提供可接受的解，並且適用於規模較大的問題。
Sign in with Wallet
Connect another wallet