Clique Finder: A Self-Adaptive Simulated Annealing Algorithm for the Maximum Clique Problem

被引：3

作者：

Almuhaideb, Sarab ^{[1
]}

Altwaijry, Najwa ^{[1
]}

AlMansour, Shahad ^{[1
]}

AlMklafi, Ashwaq ^{[1
]}

AlMojel, AlBandery Khalid ^{[1
]}

AlQahtani, Bushra ^{[1
]}

AlHarran, Moshail ^{[1
]}

机构：

[1] King Saud Univ, Dept Comp Sci, Coll Comp & Informat Sci, Riyadh, Saudi Arabia

来源：

INTERNATIONAL JOURNAL OF APPLIED METAHEURISTIC COMPUTING | 2022年 / 13卷 / 02期

关键词：

Cooling Schedule; DIMACS; Maximum Clique Problem; Metaheuristics; Nature-Inspired Methods; NP-Hard Problem; Self-Adaptive; Simulated Annealing; OPTIMIZATION;

D O I：

10.4018/IJAMC.20220401.oa1

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The maximum clique problem (MCP) is a classical NP-hard problem that has gained considerable attention due to its numerous real-world applications and theoretical complexity. It is inherently computationally complex, and so exact methods may require prohibitive computing time. Nature-inspired meta-heuristics have proven their utility in solving many NP-hard problems. In this research, the authors propose a simulated annealing-based algorithm that they call clique finder algorithm to solve the MCP. The algorithm uses a logarithmic cooling schedule and two moves that are selected in an adaptive manner. The objective (error) function is the total number of missing links in the clique, which is to be minimized. The proposed algorithm was evaluated using benchmark graphs from the open-source library DIMACS, and results show that the proposed algorithm had a high success rate.

引用

页码：1 / 22

页数：22

共 33 条

[1]

Afkhami S., 2013, International Journal of Computers and Applications, V69

[2]

Al-Taani A., 2012, INT C COMP NETW DIG, P142

[3]

[Anonymous], 2009, Metaheuristics: From Design to Implementation

[4]

Bomze IM, 2000, NONCON OPTIM ITS APP, V42, P78