求解大規模多背包問題的高級人工魚群算法

李 迎, 張 璟, 劉 慶, 張 偉

(1. 西安理工大學自動化與信息工程學院, 陜西 西安 710048; 2. 西安理工大學計算機科學與工程學院, 陜西 西安 710048; 3. 北京天云融創軟件技術有限公司, 陜西 西安 710075)

0 引 言

多背包問題(multiple knapsack problem,MKP)是一個很經典的NP-Hard組合優化問題[1-2],它可以作為很多實際問題的模型,例如多資源調度、交通規劃、資本預算、材料切割等[3-4]。

目前求解多背包問題的算法主要分為兩大類,第一類是傳統的搜索算法,例如精確求解法、啟發式算法、元啟發式算法等[5-6],均取得了一些成效,但是隨著實際應用中問題規模的不斷擴大,嚴苛的約束和指數級增長的解空間使得常規算法很難得到最優解。另一類是基于群智能的進化算法,例如遺傳算法(genetic algorithm,GA)[7]、粒子群優化(particle swarm optimization,PSO)算法[8]、蟻群優化(ant colony optimization,ACO)算法[9]和人工魚群算法(artificial fish swarm algorithm,AFSA)等,它們由于實現簡單、魯棒性強等優點被越來越廣泛的應用[10-16]。其中,GA是基于個體競爭的尋優機制,在染色體進化和淘汰的過程中,種群多樣性迅速下降,容易陷入早熟。PSO算法更注重于群體之間的學習,單個粒子對于周圍環境缺乏自主搜索能力,算法后期如果陷入局部極值很難跳出。ACO算法是利用信息素的累積和揮發來指導個體尋優的,算法初期搜索盲目性大,收斂速度慢,后期也存在算法停滯的問題。AFSA中人工魚個體在搜索的過程中,應用多種尋優行為,例如覓食、追尾、追尾等,可以很好地平衡探尋新解域和精細搜索當前解域這兩種不同的搜索模式,所以具有良好的克服局部極值的能力,在求解MKP問題中取得了優于GA、PSO算法以及ACO算法的效果[17-19]。

本文針對AFSA在求解大規模MKP時存在算法后期收斂速度慢、搜索精度低的問題,提出了一種針對大規模多背包問題的高級人工魚群算法(advanced artificial fish swarm algorithm for large scale multiple knapsack problem,AAFSA-LMKP)。本文算法通過改進AFSA的初始化方式,優化人工魚個體的行為算子,加快了算法的收斂效率。同時,引入視野和步長這兩個參數的動態調整,添加人工魚微調策略使算法的精度顯著提高。大量的仿真實驗數據表明,該算法提高了大規模多背包問題求解的速度和精度。

1 相關背景介紹

1.1 MKP

MKP的數學模型可描述為

xij∈{0,1},i=1,2,…,n;j=1,2,…,m

(1)

式中,n和m分別表示物品和背包的數目;pi表示第i件物品的價值;wi表示第i件物品所需要的容量;cj表示第j個背包的容量限制;pi,wi和cj均為大于0的值;當xij等于1時表示第i件物品被放入第j個背包內,等于0時表示未放入。

1.2 AFSA

AFSA通過對大自然中魚的行為(即隨機游動,覓食,追尾以及聚群)的簡單模擬,來指導人工魚在解空間內盡可能的搜索最優解。圖1是人工魚模型的簡單示意圖。假設當前人工魚的狀態為X,Visual表示其視野范圍,在Visual范圍內的人工魚定義為其伙伴,伙伴之間可以互相交換彼此間的信息,例如食物濃度,當前位置等。Step表示人工魚在一次尋優行為中所能達到的最大步長。

圖1 人工魚模型示意圖Fig.1 Sketch of artificial fish model

