La búsqueda de 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 inteligencia de enjambre y algoritmos de búsqueda y optimización de inspiración natural que incluye optimización de colonias de hormigas, optimización de enjambres de partículas y algoritmos genéticos ; como tal, SDS fue la primera metaheurística de Swarm Intelligence . 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 baratas de una hipótesis (una solución candidata al problema de búsqueda). Luego comparten información sobre 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 comprende más fácilmente por medio de una simple analogía: The Restaurant Game.
Un grupo de delegados asiste a una larga conferencia en un pueblo desconocido. Cada noche, 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 máximo número de delegados disfruten de cenar. Incluso una búsqueda exhaustiva paralela a través del restaurante y las combinaciones de 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 agente manteniendo una hipótesis identificando el mejor restaurante de la ciudad. Cada noche, cada delegado prueba su hipótesis cenando allí y seleccionando al azar una de las comidas que se ofrecen. A la mañana siguiente, en el desayuno, cada delegado que no disfrutó de su comida la noche anterior, le pide a un colega seleccionado al azar que comparta sus impresiones sobre la cena. Si la experiencia fue buena, también adopta este restaurante como su elección. De lo contrario, simplemente selecciona otro restaurante al azar de los que aparecen en las "Páginas amarillas". Usando esta estrategia se encuentra que muy rápidamente un número significativo de delegados se congrega alrededor del '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 . redes [Whitaker, 2002].
A diferencia de muchas técnicas de búsqueda inspiradas en la naturaleza, existe un marco matemático completo que describe el comportamiento de SDS. El análisis de SDS ha investigado su optimización global y convergencia [Nasuto, 1998], complejidad de tiempo lineal [Nasuto et al., 1999], robustez [Myatt, 2004] y asignación de recursos [Nasuto, 1999] bajo una variedad de condiciones de búsqueda.