一種求解多維背包問題的小世界算法

杜　巍　李樹茁　陳煜聰

摘要：針對遺傳算法求解復雜組合優化問題時出現早熟收斂和種群多樣性喪失等問題，提出了一種解決多維背包問題的二進制編碼小世界算法(BSWA)。BSWA算法依據社會學中的小世界現象搜索機理，采用類似遺傳變異操作的局部搜索，而非遺傳算法中的交叉操作。針對多維背包問題的多約束性，BSWA算法還按照價值資源比大小對不可行解進行貪婪修正，以保證求解的正確性。與遺傳算法相比，BSWA可以在一定程度上克服早熟收斂，在保持種群多樣性和求解精度方面均體現出較大的優勢，具有解決復雜組合優化問題的潛力。對55個標準的多約束0-1背包問題進行了50次隨機實驗，結果表明，BSWA算法對于其中72.73％的問題可以次次獲得最優解，對于其他不能次次求解到最優解的問題，也可以獲得非常接近全局最優解的滿意解。

關鍵詞：小世界算法；多維背包問題；貪婪修正算子

中圖分類號：TP183文獻標志碼：A文章編號：0253—987X(2009)02—010—05