人工魚的4種行為中,隨機游動和覓食行為為開發新的解狀態提供了可能,保證了算法的收斂性。而追尾行為提高了收斂的速度,同時聚群行為保證了算法的穩定性。根據文獻[17,20]的理論證明以及文獻[21]的優化經驗,可以發現適當簡化人工魚的行為對于算法的全局收斂性不會產生影響,所以本文只選取隨機游動,覓食和追尾3種行為來進行尋優搜索。

本文人工魚個體的尋優行為描述如下:

(1) 隨機游動:人工魚當前狀態為Xi,在Step的限制內,隨意向其他方向前進。

(2) 覓食行為:人工魚當前狀態為Xi,在Visual范圍內,隨機選取任一狀態Xj,如果Xj的適應值滿足Yj>Yi,則在Step的限制內,向Xj方向前進。否則在規定次數內重新選擇新的狀態Xj,超過規定次數找不到符合條件的Xj執行隨機游動。

(3) 追尾行為:人工魚當前狀態為Xi,在Visual范圍內,找到狀態最優的伙伴Xmax,判其適應值Ymax>Yi并且周圍不太擁擠(nf/N<δ),則在Step的限制內,向Xmax方向前進。

1.3 人工魚編碼

目前,針對MKP問題的編碼問題有3種:01編碼[22]、組編碼[23]以及多值編碼[11]。對于本文的MKP,01編碼的解空間個數為2m×n,隨著n和m增大,解空間呈指數級增長,而且在這個巨大的解空間中,存在相當多的將1個物品放入2個甚至多個背包的非法解,例如{{0,1},{1,1}}是01編碼解空間的1個解,代表的是第1個物品放入第2個背包,而第2個物品被同時放入第1個背包和第2個背包,這顯然是不符合常理的。而組編碼在求解過程中,會出現多個解表達不同而含義相同的情況,例如{(1,5,6),(3,4)}與{(6,5,1),(4,3)}這兩個解編碼不同,但都是代表第1,5,6個物品放入第1個背包,第3,4個物品放入第2個背包的情況,這樣對于搜索過程是不利的,會導致重復搜索。本文采用多值編碼方式。相比前兩者,多值編碼方式不但極大地縮小了解空間(解空間為mn),解碼簡單并且具有唯一性,同時也杜絕了非法解的產生。

對于擁有n個物品和m個背包的多背包問題來說,創建數組X=(x1,x2,…,xn),xi∈{0,1,2,…,m},i=1,2,…,n。xi表示第i個物品的放置情況,xi=0表示此物品未放入任何背包。例如:X=(1,3,1,2,0)表示第1件物品和第3件物品被放入第1個背包中,第2件物品被放入第3個背包中,第4件物品被放入第2個背包中,而第5件物品未放入任何背包。

1.4 適應值計算及約束處理

AFSA優化是依靠概率進行搜索的,需要評價函數計算人工魚的適應值后確定個體的優劣。本文的多背包問題的評價函數可以設計為

s.t.xi∈{0,1,…,m}

(2)

式中,pi表示第i件物品的價值;xi表示第i個物品被放入的背包編號,xi=0時表示物品未放入任何背包。

眾所周知,MKP問題是一個具有多個約束的組合優化問題。在實際應用中,因為問題的復雜性和規模不斷擴大導致約束個數增加,問題的求解難度也會驟然增大。所以,如何妥善的處理約束成為了求解MKP問題的關鍵。罰函數法[24]的性能很大程度依賴于懲罰系數的設置,而且當非可行解數目很多時很難提升算法效果,針對這些缺陷,學者們又提出了拒絕非可行解法以及修復非可行解法[25],這兩種方法都是將不滿足約束的非可行解轉化為可行解,但是對于非可行解的處理有很大的隨機性。根據文獻[26]中的理論分析,有約束問題的最優解基本都在約束邊界附近,所以需要對非可行解進行針對性的修復。本文算法在求解過程中產生非可行解后,根據單位價值密度由低到高依次取出物品直到將其修復為可行解,對于修復后離約束邊界較遠的個體,通過執行調整策略可以使個體盡量靠近約束邊界,調整策略具體實現將在下章詳細闡述。

