一种求解大规模问题的自学习协同粒子群算法

一种求解大规模问题的自学习协同粒子群算法

*肖根福1，刘 欢2，李东洋3，欧阳春娟2

【摘 要】随着工程技术要求的提高，许多实际优化问题从低维问题发展成高维的大规模优化问题，自然计算算法在面对该类问题时容易陷入局部最优，而协同粒子群算法是解决大规模优化问题的重要手段之一。本文将子种群划分自学习策略和惯性权重自适应策略引入到协同粒子群算法中，增强了算法的自学习能力，提高了算法的全局寻优能力。实验结果表明，所提算法的性能超过了传统协同粒子群等算法，具有求解大规模问题的较大潜力。 【期刊名称】井冈山大学学报（自然科学版） 【年(卷),期】2018(039)003 【总页数】6

【关键词】大规模优化；协同粒子群算法；学习自动机；自学习

【文献来源】https://www.zhangqiaokeyan.com/academic-journal-cn_journal-jinggangshan-university-natural-science_thesis/0201248613361.html

0 引言

近年来，自然计算在优化问题中取得了巨大的成功，进行了较多的实际应用。与传统的梯度下降法相比，自然计算算法在面对不可微、非线性问题时有较大优势。自然计算算法种类很多，如粒子群算法、微分进化算法、蚁群算法、萤火虫算法等等。每一种算法又有许多改进的形式，以1995年由kennedy提出的粒子群算法为例，有聚类粒子群[1]、散射学习粒子群[2]、自适应粒子群[3]和综合学习粒子群（CLPSO）[4]等等。

尽管自然计算算法取得了巨大的成功，但自然计算算法在求解大规模优化问题

时性能将迅速恶化，遭遇“维数诅咒”[5]。协同进化策略是解决大规模问题的重要手段之一，协同进化采用“分而治之”的策略将大规模问题分解成小的子问题。自从Potter[6]提出协同进化算法框架以来，研究者们提出了多种协同进化算法，如协同进化遗传算法[7]，协同进化粒子群算法[8]，协同进化微分进化算法[9]。

在协同策略框架中，有两个关键问题值得探讨，一是将大规模问题合理地划分为子问题，而划分子问题的关键是找到变量间的内在关系，将耦合关系强的变量归入同一子群；二是平衡子群的全局搜索能力和局部搜索能力，平衡这两种能力的关键是惯性权重的合理选取。

本文针对协同粒子群算法在求解大规模优化问题时容易陷入局部最优的特点，采取两个策略来改进协同粒子群算法，一是利用学习自动机挖掘出问题子维间的耦合关系，将关系相近的子维放入到一个子种群当中；二是将子种群自适应地分成两个部分，对优化效果差的粒子赋予新的惯性权重，令其跳出局部最优，加快算法收敛。

1 大规模优化问题

优化问题可以用下式描述：

其中，F(x)为优化问题的目标函数，有最小化和最大化两类问题，本文算法针对的是最小化问题。为边界约束，xi为决策变量，D为决策变量的个数，即优化问题的维数。

一般来说，所谓大规模优化问题是指决策变量的个数D大于100的问题[5]。大规模优化问题的求解主要有两个难点：一是决策变量的增加使解空间呈指数式增长，在计算资源有限的情况下很难找到最优解；二是决策变量增加使多峰

函数的局部最优解个数呈指数式增长，算法易陷入局部最优。

2 自学习协同粒子群算法

2.1 协同粒子群算法

粒子群算法是受飞鸟觅食行为的启发而提出的，每个粒子代表一个可行解，粒子追随个体极值（pBest）和全局极值（gBest）进行寻优。在标准粒子群算法中，粒子用下式更新自己： （3）

其中Vi为当代粒子的移动速度，Vi+1是下一代粒子的移动速度，pi是当代粒子的位置，pi+1是下一代粒子的位置，pb为个体最优位置，pg为全局最优位置，r1，r2是随机数，c1，c2是学习因子，一般为常数，w为惯性权重。 在标准粒子群算法中，每个粒子代表一个完整的解向量，包含了所有决策变量，包含了问题的每一子维。每次粒子位置的更新都要更新所有的决策变量，这容易造成“两步向前、一步向后”的问题，也就是说，虽然在优化过程中适应值函数是逐渐减小的，但问题的每一个子维并不都是向最优位置靠近，部分子维会远离最优位置，从而削弱算法的全局收敛性，使算法容易陷入局部最优。 为了保证粒子的每个子维都向正确的方向运动，Van den Bergh[8]提出了协同粒子群算法，该算法的基本思想为：将粒子群划分成多个相互独立的子种群，分别在问题的不同子维上搜索，每个子种群解决问题的一个子目标，同时，子群体之间保持信息沟通和知识共享，协同进化。在协同粒子群算法中，子种群是依次更新的，当某一子种群的粒子朝某一子维方向移动一次后，与其它子种群获得的当前最优位置结合，构造出一个完整的解向量，并用评价函数计算适应度，之后下一个子种群再朝另一子维移动，直至所有子种群都完成更新。