融合學(xué)習(xí)心理學(xué)的人類學(xué)習(xí)優(yōu)化算法

孟晗，馬良，劉勇

（上海理工大學(xué) 管理學(xué)院，上海 200093）（?通信作者電子郵箱menghan_usst@163.com）

融合學(xué)習(xí)心理學(xué)的人類學(xué)習(xí)優(yōu)化算法

孟晗*，馬良，劉勇

（上海理工大學(xué) 管理學(xué)院，上海 200093）（?通信作者電子郵箱menghan_usst@163.com）

針對(duì)簡(jiǎn)單人類學(xué)習(xí)優(yōu)化（SHLO）算法尋優(yōu)精度低和收斂慢的問(wèn)題，提出了一種融合學(xué)習(xí)心理學(xué)的人類學(xué)習(xí)優(yōu)化算法（LPHLO）。首先，結(jié)合學(xué)習(xí)心理學(xué)中的小組學(xué)習(xí)（TBL）理論引入TBL算子，從而在個(gè)體經(jīng)驗(yàn)、社會(huì)經(jīng)驗(yàn)的基礎(chǔ)上，增加了小組經(jīng)驗(yàn)來(lái)對(duì)個(gè)體學(xué)習(xí)狀態(tài)進(jìn)行控制，避免算法早熟收斂；然后，結(jié)合記憶編碼理論提出了動(dòng)態(tài)調(diào)參策略，從而實(shí)現(xiàn)個(gè)體信息、社會(huì)信息、團(tuán)隊(duì)信息的有效融合，更好地平衡了算法局部探索和全局開(kāi)發(fā)的能力。選取典型的組合優(yōu)化難題——背包問(wèn)題中的兩種算例，即單約束背包問(wèn)題、多約束背包問(wèn)題進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，所提LPHLO與基本的SHLO算法、遺傳算法（GA）和二進(jìn)制粒子群優(yōu)化（BPSO）算法等算法相比，在尋優(yōu)精度和收斂速度方面更具優(yōu)勢(shì)，具有更好的解決實(shí)際問(wèn)題的能力。

簡(jiǎn)單人類學(xué)習(xí)優(yōu)化算法；學(xué)習(xí)心理學(xué)；學(xué)習(xí)策略；小組學(xué)習(xí)算子；動(dòng)態(tài)調(diào)參策略

0 引言

簡(jiǎn)單人類學(xué)習(xí)優(yōu)化（Simple Human Learning Optimization， SHLO）算法是Wang等［1］提出的一種新的群智能優(yōu)化算法，該算法模擬了人類學(xué)習(xí)過(guò)程，人類群體通過(guò)隨機(jī)學(xué)習(xí)、個(gè)體學(xué)習(xí)、社會(huì)學(xué)習(xí)這三種學(xué)習(xí)方式提升自己的知識(shí)和能力。SHLO算法僅使用一個(gè)公式就可以完成迭代尋優(yōu)過(guò)程，具有操作簡(jiǎn)單、易于實(shí)現(xiàn)、全局尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn)，其競(jìng)爭(zhēng)力主要來(lái)源于對(duì)學(xué)習(xí)算子和算法參數(shù)的巧妙設(shè)計(jì)。與其他典型智能優(yōu)化算法相比，SHLO算法也展現(xiàn)了其優(yōu)良特性，例如：與遺傳算法（Genetic Algorithm， GA）［2］相比，SHLO的經(jīng)驗(yàn)庫(kù)使其具有精英保留機(jī)制，群體可以向最優(yōu)個(gè)體學(xué)習(xí)，從而加快了算法的收斂；與微粒群算法相比，SHLO的隨機(jī)學(xué)習(xí)算子使其具有突變功能，擴(kuò)大了算法的搜索空間。SHLO的這些優(yōu)點(diǎn)，使其在文本摘要［3］、圖像匹配［4］、模糊PID（Proportion-Integration-Differentiation）控制［5］等工程優(yōu)化問(wèn)題上得到了廣泛的應(yīng)用。

作為一種新型的群智能算法，SHLO算法性能存在很大的提升空間，學(xué)者們近幾年提出了一系列改進(jìn)的SHLO算法。文獻(xiàn)［6］中提出了新的人類學(xué)習(xí)優(yōu)化算法，在算法中增加重新學(xué)習(xí)算子，當(dāng)個(gè)體適應(yīng)度在一定迭代次數(shù)內(nèi)沒(méi)有得到改善時(shí)，重新學(xué)習(xí)算子就會(huì)清除個(gè)體的當(dāng)前最優(yōu)解。這種做法可以擴(kuò)大算法的搜索空間，降低算法陷入局部最優(yōu)的風(fēng)險(xiǎn)，但是清除當(dāng)前解的操作可能會(huì)使算法錯(cuò)過(guò)全局最優(yōu)解，增加算法的運(yùn)行時(shí)間。文獻(xiàn)［7］中提出了自適應(yīng)簡(jiǎn)化人類學(xué)習(xí)優(yōu)化（Adaptive Simplified Human Learning Optimization， ASHLO）算法，引入自適應(yīng)調(diào)參策略在尋優(yōu)過(guò)程中不斷調(diào)整三種學(xué)習(xí)方式所占比例，避免算法陷入局部最優(yōu)，算法收斂精度得到了提高，但是每次迭代重新確定學(xué)習(xí)概率的方法減慢了算法的收斂。文獻(xiàn)［8］中考慮到人類智力服從高斯分布，在算法中引入高斯分布更新策略調(diào)整每個(gè)個(gè)體的學(xué)習(xí)能力，這一操作保證了群體的多樣性，提高了整個(gè)群體的尋優(yōu)效率，強(qiáng)化了算法的全局搜索能力。文獻(xiàn)［9］中利用粒子群優(yōu)化算法具有較好的局部搜索能力，將粒子群優(yōu)化算法的粒子更新策略應(yīng)用于SHLO的學(xué)習(xí)過(guò)程，提高了SHLO算法的收斂能力，但增加了陷入局部最優(yōu)的風(fēng)險(xiǎn)。這些改進(jìn)在一定程度上提高了原始算法的性能，但對(duì)算法自身的迭代公式研究較少，算法仍然存在早熟收斂、后期收斂較慢、容易陷入局部最優(yōu)解等問(wèn)題。

