第6期 朱书伟，等：融合并行混沌莹火虫算法的K-调和均值聚类 ·873. 优化算法进行改进，以充分利用其全局搜索能力，如 这里采用欧式距离计算样本到聚类中心的 融合粒子群)、变邻域搜索)、改进候选组搜索) 距离，参数p对算法的性能具有重要的影响，且 等混合聚类算法。此外，将模糊概念引入KHM中 当p≥2时聚类的效果比较好2]。算法通过不断 也得到了一定的关注6)。目前，各种群智能优化 地迭代使目标函数值不断减小并保持稳定，每次 算法已被广泛地应用于各个领域中[81)，并且依据 迭代过程中，各个簇的中心点c()=1,2,…,k)的 没有免费的午餐定律，本文提出新的混合聚类算法。 更新如下[3) 萤火虫算法(firefly algorithm,FA)是由剑桥学者 Yang等[2.1)在2008年提出的一种新颖的群智能算 ∑，mw(c/x)XU(x)Xx i=1 (2) 法，具有结构简单、可调参数少、宜于并行处理等特 点，可以有效解决各种优化问题，并能够成功应用到 ∑mum(cy/x,)X0uw() 聚类问题中提高算法的准确性和鲁棒性[。很多 式中：成员函数m和权重函数wKv的定义分别为 学者已经对它开展了不少研究工作，引入混沌原理 式(3)和式(4)。 改进的FA具有一定的优势，Fister等[s]对现有的混 Ix:-c‖p-2 mkH(C/x:）= (3) 沌萤火虫算法(chaos-based firefly algorithm,CFA) lx-l-p-2 进行了总结，它们的主要思想都是基于算法参数的 改进，其中Gandomi等[u6]采用各种混沌映射模型进 x-6 WKHM(x:）= (4) 行了比较全面的对比分析。然而，仅对参数的调整 (,g-6) 无法更全面有效地利用混沌优化的优点，混沌局部 1.2 萤火虫算法的相关定义 搜索(chaotic local search,CLS)[91o]是一种能够有 在FA中萤火虫彼此吸引主要取决于2个因 效提高算法优化性能的策略。 素：亮度和吸引度。亮度决定了个体所处位置的好 本文从进一步提高FA的优化性能出发，提出 坏及其移动方向，吸引度决定了移动的距离，通过亮 一种新颖的CFA,并将其融入到KHM以获得一种 度和吸引度的不断更新，实现目标优化。通常直接 更有效的混合聚类方法。在FA中引入一种并行混 利用目标函数值的大小表示萤火虫i的亮度I,即 沌局部搜索策略，将CLS与并行混沌优化(parallel L=f:),x:=[xax2…xa]。FA的相关定 chaotic optimization,PC0)[7-l8]相结合，提高FA的 义如下12.13 局部搜索能力，具有更高的搜索效率，并能够有效避 定义1萤火虫i与j之间的吸引度为 免局部最优。将这种改进的CFA融入到KHM中优 B=Boe-r (5) 化其目标函数，通过对实际数据集的实验可以看出 式中：B。为在r=0处的吸引度，一般可取值为1；y 本文所提的聚类算法能够获得更好的性能指标，有 为光强吸收系数，对算法的性能具有重要的影响，通 效抑制了陷入局部最优的问题。 常情况下可以取y=1;r,为萤火虫i与j之间的空 1算法概念与定义 间距离，一般采用欧氏距离计算。 定义2萤火虫i被更亮的萤火虫j吸引而移 1.1K-调和均值算法 动的位置为 K-调和均值算法的原理基本上与K-means是相 xi=x;+B(Xi-xi)+aEi (6) 似的，不同的是其使用调和均值(harmonic means, 式中：x:、x为萤火虫i和j的位置：a为步长因子， HM)代替算术均值来计算目标函数，能够有效解决 可设为常数：e:为服从均匀分布的随机数向量。 对初始类中心点选取的敏感性问题。假定数据集 X=[x1x2…x.]包含n个数据，它们被划分 2基于改进FA的K-调和均值聚类 到k个聚类簇，每个簇的中心用c,(G=1,2,…,k)表 2.1并行混沌局部搜索策略改进的FA 示，KHM的目标函数为[) 基本的FA缺乏变异机制，当处于局部极值时 KHM(X,C)= -,i=1,2,…,n 难以摆脱，且当前最优解xg周围是搜索到更优解的 1 最有利的区域，而FA在优化过程中采用对其随机 2x:-G1 扰动的方式，搜索效率不高。混沌优化方法能够有 (1) 效地跳出局部最优并搜索到全局最优解，现有文献优化算法进行改进，以充分利用其全局搜索能力，如 融合粒子群［３］ 、变邻域搜索［４］ 、改进候选组搜索［５］ 等混合聚类算法。 此外，将模糊概念引入 ＫＨＭ 中 也得到了一定的关注［６⁃７］ 。 目前，各种群智能优化 算法已被广泛地应用于各个领域中［８⁃１１］ ，并且依据 没有免费的午餐定律，本文提出新的混合聚类算法。 萤火虫算法（ ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ， ＦＡ） 是由剑桥学者 Ｙａｎｇ 等［１２⁃１３］在 ２００８ 年提出的一种新颖的群智能算 法，具有结构简单、可调参数少、宜于并行处理等特 点，可以有效解决各种优化问题，并能够成功应用到 聚类问题中提高算法的准确性和鲁棒性［１４］ 。 很多 学者已经对它开展了不少研究工作，引入混沌原理 改进的 ＦＡ 具有一定的优势，Ｆｉｓｔｅｒ 等［１５］对现有的混 沌萤火虫算法（ ｃｈａｏｓ⁃ｂａｓｅｄ ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ， ＣＦＡ） 进行了总结，它们的主要思想都是基于算法参数的 改进，其中 Ｇａｎｄｏｍｉ 等［１６］采用各种混沌映射模型进 行了比较全面的对比分析。 然而，仅对参数的调整 无法更全面有效地利用混沌优化的优点，混沌局部 搜索（ ｃｈａｏｔｉｃ ｌｏｃａｌ ｓｅａｒｃｈ， ＣＬＳ） ［９⁃１０］ 是一种能够有 效提高算法优化性能的策略。 本文从进一步提高 ＦＡ 的优化性能出发，提出 一种新颖的 ＣＦＡ，并将其融入到 ＫＨＭ 以获得一种 更有效的混合聚类方法。 在 ＦＡ 中引入一种并行混 沌局部搜索策略，将 ＣＬＳ 与并行混沌优化（ ｐａｒａｌｌｅｌ ｃｈａｏｔｉｃ ｏｐｔｉｍｉｚａｔｉｏｎ， ＰＣＯ） ［１７⁃１８］ 相结合，提高 ＦＡ 的 局部搜索能力，具有更高的搜索效率，并能够有效避 免局部最优。 将这种改进的 ＣＦＡ 融入到 ＫＨＭ 中优 化其目标函数，通过对实际数据集的实验可以看出 本文所提的聚类算法能够获得更好的性能指标，有 效抑制了陷入局部最优的问题。 １ 算法概念与定义 １．１ Ｋ⁃调和均值算法 Ｋ⁃调和均值算法的原理基本上与 Ｋ⁃ｍｅａｎｓ 是相 似的，不同的是其使用调和均值（ ｈａｒｍｏｎｉｃ ｍｅａｎｓ， ＨＭ）代替算术均值来计算目标函数，能够有效解决 对初始类中心点选取的敏感性问题。 假定数据集 Ｘ ＝［ｘ１ ｘ２ … ｘｎ ］ 包含 ｎ 个数据，它们被划分 到 ｋ 个聚类簇，每个簇的中心用 ｃｊ（ｊ ＝ １，２，…，ｋ） 表 示，ＫＨＭ 的目标函数为［３］ ＫＨＭ（Ｘ，Ｃ） ＝ ∑ ｎ ｉ ＝ １ ｋ ∑ ｋ ｊ ＝ １ １ ‖ｘｉ － ｃｊ‖ｐ ，∀ｉ ＝ １，２，…，ｎ （１） 这里采用欧式距离计算样本到聚类中心的 距离，参数 ｐ 对算法的性能具有重要的影响，且 当 ｐ≥２ 时聚类的效果比较好［ ２］ 。 算法通过不断 地迭代使目标函数值不断减小并保持稳定，每次 迭代过程中，各个簇的中心点 ｃｊ（ ｊ ＝ １，２，…，ｋ） 的 更新如下［３］ 。 ｃｊ ｎｅｗ ＝ ∑ ｎ ｉ ＝ １ ｍＫＨＭ（ｃｊ ／ ｘｉ） × ｗＫＨＭ（ｘｉ） × ｘｉ ∑ ｎ ｉ ＝ １ ｍＫＨＭ（ｃｊ ／ ｘｉ） × ｗＫＨＭ（ｘｉ） （２） 式中：成员函数 ｍＫＨＭ和权重函数 ｗＫＨＭ的定义分别为 式（３）和式（４）。 ｍＫＨＭ（ｃｊ ／ ｘｉ） ＝ ‖ｘｉ － ｃｊ‖－ｐ－２ ∑ Ｋ ｊ ＝ １ ‖ｘｉ － ｃｊ‖ － ｐ － ２ （３） ｗＫＨＭ（ｘｉ） ＝ ∑ ｋ ｊ ＝ １ ‖ｘｉ － ｃｊ‖－ｐ－２ （∑ ｋ ｊ ＝ １ ‖ｘｉ － ｃｊ‖－ｐ ） ２ （４） １．２ 萤火虫算法的相关定义 在 ＦＡ 中萤火虫彼此吸引主要取决于 ２ 个因 素：亮度和吸引度。 亮度决定了个体所处位置的好 坏及其移动方向，吸引度决定了移动的距离，通过亮 度和吸引度的不断更新，实现目标优化。 通常直接 利用目标函数值的大小表示萤火虫 ｉ 的亮度 Ｉｉ，即 Ｉｉ ＝ｆ（ｘｉ）， ｘｉ ＝ ［ｘｉ１ ｘｉ２ … ｘｉｄ ］ 。 ＦＡ 的相关定 义如下［１２⁃１３］ ： 定义 １ 萤火虫 ｉ 与 ｊ 之间的吸引度为 β ＝ β０ ｅ －γｒ ２ ｉｊ （５） 式中： β０ 为在 ｒ ＝ ０ 处的吸引度，一般可取值为 １； γ 为光强吸收系数，对算法的性能具有重要的影响，通 常情况下可以取 γ ＝ １；ｒｉｊ为萤火虫 ｉ 与 ｊ 之间的空 间距离，一般采用欧氏距离计算。 定义 ２ 萤火虫 ｉ 被更亮的萤火虫 ｊ 吸引而移 动的位置为 ｘｉ ｎｅｗ ＝ ｘｉ ＋ β（ｘｊ － ｘｉ） ＋ α εｉ （６） 式中： ｘｉ 、 ｘｊ 为萤火虫 ｉ 和 ｊ 的位置；α 为步长因子， 可设为常数； εｉ 为服从均匀分布的随机数向量。 ２ 基于改进 ＦＡ 的 Ｋ⁃调和均值聚类 ２．１ 并行混沌局部搜索策略改进的 ＦＡ 基本的 ＦＡ 缺乏变异机制，当处于局部极值时 难以摆脱，且当前最优解 ｘｐｇ 周围是搜索到更优解的 最有利的区域，而 ＦＡ 在优化过程中采用对其随机 扰动的方式，搜索效率不高。 混沌优化方法能够有 效地跳出局部最优并搜索到全局最优解，现有文献 第 ６ 期 朱书伟，等：融合并行混沌萤火虫算法的 Ｋ⁃调和均值聚类 ·８７３·