启发式搜索和增量聚类相结合的点填充和水平设置算法对多峰函数优化的研究

沙特国王大学学报启发式搜索和增量聚类相结合的点填充和水平设置算法赵强，李昌伟东北林业大学交通运输学院，黑龙江阿提奇莱因福奥文章历史记录：2022年4月19日收到2022年7月7日修订2022年8月6日接受2022年8月19日网上发售保留字：多模态优化点填充启发式搜索增量聚类粒子群算法A B S T R A C T针对多峰函数优化问题，提出了一种新的集启发式搜索和增量聚类于一体的点填充和水平设置全局算法。该算法由点填充、层次设置、启发式搜索和增量聚类组成迭代体。其主要思想是利用连续多轮点填充抽样加启发式搜索来寻找全局最优解。在每次迭代中，在点填充采样之后执行水平集操作以去除一些坏点。通过粒子群优化算法（PSO）或遗传算法（GA）的启发式搜索，进一步提高精度，同时找到更多新的可能的全局最优解。聚类操作，谱聚类分析，以确定初始点集的聚类数，然后进行自适应增量聚类，进一步用于分类点接近不同的最优到不同的集群。首先给出了该算法的基本框架，然后通过优化Rastrigin函数给出了算法的具体实现，并给出了理论证明。对十个典型的多峰函数、一个组合CEC基准集和一个工程问题进行了优化实验。与其他8种算法进行了统计比较，结果表明该算法具有更好的效果。©2022作者（S）。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY许可下的文章（http://creativecommons.org/licenses/by/4.0/）。1. 介绍一个多峰函数通常有一个全局最优解或多个全局最优解伴随着大量的局部最优解。多峰函数全局优化的任务是从多个局部最优解中由于多峰函数的局部最优解的存在，使得多峰函数的全局最优解难以找到，而许多工程和科学应用只能转化为多峰函数优化问题的数学模型，而不能转化为简单的单峰函数优化问题。因此，多峰函数的全局优化问题在过去的几十年里引起了人们越来越多的关注众所周知，一些传统的*通讯作者。电子邮件地址：zhaoqiang@nefu.edu.cn（问：Zhao）.沙特国王大学负责同行审查制作和主办：Elsevier方法具有全局优化能力，这些方法不仅包括确定性方法：分支定界方法（Eichfelder等人，2021）;间隔方法（Shen等人，2003）;调谐方法（Nichita等人，2008）、填充函数方法（Liu等人，2020）和积分水平集方法（Zheng和Zhuang，1995），而且还有随机优化方法：模拟退火（Kirkpatrick等人，1983），遗传算法（Thakur，2014）;和粒子群优化（Kennedy和Eberhart，1995）。使用粒子群优化来解决多模态函数优化的工作包括NichePSO（Brits等人，2007）、具有局部搜索的小生境粒子群优化（Qu等人， 2012）、基于梯度的粒子群优化算法（Noel，2012）、集合粒子群优化算法（Lynn和Suganthan，2017）和模拟退火粒子群优化（Li等人，2021年）。上述方法大都提出了跳出局部最优的机制。对于全局优化，最好是尽可能多地定位局部（或全局）极值点，并进一步从所有这些极值点中寻找全局极值点，这可以大大提高找到全局最优解（或最优解）的概率聚类分析可以针对不同的局部极值点将搜索群体或种群划分为不同的组，有助于实现https://doi.org/10.1016/j.jksuci.2022.08.0081319-1578/©2022作者。由Elsevier B.V.代表沙特国王大学出版。这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comQ. Zhao和C. 李沙特国王大学学报8261De并将上述思想引入到本文提出的算法近年来，利用聚类分析来提高多模态优化问题的全局搜索能力成为一个很有前途的研究热点。Lin等人将最近最佳聚类（NBC）引入到用于多模态优化的差分进化（DE）中（Lin等人，2021），他们的算法（称为FBK-DE）首先使用NBC将种群划分为多个物种，每次迭代中具有最小尺寸限制。然而，使用NBC重新启动集群时，总是会忽略上一次迭代获得的有用信息。聚类数由一个参数f控制，同时受一个参数minsize约束，并给出了其随迭代次数的调整规则.根据问题的维数，进一步给出了minsize的上界。Schoen等人提出将聚类型决策应用于何时开始局部搜索DE以进行大规模全局优化（Schoen和Tigli，2021）。他们使用多水平单连锁（MLSL）作为聚类方法，但没有讨论如何确定聚类数。Dominico等人提出了一种自适应差分进化算法（Dominico和Parpinelli，2021），名为NCjDE-2LSar，专注于在多模态优化中找到外部候选溶液代表可能的峰，并被馈送用于进一步开发。Jiang等人使用聚类辅助的多目标填充准则来同时提高用于昂贵的约束全局优化问题的目标和约束的高斯过程回归模型的准确性（Jiang等人，2021），并采用聚类选择方法保持样本点的多样性。在聚类操作中，他们也使用了DBSCAN，它可以自动确定聚类的个数，但DBSCAN一般只适用于凸样本集，而且不是增量聚类算法，每次迭代都要进行一次新的DBSCAN聚类操作。Yang等人将K-Means聚类应用于共生生物搜索的初始解以创建子种群（Yang andSutrisno，2020），他们认为初始化的聚类数k可能不是最优的，并进一步采用合并程序来更新k值和聚类中心。Sim等人使用聚类分析来选择优化的有效数据从生成对抗网络（GAN）和深度卷积GAN（DCGAN）生成的数据中，它们被进一步应用于结构拓扑优化（Sim等人，2021），采用K-Means聚类算法，并选择肘形法确定最优聚类数。但是，它需要改进K-Means聚类算法，以最小化每个聚类的质心的距离之和。Pence等使用聚类和抛物线逼近来解决无约束全局优化，他们采用模糊K- Means聚类算法，在每次迭代中运行一个或两个步骤，以缩短下一个抛物线系数的训练时间（Pence等，2016年）。Xiong等人将筛选-聚类操作引入蒸馏过程优化（Xiong等人，2021年）。然后将搜索域划分为若干个子域，并利用Kriging代理模型预测优化目标在每个子域中的变化。值得注意的是，他们通过Calinski-Harabasz（CH）指数方法确定了聚类数，该方法需要多轮试验才能最终确定聚类数。至于在多目标/多目标优化中使用的聚类技术：Ding等人提出在他们的多目标优化问题的目标约简算法中使用自适应传播树聚类（Ding等人，（2021年 ）通过自适应地确定聚类数，可以正确地对离群点进行聚类，但需要多次更新它的参数a来调整簇数。Chen等人亲提出了一种基于聚类的费用邻域回归模型多目标优化问题（Chen等人，2019年）。他们使用层次凝聚聚类方法的一种变体，将当前种群中的个体划分为给定数量的聚类，并从每个聚类中选择一个基础个体来代表其聚类。选择是为了平衡收敛性和多样性，选择出的基在他们的方法中，给定的聚类数被设置为4+N/T，其中N是种群大小，T是邻域大小：T=D+4，其中D是优化问题的维度Li等人提出了在求解多目标优化时更新和维护外部档案的聚类操作（Li等人，2020年）。他们采用K-Means聚类来输出更多样化的Pareto边界。至于集群的数量，他们简单地将其设置为N/2，其中N是群的大小。Liang等人在其改进的差分进化算法中使用聚类技术来解决多模态多目标优化问题（Liang等人，2021年）。它们采用K-Means聚类算法，聚类数k的取值采用线性关系k=F/n，其中F为个体数，n为正整数。Sahraei等人提出了一种基于密度的空间聚类方法，以 维护随机多目标优 化算法的各种解决方 案（Sahraei 和Asadzadeh，2021）。该方法使用DBSCAN在解评估后动态聚类决策空间中的解，并且他们建议在优化过程之前咨询决策者关于考虑计算预算的两个参数，以及使用基于聚类的解归档进行高效和有效的优化。上述研究总结列于表1，由此可见，聚类分析可以有效地估计目标函数的最优分布，改善优化算法的搜索方向。聚类技术应用于优化的问题和难点主要有三个方面：一是聚类数目的确定，二是在优化过程的每一次迭代中，除了重新开始一个新的聚类外，如何实现按顺序迭代步骤的连续增量聚类第三，也是最困难的，当数据点没有明显的分布特征时，聚类结果往往是不准确的，甚至有很大的误差本文的主要动机之一就是解决上述三个问题，而谱聚类分析将用于解决第一个问题。对于第二个问题，采用增量聚类的方法，充分利用已有的聚类结果，提高聚类的连续性，同时减少计算量。对于第三个问题，在聚类之前先对数据点进行水平集运算，筛选并去除目标函数中的一些坏点这些水平集操作将使数据点分布具有更明显的特征，从而促进进一步的聚类操作更准确。如文献（Zheng and Zhuang，1995）所示，水平集方法可以用于通过多轮水平设置和点填充采样操作定位包括在几个逐渐缩小的区域中的局部和全局最优值来解决全局优化，并且最近Liu等人也将水平集方法应用于解决大规模结构优化（Liuet al.，2019年）。但是，单纯的水平设置和点填充采样，不结合其他操作，无法达到足够高的求解精度。如果结合聚类技术，就可以获得最优分布特征的知识，Q. Zhao和C. 李沙特国王大学学报8262ð Þð Þx2GRx2G表1近年来典型聚类辅助优化算法算法辅助聚类方法簇数控制参考和年份问题FBK-DE算法最佳聚类（NBC）参数/和（Lin等人，（2021年）;多峰优化minsize2021问题（MMOPs）聚类模因DE（C-MDE）多级单级联动没有讨论（Schoen和Tigli，大规模全球2021年）; 2021年优化自适应差分进化算法基于密度的空间聚类自动（多米尼克和多峰优化（NCjDE-2LSar）噪声应用（DBSCAN）决定于Parpinelli，2021）;问题（MMOPs）DBSCAN2021多目标加密辅助DBSCAN，K-Means聚类自动（Jiang等人，（2021年）;昂贵的黑匣子标准（ECGO-CMIC）确定DBSCAN2021问题共生生物搜索K-Means聚类采用合并（杨和Sutrisno，高维算法（CSOS）程序2020年）; 2020年优化问题GANs和聚类分析的结合K-Means聚类肘击法（Sim等人，（2021年）;结构拓扑（GANs-CA）2021优化聚类和抛物线近似模糊K均值聚类N/3（Pence等人， 2016年）;无约束全局（GOBC-PA）2016优化筛选聚类辅助克里格法K-Means聚类卡林斯基-哈拉巴斯（Xiong等人，（ 2021年）;蒸馏过程最优化（SCAKO）(CH)指数法2021优化目标约简方法自适应传播树聚类自适应参数（Ding等人，（2021年）;多目标高级群集多目标邻域回归层次凝聚聚类一k = 4+N/T2021（Chen等人， 2019年）;优化问题昂贵的多目标优化算法（MONRO）2019优化问题多目标粒子群优化算法K-Means聚类k =N /2（Li等人，2020年）;2020年多目标优化问题基于遗传算法的差分进化算法K-Means聚类k =dF /ne（Liang等人，（2021年）;2021多模态多目标优化问题Pareto归档-动态标注基于密度的空间聚类DBSCAN（Sahraei和水资源问题搜索（PA-DDS）随机MO算法Asadzadeh，2021）;2021不同的分离区域。如果进一步辅以启发式搜索，则解的精度和全局最优性也得到了很大的提高。在过去的几十年中，受自然和社会现象或事件的启发，元启发式搜索算法取得了快速发展，例如从经典的GA（Holland，1992）和差分进化（DE）（Storn和Price，1995）到萤火虫算法（FA）（Yang，2008）等。 这些算法被深入研究用于复杂的无约束优化问题（Molina等人，2018年; Tuba和Bacanin，2014年），并进一步用于限制型（Strumberger等人， 2017年）。这些算法在许多工程优化领域取得了成功，最近通过与其他有前途的机器学习技术相结合而传播到不同的领域，并且已经证明能够获得如在许多情况下所示的出色结果，例如通过与机器学习相结合来预测流行病传播（Zivkovic等人，2021），以及通过优化卷积神经网络来解决医学图像分类（Bacanin等人， 2021年）。基于上述动机，本文提出了一种新的全局优化算法，其主要思想是建立一种新的算法，将点填充采样和水平设置操作与启发式搜索和聚类操作相结合，实现全局优化。概括地说，该算法由四个顺序操作组成：多点填充、水平设置、搜索和聚类，因此为了后面的描述简洁起见，该算法被称为MILSC算法（MILSCA）。 在该算法中，搜索操作采用启发式搜索（包括改进的粒子群算法和遗传算法），并分别在每个聚类区域内和精英聚类外进行局部搜索和全局搜索，以利用已获得的最优解并探索更多未知的最优解区域。本文的贡献是介绍了MILSCA的基本框架、具体实现、理论证明和仿真实验验证。MILSCA的新颖之处在于它的框架完全不同于任何现有的算法。另外值得一提的是，在利用谱聚类分析确定聚类数时，实现准确聚类的关键操作本文发现了一种新的数估计方法本文的作者组织如下。第二节详细介绍了MILSCA的设计与实现。第三节将讨论MILSCA算法的理论分析和全局收敛性证明。MILSCA的仿真实验验证将在第4节中完成。在第5节中，进一步提出了讨论。最后一节将得出一些结论。2. 一种新的全局优化算法：MILSCA2.1. 多峰函数假设连续多峰函数f（x）= f（x1，x2，. . ，xn）的全局优化问题，其描述为最小fx1若 点 xω2G ， 存 在 邻 域 U<$xω;d< $ $>fxjxω-dxxω<$dg 使 得f<$xω<$6f<$x<$f对任意x2U<$xω;d <$成立，则xω是f<$x<$f在区域G中的局部最优，f<$xω <$是局部函数极小值.若不等式f<$xω<$6f<$x<$6对任意x2G成立，则xω是区域G中f x的一个整体极值点所有的全局极值点构成全局最优解集{xω}。复杂多模态功能优化模型，这涉及到搜索全局最优值。所以目标是找到点集{xω}满足fxω6minfx2以目标函数f_x的局部特征f_x= f_（max）/f_（max）纯粹随机点的替代方法抽样与Monte-Carlo模拟相结合的方法存在计算量大、求解效率和精度不高的缺点，但理论上具有较高的全局收敛性。 积分水平集方法，在一个Q. Zhao和C. 李沙特国王大学学报8263~XJ2半-]广义的随机点抽样算法是随机点抽样的极端形式，只属于概念性算法。该方法具有一定的参考意义，但仍需进一步改进，以满足实际工程优化的需要。受积分水平集方法的启发，本文提出了一种新的多峰函数优化算法。2.2. MILSCA框架该算法基于点填充采样和积分水平集方法。该算法通过寻找尽可能多的最优解（局部或全局）来寻找全局最优解，同时引入启发式局部搜索和启发式全局搜索来分别提高最优解的精度和增强全局收敛性。MILSCA的新贡献是在整数水平集方法的基础上发展了一种新的实用的离散水平集方法，同时融合了聚类和启发式搜索操作，使MILSCA成为一种有效的、高效的算法。MILSCA的流程图如图1所示，MILSCA的程序设计如下。(1) 步骤1，初始多点填充采样：在搜索空间随机创建一个初始点集作为问题的(2) 第二步，水平集操作：通过一系列的水平集操作，删除函数值较大的坏点，自然地使保留的点有足够的距离分离，从而使以后的聚类操作更加容易和准确。(3) 步骤3，启发式局部搜索：执行启发式局部搜索操作，使保留的点进一步向其附近的局部最优（也可能是全局最优）移动，为将来的聚类做进一步的密集准备。(4) 第四步，初始聚类：1) 在聚类操作之前，首先使用谱聚类分析来估计聚类的数目。2) 然后采用K-Means或其他聚类算法执行聚类操作，生成指定数量的聚类。(5) 步骤5，簇内点填充采样、水平集操作和启发式局部搜索：1) 计算每个簇的范围，即包围簇中所有点的超立方体。2) 根据聚类的平均函数值（afv）为每个聚类分配不同的权重。具有较小afv的聚类将具有较大的权重。3) 根据所有聚类的权重，对聚类进行非线性排序.4) 在每个聚类中进行点填充采样：至于填充到每个聚类中的点数，由轮盘选择策略决定，每个聚类在轮盘上所占的区域由其非线性排名决定。5) 对每个簇的所有点（包括新填充的点）分别进行几次水平集运算。6) 使每个簇进行启发式局部搜索，以提高解的精度或找到新的局部最优解（如果存在）。(6) 第六步，簇外点填充采样和启发式全局搜索：从所有簇中选取一定比例的精英簇，在每个簇外和周围随机填充点，以所有新填充的点（或加上部分已存在的精英点）为初始集合，采用启发式搜索更新这些点。(7) 第7步，自适应增量聚类：使用自适应增量聚类算法对所有这些新点（由第5步和第6步创建）进行聚类。(8) 步骤8，多轮重复迭代：即转到步骤5，重复步骤5和7的操作，直到满足预定义的终止条件或其他迭代停止标准，然后转到步骤9。(9) 第9步，结束：保存并输出最优值及其函数值。2.3. 通过一个二维优化实例，结合优化二维（2D）Rastrigin函数的例子，将介绍MILSCA的上述过程的每个步骤的详细实现nfx第1页.x2-10cos2pxj10xj2½-5：12;5：12];nFig. 1. MILSCA流程图。¼2 ð3Þ该函数在5：12; 5：12范 围 内 共 有 几 十 个 极 小 点 ，其形状和等值线如图所示。 二、其目的是尽可能多地定位最小点，并最终找到所有这些最小点中的全局最小值。对应于前面的过程，其所有步骤的详细实现如下。(1) 第一步，初始点填充采样：在算法开始时，随机填充一组点{xi}，i<$1; 2;：;M0，使其均匀分布在解空间x<$00中，这可以通过调用创建均匀分布的函数来完成。伪随机数填充有1000个采样点的Rastrigin函数的等值线图如图所示。3.第三章。Q. Zhao和C. 李沙特国王大学学报8264¼ ð Þ ¼我FFf0图四、10f0f11100F图二.二维Rastrigin函数的景观图三. 初始点填充抽样的等高线图。见图4。第一次电平设置操作的结果。(2) 步骤2，水平设置操作：基于平均值的水平设置操作如下。计算所有这些点的所有函数值：fi f x i，i1; 2;：M0.计算所有函数值的平均值，根据-f0¼M01/1FM04然后求解水平集L-0 1/4nxj. fj6-f0;j1;2;：：;M0。保留属于L的点-0，丢弃{xi}的其他点，并且以上完成平均值电平设置操作。基于平均值的电平设置操作的保留点的数量通常是不确定的，并且在此使用基于中值的电平设置操作，因为它明确地保留所有这些点的一半。按升序对所有函数值进行排序，确定其中值-0、解决的中值基于水平集图五. 第二次电平设置操作的结果。L-01/4。xj. fj6-f0;j<$1;2;：;M00，且结果为L-0显示的是（3）第三步，启发式局部搜索：进一步使每个点移动接下来，计算中位数-f0保留点的函数值，并求解L-01/4。xk. fk6-f0;k<$1;2;：;-l0mm，保留属于L-f0的点 丢弃L-f0的其他点 和接近其最近的最小点。任何随机搜索方法都是可选择的，只要它是局部搜索算法。而纯随机搜索方法效率相对较慢。启发式遗传算法、进化算法、粒子群算法等算法具有较高的效率，也许是更好的选择。本文采用粒子群算法结果如图5所示。类似地，进一步完成第三至第五水平集操作，并且结果示于图1A和1B中。六比八 从这些图中可以看出，接近不同局部最优的点逐渐清晰地分开。算法，并提出了一种改进的本地版本，适用于本地搜索粒子群优化算法最初由Kennedy和Eberhart（1995）提出，已被证明是一种有效的群体智能算法XQ. Zhao和C. 李沙特国王大学学报8265我我>：12我i;ji;ji;ji;ji;ji;jJi;j21我我21232我323-xi Þð5Þv i¼w v ic1r1-xi 2016年12月24日;i;jðkþ1Þ;;;i;jðkþ1Þi;ji;j活泼地上标（k）表示第k次迭代。C1和C2都是加速常数，并且对于全局搜索通常设置为C1/C2/C2r1和r2都是区间[0，1]内的随机数一种以多步位置可选更新PSO （MPPSO ）命名的PSO 变体（Gao等人，2007），这里它用于局部搜索，c2取小值，因此它将被称为局部MPPSO。 该算法将Eq. （5）分三步，即vk1分为wvk ，wvkc1r1pbestk-xk， wvkc1r1pbestk-xk分别为：2r2r2gbest，2r2gbest，2r2gbest，2gbest，2gbest，2gb根据Eq。（六）、这三个位置中最好的一个将被选为最终更新的位置。所有更新规则的局部MPPSO被描述为vk1wvk;xk1xkvk1ð7Þ见图6。 第三次电平设置操作的结果。1i1i1vk1vk1c1·r1·pbestk-xk;xk1xk1vk1ð8Þvk1vk1c2·r2·gbestk-xk;xk1xk1vk1ð9Þ8>xk11如果fxk1 6fxk1和fxk1 6fxk11213xk1xk1<如果fxk1 6fxk1和fxk1 6fxk1我2 2K 131 2否则3ð10Þ其中vk1、vk1和vk1是可选的更新速度，1 2xk1，xk1 和xk13是的对应可选更新1 2 3岗位这种局部MPPSO算法的步骤如下。见图7。 第四次电平设置操作的结果。见图8。 第五次电平设置操作的结果。基于优化方法。其主要迭代机制包括以下速度和位置更新规则：i) 初始化：生成n0的颗粒与随机位置x1;x2;：;xn0，以及速度v 1;v 2;：;v n0。ii) 根据问题的目标函数值评估每个粒子的适应度iii) 个人和全球最好位置更新：如果fpbest i>fx i，则令 pbest ix i ， 并 在 fpbest i 中 搜 索 最 小 值 f min 。如 果f_gbest_n>f_min，则设gbest_n = 1/4 x_min，其中x_min是与f_min相关联的粒子。iv) 速度和位置更新：使用等式更新第i个粒子速度。（7）-（9）.v) 根据等式选择最佳位置作为最终位置（十）、vi) 重复步骤ii至v，直到达到给定的最大迭代次数或满足其他停止标准。局部MPPSO算法的优点是通过引入两个中间点x∈k∈1，xk 1，也使得标准PSO的中心轨迹具有一定的‘width’,对上述局部MPPSO算法进行了进一步改进，改进了对粒子跳出搜索范围的处理。新的处理规则是，ðkþ1Þ克雷奇克雷奇克雷奇克雷奇克雷奇8xk1xjmin0：25xjmax-xjminifxk1xjminxk1xkvk1ð6Þ：xi;j¼xj;max-0： 25xj;max-xj;min如果xi;j>xj;maxi;ji;ji;j其中i= 1，2，3表示三个可选位置。xj;min和xj;max其中w是惯性重量，xk和vk是当前位置，表示j维的下界和上界第i个粒子相对于第j维的速度，分别。ð11ÞQ. Zhao和C. 李沙特国王大学学报8266第1/2段ij我我改进的局部MPPSO的伪代码在下面的算法1中给出。本文将上述超限粒子四分之一区域随机再生的处理方法应用于第9行，对MPPSO算法进行了改进，效果明显确保属于不同局部最优的点足够分离。虽然水平集运算和局部搜索都可以使点分离，但更多的水平集运算会去除许多点，减少点的数量，这是有帮助的为了减少计算成本，但是局部搜索将保持算法1.局部MPPSO（输入参数：x，xmin，xmax，maxIter）1：设置参数：维度（Dim_num）、群大小（N）、系数（c1和c2）、惯性权重（w）、Max_Iter（iterMax）、位置边界（xj，max和xj，min）;速度limit（vmax和vmin）2：初始化swarm：x=xmin+ rand（pS，dS）.*（x max-xmin）3：评估所有粒子：f（x）= f（x1，x2，. . ，xn）4：初始化个体最佳和全局最佳：pbesti=xi，fpesti=f（xi），gbest=xmin，（xmin对应于fmin，且fmin= min{f（xi）}5：对于iter= 1到maxIter do6：根据等式（1）更新第一可选速度和（七）7：根据等式7更新第二可选速度和（八）8：根据等式（1）更新第三可选速度和（九）9：根据等式9处理速度和位置超限。（十一）10：根据以下公式确定最终更新位置：分数不变。(4) 步骤4，初始聚类：使用聚类算法将图9中的这些点（本文将其集合称为点集Sp）划分为不同的聚类。对于初始聚类，在聚类前先用谱聚类分析来估计聚类数，即c0。其步骤如下。①计算Sp的亲和度（或权重）矩阵W，应用高斯核：kxi-xjk2Wxi;xje-2r212其中xi和xj是来自Sp的任意两个数据点，r是宽度参数。②构造拉普拉斯算子为：拉普拉斯方程，p= 13.00，D-13.00其中D是对角度矩阵，其对角元素（dn W）是W的顶点度。第1页③计算对称归一化拉普拉斯算子：1 1当量（十）11：更新个体最佳和全局最佳：pbesti=xi，fbesti=f（xi），gbest=xmin，（xmin对应于fmin，且fmin=min{f（xi）}十二：端十三日：返回所有单个最佳值及其函数值采用改进的局部MPPSO算法进行局部搜索，其参数设置为：w/40：7，c1/2 ， c2/40 ： 7 ， v j;max1/40 ： 5xj;max-xj;min1/4 ， v j;min1/4-0 ： 5xj;max-xj;min1/4，并且注意，C2取小于2的0.7的值，减少了全局搜索的比例，使该算法适合于局部搜索。经过五次迭代，结果如图所示。9.第九条。上述局部MPPSO算法也将用于每个聚类内部的搜索，这将在步骤5中显示。此外，对于簇外的全局搜索，将在步骤6中使用新的改进的GA。比较图9和图8，局部搜索的执行使得每个点更接近其附近的最优值，并且LaplaceωSpD-2AD22014年计算矩阵Laplaceω<$Sp<$的特征值ki，并按降序排序，即k1Pk2Pk3P：Pkn计算相邻特征值的差：g1，g2，.. . ，gi，.. . ，gn-1，其中gn=ki-ki1。g1，g2，.. . ，g i，. 和gn-1可能是复数，删除它们，只保留实数。值得注意的是，删除所有复数是关键操作，否则这种谱聚类分析方法将无法实现对聚类数的准确甚至正确的估计。这种删除操作是本文的一个新发现，正如在前面的引言部分所提到的。找出具有最大值的元素（即maxfgig），定位该元素的位置，其索引号i取为聚类数，用c0表示。根据上述步骤，获得如图10所示的gi曲线，其中估计的聚类数为17。此外，可以使用任何聚类算法来对点进行聚类本文采用K-Means聚类算法，得到的聚类结果如图11所示，可以看出聚类效果良好。这一成功的结果归因于点的深度分离和聚类数的准确估计。(5) 步骤5，簇内点填充，水平集运算和启发式局部搜索：新一轮的点填充开始于根据以下步骤将新点的一部分填充到这些簇中：①根据聚类的不同，最小函数值：fmin，fmin，..fmin，.. . ，fmin的簇，1 2i c0图9.第九条。运行改进的局部MPPSO的结果较小的最小函数值将被赋予较大的权重。具体操作如下。首先，根据以下内容对所有聚类进行升序排序：它们的f_min值，即从最佳聚类到最差聚类的顺序排序后的新序列是：簇1，簇2，.. . ，群集i，.. . ，簇C0。Q. Zhao和C. 李沙特国王大学学报8267ð Þ¼ð- ÞΣΣðÞwclusterc0我i;jmax x elitegx offsetjn如果r> 1/40：5<见图10。 相邻特征值差。见图11。 聚类结果。其次，定义基于阶的权重函数作为其中a是（0，1）中的数。所得重量如图12所示。聚类i的填充点的数量被确定为：mcluste rim0·roun d. wclusteri15其中m0是单个簇的最小渗透点数轮图十三. 每个群集的边界。③将点填充到每个聚类i每个聚类的矩形边界如图13所示被标记。簇内点填充如图14所示。在上述填充之后，分别在每个簇内进行水平集运算和进一步的局部搜索，结果如图15所示。水平设置操作和局部搜索操作都类似于前面的操作，这里进一步执行MPPSO的局部版本（如步骤3所示），与步骤3的不同之处在于这里的这些操作分别在每个簇内。水平集运算的一个效果是减少了每个聚类的点数，避免了总点数的快速增加而耗费太多的计算时间。水平集操作也提高了平均解的精度，以找到局部最优解。局部搜索操作进一步加速收敛到局部最优。(6) 第六步，簇外点填充，水平集操作和启发式全局搜索：对所有簇进行排序，选择一定比例的精英簇，在每个簇的外部和周围填充一些随机点：8minfxeliteg-xoffset;如果r1