《蟻群最佳化算法的搜尋偏離性研究》是依託揚州大學，由陳崚擔任項目負責人的面上項目。
基本介紹
- 中文名：蟻群最佳化算法的搜尋偏離性研究
- 項目類別：面上項目
- 項目負責人：陳崚
- 依託單位：揚州大學
項目摘要,結題摘要,
項目摘要
蟻群算法對各類問題存在著不同程度的搜尋偏離性，這會對蟻群算法的性能產生負面影響，甚至不能收斂到全局最優解。本課題從如下幾個方面研究蟻群算法的搜尋偏離性: (1) 研究產生蟻群算法搜尋偏離的更多的原因和更全面的分類標準，提出反饋性和互動性兩種新的搜尋偏離，對這些搜尋偏離的完全性、分類標準的合理性進行論證。(2)提出並研究用量化的指標來衡量搜尋偏離的程度, 提出解分量的質量數、整體選擇機率等概念來建立衡量偏離的指標，研究所提出的指標的合理性、有效性。(3) 研究有效地預測及避免搜尋偏離的方法，提出通過信息素髮展趨勢的靜態分析來預測偏離性的思想，提出在每個解分量上加上學習因子來避免搜尋偏離的思想。本項目的研究有利於我們更全面地識別蟻群算法的搜尋偏離, 分析它存在的原因及對算法性能的影響，可以使我們在套用中針對具體問題有效地預測和防止搜尋偏離的發生，提高蟻群算法的最佳化性能、成熟性及實用性。
結題摘要
蟻群最佳化(ACO)算法是一種元啟發式的隨機搜尋算法，有很強的最佳化能力，適合於解決傳統搜尋方法難於解決的複雜問題。蟻群算法對各類問題存在著不同程度的搜尋偏離性，這會對蟻群算法的性能產生負面影響，甚至不能收斂到全局最優解。本課題研究蟻群算法的搜尋偏離性的產生原因、衡量指標以及有效地預測及避免搜尋偏離的方法。在已經發現的蟻群最佳化算法的兩種搜尋偏離（即表征性偏離、構建性偏離）之外，我們提出了兩種新的偏離，即反饋性偏離和互動性偏離。我們給出了反饋性偏離和互動性偏離的定義，並且舉例說明了它們的存在。我們針對各種偏離提出了衡量偏離大小的評價標準，並對該評價標準進行了測試，用實驗證明了我們的評價標準的合理性和有效性。我們提出了預測和糾正蟻群算法的搜尋偏離的有效方法。我們分別對傳統的蟻群算法和我們的方法在不同問題上的收斂性進行了理論證明，我們的實驗結果也充分說明了我們改進的蟻群算法可以有效地糾正搜尋偏離，最終收斂於全局最優解。為了避免蟻群算法的搜尋偏離，加強解群體的多樣性，我們提出了三種改進的螞蟻路徑選擇策略，以增加解的多樣性，使改進的算法能夠有效地避免搜尋偏離。我們從理論上證明了所提出的各種選擇策略比傳統的“輪盤賭”方式有更好的性能, 並用實驗驗證了三種選擇策略的有效性。實驗結果表明，我們所提出的方法可以有效地增加解的多樣性，避免了搜尋偏離的產生。我們利用螞蟻在圖中遊走的所展示的很強的最佳化性能，提出複雜網路中的社區檢測的蟻群算法，解決複雜度較高的重疊社區挖掘和動態社區挖掘的問題。在多個實際數據集上的實驗結果表明，我們的算法不但能較快地識別實際網路的社區結構，而且可以獲得比其他方法更好的劃分效果。我們還用上述理論成果解決數據挖掘、生物信息學、組合最佳化等領域的問題，取得了很好的套用效果.
