基于配對(duì)機(jī)制的人類學(xué)習(xí)優(yōu)化算法研究*

曹倬銘，王文國(guó)

（曲阜師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 日照 276826）

0 引 言

在過(guò)去幾十年中，針對(duì)各種優(yōu)化問(wèn)題已經(jīng)開(kāi)發(fā)了大量的優(yōu)化算法。大多數(shù)算法是以線性或非線性規(guī)劃為基礎(chǔ)，雖然這些數(shù)值優(yōu)化算法在一些簡(jiǎn)單理想模型中能夠提供合適的方案以尋找到全局最優(yōu)解，但是有許多復(fù)雜的、大規(guī)模的現(xiàn)實(shí)問(wèn)題僅通過(guò)使用這些算法很難解決?，F(xiàn)有基于導(dǎo)數(shù)的數(shù)值方法的計(jì)算缺陷（如初始值的敏感性和所需的大量枚舉記憶等），迫使人們研究元啟發(fā)式算法，如遺傳算法、蟻群算法、粒子群優(yōu)化算法、模擬退火算法等，以解決復(fù)雜的優(yōu)化問(wèn)題[1]。

群體智能算法是以生物系統(tǒng)為基礎(chǔ)的強(qiáng)大元啟發(fā)式優(yōu)化方法，但很多經(jīng)典算法都是針對(duì)低等生物如螞蟻、果蠅等的活動(dòng)而提出，而針對(duì)人類活動(dòng)特點(diǎn)的研究卻寥寥無(wú)幾。眾所周知，人類是地球上最聰明的生物，人類強(qiáng)大的學(xué)習(xí)能力使我們能夠解決大量其他生物如鳥、螞蟻、螢火蟲等所不能應(yīng)對(duì)的復(fù)雜問(wèn)題，而許多人類學(xué)習(xí)活動(dòng)與元啟發(fā)式搜索過(guò)程相似。例如，當(dāng)一個(gè)人在學(xué)習(xí)一項(xiàng)新技能時(shí)，在無(wú)任何先驗(yàn)知識(shí)的情況下，首先進(jìn)行自我探索，無(wú)方向隨機(jī)掌握技能。當(dāng)有一定先驗(yàn)知識(shí)后，便可進(jìn)行個(gè)人學(xué)習(xí)進(jìn)行有針對(duì)性的探索。而當(dāng)社會(huì)中很多成員都在學(xué)習(xí)該項(xiàng)技能時(shí)，便能根據(jù)社會(huì)經(jīng)驗(yàn)交流加速掌握這項(xiàng)新技能。王靈等人依據(jù)人類學(xué)習(xí)過(guò)程提出了一種簡(jiǎn)單的人類學(xué)習(xí)優(yōu)化算法（Human Learning Optimization，HLO），并通過(guò)0-1背包問(wèn)題初步驗(yàn)證了其有效性[2-4]。

受到人類社會(huì)婚配現(xiàn)象的啟發(fā)，本文將在HLO基礎(chǔ)上進(jìn)一步改進(jìn)，首次提出一種基于配對(duì)機(jī)制的人類學(xué)習(xí)優(yōu)化算法（PHLO），以期獲得更好的收斂速度和尋優(yōu)精度。

1 基本人類學(xué)習(xí)優(yōu)化算法（HLO）

在HLO中，有三個(gè)學(xué)習(xí)運(yùn)算符，即隨機(jī)學(xué)習(xí)運(yùn)算符、個(gè)體學(xué)習(xí)運(yùn)算符和社會(huì)學(xué)習(xí)運(yùn)算符，用于產(chǎn)生新的候選解以求最優(yōu)化。它的工作過(guò)程主要模擬人類的學(xué)習(xí)過(guò)程。

1.1 初始化種群

HLO中采用二進(jìn)制編碼框架，因此一個(gè)個(gè)體由二進(jìn)制串表示：

hi是第i個(gè)個(gè)體，N是群體大小，M是解的維度。二進(jìn)制字符串的每一位被隨機(jī)初始化為“0”或“1”。

1.2 隨機(jī)學(xué)習(xí)

開(kāi)始學(xué)習(xí)時(shí)，人們由于沒(méi)有先驗(yàn)問(wèn)題知識(shí)，通常進(jìn)行隨機(jī)學(xué)習(xí)。又因?yàn)槿祟惔嬖谶z忘特性，所以不能完全復(fù)制以前的經(jīng)驗(yàn)。工作時(shí)，首先以一定的隨機(jī)性進(jìn)行學(xué)習(xí)，公式如下：

其中Rand(0,1)是0和1之間的隨機(jī)數(shù)。

1.3 個(gè)體學(xué)習(xí)

個(gè)體學(xué)習(xí)是個(gè)人通過(guò)反思外部刺激來(lái)構(gòu)建知識(shí)的能力。學(xué)習(xí)過(guò)程中，人類通常運(yùn)用自己的經(jīng)驗(yàn)和知識(shí)來(lái)避免錯(cuò)誤，以提高學(xué)習(xí)效率。在HLO中，用IKD來(lái)儲(chǔ)存?zhèn)€體學(xué)習(xí)經(jīng)驗(yàn)，稱為個(gè)體學(xué)習(xí)經(jīng)驗(yàn)知識(shí)庫(kù)，方程如下：