SHLO作為一個(gè)以人為主體，模擬人類學(xué)習(xí)的新型智能算法，現(xiàn)有改進(jìn)主要模擬人類學(xué)習(xí)特征和與其他算法結(jié)合。這些改進(jìn)都是基于簡(jiǎn)化的人類學(xué)習(xí)模型，很少考慮到人的心理給學(xué)習(xí)帶來(lái)的影響：例如，在許多情況下，小組學(xué)習(xí)（Team-Based Learning， TBL）對(duì)一個(gè)人的學(xué)習(xí)有很大的幫助。針對(duì)上述問(wèn)題，本文在算法設(shè)計(jì)中采取類似的思路，聚焦于學(xué)習(xí)心理學(xué)，模擬學(xué)習(xí)過(guò)程中人的心理因素對(duì)學(xué)習(xí)結(jié)果產(chǎn)生的影響，首次將學(xué)習(xí)心理學(xué)理論應(yīng)用于算法改進(jìn)之中，為算法提供了全新且可行的改進(jìn)方向。從學(xué)習(xí)心理學(xué)的角度分析SHLO，結(jié)合小組學(xué)習(xí)理論和記憶編碼理論在算法中加入小組學(xué)習(xí)策略和動(dòng)態(tài)學(xué)習(xí)策略，并設(shè)計(jì)對(duì)應(yīng)的小組學(xué)習(xí)算子和動(dòng)態(tài)調(diào)參策略。小組學(xué)習(xí)算子負(fù)責(zé)增強(qiáng)算法全局搜索能力，提高了算法的尋優(yōu)精度；動(dòng)態(tài)調(diào)參策略負(fù)責(zé)更好地平衡全局搜索與局部搜索，提高算法的尋優(yōu)效率，加快算法的收斂。最后將本文算法用于求解經(jīng)典的非確定性多項(xiàng)式（Nondeterministic Polynomial， NP）問(wèn)題——背包問(wèn)題，通過(guò)大量仿真實(shí)驗(yàn)驗(yàn)證了所提算法的性能。

1 簡(jiǎn)單人類學(xué)習(xí)優(yōu)化算法

SHLO算法［1］的基本概念源于對(duì)人類學(xué)習(xí)行為的模仿研究。從宏觀角度看，人類學(xué)習(xí)方式分為隨機(jī)學(xué)習(xí)、個(gè)體學(xué)習(xí)和社會(huì)學(xué)習(xí)。比如，一個(gè)人為了提高自己的知識(shí)水平，會(huì)進(jìn)行反復(fù)的練習(xí)：他會(huì)由于缺乏先驗(yàn)知識(shí)或希望探索新的學(xué)習(xí)策略而進(jìn)行隨機(jī)學(xué)習(xí)，他可以積累自己的學(xué)習(xí)經(jīng)驗(yàn)以指導(dǎo)接下來(lái)的學(xué)習(xí)（個(gè)體學(xué)習(xí)），也可以通過(guò)向前輩請(qǐng)教或查閱書(shū)籍等方式進(jìn)行社會(huì)學(xué)習(xí)。標(biāo)準(zhǔn)SHLO算法受到這種簡(jiǎn)化的人類學(xué)習(xí)機(jī)制的啟發(fā)，模擬人類學(xué)習(xí)過(guò)程，開(kāi)發(fā)了與之對(duì)應(yīng)的隨機(jī)學(xué)習(xí)算子、個(gè)體學(xué)習(xí)算子和社會(huì)學(xué)習(xí)算子，并利用三個(gè)學(xué)習(xí)算子產(chǎn)生新解，經(jīng)過(guò)反復(fù)迭代尋找最優(yōu)值，下面介紹其基本步驟。

1.1 初始化種群

SHLO采用二進(jìn)制編碼框架，每個(gè)個(gè)體代表一組解，用二進(jìn)制字符串表示。

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

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

隨機(jī)學(xué)習(xí)是開(kāi)拓新知識(shí)的有效途徑，為了模仿人類隨機(jī)學(xué)習(xí)過(guò)程，SHLO開(kāi)發(fā)了隨機(jī)學(xué)習(xí)算子，按式（2）進(jìn)行隨機(jī)學(xué)習(xí)：

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

