求解大規(guī)模多背包問(wèn)題的高級(jí)人工魚(yú)群算法

李 迎, 張 璟, 劉 慶, 張 偉

(1. 西安理工大學(xué)自動(dòng)化與信息工程學(xué)院, 陜西 西安 710048; 2. 西安理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院, 陜西 西安 710048; 3. 北京天云融創(chuàng)軟件技術(shù)有限公司, 陜西 西安 710075)

0 引 言

多背包問(wèn)題(multiple knapsack problem,MKP)是一個(gè)很經(jīng)典的NP-Hard組合優(yōu)化問(wèn)題[1-2],它可以作為很多實(shí)際問(wèn)題的模型,例如多資源調(diào)度、交通規(guī)劃、資本預(yù)算、材料切割等[3-4]。

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

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

1 相關(guān)背景介紹

1.1 MKP

MKP的數(shù)學(xué)模型可描述為

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

(1)

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

1.2 AFSA

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

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

人工魚(yú)的4種行為中,隨機(jī)游動(dòng)和覓食行為為開(kāi)發(fā)新的解狀態(tài)提供了可能,保證了算法的收斂性。而追尾行為提高了收斂的速度,同時(shí)聚群行為保證了算法的穩(wěn)定性。根據(jù)文獻(xiàn)[17,20]的理論證明以及文獻(xiàn)[21]的優(yōu)化經(jīng)驗(yàn),可以發(fā)現(xiàn)適當(dāng)簡(jiǎn)化人工魚(yú)的行為對(duì)于算法的全局收斂性不會(huì)產(chǎn)生影響,所以本文只選取隨機(jī)游動(dòng),覓食和追尾3種行為來(lái)進(jìn)行尋優(yōu)搜索。

本文人工魚(yú)個(gè)體的尋優(yōu)行為描述如下:

(1) 隨機(jī)游動(dòng):人工魚(yú)當(dāng)前狀態(tài)為Xi,在Step的限制內(nèi),隨意向其他方向前進(jìn)。

(2) 覓食行為:人工魚(yú)當(dāng)前狀態(tài)為Xi,在Visual范圍內(nèi),隨機(jī)選取任一狀態(tài)Xj,如果Xj的適應(yīng)值滿足Yj>Yi,則在Step的限制內(nèi),向Xj方向前進(jìn)。否則在規(guī)定次數(shù)內(nèi)重新選擇新的狀態(tài)Xj,超過(guò)規(guī)定次數(shù)找不到符合條件的Xj執(zhí)行隨機(jī)游動(dòng)。

(3) 追尾行為:人工魚(yú)當(dāng)前狀態(tài)為Xi,在Visual范圍內(nèi),找到狀態(tài)最優(yōu)的伙伴Xmax,判其適應(yīng)值Ymax>Yi并且周?chē)惶珦頂D(nf/N<δ),則在Step的限制內(nèi),向Xmax方向前進(jìn)。

1.3 人工魚(yú)編碼

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

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

1.4 適應(yīng)值計(jì)算及約束處理

AFSA優(yōu)化是依靠概率進(jìn)行搜索的,需要評(píng)價(jià)函數(shù)計(jì)算人工魚(yú)的適應(yīng)值后確定個(gè)體的優(yōu)劣。本文的多背包問(wèn)題的評(píng)價(jià)函數(shù)可以設(shè)計(jì)為

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

(2)

式中,pi表示第i件物品的價(jià)值;xi表示第i個(gè)物品被放入的背包編號(hào),xi=0時(shí)表示物品未放入任何背包。

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

2 AAFSA-LMKP在大規(guī)模MKP中的應(yīng)用

2.1 基于單位價(jià)值密度的人工魚(yú)初始化方法

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

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

本文人工魚(yú)初始化的偽代碼如下:

AF_Initialization():

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

Bag_num=Rand(0,m);

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

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

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

PutInto(pd[i],Bag_num);

∥物品被放入背包

cBag_num=cBag_num-pd[i].w;

∥重新計(jì)算背包剩余容量

pd[i].Flag=1;

