@inproceedings{KANAHARA-CISIS-2018,
title = {A restart diversification strategy for iterated local search to maximum clique problem},
author = {Kazuho Kanahara and Kengo Katayama and Takeshi Okano and Elis Kulla and Tetsuya Oda and Noritaka Nishihara},
doi = {https://doi.org/10.1007/978-3-319-93659-8_61},
year = {2018},
date = {2018-06-19},
booktitle = {CISIS 2018: Complex, Intelligent, and Software Intensive Systems, Proceedings of the 12th International Conference on Complex, Intelligent, and Software Intensive Systems, Advances in Intelligent Systems and Computing (AISC, volume 772)},
pages = {670–680},
abstract = {Iterated local search metaheuristic provides high quality solutions, in spite of a simple framework, for a large number of combinatorial optimization problems. However the search stagnation sometimes occur before finding a high quality solution for difficult problem instances particularly. One simple way to overcome such stagnation is to introduce a restart strategy into the framework that forcibly changes its search point. In this paper, we present a restart diversification strategy (RDS) for an iterated local search incorporating k-opt local search (KLS), called Iterated KLS (IKLS), for the maximum clique problem. For the RDS, we accumulate the information of solutions by KLS and it occasionally diversifies the main search of IKLS by moving to unexplored points based on the information. IKLS with the RDS is evaluated on DIMACS graphs. The experimental results showed that the RDS contributes to the improvement of the main search of IKLS for several difficult graphs.},
keywords = {Diversification, Iterated local search, Maximum clique problem},
pubstate = {published},
tppubtype = {inproceedings}
}
