采用分等级学习策略的二进制粒子群优化算法∗

戴海容 李浩君 张鹏威

（1.浙江金融职业学院工商管理学院 杭州 310018）（2.浙江工业大学教育科学与技术学院 杭州 310023）

1 引言

Kennedy和Eberhart最先提出了基本的粒子群优化算法［1］，基本粒子群优化算法被广泛应用于具有连续性质的问题；为了解决实际生活中众多离散型问题，Kennedy和Eberhart于1997年提出二进制版本的粒子群优化算法［2］（Binary Particle Swarm Optimization，BPSO）。但是二进制粒子群优化算法在寻优后期同样存在易陷入局部最优、多样性丢失现象，导致收敛精度低的问题。相关学者从参数优化［3～4］、种群优化［5～6］、混合优化［7～8］、变异算子［9～10］、速度更新［11］和映射函数［12～13］等多个角度对粒子群优化算法进行了改进，以提高算法的收敛性能和多样性能。上述方法在一定程度上提升了BPSO算法的精度和多样性，但是并不能从本质上解决精度与多样性的矛盾问题；其中多种群优化角度还存在粒子数量多、计算量大的问题。因此，二进制BPSO算法的收敛性能还有较大优化空间。

本文借鉴鸡群算法中的等级制度，提出采用分等级学习策略的二进制粒子群算法（HLBPSO）。HLBPSO算法根据适应度值将粒子分为三个等级，对每个等级粒子采取针对性的学习策略，实现算法性能提升；受变异算子能够增加种群多样性［9］的启发，进一步提出逃逸算子用于劣势粒子逃出所处区域，使劣势等级粒子有能力朝着最优解探索；最后根据当前粒子与最优等级粒子之间距离的差分向量实现惯性权重自适应更新，提升算法精度，增强解的多样性。

2 基本二进制粒子群算法

2.1 基本的BPSO算法

BPSO算法中的粒子速度更新方式与基本PSO相同；在粒子位置更新方式上，BPSO算法中设计了一种映射函数，用于将粒子速度值映射为粒子位置变换为1的概率。式（1）为BPSO中粒子速度更新公式，式（2）为BPSO算法中用到的映射函数，式（3）为粒子位置更新公式。

其中，vij(t +1)为粒子在t+1次迭代时的速度值，i表示的是当前粒子，j表示的是维度；ω为惯性权重；c1表示粒子向自身学习的比重，c2表示粒子向社会学习的比重；xij(t)表示粒子i的当前位置；T(vij(t))表示速度映射的概率值。

2.2 基本的鸡群优化算法

鸡群算法［14］（Chicken Swarm Optimization Algo⁃rithm，CSO）于2014年被提出，是通过对鸡群寻找食物过程的模拟而设计的一种优化算法。目前，已出现对鸡群算法众多不同的优化策略，并成功应用到了问题求解当中［15～16］。鸡群算法中每只鸡作为求解问题的一个可能解，根据每只鸡的适应度值将整个种群划分为若干个子群，并分为公鸡、母鸡和小鸡三类；其中每个子群中只存在一只公鸡，而母鸡和小鸡有若干个，它们只在自身所处的群体中寻找食物，公鸡是最靠近食物源的一类。在觅食过程中，通过向自身已有经验和群体中公鸡经验不断地学习实现自己的位置更新。在迭代过程中，每隔一定次数后重新按其目标函数值排序划分其等级。

3 采用分等级学习策略的二进制粒子群优化算法（HLBPSO）

采用分等级学习策略的二进制粒子群优化算法（HLBPSO）借鉴鸡群算法中的等级制度，根据适应度值把种群中适应度值较好的前2/10粒子设置为优势等级粒子，适应度值较差的后3/10粒子设置为劣势等级粒子，其他5/10为中间等级粒子。优势等级粒子采取探索学习模式，旨在探索新的未知空间，寻求最佳解；中间等级粒子采取全局学习模式，向优势等级最优粒子学习；劣势粒子采取混合学习模式，向优势等级最优粒子与中间等级最优粒子的差分向量进行学习，而且赋予粒子逃逸所处区域的能力。三种学习模式中的惯性权重根据当前粒子与优势等级最优粒子间的距离实现动态更新。

3.1 分等级学习策略

在鸡群算法中，公鸡向更加广阔的未知空间探索；母鸡向所在子群公鸡学习的同时，也向随机挑选的公鸡或母鸡学习；小鸡向所在子群的母鸡学习。参考鸡群算法中的学习机制，对其优化，最后确定HLBPSO算法的学习机制如下：

