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 enjambre de partículas y algoritmos genéticos ; como tal, SDS fue la primera metaheurística de Swarm Intelligence . A diferencia de la comunicación estigmergetica 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 hipótesis ( difusión de información) a través de 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 mejor mediante una simple analogía: el juego del restaurante.
Un grupo de delegados asiste a una larga conferencia en una ciudad desconocida. 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 disfrutarían de una cena. Incluso una búsqueda exhaustiva paralela entre 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 cuál es el mejor restaurante de la ciudad. Cada noche, cada delegado pone a prueba su hipótesis cenando allí y seleccionando al azar una de las comidas 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 adopta este restaurante como su elección. De lo contrario, simplemente selecciona otro restaurante al azar entre los que figuran en las "Páginas Amarillas". Utilizando esta estrategia se descubre que muy rápidamente un número significativo de delegados se congrega 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 comunicaciones inalámbricas . redes [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 SDS. El análisis de SDS ha investigado su optimización y convergencia global [Nasuto, 1998], complejidad temporal lineal [Nasuto et al., 1999], robustez [Myatt, 2004] y asignación de recursos [Nasuto, 1999] bajo una variedad de condiciones de búsqueda.