個(gè)體學(xué)習(xí)是人們依靠自身經(jīng)驗(yàn)進(jìn)行自我提升的學(xué)習(xí)過(guò)程。SHLO開(kāi)發(fā)了個(gè)體學(xué)習(xí)算子，創(chuàng)建了用來(lái)儲(chǔ)存?zhèn)€體最好經(jīng)驗(yàn)的個(gè)體知識(shí)庫(kù)，如式（3）所示?；诘闹R(shí)，SHLO可以按式（4）進(jìn)行個(gè)體學(xué)習(xí)：

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

隨機(jī)學(xué)習(xí)和個(gè)體學(xué)習(xí)的效率可能比較低，而社會(huì)學(xué)習(xí)可以彌補(bǔ)這個(gè)缺陷。SHLO為了進(jìn)行社會(huì)學(xué)習(xí)，開(kāi)發(fā)了社會(huì)學(xué)習(xí)算子，創(chuàng)建了用于儲(chǔ)存社會(huì)經(jīng)驗(yàn)的社會(huì)知識(shí)庫(kù)，因此可以基于的知識(shí)，按式（5）進(jìn)行社會(huì)學(xué)習(xí)：

SHLO以特定的概率執(zhí)行三個(gè)學(xué)習(xí)算子，不斷迭代產(chǎn)生新解并尋求全局最優(yōu)解，如式（6）所示：

2 融合學(xué)習(xí)心理學(xué)的人類學(xué)習(xí)優(yōu)化算法

SHLO算法是基于一個(gè)簡(jiǎn)化的人類學(xué)習(xí)模型，而真正的人類學(xué)習(xí)是一個(gè)極其復(fù)雜的過(guò)程，存在較大的改進(jìn)空間。從算法角度分析，基本的人類學(xué)習(xí)優(yōu)化算法有兩點(diǎn)不足：學(xué)習(xí)算子的設(shè)計(jì)具有局限性，如式（4）～（5）所示，僅僅學(xué)習(xí)群體當(dāng)前的最好經(jīng)驗(yàn)以及個(gè)體過(guò)去的最好經(jīng)驗(yàn)，限制了個(gè)體的學(xué)習(xí)搜索范圍，可能使個(gè)體落入局部最優(yōu)解而無(wú)法逃脫；參數(shù)設(shè)置不夠合理，SHLO的參數(shù)和對(duì)個(gè)體學(xué)習(xí)狀態(tài)進(jìn)行控制，決定了個(gè)體學(xué)習(xí)的效果，進(jìn)而影響算法的尋優(yōu)性能，如式（6）所示，采取固定的參數(shù)難以保證算法在尋優(yōu)過(guò)程中平衡好算法的探索和開(kāi)發(fā)能力，不能保證算法收斂。

作為一個(gè)以人類學(xué)習(xí)為模擬對(duì)象的智能算法，從人類學(xué)習(xí)過(guò)程出發(fā)，能從源頭上彌補(bǔ)SHLO算法的一些不足。在過(guò)去的幾十年里，學(xué)習(xí)心理學(xué)理論取得了許多成果，能為人類學(xué)習(xí)提供科學(xué)的基礎(chǔ)知識(shí)。從學(xué)習(xí)心理學(xué)角度分析，基本的人類學(xué)習(xí)優(yōu)化算法在學(xué)習(xí)過(guò)程中沒(méi)有采用高效的學(xué)習(xí)策略，不能充分發(fā)揮個(gè)人的學(xué)習(xí)潛能。為了進(jìn)一步提高算法的性能，融合學(xué)習(xí)心理學(xué)的人類學(xué)習(xí)優(yōu)化算法（Human Learning Optimization algorithm based on Learning Psychology， LPHLO）結(jié)合學(xué)習(xí)心理學(xué)理論對(duì)人類學(xué)習(xí)優(yōu)化算法進(jìn)行了兩個(gè)方面的改進(jìn)：結(jié)合小組學(xué)習(xí)理論，在個(gè)體信息和社會(huì)信息基礎(chǔ)上，增加了小組信息對(duì)個(gè)體學(xué)習(xí)狀態(tài)進(jìn)行控制，提高了個(gè)體搜索效率，解決了個(gè)體趨同問(wèn)題；在增加小組信息之后，三種信息作用權(quán)重的選擇又是一個(gè)新的問(wèn)題，對(duì)此，SHLO引入記憶編碼理論提出動(dòng)態(tài)調(diào)參策略改善算法參數(shù)，及時(shí)調(diào)整不同學(xué)習(xí)方式的選擇概率，有效利用了各種學(xué)習(xí)信息，克服了固定參數(shù)的弊端，保證了算法的尋優(yōu)速度。

2.1 引入小組學(xué)習(xí)理論改進(jìn)學(xué)習(xí)算子

