发布时间 : 星期六 文章基于群体智能的关联规则挖掘及应用更新完毕开始阅读
山东师范大学硕士学位论文
2.4.2.1 PSO算法原理概述
在由N个微粒组成的群体中,微粒Pi(i=1,2,?,N),在D 维空间中的位置信息可表示为
x(pi)?(xi?1Dpi1,xpi2,...,xpij,...,xpiD),微粒P ( i = 1,2,?,N)在D维空间中的飞
i
行速度信息可表示
v(pi)?(vj?1Dpi1,vpi2,...,vpij,...,vpiD)。根据优化目标,不断调整微粒
的飞行速度和飞行位置信息,直到满足终止条件为止。
微粒Pi (i=1,2,?,N)在D维空间中第d(d=1,?,D)维子空间中飞行速度vpid按照下式进行调整:
vpid?vpid?c1rand1(ppid?xpid)?c2rand2(ppd?xpid) (2.1)
这里vpid=vmax，如果vpid﹥vmax；vpid =-vmax，如果vpid<-vmax 加速常数c1和c2是两个非负常数。 微粒的第d维位置信息通过下式进行调整:
xpid?xpid?vpid (2.2)
PSO算法模式 (1) (2) (3)
算法选择:选用微粒群优化算法, 即ALGORITHM=PSO； 微粒群体规模:设定微粒群中微粒总数目为N；
信息集合INFORM:INFORM(ΩP)中包含了关于各个微粒的所有的信息，例如微
粒个体的位置、速度及时间等信息,也包括由优化目标约束得到的不可行信息以及算法输出的指令序列等。对微粒个体进行检测的检测信息集合DETECT(ΩP)是INFORM(ΩP)的子集。 (4)
确定待求解问题的目标优化函数AIM:根据实际的应用问题的特征，构造或转
化得到相应的目标优化函数或目标优化值。 (5)
得到修改微粒参数的指令集合：PSO算法通过对微粒个体的飞行速度(大小和
方向)进行调整,对各微粒个体给出相应的动作指令集合INSTRUCTION(ΩP),使微粒个体Pi在各维坐标上的移动。 (6)
确定特征参数CHARACTER:特征参数主要指算法中的一些主要参数，例如加速
21
山东师范大学硕士学位论文
常数c1和c2等,通常这些参数值要通过实验的方法来确定。 PSO算法的流程
PSO算法主要计算步骤如下:
(1)初始化,设定加速度常数c1和c2，最大进化代数Tmax，将当前进化代数置为t=1，在定义空间R中随机产生m个粒子x1,x2?,xm组成初始种群X(1);随机产生各粒子初始位移变化
n
v1,v2,?vm，组成位移变化矩阵V(1)。
(2) 评价种群X(t)，计算每个粒子在求解空间的适应值。
(3) 比较粒子的适应值和自身最优值pbest。如果当前值比pbest更优，则置 pbest为当前值，并设pbest位置为该粒子的当前位置值。
(4) 比较粒子适应值与种群最优值gbest。如果当前值比gbest更优，则置gbest为该粒子的当前位置值。
(5) 按式 (2.1)和(2.2)更新粒子的位移方向和步长，产生新种群 X(t+1)。
(6) 检查结束条件，若满足，则结束寻优;否则，t=t十1转至(2)。结束条件为寻优达到最大进化代数Tmax，或适应值小于给定精度?。 流程(如图2.4所示)
22
山东师范大学硕士学位论文
开始 初始化 评价粒子 更新粒子 N 终止 条件 Y 终止 (1)
图2.4 PSO算法流程图
初始化：初始搜索点的位置Xi 及其速度Vi，通常是在允许的范围内随机产
生的,每个粒子的局部最佳坐标设置为其当前位置,且计算出其相应的个体极值(即个体极值点的适应度值),而全局极值(即全局极值点的适应度值)就是个体极值中最好的,记录该最好值的粒子序号,并将gbest设置为该最好粒子的当前位置。 (2)
评价每一个粒子：计算粒子的适应度值,如果好于该粒子当前的个体极值,则
将pbest设置为该粒子的位置,且更新个体极值。如果所有粒子的个体极值中最好的好于当前的全局极值,则将gbest设置为该粒子的位置,记录该粒子的序号,且更新全局极值。 (3) (4)
粒子的更新：用公式(2)和公式(3)对每一个粒子的速度和位置进行更新。 检验是否符合结束条件：如果当前的迭代次数达到了预先设定的最大次数(或
达到最小错误要求),则停止迭代,输出最优解,否则转到(2)。
23
山东师范大学硕士学位论文
2.4.2.2参数分析
微粒群算法自出现至今,已经历了很多的调整与修正,很多研究人员对参数的选择及其对算法性能的影响进行了大量的分析和实验,为微粒群算法理论和应用的研究奠定了坚实的基础[27-28 ] 。在微粒群中,下面几个参数对算法寻优性能的影响非常显著,他们是:惯性权重ω、最大速度vmax和加速常数c1 , c2 。
（1） 惯性权重ω。ω 对于微粒群算法的收敛性起到很大的作用,ω值越大,则全局寻优能力越强,局部寻优能力越弱, 反之, 则局部寻优能力增强,而全局寻优能力减弱。通过调整ω的大小来控制以前速度对当前速度的影响, 使其成为兼顾全局搜索与局部搜索的一个折中。因为ω 大, 则速度v 就大,有利于微粒搜索更大的空间,可能发现新的解域;而ω小,则速度v 就小,有利于在当前解空间里挖掘更好的解。
(2) 最大速度vmax 。微粒群算法是通过调整每一次迭代时每一个微粒在每一维上移动的距离来进行。速度的改变是随机的,但不希望不受控制的微粒轨道扩展到越来越广阔的空间,并最终达到无穷。如果微粒要有效地搜索,必须采取某些措施使振幅衰减。传统的方法是使用一个常数vmax ,并按照式(2) 对微粒运动速度进行了规定。参数vmax有利于防止搜索发散(爆炸) ,并且可以改变微粒的搜索步长。不过, vmax值的选择需对问题有一定的先验知识。为了跳出局部最优需要较大的步长,而在接近最优值时,采用更小的步长会更好。
(3) 加速常数c1 和c2 。加速常数c1 、c2 是用来调整微粒的自身经验与社会(群体) 经验在其运动中所起作用的权重。如果c1 = 0 , 则微粒只有“社会经验”,它的收敛速度可能较快,但在处理较复杂的问题时, 容易陷入局部最优点。如果c2 =0 ,则微粒没有群体共享信息,只有“自身经验”,这时,一个规模为M的群体就因为个体间没有交互而变成了M个单微粒的运行,因而得到解的几率非常小。如果c1 = c2 = 0 ,则微粒没有任何经验的信息,微粒的运动则显得杂乱无章。
除了上述几种参数, 种群拓扑结构对群体性能的影响也是客观存在的。相对孤立的微粒搜索能力非常有限, 因为其运动过程始终缺乏信息的实时沟通。微粒群算法常用的两种种群拓扑结构分为全局最优模式和局部最优模式。在全局最优模式中,每个个体均被群体中发现最优解的个体所吸引,这种结构与完全连接的社会网络类似,每个个体都有机会和群体中的其他所有个体进行比较,并模仿最优个体的活动。在局部最优模式中,每个个体只被与其直接相连的k个个体构成的邻域中的最优个体所影响。前者与后者相比能够
24