第10卷第6期 智能系统学报 Vol.10 No.6 2015年12月 CAAI Transactions on Intelligent Systems Dee.2015 D0:10.11992.tis.201505043 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20151110.1354.006.html 融合并行混沌萤火虫算法的K-调和均值聚类 朱书伟，周治平，张道文 (江南大学物联网工程学院，江苏无锡214122) 摘要：针对K-调和均值算法易陷于局部最优的缺点，提出一种基于改进萤火虫算法(firefly algorithm,FA)的K-调 和均值聚类算法。将基于FA的粗搜索与基于并行混沌优化FA的精细搜索相结合，其中精细搜索部分首先通过FA 搜索到当前最优解及次优解，然后通过改进的1 ogistic映射与并行混沌优化策略产生混沌序列在其附近直接搜索，以 增强算法的寻优性能。最终，将这种改进的FA用于K调和均值算法聚类中心的优化。实验结果表明：该算法不但 对几种测试函数具有更高的搜索精度，而且对6种数据集的聚类结果均有一定的改善，有效地抑制了K-调和均值算 法陷于局部最优的问题，提高了聚类准确性和稳定性。 关键词：K调和均值：局部最优：莹火虫算法；聚类：并行混沌优化：混沌局部搜索：映射模型：种群多样性 中图分类号：TP18文献标志码：A文章编号：1673-4785(2015)06-0872-09 中文引用格式：朱书伟，周治平，张道文.融合并行混沌萤火虫算法的K-调和均值聚类[J].智能系统学报，2015,10(6)：872-880. 英文引用格式：ZHU Shuwei,ZHOU Zhiping,ZHANG Daowen.K-harmonic means clustering merged with parallel chaotic firefly algorithm[J].CAAI Transactions on Intelligent Systems,2015,10(6):872-880. K-harmonic means clustering merged with parallel chaotic firefly algorithm ZHU Shuwei,ZHOU Zhiping,ZHANG Daowen (School of Internet of Things Engineering,Jiangnan University,Wuxi 214122,China) Abstract:The K-harmonic means algorithm (KHM)has the disadvantage of easily falling into a local optimum.To solve this problem,we propose a hybrid KHM based on an improved firefly algorithm(FA).In this paper,we com- bined raw FA-based searching with parallel chaotic FA-based elaborate searching.In the elaborate searching,we found the current best and second-best solutions using the FA,then we used an improved logistic map model com- bined with parallel chaotic optimization to search this area in order to enhance the searching ability of the algorithm. Finally,we used the improved FA to optimize the cluster centers obtained by the KHM.Experimental results dem- onstrate that the proposed algorithm not only had higher search precision for several test functions,but also im- proved the clustering accuracy and stability of six datasets,effectively avoiding being trapped into a local optimum. Keywords:K-harmonic means;local optimum;firefly algorithm;clustering;parallel chaotic optimization;chaotic local search;map model;diversity of population 聚类分析是一种广泛使用的数据分析方法，一 最经典且使用最为广泛的聚类算法，其过程简单快 直被应用于多个领域，特别是在数据挖掘、模式识 捷，容易实现。为了克服K-means对初始聚类中心 别、图像处理等领域应用十分广泛。K-meanst是 敏感的缺陷，Zhang等)于1999年提出一种K-调和 均值(K-harmonic means,KHM)算法，具有较高的稳 收稿日期：2015-05-27.网络出版日期：2015-11-10. 定性、收敛速度快，但由于其与K-means同样基于划 基金项目：江苏省产学研联合创新资金-前瞻性联合研究基金资助项目 (BY2013015-33). 分的原理，仍存在易陷于局部最优的问题。 通信作者：朱书伟.E-mail:6131905056@ip-jiangnan.cdu.cm 目前，对于KHM算法的研究主要是结合智能
第 １０ 卷第 ６ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．６ ２０１５ 年 １２ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｄｅｃ． ２０１５ ＤＯＩ：１０．１１９９２．ｔｉｓ．２０１５０５０４３ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５１１１０．１３５４．００６．ｈｔｍｌ 融合并行混沌萤火虫算法的 Ｋ⁃调和均值聚类 朱书伟，周治平，张道文 （江南大学 物联网工程学院，江苏 无锡 ２１４１２２） 摘 要：针对 Ｋ⁃调和均值算法易陷于局部最优的缺点，提出一种基于改进萤火虫算法（ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ， ＦＡ）的 Ｋ⁃调 和均值聚类算法。 将基于 ＦＡ 的粗搜索与基于并行混沌优化 ＦＡ 的精细搜索相结合，其中精细搜索部分首先通过 ＦＡ 搜索到当前最优解及次优解，然后通过改进的 ｌｏｇｉｓｔｉｃ 映射与并行混沌优化策略产生混沌序列在其附近直接搜索，以 增强算法的寻优性能。 最终，将这种改进的 ＦＡ 用于 Ｋ⁃调和均值算法聚类中心的优化。 实验结果表明：该算法不但 对几种测试函数具有更高的搜索精度，而且对 ６ 种数据集的聚类结果均有一定的改善，有效地抑制了 Ｋ⁃调和均值算 法陷于局部最优的问题，提高了聚类准确性和稳定性。 关键词：Ｋ⁃调和均值；局部最优；萤火虫算法；聚类；并行混沌优化；混沌局部搜索；映射模型；种群多样性 中图分类号：ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０６⁃０８７２⁃０９ 中文引用格式：朱书伟，周治平， 张道文． 融合并行混沌萤火虫算法的 Ｋ⁃调和均值聚类［Ｊ］． 智能系统学报， ２０１５， １０（６）： ８７２⁃８８０． 英文引用格式：ＺＨＵ Ｓｈｕｗｅｉ， ＺＨＯＵ Ｚｈｉｐｉｎｇ， ＺＨＡＮＧ Ｄａｏｗｅｎ． Ｋ⁃ｈａｒｍｏｎｉｃ ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ｍｅｒｇｅｄ ｗｉｔｈ ｐａｒａｌｌｅｌ ｃｈａｏｔｉｃ ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（６）： ８７２⁃８８０． Ｋ⁃ｈａｒｍｏｎｉｃ ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ｍｅｒｇｅｄ ｗｉｔｈ ｐａｒａｌｌｅｌ ｃｈａｏｔｉｃ ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ ＺＨＵ Ｓｈｕｗｅｉ， ＺＨＯＵ Ｚｈｉｐｉｎｇ， ＺＨＡＮＧ Ｄａｏｗｅｎ （Ｓｃｈｏｏｌ ｏｆ Ｉｎｔｅｒｎｅｔ ｏｆ Ｔｈｉｎｇｓ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｊｉａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｕｘｉ ２１４１２２， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ Ｋ⁃ｈａｒｍｏｎｉｃ ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ （ＫＨＭ） ｈａｓ ｔｈｅ ｄｉｓａｄｖａｎｔａｇｅ ｏｆ ｅａｓｉｌｙ ｆａｌｌｉｎｇ ｉｎｔｏ ａ ｌｏｃａｌ ｏｐｔｉｍｕｍ． Ｔｏ ｓｏｌｖｅ ｔｈｉｓ ｐｒｏｂｌｅｍ， ｗｅ ｐｒｏｐｏｓｅ ａ ｈｙｂｒｉｄ ＫＨＭ ｂａｓｅｄ ｏｎ ａｎ ｉｍｐｒｏｖｅｄ ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ （ＦＡ）． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｗｅ ｃｏｍ⁃ ｂｉｎｅｄ ｒａｗ ＦＡ⁃ｂａｓｅｄ ｓｅａｒｃｈｉｎｇ ｗｉｔｈ ｐａｒａｌｌｅｌ ｃｈａｏｔｉｃ ＦＡ⁃ｂａｓｅｄ ｅｌａｂｏｒａｔｅ ｓｅａｒｃｈｉｎｇ． Ｉｎ ｔｈｅ ｅｌａｂｏｒａｔｅ ｓｅａｒｃｈｉｎｇ， ｗｅ ｆｏｕｎｄ ｔｈｅ ｃｕｒｒｅｎｔ ｂｅｓｔ ａｎｄ ｓｅｃｏｎｄ⁃ｂｅｓｔ ｓｏｌｕｔｉｏｎｓ ｕｓｉｎｇ ｔｈｅ ＦＡ， ｔｈｅｎ ｗｅ ｕｓｅｄ ａｎ ｉｍｐｒｏｖｅｄ ｌｏｇｉｓｔｉｃ ｍａｐ ｍｏｄｅｌ ｃｏｍ⁃ ｂｉｎｅｄ ｗｉｔｈ ｐａｒａｌｌｅｌ ｃｈａｏｔｉｃ ｏｐｔｉｍｉｚａｔｉｏｎ ｔｏ ｓｅａｒｃｈ ｔｈｉｓ ａｒｅａ ｉｎ ｏｒｄｅｒ ｔｏ ｅｎｈａｎｃｅ ｔｈｅ ｓｅａｒｃｈｉｎｇ ａｂｉｌｉｔｙ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ． Ｆｉｎａｌｌｙ， ｗｅ ｕｓｅｄ ｔｈｅ ｉｍｐｒｏｖｅｄ ＦＡ ｔｏ ｏｐｔｉｍｉｚｅ ｔｈｅ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ ｏｂｔａｉｎｅｄ ｂｙ ｔｈｅ ＫＨＭ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｄｅｍ⁃ ｏｎｓｔｒａｔｅ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｎｏｔ ｏｎｌｙ ｈａｄ ｈｉｇｈｅｒ ｓｅａｒｃｈ ｐｒｅｃｉｓｉｏｎ ｆｏｒ ｓｅｖｅｒａｌ ｔｅｓｔ ｆｕｎｃｔｉｏｎｓ， ｂｕｔ ａｌｓｏ ｉｍ⁃ ｐｒｏｖｅｄ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ａｃｃｕｒａｃｙ ａｎｄ ｓｔａｂｉｌｉｔｙ ｏｆ ｓｉｘ ｄａｔａｓｅｔｓ， ｅｆｆｅｃｔｉｖｅｌｙ ａｖｏｉｄｉｎｇ ｂｅｉｎｇ ｔｒａｐｐｅｄ ｉｎｔｏ ａ ｌｏｃａｌ ｏｐｔｉｍｕｍ． Ｋｅｙｗｏｒｄｓ： Ｋ⁃ｈａｒｍｏｎｉｃ ｍｅａｎｓ； ｌｏｃａｌ ｏｐｔｉｍｕｍ； ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ； ｃｌｕｓｔｅｒｉｎｇ； ｐａｒａｌｌｅｌ ｃｈａｏｔｉｃ ｏｐｔｉｍｉｚａｔｉｏｎ； ｃｈａｏｔｉｃ ｌｏｃａｌ ｓｅａｒｃｈ； ｍａｐ ｍｏｄｅｌ； ｄｉｖｅｒｓｉｔｙ ｏｆ ｐｏｐｕｌａｔｉｏｎ 收稿日期：２０１５⁃０５⁃２７． 网络出版日期：２０１５⁃１１⁃１０． 基金项目：江苏省产学研联合创新资金－前瞻性联合研究基金资助项目 （ＢＹ２０１３０１５⁃３３）． 通信作者：朱书伟． Ｅ⁃ｍａｉｌ：６１３１９０５０５６＠ ｖｉｐ．ｊｉａｎｇｎａｎ．ｅｄｕ．ｃｎ． 聚类分析是一种广泛使用的数据分析方法，一 直被应用于多个领域，特别是在数据挖掘、模式识 别、图像处理等领域应用十分广泛。 Ｋ⁃ｍｅａｎｓ ［１］ 是 最经典且使用最为广泛的聚类算法，其过程简单快 捷，容易实现。 为了克服 Ｋ⁃ｍｅａｎｓ 对初始聚类中心 敏感的缺陷，Ｚｈａｎｇ 等［２］于 １９９９ 年提出一种 Ｋ⁃调和 均值（Ｋ⁃ｈａｒｍｏｎｉｃ ｍｅａｎｓ， ＫＨＭ）算法，具有较高的稳 定性、收敛速度快，但由于其与 Ｋ⁃ｍｅａｎｓ 同样基于划 分的原理，仍存在易陷于局部最优的问题。 目前，对于 ＫＨＭ 算法的研究主要是结合智能
第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) 效地跳出局部最优并搜索到全局最优解，现有文献
优化算法进行改进，以充分利用其全局搜索能力，如 融合粒子群［３］ 、变邻域搜索［４］ 、改进候选组搜索［５］ 等混合聚类算法。 此外，将模糊概念引入 ＫＨＭ 中 也得到了一定的关注［６⁃７］ 。 目前，各种群智能优化 算法已被广泛地应用于各个领域中［８⁃１１］ ，并且依据 没有免费的午餐定律，本文提出新的混合聚类算法。 萤火虫算法（ ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ， ＦＡ） 是由剑桥学者 Ｙａｎｇ 等［１２⁃１３］在 ２００８ 年提出的一种新颖的群智能算 法，具有结构简单、可调参数少、宜于并行处理等特 点，可以有效解决各种优化问题，并能够成功应用到 聚类问题中提高算法的准确性和鲁棒性［１４］ 。 很多 学者已经对它开展了不少研究工作，引入混沌原理 改进的 ＦＡ 具有一定的优势，Ｆｉｓｔｅｒ 等［１５］对现有的混 沌萤火虫算法（ ｃｈａｏｓ⁃ｂａｓｅｄ ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ， ＣＦＡ） 进行了总结，它们的主要思想都是基于算法参数的 改进，其中 Ｇａｎｄｏｍｉ 等［１６］采用各种混沌映射模型进 行了比较全面的对比分析。 然而，仅对参数的调整 无法更全面有效地利用混沌优化的优点，混沌局部 搜索（ ｃｈａｏｔｉｃ ｌｏｃａｌ ｓｅａｒｃｈ， ＣＬＳ） ［９⁃１０］ 是一种能够有 效提高算法优化性能的策略。 本文从进一步提高 ＦＡ 的优化性能出发，提出 一种新颖的 ＣＦＡ，并将其融入到 ＫＨＭ 以获得一种 更有效的混合聚类方法。 在 ＦＡ 中引入一种并行混 沌局部搜索策略，将 ＣＬＳ 与并行混沌优化（ ｐａｒａｌｌｅｌ ｃｈａｏｔｉｃ ｏｐｔｉｍｉｚａｔｉｏｎ， ＰＣＯ） ［１７⁃１８］ 相结合，提高 ＦＡ 的 局部搜索能力，具有更高的搜索效率，并能够有效避 免局部最优。 将这种改进的 ＣＦＡ 融入到 ＫＨＭ 中优 化其目标函数，通过对实际数据集的实验可以看出 本文所提的聚类算法能够获得更好的性能指标，有 效抑制了陷入局部最优的问题。 １ 算法概念与定义 １．１ Ｋ⁃调和均值算法 Ｋ⁃调和均值算法的原理基本上与 Ｋ⁃ｍｅａｎｓ 是相 似的，不同的是其使用调和均值（ ｈａｒｍｏｎｉｃ ｍｅａｎｓ， ＨＭ）代替算术均值来计算目标函数，能够有效解决 对初始类中心点选取的敏感性问题。 假定数据集 Ｘ ＝［ｘ１ ｘ２ … ｘｎ ］ 包含 ｎ 个数据，它们被划分 到 ｋ 个聚类簇，每个簇的中心用 ｃｊ（ｊ ＝ １，２，…，ｋ） 表 示，ＫＨＭ 的目标函数为［３］ ＫＨＭ（Ｘ，Ｃ） ＝ ∑ ｎ ｉ ＝ １ ｋ ∑ ｋ ｊ ＝ １ １ ‖ｘｉ － ｃｊ‖ｐ ，∀ｉ ＝ １，２，…，ｎ （１） 这里采用欧式距离计算样本到聚类中心的 距离，参数 ｐ 对算法的性能具有重要的影响，且 当 ｐ≥２ 时聚类的效果比较好［ ２］ 。 算法通过不断 地迭代使目标函数值不断减小并保持稳定，每次 迭代过程中，各个簇的中心点 ｃｊ（ ｊ ＝ １，２，…，ｋ） 的 更新如下［３］ 。 ｃｊ ｎｅｗ ＝ ∑ ｎ ｉ ＝ １ ｍＫＨＭ（ｃｊ ／ ｘｉ） × ｗＫＨＭ（ｘｉ） × ｘｉ ∑ ｎ ｉ ＝ １ ｍＫＨＭ（ｃｊ ／ ｘｉ） × ｗＫＨＭ（ｘｉ） （２） 式中：成员函数 ｍＫＨＭ和权重函数 ｗＫＨＭ的定义分别为 式（３）和式（４）。 ｍＫＨＭ（ｃｊ ／ ｘｉ） ＝ ‖ｘｉ － ｃｊ‖－ｐ－２ ∑ Ｋ ｊ ＝ １ ‖ｘｉ － ｃｊ‖ － ｐ － ２ （３） ｗＫＨＭ（ｘｉ） ＝ ∑ ｋ ｊ ＝ １ ‖ｘｉ － ｃｊ‖－ｐ－２ （∑ ｋ ｊ ＝ １ ‖ｘｉ － ｃｊ‖－ｐ ） ２ （４） １．２ 萤火虫算法的相关定义 在 ＦＡ 中萤火虫彼此吸引主要取决于 ２ 个因 素：亮度和吸引度。 亮度决定了个体所处位置的好 坏及其移动方向，吸引度决定了移动的距离，通过亮 度和吸引度的不断更新，实现目标优化。 通常直接 利用目标函数值的大小表示萤火虫 ｉ 的亮度 Ｉｉ，即 Ｉｉ ＝ｆ（ｘｉ）， ｘｉ ＝ ［ｘｉ１ ｘｉ２ … ｘｉｄ ］ 。 ＦＡ 的相关定 义如下［１２⁃１３］ ： 定义 １ 萤火虫 ｉ 与 ｊ 之间的吸引度为 β ＝ β０ ｅ －γｒ ２ ｉｊ （５） 式中： β０ 为在 ｒ ＝ ０ 处的吸引度，一般可取值为 １； γ 为光强吸收系数，对算法的性能具有重要的影响，通 常情况下可以取 γ ＝ １；ｒｉｊ为萤火虫 ｉ 与 ｊ 之间的空 间距离，一般采用欧氏距离计算。 定义 ２ 萤火虫 ｉ 被更亮的萤火虫 ｊ 吸引而移 动的位置为 ｘｉ ｎｅｗ ＝ ｘｉ ＋ β（ｘｊ － ｘｉ） ＋ α εｉ （６） 式中： ｘｉ 、 ｘｊ 为萤火虫 ｉ 和 ｊ 的位置；α 为步长因子， 可设为常数； εｉ 为服从均匀分布的随机数向量。 ２ 基于改进 ＦＡ 的 Ｋ⁃调和均值聚类 ２．１ 并行混沌局部搜索策略改进的 ＦＡ 基本的 ＦＡ 缺乏变异机制，当处于局部极值时 难以摆脱，且当前最优解 ｘｐｇ 周围是搜索到更优解的 最有利的区域，而 ＦＡ 在优化过程中采用对其随机 扰动的方式，搜索效率不高。 混沌优化方法能够有 效地跳出局部最优并搜索到全局最优解，现有文献 第 ６ 期 朱书伟，等：融合并行混沌萤火虫算法的 Ｋ⁃调和均值聚类 ·８７３·
·874… 智能系统学报 第10卷 对混沌模型的研究非常广泛，如logistic映射、Sinu- 1.0 soidal映射、Gaussian映射等16,1。文献[9-10]中采 取一种改进logistic映射分别与粒子群(particle swarm optimization,PS0)算法和差分进化算法融合 提出2种有效的基于CLS的混合优化算法，成功用 于短期梯级水电系统调度问题，并且在文献[19]中 验证了这种混沌映射的优势，它具有较大的李雅普 -1.0 -0.590.51.0 诺夫指数。logistic映射模型为[1例 y(1+1)=4y()(1-y(l)),y(1)∈(0,1) (b)多峰 图12种特殊情况的最优解与次优解局部搜索区域 (7) Fig.1 Two particular types of local search region a- 式中：l表示迭代次数，需要注意的是混沌变量初始 round the best and second best solutions 值y(0){0.25,0.5,0.75},若设置y(1)=(z(l)+ 为了进一步提高搜索效率，提出一种并行混沌 1)/2,则可以获得改进的logistic映射如式(8)1)： 局部搜索(parallel chaotic local search,PCLS)策略， z(1+1)=1-2(z(1))2,z(1)∈（-1,1)(8) 采用并行混沌优化的思想产生N个混沌局部变量 并且其概率密度分布表达式为 对次优解和最优解并行扰动，不但克服传统CLS的 1 ,z∈(-1,1) 串行机制搜索精确解效率不高、收敛稳定性不强等 f(z)=m√1-z (9) 缺点[910，还能够有效地兼顾最优解与次优解。当 0,z年(-1,1) 最优解和次优解接近时可将它们的作用视为相等， 由式(9)可以看出改进logistic映射可以将混沌 不接近时则能够有效地拓展局部搜索空间。每次迭 变量的搜索空间拓展到(-1,1)，在接近边界-1和1 代后取N个并行变量与xg和x综合排序获得新 处具有较大的概率密度值，因此具有更好的遍历性、 的最优解和次优解，有效地提高算法搜索能力。 随机性。因此，本文利用改进logistic映射在当前最 考虑到文献[17-18]中PC0结合了粗搜索与细 优解附近直接搜索，其本质上属于一种混沌干扰法， 搜索的策略以平衡算法的探索与开发性能，为了使 即产生许多局部最优解的邻域点，以增强搜索到全 并行混沌局部搜索萤火虫算法(parallel chaotic local 局最优解的概率。与此同时，适应度值仅次于最优 search firefly algorithm,PCLSFA)在前期进行一定的 解x的次优解x同样对搜索到更优解具有一定的 粗搜索，可在前T次迭代直接执行FA,PCLSFA 价值，文献[20]中以最优点和次优点为基础进行反 的具体过程为： 射、延伸、收缩等步骤的单纯形法也为本文提供一定 1)初始化萤火虫个体的位置并计算其对应的 的启发。为了更直观地分析，在图1中分别给出二 目标函数值1，作为亮度，初始化迭代次数t=0,最大 维的单峰和多峰搜索空间的2种特殊情况的次优解 迭代次数设为T,粗搜索迭代次数T1o 与最优解局部搜索区域，它们的局部搜索半径均相 2)执行FA不断更新亮度，最亮的个体即为当 等，并且假定越往内适应度值越好。从图1(a)、 前最优解xs,并且次优解为x,若>T1,则采用 (b)中可见2种特殊情况下次优解相对于最优解均 PCLS在它们附近寻优作为细搜索。 具有更好的搜索潜力。 3)设置当前混沌搜索次数1=0，在上文几个断 点外的区域初始化混沌变量-1<g<1(i=1,2, 1.0 饮优解 …,N;j=1,2,…,m),N为并行变量数，m为单变量 0.5 维数，则表示第i个并行变量的第j维。此外，中 最秋解 间变量矩阵为Y,PCLS最大迭代次数为Cr。 ①考虑到大多数情况下x具有更好的搜索潜 -0.5 力，令0=n(,i=1,2…2,且0=.(0. -1.0 0.5 0 0.51.0 i=2N+12W+2 3 ,3,,N,使用式(8)确定第41次 (a)单峰 迭代的混沌扰动变量写+
对混沌模型的研究非常广泛，如 ｌｏｇｉｓｔｉｃ 映射、Ｓｉｎｕ⁃ ｓｏｉｄａｌ 映射、Ｇａｕｓｓｉａｎ 映射等［１６，１９］ 。 文献［９⁃１０］中采 取一种 改 进 ｌｏｇｉｓｔｉｃ 映 射 分 别 与 粒 子 群 （ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ， ＰＳＯ）算法和差分进化算法融合 提出 ２ 种有效的基于 ＣＬＳ 的混合优化算法，成功用 于短期梯级水电系统调度问题，并且在文献［１９］中 验证了这种混沌映射的优势，它具有较大的李雅普 诺夫指数。 ｌｏｇｉｓｔｉｃ 映射模型为［１９］ ｙ（ｌ ＋ １） ＝ ４ｙ（ｌ）（１ － ｙ（ｌ））， ｙ（ｌ） ∈ （０，１） （７） 式中：ｌ 表示迭代次数，需要注意的是混沌变量初始 值 ｙ（０） ∉ ｛０．２５，０．５，０．７５｝ ，若设置 ｙ（ｌ） ＝ （ｚ（ｌ） ＋ １） ／ ２，则可以获得改进的 ｌｏｇｉｓｔｉｃ 映射如式（８） ［１９］ ： ｚ（ｌ ＋ １） ＝ １ － ２ （ｚ（ｌ）） ２ ，ｚ（ｌ） ∈ （ － １，１） （８） 并且其概率密度分布表达式为 ｆ（ｚ） ＝ １ π １ － ｚ ２ ，ｚ ∈ （ － １，１） ０，ｚ ∉ （ － １，１） ì î í ï ï ïï （９） 由式（９）可以看出改进 ｌｏｇｉｓｔｉｃ 映射可以将混沌 变量的搜索空间拓展到（－１，１），在接近边界－１ 和 １ 处具有较大的概率密度值，因此具有更好的遍历性、 随机性。 因此，本文利用改进 ｌｏｇｉｓｔｉｃ 映射在当前最 优解附近直接搜索，其本质上属于一种混沌干扰法， 即产生许多局部最优解的邻域点，以增强搜索到全 局最优解的概率。 与此同时，适应度值仅次于最优 解 ｘｐｇ 的次优解 ｘｐｓ 同样对搜索到更优解具有一定的 价值，文献［２０］中以最优点和次优点为基础进行反 射、延伸、收缩等步骤的单纯形法也为本文提供一定 的启发。 为了更直观地分析，在图 １ 中分别给出二 维的单峰和多峰搜索空间的 ２ 种特殊情况的次优解 与最优解局部搜索区域，它们的局部搜索半径均相 等，并且假定越往内适应度值越好。 从图 １ （ ａ）、 （ｂ）中可见 ２ 种特殊情况下次优解相对于最优解均 具有更好的搜索潜力。 （ａ）单峰 （ｂ）多峰 图 １ ２ 种特殊情况的最优解与次优解局部搜索区域 Ｆｉｇ．１ Ｔｗｏ ｐａｒｔｉｃｕｌａｒ ｔｙｐｅｓ ｏｆ ｌｏｃａｌ ｓｅａｒｃｈ ｒｅｇｉｏｎ ａ⁃ ｒｏｕｎｄ ｔｈｅ ｂｅｓｔ ａｎｄ ｓｅｃｏｎｄ ｂｅｓｔ ｓｏｌｕｔｉｏｎｓ 为了进一步提高搜索效率，提出一种并行混沌 局部搜索（ｐａｒａｌｌｅｌ ｃｈａｏｔｉｃ ｌｏｃａｌ ｓｅａｒｃｈ， ＰＣＬＳ）策略， 采用并行混沌优化的思想产生 Ｎ 个混沌局部变量 对次优解和最优解并行扰动，不但克服传统 ＣＬＳ 的 串行机制搜索精确解效率不高、收敛稳定性不强等 缺点［９⁃１０］ ，还能够有效地兼顾最优解与次优解。 当 最优解和次优解接近时可将它们的作用视为相等， 不接近时则能够有效地拓展局部搜索空间。 每次迭 代后取 Ｎ 个并行变量与 ｘｐｇ 和 ｘｐｓ 综合排序获得新 的最优解和次优解，有效地提高算法搜索能力。 考虑到文献［１７⁃１８］中 ＰＣＯ 结合了粗搜索与细 搜索的策略以平衡算法的探索与开发性能，为了使 并行混沌局部搜索萤火虫算法（ｐａｒａｌｌｅｌ ｃｈａｏｔｉｃ ｌｏｃａｌ ｓｅａｒｃｈ ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ， ＰＣＬＳＦＡ）在前期进行一定的 粗搜索，可在前 Ｔｍａｘ１ 次迭代直接执行 ＦＡ，ＰＣＬＳＦＡ 的具体过程为： １）初始化萤火虫个体的位置并计算其对应的 目标函数值 Ｉｉ作为亮度，初始化迭代次数 ｔ ＝ ０，最大 迭代次数设为 Ｔｍａｘ，粗搜索迭代次数 Ｔｍａｘ１ 。 ２）执行 ＦＡ 不断更新亮度，最亮的个体即为当 前最优解 ｘｐｇ ，并且次优解为 ｘｐｓ ，若 ｔ＞Ｔｍａｘ１ ，则采用 ＰＣＬＳ 在它们附近寻优作为细搜索。 ３）设置当前混沌搜索次数 ｌ ＝ ０，在上文几个断 点外的区域初始化混沌变量－１＜ｚｉｊ （０） ＜１ （ ｉ ＝ １，２， …，Ｎ； ｊ ＝ １，２，…，ｍ），Ｎ 为并行变量数，ｍ 为单变量 维数，则 ｚｉｊ表示第 ｉ 个并行变量的第 ｊ 维。 此外，中 间变量矩阵为 Ｙ ，ＰＣＬＳ 最大迭代次数为 Ｃｍａｘ。 ①考虑到大多数情况下 ｘｐｇ 具有更好的搜索潜 力，令 ｙ （ｌ） ｉ ＝ ｘｐｇ （ｌ） ， ｉ ＝ １，２…， ２Ｎ ３ ，且 ｙ （ｌ） ｉ ＝ ｘｐｓ （ｌ）， ｉ ＝ ２Ｎ ＋ １ ３ ， ２Ｎ ＋ ２ ３ ，…，Ｎ ，使用式（８）确定第 ｌ＋１ 次 迭代的混沌扰动变量 ｚｉｊ （ ｌ＋ １） 。 ·８７４· 智 能 系 统 学 报 第 １０ 卷
第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,若lb,则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
②混沌变量与收缩因子 βｔ 成比例，通过混沌扰 动产生 Ｎ 个新变量如式（１０）所示。 ｙｉｊ （ｌ＋１） ＝ ｙｉｊ （ｌ） ＋ βｔ ｚｉｊ （ｌ＋１） ｌＰＣＬＳ （１０） 式中： ｌＰＣＬＳ 为并行混沌局部搜索的范围，可将其设 置为 ０．０１ｌ ～０．１ｌ ， ｌ 为变量尺度，若 ｕｂ 、 ｌ ｂ 分别为变 量的上下界，则取 ｌ ＝ （ｕｂ － ｌ ｂ） ／ ２，收缩因子 βｔ 为 βｔ ＝ ｅ －Ｃ∗ｔ／ Ｔｍａｘ （１１） 式中：Ｃ 是一个用于控制 ＰＣＬＳ 精度的正数，根据实 验分析可在［１，１０］内选取，一般对于较难搜索到全 局最优的问题取较小值。 求得 Ｎ 个新变量组成的 矩阵为 Ｙ （ｌ＋１） ＝ ｙ１１ （ｌ＋１） ｙ１２ （ｌ＋１） … ｙ１ｍ （ｌ＋１） ｙ２１ （ｌ＋１） ｙ２２ （ｌ＋１） … ｙ２ｍ （ｌ＋１） ︙ ︙ ︙ ｙＮ１ （ｌ＋１） ｙＮ２ （ｌ＋１） … ｙＮｍ （ｌ＋１） é ë ê ê ê ê ê ê ù û ú ú ú ú ú ú （１２） ③计算每个新变量所对应的目标函数值为 ｆ（ｙｉ （ｌ＋１） ） ，并将 Ｙ （ｌ＋１） 与 ｘｐｇ （ｌ＋１） 、 ｘｐｓ （ｌ＋１） 合并，对这 Ｎ＋２ 个变量的适应度值进行排序，得到第ｌ＋１ 次迭 代中的最优解 ｘｐｇ （ｌ＋１） 和次优解 ｘｐｓ （ｌ＋１） 。 ④ｌ ＝ ｌ＋１，若 ｌ＜Ｃｍａｘ，转向①；否则转向 ４）。 ４）ｔ ＝ ｔ＋１，若 ｔ＜Ｔｍａｘ，转向 ２），且随机选取一个 萤火虫个体用 ３）中获得的 ｘｐｇ 替换并更新其亮度； 否则停止迭代，输出全局最优解。 ２．２ 提高种群多样性的策略 由于 ＦＡ 缺乏保持种群多样性的操作，降低了 算法探索到全局最优解的能力，因此需要采取一定 的措施来解决这一问题。 本文中算法每迭代 Ｎｐ次 时，找出适应度值最差的 ｎｃ％的个体并采用混沌重 构法生成新的个体替代它们。 对于各维尺度相等的 优化问题，直接计算出当前种群所有维空间的最大 值 ｘｍａｘ和最小值 ｘｍｉｎ作为各维的统一边界。 对于各 维尺度不相等的优化问题，对边界向量不断地收缩， 初始时第 ｊ 维的边界等于定义域［ａｊ，ｂｊ］，当达到第 Ｎｐ次迭代的最优个体为 ｘ ∗ ，根据式（１３）收缩边界。 ａｊ ｎｅｗ ＝ ｘｊ ∗ － φ（ｂｊ － ａｊ） ｂｊ ｎｅｗ ＝ ｘｊ ∗ ＋ φ（ｂｊ { － ａｊ） （１３） 式中： φ ∈ （０，０．５） ，并且为了保证新的边界范围不 会越界， 对其进行相应的处理为： 若 ａｊ ｎｅｗ ＜ ａｊ， 则 ａｊ ｎｅｗ ＝ ａｊ；若 ｂｊ ｎｅｗ ＞ｂｊ，则 ｂｊ ｎｅｗ ＝ ｂｊ。 然后根据式（７）的 ｌｏｇｉｓｔｉｃ 映射生成比例为 ｎｃ％的 Ｎｃ个在（０，１）上的向 量 Ｃｘｉ（ｉ ＝ １，２，…，Ｎｃ） 如式（１４）所示。 Ｃｘｉ ＝ ４ × ｙ × （１ － ｙ），ｙ ∈ （０，１） （１４） 最后再将其转换到当前种群变量的取值空间如 式（１５）所示，获得替换种群并更新其适应度值。 ｘｉ ｎｅｗ ＝ ｂ ＋ Ｃｘｉ（ｂ － ａ） （１５） 这里随着迭代次数的增加对边界范围不断收 缩，在各个不同阶段生成不同尺度的混沌变量，能够 避免直接根据初始的定义域随机生成替代个体时效 率不高的问题，且同样能够改善种群多样性。 ２．３ 改进 ＦＡ 的收敛性分析及复杂度分析 目前，ＦＡ 还没有很完备的数学理论基础［１２⁃１３］ ，但 已有的仿真实验结果表明 ＦＡ 具有较高的寻优精度 和收敛速度，是一种有效的优化方法。 本文改进算法 与基本 ＦＡ 的不同之处为迭代 Ｔｍａｘ１次后增加了 ＰＣＬＳ 过程，故只需证明 ３）过程的收敛性，即可证明 ＰＣＬＳ⁃ ＦＡ 的收敛性优于 ＦＡ。 从测度论上进行分析，由于 ＰＣＬＳ 属于下降算法，并且它具有很好的遍历性，因而 设 Ｒｇ 表示全局最优点 ｘ ∗ 的可行域。 总迭代次数为 ｔ 时（ｔ＞Ｔｍａｘ１ ），在执行 ２）后的当前最优解 ｘｐｇ 和次优解 ｘｐｓ 落入 Ｒｇ 的事件集合为 Ａ０ ， Ｐ（Ａ０ ） ≤ １， ＰＣＬＳ 每次 迭代后产生的序列矩阵 ｙ （ｌ） 且与 ｘｐｇ （ｌ） 、 ｘｐｓ （ｌ） （ｌ ＝ １， ２，…，Ｃｍａｘ）合并后落入 Ｒｇ 的事件集合为 Ａｌ，因此Ａ１⊂ Ａ２⊂ … ⊂ ＡＣｍａｘ ，概率测度单调不减，故 Ｐ（ＡＣｍａｘ ） ≥ … ≥Ｐ（Ａ２ ） ≥ Ｐ（Ａ１ ）。 可知执行 ３）之后具有更高的 概率落入全局最优点 ｘ ∗ 的可行域，故 ＰＣＬＳＦＡ 的收 敛性优于 ＦＡ，接下来通过对基准函数的仿真实验能 够进一步验证其收敛性。 此外，当忽略对目标函数的 计算时，ＦＡ 的时间复杂度为 Ｏ （ Ｔｍａｘ ∙Ｎｐｏｐ２ ），且 ＰＣＬＳＦＡ 的时间复杂度为 Ｏ（ Ｔｍａｘ ∙Ｎｐｏｐ２ ＋ Ｔｍａｘ ２ ∙ Ｃｍａｘ∙Ｎ），（Ｔｍａｘ２ ＝Ｔｍａｘ －Ｔｍａｘ １ ）。 ２．４ ＫＨＭ⁃ＰＣＬＳＦＡ 算法流程 本文采用 Ｋ⁃调和均值的目标函数 ＫＨＭ（ Ｘ，Ｃ ） 作为萤火虫 ｉ 的亮度 Ｉｉ，并以此确定其移动方向，其 本质上是将聚类问题转化为一种优化问题。 若 ｋ 为 聚类的数量，ｍ 为数据的维数，则用一个 ｋ×ｍ 列的 一维向量 ｘ ＝ （ｘ１１ ，ｘ１２ ，…，ｘ１ｍ ，…，ｘｋ１ ，ｘｋ２ ，…，ｘｋｍ ） 来表示一个聚类中心，即一个萤火虫个体。 由于算 法对初始值不敏感，可从数据集中随机选择 ｋ 个不 同的点并对其进行较小的扰动以构成一个中心向量 ｘ，确定 Ｐｓｉｚｅ个这样的向量作为种群初始位置。 由于 本文算法的总迭代次数 Ｉｔｅｒｍａｘ 较小，不需要执行粗 搜索。 综上所述，本文算法 ＫＨＭ⁃ＰＣＬＳＦＡ 的流程为： １）初始化算法的基本参数 γ、 α、β、Ｃｍａｘ、 Ｎ、ｌ 并 随机初始化萤火虫种群的位置。 ２）根据萤火虫的位置计算其目标函数值作为 亮度，初始化当前迭代次数 ｇｅｎ ＝ ０。 第 ６ 期 朱书伟，等：融合并行混沌萤火虫算法的 Ｋ⁃调和均值聚类 ·８７５·
·876. 智能系统学报 第10卷 3)执行PCLSFA进行搜索，迭代运行gen,次，B=(B-B)er房+B,其中B=1,Ba= 求出当前的最优个体G以及对应的最优目标函 0.2。对搜索空间较小的函数f1~f取1cs=0.1l,对 数值F,进入下一步操作。并且，选出占种群比例 搜索空间较大的函数f取1cs=0.01l。此外， 为%的最差个体并采用混沌重构法将其替换。 PCLSFA中的N=15,N。=50,n.=20,中=0.4。 4)以G为聚类中心执行KHM操作，迭代运 仿真实验基于MATLAB201Ob平台，计算机 行gen2次，得到目标函数值KHM(X,C)和聚类中 的硬件配置为：Intel Core i5-4200MCPU2.5 心并将其转化为一维向量xKHM,若KHM(X,C)< GHz、4 GB RAM。各函数的维数均为30，每种算 F,则用xKM代替G,并以xKHM随机替换一个萤 法独立运行30次，计算各自的最大值、最小值、 火虫。 平均值和标准差，记录至表1。对各函数的收敛 5)gen=gen+1,若gen<Itermax,则转到3)继续 曲线为30次运行的平均结果，分别如图2所示， 执行，否则停止迭代得出聚类结果。 为了更明显的比较，图中纵坐标是对最优解求g 若数据集中有n个数据，则KHM每次迭代的 (f)后的平均值。 时间复杂度为O(knm),本文聚类算法FA部分采用 表14个基准函数的实验结果 的是同步的适应度更新方式，故3)中PCLSFA Table 1 The experiment results for four test functions 的时间复杂度为O(gen,·(Pic·（Pr+knm)+ 函数算法 最小值 最大值 平均值 标准差 Cms·N·knm),4)中KHM的时间复杂度为O FA3.763×1046.981×10-33.084×1031.962×10 (gen2·knm),并且Pe<khnm,gen,<gen1·Pc,因此 CLSPS07.994×1052.6605 1.2916 0.9344 本文算法的时间复杂度为O(Itermax·gen,·（Pc+ CLSFA1.139x10i00.0522 0.0201 0.0260 Cmax·N)·knm)。 PCLSFA1.052×10-01.496×10-01.259×10~01.212×101 3 实验数据与分析 FA 26.575029.2100 28.3060 0.8046 CLSPS07.919×10-4 4.2221 0.2651 0.7178 3.1 PCLSFA的性能测试 CLSEA 0.0302 32.1542 4.0760 9.6093 选取了4个标准的无约束测试函数f~f): PCLSFA2.208×10-3 0.2135 0.1308 0.0669 Ackley(x:∈[-30,30])、Rosenbrock(x∈ [-2.048,2.048])、Rastrigin(x:∈[-5.12,5.12])、 FA 20.8950 47.8200 30.9116 7.1678 CLSPS059.6970112.431088.5517 12.5322 Griewank(x:∈[-600,600])进行仿真测试，它们的 f CLSFA 10.8617 38.6014 21.0392 5.8030 最优解都是O。通过FA、采用串行CLS分别改进 PCLSFA 6.574 8 22.109113.21294.3872 PS0和FA算法的CLSPSOUS)和CLSFA进行对比分 析，以验证PCLSFA的收敛性能及寻优能力。各算 FA 3.089×1053.441×10+1.030×107.068×10-3 法种群规模都为Nm=40,最大迭代数T=2000,3 CLSPS07.116×1040.04899.674×10-30.0117 种具有CLS机制的算法中取Cmm=10,C=5。考虑 斤C5FA1.112x10-3.296×10-9.873x10-51.508×10 FA对不同函数的收敛性能不同，在CLSFA和 PCLSFA1.110×10165.541×10~63.331×1061.655×10-6 PCLSFA前期执行粗搜索的迭代数也不相同，对f 根据表1可见，PCLSFA对各函数求出的最优 和f取T,=500,对6取T,=0,对取T,= 解的平均值及标准差均为最小，表明算法具有较高 200。CLSPS0中采用线性递减的惯性权重w),且 的寻优精度与稳定性。虽然对f和f,CLSPS0能搜 wmm=0.9,0mi=0.4,学习因子为c1=c2=1.496。FA 索到更佳的最小值，但相应的概率较小，从其偏大的 型算法中统一设置y=1,随机步长α随着迭代次数 平均值和标准差可以看出。并且，CLSFA对于f和 t的增加不断减小为 f,能够获得的最小值与PCLSFA接近，但其很不稳 a+1=a((10-4/0.9)A(b/T)) 定使其平均值相对较差，有效验证了并行CLS相对 式中：a的初始值为1，b是控制收敛精度的参数，对 于串行CLS的优势。由图2可见PCLSFA对f和f 算法的收敛性能具有较大的影响，偏大会导致早熟 的收敛性均取得了显著的提高，对于相对较难寻优 收敛，偏小则会使算法无法更精确地搜索到全局最 的f2和f也取得了一定的提高。因此，表1和图2 优解，经过实验对比分析本文取b=3。此外，为防 中的实验结果有效验证了本文算法的收敛性。尽管 止距离太大使算法失效，还需对B进行调整，即为 PCLSFA对复杂函数的寻优精度方面还有待改进
３）执行 ＰＣＬＳＦＡ 进行搜索，迭代运行 ｇｅｎ１ 次， 求出当前的最优个体 Ｇｂｅｓｔ 以及对应的最优目标函 数值 Ｆｇ ， 进入下一步操作。 并且，选出占种群比例 为 ｎｃ％的最差个体并采用混沌重构法将其替换。 ４）以 Ｇｂｅｓｔ 为聚类中心执行 ＫＨＭ 操作，迭代运 行 ｇｅｎ２ 次，得到目标函数值 ＫＨＭ（Ｘ，Ｃ） 和聚类中 心并将其转化为一维向量 ｘＫＨＭ ，若 ＫＨＭ（Ｘ，Ｃ） ＜ Ｆｇ ，则用 ｘＫＨＭ 代替 Ｇｂｅｓｔ ，并以 ｘＫＨＭ 随机替换一个萤 火虫。 ５）ｇｅｎ ＝ ｇｅｎ＋１，若 ｇｅｎ＜Ｉｔｅｒｍａｘ，则转到 ３）继续 执行，否则停止迭代得出聚类结果。 若数据集中有 ｎ 个数据，则 ＫＨＭ 每次迭代的 时间复杂度为 Ｏ（ｋｎｍ），本文聚类算法 ＦＡ 部分采用 的是同步的适应度更新方式［１５］ ，故 ３） 中 ＰＣＬＳＦＡ 的时间复杂度为 Ｏ（ ｇｅｎ１ ∙（Ｐｓｉｚｅ ∙（ Ｐ ｓｉｚｅ ＋ｋｎｍ） ＋ Ｃｍａｘ∙Ｎ∙ｋｎｍ）），４） 中 ＫＨＭ 的时间复杂度为 Ｏ （ｇｅｎ２∙ｋｎｍ），并且 Ｐｓｉｚｅ＜ｋｎｍ，ｇｅｎ２＜ｇｅｎ１∙Ｐｓｉｚｅ，因此 本文算法的时间复杂度为 Ｏ（Ｉｔｅｒｍａｘ∙ｇｅｎ１∙（Ｐｓｉｚｅ ＋ Ｃｍａｘ∙Ｎ）∙ｋｎｍ）。 ３ 实验数据与分析 ３．１ ＰＣＬＳＦＡ 的性能测试 选取了 ４ 个标准的无约束测试函数 ｆ １ ～ ｆ ４ ［１７⁃１８］ ： Ａｃｋｌｅｙ （ ｘｉ ∈ ［ － ３０， ３０ ］）、 Ｒｏｓｅｎｂｒｏｃｋ （ ｘｉ ∈ ［－２．０４８，２．０４８］）、Ｒａｓｔｒｉｇｉｎ（ ｘｉ ∈ ［ － ５． １２，５． １２］）、 Ｇｒｉｅｗａｎｋ（ｘｉ∈ ［－６００，６００］） 进行仿真测试，它们的 最优解都是 ０。 通过 ＦＡ、采用串行 ＣＬＳ 分别改进 ＰＳＯ 和 ＦＡ 算法的 ＣＬＳＰＳＯ ［９］ 和 ＣＬＳＦＡ 进行对比分 析，以验证 ＰＣＬＳＦＡ 的收敛性能及寻优能力。 各算 法种群规模都为 Ｎｐｏｐ ＝ ４０，最大迭代数 Ｔｍａｘ ＝ ２ ０００，３ 种具有 ＣＬＳ 机制的算法中取 Ｃｍａｘ ＝ １０，Ｃ ＝ ５。 考虑 ＦＡ 对 不 同 函 数 的 收 敛 性 能 不 同， 在 ＣＬＳＦＡ 和 ＰＣＬＳＦＡ 前期执行粗搜索的迭代数也不相同，对 ｆ １ 和 ｆ ４取 Ｔｍａｘ１ ＝ ５００，对 ｆ ２ 取 Ｔｍａｘ１ ＝ ０，对 ｆ ３ 取 Ｔｍａｘ１ ＝ ２００。 ＣＬＳＰＳＯ 中采用线性递减的惯性权重 ｗ ［９］ ，且 ｗｍａｘ ＝ ０．９，ｗｍｉｎ ＝ ０．４，学习因子为 ｃ１ ＝ ｃ２ ＝ １．４９６。 ＦＡ 型算法中统一设置 γ ＝ １，随机步长 α 随着迭代次数 ｔ 的增加不断减小为 α ｔ＋１ ＝ α ｔ （（１０ － ４ ／ ０．９） ∧ （ｂ ／ Ｔｍａｘ）） 式中：α 的初始值为 １，ｂ 是控制收敛精度的参数，对 算法的收敛性能具有较大的影响，偏大会导致早熟 收敛，偏小则会使算法无法更精确地搜索到全局最 优解，经过实验对比分析本文取 ｂ ＝ ３。 此外，为防 止距离太大使算法失效，还需对 β 进行调整，即为 β ＝（β ｍａｘ － β ｍｉｎ ）ｅ －γｒ ２ ｉｊ ＋ β ｍｉｎ ，其中 β ｍａｘ ＝ １， β ｍｉｎ ＝ ０．２。 对搜索空间较小的函数 ｆ １ ～ ｆ ３取 ｌＰＣＬＳ ＝ ０．１ｌ ，对 搜索空间较大的函数 ｆ ４ 取 ｌＰＣＬＳ ＝ ０．０１ｌ 。 此外， ＰＣＬＳＦＡ 中的 Ｎ＝ １５，Ｎｐ ＝ ５０，ｎｃ ＝ ２０， ϕ ＝ ０．４。 仿真实验基于 ＭＡＴＬＡＢ２０１０ｂ 平台，计算机 的硬 件 配 置 为： Ｉｎｔｅｌ Ｃｏｒｅ ｉ５⁃４ ２００ Ｍ ＣＰＵ ２． ５ ＧＨｚ、４ ＧＢ ＲＡＭ。 各函数的维数均为 ３０，每种算 法独立运行 ３０ 次，计算各自的最大值、最小值、 平均值和标准差，记录至表 １。 对各函数的收敛 曲线为 ３０ 次运行的平均结果，分别如图 ２ 所示， 为了更明显的比较，图中纵坐标是对最优解求 ｌｇ （ ｆ ）后的平均值。 表 １ ４ 个基准函数的实验结果 Ｔａｂｌｅ １ Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔ ｒｅｓｕｌｔｓ ｆｏｒ ｆｏｕｒ ｔｅｓｔ ｆｕｎｃｔｉｏｎｓ 函数 算法 最小值 最大值 平均值 标准差 ｆ １ ＦＡ ＣＬＳＰＳＯ ＣＬＳＦＡ ＰＣＬＳＦＡ ３．７６３×１０ －４ ７．９９４×１０ －１５ １．１３９×１０ －１０ １．０５２×１０ －１０ ６．９８１×１０ －３ ２．６６０ ５ ０．０５２ ２ １．４９６×１０ －１０ ３．０８４×１０ －３ １．２９１ ６ ０．０２０ １ １．２５９×１０ －１０ １．９６２×１０ －３ ０．９３４ ４ ０．０２６ ０ １．２１２×１０ －１１ ｆ ２ ＦＡ ＣＬＳＰＳＯ ＣＬＳＦＡ ＰＣＬＳＦＡ ２６．５７５ ０ ７．９１９×１０ －４ ０．０３０ ２ ２．２０８×１０ －３ ２９．２１０ ０ ４．２２２ １ ３２．１５４ ２ ０．２１３ ５ ２８．３０６ ０ ０．２６５ １ ４．０７６ ０ ０．１３０ ８ ０．８０４ ６ ０．７１７ ８ ９．６０９ ３ ０．０６６ ９ ｆ ３ ＦＡ ＣＬＳＰＳＯ ＣＬＳＦＡ ＰＣＬＳＦＡ ２０．８９５ ０ ５９．６９７ ０ １０．８６１ ７ ６．５７４ ８ ４７．８２０ ０ １１２．４３１ ０ ３８．６０１ ４ ２２．１０９ １ ３０．９１１ ６ ８８．５５１ ７ ２１．０３９ ２ １３．２１２ ９ ７．１６７ ８ １２．５３２ ２ ５．８０３ ０ ４．３８７ ２ ｆ ４ ＦＡ ＣＬＳＰＳＯ ＣＬＳＦＡ ＰＣＬＳＦＡ ３．０８９×１０ －５ ７．１１６×１０ －１４ １．１１２×１０ －１６ １．１１０×１０ －１６ ３．４４１×１０ －４ ０．０４８ ９ ３．２９６×１０ －４ ５．５４１×１０ －１６ １．０３０×１０ －４ ９．６７４×１０ －３ ９．８７３×１０ －５ ３．３３１×１０ －１６ ７．０６８×１０ －５ ０．０１１ ７ １．５０８×１０ －４ １．６５５×１０ －１６ 根据表 １ 可见，ＰＣＬＳＦＡ 对各函数求出的最优 解的平均值及标准差均为最小，表明算法具有较高 的寻优精度与稳定性。 虽然对 ｆ １和 ｆ ２ ，ＣＬＳＰＳＯ 能搜 索到更佳的最小值，但相应的概率较小，从其偏大的 平均值和标准差可以看出。 并且，ＣＬＳＦＡ 对于 ｆ １和 ｆ ４能够获得的最小值与 ＰＣＬＳＦＡ 接近，但其很不稳 定使其平均值相对较差，有效验证了并行 ＣＬＳ 相对 于串行 ＣＬＳ 的优势。 由图 ２ 可见 ＰＣＬＳＦＡ 对 ｆ １和 ｆ ４ 的收敛性均取得了显著的提高，对于相对较难寻优 的 ｆ ２和 ｆ ３也取得了一定的提高。 因此，表 １ 和图 ２ 中的实验结果有效验证了本文算法的收敛性。 尽管 ＰＣＬＳＦＡ 对复杂函数的寻优精度方面还有待改进， ·８７６· 智 能 系 统 学 报 第 １０ 卷
第6期 朱书伟，等：融合并行混沌莹火虫算法的K-调和均值聚类 ·877- 但是本文中其拥有最好的寻优能力，表明了PCLS 表2实验数据集的特性 机制的引入是有效的。 Table 2 The feature of experimental data set 3.2KHM-PCLSFA的实验数据与分析 数据集 类数 维数数据个数 为了验证本文算法的聚类性能，选取了UCI数 Iris 3 150 据库中的6个常用的数据集ris、Ionosphere、Wine Ionosphere 2 33 351 Image Segmentation(本文简称为Image)、CMC和 Wine 3 13 178 Satellite进行测试，它们的特性如表2所示。 Image 个 19 210 CMC 3 9 1473 LSPSO Satellite 6 33 6435 本文以目标函数值KHM(X,C)作为聚类的内 部评价指标，其值越小则聚类结果越好：F-measure 作为聚类的外部评价指标，其值越大则聚类效果越 10 好。若已知类i中的样本数目n:,簇中的样本数目 10 20 迭代次数 m,以及簇j中属于已知类i的样本数目n,则判准 (a)f:Ackley 率为p(i》=”,查全率为r(i》=,样本数为n 4 n n ,·,,FA SPSO 的数据集的总体F-measure值为 2 -PCLSFA F=∑ma,{F(i,} n 0 F(ij)= 2×p(i,j)×r(i,j） p(i,j)+r(i,j) 10 分别采用KHM、KHM-FA、KHM-PSO)和本文 10 15 20 迭代次数 的KHM-PCLSFA对几种数据集进行实验，其中 (b)f:Rosenbrock KHM-FA与文本算法的不同体现在2.1节的3)中执 3.0 行的是FA。各算法参数设置为：种群规模与文献 …FA [3]保持一致Pc=18;KHM的最大迭代次数Max 2.5 ·-.-CLSPSO gen=100,且在迭代过程中若目标函数值不再变化 -PCLSFA 则停止：3种混合聚类算法各部分迭代次数统一设 置为Itermax=5,gen1=8,gen2=10。KHM-PS0中 1.5 PS0的相关参数为0=0.7298，c1=c2=1.496,FA及 1.0 10 15 2010 PCLSFA的相关参数为y=1,a=0.1,B同式(17)。 迭代次数 这里为了控制PCLS的执行时间，取Cm=4,N=6, (c)f3:Rastrigin C=3,lcs=0.1l。本文分别取p=2.5、3、3.5时对聚 类结果进行比较，每种算法独立运行20次，计算各 自的KHM(X,C)、F-measure和运行时间的平均值， 并分别记录在表3~表5中，需注意其中数据集Ion -10 ·-FA osphere用Sphere表示。 .-·-CLSPSO ---CLSFA 从表3~5可以看出对不同特性的数据集，3种混 -15 —PCLSFA 合聚类算法所得的KHM(X,C)和F-measure值相对 -20 10 15 2010 于KHM算法均得到了一定的改善。从KHM(X,C) 送代次数 值的降低看出，Iis和Ionosphere在p=3.5时最大程 (d)f:Griewank 度均降低了0.56%；Wine在p=3.5时最大程度降低 图2各函数的收敛曲线 了47.77%；Image在p=3.5时最大程度降低了78. Fig.2 The convergence curves for test functions 91%;CMC在p=3时最大程度降低了0.13%：Satellite
但是本文中其拥有最好的寻优能力，表明了 ＰＣＬＳ 机制的引入是有效的。 ３．２ ＫＨＭ⁃ＰＣＬＳＦＡ 的实验数据与分析 为了验证本文算法的聚类性能，选取了 ＵＣＩ 数 据库中的 ６ 个常用的数据集 Ｉｒｉｓ、Ｉｏｎｏｓｐｈｅｒｅ、Ｗｉｎｅ、 Ｉｍａｇｅ Ｓｅｇｍｅｎｔａｔｉｏｎ （ 本文简称 为 Ｉｍａｇｅ）、 ＣＭＣ 和 Ｓａｔｅｌｌｉｔｅ 进行测试，它们的特性如表 ２ 所示。 （ａ） ｆ １ ： Ａｃｋｌｅｙ （ｂ）ｆ ２ ： Ｒｏｓｅｎｂｒｏｃｋ （ｃ）ｆ ３ ： Ｒａｓｔｒｉｇｉｎ （ｄ）ｆ ４ ： Ｇｒｉｅｗａｎｋ 图 ２ 各函数的收敛曲线 Ｆｉｇ．２ Ｔｈｅ ｃｏｎｖｅｒｇｅｎｃｅ ｃｕｒｖｅｓ ｆｏｒ ｔｅｓｔ ｆｕｎｃｔｉｏｎｓ 表 ２ 实验数据集的特性 Ｔａｂｌｅ ２ Ｔｈｅ ｆｅａｔｕｒｅ ｏｆ ｅｘｐｅｒｉｍｅｎｔａｌ ｄａｔａ ｓｅｔ 数据集 类数 维数 数据个数 Ｉｒｉｓ ３ ４ １５０ Ｉｏｎｏｓｐｈｅｒｅ ２ ３３ ３５１ Ｗｉｎｅ ３ １３ １７８ Ｉｍａｇｅ ７ １９ ２１０ ＣＭＣ ３ ９ １４７３ Ｓａｔｅｌｌｉｔｅ ６ ３３ ６４３５ 本文以目标函数值 ＫＨＭ（Ｘ，Ｃ）作为聚类的内 部评价指标，其值越小则聚类结果越好；Ｆ⁃ｍｅａｓｕｒｅ 作为聚类的外部评价指标，其值越大则聚类效果越 好。 若已知类 ｉ 中的样本数目 ｎｉ，簇 ｊ 中的样本数目 ｎｊ，以及簇 ｊ 中属于已知类 ｉ 的样本数目 ｎｉｊ，则判准 率为 ｐ（ｉ，ｊ） ＝ ｎｉｊ ｎｊ ，查全率为 ｒ（ｉ，ｊ） ＝ ｎｉｊ ｎｉ ，样本数为 ｎ 的数据集的总体 Ｆ⁃ｍｅａｓｕｒｅ 值为 Ｆ ＝ ∑ｉ ｎｉ ｎ ｍａｘｊ {Ｆ（ｉ，ｊ）} Ｆ（ｉ，ｊ） ＝ ２ × ｐ（ｉ，ｊ） × ｒ（ｉ，ｊ） ｐ（ｉ，ｊ） ＋ ｒ（ｉ，ｊ） 分别采用 ＫＨＭ、ＫＨＭ⁃ＦＡ、ＫＨＭ⁃ＰＳＯ ［３］ 和本文 的 ＫＨＭ⁃ＰＣＬＳＦＡ 对 几 种 数 据 集 进 行 实 验， 其 中 ＫＨＭ⁃ＦＡ 与文本算法的不同体现在 ２．１ 节的 ３）中执 行的是 ＦＡ。 各算法参数设置为：种群规模与文献 ［３］保持一致 Ｐｓｉｚｅ ＝ １８；ＫＨＭ 的最大迭代次数 Ｍａｘ⁃ ｇｅｎ ＝ １００，且在迭代过程中若目标函数值不再变化 则停止；３ 种混合聚类算法各部分迭代次数统一设 置为 Ｉｔｅｒｍａｘ ＝ ５， ｇｅｎ１ ＝ ８， ｇｅｎ２ ＝ １０。 ＫＨＭ⁃ＰＳＯ 中 ＰＳＯ 的相关参数为 ｗ ＝ ０．７２９ ８，ｃ１ ＝ ｃ２ ＝ １．４９６，ＦＡ 及 ＰＣＬＳＦＡ 的相关参数为 γ ＝ １，α ＝ ０．１，β 同式（１７）。 这里为了控制 ＰＣＬＳ 的执行时间，取 Ｃｍａｘ ＝ ４，Ｎ ＝ ６， Ｃ＝ ３， ｌＰＣＬＳ ＝ ０．１ｌ 。 本文分别取 ｐ ＝ ２．５、３、３．５时对聚 类结果进行比较，每种算法独立运行 ２０ 次，计算各 自的 ＫＨＭ（Ｘ，Ｃ）、Ｆ⁃ｍｅａｓｕｒｅ 和运行时间的平均值， 并分别记录在表 ３～表 ５ 中，需注意其中数据集 Ｉｏｎ⁃ ｏｓｐｈｅｒｅ 用 Ｓｐｈｅｒｅ 表示。 从表 ３～５ 可以看出对不同特性的数据集，３ 种混 合聚类算法所得的 ＫＨＭ（Ｘ，Ｃ）和 Ｆ⁃ｍｅａｓｕｒｅ 值相对 于 ＫＨＭ 算法均得到了一定的改善。 从 ＫＨＭ（Ｘ，Ｃ） 值的降低看出，Ｉｒｉｓ 和 Ｉｏｎｏｓｐｈｅｒｅ 在 ｐ ＝ ３．５ 时最大程 度均降低了 ０．５６％；Ｗｉｎｅ 在 ｐ ＝ ３．５ 时最大程度降低 了 ４７．７７％；Ｉｍａｇｅ 在 ｐ ＝ ３．５ 时最大程度降低了 ７８． ９１％；ＣＭＣ 在 ｐ ＝ ３ 时最大程度降低了０．１３％；Ｓａｔｅｌｌｉｔｅ 第 ６ 期 朱书伟，等：融合并行混沌萤火虫算法的 Ｋ⁃调和均值聚类 ·８７７·
·878 智能系统学报 第10卷 在p=3.5时最大程度降低了0.28%。从F-measure值 此外，对于Satellite在p=3.5时，KHMPS0的目 的提升可以看出，Wine在p=3时最大程度提高了 标函数值为最小，而其Fmeasure值却低于其他聚类 5.79%;mage在p=3时最大程度提高了1.63%：CMC 算法，其中的原因值得进一步研究。经过综合对比 在p=3.5时最大程度提高了1.10%；Satellite在p=3 分析，比较不同p值下的聚类结果可以看出，本文算 时最大程度提高了2.23%。对于Iis和lonosphere,3 法在总体上具有最佳的聚类准确性和稳定性，并且 种混合算法的F-measure难以获得提高，这里主要通 对于较复杂数据的改进效果更明显，能够有效避免 过KHM(X,C)值的降低看出3种混合聚类算法的性 陷入局部最优解。3种混合聚类算法中都引入了群 能改善，其中本文算法能够获得最小的值，表现出更 智能算法的搜索过程，因此它们的运行时间大于 好的寻优能力。对于Wine和Satellite,几种混合聚类 KHM,并且本文算法中又引入了PCLS策略，使得其 算法的F-measure均取得比较明显的提高。虽然对于 运行时间更长一些，这无法满足于数据规模非常大 CMC和Image的F-measure提高有时比较有限，但是 的聚类问题。在时间效率要求不是很高时适当增加 对KHM(X,C)的降低取得了不错的效果，尤其是对 PCLSFA的搜索次数能够进一步获得更佳的结果， 于Image,比如在p=2.5时发现KHM算法总是会早 并且在很多情况下算法精度方面的要求也显得更为 熟收敛于KHM(X,C)=9.6364×10'左右的状态，而 重要。 表4p=3时4种算法实验结果 实验中算法可获得的实际最优值在2.2326×10'左 Table 4 The results of four algorithms when p=3 右，这时使得其最终的均值较大，而3种混合算法能 够有效减少陷入局部最优的次数，可以看出其均值都 数据集 算法 KHM(X.C) F-measure 时间/s 有较大程度的降低。 KHM 126.08 0.892 0.181 表3p=2.5时4种算法实验结果 KHM-FA 125.86 0.892 1.296 Iris Table 3 The results of four algorithms when p 2.5 KHM-PSO 125.99 0.892 1.198 数据集 算法 KHM(X,C F-measure 时间/s 本文算法 125.81 0.893 2.195 KHM 148.91 0.885 0.176 KHM 2648.0 0.700 0.693 KHM-FA 148.84 0.885 1.322 KHM-FA 2643.5 0.700 5.087 KHM-PSO 148.89 0.885 1.227 Sphere KHM-PSO 2646.5 0.700 5.067 本文算法 148.83 0.886 2.236 本文算法 2642.3 0.700 9.630 KHM 2805.6 0.706 0.691 KHM-FA 2804.8 0.706 5.108 KHM 1.0491×10 0.622 0.262 Sphere KHM-PSO 2805.2 0.706 5.105 KHM-FA 1.0491×10 0.656 2.193 本文算法 2803.7 0.706 9.668 Wine KHM-PSO 1.0490×109 0.632 2.136 KHM 75338585.3 0.689 0.272 本文算法 1.0491×109 0.658 3.831 KHM-FA 75336750.4 0.704 2.185 Wine KHM 1.7906×10 0.551 0.876 KHM-PSO 75336842.8 0.701 2.216 KHM-FA 1.7835×10 0.560 6.592 本文算法 75335247.3 0.707 3.854 Image KHM-PSO 1.7884×108 0.559 6.703 KHM 54906284.3 0.595 0.921 本文算法 1.7713×108 0.560 12.210 KHM-FA 40937350.7 0.597 6.658 Image KHM-PSO 40178361.8 0.597 6.883 KHM 187018.21 0.458 1.937 本文算法29926352.6 0.599 12.034 KHM-FA 186824.39 0.461 14.885 CMC KHM 96201.47 0.465 1.987 KHM-PSO 186943.89 0.460 14.869 KHM-FA 96165.23 0.465 14.814 本文算法 186778.24 0.464 26.389 CMC KHM-PSO 96185.28 0.464 14.924 KHM 8.8054×103 0.763 12.428 本文算法 96160.39 0.465 26.683 KHM-FA 8.8027×108 KHM 1.9543×10i 0.762 12.462 0.776 91.250 Satellite 1.9536×10 KHM-PSO 8.8028×109 0.774 99.784 KHM-FA 0.775 92.112 Satellite 本文算法 8.7965×108 0.780 175.18 KHM-PSO 1.9537×10 0.771 99.459 本文算法1.9533×108 0.772 175.71
在 ｐ ＝ ３．５ 时最大程度降低了 ０．２８％。 从 Ｆ⁃ｍｅａｓｕｒｅ 值 的提升可以看出，Ｗｉｎｅ 在 ｐ ＝ ３ 时最大程度提高了 ５．７９％；Ｉｍａｇｅ 在 ｐ ＝ ３ 时最大程度提高了 １．６３％；ＣＭＣ 在 ｐ ＝ ３．５ 时最大程度提高了１．１０％；Ｓａｔｅｌｌｉｔｅ 在 ｐ ＝ ３ 时最大程度提高了 ２．２３％。 对于 Ｉｒｉｓ 和 Ｉｏｎｏｓｐｈｅｒｅ，３ 种混合算法的 Ｆ⁃ｍｅａｓｕｒｅ 难以获得提高，这里主要通 过 ＫＨＭ（Ｘ，Ｃ）值的降低看出 ３ 种混合聚类算法的性 能改善，其中本文算法能够获得最小的值，表现出更 好的寻优能力。 对于 Ｗｉｎｅ 和 Ｓａｔｅｌｌｉｔｅ，几种混合聚类 算法的 Ｆ⁃ｍｅａｓｕｒｅ 均取得比较明显的提高。 虽然对于 ＣＭＣ 和 Ｉｍａｇｅ 的 Ｆ⁃ｍｅａｓｕｒｅ 提高有时比较有限，但是 对 ＫＨＭ（Ｘ，Ｃ）的降低取得了不错的效果，尤其是对 于 Ｉｍａｇｅ，比如在 ｐ ＝ ２．５ 时发现 ＫＨＭ 算法总是会早 熟收敛于 ＫＨＭ（Ｘ，Ｃ）＝ ９．６３６ ４×１０ ７ 左右的状态，而 实验中算法可获得的实际最优值在 ２．２３２ ６×１０ ７ 左 右，这时使得其最终的均值较大，而 ３ 种混合算法能 够有效减少陷入局部最优的次数，可以看出其均值都 有较大程度的降低。 表 ３ ｐ ＝ ２．５ 时 ４ 种算法实验结果 Ｔａｂｌｅ ３ Ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｆｏｕｒ ａｌｇｏｒｉｔｈｍｓ ｗｈｅｎ ｐ ＝ ２．５ 数据集 算法 ＫＨＭ（ Ｘ，Ｃ ） Ｆ⁃ｍｅａｓｕｒｅ 时间／ ｓ Ｉｒｉｓ ＫＨＭ ＫＨＭ⁃ＦＡ ＫＨＭ⁃ＰＳＯ 本文算法 １４８．９１ １４８．８４ １４８．８９ １４８．８３ ０．８８５ ０．８８５ ０．８８５ ０．８８６ ０．１７６ １．３２２ １．２２７ ２．２３６ Ｓｐｈｅｒｅ ＫＨＭ ＫＨＭ⁃ＦＡ ＫＨＭ⁃ＰＳＯ 本文算法 ２ ８０５．６ ２ ８０４．８ ２ ８０５．２ ２ ８０３．７ ０．７０６ ０．７０６ ０．７０６ ０．７０６ ０．６９１ ５．１０８ ５．１０５ ９．６６８ Ｗｉｎｅ ＫＨＭ ＫＨＭ⁃ＦＡ ＫＨＭ⁃ＰＳＯ 本文算法 ７５ ３３８ ５８５．３ ７５ ３３６ ７５０．４ ７５ ３３６ ８４２．８ ７５ ３３５ ２４７．３ ０．６８９ ０．７０４ ０．７０１ ０．７０７ ０．２７２ ２．１８５ ２．２１６ ３．８５４ Ｉｍａｇｅ ＫＨＭ ＫＨＭ⁃ＦＡ ＫＨＭ⁃ＰＳＯ 本文算法 ５４ ９０６ ２８４．３ ４０ ９３７ ３５０．７ ４０ １７８ ３６１．８ ２９ ９２６ ３５２．６ ０．５９５ ０．５９７ ０．５９７ ０．５９９ ０．９２１ ６．６５８ ６．８８３ １２．０３４ ＣＭＣ ＫＨＭ ＫＨＭ⁃ＦＡ ＫＨＭ⁃ＰＳＯ 本文算法 ９６ ２０１．４７ ９６ １６５．２３ ９６ １８５．２８ ９６ １６０．３９ ０．４６５ ０．４６５ ０．４６４ ０．４６５ １．９８７ １４．８１４ １４．９２４ ２６．６８３ Ｓａｔｅｌｌｉｔｅ ＫＨＭ ＫＨＭ⁃ＦＡ ＫＨＭ⁃ＰＳＯ 本文算法 １．９５４ ３×１０ ８ １．９５３ ６×１０ ８ １．９５３ ７×１０ ８ １．９５３ ３×１０ ８ ０．７６２ ０．７７５ ０．７７１ ０．７７２ １２．４６２ ９２．１１２ ９９．４５９ １７５．７１ 此外，对于 Ｓａｔｅｌｌｉｔｅ 在 ｐ ＝ ３．５ 时，ＫＨＭＰＳＯ 的目 标函数值为最小，而其 Ｆｍｅａｓｕｒｅ 值却低于其他聚类 算法，其中的原因值得进一步研究。 经过综合对比 分析，比较不同 ｐ 值下的聚类结果可以看出，本文算 法在总体上具有最佳的聚类准确性和稳定性，并且 对于较复杂数据的改进效果更明显，能够有效避免 陷入局部最优解。 ３ 种混合聚类算法中都引入了群 智能算法的搜索过程，因此它们的运行时间大于 ＫＨＭ，并且本文算法中又引入了 ＰＣＬＳ 策略，使得其 运行时间更长一些，这无法满足于数据规模非常大 的聚类问题。 在时间效率要求不是很高时适当增加 ＰＣＬＳＦＡ 的搜索次数能够进一步获得更佳的结果， 并且在很多情况下算法精度方面的要求也显得更为 重要。 表 ４ ｐ ＝ ３ 时 ４ 种算法实验结果 Ｔａｂｌｅ ４ Ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｆｏｕｒ ａｌｇｏｒｉｔｈｍｓ ｗｈｅｎ ｐ ＝ ３ 数据集 算法 ＫＨＭ（ Ｘ，Ｃ ） Ｆ⁃ｍｅａｓｕｒｅ 时间／ ｓ Ｉｒｉｓ ＫＨＭ ＫＨＭ⁃ＦＡ ＫＨＭ⁃ＰＳＯ 本文算法 １２６．０８ １２５．８６ １２５．９９ １２５．８１ ０．８９２ ０．８９２ ０．８９２ ０．８９３ ０．１８１ １．２９６ １．１９８ ２．１９５ Ｓｐｈｅｒｅ ＫＨＭ ＫＨＭ⁃ＦＡ ＫＨＭ⁃ＰＳＯ 本文算法 ２６４８．０ ２６４３．５ ２６４６．５ ２６４２．３ ０．７００ ０．７００ ０．７００ ０．７００ ０．６９３ ５．０８７ ５．０６７ ９．６３０ Ｗｉｎｅ ＫＨＭ ＫＨＭ⁃ＦＡ ＫＨＭ⁃ＰＳＯ 本文算法 １．０４９ １×１０ ９ １．０４９ １×１０ ９ １．０４９ ０×１０ ９ １．０４９ １×１０ ９ ０．６２２ ０．６５６ ０．６３２ ０．６５８ ０．２６２ ２．１９３ ２．１３６ ３．８３１ Ｉｍａｇｅ ＫＨＭ ＫＨＭ⁃ＦＡ ＫＨＭ⁃ＰＳＯ 本文算法 １．７９０ ６×１０ ８ １．７８３ ５×１０ ８ １．７８８ ４×１０ ８ １．７７１ ３×１０ ８ ０．５５１ ０．５６０ ０．５５９ ０．５６０ ０．８７６ ６．５９２ ６．７０３ １２．２１０ ＣＭＣ ＫＨＭ ＫＨＭ⁃ＦＡ ＫＨＭ⁃ＰＳＯ 本文算法 １８７ ０１８．２１ １８６ ８２４．３９ １８６ ９４３．８９ １８６ ７７８．２４ ０．４５８ ０．４６１ ０．４６０ ０．４６４ １．９３７ １４．８８５ １４．８６９ ２６．３８９ Ｓａｔｅｌｌｉｔｅ ＫＨＭ ＫＨＭ⁃ＦＡ ＫＨＭ⁃ＰＳＯ 本文算法 ８．８０５ ４×１０ ８ ８．８０２ ７×１０ ８ ８．８０２ ８×１０ ８ ８．７９６ ５×１０ ８ ０．７６３ ０．７７６ ０．７７４ ０．７８０ １２．４２８ ９１．２５０ ９９．７８４ １７５．１８ ·８７８· 智 能 系 统 学 报 第 １０ 卷
第6期 朱书伟，等：融合并行混沌莹火虫算法的K-调和均值聚类 ·879- 表5p=3.5时各算法实验结果 [2]ZHANG Bin,HSU M,DAYAL U.K-harmonic means-a da- Table 5 The result of four algorithms when p =3.5 ta clustering algorithm.Technical Report HPL-1999-124 数据集 算法 KHM(X,C)F-measure 时间/s [R].Hewlett-Packard Laboratories,1999. [3]YANG Fengqin,SUN Tieli,ZHANG Changhai.An efficient KHM 109.84 0.892 0.178 hybrid data clustering method based on K-harmonic means KHM-FA 109.53 0.892 1.304 Iris and particle swarm optimization[J].Expert Systems with KHM-PSO 109.61 0.892 1.235 Applications,2009,36(6):9847-9852. 本文算法 109.22 0.892 2.311 [4]ALGUW AIZANI A,HANSEN P,MLADENOVIC N,et al. KHM 2567.9 0.700 0.684 Variable neighborhood search for harmonic means clustering KHM-FA 2558.9 0.700 5.096 Sphere [J].Applied Mathematical Modelling,2011,35 (6): KHM-PSO 2564.4 0.700 5.088 2688-2694. 本文算法 2553.5 0.700 9.662 [5]HUNG C H,CHIOU H M,YANG Weining.Candidate KHM 2.7175×100 0.630 0.273 groups search for K-harmonic means data clustering[J]. KHM-FA 1.4204×100 0.655 2.201 Applied Mathematical Modelling,2013,37(24):10123- Wine KHM-PSO 1.4419×100 0.636 2.140 10128 本文算法 1.4193×100 0.661 3.945 [6]汪中，刘贵全，陈恩红.基于模糊K-harmonic means的谱 KHM 7.0899×10 聚类算法[J].智能系统学报，2009,4(2)：95-99. 0.535 0.928 WANG Zhong,LIU Guiquan,CHEN Enhong.A spectral KHM-FA 2.3242×10 0.537 6.667 Image KHM-PSO clustering algorithm based on fuzzy K-harmonic means[J]. 1.6685×10 0.538 6.843 本文算法 CAAI Transactions on Intelligent Systems,2009,4(2): 1.4946×10 0.540 12.162 95-99 KHM 380733.23 0.455 1.966 [7]WU Xiaohong,WU Bin,SUN Jun,et al.A hybrid fuzzy K- KHM-FA 380013.07 0.458 14.892 CMC harmonic means clustering algorithm[J].Applied Mathe- KHM-PSO 380381.58 0.458 14.855 matical Modelling,2015,39(12):3398-3409. 本文算法 379782.74 0.460 26.632 [8]王建峰，孙超，姜守达.基于粒子群优化的组合测试数 KHM 4.1714×10 0.715 12.437 据生成算法[J].哈尔滨工程大学学报，2013,34(4)： KHM-FA 4.1630×109 0.721 92.174 477-482 Satellite KHM-PS04.1506×109 0.709 97.873 WANG Jianfeng,SUN Chao,JIANG Shouda.Improved al- 本文算法4.1597×10 0.724 175.75 gorithm for combinatorial test data generation based on parti- cle swarm optimization[J].Journal of Harbin Engineering 4结束语 University,2013,34(4):477-482. 由于传统的KHM算法具有易陷于局部最优解 [9]HE Yaoyao,YANG Shanlin,XU Qifa.Short-term cascaded hydroelectric system scheduling based on chaotic particle 的问题，本文基于一种高效的群智能优化算法提出 swarm optimization using improved logistic map[J].Com- 了一种混合的聚类算法，在KHM中融合了混沌优 munications in Nonlinear Science and Numerical Simula- 化改进的莹火虫算法，不断优化其聚类中心。实验 tiom,2013,18(7):1746-1756. 结果表明，本文算法的综合性能优于KHM以及2 [10]HE Yaoyao,XU Qifa,YANG Shanlin,et al.A novel cha- 种混合聚类算法KHM-FA和KHM-PSO,具有更高 otic differential evolution algorithm for short-term cascaded 的聚类准确性和稳定性，能够有效地避免陷入局部 hydroelectric system scheduling[J].International Journal 最优。但是本文算法的运行时间相对比较长，在数 of Electrical Power Energy Systems,2014,61:455- 据量较大的情况下具有较大的计算开销而影响了算 462. 法的效率，接下来可以针对算法效率的改善开展进 [11]廖煜雷，刘鹏，王建，等.基于改进人工鱼群算法的无 人艇控制参数优化[J].哈尔滨工程大学学报，2014， 一步研究工作。此外，可以尝试将PCLSFA应用于 35(7):800-806 其他的优化问题中。 LIAO Yulei,LIU Peng,WANG Jian,et al.Control pa- 参考文献： rameter optimization for the unmanned surface vehicle with the improved artificial fish swarm algorithm[J].Journal of [1]JAIN A K.Data clustering:50 years beyond K-means[J]. Harbin Engineering University,2014,35(7):800-806. Pattern Recognition Letters,2010,31(8):651-666 [12YANG Xinshe.Firefly algorithm,stochastic test functions
表 ５ ｐ ＝ ３．５ 时各算法实验结果 Ｔａｂｌｅ ５ Ｔｈｅ ｒｅｓｕｌｔ ｏｆ ｆｏｕｒ ａｌｇｏｒｉｔｈｍｓ ｗｈｅｎ ｐ ＝ ３．５ 数据集 算法 ＫＨＭ（ Ｘ，Ｃ ） Ｆ⁃ｍｅａｓｕｒｅ 时间／ ｓ Ｉｒｉｓ ＫＨＭ ＫＨＭ⁃ＦＡ ＫＨＭ⁃ＰＳＯ 本文算法 １０９．８４ １０９．５３ １０９．６１ １０９．２２ ０．８９２ ０．８９２ ０．８９２ ０．８９２ ０．１７８ １．３０４ １．２３５ ２．３１１ Ｓｐｈｅｒｅ ＫＨＭ ＫＨＭ⁃ＦＡ ＫＨＭ⁃ＰＳＯ 本文算法 ２ ５６７．９ ２ ５５８．９ ２ ５６４．４ ２ ５５３．５ ０．７００ ０．７００ ０．７００ ０．７００ ０．６８４ ５．０９６ ５．０８８ ９．６６２ Ｗｉｎｅ ＫＨＭ ＫＨＭ⁃ＦＡ ＫＨＭ⁃ＰＳＯ 本文算法 ２．７１７ ５×１０ １０ １．４２０ ４×１０ １０ １．４４１ ９×１０ １０ １．４１９ ３×１０ １０ ０．６３０ ０．６５５ ０．６３６ ０．６６１ ０．２７３ ２．２０１ ２．１４０ ３．９４５ Ｉｍａｇｅ ＫＨＭ ＫＨＭ⁃ＦＡ ＫＨＭ⁃ＰＳＯ 本文算法 ７．０８９ ９×１０ ９ ２．３２４ ２×１０ ９ １．６６８ ５×１０ ９ １．４９４ ６×１０ ９ ０．５３５ ０．５３７ ０．５３８ ０．５４０ ０．９２８ ６．６６７ ６．８４３ １２．１６２ ＣＭＣ ＫＨＭ ＫＨＭ⁃ＦＡ ＫＨＭ⁃ＰＳＯ 本文算法 ３８０ ７３３．２３ ３８０ ０１３．０７ ３８０ ３８１．５８ ３７９ ７８２．７４ ０．４５５ ０．４５８ ０．４５８ ０．４６０ １．９６６ １４．８９２ １４．８５５ ２６．６３２ Ｓａｔｅｌｌｉｔｅ ＫＨＭ ＫＨＭ⁃ＦＡ ＫＨＭ⁃ＰＳＯ 本文算法 ４．１７１ ４×１０ ９ ４．１６３ ０×１０ ９ ４．１５０ ６×１０ ９ ４．１５９ ７×１０ ９ ０．７１５ ０．７２１ ０．７０９ ０．７２４ １２．４３７ ９２．１７４ ９７．８７３ １７５．７５ ４ 结束语 由于传统的 ＫＨＭ 算法具有易陷于局部最优解 的问题，本文基于一种高效的群智能优化算法提出 了一种混合的聚类算法，在 ＫＨＭ 中融合了混沌优 化改进的萤火虫算法，不断优化其聚类中心。 实验 结果表明，本文算法的综合性能优于 ＫＨＭ 以及 ２ 种混合聚类算法 ＫＨＭ⁃ＦＡ 和 ＫＨＭ⁃ＰＳＯ，具有更高 的聚类准确性和稳定性，能够有效地避免陷入局部 最优。 但是本文算法的运行时间相对比较长，在数 据量较大的情况下具有较大的计算开销而影响了算 法的效率，接下来可以针对算法效率的改善开展进 一步研究工作。 此外，可以尝试将 ＰＣＬＳＦＡ 应用于 其他的优化问题中。 参考文献： ［１］ＪＡＩＮ Ａ Ｋ． Ｄａｔａ ｃｌｕｓｔｅｒｉｎｇ： ５０ ｙｅａｒｓ ｂｅｙｏｎｄ Ｋ⁃ｍｅａｎｓ［ Ｊ］． Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ Ｌｅｔｔｅｒｓ， ２０１０， ３１（８）： ６５１⁃６６６． ［２］ＺＨＡＮＧ Ｂｉｎ， ＨＳＵ Ｍ， ＤＡＹＡＬ Ｕ． Ｋ⁃ｈａｒｍｏｎｉｃ ｍｅａｎｓ⁃ａ ｄａ⁃ ｔａ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ． Ｔｅｃｈｎｉｃａｌ Ｒｅｐｏｒｔ ＨＰＬ⁃１９９９⁃１２４ ［Ｒ］． Ｈｅｗｌｅｔｔ⁃Ｐａｃｋａｒｄ Ｌａｂｏｒａｔｏｒｉｅｓ， １９９９． ［３］ＹＡＮＧ Ｆｅｎｇｑｉｎ， ＳＵＮ Ｔｉｅｌｉ， ＺＨＡＮＧ Ｃｈａｎｇｈａｉ． Ａｎ ｅｆｆｉｃｉｅｎｔ ｈｙｂｒｉｄ ｄａｔａ ｃｌｕｓｔｅｒｉｎｇ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ Ｋ⁃ｈａｒｍｏｎｉｃ ｍｅａｎｓ ａｎｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ［ Ｊ］． Ｅｘｐｅｒｔ Ｓｙｓｔｅｍｓ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ， ２００９， ３６（６）： ９８４７⁃９８５２． ［４］ＡＬＧＵＷＡＩＺＡＮＩ Ａ， ＨＡＮＳＥＮ Ｐ， ＭＬＡＤＥＮＯＶＩＣ Ｎ， ｅｔ ａｌ． Ｖａｒｉａｂｌｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｓｅａｒｃｈ ｆｏｒ ｈａｒｍｏｎｉｃ ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ［Ｊ ］． Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃａｌ Ｍｏｄｅｌｌｉｎｇ， ２０１１， ３５ （ ６ ）： ２６８８⁃２６９４． ［５］ ＨＵＮＧ Ｃ Ｈ， ＣＨＩＯＵ Ｈ Ｍ， ＹＡＮＧ Ｗｅｉｎｉｎｇ． Ｃａｎｄｉｄａｔｅ ｇｒｏｕｐｓ ｓｅａｒｃｈ ｆｏｒ Ｋ⁃ｈａｒｍｏｎｉｃ ｍｅａｎｓ ｄａｔａ ｃｌｕｓｔｅｒｉｎｇ ［ Ｊ］． Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃａｌ Ｍｏｄｅｌｌｉｎｇ， ２０１３， ３７（ ２４）： １０１２３⁃ １０１２８． ［６］汪中， 刘贵全， 陈恩红． 基于模糊 Ｋ⁃ｈａｒｍｏｎｉｃ ｍｅａｎｓ 的谱 聚类算法［Ｊ］． 智能系统学报， ２００９， ４（２）： ９５⁃９９． ＷＡＮＧ Ｚｈｏｎｇ， ＬＩＵ Ｇｕｉｑｕａｎ， ＣＨＥＮ Ｅｎｈｏｎｇ． Ａ ｓｐｅｃｔｒａｌ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｆｕｚｚｙ Ｋ⁃ｈａｒｍｏｎｉｃ ｍｅａｎｓ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２００９， ４ （ ２）： ９５⁃９９． ［７］ＷＵ Ｘｉａｏｈｏｎｇ， ＷＵ Ｂｉｎ， ＳＵＮ Ｊｕｎ， ｅｔ ａｌ． Ａ ｈｙｂｒｉｄ ｆｕｚｚｙ Ｋ⁃ ｈａｒｍｏｎｉｃ ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ［ Ｊ］． Ａｐｐｌｉｅｄ Ｍａｔｈｅ⁃ ｍａｔｉｃａｌ Ｍｏｄｅｌｌｉｎｇ， ２０１５， ３９（１２）： ３３９８⁃３４０９． ［８］王建峰， 孙超， 姜守达． 基于粒子群优化的组合测试数 据生成算法［ Ｊ］． 哈尔滨工程大学学报， ２０１３， ３４（ ４）： ４７７⁃４８２． ＷＡＮＧ Ｊｉａｎｆｅｎｇ， ＳＵＮ Ｃｈａｏ， ＪＩＡＮＧ Ｓｈｏｕｄａ． Ｉｍｐｒｏｖｅｄ ａｌ⁃ ｇｏｒｉｔｈｍ ｆｏｒ ｃｏｍｂｉｎａｔｏｒｉａｌ ｔｅｓｔ ｄａｔａ ｇｅｎｅｒａｔｉｏｎ ｂａｓｅｄ ｏｎ ｐａｒｔｉ⁃ ｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｈａｒｂｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ， ２０１３， ３４（４）： ４７７⁃４８２． ［９］ＨＥ Ｙａｏｙａｏ， ＹＡＮＧ Ｓｈａｎｌｉｎ， ＸＵ Ｑｉｆａ． Ｓｈｏｒｔ⁃ｔｅｒｍ ｃａｓｃａｄｅｄ ｈｙｄｒｏｅｌｅｃｔｒｉｃ ｓｙｓｔｅｍ ｓｃｈｅｄｕｌｉｎｇ ｂａｓｅｄ ｏｎ ｃｈａｏｔｉｃ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ｕｓｉｎｇ ｉｍｐｒｏｖｅｄ ｌｏｇｉｓｔｉｃ ｍａｐ ［ Ｊ］． Ｃｏｍ⁃ ｍｕｎｉｃａｔｉｏｎｓ ｉｎ Ｎｏｎｌｉｎｅａｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｎｕｍｅｒｉｃａｌ Ｓｉｍｕｌａ⁃ ｔｉｏｎ， ２０１３， １８（７）： １７４６⁃１７５６． ［１０］ＨＥ Ｙａｏｙａｏ， ＸＵ Ｑｉｆａ， ＹＡＮＧ Ｓｈａｎｌｉｎ， ｅｔ ａｌ． Ａ ｎｏｖｅｌ ｃｈａ⁃ ｏｔｉｃ ｄｉｆｆｅｒｅｎｔｉａｌ ｅｖｏｌｕｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｈｏｒｔ⁃ｔｅｒｍ ｃａｓｃａｄｅｄ ｈｙｄｒｏｅｌｅｃｔｒｉｃ ｓｙｓｔｅｍ ｓｃｈｅｄｕｌｉｎｇ ［ Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｅｌｅｃｔｒｉｃａｌ Ｐｏｗｅｒ ＆ Ｅｎｅｒｇｙ Ｓｙｓｔｅｍｓ， ２０１４， ６１： ４５５⁃ ４６２． ［１１］廖煜雷， 刘鹏， 王建， 等． 基于改进人工鱼群算法的无 人艇控制参数优化［ Ｊ］． 哈尔滨工程大学学报， ２０１４， ３５（７）： ８００⁃８０６． ＬＩＡＯ Ｙｕｌｅｉ， ＬＩＵ Ｐｅｎｇ， ＷＡＮＧ Ｊｉａｎ， ｅｔ ａｌ． Ｃｏｎｔｒｏｌ ｐａ⁃ ｒａｍｅｔｅｒ ｏｐｔｉｍｉｚａｔｉｏｎ ｆｏｒ ｔｈｅ ｕｎｍａｎｎｅｄ ｓｕｒｆａｃｅ ｖｅｈｉｃｌｅ ｗｉｔｈ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｒｔｉｆｉｃｉａｌ ｆｉｓｈ ｓｗａｒｍ ａｌｇｏｒｉｔｈｍ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｈａｒｂｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ， ２０１４， ３５（７）： ８００⁃８０６． ［１２］ＹＡＮＧ Ｘｉｎｓｈｅ． Ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ， ｓｔｏｃｈａｓｔｉｃ ｔｅｓｔ ｆｕｎｃｔｉｏｎｓ 第 ６ 期 朱书伟，等：融合并行混沌萤火虫算法的 Ｋ⁃调和均值聚类 ·８７９·
·880· 智能系统学报 第10卷 and design optimisation[]].International Journal of Bio- [20]莫愿斌，马彦追，郑巧燕，等.单纯形法的改进萤火虫 Inspired Computation,2010,2(2):78-84. 算法及其在非线性方程组求解中的应用J].智能系统 [13]赵玉新，YANG X S,刘利强.新兴元启发式优化方法 学报，2014,9(6)：747-755. [M].北京：科学出版社，2013：148-157. MO Yuanbin,MA Yanzhui,ZHENG Qiaoyan,et al.Im- [14]SENTHILNATH J,OMKAR S N,MANI V.Clustering u- proved firefly algorithm based on simplex method and its sing firefly algorithm:performance study[J].Swarm and application in solving non-linear equation groups[J].CAAI Evolutionary Computation,2011,1(3):164-171. Transactions on Intelligent Systems,2014,9(6):747- [15]FISTER Jr I,PERC M,KAMAL S M.A review of chaos- 755. based firefly algorithms:perspectives and research challen- 作者简介： ges[J].Applied Mathematics and Computation,2015, 朱书伟，男，1990年生，硕士研究生， 252:155-165. 主要研究方向为人工智能与模式识别。 [16]GANDOMI A H,YANG X S,TALATAHARI S,et al. Firefly algorithm with chaos[J].Communications in Non- linear Science and Numerical Simulation,2013,18(1): 89-98. [17]YUAN Xiaofang,ZHAO Jingyi,YANG Yimin,et al.Hy- 周治平，男，1962年生，教授，博士， brid parallel chaos optimization algorithm with harmony 主要研究方向为智能检测、自动化装 search algorithm[].Applied Soft Computing,2014,17: 置、网络安全等。 12-22. [18]YUAN Xiaofang,ZHANG Ting,XIANG Yongzhong,et al. Parallel chaos optimization algorithm with migration and merging operation[J].Applied Soft Computing,2015,35: 591-604. 张道文，男，1989年生，硕士研究生， [19]YANG Dixiong,LIU Zhenjun,ZHOU Jilei.Chaos optimi- 主要研究方向为数据挖掘与人工智能。 zation algorithms based on chaotic maps with different probability distribution and search speed for global optimi- zation[J].Communications in Nonlinear Science and Nu- merical Simulation,2014,19(4):1229-1246
ａｎｄ ｄｅｓｉｇｎ ｏｐｔｉｍｉｓａｔｉｏｎ ［ Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｂｉｏ⁃ Ｉｎｓｐｉｒｅｄ Ｃｏｍｐｕｔａｔｉｏｎ， ２０１０， ２（２）： ７８⁃８４． ［１３］赵玉新， ＹＡＮＧ Ｘ Ｓ， 刘利强． 新兴元启发式优化方法 ［Ｍ］． 北京： 科学出版社， ２０１３： １４８⁃１５７． ［１４］ＳＥＮＴＨＩＬＮＡＴＨ Ｊ， ＯＭＫＡＲ Ｓ Ｎ， ＭＡＮＩ Ｖ． Ｃｌｕｓｔｅｒｉｎｇ ｕ⁃ ｓｉｎｇ ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ： ｐｅｒｆｏｒｍａｎｃｅ ｓｔｕｄｙ ［ Ｊ］． Ｓｗａｒｍ ａｎｄ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ， ２０１１， １（３）： １６４⁃１７１． ［１５］ＦＩＳＴＥＲ Ｊｒ Ｉ， ＰＥＲＣ Ｍ， ＫＡＭＡＬ Ｓ Ｍ． Ａ ｒｅｖｉｅｗ ｏｆ ｃｈａｏｓ⁃ ｂａｓｅｄ ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍｓ： ｐｅｒｓｐｅｃｔｉｖｅｓ ａｎｄ ｒｅｓｅａｒｃｈ ｃｈａｌｌｅｎ⁃ ｇｅｓ ［ Ｊ］． Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｃｏｍｐｕｔａｔｉｏｎ， ２０１５， ２５２： １５５⁃１６５． ［１６］ ＧＡＮＤＯＭＩ Ａ Ｈ， ＹＡＮＧ Ｘ Ｓ， ＴＡＬＡＴＡＨＡＲＩ Ｓ， ｅｔ ａｌ． Ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｃｈａｏｓ［ Ｊ］． Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｉｎ Ｎｏｎ⁃ ｌｉｎｅａｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｎｕｍｅｒｉｃａｌ Ｓｉｍｕｌａｔｉｏｎ， ２０１３， １８（１）： ８９⁃９８． ［１７］ＹＵＡＮ Ｘｉａｏｆａｎｇ， ＺＨＡＯ Ｊｉｎｇｙｉ， ＹＡＮＧ Ｙｉｍｉｎ， ｅｔ ａｌ． Ｈｙ⁃ ｂｒｉｄ ｐａｒａｌｌｅｌ ｃｈａｏｓ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｈａｒｍｏｎｙ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ［Ｊ］． Ａｐｐｌｉｅｄ Ｓｏｆｔ Ｃｏｍｐｕｔｉｎｇ， ２０１４， １７： １２⁃２２． ［１８］ＹＵＡＮ Ｘｉａｏｆａｎｇ， ＺＨＡＮＧ Ｔｉｎｇ， ＸＩＡＮＧ Ｙｏｎｇｚｈｏｎｇ， ｅｔ ａｌ． Ｐａｒａｌｌｅｌ ｃｈａｏｓ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｍｉｇｒａｔｉｏｎ ａｎｄ ｍｅｒｇｉｎｇ ｏｐｅｒａｔｉｏｎ［Ｊ］． Ａｐｐｌｉｅｄ Ｓｏｆｔ Ｃｏｍｐｕｔｉｎｇ， ２０１５， ３５： ５９１⁃６０４． ［１９］ＹＡＮＧ Ｄｉｘｉｏｎｇ， ＬＩＵ Ｚｈｅｎｊｕｎ， ＺＨＯＵ Ｊｉｌｅｉ． Ｃｈａｏｓ ｏｐｔｉｍｉ⁃ ｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｂａｓｅｄ ｏｎ ｃｈａｏｔｉｃ ｍａｐｓ ｗｉｔｈ ｄｉｆｆｅｒｅｎｔ ｐｒｏｂａｂｉｌｉｔｙ ｄｉｓｔｒｉｂｕｔｉｏｎ ａｎｄ ｓｅａｒｃｈ ｓｐｅｅｄ ｆｏｒ ｇｌｏｂａｌ ｏｐｔｉｍｉ⁃ ｚａｔｉｏｎ［ Ｊ］． Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｉｎ Ｎｏｎｌｉｎｅａｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｎｕ⁃ ｍｅｒｉｃａｌ Ｓｉｍｕｌａｔｉｏｎ， ２０１４， １９（４）： １２２９⁃１２４６． ［２０］莫愿斌， 马彦追， 郑巧燕， 等． 单纯形法的改进萤火虫 算法及其在非线性方程组求解中的应用［ Ｊ］． 智能系统 学报， ２０１４， ９（６）： ７４７⁃７５５． ＭＯ Ｙｕａｎｂｉｎ， ＭＡ Ｙａｎｚｈｕｉ， ＺＨＥＮＧ Ｑｉａｏｙａｎ， ｅｔ ａｌ． Ｉｍ⁃ ｐｒｏｖｅｄ ｆｉｒｅｆｌｙ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｓｉｍｐｌｅｘ ｍｅｔｈｏｄ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎ ｉｎ ｓｏｌｖｉｎｇ ｎｏｎ⁃ｌｉｎｅａｒ ｅｑｕａｔｉｏｎ ｇｒｏｕｐｓ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１４， ９ （ ６）： ７４７⁃ ７５５． 作者简介： 朱书伟，男，１９９０ 年生，硕士研究生， 主要研究方向为人工智能与模式识别。 周治平，男，１９６２ 年生，教授，博士， 主要研究方向为智能检测、自动化装 置、网络安全等。 张道文，男，１９８９ 年生，硕士研究生， 主要研究方向为数据挖掘与人工智能。 ·８８０· 智 能 系 统 学 报 第 １０ 卷