段敏 代永強 劉歡

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

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

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

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

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

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

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

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

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

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

[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]? ? ⑹

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

1.2 裝箱問題的實際約束

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

⑴ 完整性約束

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

⑵ 體積約束

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

⑶ 擴展模型

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

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

其中，[ψd]為集裝箱d的費用。

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

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

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

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

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

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

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

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

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

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

3.1 Tent映射策略

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

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

3.2 非線性遞減策略

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

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

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

3.3 高斯隨機游走策略

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

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

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

3.4 改進算法偽代碼

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

（b） 根據(jù)目標函數(shù)計算適應度函數(shù)

（c） 初始化r，rg，R

（d） WHILE（t<=max）

（e） ? ?FOR i in search agent

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

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

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

（i） ? ? ? ?ELSE

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

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

（l） ? ? ? ?END IF

（m） ? ?END FOR

（n） ? ?t++

（o） END WHILE

4 仿真實驗

4.1 實驗環(huán)境

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

4.2 算法模擬參數(shù)

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

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

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

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

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

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

在本節(jié)展示了ISCSO算法、FA算法、PSO算法、IWO算法以及GA算法在裝箱問題中的應用。其中物品集的體積為{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。進一步的，我們將五種算法各運行30次，圖1、圖2以及圖3分別展示了五種算法運行30次的過程中目標函數(shù)的最優(yōu)值、平均值以及最差值。

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

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

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

5 結論

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

參考文獻（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].

計算機工程與應用，2019，55（14）：32-39，47

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

運籌學學報，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