Improving Simulated Annealing for Clique Partitioning Problems
Improving Simulated Annealing for Clique Partitioning Problems
复制标题
DOI：
10.1613/jair.1.13382
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Jian Gao;Yiqi Lv;Minghao Liu;Shaowei Cai;Feifei Ma
中科院分区：
文献类型：
--
作者：
Jian Gao;Yiqi Lv;Minghao Liu;Shaowei Cai;Feifei Ma
团划分问题（CPP）是图论中的一个重要问题，有许多重要的应用。由于其NP困难性，有效的算法来解决这个问题是非常重要的实际目的，和模拟退火被证明是有效的，在国家的最先进的CPP算法。然而，为了使模拟退火更有效地解决大规模的CPPs，在本文中，我们提出了一个新的迭代模拟退火算法。在我们的算法中提出了几种方法来改善模拟退火。首先，提出了一种新的基于时间戳的配置检查策略，并将其与模拟退火算法相结合，避免了搜索周期。然后，为了增强模拟退火算法的局部搜索能力，加快收敛速度，我们将联合收割机与下降搜索法相结合来求解CPP。该方法进一步改进了模拟退火算法的解，从而弥补了局部搜索的影响。为了进一步加快收敛速度，我们引入了一个收缩因子来降低初始温度，并提出了一种基于模拟退火的迭代局部搜索算法。此外，当搜索过程收敛时，采用重新启动策略。对CPP的基准实例进行了大量的实验，结果表明，所提出的模拟退火算法优于所有现有的启发式算法，包括五个国家的最先进的算法。因此，更新了94个实例中34个实例的最佳已知解决方案。我们还对所提出的策略进行了比较分析，并显示了它们的有效性。
The Clique Partitioning Problem (CPP) is essential in graph theory with a number of important applications. Due to its NP-hardness, efficient algorithms for solving this problem are very crucial for practical purposes, and simulated annealing is proved to be effective in state-of-the-art CPP algorithms. However, to make simulated annealing more efficient to solve large-scale CPPs, in this paper, we propose a new iterated simulated annealing algorithm. Several methods are proposed in our algorithm to improve simulated annealing. First, a new configuration checking strategy based on timestamp is presented and incorporated into simulated annealing to avoid search cycles. Afterwards, to enhance the local search ability of simulated annealing and speed up convergence, we combine our simulated annealing with a descent search method to solve the CPP. This method further improves solutions found by simulated annealing, and thus compensates for the local search effect. To further accelerate the convergence speed, we introduce a shrinking factor to decline initial temperature and then propose an iterated local search algorithm based on simulated annealing. Additionally, a restart strategy is adopted when the search procedure converges. Extensive experiments on benchmark instances of the CPP were carried out, and the results suggest that the proposed simulated annealing algorithm outperforms all the existing heuristic algorithms, including five state-of-the-art algorithms. Thus the best-known solutions for 34 instances out of 94 are updated. We also conduct comparative analyses of the proposed strategies and show their effectiveness.