2 AAFSA-LMKP在大規模MKP中的應用

2.1 基于單位價值密度的人工魚初始化方法

AFSA在初始化人工魚時一般采用隨機生成的方式。根據第1.4節中的分析,為了提高算法的收斂性,在初始化時應該盡可能的使人工魚分布約束邊界附近。為了達到這個目的,本文提出了一種基于單位價值密度的人工魚初始化方法。

具體做法是:假設第i件物品的單位價值密度為pdi,首先將n個物品的pd按數值從大到小排序存入單位價值密度表pd[n]中,初始化人工魚時,從單位價值密度最高的物品開始,按表中順序依次為當前物品隨機產生1個整數Bag_num(0≤Bag_num≤m),如果Bag_num=0,則表示當前物品不放入背包,否則判斷第Bag_num個背包剩余容量是否足夠放入物品,是就將物品放入背包,背包剩余容量減少放入物品相應的w值,并將已經放入背包的物品標記;當背包容量不夠時,則不放入背包。重復以上步驟,直到所有的背包物品放置完畢。這樣的做法可以使單位價值較大的物品盡可能多地放入背包中,同時保證了初始化人工魚的物種多樣性,從而提高初始化人工魚的適應值。

本文人工魚初始化的偽代碼如下:

AF_Initialization():

fori←1 ton∥遍歷背包單位價值密度表

Bag_num=Rand(0,m);

∥0為不放入,否則選擇第Bag_num個背包

if(cBag_num>pd[i] &&pd[i].Flag==-1)

∥背包剩余容量足夠并且物品未被放入其他背包

PutInto(pd[i],Bag_num);

∥物品被放入背包

cBag_num=cBag_num-pd[i].w;

∥重新計算背包剩余容量

pd[i].Flag=1;

∥標記物品已被放入背包

end if

end for

2.2 追尾行為以及行為選擇的優化實現

對于大規模的組合優化問題,解空間非常大。人工魚初始化后其分布可能會非常稀疏,很有可能會出現所有人工魚在視野范圍內都沒有伙伴的情況,只能轉而執行覓食和隨機游動行為。但是追尾行為是人工魚在算法前期快速收斂的關鍵,快速收斂需要讓人工魚快速地游到適應值較高的區域,所以本文改進了人工魚追尾行為和行為選擇的具體實現,以提高算法的快速性。

當人工魚個體執行追尾行為之前,先判斷視野內有無伙伴符合追尾的條件,如果存在,直接向此伙伴方向前進;否則直接向公告板記錄的歷史最優解方向前進。為了避免公告板的狀態周圍過于擁擠以及算法后期震蕩,人工魚步長采用隨機步長。修改后的追尾行為描述為:人工魚當前狀態為Xi,向Xbulletin方向前進Rand(1,step)距離。偽代碼描述如下:

AF_Follow():

if (Neighbor!=NULL &&YNeighbor>Yi&&nf/N<δ)∥存在伙伴符合追尾條件

Xi|next=Xi+Rand(1, step)·(XNeighbor-Xi)

∥向追尾伙伴方向前進隨機步長

else

Xi|next=Xi+Rand(1, step)·(XBulletin-Xi)

∥向公告板方向前進隨機步長

end if

傳統的AFSA行為選擇(Behavior_Strategy)是分別執行人工魚的每種行為,然后從多個執行結果中選擇適應值結果最高的來執行。這樣的做法是非常耗時間的一種處理方式。本文的行為選擇具體實現是讓人工魚優先執行追尾行為,然后再次執行覓食行為,這樣的做法即可以讓人工魚快速聚攏到食物濃度高的區域,又能避免人工魚太過密集導致擁擠現象的出現。

2.3 視野與步長的動態調整方案

