Cooperating local search for the maximum clique problem

There are no files associated with this record.

Title Cooperating local search for the maximum clique problem
Author Pullan, Wayne John; Mascia, Franco; Brunato, Mauro
Journal Name Journal of Heuristics
Year Published 2011
Place of publication United States
Publisher Springer New York LLC
Abstract The advent of desktop multi-core computers has dramatically improved the usability of parallel algorithms which, in the past, have required specialised hardware. This paper introduces cooperating local search (CLS), a parallelised hyper-heuristic for the maximum clique problem. CLS utilises cooperating low level heuristics which alternate between sequences of iterative improvement, during which suitable vertices are added to the current clique, and plateau search, where vertices of the current clique are swapped with vertices not in the current clique. These low level heuristics differ primarily in their vertex selection techniques and their approach to dealing with plateaus. To improve the performance of CLS, guidance information is passed between low level heuristics directing them to particular areas of the search domain. In addition, CLS dynamically reconfigures the allocation of low level heuristics to cores, based on information obtained during a trial, to ensure that the mix of low level heuristics is appropriate for the instance being optimised. CLS has no problem instance dependent parameters, improves the state-of-the-art performance for the maximum clique problem over all the BHOSLIB benchmark instances and attains unprecedented consistency over the state-of-the-art on the DIMACS benchmark instances.
Peer Reviewed Yes
Published Yes
Alternative URI
Volume 17
Issue Number 2
Page from 181
Page to 199
ISSN 1381-1231
Date Accessioned 2011-01-27
Language en_US
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Artificial Intelligence and Image Processing
Publication Type Journal Articles (Refereed Article)
Publication Type Code c1

Show simple item record

Griffith University copyright notice