一种基于多子群的动态优化算法
高平安，蔡自兴，余伶俐
(中南大学 信息科学与工程学院，湖南 长沙，410083)
摘 要：
摘 要：针对动态粒子群优化算法的群体多样性问题，提出一种新的度量方法。为了提高群体多样性，在每次迭代前，子群内部各粒子以一定的概率飞离局部最优粒子，以保持子群内部粒子多样性。在此基础上，提出一种动态粒子群优化算法，即在每次迭代前，要淘汰超规模子群中的低适应值粒子，进一步增强整个群体的多样性水平，提高算法的鲁棒性。用标准测试函数MPB测试该算法跟踪动态全局最优值的能力，实验结果表明：该算法能有效跟踪5维以上的动态全局最优值，子群内部多样性水平提高60%以上。
关键词：
中图分类号：TP301 文献标识码：A 文章编号：1672-7207(2009)03-0731-06
Multi-swarm based optimization algorithm in dynamic environments
GAO Ping-an, CAI Zi-xing, YU Ling-li
(School of Information Science and Engineering, Central South University, Changsha 410083, China)
Abstract: A diversity measure was proposed for multi-swarm particle swarm optimization algorithms in dynamic environments. In order to improve the diversity of the swarm, each particle flew randomly away from its best neighbor particle before updating its velocity and location, and the redundant particles in each sub-swarm were replaced with random particles in search space. Subsequently, the change was detected by re-evaluating the objective function at the memorized best location of each particle. The results show that the diversification method can improve the diversity of sub-swarms with 60% more than that of a representative algorithm, and the proposed algorithm can efficiently track changing global optimum in high dynamic environments.
Key words: dynamic optimization; particle swarm optimization; multi-swarm; diversity
粒子群优化(Particle swarm optimization, PSO)技术可以用于求解大量的工程优化问题[1-2]，但现实中存在的许多优化问题是动态优化问题，问题的动态性通常表现为全局最优值及最优解在优化过程中会发生变化。这种变化要求优化算法既能够及时检测到优化问题的变化，又能够有效地对变化作出响应，适时调整优化方向，有效地搜索新的全局最优值[3-4]。
近年来，基于粒子群优化技术的动态优化方法研究越来越受到国内外众多研究者的关注[3-8]。研究结果表明，动态粒子群优化算法必须克服变化前的优化信息对群体进化的错误影响，能够在变化后重新获得群体多样性或在整个优化过程中能够保持群体多样性以适应环境的变化。一般可以将粒子的当前位置作为个体历史最优位置，或选择变化前粒子的个体最优位置和当前位置中两者较好的位置作为粒子的新最优位置，以减少变化前部分信息的误导作用[5]。群体多样性对于动态优化算法特别重要，因为多样性可以反映群体在解空间中的覆盖范围，若变化后的最优解处于群体覆盖范围之外，则算法很难跟踪到新的最优解。算法检测到变化发生后，可以通过随机产生新粒子替换群体中部分粒子以增强环境变化后的群体多样性[6]，但是，究竟该随机产生多少粒子进行替换是一个很难确定的问题。若随机产生的新粒子太少，则群体多样性提高不明显；若随机产生的新粒子太多，则丢弃的历史信息会太多，这2种情况都不利于提高群体对环境变化的适应能力。另一类解决群体多样性问题的方法是在整个优化过程中始终维持种群多样性，避免全体粒子收敛到同一个局部最优值，使得粒子的搜索范围总能覆盖一个较大区域。如将群体划分为多个子群，每个子群利用局部最优粒子作为粒子的社会学习对象，减少全体粒子向同一个全局最优粒子移动的压力[7-11]。Parrot等[8]提出的基于多物种模型的算法DSPSO (Dynamic species-based particle swarm optimization)没有明确考虑子群内部的多样性保持问题，在每次选择冗余粒子时，总以与子群内最优粒子适应值相同的粒子作为冗余粒子而进行随机化替代，这样容易造成子群内粒子过度聚集在局部最优粒子附近一个很小的区域内，子群内多样性会逐步丧失。当环境发生变化时，各子群由于多样性太小而降低粒子重新搜索新最优值的速度。Blackwell等[11]在多子群中加入1个反收敛算子和电荷排斥机制，避免多个子群收敛到同一个局部最优值，并总是将最差的子群作为一个全局搜索子群，以增强算法搜索新局部最优值的能力。但该算法的参数控制复杂，尤其是电子云半径rcloud和排斥半径rexcl过分依赖于优化函数的变化强度信息。在此，本文作者提出一种基于多子群的动态粒子群优化算法。该算法根据粒子间的相似性程度将全体粒子划分成若干个子群，相似程度高的粒子形成1个子群。度量2个粒子相似程度的依据是粒子之间的距离，距离越近表示2个粒子越相似。子群的数目不限定，但每个子群包含粒子的数目受到限制。为了避免同一个子群内的粒子过度聚集到子群内最优粒子，每次迭代前要将子群内粒子进行稀疏化处理。因此，在优化过程中，不仅能保持子群之间的多样性，而且能保持每个子群内部的多样性，避免参数对问题的依赖性，提高了算法的鲁棒性。
1 动态优化问题描述
动态优化问题是指在优化过程中最优解会发生变化的问题。这种变化可以是有规律地变化，也可以是无规律地变化，因此，动态优化问题的一般形式可以表示为：
Moving peaks benchmark(MPB)[12]和Generator dynamic test function(DF1)[13]是当前具有代表性的动态优化算法标准测试函数。MPB是一类多峰函数，可能存在多个全局最优值。MPB的动态性表现为多个峰的高度、峰的形状以及峰中心位置随时发生变化。D维m个峰的MPB函数的定义为：
峰中心的位置pi(t)根据速度vi(t)朝某个方向移动的尺度规格化为cs，速度变化的最大值即速度变化强度由参数cs设定。λ(0≤λ≤1)决定峰的随机移动与前一次移动的相关程度，若λ=0，则每次移动与上次移动的方向不相关，即为随机移动；若λ=1，则表明该峰总向1个方向移动(当撞到边界时则反弹)。μ是一个随机速度向量，因此，cs，λ和μ是决策峰中心位置变化的3个核心参数。
2 多子群PSO算法
2.1 动态PSO基本概念
动态PSO算法中用三元组(xi, vi, pi)表示群体中粒子
的状态，其中：xi表示粒子在解空间中的位置；vi表示粒子的“飞行”速度；pi为粒子自上次变化以来所经历的最佳位置。粒子在第d (1≤d≤D)维上状态更新规律为[14-15]：
称式(2)和(3)为标准PSO粒子状态更新方程。
定义1 2个粒子间的距离是指2个粒子在解空间中的欧几里德距离。
定义2 2个子群之间的距离是指2个子群的最优粒子之间的距离。
Blackwell[16]提出了一种度量群体多样性的标准，即群体S的多样性等于S中全体粒子在各维度中的最大区间长度。若令D(S)表示群体S的多样性，则
这种度量标准虽然能表示群体覆盖的最大范围，但这种多样性度量标准不能恰当地反映粒子的真实分布。因为对于采用随机产生新粒子替换原群体中部分粒子的动态优化算法，即使绝大多数粒子已经收敛到同一个局部最优位置，但仅由2个比较分散的随机粒子便可以增大群体的多样性水平。本文对群体多样性的度量更关注大多数粒子的分布，尤其关注子群中大多数粒子的分布，具体含义由定义3给出。
定义3 群体S的多样性等于群体中所有粒子与局部最优粒子之间的距离之和，即若令D(S)表示群体S的多样性，则
2.2 子群的划分与稀疏化处理
由于优化问题通常同时存在多个局部最优值，优化算法需要能够搜索到每个局部最优值，对此存在2种基本搜索策略，即序贯搜索策略和并行搜索策略。序贯搜索策略是群体在搜索到1个局部最优值后粒子移动到新的区域搜索新的局部最优值，而并行搜索策略是全体粒子在整个解空间中并行搜索所有的局部最优值。对于动态优化问题，由于每个局部最优值随时都会发生变化，全局最优值也发生变化，因此，不适合采用序贯搜索策略定位和跟踪全局最优值，只适合采用并行搜索策略，即多个子群并行在解空间中搜索不同区域的局部最优值，实现对全局最优值的跟踪。
假设优化问题的m个局部最优值在解空间均匀分布，则可将粒子划分成m个子群，各子群的半径rs可以根据下式计算[11]：
对群体进行子群划分时，除了需要考虑粒子之间的距离外，还需要考虑粒子的适应值，要确定以什么粒子为参照来生成子群。采用k-均值法虽然可以对群体进行划分，但子群数量和稳定迭代次数难以预先设定。本文采用文献[8]中的方法确定各子群的局部最优粒子，并根据子群半径rs对群体进行划分，子群的数目不需要预先设定。算法能快速产生所有子群的局部最优粒子，并且可以同时完成多个子群的划分。多子群生成算法(Multi-swarm identification, MI)的主要步骤描述如下。
步骤1 将全体粒子据适应值降序排列成表Ls。
步骤2 置子群最优粒子集合S。
步骤3 对Ls中的第1个未作处理的粒子p作如下处理：若S中存在粒子s与粒子p之间的距离小于rs，则粒子p加入粒子s所确定的子群，转步骤4。 若S中不存在粒子与粒子p之间的距离小于或等于rs，则将p加入S。
步骤4 标记Ls中的粒子p为“已处理”状态。
步骤5 若Ls中还有未处理的粒子，则转步骤3。
步骤6 将集合S的每个粒子设定为该粒子所在子群中的局部最优粒子。
通过实验数据分析可以发现，根据式(5)确定的子群半径决定了各子群在解空间中的最大覆盖范围，但同一子群内的粒子可能由于受到子群内最优粒子的吸引而聚集到最优粒子周围很小的区域。该算法并不能确定这些粒子的数量，也不能确定子群内粒子的分布，极端情况可以是绝大部分粒子收敛到同一个局部最优粒子，这是一种典型的多样性丧失现象。多样性的丧失将严重制约算法对动态最优值的跟踪能力，影响算法的动态优化能力。Parrot等[8]虽然采用删除多余粒子的方法能缩小子群的规模，但不能消除子群内粒子的过度聚集。因此，本文作者针对这种多样性丧失问题提出一种稀疏化处理策略，以改善子群中粒子的分布状态，保持子群内部的多样性能力，提高算法跟踪动态全局最优值的能力。
稀疏策略的基本思想是：在每次完成MI过程后，对每个子群进行一次稀疏化处理，基本过程为：对局部最优粒子s所在子群中每个粒子p，以概率Ps选择飞离s，以1-Ps的概率飞向s。设p与s之间的距离等于lp，则将粒子p以等概率在[0, rs-lp]区间上选择1个值作为飞离距离s。若子群的规模超过pmax，则优先选择稀疏化后子群中适应值最小的粒子在解空间中进行随机化处理，直到该子群规模小于pmax为止，所有被随机化的粒子不参与本次迭代。这样，稀疏化的结果是增大各粒子与局部最优粒子之间的距离，增强子群内部的多样性。
2.3 基于多子群的动态PSO算法
基于多子群的动态PSO算法(Multi-swarm based PSO，即MSPSO)的主要步骤描述如下。
步骤1 在解空间中随机确定N个粒子的位置、每个粒子的最优位置和初始飞行速度，并记粒子i的状态为(xi, vi, pi)。
步骤2 计算每个粒子的适应值和历史最优值，记粒子i在t时刻的适应值为f (xi, t)，更新历史最优位 置，并记历史最优值为f (pi, t)。
步骤3 执行MI算法确定局部最优粒子集合S，并生成|S|个子群。
步骤4 重新计算全体粒子的个体历史最优位置对应的适应值，若适应值与原来的适应值不同，则重新设置个体的历史最优位置，转步骤3。否则，对每个子群执行一次稀疏化处理过程。
步骤5 更新每个子群内所有粒子的状态，更新个体历史最优位置。
步骤6 若不满足算法的终止条件，则转步骤3。
本算法包含了子群粒子分布的调节策略，在粒子进化过程中，子群内粒子对局部最优粒子收敛的压力比DSPSO[8]的小，但算法的计算复杂度并没有增加。稀疏化子群的过程没有增加新的参数，不需要进行复杂的排斥力计算，因此，避免了MQSO(Multiswarm quantum swarm optimization)[11]中参数对问题的严重依赖性。
Brits等[17]的试验研究表明，当群体粒子总数为大于4m(m为局部最优值个数)时，算法可以满足并行搜索m个局部最优值的需要。但当群体规模小于4m时，可能会存在某些局部最优值没有足够的粒子进行搜索。当优化问题的局部最优值的个数不能预知而且规模较大时，对动态最优值的跟踪将十分困难，目前，还没有有效的方法可以解决。因此，本文作者提出的优化算法也是用于解决局部最优值数目已知或至少知道局部最优值数目的上界的动态优化问题。
3 算法性能测试
3.1 算法性能评价指标
由于动态优化问题不存在单一的非时变的全局最优值，算法的目标并不仅要获得极值点，而且要尽可能跟踪极值点在解空间内的运动轨迹，因此，目前用于评价动态优化算法性能的指标大多采用离线误 差[8, 18]。本文采用离线最优全局误差
作为算法性能评价指标。是自上次变化至
时刻全局最优粒子目标函数值的相对误差的最小值，即
3.2 算法性能测试结果与分析
MSPSO的性能测试函数MPB的定义由式(1)给出，表1所示为MPB的主要参数设置值。粒子状态更新控制参数
=
=2.05,
=0.729 844，子群稀疏化概率Ps=0.15。图1所示为MSPSO对5维空间中每 5 000次迭代发生1次变化的5个峰的MPB全局最优值离线误差示意图。算法的群体粒子总数设置为100，子群最大规模设置为20。图2所示为图1中从第9 500次迭代到第10 500次迭代之间函数发生变化前后算法的全局最优值跟踪效果。从图2可以看出，函数发生变化后会导致较大的误差，但算法迭代100次左右便可将全局最优误差降低到最小。
表1 MPB参数设置
Table 1 Parameters of MPB
图1 全局最优值离线误差
Fig.1 Offline error of global optimal particle
图2 全局最优值跟踪示意图
Fig.2 Tracking global optimum
3.3 MSPSO与DSPSO的多样性比较
保持群体多样性的根本目的在于，当算法检测到环境发生变化后，子群体中粒子的覆盖范围足够大，以便包含新的局部最优值。DSPSO没有考虑子群内的粒子多样性问题，子群内粒子容易过度收敛到局部最优粒子，子群的多样性较小。图3所示为DSPSO对二维空间中1个包含10个峰的MPB在优化过程中的粒子分布示意图，群体规模为100，子群最大规模为20。图4所示为MSPSO对同一个MPB优化的粒子分布示意图，各子群的粒子多样性明显比图3中各子群的粒子多样性要大。
图3 DSPSO的粒子分布
Fig.3 Distribution of particle of DSPSO
图4 MSPSO的粒子分布
Fig.4 Distribution of particle of MSPSO
图5所示为对1个包含10个峰的MPB动态优化过程的群体多样性对比结果。从图5可以看出，DSPSO算法的群体多样性从整体上明显小于MSPSO算法的群体多样性，而且DSPSO算法的群体多样性水平在20 000次迭代时平均为3.468 2。MSPSO算法能保持相对较高的子群多样性水平，在绝大多数情况下多样性水平大于5，经20 000次迭代的多样性水平平均值为5.561 7，要比DSPSO高60%。
图5 不同算法的多样性对比
Fig.5 Comparison of diversity of different models
4 结 论
a. 提高群体多样性有利于提高动态优化算法跟踪全局最优值的能力。基于多子群的粒子群优化算法不仅能保持子群之间的多样性水平，而且能保持子群内部的多样性水平。
b. 所提出的群体多样性度量标准不仅能反映群体的整体分散程度，而且能反映子群内粒子的分散 程度。
c. 所提出的利用稀疏化子群机制提高子群内部的多样性的多子群算法MSPSO具有2个重要特征：子群多样性水平明显高于DSPSO算法的子群内多样性水平，在大多数情况下要高60%，子群内的粒子分布更宽泛；算法的参数对问题的依赖性很小，稀疏化子群的概率只需要在[0.05, 0.2]区间中取值，对优化问题的特征不敏感。
参考文献：
[1] 李 婷, 赖旭芝, 吴 敏. 基于双种群粒子群优化新算法的最优潮流求解[J]. 中南大学学报: 自然科学版, 2007, 38(1): 133-137.
LI Ting, LAI Xu-zhi, WU Min. A novel two-swarm based particle swarm optimization algorithm for optimal power flow problem[J]. Journal of Central South University: Science and Technology, 2007, 38(1): 133-137.
[2] LI Xing-mei, ZHANG Li-hui, QI Jiang-xun, et al. An extended particle swarm optimization algorithm based on coarse-grained and fine-grained criteria and its application[J]. Journal of Central South University of Technology, 2008, 15(1): 141-146.
[3] Eberhart R C, SHI Yu-hui. Tracking and optimizing dynamic systems with particle swarms[C]//Proceedings of Congress on Evolutionary and Computation, Piscataway. New York: IEEE, 2001: 94-100.
[4] JIN Yao-chu, Branke J. Evolutionary optimization in uncertain environments: A survey[J]. IEEE Transactions on Evolutionary Computation, 2005, 9(3): 303-317.
[5] Carlisle A, Dozier G. Tracking changing extrema with adaptive particle swarm optimizer[C]//Proceedings of the World Automation Congress. Orlando, 2002: 265-270.
[6] HU Xiao-hui, Eberhart R C. Adaptive particle swarm optimization: detection and response to dynamic systems[C]// Proceedings of the IEEE Congress on Evolutionary Computation. Honolulu, 2002: 1666-1670.
[7] Janson S, Middendorf M. A hierarchical particle swarm optimizer for dynamic optimization problems[C]//Applications of Evolutionary Computing. Raidl G R. Berlin: Springer-Verlag, 2004: 513-534.
[8] Parrot D, LI Xiao-dong. Locating and tracking multiple dynamic optima by a particle swarm model using speciation[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(4): 440-458.
[9] 窦全胜, 周春光, 徐中宇, 等. 动态优化环境下的群核进化粒子群优化方法[J]. 计算机研究与发展, 2006, 43(1): 89-95.
DOU Quan-sheng, ZHOU Chun-guang, XU Zhong-yu, et al. Swarm-core evolutionary particle swarm optimization in dynamic optimization environments[J]. Journal of Computer Research and Development, 2006, 43(1): 89-95.
[10] DU Wei-lin, LI Bin. Multi-strategy ensemble particle swarm optimization for dynamic optimization[J]. Information Science, 2008, 178: 3096-3109.
[11] Blackwell T, Branke J. Multiswarms, exclusion and anti- convergence in dynamic environments[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(4): 459-472.
[12] Branke J. Memory enhanced evolutionary algorithms for changing optimization problems[C]//Proceedings of the 1999 Congress on Evolutionary Computation. Washington, 1999: 1875-1882.
[13] Morrison R W, DeJong K A. A test problem generator for non-stationary environments[C]//Proceedings of the 1999 Congress on Evolutionary Computation. Washington, 1999: 2047-2053.
[14] 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-173.
[15] Bergh F. An analysis of particle swarm optimizers[D]. Department of Computer Science, University of Pretoria, 2002.
[16] Blackwell T M. Particle swarms and population diversity[J]. Soft Computing, 2005, 9(11): 193-802.
[17] Brits R, Engelbrecht A P, Bergh F. Scalability of niche PSO[C]//Proceedings of the IEEE Swarm Intelligence Symp Indianapolis, 2003: 228-234.
[18] 汪定伟, 王俊伟, 王洪峰, 等. 智能优化方法[M]. 北京: 高等教育出版社, 2007.
WANG Ding-wei, WANG Jun-wei, WANG Hong-feng, et al. Intelligent optimization methods[M]. Beijing: Higher Education Press, 2007.
收稿日期：2008-08-10；修回日期：2008-10-18
基金项目：国家基础研究项目(A1420060159)
通信作者：高平安(1969-)，男，湖南娄底人，博士研究生，从事智能系统研究；电话：13307491589；E-mail: gaopa@xtu.edu.cn
