R. Martí and M. Laguna
Revista Iberoamericana de Inteligencia Artificial, vol. 2, no. 4, pp. 123-130 (2003)
Scatter search is an evolutionary method that has been successfully applied to hard optimization problems. The fundamental concepts and principles of the method were first proposed in the 1970s and were based on formulations, dating back to the 1960s, for combining decision rules and problem constraints. The combination strategy was devised with the belief that information could be exploited more effectively when integrated than when treated in isolation. In contrast to other evolutionary methods like genetic algorithms, scatter search is mostly based on systematic designs and methods with the purpose of creating new solutions. It uses strategies for search diversification and intensification that have proved effective in a variety of optimization problems. The Scatter Search framework is flexible, allowing the development of alternative implementations with varying degrees of sophistication. This paper's goal is to provide a grounding in the essential ideas of Scatter Search that will enable readers to create successful applications of their own. The paper also introduces an application of the method to solve the well-known knapsack problem, in order to illustrate some implementation details.
Scatter Search es un método metaheurístico para resolver problemas de optimización. Aunque fue originalmente introducido en los años setenta, recientemente es cuando ha sido probado en numerosos problemas difíciles con gran éxito. Pertenece a la familia de los llamados Algoritmos Evolutivos, los cuales se distinguen por estar basados en la combinación de un conjunto de soluciones. Aunque presenta similitudes con los Algoritmos Genéticos, difiere de éstos en principios fundamentales, tales como el uso de estrategias sistemáticas en lugar de aleatorias. Scatter Search proporciona un marco flexible que permite el desarrollo de diferentes implementaciones con distintos grados de complejidad. En este trabajo se realiza una revisión del método desde sus orígenes hasta los aspectos más novedosos, que dan lugar a algoritmos más eficientes. Además, se ilustra la aplicación del método en la resolución del conocido problema de la mochila.
Full text (In Spanish)
