求解多目標(biāo)背包問(wèn)題的改進(jìn)人工魚(yú)群算法

黃美華， 溫潔嫦， 何　勇

(廣東工業(yè)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院, 廣東 廣州 510520)

?

求解多目標(biāo)背包問(wèn)題的改進(jìn)人工魚(yú)群算法

黃美華， 溫潔嫦， 何勇

(廣東工業(yè)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院, 廣東 廣州 510520)

作為一種新的群智能算法,在求解多目標(biāo)背包問(wèn)題時(shí),人工魚(yú)群算法存在盲目搜索、收斂速度慢和求解精度低等問(wèn)題.針對(duì)這些問(wèn)題,本文結(jié)合人工魚(yú)位置全局最優(yōu)信息,對(duì)人工魚(yú)的移動(dòng)策略進(jìn)行自適應(yīng)改進(jìn),提出一種改進(jìn)的人工魚(yú)群算法.對(duì)多目標(biāo)背包優(yōu)化問(wèn)題實(shí)驗(yàn)仿真表明,本文改進(jìn)的人工魚(yú)群算法收斂速度和搜索到的非劣解的精度均優(yōu)于粒子群算法和遺傳算法.

多目標(biāo)優(yōu)化； 背包問(wèn)題； 人工魚(yú)群算法； 自適應(yīng)

多目標(biāo)背包問(wèn)題是一個(gè)易于描述卻難以解決的NP-hard問(wèn)題,在現(xiàn)實(shí)世界中具有廣泛的應(yīng)用背景.投資組合、貨物裝載、工程設(shè)計(jì)等都可以建模為多目標(biāo)背包問(wèn)題.

隨著背包內(nèi)物品的數(shù)量增加,考慮物品的性質(zhì)增多,多目標(biāo)背包問(wèn)題的求解空間和時(shí)間復(fù)雜度將呈指數(shù)級(jí)增加.大規(guī)模多目標(biāo)背包問(wèn)題的解空間很龐大,傳統(tǒng)的計(jì)算方法面臨著計(jì)算時(shí)間長(zhǎng)、計(jì)算成本高和搜索高質(zhì)量解難等問(wèn)題,需要研究有效的搜索方法,使得在求解時(shí)間和求解精度上取得平衡.粒子群算法[1-2]、遺傳算法[3- 4]和蝙蝠算法[5]等,代表一類(lèi)模擬自然進(jìn)化的隨機(jī)優(yōu)化方法，能在一次模擬運(yùn)行中求出多個(gè)有效解[6],所以特別適合研究多目標(biāo)背包問(wèn)題.

作為一種新型仿生群智能優(yōu)化算法,人工魚(yú)群算法[7]具有魯棒性強(qiáng)、全局收斂性好以及對(duì)初值要求低等優(yōu)點(diǎn).然而,由于人工魚(yú)個(gè)體的行為都是局部尋優(yōu)行為,所以難以避免個(gè)體趨同、早熟現(xiàn)象,從而陷入局部極值[8].因此,人工魚(yú)群算法求解多目標(biāo)背包問(wèn)題存在收斂速度慢、求解精度不高、復(fù)雜度高等缺點(diǎn).

針對(duì)上述缺點(diǎn),文獻(xiàn)[9-11]把全局最優(yōu)人工魚(yú)信息加入人工魚(yú)的位置更新公式中，文獻(xiàn)[12-15]根據(jù)魚(yú)群整體狀態(tài)的變化適時(shí)調(diào)整人工魚(yú)的視野和步長(zhǎng)對(duì)人工魚(yú)群算法進(jìn)行改進(jìn).

本文采用文獻(xiàn)[12]中的自適應(yīng)步長(zhǎng),加入全局信息[10],引入一個(gè)自適應(yīng)因子,自適應(yīng)調(diào)整全局信息在算法中的作用,以解決人工魚(yú)群算法在求解多目標(biāo)背包問(wèn)題時(shí)收斂慢,求解精度不高的問(wèn)題.通過(guò)計(jì)算機(jī)仿真,并與粒子群算法和遺傳算法進(jìn)行比較,采用文獻(xiàn)[3]中的評(píng)價(jià)方法評(píng)價(jià)算法的收斂性和求解精度,證明本文改進(jìn)的人工魚(yú)群算法在多目標(biāo)背包問(wèn)題上的應(yīng)用是有效的,且搜索到的解質(zhì)量比較高.

