This thesis introduces analysis tools for improving the current state of the art of heuristics for the Maximum Clique (MC) problem. The analysis focusses on algorithmic building blocks, on their contribution in solving hard instances of the MC problem, and on the development of new tools for the visualisation of search landscapes. As a result of the analysis on the algorithmic building blocks, we re-engineer an existing Reactive Local Search heuristic for the Maximum Clique (RLS-MC. We propose implementation and algorithmic improvements over the original RLS-MC aimed at faster restarts and greater diversification. The newly designed algorithm (RLS-LTM) is one order of magnitude faster than the original RLS-MC on some benchmark instances; but the proposed algorithmic changes impact also on the dynamically adjusted tabu tenure, which grows wildly on some hard instances. A more in depth analysis of the search dynamics of RLS-MC and RLS-LTM reveals the reasons behind the tabu tenure explosion and sheds some new light on the reactive mechanism. We design and implement RLS-fast which cures the issues with the tabu tenure explosion in RLS-LTM while retaining the performance improvement over RLS-MC. Moreover, building on the knowledge gained from the analysis, we propose a new hyper-heuristic which defines the new state of the art, and a novel supervised clustering technique based on a clique-finding component.

Analysis of Reactive Search Optimisation Techniques for the Maximum Clique Problem and Applications / Mascia, Franco. - (2010), pp. 1-215.

Analysis of Reactive Search Optimisation Techniques for the Maximum Clique Problem and Applications

Mascia, Franco
2010-01-01

Abstract

This thesis introduces analysis tools for improving the current state of the art of heuristics for the Maximum Clique (MC) problem. The analysis focusses on algorithmic building blocks, on their contribution in solving hard instances of the MC problem, and on the development of new tools for the visualisation of search landscapes. As a result of the analysis on the algorithmic building blocks, we re-engineer an existing Reactive Local Search heuristic for the Maximum Clique (RLS-MC. We propose implementation and algorithmic improvements over the original RLS-MC aimed at faster restarts and greater diversification. The newly designed algorithm (RLS-LTM) is one order of magnitude faster than the original RLS-MC on some benchmark instances; but the proposed algorithmic changes impact also on the dynamically adjusted tabu tenure, which grows wildly on some hard instances. A more in depth analysis of the search dynamics of RLS-MC and RLS-LTM reveals the reasons behind the tabu tenure explosion and sheds some new light on the reactive mechanism. We design and implement RLS-fast which cures the issues with the tabu tenure explosion in RLS-LTM while retaining the performance improvement over RLS-MC. Moreover, building on the knowledge gained from the analysis, we propose a new hyper-heuristic which defines the new state of the art, and a novel supervised clustering technique based on a clique-finding component.
2010
XXIII
2009-2010
Ingegneria e Scienza dell'Informaz (cess.4/11/12)
Information and Communication Technology
Brunato, Mauro
no
Inglese
Settore INF/01 - Informatica
File in questo prodotto:
File Dimensione Formato  
thesis.pdf

accesso aperto

Tipologia: Tesi di dottorato (Doctoral Thesis)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 7.13 MB
Formato Adobe PDF
7.13 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/367833
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact