一種求解多維背包問題的小世界算法
2009-04-03 01:18:04杜巍李樹茁陳煜聰
西安交通大學(xué)學(xué)報(bào) 2009年2期
杜 巍 李樹茁 陳煜聰
摘要：針對遺傳算法求解復(fù)雜組合優(yōu)化問題時(shí)出現(xiàn)早熟收斂和種群多樣性喪失等問題，提出了一種解決多維背包問題的二進(jìn)制編碼小世界算法(BSWA)。BSWA算法依據(jù)社會學(xué)中的小世界現(xiàn)象搜索機(jī)理，采用類似遺傳變異操作的局部搜索，而非遺傳算法中的交叉操作。針對多維背包問題的多約束性，BSWA算法還按照價(jià)值資源比大小對不可行解進(jìn)行貪婪修正，以保證求解的正確性。與遺傳算法相比，BSWA可以在一定程度上克服早熟收斂，在保持種群多樣性和求解精度方面均體現(xiàn)出較大的優(yōu)勢，具有解決復(fù)雜組合優(yōu)化問題的潛力。對55個(gè)標(biāo)準(zhǔn)的多約束0-1背包問題進(jìn)行了50次隨機(jī)實(shí)驗(yàn)，結(jié)果表明，BSWA算法對于其中72.73％的問題可以次次獲得最優(yōu)解，對于其他不能次次求解到最優(yōu)解的問題，也可以獲得非常接近全局最優(yōu)解的滿意解。
關(guān)鍵詞：小世界算法；多維背包問題；貪婪修正算子
中圖分類號：TP183文獻(xiàn)標(biāo)志碼：A文章編號：0253—987X(2009)02—010—05
西安交通大學(xué)學(xué)報(bào)2009年2期
- 西安交通大學(xué)學(xué)報(bào)的其它文章
- 西安交通大學(xué)獲得２００８年度國家科學(xué)技術(shù)獎(jiǎng)５項(xiàng)
- 西安交通大學(xué)獲第１８屆國際核工程大會舉辦權(quán)
- 張心湜院士受聘為西安交通大學(xué)教授
- 西安交通大學(xué)機(jī)械學(xué)院在高檔數(shù)控機(jī)床科研領(lǐng)域獲重大進(jìn)展
- 西安交通大學(xué)兩團(tuán)隊(duì)獲２００８年度國家級教學(xué)團(tuán)隊(duì)榮譽(yù)稱號
- 銅長條薄板在疲勞載荷下裂紋聚合的試驗(yàn)研究和一個(gè)新發(fā)現(xiàn)