∥標(biāo)記物品已被放入背包

end if

end for

2.2 追尾行為以及行為選擇的優(yōu)化實(shí)現(xiàn)

對(duì)于大規(guī)模的組合優(yōu)化問(wèn)題,解空間非常大。人工魚(yú)初始化后其分布可能會(huì)非常稀疏,很有可能會(huì)出現(xiàn)所有人工魚(yú)在視野范圍內(nèi)都沒(méi)有伙伴的情況,只能轉(zhuǎn)而執(zhí)行覓食和隨機(jī)游動(dòng)行為。但是追尾行為是人工魚(yú)在算法前期快速收斂的關(guān)鍵,快速收斂需要讓人工魚(yú)快速地游到適應(yīng)值較高的區(qū)域,所以本文改進(jìn)了人工魚(yú)追尾行為和行為選擇的具體實(shí)現(xiàn),以提高算法的快速性。

當(dāng)人工魚(yú)個(gè)體執(zhí)行追尾行為之前,先判斷視野內(nèi)有無(wú)伙伴符合追尾的條件,如果存在,直接向此伙伴方向前進(jìn);否則直接向公告板記錄的歷史最優(yōu)解方向前進(jìn)。為了避免公告板的狀態(tài)周?chē)^(guò)于擁擠以及算法后期震蕩,人工魚(yú)步長(zhǎng)采用隨機(jī)步長(zhǎng)。修改后的追尾行為描述為:人工魚(yú)當(dāng)前狀態(tài)為Xi,向Xbulletin方向前進(jìn)Rand(1,step)距離。偽代碼描述如下:

AF_Follow():

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

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

∥向追尾伙伴方向前進(jìn)隨機(jī)步長(zhǎng)

else

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

∥向公告板方向前進(jìn)隨機(jī)步長(zhǎng)

end if

傳統(tǒng)的AFSA行為選擇(Behavior_Strategy)是分別執(zhí)行人工魚(yú)的每種行為,然后從多個(gè)執(zhí)行結(jié)果中選擇適應(yīng)值結(jié)果最高的來(lái)執(zhí)行。這樣的做法是非常耗時(shí)間的一種處理方式。本文的行為選擇具體實(shí)現(xiàn)是讓人工魚(yú)優(yōu)先執(zhí)行追尾行為,然后再次執(zhí)行覓食行為,這樣的做法即可以讓人工魚(yú)快速聚攏到食物濃度高的區(qū)域,又能避免人工魚(yú)太過(guò)密集導(dǎo)致?lián)頂D現(xiàn)象的出現(xiàn)。

2.3 視野與步長(zhǎng)的動(dòng)態(tài)調(diào)整方案

目前有很多關(guān)于動(dòng)態(tài)調(diào)整視野和步長(zhǎng)的研究,做法都是隨著搜索的進(jìn)行,逐漸減小這兩個(gè)參數(shù)的值[27-29]。但在搜索的過(guò)程中,每個(gè)人工魚(yú)個(gè)體所處的區(qū)域不同,這樣一刀切的做法會(huì)存在兩個(gè)弊端:算法前期在較優(yōu)解區(qū)域的人工魚(yú)可能會(huì)因?yàn)橐曇昂筒介L(zhǎng)過(guò)大而跳出當(dāng)前的搜索域,而后期因?yàn)閾頂D度因子沒(méi)有進(jìn)入較優(yōu)解區(qū)域的人工魚(yú)會(huì)在較差解域內(nèi)做無(wú)意義的精細(xì)搜索。所以,根據(jù)人工魚(yú)個(gè)體當(dāng)前情況來(lái)動(dòng)態(tài)地調(diào)整Visual和Step值是非常有必要的。

