一种新改进的粒子群优化算法

时贵英，吴雅娟，倪红梅

(东北石油大学 计算机与信息技术学院，大庆 163318)

粒子群优化(Particle SwarmOptimization，简称PSO)算法是1995年berhart博士和kennedy博士提出的一种新的进化算法[1]。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中显示了其优越性。但是任何方法都有其缺陷或不足，比如遗传算法[2-4]虽然具有良好的全局搜索能力，但是实现复杂，且局部搜索能力差容易发生早熟现象；同遗传算法比较，粒子群算法[5]容易实现并且没有太多参数需要调整，但是在算法后期局部搜索能力较差，反馈信息利用不充分，容易陷入局部最优，导致算法出现停滞，破坏了粒子间的多样性，导致算法不再继续搜索解空间，从而发生早熟；蚁群算法[6]具有正反馈性、并行性、强收敛性以及鲁棒性，但是由于搜索初期信息素相对匮乏，导致算法的搜索效率降低，容易产生停滞早熟现象。一种有效的方法是将粒子群算法和蚁群算法有机地结合起来，在传统的粒子群优化算法基础上引入蚁群思想，运用类似于蚁群算法中信息素的选择机制，在每个粒子的当前最好位置附近通过局部搜索产生若干个位置，它利用粒子群算法的较强的全局搜索能力生成信息素分布，再利用蚁群算法的正反馈机制求问题的精确解。该算法实现简单，且有效地避免了蚁群算法和粒子群算法的缺陷，达到了优势互补的效果。

1 基本粒子群算法

基本粒子群算法和遗传算法相似，它也是从随机解出发，通过迭代寻找最优解。粒子群的每个粒子代表问题的一个可能解，每个粒子具有位置和速度两个特征，并通过适应度来衡量粒子的优劣。算法首先初始化n个随机粒子，在m维空间中，记第i个粒子的当前位置为，当前速度为 =1，2，…， ，然后每个粒子在搜索时需要考虑两个因素：一个是粒子本身所找到的历史最优解，即个体极值；另一个是全部粒子群目前找到的最优解，即全局极值 pg=，并通过这两个极值根据下面的两个公式(1)和(2)来更新自己的速度和位置。

其中 i∈(1，2，…，n)，j∈(1，2，…，m)，表示迭代次数， 是保持原来速度的系数，即惯性权重，一般在0.1至0.9之间取值，惯性权重的大小决定了对粒子当前速度继承的多少，研究发现在算法的迭代过程中动态的减少惯性权重，可以使算法才更加稳定，效果比较好；c1和c2被称作学习因子，通常c1=c2=2，c1是调节粒子飞向自身最好位置方向的步长，c2是调节粒子飞向全局最好位置方向的步长；r1和 r2是在[0，1]区间内均匀分布的随机数；r是对位置更新的时候，在速度前面加的一个系数，这个系数叫做约束因子，通常设置为1。

2 改进的PSO算法

在粒子群算法中由于单个粒子仅仅保留其搜索过程中遇到的最优解pi的信息，在整个进化过程中如果粒子群的全局最优解pg与局部最优解pi接近，粒子将可能陷入局部最优，无法继续在解空间内进行进一步搜索。而蚁群算法是依据蚂蚁路线上的信息素浓度进行分析，按照一定概率选择信息素浓度较高的一条作为前进方向，从而达到求取优化解的目的。受蚁群算法启发，在粒子群算法中引入信息素机制[8]，在每个粒子当前局部最优解的邻域内进行局部搜索产生k个点，连同当前局部最优解在内，生成一个包含k+1个点的新序列pp，然后根据概率公式在该序列中选择相应的点，作为新的粒子。本文构造的新序列pp中第个点被选中的概率为：，函数 fitness(j)为点j的适应度。由选择概率可知，在pp序列中适应度较高的点被选中的可能性较大。通过邻域搜索机制使粒子群进化方向有了多种选择，加大了粒子间的多样性差异，从而降低了粒子群算法陷

这里q0是一个给定的参数入局部最优的可能性。

2.1 适应值函数的构造

如何定义适应值函数，是优化算法解决问题的关键。因为适应值函数的优劣将直接影响到算法解决问题的效率。本文采用“分支函数叠加法[3]”构造适应值函数，分支函数是一个实值函数，它是分支谓词到实值的一个映射，可以量化地描述在测试数据的驱动下，被测单元的实际执行路径对选定路径的覆盖程度。设选定路径上有个分支点，个参数，则每个分支点前需插入相应的分支函数可定义为：，；则该路径的的适应度函数，其中：

