Reactive local search for the maximum clique problem
Reactive local search for the maximum clique problem
复制标题
DOI：
10.1007/s004530010074
复制
发表时间：
2001-04-01
期刊：
影响因子：
1.1
通讯作者：
Protasi, M
中科院分区：
文献类型：
--
作者：
Battiti, R;Protasi, M
提出了一种新的反应性局部搜索（RLS）算法，以解决最大问题问题的解决方案。 RLS基于本地搜索，以反馈（历史敏感）方案进行补充，以确定多元化的量。该反应作用于单个参数，该参数以受Babu搜索的启发的方式决定了邻居中选定的移动的暂时禁止。相对于在第二次DIMAC实施挑战中测试的所有算法，计算测试中获得的性能似乎要好得多。根据算法的迭代，最坏情况的复杂性是O（max {n，m}），其中n和m是图形的节点和边缘的数量。实际上，当移动顶点时，操作的数量往往与其缺失边缘数量成正比，因此迭代在密集的图中特别快。
A new Reactive Local Search (RLS) algorithm is proposed for the solution of the Maximum-Clique problem. RLS is based on local search complemented by a feedback (history-sensitive) scheme to determine the amount of diversification. The reaction acts on the single parameter that decides the temporary prohibition of selected moves in the neighborhood, in a manner inspired by Tabu Search. The performance obtained in computational tests appears to be significantly better with respect to all algorithms tested at the the second DIMACS implementation challenge. The worst-case complexity per iteration of the algorithm is O (max{n, m}) where n and m are the number of nodes and edges of the graph. In practice, when a vertex is moved, the number of operations tends to be proportional to its number of missing edges and therefore the iterations are particularly fast in dense graphs.