根據(jù)以上的分析,當(dāng)人工魚(yú)當(dāng)前適應(yīng)值較高時(shí),就可以假設(shè)它當(dāng)前處于較優(yōu)解區(qū)域內(nèi),此時(shí)應(yīng)該采用較小的Visual和Step值來(lái)促使人工魚(yú)對(duì)于當(dāng)前解區(qū)域進(jìn)行細(xì)粒度的精密搜索;如果人工魚(yú)當(dāng)前適應(yīng)值低,可以推測(cè)當(dāng)前所處的解區(qū)域搜索價(jià)值較低,應(yīng)該提高Visual和Step值來(lái)指導(dǎo)人工魚(yú)盡快游出這片區(qū)域,開(kāi)發(fā)新的解區(qū)域重新搜索。

Visual和Step值可按式(3)實(shí)施動(dòng)態(tài)調(diào)整。

(3)

式中,n為物品數(shù)目;Xi.Fitness表示人工魚(yú)當(dāng)前的適應(yīng)值；Bulletin.Fitness表示公告板記錄的適應(yīng)值。

2.4 針對(duì)MKP的人工魚(yú)調(diào)整策略

對(duì)于MKP問(wèn)題來(lái)說(shuō),背包剩余容量越小越好。人工魚(yú)每次執(zhí)行完搜索行為的時(shí)候,肯定會(huì)有一部分物品從背包中被拿出,這樣背包剩余容量發(fā)生變化后,為了提高尋優(yōu)的精度,我們需要對(duì)于人工魚(yú)當(dāng)前的背包分配方式進(jìn)行略微調(diào)整,檢查是否還有背包的剩余容量足以放入未放置的物品。具體實(shí)現(xiàn)為:從第1個(gè)背包開(kāi)始,遍歷單位價(jià)值密度表,檢查是否有未放入的物品重量小于背包剩余容量,如果有滿足條件的物品,將物品放入此背包,更新背包剩余容量,標(biāo)記物品已被放入背包,否則換下1個(gè)背包。重復(fù)以上步驟,直到所有背包的剩余容量都不夠放置任何未放置的物品。

2.5 算法流程

求解大規(guī)模MKP問(wèn)題的優(yōu)化AFSA算法具體實(shí)施流程如下:

步驟1設(shè)置AFSA基本參數(shù):種群規(guī)模Popsize,嘗試次數(shù)Trynumber,擁擠度因子δ;基于單位價(jià)值密度來(lái)初始化人工魚(yú)種群,計(jì)算AF適應(yīng)值并更新公告板;

步驟2根據(jù)式(1)調(diào)整人工魚(yú)當(dāng)前的Visual和Step值;

步驟3AF執(zhí)行行為選擇,先追尾再覓食,在搜索行為后應(yīng)用人工魚(yú)調(diào)整策略更新AF狀態(tài);

步驟4AF更新適應(yīng)值與公告板比較,如果適應(yīng)值優(yōu)于公告板記錄的值,則更新公告板,否則轉(zhuǎn)向步驟5;

步驟5判斷是否達(dá)到算法終止條件,如果達(dá)到則終止算法進(jìn)程,否則跳轉(zhuǎn)至步驟2。

3 數(shù)值實(shí)驗(yàn)及算法有效性測(cè)試

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

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

(1) 物品重量及價(jià)值數(shù)據(jù)

①非相關(guān)數(shù)據(jù):pi和wi在[10,R]中隨機(jī)生成;

②弱相關(guān)數(shù)據(jù):wi在[10,R]中隨機(jī)生成,而pi在[wi-R/10,wi+R/10]中隨機(jī)生成;

③強(qiáng)相關(guān)數(shù)據(jù):wi在[10,R]中隨機(jī)生成,而pi被設(shè)置為wi+10。

(2) 背包容量數(shù)據(jù)

由于篇幅原因,本次測(cè)試數(shù)據(jù)無(wú)法在文中詳細(xì)列出,測(cè)試數(shù)據(jù)可在https:∥github.com/DBEngine/MKP/tree/master/data下載。

由于測(cè)試算法在搜索行為中存在隨機(jī)性,為了消除其對(duì)于實(shí)驗(yàn)結(jié)果的影響,本次實(shí)驗(yàn)結(jié)果均為10次尋優(yōu)迭代過(guò)程的平均值。因?yàn)槊總€(gè)算法的復(fù)雜度不一致,每次迭代時(shí)間也會(huì)不同,所以我們?cè)趯?shí)驗(yàn)中使用時(shí)間作為算法完成條件。表1是3種測(cè)試算法在7 s內(nèi)搜索到的最優(yōu)解,“----”表示最終結(jié)果為非可行解。