目前有很多關于動態調整視野和步長的研究,做法都是隨著搜索的進行,逐漸減小這兩個參數的值[27-29]。但在搜索的過程中,每個人工魚個體所處的區域不同,這樣一刀切的做法會存在兩個弊端:算法前期在較優解區域的人工魚可能會因為視野和步長過大而跳出當前的搜索域,而后期因為擁擠度因子沒有進入較優解區域的人工魚會在較差解域內做無意義的精細搜索。所以,根據人工魚個體當前情況來動態地調整Visual和Step值是非常有必要的。

根據以上的分析,當人工魚當前適應值較高時,就可以假設它當前處于較優解區域內,此時應該采用較小的Visual和Step值來促使人工魚對于當前解區域進行細粒度的精密搜索;如果人工魚當前適應值低,可以推測當前所處的解區域搜索價值較低,應該提高Visual和Step值來指導人工魚盡快游出這片區域,開發新的解區域重新搜索。

Visual和Step值可按式(3)實施動態調整。

(3)

式中,n為物品數目;Xi.Fitness表示人工魚當前的適應值；Bulletin.Fitness表示公告板記錄的適應值。

2.4 針對MKP的人工魚調整策略

對于MKP問題來說,背包剩余容量越小越好。人工魚每次執行完搜索行為的時候,肯定會有一部分物品從背包中被拿出,這樣背包剩余容量發生變化后,為了提高尋優的精度,我們需要對于人工魚當前的背包分配方式進行略微調整,檢查是否還有背包的剩余容量足以放入未放置的物品。具體實現為:從第1個背包開始,遍歷單位價值密度表,檢查是否有未放入的物品重量小于背包剩余容量,如果有滿足條件的物品,將物品放入此背包,更新背包剩余容量,標記物品已被放入背包,否則換下1個背包。重復以上步驟,直到所有背包的剩余容量都不夠放置任何未放置的物品。

2.5 算法流程

求解大規模MKP問題的優化AFSA算法具體實施流程如下:

步驟1設置AFSA基本參數:種群規模Popsize,嘗試次數Trynumber,擁擠度因子δ;基于單位價值密度來初始化人工魚種群,計算AF適應值并更新公告板;

步驟2根據式(1)調整人工魚當前的Visual和Step值;

步驟3AF執行行為選擇,先追尾再覓食,在搜索行為后應用人工魚調整策略更新AF狀態;

步驟4AF更新適應值與公告板比較,如果適應值優于公告板記錄的值,則更新公告板,否則轉向步驟5;

步驟5判斷是否達到算法終止條件,如果達到則終止算法進程,否則跳轉至步驟2。

3 數值實驗及算法有效性測試

為了驗證本文算法的有效性,針對大規模多約束MKP問題,分別比較了文獻[17]中的標準AFSA(std.AFSA)、文獻[26]的優化AFSA(ASR-AFSA)以及本文提出的AAFSA-LMKP的尋優精度及尋優速度。本文算法以及對比算法都使用C++語言實現,在PC機(CPU Inter Core i5-4460,主頻3.2GHz,RAM 8GB)上運行。對比算法的主要參數設計如下:Popsize=20;Visual=20;Step=10;Trynumber=300;δ=0.618。本文中視野和步長由式(3)確定,其他參數與對比算法一致。

文中使用了文獻[26]中約束較多(m=50,n=200、500、1 000)的數據來測試算法的尋優效果。物品重量及價值數據包含了3種類型:非相關數據,弱相關數據以及強相關數據。每組中又根據數據生成范圍被分為3組(R=100,1 000,10 000)。背包容量數據分為2種:相似數據和非相似數據。具體數據生成方式如下:

(1) 物品重量及價值數據

①非相關數據:pi和wi在[10,R]中隨機生成;

②弱相關數據:wi在[10,R]中隨機生成,而pi在[wi-R/10,wi+R/10]中隨機生成;

③強相關數據:wi在[10,R]中隨機生成,而pi被設置為wi+10。

(2) 背包容量數據

由于篇幅原因,本次測試數據無法在文中詳細列出,測試數據可在https:∥github.com/DBEngine/MKP/tree/master/data下載。

