Tabu searching for robust solutions
Faculty of Applied Economics
Antwerp :UA, 2002
Research paper / UA, Faculty of Applied Economics UFSIA-RUCA ; 2002:027
University of Antwerp
In this paper, we investigate how tabu search techniques can be adapted so that they ¯nd 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 di®erent types of robustness. We show that tabu search and other local search techniques can be e®ectively used to ¯nd 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 ¯rst 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 °exible 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 ¯nite domain. For this type of problems, we ¯nd an approximation of the number of perturbed evaluations that are needed to create a good robust evaluation function.