Optimizing the efficiency of parameterized local search within global search: a preliminary study

Application-specific, parameterized local search algorithms (PLSAs), in which optimization accuracy can be traded-off with run-time, arise naturally in many optimization contexts. We introduce a novel approach, called simulated heating, for systematically integrating parameterized local search into global search algorithms (GSAs) in general and evolutionary algorithms in particular. Using the framework of simulated heating, we investigate both static and dynamic strategies for systematically managing the trade-off between PLSA accuracy and optimization effort. We show quantitatively that careful management of this trade-off is necessary to achieve the full potential of a GSA/PLSA combination. Furthermore, we provide preliminary results which demonstrate the effectiveness of our simulated heating techniques in the context of code optimization for embedded software implementation, a practical problem that involves vast and complex search spaces