一種改進的正弦余弦算法求解0-1背包問題

劉小娟，封成智，王聯國

(甘肅農業大學信息科學技術學院，甘肅 蘭州 730070)

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

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

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

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

1 背景知識

1.1 正弦余弦算法

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

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

(1)

(2)

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

1.2 人工蜂群算法

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

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

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

(3)

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

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

(4)

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

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

(4)偵察蜂階段。偵察蜂搜尋蜂巢周圍潛在的蜜源。當連續停留次數n到一定的閾值L仍未找到更優空間位置時，即表明陷入了局部最優，此時蜜蜂的角色由采蜜蜂或觀察蜂轉變為偵察蜂，并按照公式(3)重新搜索隨機產生新蜜源.

1.3 0-1背包問題

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

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

(5)

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

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

2.1 改進策略

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

(6)

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

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

(7)

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

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

2.2 I-SCA的時間復雜度分析

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

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

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

(8)

基本SCA的時間復雜度為：

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

(9)

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

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

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

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

(10)

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

(11)

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

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

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

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

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

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

1)j=1；

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

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

3 仿真試驗與分析

3.1 試驗環境

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

3.2 背包問題及參數設置

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

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

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

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

表1 10個經典背包問題的目標精度

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結論

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