由表1可以看出,本文算法在仿真測(cè)試中尋優(yōu)精度表現(xiàn)基本都超過(guò)了對(duì)比算法,僅有1個(gè)實(shí)例未超過(guò)但接近文獻(xiàn)[26]中的算法。而std.AFSA在有些實(shí)例中因?yàn)榱P函數(shù)參數(shù)設(shè)置問(wèn)題,甚至在一些測(cè)試實(shí)例中未能求得可行的解。

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

表1 m=50, n=200、500、1 000 7 s內(nèi)的仿真結(jié)果

圖2 3種算法進(jìn)化曲線對(duì)比Fig.2 Evolution curve comparison of three algorithms

為了驗(yàn)證本文動(dòng)態(tài)調(diào)整視野和步長(zhǎng)方案的有效性,對(duì)比了視野和步長(zhǎng)的3種設(shè)置方式,分別是文獻(xiàn)[17]中的標(biāo)準(zhǔn)AFSA(std.AFSA)的靜態(tài)設(shè)置方案、文獻(xiàn)[29]的高級(jí)AFSA(AAFSA)的漸變?cè)O(shè)置方案以及本文AAFSA-LMKP的動(dòng)態(tài)設(shè)置方案,算法其他步驟與本文算法保持一致,進(jìn)化曲線如圖3所示。由圖3可以看出,本文算法在收斂速度和精度上較對(duì)比算法有了明顯的提升。std.AFSA因?yàn)椴捎昧遂o態(tài)的視野和步長(zhǎng),算法初期很難快速的引導(dǎo)人工魚(yú)個(gè)體向適應(yīng)值較高的區(qū)域靠攏,而后期也會(huì)因?yàn)椴介L(zhǎng)過(guò)大容易錯(cuò)過(guò)最優(yōu)解導(dǎo)致精度不足。文獻(xiàn)[29]中視野和步長(zhǎng)的設(shè)置方案確實(shí)在一定程度上提高了尋優(yōu)性能,但是與本文的視野步長(zhǎng)動(dòng)態(tài)調(diào)整方案相比,少了對(duì)于公告板信息的借鑒,所以求解速度和精度上還是表現(xiàn)不佳。因?yàn)锳FSA本質(zhì)上的隨機(jī)性,可能在初期就有少量人工魚(yú)已經(jīng)靠近最優(yōu)解,對(duì)于這些人工魚(yú)個(gè)體來(lái)說(shuō),在當(dāng)前區(qū)域內(nèi)精細(xì)搜索才是最佳選擇。同理,尋優(yōu)后期也會(huì)有少量人工魚(yú)因?yàn)閾頂D度因子的影響而跳出了較優(yōu)解區(qū)域,此時(shí)應(yīng)當(dāng)引導(dǎo)它們跳出當(dāng)前區(qū)域開(kāi)發(fā)新的解域或者重新進(jìn)入已知的較優(yōu)解域。

圖3 3種視野步長(zhǎng)設(shè)置方案進(jìn)化曲線對(duì)比Fig.3 Evolution curve comparison of three setting strategy of Visual and Step

圖4展示了本文算法的3個(gè)參數(shù):種群數(shù)目Popsize、嘗試次數(shù)Trynumber和擁擠度因子δ對(duì)于算法性能的影響?？梢钥闯?當(dāng)Popsize設(shè)置較大時(shí)(Popsize=100),因?yàn)閭€(gè)體數(shù)量多,所以每代迭代耗時(shí)較長(zhǎng),前期收斂較慢,但是算法后期精度較高。從圖3(b)可以看出,Trynumber設(shè)置的過(guò)小則會(huì)同時(shí)影響收斂效率和精度,根據(jù)實(shí)際算例測(cè)試結(jié)果,此參數(shù)最好設(shè)置在200～400。而δ參數(shù)的設(shè)置對(duì)于算法性能影響不大,綜合考慮收斂效率和精度,建議設(shè)置在0.3～0.7。

