Reactive search: machine learning for memory-based heuristics

Most state-of-the-art heuristics are characterized by a certain number of choices and free parameters, whose appropriate setting is a subject that raises issues of research methodology. In some cases, these parameters are tuned through a feedback loop that includes the user as a crucial learning component: depending on preliminary algorithm tests some parameter values are changed by the user, and different options are tested until acceptable results are obtained. Therefore, the quality of results is not automatically transferred to different instances and the feedback loop can require a lengthy \trial and error" process every time the algorithm has to be tuned for a new application. Parameter tuning is therefore a crucial issue both in the scientific development and in the practical use of heuristics. In some cases the role of the user as an intelligent (learning) part makes the reproducibility of heuristic results difficult and, as a consequence, the competitiveness of alternative techniques depends in a crucial way on the user's capabilities. Reactive Search advocates the use of simple sub-symbolic machine learning to automate the parameter tuning process and make it an integral (and fully documented) part of the algorithm. If learning is performed on line, task-dependent and local properties of the configuration space can be used by the algorithm to determine the appropriate balance between diversification (looking for better solutions in other zones of the configuration space) and intensification (exploring more intensively a small but promising part of the configuration space). In this way a single algorithm maintains the exibility to deal with related problems through an internal feedback loop that considers the previous history of the search. In the following, we shall call reaction the act of modifying some algorithm parameters in response to the search algorithm's behavior during its execution, rather than between runs. Therefore, a reactive heuristic is a technique with the ability of tuning some important parameters during execution by means of a machine learning mechanism. It is important to notice that such heuristics are intrinsically history-dependent; thus, the practical success of this approach in some cases raises the need of a sounder theoretical foundation of non-Markovian search techniques.