1）优势等级粒子采用探索学习模式，探索学习模式下的优势等级粒子受自身惯性驱使的同时，向更广泛的未知空间学习，探索新解。公式如下：

2）中间等级粒子采用全局学习模式；中间等级粒子向优势等级最优粒子学习。gbestij表示优势等级中的最优粒子，也是整个群体中的全局最优粒子。

3）劣势等级粒子采用混合学习模式。劣势等级粒子向优势等级最优粒子与中间等级最优粒子的差分向量进行学习；与此同时，由于劣势粒子离全局最优粒子较远，因此设计逃逸算子，使劣势粒子以一定概率发生变异以达到提升算法寻优精度、增强种群多样性的目的。式（6）中zbestij表示中间等级的最优粒子，ES表示逃逸算子。

3.2 逃逸算子设计

为了使算法避免陷入局部最优，增加解的多样性，为劣势等级粒子设计逃逸算子ES。劣势等级粒子离全局最优解距离较远，通过设置逃逸算子，在一定程度上让劣势粒子逃离自身所处区域，增加向全局最优解靠近的概率。逃逸算子如式（7）。

式中，t表示的是当前迭代次数，T表示最大迭代次数，rand表示的是（0，1）之间的随机值，c3=0.01。

3.3 粒子位置更新

文献［13］提出了弧形映射函数，并通过实验表明了弧形比S型和V型具有更好性能。因此，HLB⁃PSO算法采用弧形映射函数将粒子的速度值映射为位置改变的概率，位置更新则使用非强制性位置更新程序。如式（8）、（9）所示：

3.4 自适应惯性权重设计

惯性权重ω采用动态非线性策略进行更新，具体地，根据当前粒子与优势等级中最优粒子间的欧式距离设计惯性权重调整策略。粒子间的欧式距离用表示，如式（10）所示；值较大时表明当前粒子i离全局最优粒子的距离较远，需要将ω值增大，增强全局探索能力；相反，则减小ω值，提高局部开采能力；本文设计的惯性权重自适应更新方案如式（11）。

3.5 算法步骤

HLBPSO算法步骤如下：

1）对HLBPSO算法中的种群进行初始化；

2）如果迭代次数小于等于1，则采用式（1）实现粒子速度更新，并利用式（9）实现粒子位置更新，之后执行步骤7）；否则，执行步骤3）；

3）在迭代过程中根据粒子的适应度值将粒子种群划分为不同的三个等级；

4）基于当前粒子与优势等级最优粒子间的距离对惯性权重值进行自适应动态更新；

5）优势等级粒子采用式（4）对粒子速度进行更新；中间等级粒子采用式（5）对粒子速度进行更新；劣势粒子采用式（6）对粒子速度进行更新；

6）采用式（9）对粒子位置进行更新；

7）计算粒子适应度值；

8）判断是否达到终止条件；如果达到，则执行步骤9）；如果否，则返回步骤3）；

9）输出结果，算法结束。

4 仿真实验分析

4.1 实验设置

通过基准测试函数验证算法的收敛性能是常用的验证方法。本文通过将所提HLBPSO算法在6个测试函数上与三个对比算法进行对比来分析算法的收敛性能。测试函数选择经典的Sphere函数（F1）、Step函数（F2）、Rosenbrock函数（F3）、Rastri⁃gin函数（F4）、Ackley函数（F5）、Griewangk函数（F6），其中，F1、F2、F3为单峰函数，F4、F5、F6为多峰函数。用到的6个基准测试函数如表1所示。

表1 基准测试函数

在对比算法选择上，本文除了选择基本的二进制粒子群优化算法BPSO［2］外，选择最新提出的、效率较高的CBPSO算法［4］作对比；鉴于HLBPSO算法采用了文献［13］中的弧形映射函数，所以也将文献［13］中提出的ABPSO算法作为对比算法。各算法实验参数设置如下：ω初始值为2，ωmax=0.9，ωmin=0.4；c1=c2=2；本文所提HLBPSO算法中c3=0.01；vmax=6。

实验从收敛精度、成功率和收敛速度三个角度实现算法的对比。

收敛精度：由四个算法单独运行30次获得的平均值数据衡量；

