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

杜　巍　李樹茁　陳煜聰

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

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

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