Data science in optimisation: an example

21^st June 2016, 13:00 Ashton Lecture Theater
Prof. Patrick De Causmaecker
KU Leuven
Faculty of Science, Campus Kulak Kortrijk
Etienne Sabbelaan 53 - box 7659
8500 Kortrijk

Abstract

Data analysis is increasingly used to support the development of algorithms. Many approaches are black box: in parameter tuning, the algorithm is exposed to a (large) number of instances in order to find the best parameter setting, in algorithm selection instance features are discovered to learn predictors of algorithm behaviour. White box approaches allow to study algorithm internals and potentially can be used as support tools for creative algorithm developers. We present an example of the latter:

Characterization of neighborhood behaviours in a multi-neighborhood local search algorithm

A multi-neighborhood local search algorithm with a large number of possible neighborhoods is investigated. Each neighborhood is chosen at each iteration with a set probability. These probabilities are fixed for the algorithm run.
We propose a systematic method to characterize each neighborhood's behaviors, representing them as a feature vector, and using cluster analysis
to form similar groups of neighborhoods. The novelty of our characterization method is that it reflects changes of behaviours according to hardness of different solution quality regions. We show that using neighborhood clusters instead of individual neighborhoods helps to reduce the parameter
configuration space without misleading the search of the tuning procedure.
The method is problem-independent and can be applied in similar contexts.