一種改進(jìn)的沙丘貓優(yōu)化算法求解裝箱問題

段敏 代永強(qiáng) 劉歡

摘? 要： 針對沙丘貓優(yōu)化算法容易陷入局部最優(yōu)的問題，提出一種改進(jìn)的沙丘貓優(yōu)化算法。首先通過帳篷混沌為映射模式來增強(qiáng)沙丘貓群體的多樣性；然后采用非線性遞減模型控制參數(shù)，降低了沙丘貓個(gè)體的敏感度；為增強(qiáng)沙丘貓的移動能力，引入了高斯隨機(jī)游走策略，使算法有更強(qiáng)大的全局探索能力。將沙丘貓優(yōu)化改進(jìn)算法和其他比較算法用于裝箱問題求解，結(jié)果表明，沙丘貓優(yōu)化改進(jìn)算法在所有算法中代價(jià)最小，收斂速度最快。

關(guān)鍵詞： 裝箱問題； 沙丘貓優(yōu)化算法； Tent映射； 高斯隨機(jī)游走策略

中圖分類號：TP3? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ? ?文章編號：1006-8228（2023）06-60-05

Improved Sand Cat Swarm Optimization to solve the bin-packing problem

Duan Min， Dai Yongqiang， Liu Huan

（College of Information Science & Technology， Gansu Agricultural University， Lanzhou， Ganshu 730070， China）

Abstract： An improved SCSO is proposed for the problem that SCSO is easy to fall into local optimum. Firstly， the diversity of the Sand Cat Swarm is enhanced by Tent chaos as a mapping model. Then， a nonlinear decreasing model is used to control the parameters， which reduces the sensitivity of individual Sand Cat. Finally， a Gaussian random wandering strategy is introduced to enhance the mobility of Sand Cats， which gives the algorithm a more powerful global exploration capability. The improved SCSO and other comparative algorithms are used to solve the bin-packing problem， and the experimental results show that the improved SCSO has the lowest cost and the fastest convergence speed among all algorithms.

Key words： bin-packing problem; Sand Cat Swarm Optimization （SCSO）; Tent mapping; Gaussian randomized wandering strategy

0 引言

1831年Gauss關(guān)注到裝箱問題（Bing Packing Problem，BPP）的近似算法，開始研究布局問題。上世紀(jì)八十年代后期，張國川和越民義開始研究最為經(jīng)典的FFD算法[1]，1991年通過權(quán)函數(shù)的改良和精準(zhǔn)分析將FFD算法近似界的尾項(xiàng)從3降到1并大大縮減了證明的篇幅[8]，自此行業(yè)內(nèi)掀起了組合優(yōu)化問題的廣泛討論[2-5]。裝箱問題是計(jì)算科學(xué)領(lǐng)域中一個(gè)非常重要的概念，它見于日常生活中，在現(xiàn)代工業(yè)上也被廣泛地應(yīng)用，如服裝行業(yè)的面料剪裁、快遞行業(yè)的集裝箱貨物裝載、現(xiàn)實(shí)生活中的物品包裝以及印刷行業(yè)的排樣等。同樣在計(jì)算機(jī)科學(xué)中裝箱問題也發(fā)揮了一定的作用，如文件分配、資源分配、任務(wù)調(diào)度等底層操作，甚至還應(yīng)用于一些智力游戲中。

自從裝箱問題問世以來，不少學(xué)者就展開了對這一問題的研究，從現(xiàn)有的研究成果來看，解決裝箱問題的算法有兩種，即精確算法與啟發(fā)式算法。精確算法有分支界定法、動態(tài)規(guī)劃法、線性規(guī)劃法等；啟發(fā)式算法有禁忌搜索、遺傳算法、模擬退火、螢火蟲算法等。以上算法在解決裝箱問題時(shí)取得了一定的成果，但同時(shí)也顯現(xiàn)出易早熟、后期收斂速度慢等不足。

2022年，土耳其學(xué)者Amir Seyyedabbasi和Farzad Kiani提出了沙丘貓優(yōu)化算法（Sand Cat Swarm Optimization，SCSO），該算法是一種模擬