在基本SHLO算法中，如式（6）所示，三個(gè)學(xué)習(xí)算子被用來(lái)產(chǎn)生新的候選解以搜索最優(yōu)值。隨機(jī)學(xué)習(xí)算子使個(gè)體保持學(xué)習(xí)活力，使其有擴(kuò)展搜索空間的趨勢(shì)，有能力探索新的區(qū)域。個(gè)體學(xué)習(xí)算子和社會(huì)學(xué)習(xí)算子表示個(gè)體的學(xué)習(xí)動(dòng)作來(lái)源于自己經(jīng)驗(yàn)的部分和群體經(jīng)驗(yàn)的部分，每個(gè)個(gè)體都是通過(guò)這兩部分的信息來(lái)確定運(yùn)動(dòng)趨勢(shì)。因此，在全局最優(yōu)信息引導(dǎo)下，隨著尋優(yōu)過(guò)程的深入，個(gè)體學(xué)習(xí)狀態(tài)趨同，使得群體多樣性喪失，陷入早熟收斂。觀察式（2）、（4）～（5）可以發(fā)現(xiàn)，SHLO設(shè)計(jì)了過(guò)于簡(jiǎn)單的學(xué)習(xí)方式，這是導(dǎo)致算法早熟的主要原因之一。在真實(shí)學(xué)習(xí)環(huán)境中，隨機(jī)學(xué)習(xí)、個(gè)體學(xué)習(xí)和社會(huì)學(xué)習(xí)不能全面反映一個(gè)人的學(xué)習(xí)過(guò)程，人們?cè)诤芏鄷r(shí)候也會(huì)進(jìn)行小組學(xué)習(xí)。小組學(xué)習(xí)（TBL）是一種很常見(jiàn)的學(xué)習(xí)方式，TBL的核心是不同的學(xué)習(xí)者在完成任務(wù)的過(guò)程中進(jìn)行交流，在這種學(xué)習(xí)模式中，學(xué)習(xí)者之間有真正的信息溝通。小組學(xué)習(xí)理論對(duì)于人們學(xué)習(xí)是有益的，Burgess等［10］驗(yàn)證了TBL能調(diào)動(dòng)學(xué)生學(xué)習(xí)的積極性，提高了學(xué)生解決問(wèn)題的能力，改善了學(xué)習(xí)的效果；Eguchi等［11］驗(yàn)證了TBL能有效提高學(xué)生的學(xué)習(xí)成績(jī)。

鑒于此，LPHLO結(jié)合小組學(xué)習(xí)理論，在算法中引入小組學(xué)習(xí)算子，用來(lái)把小組學(xué)習(xí)策略加到群體迭代學(xué)習(xí)過(guò)程中。它設(shè)定人為一個(gè)小組，小組成員根據(jù)小組的經(jīng)驗(yàn)進(jìn)行學(xué)習(xí)。小組知識(shí)庫(kù)被用來(lái)儲(chǔ)存小組最佳經(jīng)驗(yàn)，如式（7）所示：

LPHLO通過(guò)執(zhí)行隨機(jī)學(xué)習(xí)算子、個(gè)人學(xué)習(xí)算子、小組學(xué)習(xí)算子和社會(huì)學(xué)習(xí)算子產(chǎn)生新的解決方案，如式（9）所示：

2.2 引入記憶編碼理論改進(jìn)參數(shù)

小組學(xué)習(xí)算子的引入，使算法在個(gè)體信息和社會(huì)信息的基礎(chǔ)上增加了小組信息，個(gè)體和群體的信息得到了更充分的交流和應(yīng)用，較好地解決了全局最優(yōu)信息引導(dǎo)下粒子狀態(tài)趨同問(wèn)題，提高了算法的全局尋優(yōu)能力和尋優(yōu)精度。但是，不同學(xué)習(xí)信息的有效融合是影響算法搜索效果的重要因素之一，也是改進(jìn)學(xué)習(xí)算子之后要考慮的問(wèn)題。如式（9）所示，參數(shù)、、決定了各學(xué)習(xí)算子的貢獻(xiàn)率，直接影響算法探索能力和開(kāi)發(fā)能力之間的平衡。基本SHLO設(shè)置了固定參數(shù)，其優(yōu)化效果有待提高。通常在智能優(yōu)化算法里，參數(shù)動(dòng)態(tài)調(diào)整的效果會(huì)更好。Wang等［7］對(duì)參數(shù)和采取了自適應(yīng)調(diào)整策略，有效減輕了參數(shù)設(shè)置的負(fù)擔(dān)。由此可見(jiàn)，采取動(dòng)態(tài)參數(shù)更加合理，正如人們?cè)趯W(xué)習(xí)過(guò)程中會(huì)不斷調(diào)整自己的學(xué)習(xí)狀態(tài)。人們?cè)趯W(xué)習(xí)過(guò)程中，傾向于總結(jié)學(xué)習(xí)規(guī)律，根據(jù)不同的學(xué)習(xí)能力選擇更高效的學(xué)習(xí)策略。記憶編碼理論揭示了一系列人類記憶規(guī)律，可以幫助人們更好地掌握學(xué)習(xí)規(guī)律，提高學(xué)習(xí)質(zhì)量。Craik等［12］驗(yàn)證了年齡差異對(duì)學(xué)習(xí)記憶有影響，揭示了人類記憶變化規(guī)律，即隨著年齡的增長(zhǎng)，盲目隨機(jī)學(xué)習(xí)的可能性逐漸降低，根據(jù)自身經(jīng)驗(yàn)以及外界經(jīng)驗(yàn)學(xué)習(xí)的能力相對(duì)提高。

