摘 要：

針對(duì)目前算法求解多維背包時(shí)精度低、穩(wěn)定性差、特別是無法有效求解超大規(guī)模算例等問題，提出一種新型人類學(xué)習(xí)優(yōu)化算法。首先，基于認(rèn)知心理學(xué)中的記憶理論，在基本人類學(xué)習(xí)算法中采用哈希函數(shù)表示人類在學(xué)習(xí)過程中的記憶行為，避免重復(fù)搜索，提高算法搜索群體多樣性；其次，采用認(rèn)知心理學(xué)中的對(duì)比認(rèn)知理論對(duì)學(xué)習(xí)算子選擇策略進(jìn)行自適應(yīng)調(diào)整；最后，采用變鄰域搜索操作提升算法局部搜索能力。采用小規(guī)模、中等規(guī)模、大規(guī)模、超大規(guī)模共76個(gè)多維背包問題的標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集進(jìn)行數(shù)值實(shí)驗(yàn)，并將新算法和二進(jìn)制粒子群算法、遺傳算法、人類學(xué)習(xí)算法以及融合學(xué)習(xí)心理學(xué)的人類學(xué)習(xí)算法進(jìn)行比較。結(jié)果表明新算法能夠有效求解四種規(guī)模算例。與其他算法相比，新算法具有更高的尋優(yōu)精度和更好的穩(wěn)定性。此外，對(duì)提出的三種優(yōu)化策略進(jìn)行分析，測(cè)試其對(duì)提高算法搜索性能的有效性。

關(guān)鍵詞：人類學(xué)習(xí)優(yōu)化算法；認(rèn)知心理學(xué)；哈希函數(shù)；學(xué)習(xí)算子選擇策略；多維背包問題

