邱飞岳,王京京

(浙江工业大学 教育科学与技术学院，浙江 杭州 310023)

粒子群优化算法是一种模拟鸟群觅食行为的群体智能优化算法[1]，由于粒子群优化算法与其他算法相比具有参数少、实现简单等优点，因此被广泛地应用到了实际的众多优化问题中[2-5]。不论是用于解决连续性质问题的粒子群算法，还是解决离散问题的二进制粒子群算法[6]，二者都涉及到种群的全局与局部两种搜索能力，这两种能力决定了算法的收敛性能。而粒子群算法中的学习因子对算法的全局与局部搜索能力有着重要影响，传统的粒子群算法采用固定学习因子方式，不能随着种群的进化状态实现动态调整。为了缓解粒子群优化算法出现的早熟收敛现象，提升算法的收敛性能，相关学者提出了不同改进策略的粒子群优化算法。受惯性权重随时间变化策略的启发，Wang等[7-8]通过学习因子初始值与迭代次数共同实现学习因子的动态调整，使学习因子随时间的变化而变化；董辉等[9]提出学习因子与寻优代数成反比变化的更新策略；但是只根据寻优代数简单的关系进行学习因子调整，并不能利用种群进化状态精确调整学习因子。赵远东等[10-11]提出学习因子随惯性权重变化而变化的策略，在惯性权重随时间改变时，学习因子发出相应的递减或递增策略，通过惯性权重与学习因子的相互作用实现算法全局与局部搜索能力的平衡。虽然学习因子随着惯性权重的变化能够实现参数调整的灵活性与针对性，但惯性权重主要是对粒子速度产生影响，却不能反映当前种群的整体寻优状态。Jadon等[12]提出自适应学习因子的粒子优化算法，通过当前适应度值与最大适应度值的比值实现学习因子的自适应更新，增强算法跳出局部最优的能力；邵鹏等[13]提出一种学习因子与惯性权重自适应调节算法，该算法将参数x映射到0～1表示算法进度，够确定的最大适应度评估次数时利用迭代次数与全部评估次数计算算法进度，不能确定时利用精度与全局历史最优计算算法进度；利用算法进度优化学习因子提高了算法搜索能力。利用种群进化信息实现对学习因子的自适应调整的研究并不多，特别是在二进制粒子群算法中的研究更少。

上述研究通过不同的策略实现了粒子群算法性能的提升，但粒子群算法的收敛性能依然有着较大的提升空间。笔者提出一种自适应学习因子的混沌二进制粒子群优化算法(SABPSO)。SABPSO算法通过混沌策略提升初始粒子种群的质量，并根据适应度值、当前粒子与最优粒子间距离设计成长因子，用于检测当前粒子的成长状态；最后根据粒子成长状态信息和迭代次数实现学习因子的自适应更新，提升算法收敛精度。通过在4 个经典基准函数上对SABPSO算法性能测试的实验，结果表明：所提算法具有较好的收敛性能，混沌策略和自适应学习因子策略能够提升算法的收敛精度。

1 基本的二进制粒子群优化算法

为了克服传统粒子群算法无法直接应用离散问题的弊端，Kennedy和Eberhart于1997年提出了二进制粒子群优化算法BPSO。BPSO通过修改PSO中的速度和位置更新过程实现了粒子群算法在离散空间的应用。在BPSO中，粒子的位置变化是通过区间[0,1]上的概率值来表示的。粒子速度更新公式、S型映射函数以及粒子位置更新公式分别为

vij(t+1)=wvij(t)+c1r1(pbestij(t)-xij(t))+c2r2(gbestij(t)-xij(t))

(1)

(2)

(3)

式中：t为第t次迭代；i，j取1到N中的整数，N为种群数量；w为惯性权重；c1，c2为学习因子，用来平衡局部最优和全局最优在搜索过程中的影响；r1，r2为0到1之间的随机数；vij(t)为粒子i在第j维上第t次迭代的速度；xij(t)为粒子i在第j维上第t次迭代的位置；S(vij)为xij取1的概率。

