1.2 IG演算法參數分析

1.2.1 實驗目的

分析迭代貪婪演算法 (IG) 在不同參數組合下的性能表現，找出最適合的參數配置。

1.2.2 實驗環境與設計

固定參數
  • 災區點數量: 60
  • 地圖模型: DatongModel
  • 偵測半徑: 50
  • 每組參數重複次數: 30
  • Itermax (Iteration Max): 300 (災區點數量60 *5 ;與SA一致)
變化參數
參數 值範圍
Tk (Temperature K) [1, 5, 10, 20, 50, 100]
α (移除α數量候選節線) [1, 5, 10, 20, 50]
實驗分組與設計
實驗分組
  • 1. Tk變化組: 改變Tk，維持α=5
  • 2. α變化組: 改變α，維持Tk=5

1.2.3 實驗設計細節

實驗設計概述
實驗流程
// 偽代碼

    for each 參數值:
        for 重複30次:
            1. 初始化IG演算法
            2. 執行求解過程
            3. 記錄結果(距離、時間、最佳解、最差解)
        計算統計值(平均距離、平均時間、整體最佳解、最差解)
實驗數據總覽
參數名稱 參數值 執行次數 平均距離 平均時間 最佳解 最差解
Tk 1 30 52134 1.31 45435 57190
Tk 5 30 51601 1.74 41893 58314
Tk 10 30 52422.87 0.71 47078 61356
Tk 20 30 51962.23 0.63 41609 60183
Tk 50 30 52709 0.62 39432 60703
Tk 100 30 51622 0.60 44789 57538

1.2.4 程式實作規劃

需要建立的類別
  • 1. IGParameterRunner：負責執行不同參數組合的 IG 演算法，並收集實驗結果。
  • 2. IGExperimentResultCollector：負責將實驗結果輸出到 WebSite 的網頁。
實作步驟
  • 1. 建立 IGParameterRunner 類別，並實作參數設定和結果收集功能。
  • 2. 建立 IGExperimentResultCollector 類別，並實作將結果輸出到 WebSite 網頁的功能。
  • 3. 實作各參數組的實驗方法。
  • 4. 加入執行進度輸出。
  • 5. 實作結果收集和匯出功能。

1.2.5 結果分析

Tk參數實驗結果
Tk參數實驗結果
Tk值 平均距離 平均時間(秒) 最佳解 最差解
1 52134 1.31 45435 57190
5 51601 1.74 41893 58314
10 52422 0.71 47078 61356
20 51962 0.63 41609 60183
50 52709 0.62 39432 60703
100 51622 0.60 44789 57538
Tk參數對平均距離及執行時間的影響
關鍵指標
  • 最佳Tk: 5
    平均距離: 51601.27
  • 最佳解: 39432.00
    （Tk = 50）
  • 最差解: 61356.00
    （Tk = 10）
Tk參數分析結果
1. 解品質分析:
  • Tk值從1到100的平均距離變化不大,都在51,600-52,700之間
  • Tk=5時達到最佳平均距離51601.27
  • Tk=50時獲得最佳解39432.00
  • 各Tk值都能獲得相近的解品質
2. 執行時間分析:
  • Tk對執行時間的影響很小,各組平均執行時間都在0.60-1.74秒之間
  • Tk=5時執行時間略高(1.74秒),其他參數值都維持在0.60-1.31秒左右
α參數實驗結果
α參數實驗結果
α值 平均距離 平均時間(秒) 最佳解 最差解
1 52327 0.05 44050 71307
5 51179 0.04 43023 70188
10 49619 0.04 39739 67846
20 50980 0.04 44383 70158
50 50093 0.04 39468 68939
α參數對平均距離及執行時間的影響
關鍵指標
  • 最佳α: 10
    平均距離: 49619
  • 最佳解: 39468
    （α = 50）
  • 最差解: 71307
    （α = 1）
α參數分析結果
1. 解品質分析:
  • α=10時達到最佳平均距離49619
  • α=50時獲得較佳解39468
  • 較大的α值(10-50)能獲得較佳的解品質
2. 執行時間分析:
  • α對執行時間影響很小,各組平均執行時間都在0.04-0.05秒之間
  • 執行時間非常穩定,不同α值之間差異很小
最佳參數組合建議
建議參數組合:
  • Tk = 5 (提供最佳平均距離)
  • α = 10 (提供最佳平均距離)
理由:
  • 1. Tk=5時可以獲得最佳平均距離,且執行時間穩定
  • 2. α=10時達到最佳平均距離,且執行時間非常穩定
  • 3. 此參數組合在解質量和執行效率之間取得了良好的平衡