成功率：算法收敛至指定精度的次数与运行总次数之比乘以百分比。在实际问题中，指定精度可以根据所求问题由多次实验确定，或者由有经验的专家确定。本文中指定精度由以下公式计算：

公式中AC表示指定精度，H表示算法个数，Ave表示各个算法得到的30次均值。

收敛速度：由四个算法的寻优过程衡量；

实验环境为windows7操作系统，在Matlab中进行各个算法的编码。硬件环境为intel酷睿处理器i5-4570，主频为3.20GHz，内存为4GB。

4.2 实验分析

由于智能优化算法在运行中存在着随机性，为了减少这种现象对实验结果的影响，将算法在6个测试函数上分别运行30次求取均值获得实验数据。如表2～表7所示，表2～表7展示了基本的BP⁃SO算法、最新提出的ABPSO、CBPSO算法和本文所提HLBPSO算法在不同维度、不同种群规模和不同迭代次数下的实验数据。D表示维度，分别设置50维、150维、300维；N表示种群数量，分别设置30、40、50；T表示最大迭代次数，分别设置 100、300、500。通过不同维度、不同种群规模和不同迭代次数的实验设置，充分验证了HLBPSO算法的收敛性能和鲁棒性。

表2 算法在函数F1上的实验结果

表3 算法在函数F2上的实验结果

表4 算法在函数F3上的实验结果

表5 算法在函数F4上的实验结果

表6 算法在函数F5上的实验结果

4.2.1 收敛精度与成功率分析

从表2～表4中的实验数据可以看出，在单峰函数F1、F2上，HLBPSO算法在不同维度、不同规模上具有最好的均值、方差和成功率，说明收敛性能优于对比算法；CBPSO算法虽然在成功率上与HLBPSO算法相同，但均值差于HLBPSO算法；AB⁃PSO算法在三个维度的均值和成功率上优于基本的BPSO，但在维度为150和300时，方差不如基本的BPSO；BPSO算法在三个维度上的收敛性能最差。在单峰函数F3上，CBPSO算法所获均值最小，收敛精度最高，并在维度为50、150时找到了函数的极小值；HLBPSO算法在均值和成功率上优于ABPSO算法和BPSO算法；BPSO算法的性能最差。在三个单峰函数上，HLBPSO算法展现了较好的收敛性能。

从表5～表7中的数据可以看出，在多峰函数F4、F5、F6上，HLBPSO算法在三个维度上所获的30次均值都是最小的，这表明寻优精度是最高的，而且成功率也高于对比算法，表现出了较好性能。特别是对于多峰函数F6，当维度在150、300时，HLBPSO算法找到了极小值。CBPSO算法在三个多峰函数上的表现仅次于HLBPSO算法，优于BP⁃SO和ABPSO算法；BPSO算法的寻优效果不如AB⁃PSO算法。在F4、F5和F6三个多峰函数上，HLBP⁃SO展现出了比对比算法更好的寻优性能，有着较高的收敛精度和成功率。

4.2.2 收敛速度分析

图1～图6是四个算法在函数为300维时的寻优过程，除了在测试函数F3上HLBPSO算法的收敛性能不如CBPSO算法，在其他五个函数上，HLB⁃PSO算法都展现出比其他算法更佳的收敛速度和收敛精度。HLBPSO算法能够以最少的寻优代数找到最佳的解，这是由于HLBPSO算法采用了分等级学习策略，不同等级粒子采取合适的学习策略，使得算法在收敛初期具有较快的收敛性能；当HLBPSO算法陷入局部最优的时候，在逃逸算子和惯性权重自适应更新策略的帮助下，使得算法跳出局部最优，增加解的多样性，粒子继续寻找更优解。

图1 F1函数收敛曲线

图2 F2函数收敛曲线

图3 F3函数收敛曲线

图4 F4函数收敛曲线

图5 F5函数收敛曲线

图6 F6函数收敛曲线

5 结语

针对二进制粒子群存在收敛精度低、寻优后期多样性丢失的问题，本文提出了采用分等级学习策略的HLBPSO算法。该算法针对不同等级粒子采用了不同的学习策略，并为劣势等级粒子设计逃逸算子，最后根据当前粒子与优势等级最优粒子间的欧式距离设计了惯性权重动态更新策略。实验表明，本文所提HLBPSO算法具有较高的收敛精度和较好的鲁棒性，分等级学习策略和惯性权重动态更新策略提升了算法跳出局部最优的能力，在一定程度上增加了解的多样性。