2 自适应学习因子的二进制粒子群优化算法

自适应学习因子的二进制粒子群优化算法(SABPSO)将种群的进化过程定义为种群的成长过程。SABPSO算法首先设计粒子成长因子，根据粒子成长因子判断当前种群的成长状态；其次依据粒子当前成长状态自适应调整学习因子，实现全局与局部探索的平衡，提升算法的搜索精度。

2.1 SABPSO算法的速度与位置更新方式

SABPSO算法的粒子速度更新采用基本BPSO算法的速度更新公式，映射函数采用V型映射函数，其计算式为

(4)

粒子位置更新采用VBPSO算法中的非强制性位置更新程序，其计算式为

(5)

2.2 混沌初始化策略

基本二进制粒子群优化算法采用随机策略生成的初始种群质量不高，分布状态不佳，为了提升初始种群质量，SABPSO算法采用混沌策略生成初始种群，其计算式为

Xn+1=μXn(1-Xn)

(6)

式中：μ=4；如果Xn<0.5，则取Xn=0；如果Xn≥0.5，则取Xn=1。

2.3 粒子成长因子

文献[14-16]中表明进化信息对算法寻优性能有着重要影响，合理利用算法的进化信息能够提高算法的收敛性能。因此在设计成长因子更新方式之前，首先提出利用粒子成长因子反映种群的进化状态；在粒子在进化过程中，将粒子的寻优过程定义为粒子的成长过程，通过成长因子探测粒子的成长状态。

成长因子由适应度值、当前粒子与全局最优粒子之间的距离共同决定，粒子的成长因子为

gf=fit+dd=|dc-dg|

(7)

式中：d为当前粒子与全局最优粒子之间的距离；dc为当前粒子；dg为全局最优粒子。在实际编程时，将成长因子转换为0到1之间的值，归一化处理方式为

(8)

2.4 自适应学习因子

学习因子对粒子群算法的全局搜索与局部开采能力有着重要的影响；自我学习因子的大小决定着粒子向自身历史最优学习的程度，社会学习因子决定着粒子向全局最优学习的程度。自我学习因子c1值较大，则粒子更多的向pbest学习，算法的全局搜索能力增加；较小，则全局搜索能力减弱。社会学习因子c2值较大，则粒子更多的向gbest学习，算法的局部开采能力增加；较小，则局部开采能力减弱。合理的c1，c2值能够有效均衡算法的局部与全局搜索能力，实现算法收敛性能的提升。

鉴于学习因子参数对算法性能有着重要影响，设计学习因子自适应更新方式，利用粒子的成长状态和迭代次数共同实现学习因子的自适应调整，使粒子在不同的成长状态下具有不同的学习因子更新方式，提高学习因子优化的针对性。自我学习因子c1更新方式为

(9)

社会学习因子c2更新方式为

(10)

当成长因子gf值小时，说明粒子与最优解距离较远；此时应增加自我学习系数c1值，减小社会学习系数c2值，加强算法的全局探索能力。当成长因子gf值大时，说明粒子与最优解距离较近；此时应增加社会学习系数c2值，减小自我学习系数c1值，加强算法的局部开采能力。因此设计式(9)为递增函数，自我学习系数c1随着成长因子gf的递增而递增，随着gf的递减而递减；设计式(10)为递减函数，社会学习系数c2随着gf的递增而递减，随着gf的递减而递增。

2.5 SABPSO步骤

SABPSO算法采用混沌策略初始化粒子种群，能够有效提高初始种群数量；利用成长因子检测粒子的成长状态，并根据成长状态实现学习因子的自适应更新，能够实现学习因子更新的针对性。采用自适应学习因子更新策略的SABPSO算法步骤如下：

步骤1采用混沌策略初始化SABPSO算法种群。

步骤2利用公式(1)更新粒子速度。

步骤3利用公式(6)更新粒子位置。

