|
|
|
局部搜索算法是一種重要的求解組合優化問題的啟發式演算法，由於簡單且易於理解，其已受到越來越廣泛的重視。不同局部搜索算法的差別主要在於評估函數、鄰域結構以及狀態轉移函數的設計。
《局部搜索算法及其在組合優化問題中的應用》針對較小加權頂點覆蓋、較小有容量支配集、較小連通支配集幾個經典的NP難組合優化問題，提出合理的評估函數、鄰域結構以及狀態轉移函數，設計出的局部搜索算法。
叢書序
前言
第1章 緒論 1
1.1 組合優化問題 1
1.2 組合優化問題的求解方法 2
1.2.1 演算法 2
1.2.2 啟發式演算法 2
1.2.3 兩類演算法的優缺點 3
1.3 相關工作 4
1.3.1 加權頂點覆蓋問題 4
1.3.2 有容量支配集問題 6
1.3.3 連通支配集問題 7
1.3.4 頂點覆蓋與支配集之間的關係 9
1.4 本書的研究內容和貢獻 11
第2章 局部搜索演算法 13
2.1 局部搜索概述 13
2.2 基本概念 14
2.3 局部搜索演算法簡介 16
2.4 局部搜索演算法的核心技術 22
2.5 本章小結 24
第3章 加權頂點覆蓋問題求解 26
3.1 基本符號和定義 26
3.2 基於動態邊權的打分策略 28
3.2.1 動態邊權 29
3.2.2 打分策略 29
3.2.3 快速增量評估技術 30
3.3 加權格局檢測策略 32
3.4 頂點選擇策略 34
3.5 DLSWCC演算法的描述 35
3.6 實驗分析 38
3.6.1 基準實例 38
3.6.2 現有演算法介紹 40
3.6.3 加權格局檢測策略的有效性 41
3.6.4 動態打分策略的有效性 43
3.6.5 快速增量評估技術的有效性 45
3.6.6 SPI組實例實驗結果 46
3.6.7 MPI組實例實驗結果 49
3.6.8 LPI組實例實驗結果 52
3.6.9 MGI組實例實驗結果 54
3.7 本章小結 56
第4章 有容量支配集問題求解 58
4.1 基本概念 58
4.2 基於頂點懲罰的打分策略 61
4.2.1 頂點懲罰策略 61
4.2.2 頂點打分策略 62
4.2.3 頂點選擇方法 62
4.3 兩種模式的被支配頂點選擇策略 64
4.4 強化策略 66
4.5 LS_PD演算法的描述 67
4.6 實驗分析 69
4.6.1 基準實例 69
4.6.2 現有演算法介紹 70
4.6.3 固定容量的實驗結果 71
4.6.4 變化容量的實驗結果 74
4.6.5 討論 78
4.7 本章小結 81
第5章 連通支配集問題求解 83
5.1 基本概念 83
5.2 GRASP演算法框架 85
5.3 GRASP求解連通支配集問題 86
5.3.1 貪婪隨機構造階段 86
5.3.2 局部搜索階段 89
5.4 實驗分析 92
5.4.1 基準實例 92
5.4.2 現有演算法介紹 95
5.4.3 求解LPRNMR實例的實驗結果 96
5.4.4 求解隨機實例的實驗結果 97
5.4.5 求解MLSTP實例的實驗結果 99
5.5 本章小結 102
第6章 總結與展望 103
6.1 總結 103
6.2 展望 104
參考文獻 106
