一種改進(jìn)的正弦余弦算法求解0-1背包問題

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

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

背包問題(knapsack problem，KP)[1]是20世紀(jì)50年代末期由Dantzing首次提出.它既是計(jì)算機(jī)科學(xué)領(lǐng)域中的經(jīng)典NP-complete問題，也是組合優(yōu)化問題之一.截止目前，背包問題的理論價(jià)值和應(yīng)用價(jià)值已在整數(shù)規(guī)劃、資源配置、項(xiàng)目選擇、貨物裝載和決策投資等諸多領(lǐng)域應(yīng)用中得到了很好地體現(xiàn).傳統(tǒng)求解0-1背包問題(0-1 Knapsack Problem，0-1KP)的方法有回溯法、動態(tài)規(guī)劃法和分支界定法等，這類方法往往存在某種難以克服的缺陷，如隨著問題規(guī)模的增大會導(dǎo)致算法的運(yùn)行時(shí)間明顯變長.近年來興起的群體智能優(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é)同工作機(jī)理為核心的其它元啟發(fā)式智能優(yōu)化算法，SCA是一種獨(dú)有的群體智能優(yōu)化算法，它的顯著特點(diǎn)是利用三角函數(shù)Sine和Cosine模型的周期震蕩性特征實(shí)現(xiàn)算法的搜索尋優(yōu).與其它智能優(yōu)化算法一樣，SCA在迭代后期仍易出現(xiàn)一系列問題，如收斂速度慢、求解精度低和局部開發(fā)能力差.

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

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

1 背景知識

1.1 正弦余弦算法

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

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

(1)

(2)

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

1.2 人工蜂群算法

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

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

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

(3)

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

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

(4)

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

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

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

1.3 0-1背包問題

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

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

(5)

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

2 貪心改進(jìn)正弦余弦算法求解0-1背包問題

2.1 改進(jìn)策略

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

(6)

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

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

(7)

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

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

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

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

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

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

(8)

基本SCA的時(shí)間復(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ù)解以一定的編碼方式進(jìn)行編碼，并使其轉(zhuǎn)化為離散解.

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

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

(10)

式中：sig(xi)是一個(gè)將實(shí)向量映射為二進(jìn)制向量的sigmoid函數(shù)，其表達(dá)式為：

(11)

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

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

2)記錄當(dāng)前背包序列中所存放物品的臨時(shí)重量Tempwi；

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

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

2.3.3 修正連續(xù)解算法(RCSA) 為使算法在下次迭代時(shí)能從正確的實(shí)向量開始進(jìn)化，故根據(jù)修正后的編碼個(gè)體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 仿真試驗(yàn)與分析

3.1 試驗(yàn)環(huán)境

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

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

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

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

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

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

根據(jù)表2，從2種算法取得的平均最優(yōu)值來看，除了背包問題f9，2種算法均能取得理論最優(yōu)值外，相比基本SCA，在其它9個(gè)0-1 KP上，I-SCA的收斂速度和求解精度顯著提高，并最終收斂到各自的理論最優(yōu)值；從2種算法取得的標(biāo)準(zhǔn)差來看，相比基本SCA，I-SCA在背包問題f5上取得的標(biāo)準(zhǔn)差雖未能達(dá)到最小值，但數(shù)量級也顯著提高，同時(shí)在其它0-1 KP上的標(biāo)準(zhǔn)差均為0，魯棒性強(qiáng)；從2種算法取得的最優(yōu)值和最差值來看，相比基本SCA，在10個(gè)0-1 KP中I-SCA獲得的可行解質(zhì)量均相對較高；從兩種算法取得的成功率來看，相比基本SCA，I-SCA在10個(gè)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

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

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

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

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

為進(jìn)一步測試I-SCA的性能，將其與求解0-1背包問題的其它元啟發(fā)式算法進(jìn)行比較.為體現(xiàn)比較的公平性，將I-SCA的參數(shù)設(shè)置與文獻(xiàn)[21]相同，即N=30，T=1 000，R=50.其余算法的試驗(yàn)數(shù)據(jù)來自文獻(xiàn)，表3列出了I-SCA與其它元啟發(fā)式算法求解0-1 KP的試驗(yàn)結(jié)果，評價(jià)指標(biāo)包括平均最優(yōu)值(Ave)、標(biāo)準(zhǔn)差(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在標(biāo)準(zhǔn)差方面稍遜于對比算法外，算法取得的平均最優(yōu)值、最大值和最小值上已達(dá)到了理論最優(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個(gè)經(jīng)典低維0-1 KP上的求解效果基本上是理想的，表現(xiàn)出了優(yōu)良的優(yōu)化性能.

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

4 結(jié)論

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