正在加载图片...
第6期 朱书伟,等:融合并行混沌莹火虫算法的K-调和均值聚类 ·875· ②混沌变量与收缩因子B,成比例,通过混沌扰 式(15)所示,获得替换种群并更新其适应度值。 动产生N个新变量如式(10)所示。 x"M=b+Cx;(b-a) (15) y)=y(+B(Iras (10) 这里随着迭代次数的增加对边界范围不断收 式中:lrs为并行混沌局部搜索的范围,可将其设 缩,在各个不同阶段生成不同尺度的混沌变量,能够 置为0.01l~0.11,1为变量尺度,若6、l分别为变 避免直接根据初始的定义域随机生成替代个体时效 量的上下界,则取1=(u,-1,)/2,收缩因子B,为 率不高的问题,且同样能够改善种群多样性。 B=e-cvTn (11) 2.3改进FA的收敛性分析及复杂度分析 式中:C是一个用于控制PCLS精度的正数,根据实 目前,FA还没有很完备的数学理论基础[2),但 验分析可在[1,10]内选取,一般对于较难搜索到全 已有的仿真实验结果表明FA具有较高的寻优精度 局最优的问题取较小值。求得N个新变量组成的 和收敛速度,是一种有效的优化方法。本文改进算法 矩阵为 与基本FA的不同之处为迭代T,次后增加了PCLS (1+1) y11 2+) …yw7 过程,故只需证明3)过程的收敛性,即可证明PCLS 31) y2(1 …y2*0 FA的收敛性优于FA。从测度论上进行分析,由于 (12) PCLS属于下降算法,并且它具有很好的遍历性,因而 (1+1) 设R表示全局最优点x·的可行域。总迭代次数为t LYMI 时(t>T,),在执行2)后的当前最优解xg和次优解 ③计算每个新变量所对应的目标函数值为 fy,”),并将y+w与xw”、x+》合并,对这 x落入R的事件集合为A,P(A,)≤1,PCLS每次 N+2个变量的适应度值进行排序,得到第l+1次迭 迭代后产生的序列矩阵y”且与x”、x0(1=1, 代中的最优解x网)和次优解xn。 2,…,C)合并后落入R的事件集合为A,因此AC ④=l+1,若l<C,转向①;否则转向4)。 A,C…CAc,概率测度单调不减,故P(Ac)≥ …≥P(A2)≥P(A)。可知执行3)之后具有更高的 4)t=t+1,若t<Tmx,转向2),且随机选取一个 萤火虫个体用3)中获得的x替换并更新其亮度; 概率落入全局最优点x·的可行域,故PCLSFA的收 敛性优于FA,接下来通过对基准函数的仿真实验能 否则停止迭代,输出全局最优解。 够进一步验证其收敛性。此外,当忽略对目标函数的 2.2提高种群多样性的策略 由于FA缺乏保持种群多样性的操作,降低了 计算时,FA的时间复杂度为O(Ts·N2),且 算法探索到全局最优解的能力,因此需要采取一定 PCLSFA的时间复杂度为O(Tm·Np2+T2· 的措施来解决这一问题。本文中算法每迭代V。次 Cmx·N),(Tnma=Tnax-Tmxi)。 2.4KHM-PCLSFA算法流程 时,找出适应度值最差的n%的个体并采用混沌重 本文采用K-调和均值的目标函数KHM(X,C) 构法生成新的个体替代它们。对于各维尺度相等的 优化问题,直接计算出当前种群所有维空间的最大 作为萤火虫i的亮度1:,并以此确定其移动方向,其 值xmm和最小值xmn作为各维的统一边界。对于各 本质上是将聚类问题转化为一种优化问题。若k为 维尺度不相等的优化问题,对边界向量不断地收缩, 聚类的数量,m为数据的维数,则用一个k×m列的 初始时第j维的边界等于定义域[a,b],当达到第 一维向量x=(x1,x2,…,xm,…,x1,x2,…,xm) 来表示一个聚类中心,即一个萤火虫个体。由于算 N,次迭代的最优个体为x·,根据式(13)收缩边界。 法对初始值不敏感,可从数据集中随机选择k个不 %=考-o(6,-a) (13) 同的点并对其进行较小的扰动以构成一个中心向量 (b"ew=x·+p(b-a) x,确定P个这样的向量作为种群初始位置。由于 式中:p∈(0,0.5),并且为了保证新的边界范围不 本文算法的总迭代次数Itermax较小,不需要执行粗 会越界,对其进行相应的处理为:若a"<a,则 搜索。 g=a;若b,>b,则6=b。然后根据式(7)的 综上所述,本文算法KHM-PCLSFA的流程为: logistic映射生成比例为n.%的N个在(0,1)上的向 1)初始化算法的基本参数y、aB、Cms、N、l并 量Cx(i=1,2,…,N)如式(14)所示。 随机初始化萤火虫种群的位置。 Cx:=4×y×(1-y),y∈(0,1)(14) 2)根据萤火虫的位置计算其目标函数值作为 最后再将其转换到当前种群变量的取值空间如 亮度,初始化当前迭代次数gen=0。②混沌变量与收缩因子 βt 成比例,通过混沌扰 动产生 N 个新变量如式(10)所示。 yij (l+1) = yij (l) + βt zij (l+1) lPCLS (10) 式中: lPCLS 为并行混沌局部搜索的范围,可将其设 置为 0.01l ~0.1l , l 为变量尺度,若 ub 、 l b 分别为变 量的上下界,则取 l = (ub - l b) / 2,收缩因子 βt 为 βt = e -C∗t/ Tmax (11) 式中:C 是一个用于控制 PCLS 精度的正数,根据实 验分析可在[1,10]内选取,一般对于较难搜索到全 局最优的问题取较小值。 求得 N 个新变量组成的 矩阵为 Y (l+1) = y11 (l+1) y12 (l+1) … y1m (l+1) y21 (l+1) y22 (l+1) … y2m (l+1) ︙ ︙ ︙ yN1 (l+1) yN2 (l+1) … yNm (l+1) é ë ê ê ê ê ê ê ù û ú ú ú ú ú ú (12) ③计算每个新变量所对应的目标函数值为 f(yi (l+1) ) ,并将 Y (l+1) 与 xpg (l+1) 、 xps (l+1) 合并,对这 N+2 个变量的适应度值进行排序,得到第l+1 次迭 代中的最优解 xpg (l+1) 和次优解 xps (l+1) 。 ④l = l+1,若 l<Cmax,转向①;否则转向 4)。 4)t = t+1,若 t<Tmax,转向 2),且随机选取一个 萤火虫个体用 3)中获得的 xpg 替换并更新其亮度; 否则停止迭代,输出全局最优解。 2.2 提高种群多样性的策略 由于 FA 缺乏保持种群多样性的操作,降低了 算法探索到全局最优解的能力,因此需要采取一定 的措施来解决这一问题。 本文中算法每迭代 Np次 时,找出适应度值最差的 nc%的个体并采用混沌重 构法生成新的个体替代它们。 对于各维尺度相等的 优化问题,直接计算出当前种群所有维空间的最大 值 xmax和最小值 xmin作为各维的统一边界。 对于各 维尺度不相等的优化问题,对边界向量不断地收缩, 初始时第 j 维的边界等于定义域[aj,bj],当达到第 Np次迭代的最优个体为 x ∗ ,根据式(13)收缩边界。 aj new = xj ∗ - φ(bj - aj) bj new = xj ∗ + φ(bj { - aj) (13) 式中: φ ∈ (0,0.5) ,并且为了保证新的边界范围不 会越界, 对其进行相应的处理为: 若 aj new < aj, 则 aj new = aj;若 bj new >bj,则 bj new = bj。 然后根据式(7)的 logistic 映射生成比例为 nc%的 Nc个在(0,1)上的向 量 Cxi(i = 1,2,…,Nc) 如式(14)所示。 Cxi = 4 × y × (1 - y),y ∈ (0,1) (14) 最后再将其转换到当前种群变量的取值空间如 式(15)所示,获得替换种群并更新其适应度值。 xi new = b + Cxi(b - a) (15) 这里随着迭代次数的增加对边界范围不断收 缩,在各个不同阶段生成不同尺度的混沌变量,能够 避免直接根据初始的定义域随机生成替代个体时效 率不高的问题,且同样能够改善种群多样性。 2.3 改进 FA 的收敛性分析及复杂度分析 目前,FA 还没有很完备的数学理论基础[12⁃13] ,但 已有的仿真实验结果表明 FA 具有较高的寻优精度 和收敛速度,是一种有效的优化方法。 本文改进算法 与基本 FA 的不同之处为迭代 Tmax1次后增加了 PCLS 过程,故只需证明 3)过程的收敛性,即可证明 PCLS⁃ FA 的收敛性优于 FA。 从测度论上进行分析,由于 PCLS 属于下降算法,并且它具有很好的遍历性,因而 设 Rg 表示全局最优点 x ∗ 的可行域。 总迭代次数为 t 时(t>Tmax1 ),在执行 2)后的当前最优解 xpg 和次优解 xps 落入 Rg 的事件集合为 A0 , P(A0 ) ≤ 1, PCLS 每次 迭代后产生的序列矩阵 y (l) 且与 xpg (l) 、 xps (l) (l = 1, 2,…,Cmax)合并后落入 Rg 的事件集合为 Al,因此A1⊂ A2⊂ … ⊂ ACmax ,概率测度单调不减,故 P(ACmax ) ≥ … ≥P(A2 ) ≥ P(A1 )。 可知执行 3)之后具有更高的 概率落入全局最优点 x ∗ 的可行域,故 PCLSFA 的收 敛性优于 FA,接下来通过对基准函数的仿真实验能 够进一步验证其收敛性。 此外,当忽略对目标函数的 计算时,FA 的时间复杂度为 O ( Tmax ∙Npop2 ),且 PCLSFA 的时间复杂度为 O( Tmax ∙Npop2 + Tmax 2 ∙ Cmax∙N),(Tmax2 =Tmax -Tmax 1 )。 2.4 KHM⁃PCLSFA 算法流程 本文采用 K⁃调和均值的目标函数 KHM( X,C ) 作为萤火虫 i 的亮度 Ii,并以此确定其移动方向,其 本质上是将聚类问题转化为一种优化问题。 若 k 为 聚类的数量,m 为数据的维数,则用一个 k×m 列的 一维向量 x = (x11 ,x12 ,…,x1m ,…,xk1 ,xk2 ,…,xkm ) 来表示一个聚类中心,即一个萤火虫个体。 由于算 法对初始值不敏感,可从数据集中随机选择 k 个不 同的点并对其进行较小的扰动以构成一个中心向量 x,确定 Psize个这样的向量作为种群初始位置。 由于 本文算法的总迭代次数 Itermax 较小,不需要执行粗 搜索。 综上所述,本文算法 KHM⁃PCLSFA 的流程为: 1)初始化算法的基本参数 γ、 α、β、Cmax、 N、l 并 随机初始化萤火虫种群的位置。 2)根据萤火虫的位置计算其目标函数值作为 亮度,初始化当前迭代次数 gen = 0。 第 6 期 朱书伟,等:融合并行混沌萤火虫算法的 K⁃调和均值聚类 ·875·
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有