La búsqueda por difusión estocástica (SDS) se describió por primera vez en 1989 como un algoritmo de coincidencia de patrones basado en la población . [1] Pertenece a una familia de algoritmos de búsqueda y optimización de inspiración natural e inteligencia de enjambre que incluye la optimización de colonias de hormigas , la optimización de enjambre de partículas y los algoritmos genéticos ; como tal, SDS fue la primera metaheurística de inteligencia de enjambre . A diferencia de la comunicación estigmergética empleada en la optimización de colonias de hormigas , que se basa en la modificación de las propiedades físicas de un entorno simulado, SDS utiliza una forma de comunicación directa (uno a uno) entre los agentes similar al mecanismo de llamada en tándem empleado por una especie de hormigas, Leptothorax acervorum .
En SDS, los agentes realizan evaluaciones parciales y económicas de una hipótesis (una solución candidata al problema de búsqueda). Luego comparten información sobre las hipótesis ( difusión de información) a través de una comunicación directa uno a uno. Como resultado del mecanismo de difusión, se pueden identificar soluciones de alta calidad a partir de grupos de agentes con la misma hipótesis. El funcionamiento de SDS se entiende más fácilmente mediante una analogía simple: el juego del restaurante.
Un grupo de delegados asiste a una larga conferencia en una ciudad desconocida. Todas las noches, cada delegado debe encontrar un lugar para cenar. Hay una gran variedad de restaurantes, cada uno de los cuales ofrece una gran variedad de comidas. El problema al que se enfrenta el grupo es encontrar el mejor restaurante, es decir, el restaurante donde el mayor número de delegados disfrutaría de una cena. Incluso una búsqueda exhaustiva paralela a través de las combinaciones de restaurantes y comidas llevaría demasiado tiempo. Para resolver el problema, los delegados deciden emplear una búsqueda de difusión estocástica.
Cada delegado actúa como un agente que mantiene una hipótesis que identifica el mejor restaurante de la ciudad. Cada noche, cada delegado pone a prueba su hipótesis cenando allí y seleccionando al azar uno de los platos que se ofrecen. A la mañana siguiente, durante el desayuno, cada delegado que no disfrutó de su comida la noche anterior pide a un colega seleccionado al azar que comparta sus impresiones sobre la cena. Si la experiencia fue buena, también elige ese restaurante. De lo contrario, simplemente selecciona otro restaurante al azar de los que aparecen en las "Páginas Amarillas". Utilizando esta estrategia, se descubre que muy rápidamente un número significativo de delegados se reúnen en torno al "mejor" restaurante de la ciudad.
SDS se ha aplicado a diversos problemas, como la búsqueda de texto [Bishop, 1989], el reconocimiento de objetos [Bishop, 1992], el seguimiento de características [Grech-Cini, 1993], la autolocalización de robots móviles [Beattie, 1998] y la selección de sitios para redes inalámbricas [Whitaker, 2002].
A diferencia de muchas técnicas de búsqueda inspirada en la naturaleza, existe un marco matemático integral que describe el comportamiento de la búsqueda inspirada en la naturaleza. El análisis de la búsqueda inspirada en la naturaleza ha investigado su optimalidad y convergencia globales [Nasuto, 1998], complejidad temporal lineal [Nasuto et al., 1999], robustez [Myatt, 2004] y asignación de recursos [Nasuto, 1999] en una variedad de condiciones de búsqueda.