由于測試算法在搜索行為中存在隨機性,為了消除其對于實驗結果的影響,本次實驗結果均為10次尋優迭代過程的平均值。因為每個算法的復雜度不一致,每次迭代時間也會不同,所以我們在實驗中使用時間作為算法完成條件。表1是3種測試算法在7 s內搜索到的最優解,“----”表示最終結果為非可行解。

由表1可以看出,本文算法在仿真測試中尋優精度表現基本都超過了對比算法,僅有1個實例未超過但接近文獻[26]中的算法。而std.AFSA在有些實例中因為罰函數參數設置問題,甚至在一些測試實例中未能求得可行的解。

為了更直觀的證明本文算法對于大規模MKP問題求解的有效性,又測試了1組更大規模的多背包數據(m=100,n=2 000)。3種測試算法的尋優效果如圖2所示,可以看出本文算法的尋優性能具有明顯的優勢。因為應用了改良的初始化方式,收斂初值較另外兩種算法大大提升。在算法前期,對比算法由于追尾行為條件的限制,初期速度較慢,而本文算法由于借鑒了公告板的的優良記錄,能夠引導更多的人工魚向較優的區域方向前進,所以收斂效率更高。

表1 m=50, n=200、500、1 000 7 s內的仿真結果

圖2 3種算法進化曲線對比Fig.2 Evolution curve comparison of three algorithms

為了驗證本文動態調整視野和步長方案的有效性,對比了視野和步長的3種設置方式,分別是文獻[17]中的標準AFSA(std.AFSA)的靜態設置方案、文獻[29]的高級AFSA(AAFSA)的漸變設置方案以及本文AAFSA-LMKP的動態設置方案,算法其他步驟與本文算法保持一致,進化曲線如圖3所示。由圖3可以看出,本文算法在收斂速度和精度上較對比算法有了明顯的提升。std.AFSA因為采用了靜態的視野和步長,算法初期很難快速的引導人工魚個體向適應值較高的區域靠攏,而后期也會因為步長過大容易錯過最優解導致精度不足。文獻[29]中視野和步長的設置方案確實在一定程度上提高了尋優性能,但是與本文的視野步長動態調整方案相比,少了對于公告板信息的借鑒,所以求解速度和精度上還是表現不佳。因為AFSA本質上的隨機性,可能在初期就有少量人工魚已經靠近最優解,對于這些人工魚個體來說,在當前區域內精細搜索才是最佳選擇。同理,尋優后期也會有少量人工魚因為擁擠度因子的影響而跳出了較優解區域,此時應當引導它們跳出當前區域開發新的解域或者重新進入已知的較優解域。

圖3 3種視野步長設置方案進化曲線對比Fig.3 Evolution curve comparison of three setting strategy of Visual and Step

圖4展示了本文算法的3個參數:種群數目Popsize、嘗試次數Trynumber和擁擠度因子δ對于算法性能的影響。可以看出,當Popsize設置較大時(Popsize=100),因為個體數量多,所以每代迭代耗時較長,前期收斂較慢,但是算法后期精度較高。從圖3(b)可以看出,Trynumber設置的過小則會同時影響收斂效率和精度,根據實際算例測試結果,此參數最好設置在200～400。而δ參數的設置對于算法性能影響不大,綜合考慮收斂效率和精度,建議設置在0.3～0.7。

圖4 人工魚其他參數對算法性能影響對比Fig.4 Performance impact comparison of artificial fish’s other parameters

4 結 論

本文主要研究了大規模的MKP,針對其多約束以及解空間大的特點,提出了AAFSA-LMKP算法來求解此問題。針對現有算法求解速度慢的問題,AAFSA-LMKP改進了人工魚個體初始化方法、追尾行為以及行為選擇方式,保證了算法的收斂速度。同時,為了進一步提高算法的求解精度,引入了動態的參數設計和人工魚個體調整策略。

為了有效分析AAFSA-LMKP對于大規模MKP的尋優能力,與現有的算法同時對多個測試實例進行了求解。實驗數據表明,本文算法不僅較現有算法收斂速度更快,同時在算法后期,精度也有了很大的提升,并且隨著多背包問題規模增加,AAFSA-LMKP性能提升更加明顯。因為算法對于參數不敏感的特點,也避免了參數選擇的麻煩。本文算法特別適用于多約束的大規模組合優化問題,如何利用AFSA個體在尋優過程中的獨立性,利用現在的多處理器的硬件條件來并行實現進一步提升算法的尋優效率,將是筆者今后研究的方向。

[1] SONG X, LEWIS R, THOMPSON J, et al. An incomplete m-exchange algorithm for solving the large-scale multi-scenario knapsack problem[J].Computers & Operations Research,2012, 39(9): 1988-2000.

[2] 薛俊杰, 王瑛, 孟祥飛,等. 二進制反向學習煙花算法求解多維背包問題[J]. 系統工程與電子技術, 2017, 39(2): 451-458.

XUE J J, WANG Y, MENG X F, et al. Binary opposite backward learning fireworks algorithm for multidimensional knapsack problem[J].Systems Engineering and Electronics,2017,39(2): 451-458.

[3] 王凌, 王圣堯, 方晨. 一種求解多維背包問題的混合分布估計算法[J]. 控制與決策, 2011,26(8): 1121-1125.

WANG L, WANG S Y, FANG C. A hybrid distribution estimation algorithm for solving multidimensional knapsack problem[J]. 2011,26(8): 1121-1125.

[4] CHIH M C. Self-adaptive check and repair operator-based particle swarm optimization for the multidimensional knapsack problem[J]. Applied Soft Computing, 2015, 26(1): 378-389.

[5] VARNAMKHASTI M J. Overview of the algorithms for solving the multidimensional Knapsack problems[J]. Advanced Studies in Biology, 2012, 4(1): 37-47.

[6] PUCHINGER J, RAIDL G R, PFERSCHY U. The multidimensional knapsack problem: structure and algorithms[J]. Informs Journal on Computing, 2010, 22(2): 250-265.

[7] HOLLAND J H. Adaptation in Natural and Artificial Systems[M]. Cambridge: MIT Press, 1975.

[8] KENNEDY J, EBERHART R C. Particle swarm optimization[C]∥Proc.of the IEEE International Conference on Neural Networks. Honolulu: IEEE Press, 2002: 1942-1948.

[9] DORIG M, MANIEZZO V, COLORNI A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Trans.on Systems, Man and Cybernetics, 1996, 26(1): 29-41.

[10] BERBERLER M E, GULER A, NURIYEV U G. A genetic algorithm to solve the multidimensional knapsack problem[J]. Mathematical & Computational Applications, 2013, 18(3): 486-494.

[11] 宋海生,傅仁毅,徐瑞松,等.求解多背包問題的混合遺傳算法[J].計算機工程與應用, 2009, 45(20): 45-48.

SONG H S, FU R Y, XU R S, et al. Hybrid genetic algorithm for multi-knapsack problem[J]. Computer Engineering and Application, 2009, 45(20): 45-48.

[12] YE J, LIU X D,HAN L. Evolutionary game algorithm for multiple knapsack problem[C]∥Proc.of the IEEE/WIC International Conference on Intelligent Agent Technology,2003: 424-427.

[13] SABET S, SHOKOUHIFAR M, FAROKHI F. A discrete artificial bee colony for multiple knapsack problem[J]. International Journal of Reasoning-based Intelligent Systems,2013,5(2): 88-95.

[14] KTARI R, CHABCHOUB H. Essential particle swarm optimization queen with Tabu Search for MKP resolution[J]. Computing, 2013, 95(9): 897-921.

[15] 馬炫, 劉慶. 求解多背包問題的人工魚群算法[J]. 計算機應用, 2010, 30(2): 469-471.

MA X, LIU Q. Artificial fish swarm algorithm for multiple knapsack problem[J]. Journal of Computer Application, 2010, 30(2): 469-471.