圖4 人工魚(yú)其他參數(shù)對(duì)算法性能影響對(duì)比Fig.4 Performance impact comparison of artificial fish’s other parameters

4 結(jié) 論

本文主要研究了大規(guī)模的MKP,針對(duì)其多約束以及解空間大的特點(diǎn),提出了AAFSA-LMKP算法來(lái)求解此問(wèn)題。針對(duì)現(xiàn)有算法求解速度慢的問(wèn)題,AAFSA-LMKP改進(jìn)了人工魚(yú)個(gè)體初始化方法、追尾行為以及行為選擇方式,保證了算法的收斂速度。同時(shí),為了進(jìn)一步提高算法的求解精度,引入了動(dòng)態(tài)的參數(shù)設(shè)計(jì)和人工魚(yú)個(gè)體調(diào)整策略。

為了有效分析AAFSA-LMKP對(duì)于大規(guī)模MKP的尋優(yōu)能力,與現(xiàn)有的算法同時(shí)對(duì)多個(gè)測(cè)試實(shí)例進(jìn)行了求解。實(shí)驗(yàn)數(shù)據(jù)表明,本文算法不僅較現(xiàn)有算法收斂速度更快,同時(shí)在算法后期,精度也有了很大的提升,并且隨著多背包問(wèn)題規(guī)模增加,AAFSA-LMKP性能提升更加明顯。因?yàn)樗惴▽?duì)于參數(shù)不敏感的特點(diǎn),也避免了參數(shù)選擇的麻煩。本文算法特別適用于多約束的大規(guī)模組合優(yōu)化問(wèn)題,如何利用AFSA個(gè)體在尋優(yōu)過(guò)程中的獨(dú)立性,利用現(xiàn)在的多處理器的硬件條件來(lái)并行實(shí)現(xiàn)進(jìn)一步提升算法的尋優(yōu)效率,將是筆者今后研究的方向。

[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ìn)制反向?qū)W習(xí)煙花算法求解多維背包問(wèn)題[J]. 系統(tǒng)工程與電子技術(shù), 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] 王凌, 王圣堯, 方晨. 一種求解多維背包問(wèn)題的混合分布估計(jì)算法[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] 宋海生,傅仁毅,徐瑞松,等.求解多背包問(wèn)題的混合遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用, 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] 馬炫, 劉慶. 求解多背包問(wèn)題的人工魚(yú)群算法[J]. 計(jì)算機(jī)應(yīng)用, 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] 李迎,張璟,虎群,等.人工魚(yú)群算法在虛擬機(jī)分配中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,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] 李曉磊. 一種新型的智能優(yōu)化方法-人工魚(yú)群算法[D]. 杭州:浙江大學(xué), 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] 黃光球,朱華平,周靜.用魚(yú)群算法求解石油運(yùn)輸系統(tǒng)多級(jí)站定位優(yōu)化問(wèn)題[J].系統(tǒng)工程理論與實(shí)踐,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] 黃光球, 劉嘉飛, 姚玉霞. 求解組合優(yōu)化問(wèn)題的魚(yú)群算法的收斂性證明[J]. 計(jì)算機(jī)工程與應(yīng)用, 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] 虞安波, 楊家本. 多背包問(wèn)題的遺傳算法求解[J]. 計(jì)算技術(shù)與自動(dòng)化, 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] 王聯(lián)國(guó),洪毅,施秋紅.全局版人工魚(yú)群算法[J].系統(tǒng)仿真學(xué)報(bào),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] 周燕云, 許國(guó)軍, 覃錫忠,等. 基于改進(jìn)人工魚(yú)群算法的蜂窩網(wǎng)絡(luò)信道分配[J]. 計(jì)算機(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] 桓自強(qiáng),倪宏,胡琳琳,等.AAFSA-RA:一種采用高級(jí)人工魚(yú)群算法的多資源分配方法[J].西安交通大學(xué)學(xué)報(bào),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.