一种基于翻转角度的二进制粒子群优化算法

2014-12-23豆增发

科技视界 2014年6期

豆增发

(中国电子科技集团第二十研究所，陕西西安710068)

0 引言

近年来，基于仿生学的粒子群优化算法得到了飞速发展，各种粒子群优化算法被开发出来，并将其应用到了实践当中，取得了良好的效果。二进制粒子群算法是粒子群优化算法的一种，该算法在特征选择等方面得到了很好的应用，但是，传统的二进制粒子群算法存在收敛速度慢和收敛值不稳定的问题，因此，为了提高二进制粒子群优化收敛速度和收敛效果，本文提出了基于翻转角度的二进制粒子群优化算法。

1 传统二进制粒子群优化

二进制粒子群优化的所有的粒子在一个二值搜索空间寻找最佳解。根据粒子群优化的社会方法，一个粒子决定‘是’或者‘否’的概率可以建模如下：

概率P（Xid=1）完全依赖于Pid和Pg。Pid是迄今为止发现的个体最佳状态，如果最佳个体发生在Xid为1时，Pid为1，否则，Pid为0。Pg是全局最佳，如果全局最佳发生在Xid为1时，Pg为1，否则，Pg为0。Vid决定了概率函数P（Xid=1）上的一个门限值，因而其取值范围为[0.0,1.0],可以用反曲线函数表示：

在时刻t，第i个个体在字符串中第d个位置上的状态Xid(t)表示为：

当ρid＜S(Vid)时，Xid(t)=1;当ρid＞=S(Vid)时，Xid(t)=0。

ρid是一个在[0.0,1.0]之间均匀分布的随机数。Vid如下式所示：

rand1和rand2是在[0.0,1.0]范围上均匀分布的随机数,φ1和φ2两个参数的和为4.0。Vid的最大门限值Vmax被设为4.0。新的粒子位置由下式决定：

2 改进二进制粒子群优化算法

在二进制粒子群优化中，每个粒子有两种状态，即状态1和状态0，表示粒子处于状态0的概率，表示粒子处于状态1的概率，二进制粒子群并不是在一个连续的多维空间搜索，它实际上只是状态的反转而已，因此，通过对速率更新公式进行改进，移除随机权重φ1和φ2，增加了一个状态翻转因子。第i个粒子的下式取0或1：位置向量根据概率进行更新，即，第i个粒子的第j个元素根据

其中，random()是取值在[0,1]区间同一分布的随机函数，m是粒子群的最大个数，n是粒子群的维度。其中， β2可以用一个翻转速率Δθ来代替：

上式中，XP表示局部最优解，XG表示全局最优解，θ是翻转角度，γ1i和γ2i是局部翻转因子和全局翻转因子，它们可以通过分别与局部最佳解Pbesti和全局最佳解Gbest位置的适应函数作比较获得：

一般根据收敛情况动态的获得翻转角度：

上式中，θmax为最大翻转角度，一般取0.05π，θmin为最小翻转角度，一般取0.001π，t为当前迭代次数，M为最大迭代次数。

3 实验结果及分析

本文将改进二进制粒子群优化和传统二进制粒子群优化、传统粒子群优化算法、GA算法做了比较。传统粒子群优化的维度取30,每个算法各运行50次，然后得出平均迭代次数和平均收敛值。为了公平起见，根据经验，二进制粒子群优化、传统二进制粒子群优化以及传统粒子群优化中惯性因子和学习因子都去固定参数值，即惯性因子为0.9，局部学习因子和全局学习因子为2。

本文用平均收敛速度和平均收敛值来评价改进二进制粒子群优化算法的收敛性能，结果如表1所示。总体来讲，改进二进制粒子群优化的收敛速度较传统二进制粒子群优化略快，平均收敛值要好很多。平均收敛速度v和平均收敛值t定义如下：

上式中m为迭代次数，n为测试次数，s为收敛值。平均收敛速度表示算法的平均在收敛之前的平均迭代次数，平均收敛值表示算法最后所取得的平均最优解（表1）。

4 小结

本文提出了基于翻转教的改进二进制粒子群优化算法,该算法在二进制取值空间上，使粒子按翻转角度进行随机进化，最终得到使目标函数最大的二进制参数向量。与实值连续空间的粒子群优化不同，二进制粒子群在二进制空间取值，即每个粒子的取值为0或者为1，其进化速率根据一个翻转角度随机更新，这个翻转角度参照全局最优解和局部最优解。