面向實例的群體智慧型最佳化算法及其套用研究

《面向實例的群體智慧型最佳化算法及其套用研究》是依託西安交通大學，由任志剛擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：面向實例的群體智慧型最佳化算法及其套用研究
• 項目類別：青年科學基金項目
• 項目負責人：任志剛
• 依託單位：西安交通大學

中文摘要

以蟻群和粒子群為代表的群體智慧型最佳化算法近年得到了廣泛研究和套用。為保障對不同問題的適應能力，這類算法一般提供一些可選運算元和可調參數。由於數學描述的複雜性，當前主要基於簡單實驗配置這些運算元和參數，無法反映待解決問題實例的具體特徵，而有關算法性能預測方面的研究更為少見。本項目擬將機器學習的思想引入群體智慧型領域，在元學習框架下，通過對大量歷史實例求解數據進行離線地分類和回歸學習，挖掘群體智慧型算法與問題屬性、運行時間的內在關係，並據此提出一種面向實例的算法線上配置和性能預測方法，解決其中的關鍵理論和技術問題。在套用方面，擬將取得的理論成果套用於衛星測控資源調度問題，實現一種支持線上配置和性能預測的群體智慧型調度算法。本項目的實施有助於充實群體智慧型的理論基礎，促進群體智慧型與機器學習的學科交叉，同時有望為衛星測控資源調度問題提供一套切實可行的解決方案。

結題摘要

本項目採用機器學習的思想和方法，通過系統分析群體智慧型最佳化算法在求解歷史實例時所積累的大量數據，獲取算法性能與算法配置、問題屬性之間的關係，用以指導新實例的求解，並對求解性能進行評價。 以MKP問題為例，研究分析了問題屬性的抽取方法，確定了影響問題難易程度和算法適應度的關鍵屬性；通過在屬性空間進行聚類分析，構建了MKP的元實例集。在採用蟻群算法求解MMKP問題時，根據MMKP問題中對象的組間可分性，提出了一種面向單組的狀態轉移運算元；根據MMKP問題的約束特徵，提出了一種不可行性指標和修復運算元。仿真實驗表明，由此形成的AL-MMKP算法具有很強的競爭力。在採用粒子群算法求解連續最佳化問題時，根據問題的多模特徵，提出了一種新型的學習規則，該規則綜合利用“學習標本”的適應度和分布信息，提高了搜尋效率；對影響算法性能的關鍵參數進行了理論研究，給出了一種魯棒且簡單的參數設定規則。統計分析表明，由此形成的SLPSOA算法優於已有的PSO算法。基於序最佳化理論，提出了一種群體智慧型算法解性能評價方法。該方法首先通過聚類分析，將採樣樣本均勻化分區；然後通過核密度估計獲得分區後各子區域的適應度分布，在此基礎上計算出可以用來評價解性能的對準機率。通過對比分析該方法的理論計算結果與實際統計結果，驗證了該方法的有效性。針對實際的衛星測控資源調度問題，以可見弧段為調度對象，建立了該問題的複合獨立集模型；分別在單目標和多目標框架下，提出了兩種蟻群求解算法；並在多目標框架下，利用目標向量之間的間距概念，提出了一種解集分布度量方法，進而實現了對解性能的評價。 在項目執行期間，發表論文10篇，協助培養博士生2名，獨立培養碩士生1名，實現了預期目標。