沙丘貓群沙漠生存行為的元啟發(fā)式算法[6]。該算法具有參數(shù)少、收斂性和魯棒性較好等特點(diǎn)。但由于該算法提出時(shí)間較晚，現(xiàn)在正處于該算法的研究初期階段。目前關(guān)于SCSO的研究較少，且鮮有利用改進(jìn)的SCSO算法求解離散優(yōu)化問題。

針對沙丘貓優(yōu)化算法收斂精度低、易陷入局部最優(yōu)等問題，本文提出了一種改進(jìn)的沙丘貓優(yōu)化算法（ISCSO）并用該算法求解組合優(yōu)化中一維裝箱問題，以此驗(yàn)證該算法的可行性。

1 數(shù)學(xué)模型的建立

1.1 裝箱問題數(shù)學(xué)模型

有m個(gè)待裝貨物和n個(gè)集裝箱，在保證使用集裝箱最少的情況下，將m個(gè)貨物裝入n個(gè)集裝箱，同時(shí)考慮箱體（或容積）限制等限制條件。在建立模型之前，我們首先給出符號說明：ki為物品i的體積；W為任意一個(gè)集裝箱的容積；N為集裝箱集合，N={1，2，…，n}；為集裝箱d中已裝箱物品集合。具體數(shù)學(xué)模型如下：

[minf=d∈Nψd]? ? ⑴

[ψd∈0，1; ?d∈N]? ?⑵

[κi，d∈0，1;?d∈N，?i=1，2，…，m]? ⑶

[i=1mwi×κi，d≤W;?d∈N]? ⑷

[i=1mκi，d=1; ?d∈N]? ? ⑸

[d∈Nκi，d=1;?i=1，2，???，m]? ? ⑹

其中，式⑴為目標(biāo)函數(shù)，表示使用的集裝箱數(shù)量最少。式⑵中為0-1變量，表示集裝箱d是否被使用，集裝箱d被使用為1，反之為0；式⑶中為0-1變量，表示物品i是否會裝入集裝箱d中，如果物品i會被裝入集裝箱d，為1，反之為0。式⑷為集裝箱的最大容積約束，保證了裝入集裝箱d的所有物品的體積之和小于集裝箱的容積。式⑸、⑹則保證了任何一件物品均被裝入集裝箱中，且同一物品不會被裝入兩個(gè)集裝箱。式⑺限制了下一個(gè)裝箱到集裝箱d的物體體積不能大于集裝箱d剩余部分的容積。

1.2 裝箱問題的實(shí)際約束

在實(shí)際裝載過程中，物品尺寸、體積、形狀、數(shù)量以及集裝箱的規(guī)格等可能是不同的，這在一定程度上增加了集裝箱裝載的復(fù)雜性。針對以上對集裝箱裝載問題分類以及復(fù)雜性的討論，我們將集裝箱裝載常用的約束條件和一維裝箱問題的變體做如下說明[7]。

⑴ 完整性約束

物品是一個(gè)完整的不可再次切割的物體。即同一物體不允許裝在不同的集裝箱中，具體如式⑸所示。

⑵ 體積約束

貨物在裝載過程中，其集裝箱的可用體積不?？s小，貨物的體積小于等于集裝箱的可用體積，貨物才可以裝入集裝箱。具體如式⑺所示。

⑶ 擴(kuò)展模型

由于在現(xiàn)實(shí)生活中，集裝箱的規(guī)格和費(fèi)用可能并不相同，如冷藏式集裝箱和普通集裝箱等，因此，在計(jì)算目標(biāo)函數(shù)時(shí)需要使集裝箱的費(fèi)用最低，具體如下：

[minf=d∈Nψd+d∈NPd×ψd]? ⑺

其中，[ψd]為集裝箱d的費(fèi)用。

2 沙丘貓優(yōu)化算法（SCSO）

