近幾年，在進化計算領域興起了一類新型的最佳化算法，稱為分散搜尋(Scatter Search，SS)。該算法迅速成為進化計算領域的研究熱點和解決複雜組合最佳化問題的有效方法。SS算法最早在1977 年由Glover 為解決整數規劃問題而提出，但直到最近幾年才被學者們廣泛地關注與套用。SS採用基於種群的全局搜尋策略，運用“分散-收斂集聚”的智慧型疊代機制，在參考集中形成高質量和多樣性的解，並通過子集合併方法和參考集更新方法，求取問題的全局最優解或滿意解。相比於其它進化算法，如遺傳算法，SS 由於其參考集的記憶能力，使其可以動態跟蹤當前的搜尋情況，以調整其搜尋策略，這樣可以減少搜尋過程的隨機性，更加注重於採用一些系統性的方法來構建新解。同時，SS 具有柔性的框架，其中的每種機制都可用多種方法予以實現。SS 算法整合了多種有效機制，包括多樣性生成方法、局域搜尋方法、以及路經重連方法等，這使得該算法可以快速獲得滿意解，同時避免過早地陷入局部最優解，從而能夠有效求解一些常規數學規劃方法難以求解的最佳化問題。目前，SS 已經在許多領域得到了套用，譬如物流與供應鏈、生產管理、圖像處理、數據挖掘、信號處理和運籌學等領域。文獻檢索時也稱SS算法。
基本介紹
- 中文名：分散搜尋算法
- 外文名：Scatter Search Algorithm
1 基本分散搜尋
SS算法作為一種進化算法，很少依賴搜尋過程的隨機性，而是採用其框架中一系列系統性方法來實現對最佳化問題的求解,其本質是一種基於整數編碼的具有保優思想的亞啟發式算法。Glover 在1998 年定義了SS 的模版，並提出了模版中關鍵部分的實現方法。Laguna 等在2003 年進一步擴展了算法，形成SS的基本框架，並用C 語言完整的描述了算法。SS 框架中通常包含5 個系統性的子方法，即多樣性產生方法、參考集更新方法、子集產生方法、子集合併方法和解改進方法。
SS算法作為一種進化算法，很少依賴搜尋過程的隨機性，而是採用其框架中一系列系統性方法來實現對最佳化問題的求解,其本質是一種基於整數編碼的具有保優思想的亞啟發式算法。Glover 在1998 年定義了SS 的模版，並提出了模版中關鍵部分的實現方法。Laguna 等在2003 年進一步擴展了算法，形成SS的基本框架，並用C 語言完整的描述了算法。SS 框架中通常包含5 個系統性的子方法，即多樣性產生方法、參考集更新方法、子集產生方法、子集合併方法和解改進方法。
