董亞科，杜 軍，李 博，丁 超

(空軍工程大學(xué) 航空航天工程學(xué)院，陜西 西安710038)

0 引 言

多選擇背包問題是經(jīng)典的NP 難問題，現(xiàn)實(shí)中的很多問題都是以多選擇背包問題為背景而建模的。因此，對該類的研究具有重大理論意義和應(yīng)用價(jià)值。目前對NP 難問題已經(jīng)提出如人工魚群算法、啟發(fā)式算法、粒子群算法、遺傳算法等諸多方法［1～10］，但在大規(guī)模約束條件下這些算法很難獲得最優(yōu)解。狼群算法在多維多峰值連續(xù)函數(shù)尋優(yōu)方面取得了很好效果［11］，如何將狼群算法擴(kuò)展到離散領(lǐng)域，準(zhǔn)確地找到最優(yōu)解，在研究狼群算法和多選擇背包問題兩方面都具有重要意義。

本文提出的一種求解多選擇背包問題離散狼群算法(discrete wolf pack algorithm，DWPA)通過采用遺傳算法編碼規(guī)則，把人工狼引入到了離散領(lǐng)域。利用學(xué)習(xí)機(jī)制，使得人工狼優(yōu)秀基因得到繼承，實(shí)現(xiàn)了人工狼之間的交流，保證了離散狼群算法的收斂性，通過人工狼的“強(qiáng)者生存”群體更新策略，保留了最優(yōu)個體，增加了搜索的多樣性，猛狼奔襲采用了自適應(yīng)步長，加快了算法收斂速度。

1 多選擇背包模型

多選擇背包問題有如下定義:有一個載重重量一定的背包和一批要放進(jìn)該背包具有一定價(jià)值和重量的物品，這些物品首先被分為相互排斥的若干類，每一類中有若干個不同物品。從每一類物品中取一個物品放入背包中，在背包內(nèi)的物品重量在不超過背包載重前提下，使背包內(nèi)物品價(jià)值總和最大。對該問題的數(shù)學(xué)描述如下

其中，i 為不同分類的下標(biāo)，j 為每一類中不同物品的下標(biāo)，ni為第i 類物品的數(shù)量，cij為第i 類中第j 個物品的價(jià)值。m 為不同分類的數(shù)量，Wij為第i 類中第j 個物品的重量，w 為背包的載重，當(dāng)Xij=1 時(shí)，表示第i 類中的第j 個物品放入背包;當(dāng)Xij=0 時(shí)，表示第i 類中的第j 個物品不放入背包。

2 狼群優(yōu)化算法

狼群過著群居且分工明確的群居生活，根據(jù)職能的不同，人工狼分為頭狼、探狼和猛狼。頭狼:頭狼是狼群中的首領(lǐng)，它不斷地根據(jù)狼群所感知的信息進(jìn)行決策，指揮狼群盡快的捕捉到獵物。探狼:尋找獵物時(shí)，狼群會派出幾只敏銳的探狼在獵物活動范圍內(nèi)隨機(jī)尋找，根據(jù)獵物氣味的濃度進(jìn)行決策，濃度越高表明離獵物越近。猛狼:當(dāng)探狼發(fā)現(xiàn)獵物后會立即報(bào)告給頭狼，頭狼通過嚎叫召喚周圍的猛狼對獵物進(jìn)行圍攻，猛狼聞聲會朝著該探狼奔襲，向獵物靠近，狼群算法流程如圖1。

圖1 WPA 流程圖Fig 1 Flow chart of WPA

狼群算法具體步驟:

1)初始化狼群種群中個體數(shù)目N，最大迭代次數(shù)kmax，探狼比例因子α，最大游走次數(shù)Tmax，種群更新比例因子R等。

2)選擇最優(yōu)個體為頭狼，除頭狼外的S_num 人工狼為探狼并執(zhí)行游走行為，直到某只探狼感覺到的獵物氣味濃度Yi大于頭狼所感知的獵物氣味濃度Ylead或達(dá)到最大游走次數(shù)。

3)猛狼奔襲:若途中猛狼感知的獵物氣味濃度Yi＞Ylead，則Yi=Ylead，替代頭狼發(fā)起召喚行為;若Yi＜Ylead，則猛狼繼續(xù)奔襲直到距離獵物的距離小于閾值dnear。

4)對參與圍攻的人工狼位置進(jìn)行更新。

5)挑選出距離獵物最近的人工狼代替頭狼，完成對頭狼的更新，并按照種群更新比例因子對群體進(jìn)行更新，淘汰距離獵物較遠(yuǎn)的人工狼。

6)判斷是否達(dá)到最大迭代次數(shù)Tmax或精度要求，若達(dá)到要求，則輸出頭狼位置;否則，轉(zhuǎn)至步驟(2)。

3 離散空間的DWPA