據(jù)此，LPHLO結(jié)合記憶編碼理論提出了動(dòng)態(tài)學(xué)習(xí)策略，在學(xué)習(xí)早期更多地進(jìn)行隨機(jī)學(xué)習(xí)，隨著年齡增加更多地進(jìn)行個(gè)體學(xué)習(xí)以及小組學(xué)習(xí)。為了模擬動(dòng)態(tài)學(xué)習(xí)策略，LPHLO在算法中引入了動(dòng)態(tài)調(diào)參策略，用迭代次數(shù)的增加來(lái)模擬人類年齡的變化，、、、分別代表隨機(jī)學(xué)習(xí)、個(gè)體學(xué)習(xí)、小組學(xué)習(xí)、社會(huì)學(xué)習(xí)的貢獻(xiàn)率，它們的大小隨著迭代次數(shù)的變化而變化，其中的值隨著迭代次數(shù)的增加呈現(xiàn)遞減趨勢(shì)，、的值隨著迭代次數(shù)的增加呈現(xiàn)遞增趨勢(shì)，如式（10）～（12）所示：

2.3 更新策略

2.4 LPHLO流程

LPHLO的具體步驟如下：

步驟2 學(xué)習(xí)階段。在迭代學(xué)習(xí)過(guò)程中，加入小組學(xué)習(xí)算子和動(dòng)態(tài)調(diào)參策略，按照式（10）～（12）得到、、的值，然后按照式（9）生成新一代群體。

步驟3 更新階段。計(jì)算新一代群體的適應(yīng)度值，根據(jù)更新策略分別更新、、。

步驟4 判斷終止準(zhǔn)則，如果當(dāng)前迭代次數(shù)大于最大迭代次數(shù)，則輸出所求問(wèn)題的最優(yōu)解并終止運(yùn)行LPHLO；否則轉(zhuǎn)步驟2。

3 實(shí)驗(yàn)和結(jié)果分析

為了測(cè)試本文算法的有效性，選取經(jīng)典的NP問(wèn)題——單約束背包問(wèn)題（0-1 Knapsack Problem， 0-1KP）［13］和多約束背包問(wèn)題（Multi-constrained KP， MKP）進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)1按照文獻(xiàn)［14］中提出的0-1KP實(shí)例產(chǎn)生流程，產(chǎn)生20個(gè)0-1KP實(shí)例測(cè)試算法性能。實(shí)驗(yàn)2來(lái)自O(shè)R-Library的MKP實(shí)例，在30個(gè)MKP算例上考察本文算法優(yōu)化多約束背包問(wèn)題的有效性和可行性。將所提的LPHLO和ASHLO、SHLO、GA、二進(jìn)制粒子群優(yōu)化（Binary Particle Swarm Optimization， BPSO）算法［15］以及二進(jìn)制蝙蝠算法（Binary Bat Algorithm， BBA）［16］這五種算法在每個(gè)實(shí)例上進(jìn)行30次對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境如下：計(jì)算機(jī)CPU為i5-6200U，內(nèi)存RAM為4 GB，操作系統(tǒng)為Windows 10，編程軟件為Matlab 2019a。

3.1 單約束背包問(wèn)題仿真實(shí)驗(yàn)

為了充分測(cè)試LPHLO的性能和特點(diǎn)，使用兩組共20個(gè)大規(guī)模0-1KP實(shí)例來(lái)測(cè)試算法的尋優(yōu)性能。每組10個(gè)問(wèn)題維數(shù)分別設(shè)置為100、200、400、600、800、1 000、1 200、1 500、2 000、3 000。對(duì)于KP的每個(gè)實(shí)例，重量和價(jià)值根據(jù)文獻(xiàn)［14］產(chǎn)生，即重量在5～20隨機(jī)取值，價(jià)值在50～100隨機(jī)取值。每組10個(gè)實(shí)例的容量值分別設(shè)置為1 000、2 400、4 000、6 000、8 000、10 000、14 000、16 000、20 000、25 000。維數(shù)小于1 000時(shí)，種群大小和最大迭代次數(shù)分別設(shè)置為100、10 000，否則分別設(shè)置為200、40 000。每個(gè)實(shí)例產(chǎn)生后保持不變，算法其他參數(shù)設(shè)置如下：BBA中，；BPSO中，；GA中，；SHLO中，；ASHLO中，；LPHLO中，。

