Finding Robust Solutions Using Local Search Export

@article{Soe04, abstract = {Abstract\ \ This paper investigates how a local search metaheuristic for continuous optimisation can be adapted so that it finds broad peaks, corresponding to robust solutions. This is relevant in problems in which uncertain or noisy data is present. When using a genetic or evolutionary algorithm, it is standard practice to perturb solutions once before evaluating them, using noise from a given distribution. This approach however, is not valid when using population-less techniques like local search and other heuristics that use local search. For those algorithms to find robust solutions, each solution needs to be perturbed and evaluated several times, and these evaluations need to be combined into a measure of robustness. In this paper, we examine how many of these evaluations are needed to reliably find a robust solution. We also examine the effect of the parameters of the noise distribution. Using a simple tabu search procedure, the proposed approach is tested on several functions found in the literature.}, author = {S\"{o}rensen, Kenneth}, citeulike-article-id = {2666083}, citeulike-linkout-0 = {http://dx.doi.org/10.1023/B:JMMA.0000026710.74315.3e}, day = {27}, doi = {10.1023/B:JMMA.0000026710.74315.3e}, journal = {Journal of Mathematical Modelling and Algorithms}, keywords = {besorgen, ea, robustness, worst-case}, month = {March}, number = {1}, pages = {89--103}, posted-at = {2008-04-14 09:31:58}, priority = {2}, title = {Finding Robust Solutions Using Local Search}, url = {http://dx.doi.org/10.1023/B:JMMA.0000026710.74315.3e}, volume = {3}, year = {2004} }

TY - JOUR ID - Soe04 L3 - citeulike-article-id:2666083 N2 - Abstract  This paper investigates how a local search metaheuristic for continuous optimisation can be adapted so that it finds broad peaks, corresponding to robust solutions. This is relevant in problems in which uncertain or noisy data is present. When using a genetic or evolutionary algorithm, it is standard practice to perturb solutions once before evaluating them, using noise from a given distribution. This approach however, is not valid when using population-less techniques like local search and other heuristics that use local search. For those algorithms to find robust solutions, each solution needs to be perturbed and evaluated several times, and these evaluations need to be combined into a measure of robustness. In this paper, we examine how many of these evaluations are needed to reliably find a robust solution. We also examine the effect of the parameters of the noise distribution. Using a simple tabu search procedure, the proposed approach is tested on several functions found in the literature. IS - 1 JF - Journal of Mathematical Modelling and Algorithms EP - 103 TI - Finding Robust Solutions Using Local Search VL - 3 SP - 89 KW - besorgen KW - ea KW - robustness KW - worst-case AU - Sörensen, Kenneth PY - 2004/03/27/ UR - http://dx.doi.org/10.1023/B:JMMA.0000026710.74315.3e ER -