基于增强型kick策略的ILS算法求解一类聚类问题

New Iterated Local Search with Reinforced Kick Strategy for Clustering Problems

提出一种新型的基于环交换邻域的迭代局部搜索算法(ILS),用于求解一类聚类问题.算法的主要特点是:1)基于环交换的邻域结构:环交换邻域与传统的Sw ap和Insert邻域相比,算法在一次迭代中允许多个点同时移动;2)针对聚类问题提出了增强型的k ick移动策略:根据每组内点的密度分布摄动聚类中心,对给定的解重新聚类.实验结果表明,基于环交换的迭代局部搜索算法对求解该类聚类问题是有效的.

A new iterated local search （ILS） algorithm with cylce exchange neighborhood is developed to solve a class of clustering problems. The main characteristics of the algorithm are as follows： 1）Cycle exchange neighborhood is used where several points are allowed to move simultaneously in an iteration, which is different from traditional neighborboods such as swap and insert where only at most two points are permitted to move simultaneously in each iteration; 2） a new ＂reinforced kick＂ is proposed for the clustering problem, in which for a given solution, the center point of each cluster is updated according to the point distribution in the cluster, and the remained points are regrouped based on these centers. Computational experiments show the efficiency of the new ILS algorithm with cycle exchange.