论文标题：Improving local search algorithms for clique relaxation problems via group driven initialization

期刊：Frontiers of Computer Science

作者：Rui SUN, Yiyuan WANG, Minghao YIN

发表时间：02 Jun 2024

DOI： 10.1007/s11704-024-40238-8

微信链接：点击此处阅读微信文章

引用格式：

Rui SUN, Yiyuan WANG, Minghao YIN. Improving local search algorithms for clique relaxation problems via group driven initialization. Front. Comput. Sci., 2025, 19(6): 196403

阅读原文：

问题概述

最大松弛团问题是最大团问题的重要泛化问题，在现实世界中具有广泛的应用。尽管有许多研究都提出了高效的局部搜索算法来解决这些问题，但几乎所有针对该问题的局部搜索算法都采用了通用的初始化方法。通用初始化方法只利用顶点操作信息频率来指导初始化过程，忽略了其他重要搜索信息和结构信息。

为了改进松弛团局部搜索算法的初始化过程，本文提出了一种分组驱动的初始化方法。它包括一个基于分组的初始化方法，以及两个分组生成和维护过程。两者都在一定程度上考虑了搜索过程中的信息和给定测试用例的结构信息。

技术步骤

具体来说，该团队根据局部最优矩阵以及模块度，将顶点划分为不同分组。基于顶点的组信息，使用轮盘赌法获得初始解。所提出的组驱动初始化方法不影响搜索过程，因此任何使用通用松弛团局部搜索框架的算法都可以直接应用该方法。

实验结果

该团队将所提出的初始化方法应用于三个松弛团局部搜索算法，并进行了大量实验。结果表明，应用了分组驱动初始化算法之后，原有局部搜索算法的性能有了很大提升。

期刊简介

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办，南京大学支持，SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，双月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐B类期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；两次入选“中国科技期刊卓越行动计划”（一期梯队、二期领军）。

中国学术前沿期刊网

http://journal.hep.com.cn