Extensions to Guided Local Search

In this thesis, we show how an Extended Guided Local Search can be applied to a set of problems and show that the extensions can improve its performance. We show how an aspiration criterion can be added to Guided Local Search to improve its performance for some problem types and parameter settings. We then demonstrate how, by making an occasional random move, the performance of Guided Local Search can be further improved for some problems and parameter settings. For both extensions, we make use of search monitors to attempt to analyse when and why each extension succeeds or fails. Finally, we combine the extensions and compare the resulting Extended Guided Local Search with some state-of-the-art algorithms for the different problem types, we have used for our experiments