1　多目標(biāo)背包問(wèn)題及其數(shù)學(xué)模型

假設(shè)存在m類(lèi)物品,每類(lèi)物品中又包含n種具體物品,現(xiàn)要求從這m種類(lèi)別物品中分別選擇一種物品放入背包中,使得背包內(nèi)物品的總價(jià)值最大,總體積最小,并且背包的總質(zhì)量不超過(guò)ckg.背包問(wèn)題的數(shù)學(xué)模型為

其中,Px表示背包內(nèi)物品價(jià)值,Rx表示背包內(nèi)物品體積,C表示物品質(zhì)量,X為選擇物品.P為每個(gè)物品的價(jià)值,R為每個(gè)物品的體積,X為一個(gè)0-1矩陣,1表示該物品被選擇,0表示該物品不被選擇.P,R,C的取值如下：

2　人工魚(yú)群算法

2.1人工魚(yú)群算法基本原理

在一片水域里,魚(yú)總是自行或尾隨其他魚(yú)朝該水域中營(yíng)養(yǎng)物質(zhì)最豐富的地方游動(dòng).人工魚(yú)群算法就是根據(jù)魚(yú)的這一自然特性,模仿魚(yú)群覓食等行為,實(shí)現(xiàn)尋優(yōu).

2.2人工魚(yú)移動(dòng)策略

2.3自適應(yīng)步長(zhǎng)

在聚群行為和追尾行為中,步長(zhǎng)是一個(gè)固定的參數(shù),致使初期收斂速度較快,后期不易集中,最優(yōu)解不精確.依據(jù)最優(yōu)人工魚(yú)與當(dāng)前人工魚(yú)的兩種適應(yīng)原則及食物濃度的比較,確定移動(dòng)步長(zhǎng),表示如下：

即算法中移動(dòng)步長(zhǎng)大小取決于當(dāng)前所在狀態(tài)和視野范圍中視點(diǎn)感知的狀態(tài)[12].

2.4全局人工魚(yú)群算法

基本人工魚(yú)群算法中,人工魚(yú)的位置更新公式中只有局部信息沒(méi)有全局信息.全局人工魚(yú)群算法就是把人工魚(yú)全局最優(yōu)位置信息Xbest_af加入位置更新模式中,實(shí)現(xiàn)人工魚(yú)全局尋優(yōu)[9].位置更新表示如下：

3　改進(jìn)的人工魚(yú)群算法

本文引入一個(gè)自適應(yīng)因子w，自適應(yīng)調(diào)整全局信息在人工魚(yú)尋找下一個(gè)位置時(shí)的判斷和決策中的作用.其中，

w1>w2,Tmax為最大迭代次數(shù),Tcur為當(dāng)前迭代次數(shù).

3.1改進(jìn)算法人工魚(yú)的行為描述

3.1.1覓食行為

若不符合則繼續(xù)搜索,反復(fù)嘗試Try_number次后，如果仍不符合前進(jìn)條件,則隨機(jī)移動(dòng)一步

3.1.2聚群行為

否則執(zhí)行隨機(jī)行為.

3.1.3追尾行為

否則執(zhí)行隨機(jī)行為.

3.1.4隨機(jī)行為

隨機(jī)行為是在其視野范圍內(nèi)隨機(jī)選取一個(gè)位置,然后向該方向移動(dòng).其實(shí),它是覓食行為的一個(gè)缺省行為.

3.2算法基本流程

根據(jù)多目標(biāo)搜索算法原理，本文改進(jìn)算法的基本流程如下.

Step1:初始化人工魚(yú)初始位置以及人工魚(yú)的相關(guān)參數(shù),計(jì)算每條人工魚(yú)的適應(yīng)度值,初始篩選非劣解.