DWPA 關(guān)鍵問題是人工狼位置的更新的表示，同時(shí)，根據(jù)離散量的特點(diǎn)定義人工狼位置更新的運(yùn)動方程。設(shè)狼群的捕獵空間為一個M×N 的空間，其中，M 為狼群中人工狼數(shù)目，N 為要尋優(yōu)的變量數(shù)。人工狼i 的狀態(tài)可表示為:Xi=［Xi1，Xi2，…，XiN］，其中，XiN為第i 匹人工狼在欲尋優(yōu)的第d(d=1，2，3，…，N)維變量空間中的位置;人工狼所感知到的氣味濃度為y=f(x)，其中，y 就是要尋優(yōu)的目標(biāo)函數(shù)。

3.1 人工狼的位置

每個人工狼染色體定義為按一定規(guī)則編碼的個體，遺傳算法中的一個染色體相當(dāng)于狼群算法中的一個人工狼，設(shè)有M 個人工狼組成一個群體，第i 個狼表示一N 維的向量Xi=［Xi1，Xi2，Xi3，…，XiN］，i=1，2，3，…，M，即第i 個狼在空間中的位置是Xij。本文編碼方式采用正整數(shù)編碼。在正整數(shù)編碼方式中，種群中每一個人工狼的染色體由N個基因組成，分別對應(yīng)著N 個不同的分類，其中第i 個基因是從集合Ni(Ni為第i 類所有物品編號所構(gòu)成的集合{1，2，…，ni})中任意選取的一個正整數(shù)，即基因在染色體中的位置用來表示選取的物品所在的類的編號，而基因值則表示物品在該類中的編號。

圖2 為人工狼的染色體。

圖2 編碼規(guī)則Fig 2 Coding rule

3.2 學(xué)習(xí)機(jī)制

狼群算法應(yīng)用在離散空間的關(guān)鍵問題是解決人工狼位置更新的表示，學(xué)習(xí)機(jī)制是一種向精英個體不斷學(xué)習(xí)的行為，使精英個體的優(yōu)秀基因得到繼承，以此完成向頭狼的奔襲，人工狼向優(yōu)秀個體學(xué)習(xí)的過程，是人工狼不斷向頭狼靠攏的過程。當(dāng)頭狼發(fā)起召喚，人工狼向頭狼奔襲時(shí)，隨機(jī)選擇頭狼染色體上的若干編碼，賦給對應(yīng)位置上的該人工狼的染色體，這樣有利于開辟新的解，防止早熟而陷入局部最優(yōu)。

3.3 位置更新機(jī)制

本文通過引入學(xué)習(xí)機(jī)制，重新設(shè)計(jì)了狼群算法中人工探狼游走、猛狼奔襲和群狼圍攻過程。

1)人工探狼游走:當(dāng)前頭狼位置為感受獵物氣味濃度最高的人工狼。假設(shè)人工探狼Yi的染色體編碼［Xi1，Xi2，…，XiN］，利用遺傳算法中染色體基因的變異思想，隨機(jī)對每個人工探狼染色體的個編碼進(jìn)行變異操作，然后計(jì)算探狼Yi當(dāng)前位置的獵物氣味濃度，如果當(dāng)前獵物氣味濃度大于頭狼所感知的氣味濃度，表明獵物離探狼Yi的位置更近且該探狼最有可能捕獲獵物，于是探狼Yi代替頭狼并發(fā)起召喚行為，即Ytead=Yi。

探狼游走步長定義如下

其中，λ∈［0，1］，L 為編碼長度。

2)人工猛狼奔襲:假設(shè)人工猛狼的染色體編碼為［Xi1，Xi2，…，XiN］，頭狼發(fā)起召喚行為后，猛狼i 以較大步長向頭狼的位置奔襲。利用學(xué)習(xí)機(jī)制，采用自適應(yīng)步長，選擇頭狼染色體的個編碼，用這個編碼替換猛狼對應(yīng)的位置上的編碼，完成猛狼i 向頭狼Ylead位置的奔襲，奔襲途中，若猛狼i 感知到的獵物氣味濃度Yi＞Ylead，則Ylead=Yi，該猛狼轉(zhuǎn)換為頭狼并發(fā)起召喚行為;若Yi＜Ylead，則該猛狼繼續(xù)向頭狼奔襲直到其與頭狼嗅到的獵物氣味濃度的差值小于某閾值P 時(shí)加入到對獵物的圍捕。

自適應(yīng)奔襲步長定義如下

式中 L 為編碼長度，Ypg為當(dāng)前狼群中最大的獵物氣味濃度，Ymax為當(dāng)前猛狼中最大的獵物氣味濃度，Yi為猛狼i 嗅到的獵物氣味濃度。