[16] 李迎,張璟,虎群,等.人工魚群算法在虛擬機分配中的應用[J].計算機工程與應用,2015,51(4):22-28.

LI Y, ZHANG J, HU Q, et al. Artificial fish swarm algorithm for virtual machine placement[J]. Computer Engineering and Application, 2015, 51(4): 22-28.

[17] 李曉磊. 一種新型的智能優化方法-人工魚群算法[D]. 杭州:浙江大學, 2003.

LI X L. A new intelligent optimization method-artificial fish school algorithm[D]. Hangzhou: Zhejiang University, 2003.

[18] ZHANG Y L, OGURA H, KUROIWA J. Fish swarm optimization method for the two-dimensional guillotine cutting pro-blem[J]. Journal of Signal Processing,2011,15(3):225-234.

[19] 黃光球,朱華平,周靜.用魚群算法求解石油運輸系統多級站定位優化問題[J].系統工程理論與實踐,2008,28(3):94-102.

HUANG G F, ZHU H P, ZHOU J. An optimization method of multistage stations locating in oil transportation based on fish-swarm algorithm[J]. Systems Engineering Theory & Practice, 2008, 28(3): 94-102.

[20] 黃光球, 劉嘉飛, 姚玉霞. 求解組合優化問題的魚群算法的收斂性證明[J]. 計算機工程與應用, 2012, 48(10): 59-63.

HUANG G Q, LIU J F, YAO Y X. Global convergence proof of artificial fish swarm for solving combinatorial optimization problems[J].Computer Engineering and Application,2012,48(10): 59-63.

[21] LIU Q, ODAKA T, KUROIWA J, et al. An artificial fish swarm algorithm for the multicast routing problem[J]. IEICE Trans.on Communications,2014,E97.B(5):996-1011.

[22] 虞安波, 楊家本. 多背包問題的遺傳算法求解[J]. 計算技術與自動化, 2002, 21(2): 59-63.

YU A B, YANG J B. Genetic algorithm for multi knapsack problem[J]. Computing Technology and Automation, 2002, 21(2): 59-63.

[23] FUKUNAGA A S. Dominance in incomplete solvers for the multiple knapsack problem[C]∥Proc.of the IEEE World Congress on Computational Intelligence, 2003: 2225-2232.

[24] COELLO C A C. Use of a self-adaptive penalty approach for engineering optimization problems[J]. Computers in Industry, 2000, 41(2): 113-127.

[25] SALCEDO-SANZ S S. A survey of repair methods used as constraint handling techniques in evolutionary algorithms[J]. Computer Science Review, 2009, 3(3): 175-192.

[26] LIU Q, ODAKA T, KUROIWA J, et al. A new artificial fish swarm algorithm for the multiple knapsack problem[J]. IEICE Trans.on Information & Systems,2014,E97.D(3):455-468.

[27] 王聯國,洪毅,施秋紅.全局版人工魚群算法[J].系統仿真學報,2009,21(23):7483-7486.

WANG L G, HONG Y, SHI Q H. Global edition artificial fish swarm algorithm[J].Journal of System Simulation,2009,21(23): 7483-7486.

[28] 周燕云, 許國軍, 覃錫忠,等. 基于改進人工魚群算法的蜂窩網絡信道分配[J]. 計算機仿真, 2013, 30(6): 206-209.

ZHOU Y Y, XU G J, TAN X Z, et al. Channel assignment in cellular network based on improved artificial fish school algorithm[J]. Computer Simulation, 2013, 30(6):206-209.

[29] 桓自強,倪宏,胡琳琳,等.AAFSA-RA:一種采用高級人工魚群算法的多資源分配方法[J].西安交通大學學報,2014,48(10):120-125.

HENG Z Q, NI H, HU L L, et al. AAFSA-RA: A Multi-Resource Allocation Method Based on an Advanced Artificial Fish Swarm Algorithm[J]. Journal of Xi’an Jiaotong University, 2014, 48(10): 120-125.