Step2:在非劣解集中隨機(jī)選取人工魚(yú)作為全局最優(yōu)人工魚(yú),并記錄全局最優(yōu)的人工魚(yú)的狀態(tài),計(jì)算w.

Step3:對(duì)每條人工魚(yú)進(jìn)行行為評(píng)價(jià),對(duì)其要執(zhí)行的行為進(jìn)行選擇,包括覓食、聚群、追尾和隨機(jī)行為.

Step4:執(zhí)行人工魚(yú)選擇的行為,基于全局信息和局部信息更新人工魚(yú)的位置信息.

Step5:更新全局最優(yōu)人工魚(yú)的狀態(tài).

Step6:如果達(dá)到最大迭代次數(shù),則更新人工魚(yú)位置，否則跳轉(zhuǎn)到Step3.

Step7:根據(jù)新人工魚(yú)和當(dāng)前最優(yōu)人工魚(yú)的支配關(guān)系,更新個(gè)體最優(yōu)人工魚(yú)位置,即當(dāng)兩條人工魚(yú)存在支配人工魚(yú)時(shí),選擇支配人工魚(yú),否則從中隨機(jī)選取一條人工魚(yú)作為新的個(gè)體最優(yōu)人工魚(yú).

Step8：非劣解篩選.

Step8.1:合并新非劣解集和舊非劣解集,獲取新的非劣解集；

Step8.2:根據(jù)非劣解集中的支配關(guān)系,篩選出新的非劣解集.

Step9:如果達(dá)到最大迭代次數(shù),則輸出最優(yōu)解,否則轉(zhuǎn)到Step2.

4　數(shù)值實(shí)驗(yàn)

4.1編碼方式

4.2數(shù)值算例

算法用Matlab7.0編程,在PC機(jī)上運(yùn)行,參數(shù)設(shè)定為T(mén)max=2000、N=50、Try_number=50、δ=25、Visual=10、Step=1.5、w1=10、w2=1.5.最大值與最小值問(wèn)題可以互相轉(zhuǎn)換,為了能直觀地評(píng)價(jià)解質(zhì)量,把求背包內(nèi)物品的總體積最小問(wèn)題轉(zhuǎn)化為求總體積最大問(wèn)題,即總體積公式變?yōu)?/p>

算例1取10類(lèi)物品,每類(lèi)物品包含5種物品,分別在[1,30],[0,1]和[1,30]中隨機(jī)生成物品的價(jià)值、體積和質(zhì)量,c取162.實(shí)驗(yàn)結(jié)果如圖1和圖2所示.

算例2取20類(lèi)物品,每類(lèi)物品包含5種物品,分別在[1,30]，[0,1]和[1,30]中隨機(jī)生成物品的價(jià)值、體積和質(zhì)量,c取325.實(shí)驗(yàn)結(jié)果如圖3和圖4所示.

5　實(shí)驗(yàn)結(jié)果

圖1　算例1各算法獲得的非劣解分布情況

Fig.1Non-dominated distribution of each algorithm of example 1

圖2　算例1各算法非劣解平均距離曲線

Fig.2Average distance curve of the non-dominated solutions of each algorithm of example 1

圖3　算例2各算法獲得的非劣解分布情況

Fig.3Non-dominated distribution of each algorithm of example 2

圖4　算例2各算法非劣解平均距離曲線

Fig.4Average distance curve of the non-dominated solutions of each algorithm of example 2

對(duì)于本文中的多目標(biāo)背包問(wèn)題,每個(gè)算法獨(dú)立運(yùn)行10次,每次運(yùn)行,3個(gè)算法的初始種群都是相同的,并迭代2 000次,實(shí)驗(yàn)結(jié)果隨機(jī)取其中一次.

