【关键词】算法,网格,资源,聚类,均值,C,混合,优化,模糊,基于,
聚类的准则为min{Jm(U,V)},应用拉格朗日乘法,结合约束条件∑ci=1μik?=1,可得使Jm?(U,V)为最小的μik?的值为
μik?=1∑cj=1dik?djk??2/m-1?(2)
同理可以获得Jm(U,V)为最小时,聚类中心vi的值:
vi=1∑nk=1(μik?)m∑nk=1(μik?)mxk(3)
下面给出FCM算法的具体步骤:
a)初始化参数。给定聚类类别数c,设定迭代停止阈值ε,初始化聚类中心V,设置迭代计数器t。
b)根据式(2)计算隶属度矩阵U。
c)根据式(3)更新聚类中心V,并计算Jm(U,V)。
d)如果Jmt(U,V)-Ji?t-1?(U,V)<ε,则算法停止并输出划分矩阵U和聚类中心V;否则令t=t+1,转向步骤a)。
2 基于GA操作的PSO混合算法
2.1 PSO简介
粒子群算法(PSO)是一种典型的群体智能算法,可以在没有集中控制、不提供全局模型的前提下,很好地解决复杂性问题。其基本思想是受到早期对鸟类群体行为研究结果的启发,粒子可以根据它本身和同伴的飞行经验来动态调整飞行速度,从而改变自己当前的位置,完成粒子在搜索空间的寻优过程。
假设在一个d维的搜索空间中,由m个代表潜在问题解的粒子组成一个粒子群。其中每个粒子表示一个d维的向量,记为xi=(xi1?,xi2?,…,xid?),i=1,2,…,m,即第i个粒子在d维的搜素空间中的位置是xi。将xi代入一个与求解问题相关的目标函数中,可计算出其适应度值,然后根据适应度值的大小评价xi的优劣。用pbest?记录第i个粒子自身搜索到的最好点(计算得到的适应值目前最优)。在整个粒子群中,至少有一个粒子的适应值是全局最优的,将其记录为gbest?。另外每个粒子还有个速度变量,也是一个d维向量,记为vi=(vi1?,vi2?,…,vid?),i=1,2,…,m。
PSO算法中粒子的位置、速度更新计算式如下:
vi?k+1?=wvik+c1r1(pbest?(i)-xi)+c2r2(gbest?-xi)(4)
xi?k+1?=xik+vi?k+1?(5)
其中:i=1,2,…,m;学习因子c1、c2一般取值为2;r1、r2是均匀分布在[0,1]的两个随机数;w是惯性权重;k为迭代次数。
2.2 基于GA操作的PSO算法
众所周知,PSO在寻找最优解的效率上好于遗传算法[5,6],但是PSO没有遗传操作(如选择、交叉、变异),而是根据自己的速度来决定搜索过程,这样在算法收敛的情况下,所有的粒子都趋向同一最优解,约束了粒子的多样性。因此,以粒子群算法为模板,在粒子群原始操作的基础上增加遗传操作[7],可以融合GA与PSO两者的优势,达到更快的收敛速度及更高的搜索精度。下面介绍基于GA操作的PSO算法优化过程。
1)选择 根据个体适应度,按照赌轮选择法,从粒子群中选择出M(偶数)个优良的个体。
2)交叉 对选出的M个个体,以交叉概率pc在随机产生的编码长度k处断点进行交叉,产生M个更优良的新个体。
xi=xi1?xi2?…xik?xik+1?…xil??xj=xj1?xj2?…xjk?xjk+1?…xjl??交叉后??xi?^=xi1?xi2?…xik?xjk+1?…xjl?
xi?^=xj1?xj2?…xjk?xik+1?…xil?
vi=vi1?vi2?…vik?vik+1?…vil?
vj=vj1?vj2?…vjk?vjk+1?…vjl??交叉后?
vi??^=vi1?vi2?…vik?vjk+1?…vjl?
vj?^=vj1?vj2?…vjk?vik+1?…vil?
3)变异 变异操作是保持种群多样性的有效手段,交叉结束后的全部个体的编码位按变异概率pm随机改变。pm过小、过大都会影响算法的收敛速度和搜索精度,不利于实现提高全局搜索能力的目的。
3 基于GA?PSO混合优化的模糊C均值算法
经过以上介绍分析,可以知道FCM是通过梯度下降的方法来寻优的,这样就存在局部最优问题。另外FCM的收敛速度对初始值的设定很敏感,尤其在聚类样本集较大的情况下。基于遗传操作的PSO优化算法有很强的全局搜索能力,收敛速度快,而且有很高的搜索精度,本文将两者结合,提出了一种新的混合模糊聚类。
3.1 算法思想
FCM的核心就是确定聚类中心,所以基于GA操作的PSO算法对聚类中心进行编码。粒子均由c个聚类中心组成,每个粒子对应一种聚类方法,即粒子xi={ai1?,ai2?,…,aic?}。其中aij?代表第i种聚类方式的第j个聚类中心,即如果样本集有n个粒子,则有n种聚类方式。
方案的优劣用适应度函数来评判,这里的适应度函数即为FCM聚类准则函数公式加上常数的倒数。即
f(xi)=1Jm(U,V)+δ(6)
其中:δ为一给定的常数,一般取1。
如果聚类效果越好,适应度函数值就越高。
另外很重要的一点就是遗传操作触发的条件:当中止条件f ?t+1?(xi)-f t(xi)<ε未满足时,检查一段时间内粒子的pbest?和gbest?,若这两个向量没有变化,则认为迭代陷入循环,此时遗传操作触发。
3.2 算法流程
下面给出算法详细的流程:
a)初始化参数。给定模糊化程度常数m,阈值ε,粒子群规模N,迭代计数器t。
b)初始化粒子群。随机选出c个样本作为一个聚类中心集(一个粒子),共进行N次,即形成规模为N的粒子群。随机产生每个粒子的初始速度vi,给定学习因子c1、c2,权?重w。?
c)对粒子群进行编码。采用实数编码,一个编码对应一个可行解。编码结构如下:
x11?…x1s?x21?…x2s?…xc1?…xcs?