中圖分類號(hào)：TP301.6"" 文獻(xiàn)標(biāo)志碼：A""" 文章編號(hào)：1001-3695（2024）12-022-3689-12

doi： 10.19734/j.issn.1001-3695.2024.04.0127

Novel human learning optimization algorithm for

multidimensional knapsack problem

Zhang Yipeng， Liu Yong， Ma Liang

（Management School， University of Shanghai for Science amp; Technology， Shanghai 200093， China）

Abstract：

Aiming at the problems of low accuracy and poor stability of the current algorithms in solving multi-dimensional knapsacks， especially the inability to effectively solve super-large-scale arithmetic cases， this paper proposed a new type of human learning optimization algorithm. Firstly， the noval human learning algorithm used a hash function based on the memory theory in cognitive psychology to represent the memory behaviour of human beings in the learning process， avoiding repeated searches and improving the algorithm’s search group diversity. Secondly， the algorithm used the contrastive cognition theory from cognitive psychology to adaptively adjust the learning operator selection strategy. Finally， the algorithm used a variable neighborhood search operation to enhance the algorithm’s local search capability. This paper conducted numerical experiments using a standardized test dataset of a total of 76 multidimensional knapsack problems that covered small， medium， large， and very large scales. Experiments compared the new algorithm with binary particle swarm algorithms， genetic algorithms， human learning algorithms， and human learning algorithms that incorporated the psychology of learning. The results show that the new algorithm is able to solve the four scale instances efficiently. Compared with other algorithms， the new algorithm has higher accuracy in finding the optimum and better stability. In addition， this paper analyzed three proposed optimization strategies to test their effectiveness in improving the algorithm’s search performance.

Key words：human learning optimization algorithm; cognitive psychology; hash function; learning operator selection strategy; multidimensional knapsack problem

0 引言

多維背包問題（multidimensional knapsack problem，MKP）是一類經(jīng)典的非確定性多項(xiàng)式（nondeterministic polynomial， NP）問題。自1955年Lorie等人［1］首次提出MKP模型以來，該模型在資本預(yù)算與項(xiàng)目選擇［1，2］、切割庫存［3］、集裝箱裝載［1］、分布式計(jì)算中資源的分配［5］和約束批準(zhǔn)投票［6］等問題上有著廣泛的應(yīng)用。作為經(jīng)典0-1背包問題的變體，多維背包問題有著更嚴(yán)格的約束條件，模型更加復(fù)雜且求解難度更高［7］。在目前的研究中，MKP所應(yīng)用于的現(xiàn)實(shí)問題規(guī)模逐漸增大，問題的計(jì)算量呈指數(shù)級(jí)增長，計(jì)算復(fù)雜度也隨之增加。模型維度高、約束強(qiáng)的特點(diǎn)與實(shí)際問題規(guī)模的擴(kuò)大使得MKP問題存在較大的求解難度。目前對(duì)多維背包問題的求解方法可以分為精確算法與智能優(yōu)化算法。在對(duì)精確算法的研究中，文獻(xiàn)［8］首次將分支定界算法引入MKP問題；文獻(xiàn)［9］對(duì)分支定界算法改進(jìn)并應(yīng)用于更大規(guī)模MKP問題中；文獻(xiàn)［10］首次將動(dòng)態(tài)規(guī)劃算法應(yīng)用于MKP問題，通過構(gòu)造子狀態(tài)、遞推關(guān)系式對(duì)問題進(jìn)行求解，精確算法雖能求得MKP問題的最優(yōu)解，但無法應(yīng)用于大規(guī)模問題。智能優(yōu)化算法旨在找到問題的滿意解，目前求解MKP問題效果較好的有蟻群算法［11］、二進(jìn)制粒子群算法［12］、遺傳算法［13］等。與精確算法相比，雖然智能優(yōu)化算法能求解更大規(guī)模問題，但對(duì)于如規(guī)模大于100、維度超過10的問題應(yīng)用較少，求解精度與穩(wěn)定性仍需提高。綜上所述，由于MKP問題嚴(yán)格的多維約束條件與現(xiàn)實(shí)規(guī)模問題的增大導(dǎo)致問題難以求解，目前仍需設(shè)計(jì)能有效求解MKP問題的算法。

人類學(xué)習(xí)算法（human learning optimization，HLO）由Wang等人［14］于2014年提出，通過模擬人類的學(xué)習(xí)過程對(duì)問題進(jìn)行求解。算法通過設(shè)計(jì)學(xué)習(xí)算子、個(gè)體學(xué)習(xí)算子和社會(huì)學(xué)習(xí)算子三種學(xué)習(xí)算子不斷提高個(gè)體的學(xué)習(xí)能力進(jìn)行迭代尋優(yōu)。HLO由于其具有易于實(shí)現(xiàn)、尋優(yōu)能力強(qiáng)的特點(diǎn)，已經(jīng)成功用于調(diào)度問題［15］、選址問題［16］、供應(yīng)鏈網(wǎng)絡(luò)設(shè)計(jì)［17］、自動(dòng)文本摘要［18］、爐膛燃燒火焰的精確快速識(shí)別［19］等。這表明HLO有著良好的優(yōu)化性能與潛力。目前對(duì)HLO求解MKP問題的研究處于起步階段。Wang等人［20］首次將HLO應(yīng)用于MKP問題中，通過增加再學(xué)習(xí)算子對(duì)算例進(jìn)行求解。文獻(xiàn)［21］結(jié)合學(xué)習(xí)心理學(xué)對(duì)算法進(jìn)行改進(jìn)，并與遺傳算法等方法在求解MKP問題上進(jìn)行對(duì)比，結(jié)果表明改進(jìn)算法具有更好的性能。但上述人類學(xué)習(xí)優(yōu)化算法僅能對(duì)部分規(guī)模MKP算例有效求解，并且算法穩(wěn)定性與精度仍有待提高。此外，算法所求解的MKP問題規(guī)模均不超過10個(gè)約束、100個(gè)物品；特別對(duì)于20個(gè)約束、200個(gè)物品以及50個(gè)約束、500個(gè)物品等超大規(guī)模算例無法求解。

因此，本文針對(duì)以上存在的問題，結(jié)合認(rèn)知心理學(xué)提出一種新型人類學(xué)習(xí)算法（novel human learning optimization，NHLO）。在學(xué)習(xí)過程中人腦會(huì)對(duì)所學(xué)知識(shí)進(jìn)行記憶，本文通過哈希表與哈希函數(shù)模擬了人類在學(xué)習(xí)過程中的記憶行為，減少重復(fù)搜索，提高搜索群體的多樣性。本文結(jié)合對(duì)比認(rèn)知理論對(duì)算法中學(xué)習(xí)算子的選擇策略進(jìn)行改進(jìn)，使得算法擁有動(dòng)態(tài)調(diào)整算子選擇的能力，提高算法的尋優(yōu)效率。此外，將算法與變鄰域搜索操作相結(jié)合，增強(qiáng)算法跳出局部最優(yōu)與尋優(yōu)能力。最后將本文算法應(yīng)用于四種不同規(guī)模的多維背包問題，驗(yàn)證了所提出三種策略的有效性與新型算法的性能。

1 多維背包問題

多維背包問題的數(shù)學(xué)模型可定義為

max z=∑Mi=1cixi（1）

s.t. ∑Mi=1kijxi≤bj" "j=1，2，…，J（2）

xi∈{0，1}" i=1，2，…，M（3）

其中：J、M分別表示背包中的資源與物品數(shù)量；ci表示第i個(gè)物品的價(jià)值；kij表示第i個(gè)物品對(duì)資源j的消耗量；bj為該資源的總量；xi表示決策變量，xi=1表示選擇該物品放入背包，xi=0表示不選擇該物品放入背包。多維背包問題的目標(biāo)則是在滿足約束情況下選擇若干物品，使得放入背包物品的總價(jià)值最大。

與0-1背包問題相比，模型的約束條件增加，求解難度更大，屬于NP-難問題［22］。

2 基本人類學(xué)習(xí)算法

基本人類學(xué)習(xí)算法HLO主要包括群體初始化、學(xué)習(xí)算子和知識(shí)庫更新三個(gè)部分。

2.1 群體初始化

人類學(xué)習(xí)優(yōu)化算法通過二進(jìn)制編碼對(duì)解進(jìn)行表示，具體表示方式為

x={xij，i=1，2，…，N; j=1，2，…，M;xij∈{0，1}}（4）

其中：N表示群體規(guī)模；M表示解的維數(shù)；xij表示第i個(gè)個(gè)體的第j個(gè)分量。

2.2 學(xué)習(xí)算子

2.2.1 隨機(jī)學(xué)習(xí)算子

在初期學(xué)習(xí)過程中，存在隨機(jī)獲取知識(shí)的過階段，算法通過隨機(jī)學(xué)習(xí)算子模擬該學(xué)習(xí)過程，其數(shù)學(xué)表達(dá)式為

xij=0" 0≤randlt;0.51" else（5）

其中：rand表示一個(gè)［0，1］的隨機(jī)數(shù)。

2.2.2 個(gè)體學(xué)習(xí)算子

個(gè)體學(xué)習(xí)是學(xué)習(xí)過程中的普遍現(xiàn)象，其表現(xiàn)為個(gè)體根據(jù)自己以往經(jīng)驗(yàn)進(jìn)行學(xué)習(xí)。算法通過個(gè)體學(xué)習(xí)算子對(duì)其進(jìn)行模擬。人類學(xué)習(xí)優(yōu)化算法通過創(chuàng)建如式（6）（7）所示的個(gè)體知識(shí)庫（individual knowledge database， IKD）來存儲(chǔ)每個(gè)個(gè)體的歷史最好經(jīng)驗(yàn)，并通過式（8）進(jìn)行學(xué)習(xí)。

IKD=ikd1ikd2ikdiikdN 1≤i≤N（6）

ikdi=ikdi1ikdi2ikdipikdiL=iki11iki12…iki1j…iki1Miki21iki22…iki2j…iki2M ikip1ikip2…ikipj…ikipM ikiL1ikiL2…ikiLj…ikiLM 1≤p≤L

（7）

xij=ikdipj（8）

其中：ikdi表示第i個(gè)人的個(gè)體知識(shí)庫；ikdip表示該個(gè)體第p個(gè)個(gè)體最優(yōu)解；ikipj表示該個(gè)體最優(yōu)解的第j個(gè)分量；L表示個(gè)體知識(shí)庫規(guī)模。

2.2.3 社會(huì)學(xué)習(xí)算子

社會(huì)學(xué)習(xí)算子代表個(gè)體向種群中最優(yōu)個(gè)體進(jìn)行學(xué)習(xí)的過程。社會(huì)知識(shí)庫（social knowledge database， SKD）如式（9）所示。

SKD=skd1skd2skdqskdH=sk11sk12…sk1j…sk1Msk21sk22…sk2j…sk2M skq1skq2…skqj…skqM skH1skH2…skHj…skHM 1≤q≤H

（9）

其中：skdq表示整個(gè)種群中第q個(gè)最優(yōu)的歷史最優(yōu)解；skqj表示其第j個(gè)分量；H表示社會(huì)知識(shí)庫的規(guī)模。個(gè)體按照下式進(jìn)行學(xué)習(xí)：

xij=skdqj" 1≤q≤H（10）

人類學(xué)習(xí)算法通過以上三種算子對(duì)解空間搜索并不斷產(chǎn)生新解。三種算法的選擇策略如下：

uij=rand（0，1） 0≤rand≤prikipjprlt;rand≤piskqjelse（11）

其中：pr表示進(jìn)行隨機(jī)學(xué)習(xí)的概率；pi-pr為進(jìn)行個(gè)體學(xué)習(xí)的概率；1-pi為進(jìn)行社會(huì)學(xué)習(xí)的概率。

2.3 知識(shí)庫的更新

知識(shí)庫IKD、SKD的更新策略如下：當(dāng)每一代新生成解的適應(yīng)度值大于知識(shí)庫中對(duì)應(yīng)的最差解的適應(yīng)度值或者知識(shí)庫中解的數(shù)量小于對(duì)應(yīng)知識(shí)庫的規(guī)模時(shí)，則將新生成的解添加到對(duì)應(yīng)的知識(shí)庫中。

3 新型人類學(xué)習(xí)算法

基本人類學(xué)習(xí)算法存在著計(jì)算精度不高、算法穩(wěn)定性較差、優(yōu)化速度慢等問題。從人類學(xué)習(xí)的角度來分析，HLO算法對(duì)人類學(xué)習(xí)機(jī)制的描述較為簡單，忽略了在學(xué)習(xí)過程中心理因素會(huì)對(duì)學(xué)習(xí)效果產(chǎn)生的巨大影響。為提高算法中個(gè)體學(xué)習(xí)效果，本文結(jié)合認(rèn)知心理學(xué)對(duì)基本人類學(xué)習(xí)算法進(jìn)行了如下改進(jìn)：受到文獻(xiàn)［15］的啟發(fā)，通過加入小組學(xué)習(xí)算子提高算法性能；學(xué)習(xí)中的記憶行為，通過哈希表與哈希函數(shù)對(duì)解進(jìn)行記憶，避免了算法中解的重復(fù)搜索，提高種群多樣性；根據(jù)對(duì)比認(rèn)知理論，在選擇學(xué)習(xí)算子時(shí)將個(gè)體進(jìn)行比較，賦予算法動(dòng)態(tài)選擇算子的能力；最后將算法與變鄰域搜索算法結(jié)合，增強(qiáng)算法局部開發(fā)能力。

3.1 小組學(xué)習(xí)算子

在學(xué)習(xí)過程中，小組學(xué)習(xí)是一種常見學(xué)習(xí)方式，通過將群體分組，實(shí)現(xiàn)組內(nèi)各成員的小組學(xué)習(xí)。與個(gè)體學(xué)習(xí)類似，文獻(xiàn)［15］通過建立式（12）所示的小組知識(shí)庫（team knowledge database， TKD），進(jìn)行小組最佳經(jīng)驗(yàn)的存儲(chǔ)，并通過式（13）進(jìn)行學(xué)習(xí)。

TKD=tkd1tkd2tkdrtkdR=

tkd11tkd12…tkd1j…tkd1Mtkd21tkd22…tkd2j…tkd2M tkdr1tkdr2…tkdrj…tkdrM tkdR1tkdR2…tkdRj…tkdRM（12）

Xij=tkdrj" 1≤r≤R（13）

其中：R表示小組知識(shí)庫規(guī)模；tkdr表示該小組知識(shí)庫中的第r個(gè)解；tkdrj表示該解的第j個(gè)分量。

3.2 基于哈希函數(shù)的解的記憶機(jī)制

在人類學(xué)習(xí)算法中，通過對(duì)更新策略的分析可以發(fā)現(xiàn)，隨著算法的進(jìn)行，優(yōu)于知識(shí)庫中最差解的個(gè)體會(huì)不斷地加入其中，這導(dǎo)致IKD、TKD、SKD中個(gè)體會(huì)逐漸趨同，通過三個(gè)知識(shí)庫學(xué)習(xí)得到的種群多樣性也會(huì)受到影響，導(dǎo)致算法進(jìn)行大量的重復(fù)搜索與過早收斂，陷入局部最優(yōu)。在實(shí)際的學(xué)習(xí)過程中，大腦會(huì)對(duì)已經(jīng)學(xué)習(xí)過的知識(shí)或者已經(jīng)完成的目標(biāo)通過神經(jīng)元的電信號(hào)編碼成記憶。新型人類學(xué)習(xí)算法通過引入個(gè)體的記憶機(jī)制，在選中當(dāng)前最優(yōu)解的同時(shí)將該解記憶以限制該局部最優(yōu)解再次被選中，從而增加種群多樣性，防止算法重復(fù)搜索。

在認(rèn)知行為學(xué)中，記憶發(fā)揮著重要的作用。在認(rèn)知心理學(xué)中，記憶被定義為人腦對(duì)輸入信息進(jìn)行編碼、存儲(chǔ)與提取的過程。

本文通過哈希映射、哈希表賦值與訪問實(shí)現(xiàn)人腦對(duì)信息編碼、存儲(chǔ)與提取的模擬。

對(duì)于一個(gè)候選解M′∈Ω，可以通過哈希函數(shù)h單向映射為一個(gè)哈希值h（M′），即M′∈Ω→{0，1，2，…，l－1}。該哈希值h（M′）作為哈希表H的索引，可以將解的記憶情況存儲(chǔ)在哈希表H中，H［h（M′）］=1表示該解已經(jīng)訪問過，處于記憶狀態(tài)，H［h（M′）］=0則表示該解未被訪問過，可當(dāng)做當(dāng)前最優(yōu)解。

為減小發(fā)生哈希沖突的概率，本文引入了三個(gè)哈希函數(shù)hk（M）（k=1，2，3）與哈希表Hk（k=1，2，3），哈希函數(shù)如下：

hk（M）=（∑ni=1wk（i）×xi） mod l（14）

其中：wk（i）=wk（i－1）+βk+rand（βk/2），wk（0）=βk，βk（k=1，2，3）為不同的固定值；rand（βk/2）為屬于［0，βk/2］的隨機(jī)數(shù)；xi為二進(jìn)制編碼解中的第i個(gè)元素；l為哈希表的長度。通過將三個(gè)哈希表中對(duì)應(yīng)哈希值位置的元素賦值為1，完成對(duì)該解的記憶操作，過程如圖1所示。

3.3 結(jié)合對(duì)比認(rèn)知理論的學(xué)習(xí)算子選擇策略

算子的選擇既要考慮隨機(jī)性，又要考慮合理性。因此，算法在選擇學(xué)習(xí)操作時(shí)加入了個(gè)體適應(yīng)度值對(duì)各個(gè)知識(shí)庫平均適應(yīng)度值的比較。對(duì)比認(rèn)知理論認(rèn)為，人在作出決策時(shí)往往會(huì)受到認(rèn)知對(duì)比的影響，當(dāng)個(gè)體選擇學(xué)習(xí)操作時(shí)也應(yīng)通過比較選擇學(xué)習(xí)庫進(jìn)行學(xué)習(xí)。當(dāng)存在TKD或SKD的平均適應(yīng)度值優(yōu)于個(gè)體的適應(yīng)度值時(shí)，說明對(duì)應(yīng)的小組學(xué)習(xí)或社會(huì)學(xué)習(xí)操作效果較好，選擇對(duì)應(yīng)的學(xué)習(xí)操作，若TKD與SKD的平均適應(yīng)度值均優(yōu)于個(gè)體適應(yīng)度值，則選擇適應(yīng)度值更優(yōu)的學(xué)習(xí)算子，否則選擇隨機(jī)學(xué)習(xí)算子。

Xij=rand（0，1）" 0≤rand≤pr（t）

ikipj pr（t）lt;rand且fi（t）gt;tavg（t）且fi（t）gt;favg（t）

tkipj pr（t）lt;rand且tavg（t）gt;fi（t）且tavg（t）gt;favg（t）

skipj pr（t）lt;rand且favg（t）gt;fi（t）且favg（t）gt;tavg（t）（15）

其中：tavg（t）、favg（t）分別為TKD與SKD的平均適應(yīng)度值；pr（t）為進(jìn)行隨機(jī)學(xué)習(xí)的概率，具體表達(dá)式如下：

pr（t）=prmax－prmax－prminTt（16）

3.4 變鄰域搜索

為提高算法的局部開發(fā)能力，在對(duì)個(gè)體進(jìn)行學(xué)習(xí)得到新個(gè)體后，對(duì)該個(gè)體進(jìn)行變鄰域搜索。本文對(duì)多維背包問題設(shè)計(jì)了交換、反轉(zhuǎn)、刪除三種鄰域搜索算子，如圖2～4所示。

1）交換算子

為防止交換后解不發(fā)生變化，本文交換算子分別從選中與未選中放入背包的物品集合中選出物品進(jìn)行交換，如圖2所示。

2）反轉(zhuǎn)算子

本文反轉(zhuǎn)算子如圖3所示。

3）刪除算子

隨機(jī)選擇一個(gè)物品進(jìn)行刪除，在不違反約束的前提下，按照物品價(jià)值重量比排序放入若干剩余物品，如圖4所示。

3.5 算法流程

求解MKP問題的新型人類學(xué)習(xí)算法主要步驟如下：

a）初始化階段：生成初始群體，并計(jì)算每個(gè)個(gè)體的適應(yīng)度。將個(gè)體知識(shí)庫IKD、小組知識(shí)庫TKD和社會(huì)知識(shí)庫SKD初始化，個(gè)體放入對(duì)應(yīng)的知識(shí)庫中。

b）學(xué)習(xí)階段：根據(jù)對(duì)比認(rèn)知理論，按照式（15）（16），將個(gè)體適應(yīng)度值與各個(gè)知識(shí)庫平均適應(yīng)度值進(jìn)行比較，動(dòng)態(tài)選擇學(xué)習(xí)算子。

c）變鄰域搜索階段：對(duì)生成的新個(gè)體進(jìn)行變鄰域搜索，得到局部最優(yōu)解。

d）記憶階段：通過哈希函數(shù)與哈希表判斷該局部最優(yōu)解是否處于記憶狀態(tài)。若該解未被訪問過，則在哈希表中將該解記憶，否則重新進(jìn)行鄰域搜索，直至找到未記憶解。

e）更新階段：計(jì)算新一代個(gè)體的適應(yīng)度值，對(duì)IKD、TKD、SKD進(jìn)行更新。

判斷迭代次數(shù)是否大于最大迭代次數(shù)，若大于則終止，輸出最優(yōu)解。

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)設(shè)置

為驗(yàn)證新算法性能，選取多約束背包問題MKP標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集進(jìn)行數(shù)值實(shí)驗(yàn)。如文獻(xiàn)［22］所示，本文數(shù)據(jù)集可從OR-Library（http：//people.brunel.ac.uk/～mastjjb/jeb/orlib/mknapinfo.html）獲取。將MKP問題的眾多數(shù)據(jù)集進(jìn)行整理分類，將其分為由sento、hp、pb與weing 組成的小規(guī)模算例（set1）；由weish組成的中等規(guī)模算例（set2）；由chubeas中部分?jǐn)?shù)據(jù)組成的大規(guī)模算例（set3）與由gk中部分?jǐn)?shù)據(jù)組成的超大規(guī)模算例（set4）。此外，將所提算法與二進(jìn)制粒子群算法（red-billed blue magpie optimizer，RBMO）［11］、遺傳算法（genetic algorithm，GA）［12］、簡單人類學(xué)習(xí)算法（simple human learning optimization，SHLO）［17］與融合心理學(xué)的人類學(xué)習(xí)算法（human learning optimization algorithm based on learning psychology，LPHLO）［21］進(jìn)行比較。算法采用MATLAB R2022b編程實(shí)現(xiàn)，實(shí)驗(yàn)環(huán)境為Intel Core i7-12700H和Windows 11操作系統(tǒng)。本文算法的參數(shù)設(shè)置如表1所示。

對(duì)于對(duì)比算法，均采用對(duì)應(yīng)文獻(xiàn)的參數(shù)設(shè)置。各算法的最大迭代次數(shù)與種群規(guī)模均為1 000、100。

4.2 算法對(duì)比

表2為RMBO、GA、SHLO、LPHLO和NHLO四種算法求解小規(guī)模算例set1的結(jié)果。結(jié)果表明NHLO、SHLO、LPHLO、RMBO與GA算法均能成功求出小規(guī)模18個(gè)算例的已知最優(yōu)值。 NHLO的平均標(biāo)準(zhǔn)差為0，GA、RMBO、HLO與LPHLO算法18個(gè)算例的平均標(biāo)準(zhǔn)差分別為154.07、136.02、132.27、116.56。

上述實(shí)驗(yàn)結(jié)果表明，在求解難度較低的小規(guī)模算例中，所有對(duì)比算法均能求得算例的已知最優(yōu)解。但NHLO在求解小規(guī)模算例的穩(wěn)定性明顯優(yōu)于其余對(duì)比算法，每個(gè)算例30次實(shí)驗(yàn)的已知最優(yōu)解求得率均為100%。

表3記錄了各個(gè)算法求解中等規(guī)模算例set2的結(jié)果。從結(jié)果可知，本文算法與RMBO能夠求解得到30個(gè)算例的最優(yōu)解，但在求解的穩(wěn)定性上本文算法明顯更優(yōu)。雖然GA、SHLO與LPHLO能夠求出其中29個(gè)算例的最優(yōu)值，但是NHLO平均值、最差值指標(biāo)在29個(gè)算例中優(yōu)于對(duì)比算法，所有標(biāo)準(zhǔn)差均為0。

以上實(shí)驗(yàn)結(jié)果表明 NHLO算法在中規(guī)模算例上的求解精度、尋優(yōu)能力與穩(wěn)定性要明顯優(yōu)于其余對(duì)比算法。

表4為NHLO與四種對(duì)比算法RMBO、GA、SHLO、LPHLO求解大規(guī)模算例set3的結(jié)果。其中，表格中的數(shù)據(jù)集列表示求解的數(shù)據(jù)集序號(hào)，5-100-1則表示規(guī)模為5個(gè)約束、100個(gè)物品的數(shù)據(jù)集中的第一個(gè)數(shù)據(jù)。從實(shí)驗(yàn)結(jié)果來看，RMBO、GA、SHLO與LPHLO分別能夠求解出30個(gè)算例中6個(gè)、4個(gè)、7個(gè)、19個(gè)算例的已知最優(yōu)解，NHLO能夠求得所有算例最優(yōu)解。

通過表4可以發(fā)現(xiàn)，隨著算例規(guī)模的擴(kuò)大，四種對(duì)比算法的求解能力有限，難以求得已知最優(yōu)解。NHLO在大規(guī)模算例下求得的最優(yōu)值與平均值更大、標(biāo)準(zhǔn)差更小。這表明算法對(duì)大規(guī)模問題的求解能力更強(qiáng)、求解穩(wěn)定性更高。NHLO最差值大于對(duì)比算法，這表明算法通過對(duì)解進(jìn)行記憶，有效地跳出了局部最優(yōu)。

圖5為五種算法求解算例cb5-100-01、cb10-100-01、gk01、gk02的優(yōu)化速度對(duì)比。由圖可知，NHLO求解以上四個(gè)算例的優(yōu)化速度明顯優(yōu)于其余對(duì)比算法。這是因?yàn)镹HLO中解的記憶機(jī)制有效減少了解的重復(fù)搜索，提高了算法的優(yōu)化速度。

表5為五種算法求解超大規(guī)模算例set4的結(jié)果?？梢园l(fā)現(xiàn)在求解難度更高、數(shù)據(jù)規(guī)模超大的算例中，GA、RMBO、HLO與LPHO均無法求得已知最優(yōu)解。NHLO能夠求得算例中4個(gè)算例的已知最優(yōu)解，其余算例求得的最優(yōu)值與已知最優(yōu)解差距較小。

表5中LPHO求解gk01、gk04、gk05、gk06、gk11算例的標(biāo)準(zhǔn)差優(yōu)于NHLO，但最優(yōu)值與平均值低于NHLO。這表明LPHO雖求解結(jié)果穩(wěn)定，但求解質(zhì)量不高，易陷入局部最優(yōu)。與對(duì)比算法相比，NHLO在求解更大規(guī)模的算例時(shí)，求解效果更好，性能優(yōu)勢(shì)明顯。

圖6、7分別給出了這五種算法求解算例最優(yōu)解個(gè)數(shù)和平均標(biāo)準(zhǔn)差的比較情況。從圖5可知，NHLO在四種規(guī)模下成功求解算例個(gè)數(shù)高于四種對(duì)比算法，求解精度更高。圖6表明與其他算法相比，NHLO平均標(biāo)準(zhǔn)差更小，算法穩(wěn)定性更高，且隨著算例規(guī)模的擴(kuò)大，NHLO優(yōu)勢(shì)更加明顯。

4.3 三種優(yōu)化策略分析

本文NHLO的主要優(yōu)化策略包括基于哈希函數(shù)的解的記憶機(jī)制、結(jié)合對(duì)比認(rèn)知理論的學(xué)習(xí)算子選擇策略和變鄰域搜索三種。為方便起見，分別用A、B、C表示這三種策略。為測(cè)試這三種優(yōu)化策略的有效性，令NHLO1、NHLO2和NHLO3分別表示在基本HLO算法上增加A、B、C策略；NHLO4、NHLO5和NHLO6分別表示增加AB、AC、BC策略。求解不同規(guī)模算例的結(jié)果如表6所示。

通過表6可以發(fā)現(xiàn)：NHLO在四種評(píng)價(jià)指標(biāo)的表現(xiàn)上明顯優(yōu)于去除某一策略的算法NHLO-4、NHLO-5、NHLO-6。其中當(dāng)本文算法去除B策略后（NHLO-5），與去除A策略（NHLO-6）和去除C策略（NHLO-4）相比，總體上最大值、最小值與平均值下降更為顯著，標(biāo)準(zhǔn)差增加更為顯著。這說明B策略（即對(duì)比學(xué)習(xí)算子選擇策略）對(duì)算法性能的影響大于A與C策略，為算法性能提升的主要來源。這是因?yàn)閷?duì)比學(xué)習(xí)算子選擇策略能夠有效平衡全局探索與局部開發(fā)。算法通過對(duì)三種學(xué)習(xí)庫中解的質(zhì)量進(jìn)行比較，來動(dòng)態(tài)選擇算子。當(dāng)進(jìn)行隨機(jī)學(xué)習(xí)時(shí)，算法進(jìn)行全局探索；當(dāng)進(jìn)行個(gè)體、小組與社會(huì)學(xué)習(xí)時(shí)，算法進(jìn)行局部開發(fā)。通過合理的算子選擇使得算法可行解質(zhì)量更高、求得結(jié)果更加穩(wěn)定。因此，NHLO-5與NHLO-4、NHLO-6相比，最大值、最小值與平均值更大，標(biāo)準(zhǔn)差更小。

A策略為解的記憶機(jī)制，該策略通過對(duì)算法已經(jīng)訪問過的解進(jìn)行記憶，防止算法對(duì)解空間重復(fù)搜索，避免算法陷入局部最優(yōu)。表6中，NHLO-1與基本HLO算法相比，NHLO-1求解最小值總體上大于HLO。這說明解的記憶機(jī)制能夠有效幫助算法跳出局部最優(yōu)，導(dǎo)致最小值增大。C策略為變鄰域搜索操作，通過搜索鄰域中的解提高算法的局部開發(fā)能力。表6中加入C策略后，NHLO-3求得可行解的平均值總體上大于HLO算法。這表明算法通過對(duì)可行解進(jìn)行鄰域搜索進(jìn)一步提高了解的質(zhì)量，使得總體的平均值提高。圖8為八個(gè)算法求解算例10-100-5的優(yōu)化速度對(duì)比。結(jié)果表明A、B、C三種策略能夠有效提升算法的優(yōu)化速度，且三種策略的融合能夠大幅提高算法求解MKP問題的優(yōu)化速度。

綜上所述，解的記憶機(jī)制與變鄰域搜索能夠避免算法陷入局部最優(yōu)并提高了局部開發(fā)的能力；對(duì)比學(xué)習(xí)算子選擇策略有效平衡了算法的探索與開發(fā)。實(shí)驗(yàn)結(jié)果表明，三種策略均能有效增強(qiáng)算法的性能且三種策略的融合能夠大幅度提升算法的性能與優(yōu)化速度。

5 結(jié)束語

本文針對(duì)現(xiàn)有算法求解MKP問題存在精度低、穩(wěn)定性差、難以求解超大規(guī)模算例等問題，結(jié)合認(rèn)知心理學(xué)提出了一種新型人類學(xué)習(xí)算法。本文設(shè)計(jì)了基于哈希函數(shù)的解的記憶機(jī)制、結(jié)合對(duì)比認(rèn)知理論的學(xué)習(xí)算子選擇和變鄰域搜索三種策略來提升算法性能。本文將新型人類學(xué)習(xí)算法應(yīng)用于小規(guī)模、中等規(guī)模、大規(guī)模、超大規(guī)模共76個(gè)MKP問題算例，并與GA、RMBO、HLO、LPHLO算法對(duì)比。實(shí)驗(yàn)結(jié)果表明，本文算法在求解精度、求解穩(wěn)定性以及優(yōu)化速度方面明顯優(yōu)于對(duì)比算法，能夠有效求解超大規(guī)模算例。為進(jìn)一步驗(yàn)證三種優(yōu)化策略有效性，本文將三種策略排列組合加入HLO算法，求解不同規(guī)模算例。結(jié)果表明三種優(yōu)化策略能夠有效提升算法的計(jì)算精度、穩(wěn)定性與優(yōu)化速度。后續(xù)可將算法應(yīng)用于多目標(biāo)背包問題。

參考文獻(xiàn)：

［1］Lorie J H， Savage L J. Three problems in rationing capital［J］. The Journal of Business， 1955， 28（4）： 229-239.

［2］Claude M， Donald R. Resource allocation via 0-1 programming［J］. Decision Sciences， 1973， 4（1）： 119-132.

［3］Gilmore P， Gomory R. The theory and computation of knapsack functions［J］. Operations Research， 1966， 14（6）： 1045-1074.

［4］Li Ying， Chen Mingzhou， Huo Jiazhen. A hybrid adaptive large neighborhood search algorithm for the large-scale heterogeneous container loading problem［J］. Expert Systems with Applications， 2022， 189： article ID 115909.

［5］Gavish B， Pirkul H. Allocation of databases and processors in a distributed data processing ［EB/OL］. （1982）. https：//api.semanticscholar.org/CorpusID：59647887.

［6］Straszak A， Libura M， Sikorski J， et al. Computer-assisted constrained approval voting［J］. Group Decision and Negotiation， 1993， 2： 375-85.

［7］王麗娜， 陸芷. 多維背包問題的啟發(fā)式算法研究探討 ［J］. 軟件， 2024， 45（2）： 34-36. （Wang Lina， Lu Zhi. Heuristic algorithms of multidimensional knapsack problem ［J］. Software， 2024， 45（2）： 34-36.）

［8］Wei S. A branch and bound method for the multi-constraint zero-one knapsack problem［J］. Journal of the Operational Research Society， 1979， 30（4）： 369-378.

［9］Fu Shengwei， Li Ke， Huang Haisong， et al. Red-billed blue magpie optimizer： a novel metaheuristic algorithm for 2D/3D UAV path planning and engineering design problems ［J］. Artificial Intelligence Review， 2024， 57（6）： 1-89.

［10］Thomas L， Augustine M. The imbedded state space approach to reducing dimensionality in dynamic programs of higher dimensions ［J］. Journal of Mathematical Analysis and Applications， 1974， 48（3）： 801-810.

［11］熊偉清， 魏平， 王小權(quán). 蟻群算法求解多維0/1背包問題 ［J］. 計(jì)算機(jī)工程與科學(xué)， 2006， 28（10）： 78-79， 86. （Xiong Weiqing， Wei Ping， Wang Xiaoquan. Ant colony algorithm for solving multi-dimensional 0/1 knapsack problem ［J］. Computer Engineering and Science， 2006， 28（10）： 78-79， 86.）

［12］Aiman H E， Ahmad T S， Sadiq M S. Binary particle swarm optimization （BPSO） based state assignment for area minimization of sequential circuits ［J］. Applied Soft Computing Journal， 2013， 13（12）： 4832-4840.

［13］曾智， 楊小帆， 陳靜， 等. 求解多維0-1背包問題的一種改進(jìn)的遺傳算法 ［J］. 計(jì)算機(jī)科學(xué)， 2006， 33（7）： 220-223. （Zeng Zhi， Yang Xiaofan， Chen Jing， et al. An improved genetic algorithm for solving multi-dimensional 0-1 knapsack problem［J］. Computer Science， 2006， 33（7）： 220-223.）

［14］Wang Ling， Ni Haoqi， Yang Ruixin， et al. A simple human learning optimization algorithm ［M］// Fei Minrui， Peng Chen， Su Zhou， et al. Computational Intelligence， Networked Systems and Their Applications. Berlin： Springer， 2014： 56-65.

［15］Ding Haojie， Gu Xingsheng. Hybrid of human learning optimization algorithm and particle swarm optimization algorithm with scheduling strategies for the flexible job-shop scheduling problem［J］. Neurocomputing， 2020， 414： 313-332.

［16］Shoja A， Molla-Alizadeh-Zavardehi S， Niroomand S. Hybrid adaptive simplified human learning optimization algorithms for supply chain network design problem with possibility of direct shipment［J］. Applied Soft Computing， 2020， 96： article ID 106594.

［17］Li Xiaoyu， Yao Jun， Wang Ling， et al. Application of human lear-ning optimization algorithm for production scheduling optimization［M］// Fei Minrui， Ma Shiwei， Li Xin， et al. Advanced Computational Methods in Life System Modeling and Simulation. Singapore： Springer， 2017： 242-252.

［18］Alguliyev R， Aliguliyev R， lsazade N. A sentence selection model and HLO algorithm for extractive text summarization［C］// Proc of the 10th International Conference on Application of Information and Communication Technologies. Piscataway， NJ： IEEE Press， 2016： 1-4.

［19］張平改， 費(fèi)敏銳， 王靈， 等. 基于自適應(yīng)顏色模型的爐膛火焰識(shí)別方法［J］. 中國科學(xué)： 信息科學(xué)， 2018， 48（7）： 856-870. （Zhang Pinggai， Fei Minrui， Wang Ling， et al. Furnace flame recognition method based on adaptive color model［J］. Science in China： Information Sciences， 2018， 48（7）： 856-870.）

［20］Wang Ling， Yang Ruixin， Ni Haoqi， et al. A human learning optimization algorithm and its application to multi-dimensional knapsack problems［J］. Applied Soft Computing， 2015， 34： 736-743.

［21］孟晗， 馬良， 劉勇. 融合學(xué)習(xí)心理學(xué)的人類學(xué)習(xí)優(yōu)化算法［J］. 計(jì)算機(jī)應(yīng)用， 2022， 42（5）： 1367-1374. （Meng Han， Ma Liang， Liu Yong. Human learning optimization algorithm integrating learning psychology［J］. Journal of Computer Applications， 2022， 42（5）： 1367-1374.）

［22］Chu P C， Beasley J E. A genetic algorithm for the multidimensional knapsack problem［J］. Journal of Heuristics， 1998， 4： 63-86.

［23］Cui Tianxiang， Du Nanjiang， Yang Xiaoying， et al. Multi-period portfolio optimization using a deep reinforcement learning hyper-heuristic approach［J］. Technological Forecasting and Social Change， 2024， 198： 122944.

［24］Han Yuhang， Zhang Miaohan， Nan Pan， et al. Two-stage heuristic algorithm for vehicle-drone collaborative delivery and pickup based on medical supplies resource allocation［J］. Journal of King Saud University-Computer and Information Sciences， 2023， 35（10）： 101811.

［25］Fréville A. The multidimensional 0-1 knapsack problem： an overview［J］. European Journal of Operational Research， 2004， 155（1）： 1-21.

［26］丁增良， 陳玨， 邱禧荷. 一種應(yīng)用于旅行商問題的萊維飛行轉(zhuǎn)移規(guī)則蟻群優(yōu)化算法［J］. 計(jì)算機(jī)應(yīng)用研究， 2024， 41（5）： 1420-1427. （Ding Zengliang， Chen Jue， Qiu Xihe. Ant colony optimization algorithm based on Lévy flight transfer rule for solving traveling salesman problem［J］. Application Research of Computers， 2024， 41（5）： 1420-1427.）

［27］Kleinmuntz D N， Kleinmuntz C E. Multiobjective capital budgeting in not-for-profit hospitals and healthcare systems［D］. Champaign， IL： University of Illinois at Urbana-Champaign， 2001.

［28］Gearing C， Swart W， Var T. Determining the optimal investment poli-cy for the tourism sector of a developing country［J］. Management Science， 1973， 20： 487-497.