由圖1，圖3可以看出,實(shí)驗(yàn)結(jié)果獲得的Pareto最優(yōu)前端在以目標(biāo)空間坐標(biāo)原點(diǎn)為球心的超球面上,非劣解離原點(diǎn)越遠(yuǎn),解的精度越高.因而,采用文獻(xiàn)[3]中的評(píng)價(jià)方法,根據(jù)某一次迭代后獲得的所有非劣解到原點(diǎn)的距離算術(shù)平均值來(lái)評(píng)價(jià)該次迭代的求解精度,再利用平均距離的變化趨勢(shì)來(lái)評(píng)價(jià)算法的收斂性.

物品種類(lèi)為10,如圖1所示,本文算法與遺傳算法搜索到的解基本在一個(gè)球面上,解離原點(diǎn)的距離比粒子群算法遠(yuǎn),且本文搜索到的解比遺傳算法的多.如圖2所示,本文算法的收斂速度比另外兩個(gè)算法快,解比較穩(wěn)定.

當(dāng)物品種類(lèi)為20,如圖3所示,本文算法搜索到的解與原點(diǎn)距離遠(yuǎn)遠(yuǎn)大于另外兩個(gè)算法,且分布均勻.如圖4所示,本文算法的收斂速度,解的精度、穩(wěn)定性和均勻的優(yōu)勢(shì)更加明顯.

6　結(jié)語(yǔ)

本文提出一種基于自適應(yīng)移動(dòng)策略,加入位置全局最優(yōu)信息的人工魚(yú)群算法,并用其求解多目標(biāo)背包問(wèn)題.仿真結(jié)果表明,本文改進(jìn)的人工魚(yú)群算法在求解多目標(biāo)背包問(wèn)題上是有效的,收斂速度和求解精度均優(yōu)于遺傳算法和粒子群算法.隨著多目標(biāo)背包問(wèn)題中物品種類(lèi)增加一倍,本文算法的優(yōu)勢(shì)更加明顯.

[1] 史峰,王輝,胡斐，等.MATLAB智能算法30個(gè)案例分析[M].北京：北京航空航天大學(xué)出版社,2011.

[2] 張雁,肖偉.基于禁忌粒子群求解多目標(biāo)0-1背包問(wèn)題研究與實(shí)現(xiàn)[J].軟件導(dǎo)刊,2012,11(3):36-37.

ZHANG Y, XIAO W. The Research and implementation of multiple knapsack problem on Tabu PSO[J].Software Guide, 2012, 11(3): 36-37.

[3] 郭觀七,楊觀賜,黃韜,等.用遺傳算法求解多目標(biāo)0/1背包問(wèn)題[J].湖南理工學(xué)院學(xué)報(bào),2004,17(4):18-21.

GUO G Q, YANG G C, HUANG T, et al. Solving multi-objective 0/1 knapsack problems by genetic algorithms[J].Journal of Hunan Institute of Science and Technology: Natural Sciences Edition, 2004, 17(4): 18-21.

[4] 溫金寶,蔡延光.基于自適應(yīng)小生境遺傳算法的物流配送路徑優(yōu)化研究[J].廣東工業(yè)大學(xué)學(xué)報(bào),2011,28(1):20-23.

WEN J B, CAI Y G. On the optimization of logistics distribution route based on self-adaption nice genetic algorithm[J].Journal of Guangdong University of Technology, 2011, 28(1): 20-23.

[5] 李枝勇,馬良,張慧珍.蝙蝠算法在多目標(biāo)背包問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)仿真,2013,30(10): 350-353.

LI Z Y, MA L, ZHANG H Z. Application of bat algorithm in multi-objective and multi-choice knapsack problem[J].Journal of Computer Simulation, 2013,30(10): 350-353.

[6] 劉海林,劉永清.多目標(biāo)最優(yōu)進(jìn)化算法中適應(yīng)性的選擇[J].廣東工業(yè)大學(xué)學(xué)報(bào),2002,19(1): 7-10.

LIU H L, LIU Y Q. The fitness selection about evolutionary algorithms for multi-objective optimization[J]. Journal of Guangdong University of Technology, 2002, 19(1): 7-10.

[7] 李曉磊,邵之江,錢(qián)積新.一種基于動(dòng)物自治體的尋優(yōu)模式:魚(yú)群算法[J].系統(tǒng)工程理論與實(shí)踐,2002,22(11):32-38.