不同算法的0-1KP實(shí)例求解結(jié)果如表1所示，每個(gè)實(shí)例上最好的值做加粗處理。其中，第1列是問(wèn)題類型，如KP1.100表示第1組實(shí)驗(yàn)中問(wèn)題維數(shù)為100的0-1KP實(shí)例。分別從最優(yōu)值、平均值、最差值和標(biāo)準(zhǔn)差這4個(gè)方面對(duì)算法進(jìn)行全面評(píng)估。最優(yōu)值、平均值可以反映算法的求解精度和尋優(yōu)能力，最差值、標(biāo)準(zhǔn)差可以反映算法的穩(wěn)定性和跳出局部極值的能力。可以看出，BBA、BPSO、GA這三種算法獲得的優(yōu)化結(jié)果不如LPHLO、ASHLO、SHLO。這是因?yàn)槿祟悓W(xué)習(xí)優(yōu)化算法是天然的二進(jìn)制編碼算法，對(duì)二進(jìn)制問(wèn)題有更強(qiáng)的求解能力。當(dāng)問(wèn)題規(guī)模不超過(guò)1 000時(shí)，LPHLO、ASHLO、SHLO這3種算法無(wú)論是求解質(zhì)量還是求解的穩(wěn)定性差別并不大；但隨著問(wèn)題維數(shù)的增加，解空間呈幾何倍增長(zhǎng)，特別當(dāng)問(wèn)題規(guī)模超過(guò)1 200時(shí)，搜索空間超過(guò)21200級(jí)，算法在有限迭代次數(shù)內(nèi)僅能開(kāi)采較小的解空間，造成求解質(zhì)量的下降，這就對(duì)算法擺脫局部最優(yōu)和勘探新解的能力有了更高的要求。對(duì)比發(fā)現(xiàn)，LPHLO的最優(yōu)值、平均值和最差值在所有實(shí)例中都是最好的，且隨著問(wèn)題規(guī)模的增加，與另外5種算法的差距越來(lái)越明顯，表明LPHLO有更強(qiáng)的對(duì)抗局部極值的能力和更高的尋優(yōu)精度。同時(shí)隨著問(wèn)題規(guī)模的增大，各算法求解的穩(wěn)定性也會(huì)下降，LPHLO的標(biāo)準(zhǔn)差除了在KP1.200、KP1.400、KP2.1000這三個(gè)實(shí)例上略遜于SHLO或ASLHO外，在其余17個(gè)實(shí)例上始終表現(xiàn)最好，驗(yàn)證了算法的魯棒性和求解的穩(wěn)定性。

表1 單約束背包問(wèn)題的結(jié)果對(duì)比Tab. 1 Comparison of results on 0-1KPs

3.2 多約束背包問(wèn)題仿真實(shí)驗(yàn)

為了評(píng)估LPHLO在MKP實(shí)例上的性能，使用OR-Library的MKP基準(zhǔn)進(jìn)行測(cè)試。前15個(gè)算例使用測(cè)試基準(zhǔn)mknapcbl（5.100），它有5個(gè)約束和100個(gè)物品，后15個(gè)算例使用測(cè)試基準(zhǔn)mknapcb4（10.100），它有10個(gè)約束和100個(gè)物品。為了保證算法對(duì)比的公平性，實(shí)驗(yàn)采用每種算法對(duì)目標(biāo)函數(shù)計(jì)算50 000次。對(duì)30個(gè)算例的測(cè)試結(jié)果如表2所示，其中第1列表示問(wèn)題類型，如5.100.00代表mknapcbl（5.100）中的第1個(gè)算例，第2列表示OR-Library中的最優(yōu)解。

由表2的實(shí)驗(yàn)結(jié)果可知，LPHLO在所有實(shí)例上都能得到比ASHLO、SHLO、GA、BPSO、BBA這五種算法更好的結(jié)果，并且在每個(gè)實(shí)例上都能找到目前已知最優(yōu)解，表現(xiàn)出較優(yōu)的解決多約束背包問(wèn)題的能力。

表1和表2驗(yàn)證了LPHLO具有較優(yōu)的收斂精度，為了進(jìn)一步驗(yàn)證LPHLO的收斂速度，圖1給出了部分背包問(wèn)題的迭代收斂曲線。所有這些曲線都顯示了在一個(gè)獨(dú)立測(cè)試中發(fā)現(xiàn)最佳值的變化過(guò)程，并且每個(gè)圖中使用的測(cè)試是在30個(gè)獨(dú)立測(cè)試中達(dá)到最佳值的測(cè)試。為了更清晰地對(duì)比6種算法，圖1中的適應(yīng)度函數(shù)值經(jīng)過(guò)了指數(shù)形式處理得到。

觀察圖1可以發(fā)現(xiàn)，LPHLO在6個(gè)不同的背包實(shí)例上都能以最少的迭代次數(shù)收斂到目前最好的解。因?yàn)樾〗M學(xué)習(xí)算子增加了種群信息交流的深度，動(dòng)態(tài)調(diào)參策略提高了種群的信息交流速度，所以個(gè)體能更高效地進(jìn)行學(xué)習(xí)，使LPHLO在尋優(yōu)過(guò)程中能夠更快地收斂。

表2 多約束背包問(wèn)題的結(jié)果對(duì)比Tab. 2 Comparison of results on MKPs

為了進(jìn)一步檢驗(yàn)兩組實(shí)驗(yàn)中不同方法準(zhǔn)確性差異的顯著性，對(duì)6種算法在50個(gè)背包實(shí)例上的測(cè)試結(jié)果進(jìn)行Freidman統(tǒng)計(jì)檢驗(yàn)，結(jié)果如圖2所示，其中每個(gè)算法原點(diǎn)為其平均序值，線段為臨界閾值的大小，若兩種算法有交集，則說(shuō)明沒(méi)有顯著差異，否則有顯著差異。統(tǒng)計(jì)檢驗(yàn)表明，LPHLO在Friedman檢驗(yàn)中排名第一，和50個(gè)已知最優(yōu)值一樣。BBA、BPSO、GA、SHLO、ASHLO這五種算法得到的解和已知最優(yōu)值之間存在顯著差異，而LPHLO的結(jié)果和目前已知最優(yōu)結(jié)果之間的差異不具有統(tǒng)計(jì)學(xué)意義，直觀地表明了LPHLO優(yōu)于BBA、BPSO、GA、SHLO、ASHLO這五種算法，且給出了目前已知最優(yōu)的結(jié)果。