步骤4利用成长因子检测粒子成长状态，用公式(7)计算成长因子。

步骤5利用步骤4中的成长因子实现学习因子的自适应更新，用公式(9，10)计算学习因子。

步骤6计算粒子适应度值。

步骤7若达到输出条件，则输出结果；否则，返回步骤2。

步骤8算法结束。

SABPSO算法的伪代码为

1) INPUT：种群规模N，最大迭代次数T，当前迭代次数t，惯性权重w，初始自我学习因子c1，初始社会学习因子c2=2，最大速度值Vmax。

2) OUTPUT：适应度值fitness

3) BEGIN

4) 初始化种群。

5) FORt=1 TOT

6) 计算粒子速度和位置，并更新。

7) 计算粒子适应度值fitness，若当前值优于上一代，则更新fitness。

8) IF当前适应度值优于个体最优

9) 更新个体历史最优pbest。

10) END

11) IF当前适应度值优于全局最优

12) 更新全局最优gbest。

13) END

14) 计算当前粒子与全局最优的距离。

15) 根据式(7)计算粒子成长因子。

16) 根据式(8)进行成长因子的归一化处理。

17) 更新自我学习因子。

18) 更新社会学习因子。

19) END

20) END

3 实验仿真

利用4 个经典的测试函数验证所提SABPSO算法的收敛性能，并分别与3 个采用不同学习因子更新策略的二进制粒子群优化算法进行对比。由于SABPSO算法在初始化时采用了混沌策略，为了保证实验数据能够反映不同学习因子策略的对比情况，在其他3 个对比算法中也加入混沌策略。

3.1 实验设置

测试函数采用2 个经典的单峰函数Sphere，Step和2 个经典的多峰函数Rastrigin，Griewangk对所提SABPSO算法的性能进行测试，测试函数如表1所示。

表1 基准测试函数Table 1 The Benchmark function

对比算法选择3 个与笔者改进角度相同的算法：采用固定学习因子的二进制粒子群优化算法VBPSO[14]；带有权重函数学习因子的二进制粒子群优化算法WFBPSO[10]；动态改变学习因子的二进制粒子群优化算法DFBPSO[17]；其中，WFBPSO算法和DFBPSO算法只采用原始文献中对学习因子改进的策略，其他部分与基本的BPSO算法相同。因此各算法采用策略如表2所示。

表2 各算法策略Table 2 The Algorithmic strategies

实验参数设置：种群数量N分别设置20，40，50，维度分别设置100，300，500 维，对应的最大迭代次数T分布设置为300，500，1 000。在不同种群规模、不同维度和不同迭代次数下观察SABPSO算法的收敛性能，验证SABPSO算法的鲁棒性。惯性权重w=2，惯性权重最大值wmax=0.9，惯性权重最小值wmin=0.4，自我学习因子c1=2，社会学习因子c2=2，最大速度值vmax=6。

实验采用Matlab语言编程，Window 7操作系统，Intel(R) Core(TM) i5-3230M CPU @ 2.60 GHz；4 G内存。

3.2 对比标准

实验采用3 种标准判断算法的收敛性能，即

1) 均值：各对比算法在实验平台上单独运行30 次获得的数据平均值。

2) 方差：各对比算法在实验平台上单独运行30 次获得的数据方差。

3) 分布状态：利用箱须图检验数据的分布状态。

3.3 实验结果分析

表3～6为3 个对比算法和笔者所提SABPSO算法在不同种群规模、不同维度和不同迭代次数下，单独运行30 次获得的实验数据。表3～6中：N为算法的种群规模；D为维度；T为最大迭代次数。

表3 算法在测试函数F1上的实验结果Table 3 The experimental results of the algorithm on the on the test function F1

表4 算法在测试函数F2上的实验结果Table 4 The experimental results of the algorithm on the on the test function F2

表5 算法在测试函数F3上的实验结果Table 5 The experimental results of the algorithm on the on the test function F3