3)人工狼圍捕:當(dāng)其它人工狼嗅到的食物氣味濃度和頭狼嗅到的食物濃度之差小于設(shè)定的閾值P，狼群展開圍捕行為。在人工狼的新的圍捕策略中，即對每個人工狼的染色體［Xi1，Xi2，Xi3，…，XiN］，利用學(xué)習(xí)機(jī)制，隨機(jī)選擇染色體一個編碼，將當(dāng)前頭狼染色體對應(yīng)位置上的編碼賦到該人工狼的染色體的對應(yīng)位置上，實(shí)現(xiàn)對獵物的圍捕

4 仿真實(shí)驗(yàn)

4.1 DWPA 求解多選擇背包問題

為了說明本文提出的求解多選擇背包問題的DWPA的有效性，采用文獻(xiàn)［12］中提出的一個含有8 類物品的多選擇背包問題典型例子進(jìn)行仿真實(shí)驗(yàn)，文獻(xiàn)［12］中設(shè)置種群規(guī)模為40，迭代次數(shù)為100 次，進(jìn)行40 次運(yùn)算，找到最優(yōu)解34 的概率為67.5%

表1 表示不同迭代次數(shù)下DWPA 找到最優(yōu)解34 的概率，DWPA 的準(zhǔn)確性明顯優(yōu)于遺傳算法。

表1 不同迭代次數(shù)下DWPA 找到最優(yōu)結(jié)果的準(zhǔn)確率Tab 1 Accuracy of DWPA finding the optimal result under different number of iterations

4.2 離散空間的DWPA 自適應(yīng)步長測試

針對文獻(xiàn)［12］提出的多選擇背包問題，表2 記錄運(yùn)行次數(shù)均為100 次，求得最優(yōu)解34 時(shí)的平均迭代次數(shù)。從表中可以明顯看出:自適應(yīng)步長的平均迭代次數(shù)和運(yùn)行時(shí)間少于其他步長的平均迭代次數(shù)和運(yùn)行時(shí)間，說明了自適應(yīng)步長的有效性。

表2 不同步長時(shí)找到最優(yōu)解時(shí)的平均迭代次數(shù)Tab 2 Average number of iterations finding the optimal solution of different step length

5 結(jié) 論

以求解多選擇背包問題為例，提出了一種基于離散空間的DWPA 的具體實(shí)現(xiàn)，DWPA 中使用了自適應(yīng)步長，增加了搜索效率。采用了學(xué)習(xí)機(jī)制，有效實(shí)現(xiàn)人工狼的交流，使算法在搜索效率和搜索精度方面得到提高。仿真實(shí)驗(yàn)表明:DWPA 具有非常好的性能，能夠成功應(yīng)用到NP－h(huán)ard 等組合優(yōu)化問題領(lǐng)域。

［1］ Sun Youfa，Gao Jingguang，Zhang Chengke，et al.Chaotic genetic algorithm with feedback and its applications to constrained optimization［J］.Journal of South China University of Technology:Natural Science Edition，2007，35(1):19－23.

［2］ Frevile A.The multi－optional 0－1knapsack problem:An overview［J］.European Journal of Operational Research，2004，155(1):1－21.

［3］ Gen M，Cheng R，Wang D.Genetic algorithm for solving shortest path problems［C］∥IEEE International Conference on Evolutional Computation，Piscataway:IEEE，1997:401－406.

［4］ Andonov R，Poirriez V，Rajopadhye S.Unbouned knapsack problem:Dynamic program revisited［J］.European Journal of Operational Research，2000，123(2):394－407.

［5］ Yuan Liwei，Liu Fuxian，Zhao Baojun.Improved GA and its application to knapsack problem［J］.System Engineering and Electronics，2005，27(4):718－719.

［6］ Hong Baojiang，Yang Qigui.Fast solution algorithm of multiple choice knapsack problem［J］.Journal of South China University of Technology:Natural Science Edition，2009，37(4):42－45.

［7］ 陳 娟，王志剛，夏慧明.粒子群優(yōu)化算法求解多選擇背包問題［J］.價(jià)值工程，2012，2(5):197－198.

［8］ 葉宇風(fēng).多重群體遺傳算法在多選擇背包問題中的應(yīng)用［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2005，26(12):3442－3444.

［9］ Lu Haiyan，Chen Weiqi.Dynamic－objective particle S－warm optimization for constrained optimization［J］.Journal of Combinational Optimization，2006，12(4):409－419.

［10］Gary M，Johnsin D.Computer and intractability:A guide to the theory of NP－completeness［M］.New York:［s.n.］，1979.

［11］吳虎勝，張鳳鳴，吳廬山.一種新的群體智能算法狼群算法［J］.系統(tǒng)工程與電子技術(shù)，2013，35(11):2430－2438.

［12］玄光男，程潤偉，于歆杰，等.遺傳算法與工程優(yōu)化［M］.北京:清華大學(xué)出版社，2004:56－59.