表1～2以及圖1～2的結(jié)果表明，本文提出的LPHLO具有較高的尋優(yōu)精度、較快的收斂速度以及解決實(shí)際問(wèn)題的可靠性等優(yōu)勢(shì)，這得益于人類學(xué)習(xí)優(yōu)化算法和學(xué)習(xí)心理學(xué)理論的結(jié)合。從學(xué)習(xí)心理學(xué)角度分析人類學(xué)習(xí)優(yōu)化算法，結(jié)合小組學(xué)習(xí)理論引入小組學(xué)習(xí)算子，使個(gè)體和群體之間的信息得到了充分的交流，提升了學(xué)習(xí)的效果，提高了算法的求解精度；結(jié)合記憶編碼理論引入動(dòng)態(tài)調(diào)參策略，增加了學(xué)習(xí)的靈活性，使算法更易跳出局部最優(yōu)，提高了算法的尋優(yōu)效率。小組學(xué)習(xí)算子和動(dòng)態(tài)調(diào)參策略的配合使用，使算法的尋優(yōu)精度和收斂速度得到同步提升，提高了算法的魯棒性以及解決實(shí)際問(wèn)題的能力。

圖1 部分背包問(wèn)題的最優(yōu)值收斂曲線Fig. 1 Optimal value convergence curves of partial knapsack problems

圖2 六種算法的Friedman檢驗(yàn)結(jié)果Fig. 2 Friedman test results of six algorithms

4 結(jié)語(yǔ)

針對(duì)人類學(xué)習(xí)優(yōu)化算法尋優(yōu)精度不高、收斂較慢的問(wèn)題，本文提出了融合學(xué)習(xí)心理學(xué)的人類學(xué)習(xí)優(yōu)化算法，結(jié)合學(xué)習(xí)心理學(xué)理論對(duì)人類學(xué)習(xí)優(yōu)化算法進(jìn)行改進(jìn)。從學(xué)習(xí)心理學(xué)角度分析，所提算法通過(guò)提升人類學(xué)習(xí)效果來(lái)提高算法性能。結(jié)合小組學(xué)習(xí)理論提出了小組學(xué)習(xí)策略，然后結(jié)合記憶編碼理論提出了動(dòng)態(tài)學(xué)習(xí)策略，并在算法中引入了與兩種學(xué)習(xí)策略相對(duì)應(yīng)的小組學(xué)習(xí)算子和動(dòng)態(tài)調(diào)參策略，提高了算法的收斂速度和尋優(yōu)精度，增強(qiáng)了算法解決實(shí)際問(wèn)題的能力。將提出的LPHLO應(yīng)用于求解經(jīng)典的NP問(wèn)題——背包問(wèn)題，實(shí)驗(yàn)結(jié)果驗(yàn)證了LPHLO的可行性和有效性。下一步的工作是將LPHLO應(yīng)用到其他類型的組合優(yōu)化問(wèn)題中，如應(yīng)急選址問(wèn)題等。

[1] WANG L， NI H Q， YANG R X， et al. A simple human learning optimization algorithm ［C］// Proceedings of the 2014 International Conference on Intelligent Computing for Sustainable Energy and Environment and the 2014 International Conference of Life System Modeling and Simulation， CCIS 462. Berlin： Springer， 2014：56-65.

[2] LIEPINS G E， HILLIARD M R. Genetic algorithms： foundations and applications ［J］. Annals of Operations Research， 1989， 21（1）： 31-57.

[3] ALIGULIYEV R， ALIGULIYEV R， ISAZADE N. A sentence selection model and HLO algorithm for extractive text summarization ［C］// Proceedings of the 2016 IEEE 10th International Conference on Application of Information and Communication Technologies. Piscataway： IEEE， 2016： 1-4.

[4] 張旭，郭東恩.基于DCT與自適應(yīng)人類學(xué)習(xí)優(yōu)化算法的圖像匹配算法［J］.電子測(cè)量與儀器學(xué)報(bào)，2018，32（6）：148-154.（ZHANG X， GUO D E. Image matching approach based on DCT and adaptive human learning optimization algorithm ［J］. Journal of Electronic Measurement and Instrumentation， 2018， 32（6）： 148-154.）

[5] 張安發(fā)，張瑋，童鑫，等.基于人類學(xué)習(xí)優(yōu)化算法的變論域模糊PID控制研究［J］.工業(yè)控制計(jì)算機(jī)，2017，30（7）：45-47.（ZHANG A F，ZHANG W， TONG X， et al. Variable universe fuzzy-PID control based on human learning optimization algorithm ［J］. Industrial Control Computer， 2017， 30（7）： 45-47.）

[6] WANG L， YANG R X， NI H Q， et al. A human learning optimization algorithm and its application to multi-dimensional knapsack problems ［J］. Applied Soft Computing， 2015， 34： 736-743.

[7] WANG L， NI H Q， YANG R X， et al. An adaptive simplified human learning optimization algorithm ［J］. Information Sciences， 2015， 320： 126-139.

