文章編號:(2006)0104二進制改進粒子群算法在背包問題中的應用上海理工大學管理學院上海)摘要背包問題的二進制編碼的粒子群算法,闡明了該算法求解背包問題的具體實現過程為了提高粒子群算法的收斂速度,在傳統的二進制編碼的粒子群算法中嵌入了記憶功能。通過對其他文獻中仿真實例的計算和結果比較,表明該算法在尋優能力、計算速度和穩定性方面都超過了文獻中提到的遺傳算法和模擬退火算法。提出的求解背包問題的二進制改進粒子群算法,同樣可以應用于其他離散優化問題記憶機制中圖分類號hina))d。
ed。。背包問題)是運籌學一個典型的優化難理中的資源分配、投資決策、裝載問題、材料切割及預算控制等問題,并且還常常作為其他問題的子問題加以研究對背包問題求解方法的研究,無論是在理論上還是在實踐中都具有一定的意義。從計算復雜性理論來看mial)完全問題是否存在多項式時間有效算法尚不可知如貪心算法、遺傳算法及模擬退火算法等年提出的收稿日期13基金項目T0502)作者簡介一種新的進化算法,它源于對鳥群群體尋食運動行為研究結果的啟發。
由于粒子群優化算法有收斂速、運算簡單、易于實現及魯棒性好等優點,該算法一經提出立即引起了進化計算、計算機和管理等領域學者們的廣泛關注,并取得了大量的研究成果這些研究成果大部分是對各類多維連續空間優化問題研究所取得的,但對離散優化問題中的應用研究位置值。每一個擇是否裝入背包。如果ij制改進粒子群算法,經大量的仿真實驗取得了很好的效果。求解背包問題的二進制改進粒子群算法的流程如下確定參數值確定種群規模確定學習因子c1初始化所有粒子的位置和速度每個粒子的位置由背包問題的描述背包問題的一般提法為個物品s1些物品裝入背包可使在背包的容量限制之內所裝物品的總價值最大物品sj放入背包則該問題的數學模型為隨機生成,其中]之間的隨機數。每個粒子的速度由。t求解背包問題的二進制改進粒子群算法粒子群算法是繼蟻群算法之后又一群體智能算計算粒子的適應值并更新記憶庫粒子的適應值為,該算法模擬鳥群飛行覓食的行為,通過鳥群之間的集體協作使群體達到目的。在粒子群算法中,每個粒子根據自己的飛行經驗和同伴的飛行經驗來調整自己的飛行速度和方向,從而尋找問題的最優解是一種隨機搜索算法,而且是從多個初始點開始進行搜索的完全背包問題算法,比較容易克服局部最優問題。
標準粒子群算法主要適用于連續空間函數的優化問題,如何將粒子群算法應用于離散空間優化問題是粒子群算法的主要研究方向之一表示整個種群進化代所經歷的最好位置。如果并將GB存入記憶庫。檢查結束條件是否滿足首先引入用本文提出的二進制改進粒子群算法來求解仿真實例記憶更新粒子數11,最大進化代數為完全背包問題算法,128內存的計算機上獨立運行,平均耗時不到1s,平均進化代數為51GA)算法的最優值為)算法在算法在100時的最優值為15955,遺傳退火進化算法GAEA)算法的最優值為16102從以上的比較可以看出,本文提出的求解背包問題的二進制改進粒子群算法在最優值方面優于文獻GA算法和SA算法GAEA算法相同(10)使結果值處于13)來更新粒子的位置和速度,然后轉步驟50法在平均個可能解中找到了最優解,同時在50次的隨機實驗中,均達到了文獻從這些數據可以看出,本文的算法在速度方面和穩定性方面具有很好的效果。ijc2仿真實驗為了更好為本文的算法編寫了程序,選取文獻中的仿真實例進行求解,并將求解的結果與文獻的結果進行了對比結果表明本算法的有效性,同時也體現了本算法的優越性。
仿真實例收斂曲線Fig。仿真實例用本文提出的二進制改進粒子群算法來求解仿真實例11,最大進化代數為,128內存的計算機上獨立運50次的運行結果的目標函數最優值都為077,貪婪算法的最優值為本文提出的求解背包問題的二進制改進粒子群算法在最優值方面優于文獻中的簡單遺傳算法和貪婪算法,與混合遺傳算法相同。本文的算法在平均左右的時間內從250個可能解中找到了最優解,同時在50次的隨機實驗中,均達到了文獻從這些數據可以看出,本文的算法在速度方面和穩定性方面具有很好的效果,表明該算法不論是在尋優能力方面,還是在速度和穩定性方面都優于文獻中提到的遺傳算法和模擬退火算法。本文為粒子群算法應用于其他離散優化問題,提供了很好的參考。參考文獻,2001,,1995,’lCo wor ks 基于改進粒子群算法求解單級多資源 2005,10 。
swarm op level lot he12t Co t ress,2006 ,602 EBER HARD swarm op heco ,1997 swarm op tio ,2003 上海理工大學學報,2004 ,26 南昌航空工業學院學報,1998 ,12 收斂曲線Fig。 curve nd 結束語粒子群算法目前主要在連續優化問題的應用中 取得了大量的研究成果,本文從促進粒子群算法在 離散優化問題中的應用的角度出發 ,提出了用于求 背包問題的二進制改進粒子群算法,并闡明 為了加快粒子群算法的收斂速度 ,本文在傳統粒子群算法中引入了記憶機制。 通過對其他文獻中的兩個仿真實例的計算和結果比