表6 算法在测试函数F4上的实验结果Table 6 The experimental results of the algorithm on the test function F4

在单峰函数F1，F2上，从表3，4中可以看出：SABPSO算法在3 个不同的种群规模、不同的维度和不同的迭代次数上具有最小的均值，说明SABPSO算法具有最佳的收敛精度；DFBPSO算法的均值小于WFBPSO算法，但差于VBPSO算法，VBPSO算法的收敛精度仅次于笔者所提的SABPSO算法，WFBPSO算法收敛精度最差。SABPSO算法在维度为100，500时具有最小的方差，说明SABPSO算法在稳定性上具有较好表现。在多峰函数F3，F4上，从表5，6中可以看出：对于多峰函数F3，SABPSO算法在3 个维度上都有最小的均值和方差，说明收敛精度和稳定性优于对比算法；对于函数F4，SABPSO算法在维度100，300时获得了最小的方差，但收敛精度表现略差；VBPSO算法在多峰函数F4上具有最小的均值，表现最佳。

从表3～6中的均值和方差数据可以看出：SABPSO算法在大部分测试函数上的收敛性能优于对比算法，这是因为SABPSO算法利用粒子的成长信息对学习因子进行调整，当粒子与全局最优粒子较远时，采用较大的c1值，较小的c2值，增强算法的全局探索能力，当粒子与全局最优粒子较近时，采用较小的c1值，较大的c2值，增强算法的局部开采能力。利用粒子成长信息实现学习因子自适应更新的策略有效提升了算法的搜索精度。

图1～4展示了SABPSO算法在种群为40、维度为300、迭代次数为500的条件下，在4 个测试函数上的寻优过程曲线，从图1～4中可以看出：由于4 个算法都采用了混沌初始化策略，因此在寻优初期4 个算法的收敛性能接近；算法的寻优后期，SABPSO算法在大部分函数能够很好地跳出局部最优，实现收敛精度的提升。在相同的500 次迭代中，SABPSO算法在大部分函数上都能找到比其他算法更好的解，这是因为SABPSO算法根据粒子的成长状态信息进行学习因子的自适应更新，在寻优过程中，学习因子自适应更新策略能够更好地均衡算法局部与全局搜索的平衡，进而实现算法收敛性能的提升。

图1 函数F1Fig.1 Function F1

图2 函数F2Fig.2 Function F2

图3 函数F3Fig.3 Function F3

图4 函数F4Fig.4 Function F4

图5～8是各算法在维度为300时的解集分布情况，从图5～8中可以看出：WFBPSO算法和DFBPSO算法在两个测试函数上都出现了异常值，VBPSO算法和笔者所提SABPSO算法只有在一个测试函数上出现了异常值。在单峰函数F1，F2和多峰函数F3上，SABPSO算法得到的解集比对比算法更加接近x轴，说明SABPSO算法得到的解精度更高；在多峰函数F4上，VBPSO算法的解更加接近x轴，但是数据范围比较大，稳定性不如其他3 个算法。SABPSO算法在大部分测试函数上的数据范围都相对较小，说明稳定性较好。

图5 测试函数F1Fig.5 Test function F1

图6 测试函数F2Fig.6 Test function F2

图7 测试函数F3Fig.7 Test function F3

图8测试函数F4Fig.8 Test function F4

从上述分析可知：SABPSO算法具有较好的收敛性能和较好的稳定性，这充分证明了利用粒子成长信息实现学习因子的自适应更新策略能够提升算法的收敛性能。

4 结 论

通过对学习因子的分析，提出一种自适应学习因子的混沌二进制粒子群优化算法。该算法借助成长因子实现学习因子的自适应更新，充分利用了种群的进化信息。仿真实验结果表明：SABPSO算法在单峰函数和多峰函数上都具有比对比算法更好的收敛精度，同时算法的解集箱须图证明了算法具有更好的稳定性。在下一步的研究工作中，将对SABPSO算法解决实际问题的能力进行验证并不断优化。