基于自适应排斥因子的改进粒子群算法

摘 要：基本粒子群算法在求解复杂的多峰问题时，由于存在较多的局部最优解，算法极易出现早熟现象。为克服这一缺陷，采用蒙特卡洛（Monte Carlo）方法模拟了种群飞行轨迹，得出种群极易陷入局部最优解的原因；在此基础上，通过定义粒子间距离、粒子间最大距离和粒子间平均距离，提出一种自适应控制粒子自身最优位置（pp）和种群最优位置（pg）间距离的排斥因子（Adaptive rejection factor，ARF），来提升种群跳出局部最优的能力。为测试提出策略的有效性，在60次独立运行时，基于ARF的改进PSO算法（ARFPSO）在Rosenbrock，Ackley和Griewank函数上所获得的最好值分别为53.82，2.1203和5.32E-004，都优于其他两种对比算法，这表明ARFPSO能有效地跳出局部最优解；算法的复杂度分析表明引入的策略没有增加计算复杂度。

关键词：粒子群算法；自适应排斥因子；蒙特卡洛模拟；多峰问题；局部最优解

中图分类号： TP18

文献标志码：A

0 引言

粒子群算法（Particle Swarm Optimization， PSO）[1]是群智能算法领域中应用较为广泛的一种算法，其概念简单，相比其他算法具有控制参数少、容易实现等优点，已被社会科学、自然科学等各领域的学者广泛应用[2-5]。但基本粒子群算法在优化复杂多峰问题时，由于种群多样性的丧失，算法极易陷入局部最优解，使得基本粒子群算法在实际应用中受到了限制。为更好地将PSO应用于实际问题的求解，国内外许多学者针对基本PSO提出了一些改进策略。比较经典的改进算法，如Clerc等[6]引入了收缩因子，在基本PSO基础上，提出带有收缩因子的PSO变形。Mendes等[7]提出完全信息粒子群算法，充分利用了种群中粒子的各维信息，以提升种群的潜在搜索空间。Zhan等[8]和Riget等[9]提出新的粒子学习策略来提升种群向全局最优解收敛的概率。迟玉红等[10]提出一种基于空间缩放和吸引子的粒子群优化，它利用对搜索空间进行缩放的边界变异策略有效控制了粒子搜索范围，保证了算法全局探测能力。

申元霞等[11]提出相关性粒子群优化模型。该模型采用Copula函数刻画随机因子间的相关结构，而不同的相关结构和相关性程度反映了粒子对自身经验信息和群体共享信息的利用策略的差异，同时给出了基于Gaussian Copula的相关性粒子群优化模型的实现方法。陈志敏等[12]提出自适应粒子群优化的新型粒子滤波来提升算法的性能及应用。最近，Blackwell等[13]提出一种动态更新规则粒子群算法以提升算法的运行效率。Wan等[14]和聂新立等[15]提出混合算法来改善粒子群算法的性能。

总之，目前已有的各种改进算法都是从种群多样性、粒子学习样本改进、算法的混合等角度展开讨论，取得了一定的效果，但是在求解精度上仍有改进空间。

因此，为有效地提升算法跳出局部最优解的能力，提升算法的求解精度，本文提出一种自适应排斥因子粒子群算法。首先，采用蒙特卡洛（Monte Carlo）方法模拟了种群飞行轨迹，得出种群极易陷入局部最优解的原因；然后，通过定义粒子间距离、粒子间最大距离和粒子间平均距离，提出一种自适应控制粒子自身最优位置（pp）和种群最优位置（pg）间距离的排斥因子来提升种群跳出局部最优的能力；最后，将所提出算法与其他几种算法进行算法收敛性及统计分析对比。

3.3 算法的计算复杂度分析

由于本文提出的自适应排斥因子粒子群算法（ARFPSO） 是在基本粒子群算法基础上引入了相应的策略，因此，需要从计算复杂度上分析引入的策略是否增加了算法的计算复杂度。用T表示最大迭代次数，N表示粒子总数，D表示决策变量的维数。自适应排斥因子的计算复杂度T1（N）=O（N×T），基本粒子群算法的计算复杂度T2（N）=O（N×D×T），这样，ARFPSO算法的计算复杂度为T（N）=O（N×D×T）+O（N×T）≈O（N×D×T）=T2（N）。因此，理论上ARFPSO与基本PSO算法的复杂度在同一数量级上。

