《演化算法時間複雜性及相關問題》是依託武漢大學，由丁立新擔任項目負責人的面上項目。
基本介紹
- 中文名：演化算法時間複雜性及相關問題
- 項目類別：面上項目
- 項目負責人：丁立新
- 依託單位：武漢大學
項目摘要,結題摘要,
項目摘要
演化算法時間複雜性及其相關問題是演化計算基礎理論研究的前沿與難點。本項目擬運用隨機穩定性理論、動力系統理論、譜分析理論等技術手段，研究演化算法時間複雜性與動力學行為分析的某些待解問題。具體研究內容為：基於一般最佳化模型，研究可用於嚴格分析群體演化算法時間複雜性的基本手段與方法，定量刻畫問題類型、群體規模、遺傳運算元以及與問題相關聯的啟發式知識等關鍵因素對演化算法時間複雜度的影響，研究演化算法在多項式時間內求解典型NP-難度問題所得近似解的質量；進一步地，研究與算法時間複雜性相關聯的最優轉移運算元存在的譜條件，探索有限群體模型與無限群體模型的譜關係，推廣Karlin定理，使之適應多遺傳運算元的演化算法動力學行為描述。項目的意義在於：建立演化算法時間複雜度估計的新手段，解決演化算法時間複雜性與動力學行為分析中的某些公開理論問題；為相關理論研究者提供參考，為相關從業者在實踐中選擇和設計演化算法提供借鑑。
結題摘要
演化算法計算複雜性是演化計算理論研究領域的重要課題，也是目前演化計算基礎理論研究的薄弱環節。通過三年的研究，本項目完成的研究工作和取得的研究成果如下：（1）運用非時齊Markov過程理論，研究了自適應演化算法模型的漸近行為和時變特徵，建立了可用於分析一般演化算法時間複雜度的技術手段和理論框架；（2）基於建立的理論框架，綜合運用適應值分層技術和截尾不等式，獲得了一些典型計算問題的時間複雜度估計；（3）研究了對應於演化算法的隨機樹的產生過程刻畫，探討了演化算法對應的隨機樹上的機率結構與機率性質，為引入隨機樹方法作為演化算法時間複雜度估計的新手段奠定了理論基礎；（4）運用Markov鏈理論和動力系統理論，研究了遺傳運算元、選擇策略、群體規模對EA時間複雜度的影響，給出了演化算法對應的轉移運算元的譜與算法時間複雜度的理論關係；（5）研究了基於演化算法的近似解質量與算法時間複雜度的關係，為演化算法有效求解複雜計算問題提供了一定理論支持；（6）研究了elitist演化算法的收斂速度與平均首達時間、量子演化算法的收斂性、群體規模可變的自適應演化算法的時間複雜性問題，得到了這些經典演化算法模型的極限行為刻畫；（7）研究了演化算法的難易問題的劃分與度量準則，基於演化算法所對應的轉移運算元的譜特徵研究演化算法的動力學行為，基於推廣的Karlin定理刻畫了多遺傳運算元演化算法的動力學行為。項目的成果已經發表或錄用在國內外核心學術刊物和相關學術會議上，已發表學術論文37篇。本項目的研究工作建立了演化算法時間複雜性分析的基礎框架，解決了演化算法時間複雜性分析的一些公開理論問題。
