演化和蟻群算法的近似性能分析

《演化和蟻群算法的近似性能分析》是依託華南理工大學，由周育人擔任項目負責人的面上項目。

基本介紹

• 中文名：演化和蟻群算法的近似性能分析
• 項目類別：面上項目
• 項目負責人：周育人
• 依託單位：華南理工大學

項目摘要

大量的數值實驗顯示，演化和蟻群算法能夠有效地求解眾多的複雜最佳化問題。但對於NP-完全（難）問題，由於其難解性，人們也難以期待演化和蟻群算法在多項式時間內找到全部NP-完全（難）最佳化問題的精確解。本項目研究演化和蟻群算法關於NP-完全（難）最佳化問題的近似性能。針對命題公式的最大可滿足問題、最大團問題、旅行商問題等組合最佳化問題，分析兩種算法在最壞情況和平均情況下，在多項式時間或指數時間內達到的近似比；同時在輸入問題存在隨機擾動的假設下，分析兩算法的光滑近似性能；建立演化算法和蟻群算法近似性能分析框架和理論基礎。演化和蟻群算法近似性能的分析更接近算法設計與套用的真實情景，其研究有助於理解算法的工作原理和指導算法的套用。

結題摘要

演化算法和蟻群算法是求解複雜最佳化問題的隨機啟發式算法的出色代表。當前演化和蟻群算法理論研究遠遠落後於算法的數值實驗和真實套用。理論研究可以使人們更好地理解算法的工作原理，為算法的設計、算法的參數選取、算法的套用等指明改進的方向。本項目分析演化和蟻群算法關於NP-完全（難）最佳化問題的近似性能，其分析接近算法設計與套用的真實情景，其研究具有現實意義。 本項目在2012年1月至2015年12年期間，按項目計畫執行預定的研究任務,在演化算法與蟻群算法的近似性能理論分析以及演化算法設計取得若干進展和成果。分析了演化算法和蟻群算法關於一些經典NP完全（難）組合最佳化問題的近似性能,如最大割問題、多機調度問題、0-1背包問題、旅行商問題、Steiner樹問題、最小標籤生成樹問題等，研究結果表明演化算法和蟻群算法關於這些NP完全（難）組合最佳化問題可在平均多項式時間內獲得一些特定的近似比；討論了算法參數對於近似性能的影響；將演化算法和蟻群算法與其他局部搜尋算法從理論分析上進行比較。套用蟻群算法求解矩陣乘法問題、可滿足問題等；以及使用蜂群算法求解高維多目標最佳化問題等。完成學術論文16篇，其中14篇已發表，2篇已錄用待發表。完成論文包括11篇SCI期刊論文，主要成果發表在“Algorithmica”、“IEEE Transactions on Evolutionary Computation”、“ IEEE Transactions on Cybernetics”、“ European Journal of Operational Research”、“ Journal of Global Optimization”、“ Science China”等相關研究領域重要國際刊物。