基于配對機制的人類學習優(yōu)化算法研究*

曹倬銘，王文國

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

0 引 言

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

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

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

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

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

1.1 初始化種群

HLO中采用二進制編碼框架，因此一個個體由二進制串表示：

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

1.2 隨機學習

開始學習時，人們由于沒有先驗問題知識，通常進行隨機學習。又因為人類存在遺忘特性，所以不能完全復制以前的經(jīng)驗。工作時，首先以一定的隨機性進行學習，公式如下：

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

1.3 個體學習

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

當HLO進行個體學習時，它將根據(jù)IKD的知識產(chǎn)生新的解決方案，方程如下：

1.4 社會學習

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

社會學習中，HLO使用如式（6）進行學習：

綜上所述，HLO學習過程可以表示為：

其中，pr是隨機學習的概率，pi-pr和1-pi的值分別表示執(zhí)行個體學習和社會學習的概率。

2 基于配對機制的HLO算法

2.1 配對學習

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

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

當PHLO進行配對學習時，它將根據(jù)PKD的知識產(chǎn)生新的解決方案，方程如下：

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

其中，pr是隨機學習的概率，pp-pr和pi-pp的值分別表示執(zhí)行個體學習和配對學習的概率，1-pi表示執(zhí)行社會學習的概率。

2.2 流程圖

改進算法PHLO的流程圖，如圖1所示。

圖1 PHLO程序流程

3 測試和分析

為了檢驗HLO增加配對學習機制后（即PHLO）的效果，采用0-1背包問題作為測試基準，分別將PHLO、HLO以及模擬退火算法SA進行對比。

各自進行237次迭代，輸入物品重量為：

物品價值為：

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

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

4 結(jié) 語

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

[1] 劉洋,王文國.差異化密集蟻群算法與網(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.