在d維優(yōu)化問題中，每個(gè)沙貓都是一個(gè)1?d陣列，每個(gè)變量值（x1，x2，…，xd）都是浮點(diǎn)型，且每個(gè)x都必須處于上下邊界之間，算法運(yùn)行時(shí)首先根據(jù)問題的規(guī)模，利用沙丘貓群來創(chuàng)建一個(gè)候選矩陣。此外，每次迭代都會輸出相應(yīng)的解。若接下來的解更好，則替換當(dāng)前解決方案。若后續(xù)的迭代沒有找到更好的解，則不存儲本次迭代的解。

在搜索獵物的過程中，假設(shè)沙丘貓的聽力靈敏范圍2kHz，沙丘貓常規(guī)靈敏范圍將隨著迭代過程從2線性的降為0。每只沙丘貓會根據(jù)最優(yōu)解、自己當(dāng)前的位置和[r]來更新自己位置。位置更新公式如下：

[pos（t+1）=r×（posbc（t）- rand（0，1）×posc（t））] ⑻

其中，[posbc]為最佳候選位置，[posc]為當(dāng)前位置，[posb]為最佳位置之間的距離，最優(yōu)位置與當(dāng)前位置可根據(jù)式⑼和式⑽計(jì)算。

[posrnd=rand（0，1）×posb（t）-posc（t）]? ⑼

[post+1=posbt-r×posrnd×cos（θ）]? ⑽

搜索和攻擊階段根據(jù)自適應(yīng)的R和[rg]來保證，當(dāng)[R≤1]時(shí)，SCSO算法強(qiáng)制搜索Agent進(jìn)行探索，否則，搜索Agent進(jìn)行探索并尋找獵物。

[Xt+1=Posbt-Posrnd×cosθ×r |R|≤1;r×Posbc（t）-rand（0，1）×Posc（t）R>1;] ⑾

3 沙丘貓優(yōu)化改進(jìn)算法（ISCSO）

3.1 Tent映射策略

SCSO算法在初始化的過程中，同絕大多數(shù)元啟發(fā)示算法類似，通過基礎(chǔ)語言包隨機(jī)產(chǎn)生的數(shù)據(jù)作為種群信息，在這種情況下算法很難保證群體的多元化。在算法優(yōu)化過程中，初始化物種分布在搜索空間內(nèi)越均勻，越能有效提高算法的尋優(yōu)結(jié)果[9]?；谝陨辖Y(jié)論，本文借助Tent映射模型進(jìn)行種群初始化。Tent映射模型如下：

[xn+1=21-xn12≤xn≤12xn? ? 0≤xn<12]? ⑿

3.2 非線性遞減策略

在SCSO中，沙丘貓的常規(guī)靈敏度范圍[rg]不僅控制著搜索和攻擊的轉(zhuǎn)換，同時(shí)也決定了每只沙丘貓的靈敏度范圍。研究發(fā)現(xiàn)，沙丘貓的敏感度與算法尋優(yōu)能力相關(guān)，因此，為了提升沙丘貓優(yōu)化算法跳出局部極值的能力，本文引入了非線性指數(shù)遞減策略，從而改變沙丘貓靈敏度。詳見式⒀、式⒁。

[rg=S-S×tctmax+δ]? ⒀

[δ=rand×cosrand0，1×2π*tctmax×sinrand×2π*tctmax-1] ⒁

3.3 高斯隨機(jī)游走策略

高斯隨機(jī)游走模型是隨機(jī)游走模型中較為典型的一種，具有較強(qiáng)的開發(fā)能力。在ISCSO的搜索階段引入高斯隨機(jī)游走策略，以擾動種群的最優(yōu)個(gè)體[10]。通過此方法，提高了算法的收斂速度，從而使算法能跳出局部最優(yōu)，彌補(bǔ)算法的早熟缺陷。ISCSO其位置更新策略詳見式⒂、式⒃。

[pos（t+1）new=Gaussianposbct，κ+r×（posbc（t）-rand（0，1）×posc（t））] ⒂

[κ=cos（π2×tcπ2）×pos（t）-posbct]? ⒃

3.4 改進(jìn)算法偽代碼

（a） 根據(jù)式⑿初始化種群

（b） 根據(jù)目標(biāo)函數(shù)計(jì)算適應(yīng)度函數(shù)

