劉小娟，封成智，王聯(lián)國

(甘肅農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，甘肅 蘭州 730070)

背包問題(knapsack problem，KP)[1]是20世紀50年代末期由Dantzing首次提出.它既是計算機科學(xué)領(lǐng)域中的經(jīng)典NP-complete問題，也是組合優(yōu)化問題之一.截止目前，背包問題的理論價值和應(yīng)用價值已在整數(shù)規(guī)劃、資源配置、項目選擇、貨物裝載和決策投資等諸多領(lǐng)域應(yīng)用中得到了很好地體現(xiàn).傳統(tǒng)求解0-1背包問題(0-1 Knapsack Problem，0-1KP)的方法有回溯法、動態(tài)規(guī)劃法和分支界定法等，這類方法往往存在某種難以克服的缺陷，如隨著問題規(guī)模的增大會導(dǎo)致算法的運行時間明顯變長.近年來興起的群體智能優(yōu)化算法能快速、高效、精確地求解0-1KP，如粒子群算法[2]、混合蛙跳算法[3]、人工蜂群算法[4]、遺傳算法[5]、獅群算法[6]、煙花算法[7]、混合蝙蝠算法[8-9]等.

2016年，澳大利亞格里菲斯大學(xué)教授Seyedali Mirjalili提出了一種基于正弦余弦函數(shù)模型的群體智能優(yōu)化算法—正弦余弦算法(sine cosine algorithm，SCA)[10].區(qū)別于以模擬自然界生物行為協(xié)同工作機理為核心的其它元啟發(fā)式智能優(yōu)化算法，SCA是一種獨有的群體智能優(yōu)化算法，它的顯著特點是利用三角函數(shù)Sine和Cosine模型的周期震蕩性特征實現(xiàn)算法的搜索尋優(yōu).與其它智能優(yōu)化算法一樣，SCA在迭代后期仍易出現(xiàn)一系列問題，如收斂速度慢、求解精度低和局部開發(fā)能力差.

迄今為止，關(guān)于SCA及其諸多改進算法已被成功應(yīng)用于函數(shù)優(yōu)化、電網(wǎng)故障、圖像處理、特征選擇等領(lǐng)域中[11～15].因SCA提出時間較短，對該算法的研究正處于中前期探索階段，并且鮮有關(guān)于利用SCA的改進算法來求解離散型優(yōu)化問題的研究，如0-1 KP、高維KP及折扣KP.

因此，本文借鑒文獻[16]中群體智能優(yōu)化算法的混合方法，將人工蜂群算法(artificial bee colony，ABC)[17]與正弦余弦算法進行混合，并結(jié)合ABC算法中采蜜蜂算子具有較強局部開發(fā)能力和SCA中正余弦算子具有較好全局探索能力的優(yōu)勢，提出了一種用于求解0-1背包問題的改進正弦余弦算法(I-SCA)，并利用I-SCA求解經(jīng)典組合優(yōu)化中的0-1 KP，以說明該算法的有效性和可行性.

1 背景知識

1.1 正弦余弦算法

SCA基于數(shù)學(xué)中三角函數(shù)模型的周期震蕩性使其趨于問題的最優(yōu)解，同時嵌入隨機參數(shù)和自適應(yīng)參數(shù)，平衡算法的全局探索與局部開發(fā)階段.SCA求解優(yōu)化問題始于一組隨機解，并通過全局探索和局部開發(fā)兩個階段逐步趨向全局最優(yōu)解.

設(shè)Xi=(Xi1，Xi2,…，XiD)T為第i個個體的空間位置，i∈{1,2,…,N}，N為種群規(guī)模，D為搜索空間的維度，f(Xi)為第i個個體的目標函數(shù)值，P=(P1,P2,…,PD)T為種群中最優(yōu)個體的空間位置。在搜索過程中，第i個個體的第j維按照公式(1)更新空間位置：

(1)

(2)

式中：t、T分別為當前迭代次數(shù)和最大迭代次數(shù)，a為常數(shù)2.

1.2 人工蜂群算法

