1.1 SA演算法參數分析
1.1.1 實驗目的
分析模擬退火演算法 (SA) 在不同參數組合下的性能表現，找出最適合的參數配置。主要著重於以下參數的影響：
- 初始溫度 (T0)
- 終止溫度 (Tf)
- 降溫係數 (Beta)
- 每個溫度的迭代次數 (Nummax)
1.1.2 實驗環境與設計
固定參數
- 災區點數量: 60
- 地圖模型: DatongModel
- 偵測半徑: 50
- 每組參數重複次數: 30
變化參數
| 參數 | 值範圍 |
|---|---|
| 初始溫度 (T0) | [100, 200, 250, 500, 750, 1000, 1250, 1500] |
| 終止溫度 (Tf) | [1, 5, 10, 15, 20] |
| 降溫係數 (Beta) | [0.87, 0.90, 0.93, 0.96, 0.99] |
| 每溫度迭代次數 (Nummax) | [5, 20, 50, 100, 200] |
| 最大迭代次數 (Itermax) | [10,50,100,200,300,500, 1000, 1500, 2000] |
基準參數組合
T0 = 1000
TF = 10
Itemax = 500
Nummax = 50
Beta = 0.91.1.3 實驗設計
實驗分組
- 1. 基準組: 使用基準參數組合
- 2. T0變化組: 改變T0，其他參數維持基準值
- 3. TF變化組: 改變TF，其他參數維持基準值
- 4. Itemax變化組: 改變Itemax，其他參數維持基準值
- 5. Nummax變化組: 改變Nummax，其他參數維持基準值
- 6. Beta變化組: 改變Beta，其他參數維持基準值
實驗流程
// 偽代碼
for each 參數組別:
for each 參數值:
for 重複30次:
1. 初始化SA演算法
2. 執行求解過程
3. 記錄結果(距離、時間、最佳解、最差解)
計算統計值(平均距離、平均時間、整體最佳解、最差解)1.1.3 實驗結果分析
初始溫度(T0)的影響
- 最佳表現：T0=1250時，平均路徑距離為47763.60
- 執行時間隨T0增加而增加（100: 2.16秒 -> 1500: 5.11秒）
- 中等的初始溫度(1000-1250)在本實驗中表現更好
結束溫度(TF)的影響
- 平均距離：TF=20時為50155.80，表現穩定
- 執行時間與TF成反比：TF=1時13.47秒，TF=20時4.49秒
- TF=20時具有最佳的時間效率與解質量平衡
最大迭代次數(Itemax)的影響
- 最佳平均距離：Itemax=300時達到48501.60
- 執行時間與迭代次數關係相對穩定（約5-6秒）
- 適中的迭代次數(300)能在時間和解質量間取得平衡
內部迭代次數(Nummax)的影響
- 最佳表現：Nummax=100時平均距離為47200.40
- 執行時間隨Nummax增加（5: 0.60秒 -> 200: 21.95秒）
- 較大的Nummax值(100)能得到更好的解，但執行時間較長
降溫速率(Beta)的影響
- 最佳平均距離：Beta=0.99時達到46990.60
- 執行時間隨Beta增加而顯著增加（0.87: 4.15秒 -> 0.99: 57.75秒）
- Beta=0.93提供了良好的解質量(48088.60)和時間(7.96秒)平衡
最佳參數組合建議
| 參數 | 建議值 | 說明 |
|---|---|---|
| T0 | 1250 | 最佳的初始解和執行效率 |
| TF | 20 | 最佳解和執行時間的平衡 |
| Itermax | 300 | 達到最佳解質量 |
| Nummax | 100 | 達到最佳解質量 |
| Beta | 0.93 | 良好的解質量和執行效率平衡 |
1.1.4 實驗結果
使用DatongModel地圖模型，共60個災區點，偵測半徑50，每組參數執行30次。以下為詳細實驗數據：
基準組實驗結果
- 平均距離：49144.60
- 平均執行時間：5.07秒
- 最佳解：45745.00
- 最差解：54775.00
初始溫度(T0)實驗結果
| T0值 | 平均距離 | 平均時間(秒) | 最佳解 | 最差解 |
|---|---|---|---|---|
| 100 | 50197.60 | 2.16 | 46833.00 | 52598.00 |
| 200 | 53998.60 | 3.08 | 52271.00 | 54712.00 |
| 250 | 48846.00 | 3.03 | 44158.00 | 53668.00 |
| 500 | 49577.40 | 3.91 | 46810.00 | 55651.00 |
| 750 | 50231.60 | 4.64 | 42661.00 | 56350.00 |
| 1000 | 48874.20 | 4.48 | 45151.00 | 53529.00 |
| 1250 | 47763.60 | 4.89 | 44624.00 | 49377.00 |
| 1500 | 48694.40 | 5.11 | 45807.00 | 53613.00 |
結束溫度(TF)實驗結果
| TF值 | 平均距離 | 平均時間(秒) | 最佳解 | 最差解 |
|---|---|---|---|---|
| 1 | 50358.40 | 13.47 | 41276.00 | 52208.00 |
| 5 | 51204.00 | 16.31 | 47422.00 | 54951.00 |
| 10 | 51070.40 | 5.46 | 49304.00 | 53276.00 |
| 15 | 52410.00 | 5.17 | 48169.00 | 57222.00 |
| 20 | 50155.80 | 4.49 | 46024.00 | 53440.00 |
最大迭代次數(Itemax)實驗結果
| Itemax值 | 平均距離 | 平均時間(秒) | 最佳解 | 最差解 |
|---|---|---|---|---|
| 10 | 51926.40 | 1.26 | 46977.00 | 54808.00 |
| 50 | 49165.80 | 5.45 | 45972.00 | 55696.00 |
| 100 | 49918.80 | 5.53 | 47381.00 | 53648.00 |
| 200 | 50180.60 | 5.12 | 43890.00 | 56193.00 |
| 300 | 48501.60 | 5.44 | 45984.00 | 50871.00 |
| 500 | 50718.80 | 5.73 | 46730.00 | 54907.00 |
| 1000 | 50381.80 | 5.49 | 46263.00 | 54992.00 |
| 1500 | 49581.60 | 5.36 | 46085.00 | 57120.00 |
| 2000 | 51286.40 | 5.93 | 48703.00 | 53639.00 |
內部迭代次數(Nummax)實驗結果
| Nummax值 | 平均距離 | 平均時間(秒) | 最佳解 | 最差解 |
|---|---|---|---|---|
| 5 | 53365.60 | 0.60 | 50401.00 | 57640.00 |
| 20 | 50036.80 | 2.17 | 44657.00 | 56247.00 |
| 50 | 50771.60 | 5.30 | 48601.00 | 54291.00 |
| 100 | 47200.40 | 11.58 | 43683.00 | 49459.00 |
| 200 | 48155.00 | 21.95 | 44965.00 | 52622.00 |
降溫速率(Beta)實驗結果
| Beta值 | 平均距離 | 平均時間(秒) | 最佳解 | 最差解 |
|---|---|---|---|---|
| 0.87 | 48461.20 | 4.15 | 47448.00 | 49561.00 |
| 0.90 | 49647.00 | 5.72 | 45951.00 | 53561.00 |
| 0.93 | 48088.60 | 7.96 | 46852.00 | 51423.00 |
| 0.96 | 48411.20 | 14.08 | 45287.00 | 52641.00 |
| 0.99 | 46990.60 | 57.75 | 43826.00 | 51288.00 |
建議參數組合
- T0: 1250
- TF: 20
- Itermax: 300 (=災區點數量60 *5) 為了公平，IG與Tabu都會用以此為基準
- Nummax: 100
- Beta: 0.93
: