Tabu searching for robust solutions. Theoretical framework

In this paper, we investigate how tabu search techniques can be adapted so that they find solutions that (1) have a good solution quality and (2) are more robust than other solutions. We show that there is a need for robust solutions in many practical problems and discuss different types of robustness. We show that tabu search and other local search techniques can be effectively used to find solutions that are both robust and of high quality. The concept of robust evaluation function is introduced. In a robust evaluation function, a number of solutions are first perturbed and then combined into a single measure of both robustness and solution quality. We show that this concept extends tabu search so that it searches for robust solutions without requiring large modi¯cations to the tabu search algorithm itself, thus rendering the technique very flexible and practically useable. The proposed procedure is tested for a simple tabu search procedure, the optimisation of a continuous function of a single variable on a finite domain. For this type of problems, we find an approximation of the number of perturbed evaluations that are needed to create a good robust evaluation function.