（c） 初始化r，rg，R

（d） WHILE（t<=max）

（e） ? ?FOR i in search agent

（f） 根據(jù)輪盤賭獲取隨機(jī)角度（0°≤[θ]≤ 360°）

（g） ? ? ? ?IF（ABS（R）<=1）

（h） 根據(jù)式⑼、式⑽獲取更新代理的位置

（i） ? ? ? ?ELSE

（j） 根據(jù)式⑿獲取更新代理的位置

（k） 用高斯隨機(jī)游走策略（式⒂、式⒃）來獲取新位置

（l） ? ? ? ?END IF

（m） ? ?END FOR

（n） ? ?t++

（o） END WHILE

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

4.1 實(shí)驗(yàn)環(huán)境

仿真實(shí)驗(yàn)在64bitWindows11操作系統(tǒng)、Intel（R） Core（TM） i9-12900H 2.50 GHz處理器、16G內(nèi)存的計(jì)算機(jī)上進(jìn)行，算法采用軟件MATLABR2021a編譯實(shí)現(xiàn)。

4.2 算法模擬參數(shù)

本文為了評估ISCSO算法與其他優(yōu)化算法的性能，采用測試函數(shù)與求解一維裝箱的尋優(yōu)性能兩個(gè)方面進(jìn)行對比。測試函數(shù)測試時(shí)算法維度D=30，群體規(guī)模N=30，迭代次數(shù)T=500。對比算法參數(shù)選自國外學(xué)者Amir Seyyedabbas的沙丘貓優(yōu)化算法。

4.3 測試函數(shù)結(jié)果分析與對比

為了比較和分析ISCSO算法與另外三種算法（SCSO、PSO、GWO）的尋優(yōu)性能，選取CEC2014、CEC2015共12個(gè)經(jīng)典測試函數(shù)來驗(yàn)證所提出的優(yōu)化算法的性能，其中F1～F7為單峰函數(shù)，F(xiàn)8～F12為雙峰函數(shù)。函數(shù)表達(dá)式詳見Amir Seyyedabbas學(xué)者的沙丘貓優(yōu)化算法，其他參數(shù)如表1所示。

通過表2可知，在30次單獨(dú)運(yùn)行時(shí)，ISCSO算法在限定的函數(shù)評定次數(shù)內(nèi)，較其他三種算法有更好的收斂性，F(xiàn)1～F5、F7的優(yōu)化精度最高，其中F1函數(shù)精度最為明顯。在 F5函數(shù)下SCSO、GSO和ISCSO算法收斂速度均有較大提高，但I(xiàn)SCSO算法收斂速度最快；針對F6函數(shù)的平均差，PSO算法具有最優(yōu)的收斂性能。

同時(shí)通過表3可見 ISCSO對于五種雙峰函數(shù)的優(yōu)化結(jié)果，針對F8～F11函數(shù)，融合于高斯隨機(jī)游走策略和非線性遞減策略，ISCSO算法快速跳出局部最優(yōu)，收斂于全局最佳，且在 F9、F11上尋找到了最佳值；對于F10函數(shù)而言，雖然兩類算法都在尋找全局最佳，但I(xiàn)SCSO標(biāo)準(zhǔn)差略勝于SCSO算法。綜上所述，ISCSO算法的收斂速度和收斂精度都有明顯的提升。

4.4 基于ISCSO算法的裝箱問題性能分析

在本節(jié)展示了ISCSO算法、FA算法、PSO算法、IWO算法以及GA算法在裝箱問題中的應(yīng)用。其中物品集的體積為{6，3，4，6，8，7，4，7，7，5，5，6，7，7，6，4，8，7，8，8，2，3，4，5，6，8，5，7，7，12}，箱子體積為30，最佳值為7。進(jìn)一步的，我們將五種算法各運(yùn)行30次，圖1、圖2以及圖3分別展示了五種算法運(yùn)行30次的過程中目標(biāo)函數(shù)的最優(yōu)值、平均值以及最差值。

