Home > Research > Publications & Outputs > Experiments to shed light on the best way to us...

Electronic data

View graph of relations

Experiments to shed light on the best way to use Iterated Local Search for a complex combinatorial problem

Research output: Working paper

Publication date2007
Place of PublicationLancaster University
PublisherThe Department of Management Science
<mark>Original language</mark>English

Publication series

NameManagement Science Working Paper Series


Iterated Local Search (ILS) is a popular metaheuristic search technique for use on combinatorial optimisation problems. As with most such techniques, there are many ways in which ILS can be implemented. The aim of this paper is to shed light on the best variants and choice of parameters when using ILS on a complex combinatorial problem with many objectives, by reporting on the results of an exhaustive set of experimental computer runs using ILS for a real-life sports scheduling problem. The results confirm the prevailing orthodoxy that a random element is ended for the ILS "kick", but also concludes that a non-random element can be valuable if it is chosen intelligently. Under these circumstances it is also found that the best ILS acceptance criterion to choose appears to depend upon the length of the run; for short runs, a high-diversification approach works best; for very long runs a high-intensification approach is best; while between these extremes, a more sophisticated approach using simulated annealing or threshold methods appears to be best.