Iterated k-opt local search for the maximum clique problem

被引：0

作者：

Katayama, Kengo ^{[1
]}

Sadamatsu, Masashi ^{[1
]}

Narihisa, Hiroyuki ^{[1
]}

机构：

[1] Okayama Univ Sci, Informat & Comp Engn, 1-1 Ridai Cho, Okayama 7000005, Japan

来源：

EVOLUTIONARY COMPUTATION IN COMBINATORIAL OPTIMIZATION, PROCEEDINGS | 2007年 / 4446卷

关键词：

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper presents a simple iterated local search metaheuristic incorporating a k-opt local search (KLS), called Iterated KLS (IKLS for short), for solving the maximum clique problem (MCP). IKLS consists of three components: LOCALSEARCH at which KLS is used, a KICK called LEC-Kick that escapes from local optima, and RESTART that occasionally diversifies the search by moving to other points in the search space. IKLS is evaluated on DIMACS benchmark graphs. The results showed that IKLS is an effective algorithm for the MCP through comparisons with multi-start KLS and state-of-the-art metaheuristics.

引用

页码：84 / +

页数：3

共 23 条

[1]

[Anonymous], 1999, HDB COMBINATORIAL OP

[2] Chained Lin-Kernighan for large traveling salesman problems [J].

Applegate, D ;

Cook, W ;

Rohe, A .

INFORMS JOURNAL ON COMPUTING, 2003, 15 (01) :82-92

[3] Reactive local search for the maximum clique problem [J].

Battiti, R ;

Protasi, M .

ALGORITHMICA, 2001, 29 (04) :610-637

[4]

Garey MR, 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[5] Variable neighborhood search for the maximum clique [J].

Hansen, P ;

Mladenovic, N ;

Urosevic, D .

DISCRETE APPLIED MATHEMATICS, 2004, 145 (01) :117-125

[6] Clique is hard to approximate within n1-ε [J].

Håstad, J .

ACTA MATHEMATICA, 1999, 182 (01) :105-142

[7]

Johnson DS., 1997, Local search in combinatorial optimization, P215, DOI DOI 10.1108/01445150910987763

[8]

JOHNSON DS, 1996, DIMACS SERIES DISCRE

[9] An effective local search for the maximum clique problem [J].

Katayama, K ;

Hamamoto, A ;

Narihisa, H .

INFORMATION PROCESSING LETTERS, 2005, 95 (05) :503-511

[10]

Katayama K, 1999, GECCO-99: PROCEEDINGS OF THE GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, P321

← 1 2 3 →