2.2 改进的PSO算法的实现描述

步骤1：在算法的初期用粒子群算法，初始化粒子群并计算粒子适应度，初始化粒子的个体最优值和全局最优值，使达到精度要求的粒子退出迭代；

步骤2：粒子达到迭代次数或满足精度要求后退出迭代，转步骤6；

步骤3：根据公式(1)和(2)更新剩余粒子的速度和位置，重新计算粒子适应度，更新粒子的个体最优值和全局最优值，同样达到精度要求的粒子也要退出迭代，转步骤6；

步骤4：在最后剩余粒子的当前局部最优解 pi的邻域内进行局部搜索产生k个点，然后根据概率公式(3)在该序列中选择相应的点，作为新的粒子，并重新计算粒子适应度，更新粒子的个体最优值和全局最优值；

步骤5：迭代次数加1，然后转步骤2；

步骤6：输出每个粒子当前的局部最优解。

3 仿真实验

三角形分类问题包含了清晰而又复杂的逻辑，下面以三角形分类程序为例，来验证本文算法在求解面向路径的测试数据问题的性能。三角形分类问题描述为：输入3个整数A、B和C，作为三角形的边，根据边的关系输出三角形类型。例如以1到10的整数作为输入，在1000组可能的组合中，只有10组能满足判定为等边三角形的分支。在本文算法的实现过程中，采用整数编码方式，随机产生1到100之间的整数，生成初始种群，设置种群初始规模为100，取粒子群算法的参数随迭代次数由0.7线性地减小到0.4，最大迭代次数是20，取k=10。使用本文算法生成的路径测试数据实验结果如图1所示。

图1 本文算法的实验结果Fig.1 The experiment result of the improved PSO algorithm

为了验证本文算法的有效性，本文同时使用在相同条件下没有引入信息素机制的粒子群算法(暂时称作基本的粒子群算法)来生成测试数据，以便于与使用本文算法生成的数据进行对比。为了更好地进行比较，系统将使用本文算法生成的初始粒子群数据保留在外部文件中，作为没有改进的粒子群算法的初始种群，生成的三角形路径测试实验结果如图2所示。

图2 基本粒子群算法的实验结果Fig.2 The experiment result of PSO algorithm

根据以上两组数据的对比，可以很清楚地看到，在改进粒子群算法中由于引入了信息素的调解作用，从而有效地保证了个体的多样性，不至于在很短的时间内使适应度高的少数个体占据群体总数的大部分，更好地避免了早熟和局部最优等不足，使得路径覆盖更全面，更合理，测试数据生成更可靠，更具有实用价值。

4 结束语

本文提出一种改进的粒子群算法，算法融合蚁群算法和粒子群算法的优缺点，在搜索算法早期用粒子群算法生成初步测试结果，然后引入蚁群算法的信息素机制来加强粒子的区域搜索能力，克服了使用单一粒子群算法容易陷入局部最优的问题。实验结果表明改进后粒子群算法实现简单方便，用于测试用例自动生成，效果好于单独的粒子群算法。

[1]Kennedy J，Eberhert R.Particle swarm optimization[J].IEEE International Conferenceon Neural Networks，1995：1942-1948.

[2]夏芸，刘锋.基于免疫遗传算法的软件测试数据自动生成[J].计算机应用，2008，8(3)：723-725.

[3]汪浩，谢军凯，高仲仪.遗传算法及其在软件测试数据生成中的应用研究[J].计算机工程与应用，2001，37(12)：64-68．

[4]许秀梅.基于退火免疫遗传算法的测试数据生成方法研究[D].北京：北京交通大学，2007.

[5]尉小环，高慧敏，李峰.微粒群算法在软件测试数据生成中的应用[J].太原科技大学学报，2009.8，30(4)：294-296.

[6]傅博.基于蚁群算法的软件测试数据自动生成[J].计算机工程与应用，2007，43(12)：97-99.

[7]段玉红，高岳林.基于蚁群信息机制的粒子群算法[J].计算机工程与应用，2008，44(31)：81-83.

[8]史海军，王志刚，郭广寒.引入变异算子的粒子群优化算法[J].长春理工大学学报：自然科学版，2007，30(3)：81-83.