ABC算法是土耳其學(xué)者Dervis Karaboga于2005年受蜜蜂啟發(fā)行為提出的一種覓食尋優(yōu)算法。與經(jīng)典的優(yōu)化方法相比，該算法對目標函數(shù)和約束幾乎無要求，在搜索過程中基本不利用外部信息，僅以適應(yīng)度函數(shù)作為進化的依據(jù)，同時Pholdee等[18]已證明該算法是性能最好的優(yōu)化算法之一，因而備受科研人員關(guān)注，并在解決各種復(fù)雜問題中取得了顯著成效.

ABC算法利用不同類型蜜蜂(采蜜蜂、觀察蜂和偵察蜂)的分工協(xié)作機制以求解問題的最優(yōu)解，主要包括初始化、采蜜蜂、觀察蜂和偵察蜂4個階段，每個階段具體為：

(1)初始化階段。在解搜索空間中按照公式(3)隨機初始化N個個體的空間位置：

(3)

(2)采蜜蜂階段。計算蜜源的適應(yīng)度函數(shù)值，并根據(jù)適應(yīng)度函數(shù)值大小將蜜蜂分為采蜜蜂和觀察蜂，并執(zhí)行采蜜蜂階段。采蜜蜂按照搜索公式(4)進行鄰域搜索并產(chǎn)生新蜜源，同時計算新蜜源的適應(yīng)度函數(shù)值，再采用貪婪選擇策略或輪盤賭法更新蜜源.

new_Xij=Xij+rand2()(Xij-Xkj)

(4)

式中：rand2()為[-1,1]之間的隨機數(shù)，j∈{1,2,…,D}，k∈{1,2,…,N}，j和k隨機選取，且k≠i，N為蜜源總數(shù).

(3)觀察蜂階段。每只觀察蜂按照與蜜源適應(yīng)度值成比例的概率大小尋找新蜜源，并轉(zhuǎn)化為采蜜蜂按公式(4)進行鄰域搜索，同時計算新蜜源的適應(yīng)度函數(shù)值，并決定是否更新蜜源位置.

(4)偵察蜂階段。偵察蜂搜尋蜂巢周圍潛在的蜜源。當連續(xù)停留次數(shù)n到一定的閾值L仍未找到更優(yōu)空間位置時，即表明陷入了局部最優(yōu)，此時蜜蜂的角色由采蜜蜂或觀察蜂轉(zhuǎn)變?yōu)閭刹旆洌凑展?3)重新搜索隨機產(chǎn)生新蜜源.

1.3 0-1背包問題

0-1 KP作為KP的一個分支，是一種帶有約束條件的離散優(yōu)化問題.經(jīng)典0-1 KP可以形象地描述為[1]：

給定含有重量和價值的n個物品和有載質(zhì)量限制的一個背包，判斷如何將物品裝入背包，并使當前背包總重量在不超過背包最大載質(zhì)量的前提下，背包內(nèi)所裝入的物品總價值達到最大.物品i被選擇的狀態(tài)只有2種，即物品i裝入與不裝入背包(絕不允許將物品分割裝入背包)，則定義決策變量Xi，當Xi=1時，物品i裝入背包；當Xi=0時，物品i不裝入背包.故0-1 KP的數(shù)學(xué)模型為：

(5)

式中：Wi(Wi>0) 和Vi(Vi>0)分別為第i個物品的質(zhì)量和價值，i∈{1，2，…,n}，C(C>0)為背包的最大載質(zhì)量.

2 貪心改進正弦余弦算法求解0-1背包問題

2.1 改進策略

2.1.1 按冪遞減函數(shù)自適應(yīng)調(diào)整參數(shù)r1調(diào)整參數(shù)r1為冪遞減函數(shù)，表達式見公式(6).使算法在迭代前期，SCA全局探索能力最強；在迭代中期，算法逐步從全局探索向局部開發(fā)階段過渡；到迭代后期，r1非線性遞減，逐步為0，使算法局部開發(fā)能力增強.

(6)

式中：δ為調(diào)整參數(shù)，其值設(shè)為5，主要作用是調(diào)整非線性冪遞減函數(shù)的下降速率.

2.1.2 更改位置更新方程 考慮到正弦函數(shù)sin(r2)取正值和負值的概率相等，文獻[11]去掉公式(1)中的絕對值符號，故本文將公式(1)的位置更新方程改寫為：

(7)

2.1.3 混合策略 利用ABC算法中的采蜜蜂算子增強SCA的局部開發(fā)能力，提高算法的優(yōu)化精度.

