Step2.4:
对每个粒子,依据公式(2.1b)、(2.2b)更新V[i]和X[i]值
2.4PSO算法的改进
2.4.1加入惯性权重因子w的PSO算法[6]
正如先前所述,公式(2.1a)由三部分组成:
第一部分是粒子先前的速度项,即
,第二部分和第三部分是导致粒子速度变化的两项,即
和
。
一方面,公式(2.1a)如果没有后两项,粒子将保持在相同的方向上以当前的速度“飞翔”至下一个点,直至达到边界值。
这样的PSO将不能找到一个可接受的解,除非这样的飞行轨迹是一种合理的方案,而这在现实中是非常少见的。
另一方面,如果公式(2.1a)没有第一项,那么“飞翔”粒子的速度仅仅取决于粒子的当前位置和它们最好的历史位置。
速度自身是没有记忆性的。
假设在开始的时候,粒子i正好是整体最好所在的点,那么粒子i将以速度为0“飞翔”,这将保持粒子此次的位置不变,直到出现新的一个最好点替代粒子i。
同时,每一个粒子将向自身最好点和整体最好点的质心方向“飞翔”。
推荐c1和c2都取常数2,这正如文献[7]中提到的那样,这样使得“社会认知”和“个体经验”的权重为l。
在这种状况下,各个粒子逐渐的向当前最好的位置处收缩,直到出现新的最好值,而那样粒子群体又向这个位置收缩。
因此可以想象,在没有第一项情况下的PSO搜索过程,其搜索空间将在迭代中逐渐衰退,这类似与局部搜索算法。
只有当全局最好点包含在初始搜索空间内的时候,才有可能找到满意解。
这样,最终解在很大程度上要依赖于初始化种群。
这也说明了在没有第一项内容的情况下,PSO算法更多的显现的是局部搜索能力。
从另一层意思来说,第一项内容使得粒子有一种扩展搜索空间的能力,即开拓能力(exploreability),是一种全局搜索能力的表现。
在各类问题的解决,局部搜索和全局搜索都起着重要作用。
对于某一类优化问题的具体解决中,我们应该权衡局部搜索和全局搜索的贡献。
我们可以考虑在公式(2.1a)中引入一个惯性权重因子W,以起到权衡全局搜索和局部搜索能力。
惯性权重因子w可以是个正整数常数,也可以是以时问为变量的线性或非线性正整数。
这样公式(2.la)(2.2a)就变为:
(2.1b)
(2.2b)
以上的算法公式中所涉及到的参数较少,算法也相对比较简单,可将此称为基本粒子群优化算法(SimpleParticleSwarmOptimization,SPSO)。
2.4.2拓扑结构的研究(参考王晗丁的PSO综述)
对于粒子群拓扑结构的研究最早是源于对于gbest和pbest两种拓扑结构的研究,gbest为整个粒子群的最优者,而pbest为粒子邻居中的最优者。
gbest结构允许信息在整个种群中传播,粒子跟随gbest,因此该结构的收敛速度比较快,同时多样性的保持较差,较容易陷入局部最优。
相反的,pbest结构中,粒子跟随相应的pbest飞行,相当于在多个区域内搜索,且信息是逐步通过邻居扩散出去的,因此在收敛速度上相比gbest结构相对慢,但其多样性的保持较好[8]。
上述两种结构是研究的比较多的结构,也有一些其他的新的结构在实验结果上也有较好的效果。
gbest环形结构方形结构vonNeumann结构
除此之外还有其他策略也与拓扑结构有关,划分子群策略[9][10]和小生境技术[11]可以很好的保持整个种群的多样性,文献[12]是以每个变量为一个子群,通过子群间的合作来进行优化的。
第三章基本PSO与其他进化算法的比较与结合
3.1基本PSO与其他算法的比较
3.1.1相似点
粒子群算法与其他进化算法有许多相似之处。
首先,粒子群算法和其它进化算法都使用“种群”概念(Swarm),用于表示一组解空间中的个体集合。
两者都随机初始化种群,都使用适应值来评价个体,而且都根据适应值来进行一定的随机搜索,两个算法都不能保证一定找到最优解[13]。
如果将粒子所持有的最好位置也看作种群的组成部分,则粒子群的每一步迭代都可以看作是一种弱化的选择机制[14]。
在(μ+λ)进化策略算法中,子代与父代竞争,若子代具有更好的适应值,则子代将替换父代,而PSO算法的进化方程式也具有与此类似的机制,只有当粒子的当前位置与所经历的最好位置相比具有更好的适应值时,所经历的最好位置才会唯一地被当前的位置所替代。
可见PSO算法中也隐藏着一定形式的“选择”机制。
PSO和GA都具有隐含并行性。
搜索过程是从问题解的一个集合开始的,而不是从单个个体开始,从而减小了陷入局部极小的可能性。
这种并行性易于在并行计算机上实现,以提高算法的性能和效率。
3.1.2不同点
与GA等其他进化算法比较,PSO具有独特的信息共享机制。
在GA中,染色体互相共享信息,所以整个种群的移动是比较均匀地向最优区域移动。
在全局版PSO中,只有全局最优粒子提供信息给其他的粒子,这是单向的信息流动,整个搜索更新过程是跟随当前最优解的过程。
与遗传算法比较,所有的粒子很可能更快地收敛于最优解。
PSO算法与其他进化算法的另一个重要不同点在于它在进化过程中同时保留和利用位置与速度信息,而其它进化算法仅保留和利用位置信息。
从以上分析中看,基本PSO算法与其他进化算法有相似之处,但同时也具备其它算法不具备的特性,特别的是PSO算法同时将粒子的位置与速度模型化,并给出了它们的进化方程。
3.2基本PSO与其他算法的结合
PSO与一般的EA有相似之处,也有很多的不同点[15],PSO没有进化意义层面上的交叉、变异和选择算子,但是通过文献[16]可知一般意义上的交叉和变异都是很低效的,然而PSO是有指导的选择交叉的父代以及变异的方向,但PSO得选择机制是很弱的,只是保留了全局最优以及个人最优。
因此目前主流EA与PSO结合的算法就是在PSO中添加交叉[17]、差分[18]、变异[19]和选择[20]算子。
除与其他EA结合的PSO之外,PSO与其他算法结合也有较好的的效果,如正交量子群优化(OPSO,OrthogonalParticleSwarmOptimization)[21]等。
第四章PSO算法的发展
PSO算法概念简单容易实现,其代码只有短短的几行,和其他优化算法相比,这也是它的优点之一。
短短几年里,PSO算法己经获得了很大的发展,并已在一些领域得到应用。
但是它的缺点是易陷入局部极小点,搜索精度不高,因此研究者们对其作了各种各样的改进。
现在已经从PSO基本算法发展出许多不同的版本,这些版本是对基本PSO算法的改进或者是在某一方面应用领域的延伸。
4.1自适应PSO(AdaptiveParticleSwarmOptimization,APSO)
我们已经研究了惯性因子w对优化性能的影响,发现较大的w值有利于跳出局部极小点,而较小的w值有利于算法收敛,因此提出了自适应调整w的策略,即随着迭代的进行,线性地减小w的值。
这种方法的进一步发展是用模糊规则动态地修改w的值[27],即构造一个2输入、l输出的模糊推理机来动态地修改惯性因子w。
模糊推理机的两个输入分别是当前w值,以及规范化的当前最好性能演化(thenormalizedcurrentbestperformanceevaluation,NCBPE):
而输出是w的增量。
CBPE是PSO算法迄今为止发现的最好候选解的性能测度。
CBPE可以有不同的定义方法,但是一般CBPE可以定义为最好候选解的适应值。
NCBPE用下式计算:
其中
和
分别是
可能取值的上下限。
模糊推理机的输入、输出的论域定义为3个模糊集合:
LOW,MEDIUM和HIGH,相应的模糊隶属度函数分别是leftTriangle,Traingle,rightTriangle,其中文献[27]给出的这三种模糊隶属度函数的定义分别如下:
leftTrangle的定义:
Triangle的定义:
rightTriangle的定义:
模糊度函数的图形如下:
图2.2]
图2.2模糊度函数
文献[27]也为模糊推理机定义了9条规则进行模糊推理,决定当前w的增量。
对于一些基准函数,如Rosennbrock、Rasrigrin、Griewank的试验结果表明,这一类自适应PSO算法都能取得满意的结果,同样也适用于许多优化问题。
通过自适应调整全局系数,兼顾搜索效率和搜索精度,是一类有效的算法。
但对许多复杂的非线性优化问题,试图通过自适应调整一个全局系数提高搜索精度的余地是有限的。
4.2混合PSO(HybridParticleSwarmOptimization,HPSO)
借鉴遗传算法的思想,文献[22,23]最早提出了混合PSO算法(HybridPSO,HPSO)的概念。
混合PSO算法是将基本PSO算法和选择机制相结合而得到的,基本PSO算法的搜索过程很大程度上依赖pbest和gbest,它的搜索区域受到pbest和gbest的限制。
在通常的进化算法中,选择机制用来选择相对较好的区域和淘汰较差的区域。
可以更合理地分配有限的资源。
混合PSO算法的选择机制与其它进化算法十分相似,如遗传算法。
混合PSO算法计算每个个体基于当前位置的适应值,并将这些适应值进行排序,然后将群体中一半适应值差的个体的当前位置和速度替换为另一半好的个体的当前位置和速度,但保留每个个体的最好位置pbest。
因此,群体搜索集中到相对较优的空间,但还受到个体自身以前最好位置的影响。
混合PSO算法的流程如下:
1)初始化所有粒子;
2)评价每个粒子的适应值;
3)使用适应值对粒子进行选择;
4)调整粒子的搜索位置,粒子从新的位置开始搜索;
5)检查终止条件.如果达到最大迭代次数或者最好解停滞不再变化,就终止迭代;否则回到步骤
(2)。
混合PSO算法的流程如图2.3
图2.3混合PSO算法的流程图
文献[24]进一步提出具有繁殖和子群的HPSO算法。
粒子群中的粒子被赋予一个杂交概率,这个杂交概率是用户确定的,与粒子的适应值无关。
在每次迭代中,依据杂交概率选取指定数量的粒子放入一个池中。
池中的粒子随机地两两杂交,产生同样数目的孩子粒子,并用孩子粒子代替父母粒子,以保持种群的粒子数目不变。
孩子粒子的位置由父母粒子的位置的算术加权和计算,即
(2.3)
(2.4)
其中
是D维的位置矢量,而
和
,k=1,2分别指明是孩子粒子还是父母粒子的位置;
是D维均匀分布的随机数向量,为杂交概率,
的每个分量都在[0,1]取值。
孩子粒子的速度分别由下面的公式得到:
(2.5)
(2.6)
其中
是D维的速度矢量,而
和
,k=l,2分别指明是孩子粒子还是父母粒子的速度。
对局部版的PSO算法而言,相当于在一个种群中划分了若干个子群,因此,杂交操作既可以在同一子群内部进行,也可以选择再不同的子群之间进行。
同时,在文献[22-24]的实验结果显示,HPSO算法的收敛速度比较快,搜索精度也相对比较高,对一类非线性优化问题可以得到满意的结果。
不过引入了较多的待调整参数,对使用者的经验有一定要求。
4.3协同PSO(CooperativeParticleSwarmOptimization,CPSO)
文献[25,28]提出了一种协同PSO算法,其基本思想是用K个相互独立的粒子群分别在D维的目标搜索空间中的不同维度方向上进行搜索。
具体做法是:
选定划分因子(splitfactor)K和粒子群的粒子数M,将输入的D维向量(粒子的位置及速度向量)划分到K个粒子群。
前(DmodK)个粒子群,其粒子的位置及速度向量都是D/K维的;而后K一(DmodK)个粒子群,其粒子的位置及速度向量也是D/K维的。
在每一步迭代中这K个的粒子群相互独立地进行状态更新,粒子群之间不共享信息。
计算适应值时,将每个粒子群中最优粒子的位置向量拼接起来,组成D维向量并代入适应函数计算适应值。
例如,考虑有24个自变量的优化问题,即D=24。
如果选取M=10,K=5,那么每个粒子的位置及速度向量的维数就是D/K=5。
这种协同PSO算法有明显的“启动延迟”[25](startupdelay)现象,在迭代初期,适应值下降缓慢,换言之,收敛速度慢。
文献[27]的实验结果显示粒子群数目越大,收敛越慢。
不过这种协同PSO算法因为实际上采用的是局部学习策略,因此比基本PSO算法更易跳出局部极小点,达到较高的收敛精度。
4.4离散PSO(DiscreteParticleSwarmOptimization)
PSO的基本算法最初是用来对连续函数进行优化的。
而实际中许多问题是组合优化向题,因此,Kennedy和Eberhart博士在基本PSO算法[26]的基础上发展了离散二进制版PSO算法来解决这一类问题。
离散二进制版PSO算法与基本PSO算法的主要区别在于运动方程(即公式
(1),
(2)),离散二进制版PSO算法的运动方程如下:
(2.7)
(2.8)
式(2.8)中,
是sigmoid函数;
是随机矢量
的第d维分量,粒子的位置只有(o,1)两种状态,而速度V与某个概率的门限值相关,速度越大,则粒子位置取1的可能性越大,反之越小。
在式(2.7)中没有权重函数w对速度进行调节。
为防止速度V过大,可以设置Vmax,使函数sig(V)不会过于接近0或1,以保证一定的概率使算法从一种状态跃迁到另一种状态。
从上文可以看出,除了式(2.7),(2.8)不同,离散二进制版的PSO算法与基本PSO算法几乎一样。
而文献[27]推广了这一工作,研究了离散版的PSO算法,并将其应用于旅行商问题(TSP)的求解。
离散PSO算法扩展了基本PSO算法的应用领域,尤其是让人看到了在一类组合优化问题中的应用前景。
但是,正如文献[26]指出的那样,PSO算法的优势在于求解一些连续函数的优化问题,目前的离散PSO算法在组合优化这类问题上未能有如同蚁群算法那样有优势。
第五章PSO的应用
已经有一些利用PSO算法代替反向传播算法来训练神经网络的论文,研究表明PSO算法是一种很有潜力的神经元网络训练算法。
PSO算法速度比较快而且可以得到比较好的结果,还没有遗传算法碰到的问题[29]。
PSO算法被用于选择BP神经元网络的权值[30]。
文献[30]使用BP神经网络的输入层、隐含层和输出层分别有5个、3个和1个神经元。
他们使用标准BP算法训练,需要大约3.5小时,而使用PSO算法以后,训练时间降为2.2分钟。
此外,用PSO算法进化神经网络的一个成功例子是用于分析人的颤抖。
对人的颤抖的诊断,包括帕金森(Parkinson)病和原发性振颤(EssentialTremor),是一个非常有挑战性的领域[31]。
PSO算法被应用于进化一个神经网络这个进化神经网络能快速和准确地辨别正常颤抖和病态颤抖。
PSO算法也被成功地应用于电力系统领域[32-35],这里主要涉及到带有约束条件的,使用不同版本的PSO算法相结合用来决定对连续和离散的控制变量的控制策略的问题。
PSO算法和其它演化计算算法类似,能用于求解大多数优化问题,比如多元函数的优化问题,包括带约束的优化问题[36]。
此外,PSO还在动态问题[37]和多