黃美華， 溫潔嫦， 何　勇

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

?

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

黃美華， 溫潔嫦， 何勇

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

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

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

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

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

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

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

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

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

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

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

2　人工魚群算法

2.1人工魚群算法基本原理

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

2.2人工魚移動策略

2.3自適應(yīng)步長

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

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

2.4全局人工魚群算法

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

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

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

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

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

3.1.1覓食行為

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

3.1.2聚群行為

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

3.1.3追尾行為

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

3.1.4隨機(jī)行為

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

3.2算法基本流程

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

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

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

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

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

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

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

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

Step8：非劣解篩選.

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

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

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

4　數(shù)值實驗

4.1編碼方式

4.2數(shù)值算例

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

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

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

5　實驗結(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

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

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

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

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

6　結(jié)語

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

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

[2] 張雁,肖偉.基于禁忌粒子群求解多目標(biāo)0-1背包問題研究與實現(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背包問題[J].湖南理工學(xué)院學(xué)報,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é)報,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)背包問題中的應(yīng)用[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é)報,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] 李曉磊,邵之江,錢積新.一種基于動物自治體的尋優(yōu)模式:魚群算法[J].系統(tǒng)工程理論與實踐,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ōu)化中的應(yīng)用[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)國,洪毅,施秋紅.全局版人工魚群算法[J].系統(tǒng)仿真學(xué)報,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)化方法——人工魚群算法[D].杭州:浙江大學(xué)系統(tǒng)工程研究所,2003.

[13] 廖煜雷,蘇玉明,張磊。一種自適應(yīng)人工魚群算法及其在無人艇控制中的應(yīng)用[J].中南大學(xué)學(xué)報：自然科學(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] 朱旭輝,倪志偉,程美英.變步長自適應(yīng)的改進(jìn)人工魚群算法[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)視野的人工魚群算法求解最短路徑問題[J].通信學(xué)報,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ī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)新項目(2014KTSCX055)

黃美華(1987-)，女，碩士研究生，主要研究方向為最優(yōu)化方法與應(yīng)用.

10.3969/j.issn.1007- 7162.2016.05.008

F252; TP301

A

1007-7162(2016)05- 0044- 05