在迭代過程中，按照概率Pr執(zhí)行正余弦算子，按照概率1 -Pr執(zhí)行采蜜蜂算子，同時采用貪婪選擇策略使較優(yōu)的個體進入下一代，并利用偵察蜂算子防止算法陷入局部極值，提高全局探索能力，較好地平衡SCA的全局探索和局部開發(fā)階段.

2.2 I-SCA的時間復(fù)雜度分析

算法的時間復(fù)雜度主要與種群規(guī)模、問題維度和最大迭代次數(shù)有關(guān)。假設(shè)種群規(guī)模為N，問題維度為D，最大迭代次數(shù)為T。由于初始化階段的時間復(fù)雜度為O(N×D)，可以忽略不計.

I-SCA的時間復(fù)雜度主要由基本SCA、采蜜蜂算子和偵察蜂算子三部分組成，并按照概率Pr執(zhí)行正余弦算子，按照概率1-Pr執(zhí)行采蜜蜂算子。正余弦算子的時間復(fù)雜度為O(N×Pr×D×T)，采蜜蜂算子的時間復(fù)雜度為O(N×(1-Pr)×T)，偵察蜂算子的最大時間復(fù)雜度為O(N×D×T/L)，則I-SCA的時間復(fù)雜度為：

O(I-SCA)=O(N×Pr×D×T)+O(N×(1-Pr)×T)+O(N×D×T/L)

(8)

基本SCA的時間復(fù)雜度為：

O(SCA)=O(N×D×T)

(9)

2.3 基于貪心I-SCA求解0-1背包問題

由于大多數(shù)智能優(yōu)化算法的尋優(yōu)過程是連續(xù)的，僅適用于求解連續(xù)型數(shù)值優(yōu)化問題，而組合優(yōu)化問題中的0-1 KP屬于離散型問題，則需要將問題解空間內(nèi)的連續(xù)解以一定的編碼方式進行編碼，并使其轉(zhuǎn)化為離散解.

文獻[3]借鑒文獻[2]的思想和貪心變換算法(GTA)[19]，提出了一種用于求解0-1 KP的二進制混合蛙跳算法.故本文受文獻[3]的啟發(fā)，將GTA引入到I-SCA中，提出一種求解0-1 KP問題的貪心I-SCA.

2.3.1 二進制編碼方式 采用二進制的編碼方式[2]實現(xiàn)I-SCA對離散解空間問題的求解.假設(shè)用有序向量對(X，Y)代表解空間中的每一個候選解，其中，X=(x1，x2,…，xD)T為D維實向量，Y=(y1，y2,…,yD)T為對應(yīng)的二進制向量.本文任意給定一個正數(shù)s，其值設(shè)為5，以X∈[-s，s]D為所求問題的連續(xù)解空間，Y∈[0，1]D為所求問題對應(yīng)的二進制解空間，則從連續(xù)解空間到離散解空間的編碼轉(zhuǎn)化方式為：

(10)

式中：sig(xi)是一個將實向量映射為二進制向量的sigmoid函數(shù)，其表達式為：

(11)

2.3.2 貪心變換算法(GTA) 包括SCA在內(nèi)的大多數(shù)智能優(yōu)化算法在求解0-1 KP問題時會遇到不滿足0-1 KP約束條件的個體，即出現(xiàn)非正常編碼的個體，則需要按照一定的修復(fù)策略來處理非正常編碼個體并使其轉(zhuǎn)化為正常編碼個體.因而，本文借鑒GTA[19]的思想處理I-SCA在優(yōu)化過程中產(chǎn)生的不可行解.

1)將背包中的物品按照價重比Vi/Wi由大到小排序(i=1,2，…,D)，得到序列Q=(Q1，Q2，…，QD)；

2)記錄當前背包序列中所存放物品的臨時重量Tempwi；

3)不斷修正個體，直到背包內(nèi)物品的總重量Temp>C；

4)算法終止，輸出修正后的編碼個體Y.

2.3.3 修正連續(xù)解算法(RCSA) 為使算法在下次迭代時能從正確的實向量開始進化，故根據(jù)修正后的編碼個體Y，反向修正有序向量對(X，Y)中的X，RCSA描述為：

1)j=1；

3)j=j+1，若j<=D，轉(zhuǎn)向步驟2，否則，輸出X.