[8] WANG L， AN L， PI J X， et al. A diverse human learning optimization algorithm ［J］. Journal of Global Optimization， 2017， 67（1/2）： 283-323.

[9] WANG L， PEI J， MENHAS M I， et al. A Hybrid-coded Human Learning Optimization for mixed-variable optimization problems ［J］. Knowledge-Based Systems， 2017， 127： 114-125.

[10] BURGESS A， VAN DIGGELE C， ROBERTS C， et al. Team-based learning： design， facilitation and participation ［J］. BMC Medical Education， 2020， 20（S2）： Article No.461.

[11] EGUCHI H， SAKIYAMA H， NARUSE H， et al. Introduction of team-based learning improves understanding of glucose metabolism in biochemistry among undergraduate students ［J］. Biochemistry and Molecular Biology Education， 2021， 49（3）： 383-391.

[12] CRAIK F I M， SALTHOUSE T A. The Handbook of Aging and Cognition ［M］. 3rd ed. New York： Psychology Press， 2008： 445-484.

[13] 陳楨，鐘一文，林娟.求解0-1背包問(wèn)題的混合貪婪遺傳算法［J］.計(jì)算機(jī)應(yīng)用，2021，41（1）：87-94.（CHEN Z， ZHONG Y W， LIN J. Hybrid greedy genetic algorithm for solving 0-1 knapsack problem ［J］. Journal of Computer Applications， 2021， 41（1）： 87-94.）

[14] ZOU D X， GAO L Q， LI S， et al. Solving 0-1 knapsack problem by a novel global harmony search algorithm ［J］. Applied Soft Computing， 2011， 11（2）： 1556-1564.

[15] EL-MALEH A H， SHEIKH A T， SAIT S M. Binary Particle Swarm Optimization （BPSO） based state assignment for area minimization of sequential circuits ［J］. Applied Soft Computing， 2013， 13（12）： 4832-4840.

[16] MIRJALILI S， MIRJALILI S M， YANG X S. Binary bat algorithm ［J］. Neural Computing and Applications， 2014， 25（3/4）： 663-681.

Human learning optimization algorithm based on learning psychology

MENG Han*， MA Liang， LIU Yong

（Business School，University of Shanghai for Science and Technology，Shanghai200093，China）

Aiming at the problems of low optimization accuracy and slow convergence of Simple Human Learning Optimization （SHLO）algorithm， a new Human Learning Optimization algorithm based on Learning Psychology （LPHLO） was proposed. Firstly， based on Team-Based Learning （TBL） theory in learning psychology， the TBL operator was introduced， so that on the basis of individual experience and social experience， team experience was added to control individual learning state to avoid the premature convergence of algorithm. Then， the memory coding theory was combined to propose the dynamic parameter adjustment strategy， thereby effectively integrating the individual information， social information and team information. And the abilities of the algorithm to explore locally and develop globally were better balanced. Two examples of knapsack problem of typical combinatorial optimization problems， 0-1 knapsack problem and multi-constraint knapsack problem， were selected for simulation experiments. Experimental results show that， compared with the algorithms such as SHLO algorithm， Genetic Algorithm （GA） and Binary Particle Swarm Optimization （BPSO） algorithm， the proposed LPHLO has more advantages in optimization accuracy and convergence speed， and has a better ability to solve the practical problems.

Simple Human Learning Optimization (SHLO) algorithm; learning psychology; learning strategy; Team-Based Learning (TBL) operator; dynamic parameter adjustment strategy

TP273

A

1001-9081（2022）05-1367-08

10.11772/j.issn.1001-9081.2021030505

2021?04?02；

2021?06?01；

2021?06?02。

上海市“科技創(chuàng)新行動(dòng)計(jì)劃”軟科學(xué)研究重點(diǎn)項(xiàng)目（18692110500）；上海市哲學(xué)社會(huì)科學(xué)規(guī)劃項(xiàng)目（2019BGL014）；上海市高原科學(xué)建設(shè)項(xiàng)目（第2期）；上海理工大學(xué)科技發(fā)展項(xiàng)目（2020KJFZ040）。

孟晗（1996—），女，河南漯河人，碩士研究生，主要研究方向：系統(tǒng)工程、智能優(yōu)化； 馬良（1964—），男，上海人，教授，博士，主要研究方向：管理科學(xué)與工程、系統(tǒng)工程； 劉勇（1982—），男，江蘇金湖人，副教授，博士，主要研究方向：智能優(yōu)化、服務(wù)網(wǎng)絡(luò)設(shè)計(jì)與優(yōu)化、系統(tǒng)工程。

This work is partially supported by Key Soft Science Research Project of Shanghai “Scientific and Technological Innovation Action Plan” （18692110500），Shanghai Philosophy and Social Science Planning Project （2019BGL014）， Shanghai Plateau Science Construction Project （Phase 2），Science and Technology Development Project of University of Shanghai for Science and Technology （2020KJFZ040）.

MENG Han， born in 1996， M. S. candidate. Her research interests include system engineering， intelligent optimization.

MA Liang， born in 1964， Ph. D.， professor. His research interests include management science and engineering， system engineering.

LIU Yong， born in 1982， Ph. D.， associate professor. His research interests include intelligent optimization， service network design and optimization， system engineering.