LI X L, SHAO Z J, QIAN J X. An optimizing method based on autonomous animats: fish-swarm algorithm[J]. Systems Engineering-Theory & Practice, 2002, 22(11): 32-38.

[8] 王翠茹,周春雷,馬建偉.一種改進(jìn)的人工魚(yú)群算法及其在軟件可靠性優(yōu)化中的應(yīng)用[J].計(jì)算機(jī)研究與發(fā)展,2005,4(增刊): 163-166.

WANG C R, ZHOU C L, MA J W. An Improved artificial fish-swarm algorithm and its application in software reliability optimization[J].Journal of Computer Research and Development, 2005, 4 (S):163-166.

[9] 程永明.群智能優(yōu)化算法及其在通信中的應(yīng)用研究[D].濟(jì)南:山東大學(xué)信息科學(xué)與工程學(xué)院,2010.

[10] JIANG M Y, YUAN D F, CHENG Y M. Improved artificial fish swarm algorithm[C]∥Proceedings of the 5th International Conference on Natural Computation. Tianjin: IEEE: 2009: 281-285.

[11] 王聯(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.

[12] 李曉磊.一種新型的智能優(yōu)化方法——人工魚(yú)群算法[D].杭州:浙江大學(xué)系統(tǒng)工程研究所,2003.

[13] 廖煜雷,蘇玉明,張磊。一種自適應(yīng)人工魚(yú)群算法及其在無(wú)人艇控制中的應(yīng)用[J].中南大學(xué)學(xué)報(bào)：自然科學(xué)版,2013, 44(10): 4109- 4116.

LIAO Y L, SU Y M, ZHANG L. Adaptive artificial fish swarm algorithm and application in control of unmanned surface vessel[J].Journal of Central South University：Science and Technology, 2013,44(10): 4109- 4116.

[14] 朱旭輝,倪志偉,程美英.變步長(zhǎng)自適應(yīng)的改進(jìn)人工魚(yú)群算法[J].計(jì)算機(jī)科學(xué),2015,42(2): 210-216.

ZHU X H, NI Z W, CHENG M Y. Self-adaptive improved artificial fish swarm algorithm with changing step[J].Computer Science, 2015, 42(2): 210-216.

[15] 馬憲民,劉妮.自適應(yīng)視野的人工魚(yú)群算法求解最短路徑問(wèn)題[J].通信學(xué)報(bào),2014,35(1): 1-6.

MA X M, LIU N. Improved artificial fish-swarm algorithm based on adaptive vision for solving the shortest path problem[J]. Journal on Communications, 2014, 35(1): 1-6.

[16] 江銘武,袁東風(fēng).人工魚(yú)群算法及其應(yīng)用[M].北京：科學(xué)出版社,2012.

An Improved Artificial Fish Swarm Algorithm for Multi-objective Knapsack Problem

Huang Mei-hua, Wen Jie-chang, He Yong

(School of Applied Mathematics, Guangdong University of Technology, Guangzhou 510520, China)

As a swarm intelligence, the Artificial Fish Swarm Algorithm(AFSA) has its weakness in solving the problem of Multi-objective Knapsack, such as blindness search, low speed of convergence and low accuracy in solution. Combining the global information of the artificial fish position with improving the moving strategy of artificial fish self-adapting, an improved AFSA is proposed. Simulation on multi-objective knapsack problem shows that the convergence rate as well as the accuracy in the non-dominated solutions which have been found out in the improved AFSA is superior to Genetic Algorithm and Particle Swarm Optimization.

multi-objective optimization; Knapsack problem; artificial fish swarm algorithm; self-adaptive

2015- 04- 29

廣東省特色創(chuàng)新項(xiàng)目(2014KTSCX055)

黃美華(1987-)，女，碩士研究生，主要研究方向?yàn)樽顑?yōu)化方法與應(yīng)用.

10.3969/j.issn.1007- 7162.2016.05.008

F252; TP301

A

1007-7162(2016)05- 0044- 05