2.3.4 基于貪心I-SCA求解0-1背包問題的步驟 基于貪心I-SCA求解0-1背包問題流程圖如圖1所示.

3 仿真試驗與分析

3.1 試驗環(huán)境

所有仿真試驗在64 bit Windows10操作系統(tǒng)，Intel(R) Core(TM) i5-6200U CPU @ 2.30 GHz處理器，4 G內(nèi)存的計算機上進行，算法采用軟件Microsoft Visual C++6.0編譯實現(xiàn).

3.2 背包問題及參數(shù)設(shè)置

為驗證本文提出的I-SCA在求解0-1 KP方面的尋優(yōu)性能，選用文獻[20]中的10個經(jīng)典0-1 KP進行仿真試驗，具體0-1 KP參數(shù)設(shè)置詳見文獻，試驗中設(shè)置0-1KP的目標精度如表1所示.

3.3 I-SCA與基本SCA的性能比較

實驗中，2種算法的參數(shù)設(shè)置為：種群規(guī)模N=20，最大迭代次數(shù)T=500，運行次數(shù)R=30.另外，I-SCA中的閾值L=150，2.1.3小節(jié)中的概率Pr=0.5.基本SCA中也采用GTA和RCSA修復(fù)不可行解.表2列出了2種算法求解10個經(jīng)典0-1 KP的實驗結(jié)果，評價指標包括2種算法獨立運行30次后取得的平均最優(yōu)值、標準差、最優(yōu)值、最差值和成功率.與此同時，2種算法求解0-1 KP獲得平均最優(yōu)值的收斂曲線圖，見圖2～11.其中，平均最優(yōu)值反映算法的收斂速度和求解精度，標準差反映算法的穩(wěn)定性和魯棒性，最優(yōu)值和最差值反映可行解的質(zhì)量，成功率反映算法達到目標精度的執(zhí)行效率，收斂曲線圖反映算法的收斂趨勢變化(表中加粗數(shù)據(jù)代表對比結(jié)果的最優(yōu)值).

圖1 基于貪心I-SCA求解0-1背包問題流程圖Figure 1 Flowchart for solving the 0-1 knapsack problem based on greedy I-SCA

表1 10個經(jīng)典背包問題的目標精度

表2 I-SCA與基本SCA求解0-1背包問題的實驗結(jié)果

根據(jù)表2，從2種算法取得的平均最優(yōu)值來看，除了背包問題f9，2種算法均能取得理論最優(yōu)值外，相比基本SCA，在其它9個0-1 KP上，I-SCA的收斂速度和求解精度顯著提高，并最終收斂到各自的理論最優(yōu)值；從2種算法取得的標準差來看，相比基本SCA，I-SCA在背包問題f5上取得的標準差雖未能達到最小值，但數(shù)量級也顯著提高，同時在其它0-1 KP上的標準差均為0，魯棒性強；從2種算法取得的最優(yōu)值和最差值來看，相比基本SCA，在10個0-1 KP中I-SCA獲得的可行解質(zhì)量均相對較高；從兩種算法取得的成功率來看，相比基本SCA，I-SCA在10個0-1 KP上取得的成功率分別增加了87%、54%、10%、14%、10%、54%、23%、100%、0%和100%.

圖2 f1平均最優(yōu)值的收斂曲線Figure 2 Convergence curve of the average optimal value of f1

圖3 f2平均最優(yōu)值的收斂曲線Figure 3 Convergence curve of the average optimal value of f2

圖4 f3平均最優(yōu)值的收斂曲線Figure 4 Convergence curve of the average optimal value of f3

圖5 f4平均最優(yōu)值的收斂曲線Figure 5 Convergence curve of the average optimal value of f4

圖6 f5平均最優(yōu)值的收斂曲線Figure 6 Convergence curve of the average optimal value of f5

圖7 f6平均最優(yōu)值的收斂曲線Figure 7 Convergence curve of the average optimal value of f6

圖8 f7平均最優(yōu)值的收斂曲線Figure 8 Convergence curve of the average optimal value of f7

圖9 f8平均最優(yōu)值的收斂曲線Figure 9 Convergence curve of the average optimal value of f8

圖10 f9平均最優(yōu)值的收斂曲線Figure 10 Convergence curve of the average optimal value of f9

