求解多目標最小生成樹的改進多目標蟻群算法

0 引言

最小生成樹問題(MST)構造一個帶權圖的最小代價生成樹，在網絡優化中具有舉足輕重的作用。目前，圖論中已有一些經典的求解最小生成樹算法，如Kruskal和Prim算法等，其計算復雜度為多項式時間，但當給MST增加約束條件或問題目標為多個時，相應的問題稱為多目標最小生成樹問題，而且問題本身也變成了一個NP完全問題。因此近年來許多啟發式算法應運而生，其中最具代表的是Zhou等人提出一種求解多目標最小生成樹問題的遺傳算法。相應地還給出一種計數算法用于計數所有非劣最優解，但該計數算法所求解到的非劣最優解是不精確的。研究者繼而給出一種求解的多目標遺傳算法，并用改進的計數算法進行性能評價，結果表明提出的多目標遺傳算法的有效性。