Búsqueda de difusión estocástica

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 poblaciones . ^{[ 1 ]} Pertenece a una familia de algoritmos de búsqueda y optimización inspirados en la inteligencia de enjambre y la naturaleza que incluye la optimización de colonias de hormigas , la optimización de enjambres 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 posible solución al problema de búsqueda). Posteriormente, comparten información sobre las hipótesis ( difusión de información) mediante comunicación directa uno a uno. Gracias a este mecanismo de difusión, se pueden identificar soluciones de alta calidad entre grupos de agentes con la misma hipótesis. El funcionamiento de SDS se comprende mejor mediante una analogía sencilla : 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 con una amplia selección de platos. El problema consiste en encontrar el mejor restaurante, es decir, aquel donde el mayor número posible de delegados disfrute de la comida. Incluso una búsqueda exhaustiva paralela entre las combinaciones de restaurantes y platos resultaría demasiado larga. 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 para identificar el mejor restaurante de la ciudad. Cada noche, cada delegado pone a prueba su hipótesis cenando allí y eligiendo al azar uno de los platos que se ofrecen. A la mañana siguiente, durante el desayuno, todo delegado que no haya disfrutado de su cena la noche anterior, le pide a un colega elegido al azar que comparta sus impresiones. Si la experiencia fue buena, también elige ese restaurante. De lo contrario, simplemente selecciona otro restaurante al azar de entre los que aparecen en las Páginas Amarillas. Mediante esta estrategia, se observa que un número significativo de delegados se congrega rápidamente 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 inspiradas en la naturaleza, existe un marco matemático integral que describe el comportamiento de SDS. El análisis de SDS ha investigado su optimalidad global y convergencia [Nasuto, 1998], complejidad temporal lineal [Nasuto et al., 1999], robustez [Myatt, 2004] y asignación de recursos [Nasuto, 1999] bajo diversas condiciones de búsqueda.

• Bishop, JM (1989). "Redes de búsqueda estocástica" . 1989 Primera Conferencia Internacional IEE sobre Redes Neuronales Artificiales, (Publicación de la conferencia n.° 313) . Londres. págs. 329–331 . {{cite book}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )
• Bishop, JM y Torr, P., (1992). La red de búsqueda estocástica . En R. Linggard, DJ Myers, C. Nightingale (eds.), Redes neuronales para imágenes, habla y lenguaje natural, pp. 370-387, Nueva York, Chapman & Hall.
• Beattie, PD y Bishop, JM, (1998). Autolocalización en la silla de ruedas autónoma 'Senario' . Journal of Intelligent and Robotic Systems 22, pp 255–267, Kluwer Academic Publishers.
• Grech-Cini, HJ y McKee, GT (1993) Localización de la región de la boca en imágenes de rostros humanos . En PSSchenker (Ed.), Actas de SPIE – La Sociedad Internacional de Ingeniería Óptica, Sensor Fusion VI 2059, Massachusetts.
• Myatt, DR, Bishop JM y Nasuto, SJ, (2004). Criterios mínimos de convergencia estable para la búsqueda de difusión estocástica. Se publicará en Electronics Letters.
• Nasuto, SJ, (1999). Análisis de la asignación de recursos en la búsqueda de difusión estocástica. Tesis doctoral. Universidad de Reading, Reino Unido.
• Nasuto, SJ y Bishop, JM, (1999). Análisis de convergencia de la búsqueda de difusión estocástica. Journal of Parallel Algorithms and Applications 14:2, pp 89–107.
• Nasuto, SJ, Bishop, JM y Lauria, L., (1998). Complejidad temporal de la búsqueda de difusión estocástica. Neural Computation '98, Viena, Austria.
• Whitaker, RM, Hurley, S., (2002). Un enfoque basado en agentes para la selección de sitios para redes inalámbricas. Actas del Simposio ACM sobre Computación Aplicada (Madrid). 574 – 577.
• Jones, D. (2002). Búsqueda de difusión estocástica restringida . SCARP 2002, Universidad de Reading, Reino Unido.