第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。②混沌变量与收缩因子 βｔ 成比例，通过混沌扰 动产生 Ｎ 个新变量如式（１０）所示。 ｙｉｊ （ｌ＋１） ＝ ｙｉｊ （ｌ） ＋ βｔ ｚｉｊ （ｌ＋１） ｌＰＣＬＳ （１０） 式中： ｌＰＣＬＳ 为并行混沌局部搜索的范围，可将其设 置为 ０．０１ｌ ～０．１ｌ ， ｌ 为变量尺度，若 ｕｂ 、 ｌ ｂ 分别为变 量的上下界，则取 ｌ ＝ （ｕｂ － ｌ ｂ） ／ ２，收缩因子 βｔ 为 βｔ ＝ ｅ －Ｃ∗ｔ／ Ｔｍａｘ （１１） 式中：Ｃ 是一个用于控制 ＰＣＬＳ 精度的正数，根据实 验分析可在［１，１０］内选取，一般对于较难搜索到全 局最优的问题取较小值。 求得 Ｎ 个新变量组成的 矩阵为 Ｙ （ｌ＋１） ＝ ｙ１１ （ｌ＋１） ｙ１２ （ｌ＋１） … ｙ１ｍ （ｌ＋１） ｙ２１ （ｌ＋１） ｙ２２ （ｌ＋１） … ｙ２ｍ （ｌ＋１） ︙ ︙ ︙ ｙＮ１ （ｌ＋１） ｙＮ２ （ｌ＋１） … ｙＮｍ （ｌ＋１） é ë ê ê ê ê ê ê ù û ú ú ú ú ú ú （１２） ③计算每个新变量所对应的目标函数值为 ｆ（ｙｉ （ｌ＋１） ） ，并将 Ｙ （ｌ＋１） 与 ｘｐｇ （ｌ＋１） 、 ｘｐｓ （ｌ＋１） 合并，对这 Ｎ＋２ 个变量的适应度值进行排序，得到第ｌ＋１ 次迭 代中的最优解 ｘｐｇ （ｌ＋１） 和次优解 ｘｐｓ （ｌ＋１） 。 ④ｌ ＝ ｌ＋１，若 ｌ＜Ｃｍａｘ，转向①；否则转向 ４）。 ４）ｔ ＝ ｔ＋１，若 ｔ＜Ｔｍａｘ，转向 ２），且随机选取一个 萤火虫个体用 ３）中获得的 ｘｐｇ 替换并更新其亮度； 否则停止迭代，输出全局最优解。 ２．２ 提高种群多样性的策略 由于 ＦＡ 缺乏保持种群多样性的操作，降低了 算法探索到全局最优解的能力，因此需要采取一定 的措施来解决这一问题。 本文中算法每迭代 Ｎｐ次 时，找出适应度值最差的 ｎｃ％的个体并采用混沌重 构法生成新的个体替代它们。 对于各维尺度相等的 优化问题，直接计算出当前种群所有维空间的最大 值 ｘｍａｘ和最小值 ｘｍｉｎ作为各维的统一边界。 对于各 维尺度不相等的优化问题，对边界向量不断地收缩， 初始时第 ｊ 维的边界等于定义域［ａｊ，ｂｊ］，当达到第 Ｎｐ次迭代的最优个体为 ｘ ∗ ，根据式（１３）收缩边界。 ａｊ ｎｅｗ ＝ ｘｊ ∗ － φ（ｂｊ － ａｊ） ｂｊ ｎｅｗ ＝ ｘｊ ∗ ＋ φ（ｂｊ { － ａｊ） （１３） 式中： φ ∈ （０，０．５） ，并且为了保证新的边界范围不 会越界， 对其进行相应的处理为： 若 ａｊ ｎｅｗ ＜ ａｊ， 则 ａｊ ｎｅｗ ＝ ａｊ；若 ｂｊ ｎｅｗ ＞ｂｊ，则 ｂｊ ｎｅｗ ＝ ｂｊ。 然后根据式（７）的 ｌｏｇｉｓｔｉｃ 映射生成比例为 ｎｃ％的 Ｎｃ个在（０，１）上的向 量 Ｃｘｉ（ｉ ＝ １，２，…，Ｎｃ） 如式（１４）所示。 Ｃｘｉ ＝ ４ × ｙ × （１ － ｙ），ｙ ∈ （０，１） （１４） 最后再将其转换到当前种群变量的取值空间如 式（１５）所示，获得替换种群并更新其适应度值。 ｘｉ ｎｅｗ ＝ ｂ ＋ Ｃｘｉ（ｂ － ａ） （１５） 这里随着迭代次数的增加对边界范围不断收 缩，在各个不同阶段生成不同尺度的混沌变量，能够 避免直接根据初始的定义域随机生成替代个体时效 率不高的问题，且同样能够改善种群多样性。 ２．３ 改进 ＦＡ 的收敛性分析及复杂度分析 目前，ＦＡ 还没有很完备的数学理论基础［１２⁃１３］ ，但 已有的仿真实验结果表明 ＦＡ 具有较高的寻优精度 和收敛速度，是一种有效的优化方法。 本文改进算法 与基本 ＦＡ 的不同之处为迭代 Ｔｍａｘ１次后增加了 ＰＣＬＳ 过程，故只需证明 ３）过程的收敛性，即可证明 ＰＣＬＳ⁃ ＦＡ 的收敛性优于 ＦＡ。 从测度论上进行分析，由于 ＰＣＬＳ 属于下降算法，并且它具有很好的遍历性，因而 设 Ｒｇ 表示全局最优点 ｘ ∗ 的可行域。 总迭代次数为 ｔ 时（ｔ＞Ｔｍａｘ１ ），在执行 ２）后的当前最优解 ｘｐｇ 和次优解 ｘｐｓ 落入 Ｒｇ 的事件集合为 Ａ０ ， Ｐ（Ａ０ ） ≤ １， ＰＣＬＳ 每次 迭代后产生的序列矩阵 ｙ （ｌ） 且与 ｘｐｇ （ｌ） 、 ｘｐｓ （ｌ） （ｌ ＝ １， ２，…，Ｃｍａｘ）合并后落入 Ｒｇ 的事件集合为 Ａｌ，因此Ａ１⊂ Ａ２⊂ … ⊂ ＡＣｍａｘ ，概率测度单调不减，故 Ｐ（ＡＣｍａｘ ） ≥ … ≥Ｐ（Ａ２ ） ≥ Ｐ（Ａ１ ）。 可知执行 ３）之后具有更高的 概率落入全局最优点 ｘ ∗ 的可行域，故 ＰＣＬＳＦＡ 的收 敛性优于 ＦＡ，接下来通过对基准函数的仿真实验能 够进一步验证其收敛性。 此外，当忽略对目标函数的 计算时，ＦＡ 的时间复杂度为 Ｏ （ Ｔｍａｘ ∙Ｎｐｏｐ２ ），且 ＰＣＬＳＦＡ 的时间复杂度为 Ｏ（ Ｔｍａｘ ∙Ｎｐｏｐ２ ＋ Ｔｍａｘ ２ ∙ Ｃｍａｘ∙Ｎ），（Ｔｍａｘ２ ＝Ｔｍａｘ －Ｔｍａｘ １ ）。 ２．４ ＫＨＭ⁃ＰＣＬＳＦＡ 算法流程 本文采用 Ｋ⁃调和均值的目标函数 ＫＨＭ（ Ｘ，Ｃ ） 作为萤火虫 ｉ 的亮度 Ｉｉ，并以此确定其移动方向，其 本质上是将聚类问题转化为一种优化问题。 若 ｋ 为 聚类的数量，ｍ 为数据的维数，则用一个 ｋ×ｍ 列的 一维向量 ｘ ＝ （ｘ１１ ，ｘ１２ ，…，ｘ１ｍ ，…，ｘｋ１ ，ｘｋ２ ，…，ｘｋｍ ） 来表示一个聚类中心，即一个萤火虫个体。 由于算 法对初始值不敏感，可从数据集中随机选择 ｋ 个不 同的点并对其进行较小的扰动以构成一个中心向量 ｘ，确定 Ｐｓｉｚｅ个这样的向量作为种群初始位置。 由于 本文算法的总迭代次数 Ｉｔｅｒｍａｘ 较小，不需要执行粗 搜索。 综上所述，本文算法 ＫＨＭ⁃ＰＣＬＳＦＡ 的流程为： １）初始化算法的基本参数 γ、 α、β、Ｃｍａｘ、 Ｎ、ｌ 并 随机初始化萤火虫种群的位置。 ２）根据萤火虫的位置计算其目标函数值作为 亮度，初始化当前迭代次数 ｇｅｎ ＝ ０。 第 ６ 期 朱书伟，等：融合并行混沌萤火虫算法的 Ｋ⁃调和均值聚类 ·８７５·