從圖1可以看出，當(dāng)五種算法在30次運(yùn)行最佳適應(yīng)度函數(shù)最佳值時(shí)，ISCSO算法的最佳迭代次數(shù)是最少的，僅在第8次迭代便獲得了最佳值，與 FA、 GA、PSO和IWO算法相比分別快25%、25%、100%以及3250%。

從圖2得出，當(dāng)五種算法在30次運(yùn)行平均適應(yīng)度函數(shù)最佳值時(shí)，ISCSO算法在第154次迭代便取得了最佳值，分別比FA、GA、PSO和IWO算法快127.27%、20.78%、47.40%以及127.27%。

從圖3可見，在五種算法的適應(yīng)度函數(shù)最差的情況下，ISCSO算法的最佳值出現(xiàn)在迭代次數(shù)472次內(nèi)，其余算法在500次循環(huán)中均未能找到相應(yīng)的解。從而得到一個(gè)結(jié)論，無論在適應(yīng)函數(shù)最優(yōu)值、最差值還是平均值的情況下，ISCSO算法的求解效果均是最優(yōu)異的。

5 結(jié)論

本文針對裝箱問題，融合混沌映射、非線性遞減系數(shù)和高斯隨機(jī)游走等機(jī)制，提出了一種改進(jìn)的沙丘貓優(yōu)化算法（ISCSO）。CEC仿真實(shí)驗(yàn)結(jié)果表明，ISCSO算法相比較SCSO、PSO、GWO等算法，表現(xiàn)出較好的結(jié)果，ISCSO算法在求解裝箱問題時(shí)相比較PSO、GWO、IWO、GA等算法，具有較好的尋優(yōu)性和求解精度。在進(jìn)一步研究過程中，將對一維裝箱問題擴(kuò)展至三維裝箱問題，同時(shí)考慮物流、海運(yùn)等實(shí)際場景中的約束條件，構(gòu)建相應(yīng)的數(shù)學(xué)模型，并提出對應(yīng)的改進(jìn)策略應(yīng)用ISCSO算法的框架求解多約束的三維裝箱問題。

參考文獻(xiàn)（References）：

[1] 張國川，越民義.TIGHT PERFORMANCE BOUND OF

AFBK BIN PACKING[J].Acta Mathematicae Applicatae Sinica（English Series），1997（4）：321-331

[2] Hao X， Zheng L， Li N， et al. Integrated bin packing and lot-

sizing problem considering the configuration-dependent bin packing process[J]. European Journal of Operational Research，2022，303

[3] Dell' AmicoM， Furini F， Iori M. A branch-and-price

algorithm for the temporal bin packing problem[J]. Computers & operations research，2020，114（Feb.）：104825.1-104825.16

[4] Martinez-SykoraA， Alvarez-Valdes R， Bennell J， et al.

Matheuristics for the irregular bin packing problem with free rotations[J]. European Journal of Operational Research，2017：S0377221716307950

[5] Lw D， Ml B， Al C， et al. A branch-and-price algorithm for

the two-dimensional vector packing problem[J]. European Journal of Operational Research，2020，281（1）：25-35

[6] Seyyedabbasi A， Kiani F. Sand Cat swarm optimization： a

nature-inspired algorithm to solve global optimization problems. EngComput 2022. https：//doi.org/10.1007/s00366-022-01604-x.

[7] 張鈞，賀可太.求解三維裝箱問題的混合遺傳模擬退火算法[J].

計(jì)算機(jī)工程與應(yīng)用，2019，55（14）：32-39，47

[8] 陳婳，張國川.經(jīng)典一維裝箱問題近似算法的研究進(jìn)展[J].

運(yùn)籌學(xué)學(xué)報(bào)，2022，26（1）：69-84

[9] Sneha P S，SankarS，Kumar A S.A chaotic colour image

encryption scheme combining Walsh-Hadamard transform and Arnold-Tent maps[J]. Journal of ambient intelligence and humanized computing，2020，11（3）：1289-1308

[10] Sun C J， Gao F. A Tent Marine Predators Algorithm

with Estimation Distribution Algorithm and Gaussian Random Walk for Continuous Optimization Problems[J]. Computational intelligence and neuroscience，2021（Pt.14）：2021