基于配对机制的人类学习优化算法研究*

曹倬铭，王文国

（曲阜师范大学 信息科学与工程学院，山东 日照 276826）

0 引 言

在过去几十年中，针对各种优化问题已经开发了大量的优化算法。大多数算法是以线性或非线性规划为基础，虽然这些数值优化算法在一些简单理想模型中能够提供合适的方案以寻找到全局最优解，但是有许多复杂的、大规模的现实问题仅通过使用这些算法很难解决。现有基于导数的数值方法的计算缺陷（如初始值的敏感性和所需的大量枚举记忆等），迫使人们研究元启发式算法，如遗传算法、蚁群算法、粒子群优化算法、模拟退火算法等，以解决复杂的优化问题[1]。

群体智能算法是以生物系统为基础的强大元启发式优化方法，但很多经典算法都是针对低等生物如蚂蚁、果蝇等的活动而提出，而针对人类活动特点的研究却寥寥无几。众所周知，人类是地球上最聪明的生物，人类强大的学习能力使我们能够解决大量其他生物如鸟、蚂蚁、萤火虫等所不能应对的复杂问题，而许多人类学习活动与元启发式搜索过程相似。例如，当一个人在学习一项新技能时，在无任何先验知识的情况下，首先进行自我探索，无方向随机掌握技能。当有一定先验知识后，便可进行个人学习进行有针对性的探索。而当社会中很多成员都在学习该项技能时，便能根据社会经验交流加速掌握这项新技能。王灵等人依据人类学习过程提出了一种简单的人类学习优化算法（Human Learning Optimization，HLO），并通过0-1背包问题初步验证了其有效性[2-4]。

受到人类社会婚配现象的启发，本文将在HLO基础上进一步改进，首次提出一种基于配对机制的人类学习优化算法（PHLO），以期获得更好的收敛速度和寻优精度。

1 基本人类学习优化算法（HLO）

在HLO中，有三个学习运算符，即随机学习运算符、个体学习运算符和社会学习运算符，用于产生新的候选解以求最优化。它的工作过程主要模拟人类的学习过程。

1.1 初始化种群

HLO中采用二进制编码框架，因此一个个体由二进制串表示：

hi是第i个个体，N是群体大小，M是解的维度。二进制字符串的每一位被随机初始化为“0”或“1”。

1.2 随机学习

开始学习时，人们由于没有先验问题知识，通常进行随机学习。又因为人类存在遗忘特性，所以不能完全复制以前的经验。工作时，首先以一定的随机性进行学习，公式如下：

其中Rand(0,1)是0和1之间的随机数。

1.3 个体学习

个体学习是个人通过反思外部刺激来构建知识的能力。学习过程中，人类通常运用自己的经验和知识来避免错误，以提高学习效率。在HLO中，用IKD来储存个体学习经验，称为个体学习经验知识库，方程如下：

当HLO进行个体学习时，它将根据IKD的知识产生新的解决方案，方程如下：

1.4 社会学习

当问题复杂时，随机学习和个体学习会非常缓慢，效率低下。社会环境中，人们可以通过社会交流从集体经验中学习，进一步发展自己的能力。设社会学习经验知识库为SKD，定义如下：

社会学习中，HLO使用如式（6）进行学习：

综上所述，HLO学习过程可以表示为：

其中，pr是随机学习的概率，pi-pr和1-pi的值分别表示执行个体学习和社会学习的概率。

2 基于配对机制的HLO算法

2.1 配对学习

人类学习过程中，个体学习往往因为个体学习经验知识库（IKD）的限制，工作效率低下，而社会学习过程往往比较繁琐。为了提高学习效率，在基本人类学习优化算法（HLO）的基础上，增加一个配对学习运算符，即双人学习过程。它对应的配对学习经验知识库（PKD）的定义为：

其中，L是保存在PKD中的预定数量的解决方案，pkdip表示配对学习最优值。

当PHLO进行配对学习时，它将根据PKD的知识产生新的解决方案，方程如下：

这样，PHLO算法就可以表示为：

其中，pr是随机学习的概率，pp-pr和pi-pp的值分别表示执行个体学习和配对学习的概率，1-pi表示执行社会学习的概率。

2.2 流程图

改进算法PHLO的流程图，如图1所示。

图1 PHLO程序流程

3 测试和分析

为了检验HLO增加配对学习机制后（即PHLO）的效果，采用0-1背包问题作为测试基准，分别将PHLO、HLO以及模拟退火算法SA进行对比。

各自进行237次迭代，输入物品重量为：

物品价值为：

背包总容量为100。

以上三种算法针对0-1背包问题的Matlab优化结果，如图2所示。图2表明，引入配对机制的人类学习优化算法在解决背包类问题时，可以获得比传统HLO、模拟退火算法更快的收敛速度和更精确的优化结果。

4 结 语

本文在基本人类学习优化算法的基础上，首次引入配对学习的概念，以提高算法效率和准确性。实验结果表明，改进后的算法能够大大提升原始算法的寻优效果，同时在收敛速度、算法稳定性方面具有明显优势。

[1] 刘洋,王文国.差异化密集蚁群算法与网络路由选择[J].通信技术,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.