发布时间 : 星期五 文章进化粒子群算法在TSP中的应用更新完毕开始阅读
第17页
第3章PSO算法的改进算法
自然界是丰富多彩的，我们的生活也同样多姿多彩。存在于现实生活中的不同领域的优化问题同样极其种类繁多，每个优化问题也都具备各自的特点，互不相同。
“没有免费午餐”的理论认为：不包含领域知识的算法不一定有效，但包含过多的问题领域知识也会因此导致算法对其它问题的脆弱性。
PSO算法一提出就吸引了学术界的广泛重视，目前已成为一个研究热点，各种关于PSO算法应用研究的成果不断涌现，有力地推动了PSO研究。当前已经有多种对PSO算法的改进，然而正如“没有免费午餐”的理论所认为的，这些改进算法需要针对具体问题的特点，根据领域知识对算法参数进行设置，在提高某种性能的同时也为此付出相应代价。
3.1 基于惯性权值的改进
粒子群优化算法以种群行为而不是适者生存原则来激励粒子的运动。每个潜在解与粒子运行速度相联系，该速度不停地根据粒子经验以及粒子邻居们的经验来调整大小、方向，总是希望粒子能朝着更好的方向发展。在搜索过程中，全局搜索能力与局部搜索能力的平衡关系对于算法的成功起着至关重要的作用。
为了方便讨论，这里再次列出粒子的更新公式：
'Vid??Vid?c1rand()(Pid?Xid)?c2rand()(Pgd?Xid) （3-1）
''Xid?Xid?Vid （3-2）
可以看出，公式的第一部分表示了粒子以前的速度对粒子飞行轨迹的影响，这部分提供了粒子在搜索空间飞行的动力，是粒子群优化算法中的关键部分。其中的惯性权值控制了粒子以前经历过的速度对当前速度的影响，决定上一时刻的速度将保留多少下来。因此惯性权值的设置影响了粒子的全局（广范围）搜索能力与局部（小范围）搜索能力之间的平衡。
简要解释w的效果，令c1=c2=0，设初始速度非零，则大于1.0的w将使粒子朝最大速度Vmax方向加速；小于1.0的w使粒子放慢速度，直至最终速度达到零，粒子停止了运动。Shi和Eberhart研究了w在范围P[0,1.4]的影响。其结果表明选择w∈[0.8,1.2]导致收敛加速，但是大的w值（>1.2）导致收敛失败。
由于PSO的搜索过程是非线性的且非常复杂，对搜索过程数学模型化，从而动态地修改惯性权值是非常困难的。由于惯性权值的设置对PSO算法性能的关键作用，目前已经有多个文献针对惯性权值的研究，并且对算法作了不同改进。
第18页
3.2 基于加速因子的PSO改进
从粒子的速度更新公式来看，第一部分表示了粒子当前速度对粒子飞行的影响，这部分提供了粒子在搜索空间飞行的动力。第二部分是所谓的“个体认知”部分，代表了粒子的个人经验，促使粒子朝着自身所经历过的最好位置移动。第三部分是所谓“群体认知”部分，代表了群体经验对粒子飞行轨迹的影响，促使粒子朝着群体发现的最好位置移动。
加速因子c1和c2决定了粒子本身经验信息和其他粒子的经验信息对粒子运行轨迹的影响，反映了粒子群之间的信息交流。设置较大c1的值，会使粒子过多的在局部范围徘徊，相反，较大的c2值会促使粒子过早收敛到局部最小值。Shi和Eberhart建议，为了平衡随机因素的作用，一般情况下设置c1?c2?2，大部分算法都采用这个建议。但是一般c1等于c2并且范围在0和4之间。
Clerc的研究表明，加速因子有助于保证算法收敛。Suganthan测试了一种根据叠代次数线性递减加速因子的方法，实验结果比使用加速因子固定值等于2的PSO算法差。但通过实验观察结果，他认为加速因子在搜索过程中不必保持不变。
Ratnaweera和Halgamuge在文献[8]使用根据叠代次数修改加速因子的方法进行实验，在算法初期使用较大c1值，较小c2值，允许粒子在局部范围搜索，而不是直接向全局最优位置移动；算法后期减小c1值，增大c2值，促使算法收敛。计算加速因子的公式如下：
c1?(c1f?c1i) c2?(c2f?c2i)iter?c1i （3-3）
MAXiteriter?c2i （3-4）
MAXiter实验结果表明，这种方法确实加速了算法的收敛，在单峰值函数的测试表现优异。为此付出的代价是算法容易陷入局部最小值，在多峰值函数的测试中容易过早收敛。
3.3 基于邻近群拓扑的改进
根据在公式（3-1）中对群体的全局最优位置pg的选择方法，粒子群优化算法可以分为：全局版本（gBest）和局部版本（lBest）。 ● gBest模型
在gBest模型中，选择整个群中的最优粒子作为唯一的最优解，群的所有粒子都使用相同的pg值更新自己的速度和位置，朝着这个最优粒子聚集。 ● lBest模型
第19页
在lBest模型中，粒子群根据选择的拓扑，划分为多个小种群，每个粒子根据自己所属的小种群，选择该小种群的局部最优解更新自己的速度和位置，因此，每个粒子选择的pg值不一定是全体粒子的最优位置。也就是说，更新粒子群的pg的值有多个。
图3-1反映了两个不同邻近群拓扑PSO中粒子之间的信息流向：
图3-1两种不同的邻近群拓扑的PSO
从图中可以看出，在全局PSO中，每个粒子的信息可以被其它所有粒子获得，一旦某个粒子发现较好的位置，所有粒子都会迅速聚集到该粒子周围，算法的收敛速度快，同时，粒子群也容易陷入局部最优值。在局部PSO中，由于每个粒子获得的群体最优位置的信息不一定相同，导致粒子收敛的方向不一定相同，因此算法的收敛速度比全局PSO慢，不容易陷入局部最优。因此，对邻近群拓扑的选择影响了PSO算法的性能。
基于lBest模型，产生了多种拓扑的变形，如图3-2所示。
图3-2两种变形拓扑
第20页
Kennedy的研究对不同邻近群的拓扑结构进行测试。在文献[9]也使用了不同连接拓扑的PSO进行实验。实验结果都表明了，选择一种合适的邻近群拓扑，对算法性能的影响是明显的。然而没有一种邻近群拓扑对所有基准函数都是最合适的，具体选择哪一中邻近群拓扑与具体的问题有关。例如，使用信息交流率越高的拓扑（如轮形），算法的收敛速度越快，适用于单峰值分布的函数。这再次验证了“免费午餐理论”。
3.4 基于种群规模的改进
粒子群的大小也是标准粒子群优化算法的关键参数之一，粒子数太少，容易使粒子在陷入局部最小值，粒子数太多会减慢算法的速度。大多数的实验使用的粒子数为20～40个。同样的，粒子数的选择于具体问题有关。
通常情况下，群大小是一个常数，群粒子的数目在算法运行中保持不变。但是，仍无法提出一个最优的群大小。所以，算法中不时地改变群大小似乎更有优势。Clerc提出了动态调整种群的规模的想法：
● 如果种群的改进质量达不到预设置的阈值，那么如果一个粒子是所在邻近群中的最优粒子，为种群增加一个自己的复制
● 如果种群的改进质量达到了预设置的阈值，那么如果一个粒子是所在邻近群中的最差粒子，把该粒子消灭
Clerc设置了一个能量函数，用来评价固定规模PSO和动态规模PSO的性能变化。单个粒子的能量计算公式如下：
epi(t)?|f(xi(t))|? （3-5）
整个种群的能量由下式计算：
Ep(t)?G?ep.i(t) （3-6）
通过观测种群和粒子的能量在算法运行过程中的变化，Clerc认为，针对具体函数，一个合适的固定的种群规模的PSO要比动态调整种群规模的PSO性能更好。但是在需要通过多次尝试才能找到合适种群规模的情况下，使用动态调整种群规模的方法可以节省时间。
i