當(dāng)HLO進(jìn)行個(gè)體學(xué)習(xí)時(shí)，它將根據(jù)IKD的知識(shí)產(chǎn)生新的解決方案，方程如下：

1.4 社會(huì)學(xué)習(xí)

當(dāng)問(wèn)題復(fù)雜時(shí)，隨機(jī)學(xué)習(xí)和個(gè)體學(xué)習(xí)會(huì)非常緩慢，效率低下。社會(huì)環(huán)境中，人們可以通過(guò)社會(huì)交流從集體經(jīng)驗(yàn)中學(xué)習(xí)，進(jìn)一步發(fā)展自己的能力。設(shè)社會(huì)學(xué)習(xí)經(jīng)驗(yàn)知識(shí)庫(kù)為SKD，定義如下：

社會(huì)學(xué)習(xí)中，HLO使用如式（6）進(jìn)行學(xué)習(xí)：

綜上所述，HLO學(xué)習(xí)過(guò)程可以表示為：

其中，pr是隨機(jī)學(xué)習(xí)的概率，pi-pr和1-pi的值分別表示執(zhí)行個(gè)體學(xué)習(xí)和社會(huì)學(xué)習(xí)的概率。

2 基于配對(duì)機(jī)制的HLO算法

2.1 配對(duì)學(xué)習(xí)

人類學(xué)習(xí)過(guò)程中，個(gè)體學(xué)習(xí)往往因?yàn)閭€(gè)體學(xué)習(xí)經(jīng)驗(yàn)知識(shí)庫(kù)（IKD）的限制，工作效率低下，而社會(huì)學(xué)習(xí)過(guò)程往往比較繁瑣。為了提高學(xué)習(xí)效率，在基本人類學(xué)習(xí)優(yōu)化算法（HLO）的基礎(chǔ)上，增加一個(gè)配對(duì)學(xué)習(xí)運(yùn)算符，即雙人學(xué)習(xí)過(guò)程。它對(duì)應(yīng)的配對(duì)學(xué)習(xí)經(jīng)驗(yàn)知識(shí)庫(kù)（PKD）的定義為：

其中，L是保存在PKD中的預(yù)定數(shù)量的解決方案，pkdip表示配對(duì)學(xué)習(xí)最優(yōu)值。

當(dāng)PHLO進(jìn)行配對(duì)學(xué)習(xí)時(shí)，它將根據(jù)PKD的知識(shí)產(chǎn)生新的解決方案，方程如下：

這樣，PHLO算法就可以表示為：

其中，pr是隨機(jī)學(xué)習(xí)的概率，pp-pr和pi-pp的值分別表示執(zhí)行個(gè)體學(xué)習(xí)和配對(duì)學(xué)習(xí)的概率，1-pi表示執(zhí)行社會(huì)學(xué)習(xí)的概率。

2.2 流程圖

改進(jìn)算法PHLO的流程圖，如圖1所示。

圖1 PHLO程序流程

3 測(cè)試和分析

為了檢驗(yàn)HLO增加配對(duì)學(xué)習(xí)機(jī)制后（即PHLO）的效果，采用0-1背包問(wèn)題作為測(cè)試基準(zhǔn)，分別將PHLO、HLO以及模擬退火算法SA進(jìn)行對(duì)比。

各自進(jìn)行237次迭代，輸入物品重量為：

物品價(jià)值為：

背包總?cè)萘繛?00。

以上三種算法針對(duì)0-1背包問(wèn)題的Matlab優(yōu)化結(jié)果，如圖2所示。圖2表明，引入配對(duì)機(jī)制的人類學(xué)習(xí)優(yōu)化算法在解決背包類問(wèn)題時(shí)，可以獲得比傳統(tǒng)HLO、模擬退火算法更快的收斂速度和更精確的優(yōu)化結(jié)果。

4 結(jié) 語(yǔ)

本文在基本人類學(xué)習(xí)優(yōu)化算法的基礎(chǔ)上，首次引入配對(duì)學(xué)習(xí)的概念，以提高算法效率和準(zhǔn)確性。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法能夠大大提升原始算法的尋優(yōu)效果，同時(shí)在收斂速度、算法穩(wěn)定性方面具有明顯優(yōu)勢(shì)。

[1] 劉洋,王文國(guó).差異化密集蟻群算法與網(wǎng)絡(luò)路由選擇[J].通信技術(shù),2015,48(08):949-953.LIU Yang,WANG Wen-guo.Differentiated Dense Ant Colony Algorithm and Network QoS Routing Selection[J].Communications Technology,2015,48(08):949-953.

[2] Wang L,Ni H,Yang R.An Adaptive Simplified Human Learning Optimization Algorithm[J].Information Sciences,2015(320):126-139.

[3] Wang L,Ni H,Yang R,et al.A Simple Human Learning Optimization Algorithm[C].International Conference on Life System Modeling and Simulation and International Conference on Intelligent Computing for Sustainable Energy and Environment,2014:56-65.

[4] Wang L,Yang R,Ni H,et al.A Human Learning Optimization Algorithm and Its Application to Multidimensional Knapsack Problems[J].Applied Soft Computing,2015,34(C):736-743.