为进一步测试算法的计算复杂度，将三种算法在检测函数上Rosenbrock，Ackley和Griewank上，采用仿真平台Pentium Core Duo，1.8GB RAM CPU，2GB RAM，Matlab R2008b，每个检测函数独立运行30次，每次迭代3×104次函数评价，对每种算法运行时间取平均值。表2给出每种算法的独立运行时间，可以看出，ARFPSO与其他算法在运行时间在同一数量级，引入的策略并没有增加计算复杂度。

4 结语

针对基本粒子群算法在求解复杂的多峰问题时，算法极易陷入局部最优解的缺陷，本文提出一种自适应排斥因子粒子群算法。首先，采用蒙特卡洛（Monte Carlo）模拟了种群运行轨迹，得出种群极易陷入局部最优解的根源在于，在算法迭代后期，粒子自身最优位置（pp）和种群最优位置（pg）间距离过于接近，导致种群速度接近于0，种群静止，失去进一步探索能力。针对这一结论，提出一种排斥因子，自适应地控制粒子的进化速度，来提升种群跳出局部最优的能力。通过在Rosenbrock，Ackley和Griewank三个检测函数上的仿真实验表明：1）相比其他算法，ARFPSO算法具有较快的收敛速度及较好的跳出局部最优解的能力；2）相比其他算法，ARFPSO算法所获结果具有统计学意义；3）ARFPSO算法引入的策略没有明显增加计算复杂度，与基本粒子群算法在同一计算复杂度上。因此，ARFPSO算法是求解复杂多峰问题的一种有效方法。

参考文献：

[1]KENNEDY J， EBERHART R C. Particle swarm optimization [C]//Proceedings of 1995 IEEE International Conference on Neural Networks. Piscataway： IEEE， 1995， 4：1942-1948.

[2]ZHOU X C， ZHAO Z X， ZHOU K J， et al. Remanufacturing closedloop supply chain network design based on genetic particle swarm optimization algorithm [J]. Journal of Central South University of Technology， 2012， 19（2）： 482-487.

http：//.cn/Periodical_zngydxxb-e201202026.aspx【

[3]SUBRAMANIAN P， RAMKUMAR N， NARENDRANA T T， et al. A technical note on ‘Analysis of closed loop supply chain using genetic algorithm and particle swarm optimisation’ [J]. International Journal of Production Research， 2012， 50（2）： 593-602.

http：///doi/abs/10.1080/00207543.2011.593348#preview

[4]韩鹏飞， 孙占磊，赵罡. 改进离散粒子群算法及其在飞机装配任务调度中的应用研究 [J]. 图学学报， 2013， 34（1）： 60-65.

[5]王念桥， 姚四改. 基于改进粒子群优化算法的排课问题 [J]. 计算机应用， 2013， 33（1）： 207-210.

[6]CLERC M， KENNEDY J. The particle swarm — explosion， stability， and convergence in a multidimensional complex space [J]. IEEE Transactions on Evolutionary Computation， 2002， 6（1）： 58-73.

[7]MENDES R， KENNEDY J. The fully informed particle swarm： simpler， maybe better [J]. IEEE Transactions on Evolutionary Computation， 2004， 8（3）： 204-210.

[8]ZHAN Z H， ZHANG J， LI Y， et al. Orthogonal learning particle swarm optimization [J]. IEEE Transactions on Evolutionary Computation， 2011， 15（6）： 832-847.

[9]RIGET J， VESTERSTRM J S. A diversityguided particle swarm optimizer — the ARPSO， EVALife TR 2002-02 [R]. Aarhus， Denmark： University of Aarhus， 2002.

http：///Publication/58025/a-diversity-guided-particle-swarm-optimizer-the-arpso

[10]迟玉红，孙富春，王维军，等.基于空间缩放和吸引子的粒子群优化算法[J]. 计算机学报，2011，34（1）：115-130.

[11]申元霞， 王国胤，曾传华.相关性粒子群优化模型 [J]. 软件学报，2011，22（4）：695-707.

[12]陈志敏，薄煜明，吴盘龙，等.基于自适应粒子群优化的新型粒子滤波在目标跟踪中的应用[J].控制与决策，2013，28（2）：193-200.

[13]BLACKWELL T. A study of collapse in bare bones particle swarm optimization [J]. IEEE Transactions on Evolutionary Computation， 2012， 16（3）： 354-372.

[14]WAN Z P， WANG G M， SUN B. A hybrid intelligent algorithm by combining particle swarm optimization with chaos searching technique for solving nonlinear bilevel programming problems [J]. Swarm and Evolutionary Computation， 2013， 8： 26-32.

[15]聂立新，张天侠.并行定向扰动的混合粒子群优化算法[J]. 计算机应用研究， 2013， 30（6）：1633-1635.