以上收斂曲線圖中，橫坐標為迭代次數(shù)，縱坐標為函數(shù)平均最優(yōu)值.分析曲線圖發(fā)現(xiàn)，對背包問題f1、f2、f5、f6和f10，I-SCA在迭代次數(shù)不到100次時基本上開始收斂，并隨著迭代次數(shù)的加大，收斂速度加快，直到最終收斂到理論最優(yōu)值；對背包問題f3，I-SCA一開始就已經(jīng)取得理論最優(yōu)值，表現(xiàn)出了很好的收斂速度；對背包問題f4和f7，I-SCA前期收斂速度相對較好，直到迭代次數(shù)在200次左右時，其收斂速度加快并收斂到理論最優(yōu)值；對背包問題f8，I-SCA前期收斂速度勻速增大，直到迭代次數(shù)達到230次左右時，算法逐漸收斂并趨向理論最優(yōu)值；對背包問題f9，I-SCA和SCA的優(yōu)化效果相同，并在固定迭代次數(shù)內(nèi)均已收斂到理論最優(yōu)值.由此可見，在求解以上10個經(jīng)典的0-1 KP時，I-SCA相比基本SCA在收斂速度和優(yōu)化精度方面都有顯著的改進效果.

圖11 f10平均最優(yōu)值的收斂曲線Figure 11 Convergence curve of the average optimal value of f10

表3 I-SCA與其它元啟發(fā)式算法求解0-1背包問題的試驗結(jié)果

3.4 I-SCA與其它元啟發(fā)式算法的性能比較

為進一步測試I-SCA的性能，將其與求解0-1背包問題的其它元啟發(fā)式算法進行比較.為體現(xiàn)比較的公平性，將I-SCA的參數(shù)設(shè)置與文獻[21]相同，即N=30，T=1 000，R=50.其余算法的試驗數(shù)據(jù)來自文獻，表3列出了I-SCA與其它元啟發(fā)式算法求解0-1 KP的試驗結(jié)果，評價指標包括平均最優(yōu)值(Ave)、標準差(Std)、最優(yōu)值(Best)和最差值(Worst).

表3結(jié)果顯示，對于背包問題f1、f6和f7，I-SCA與算法BA、BCS、WDO、GGA、CCS和CWDO都取得了理論最優(yōu)值；對于背包問題f2，I-SCA與算法BCS、GGA、CCS和CWDO取得了理論最優(yōu)值；對于背包問題f3、f4和f9，I-SCA與其它7種算法一樣，同樣取得了其理論最優(yōu)值；對于背包問題f5，除了I-SCA在標準差方面稍遜于對比算法外，算法取得的平均最優(yōu)值、最大值和最小值上已達到了理論最優(yōu)值；對于背包問題f8，I-SCA與算法BCS、GGA和CWDO都取得了理論最優(yōu)值；對于背包問題f10，I-SCA優(yōu)于算法PSO、BA和WDO，與算法BCS、GGA和CWDO一樣，同樣取得了理論最優(yōu)值.總體來看，相比其它7種算法，I-SCA在10個經(jīng)典低維0-1 KP上的求解效果基本上是理想的，表現(xiàn)出了優(yōu)良的優(yōu)化性能.

綜上所述，基于貪心I-SCA求解0-1 KP的收斂速度較快、求解精度較高，表明了I-SCA同樣能用于求解0-1 KP，并能達到相對較好的求解效果.

4 結(jié)論

本文將ABC算法中的采蜜蜂算子與偵察蜂算子引入到基本SCA中，采用二進制方式編碼、對不可行解修復(fù)的GTA和RCSA、群智能算法通用的貪婪選擇，以優(yōu)勢互補策略，提出了一種求解0-1 KP的改進正弦余弦算法(I-SCA).首先，I-SCA能有效提高SCA的搜索效率，同時能克服其陷入局部最優(yōu)的缺陷；其次，求解0-1 KP的仿真實驗表明，相比基本SCA，I-SCA的收斂速度和求解精度均有所改進，并且I-SCA與其它算法的求解效果相當，故I-SCA可以求解0-1 KP；最后，下一步的工作將是研究如何完善I-SCA，并使其能更好地應(yīng)用于大規(guī)模多維KP、折扣KP以及其它領(lǐng)域的組合優(yōu)化問題.