Post que he decido publicar. He tardado en elaborarlo más de un mes en ratos libres. Es un tema que me apasiona y creo que tanto esto como la colaboración estigmérgica son importantes para desarrollar investigaciones en espacios virtuales de colaboración con sus interacciones o también podemos llamarlo Aprendizaje colaborativo en red (Networked Collaborative Learning). Espero que os gusten estos nuevos post descriptivos e introductorios. De pequño siempre observaba las hormigas mientras regaba las alubias y la remolacha.
Este término es adaptado del inglés «Swarm Intelligence» y se trata de un enjambre/grupo que se define como una población de elementos interactuantes que son capaces de optimizar un objetivo global a través de la búsqueda de colaboración de un espacio (Kennedy, 2001). Los elementos o agentes pueden ser máquinas muy simples o muy complejas. Existen dos restricciones que deben observarse: se suelen limitar a las interacciones locales, por lo general la interacción no se realiza directamente, sino indirectamente a través del entorno. Es lo que se llama la estigmergía. La propiedad básica que los hace enjambres es su comportamiento de autoorganización, es decir, es el hecho de que una gran cantidad de procesos simples pueden conducir a resultados complejos y que explica muy bien Len Fisher en su último libro «The perfect swarm: the science of complexity in everyday life»
El comportamiento de las hormigas es el ejemplo más conocido de la inteligencia de enjambre. En muchas especies de hormigas tienen un depósito de una sustancia química llamada feromona. Es un medio de señales cuyas principales ventajas son el gran alcance y el evitar obstáculos, puesto que son arrastradas por el aire. Por ello, las hormigas no se comunican directamente entre sí, pero siguen rastros de feromona (dejando a sus propias feromonas, por lo que la pista se ve reforzado). El camino que conecta la fuente de alimento y el nido está optimizado, y además, no tienen ningún tipo de conocimiento global del problema por cualquiera de los agentes. Este proceso de comunicación indirecta en un enjambre se llama estigmergía (en el siguiente post hablaré de su importancia para una colaboración natural en grupos) como comentamos arriba. La posibilidad de que un sistema se quede atascado localmente es una solución mucho mejor, pero no la óptima no se conoce el estancamiento (Bonabeau, 1999).
Elementos de la investigación
La inteligencia de enjambre es un creciente campo de investigación bastante activo y sus aplicaciones fuera de Internet son múltiples. Las técnicas de inteligencia de enjambre se han aplicado a muchos tipos diferentes de problemas. Los ejemplos van desde la muy general, el gráfico como colorante (Costa, 1995) o la satisfacción de restricciones (ver Zlochin de 2002, para una encuesta sobre este tema), a las aplicadas a problemas muy particulares como la asignación de tareas para los robots en una fábrica (Morley , 1996), la expedición de una flota de camiones (Gambardella, 1999), o incluso el diseño de un calendario conjunto de cursos universitarios (Socha, 2002). Hay un buen estudio de aplicaciones de robótica, junto con las explicaciones de los comportamientos diferentes de hormigas que los inspiraron (alimentación de los alimentos para el transporte colectivo o la construcción de nidos).
Aplicaciones a partir de agentes virtuales
La mayoría de las aplicaciones basadas en fenómenos de la inteligencia de enjambre se basan en grupos de agentes virtuales. Ellos muestran buenos resultados cuando se aplica a los problemas que se distribuyen espacialmente y cambian con el tiempo. Como muchos de los problemas de Internet se distribuyen y variables en el tiempo por la naturaleza, basado en la optimización de enjambre y técnicas de resolución de problemas se presenta con buenos resultados cuando se aplica a ellos.
Si nos centramos en aplicaciones orientadas a la red, la mayoría están relacionados con problemas de enrutamiento. Aunque ha habido mucha investigación sobre este tema (véase Steenstrup, 1995 para una buena encuesta), las técnicas de inteligencia de enjambre se adaptan especialmente a los grupos de los problemas a medida o que tienen unas ciertas similitudes unos de otros y que son inherentemente dinámicos y distribuidos.
En redes de paquetes como Internet, cada paquete puede seguir una ruta diferente hacia su destino. La función principal de una red de paquetes es asegurar la distribución eficiente de información entre sus usuarios. Hay tres cuestiones principales que deben tenerse en cuenta: el control de la congestión, la seguridad de la comunicación, y de enrutamiento. Ha habido muchos enfoques de enjambre basado en el problema de enrutamiento (ver Dorigo, 2004 para una encuesta). Nos centraremos aquí en el algoritmo AntNet en la forma que lo explica Dorigo (2004), ya que es un ejemplo representativo y muestra todas las características principales de los enfoques basados en enjambre (los agentes simples, la comunicación indirecta, y el comportamiento de enjambre de forma emergente). Se pueden encontrar más algoritmos de optimización en Bonabeau (1999) y Dorigo (2004).
El algoritmo AntNet
El algoritmo AntNet es distribuido y adaptativo, aplicando la distancia-vector al algoritmo de enrutamiento. Es un caso especial del algoritmo ACO sobre la base de hormigas artificiales y deposición de las feromonas. Los agentes de AntNet , al mismo tiempo, exploran la información en la red y el intercambio de la recogida. La comunicación entre los agentes es indirecta y asincrónica, mediada por la propia red (características para investigaciones en conceptos como estigmergía y autoorganización). En AntNet (Paper: AntNet: Distributed Stigmergetic Control for Communications Networks). En este artículo se presenta un enfoque diferente y cómo optimizar el aprendizaje de adaptación ante una situación o problema. Cada nodo mantiene dos tablas diferentes (aparte de la tabla de enrutamiento): una tabla de feromona, T, y una red de tráfico de modelo, M. Su construcción y el mecanismo de actualización se explica a continuación (Gutiérrez, 2007):
AntNet utiliza dos tipos de agentes artificiales en las hormigas: las hormigas adelantadas y las hormigas retrasadas. Las hormigas son independientes y no hay ni coordinación ni comunicación directa entre ellas. Las hormigas de adelante se generan en cada nodo, y se dirigen a otros nodos en relación con el tráfico generado del nodo: las hormigas de adelante se van hacia los nodos donde se está más de tráfico han enviado. Comparten las colas normales utilizados por los paquetes de datos, por lo que la experiencia de la misma carga de tráfico. Almacenan el camino para viajar hasta que llegan a su destino. Las hormigas con versiones anteriores se generan cuando una hormiga de adelante llega a su destino, y sigue el camino almacenados por la hormiga hacia adelante correspondiente. No todas las hormigas de adelante lleguen a su destino, como las hormigas que realizan un ciclo (visita un nodo ya visitado), que es más de la mitad de la edad de la hormiga que descartan. Las hormigas con versiones anteriores de uso de colas de alta prioridad en su camino de regreso.
Después de llegar a cada nodo, las hormigas seleccionan su próximo salto probabilístico de acuerdo con la matriz de feromonas (evitando, si es posible, los nodos que ya han visitado). Las feromonas de la matriz tienen un número de columnas igual al número de nodos en la red, y un número de filas igual al número de enlaces salientes (vecinos) del nodo. Todas las columnas suman uno y, para un determinado destino, que muestran la probabilidad (sin corregir) que una hormiga de adelante seguirá ese enlace. Esta probabilidad se corrige mediante una regla heurística que le da una mayor probabilidad a los vínculos con colas vacías de salida, así que el sistema es reactivo a las fluctuaciones de carga de la red. La misión de las hormigas a seguir es almacenar la ruta seguida a su destino y para registrar el tiempo necesario para llegar a todos los nodos a lo largo de ella.
La misión de las hormigas de atrás es la actualización de las feromonas y las matrices en el modelo de tráfico. El modelo de tráfico de la matriz tiene tres filas, y para todos los almacenes de destino posible de la media (μd) y el tiempo de la varianza (σd) para llegar allí, así como el mejor momento durante las iteraciones máximas del pasado. Cuando una hormiga de atrás llega a un nodo, el nodo de la matriz M se actualiza con los valores almacenados en la memoria de la hormiga (recogidos por la hormiga con interés correspondiente). La media de ambos se actualizan de forma que los valores más recientes tienen más peso que los antiguos. La actualización de la matriz T feromonas se realiza de una manera que depende de una medida de la bondad asociadas con el tiempo de viaje experimentado por la hormiga hacia adelante. El valor de feromonas que se corresponde con el nodo de destino y el enlace de salida de las hormigas que se incrementan (valores pequeños de feromonas se incrementan proporcionalmente más). Los demás valores se reducen en consecuencia (la evaporación de feromonas virtuales) para que la columna de resumen a uno.
Por último, los paquetes de datos en un escenario AntNet se envían probabilísticamente. Las tablas de rutas se calculan a partir de tablas de feromonas para elevar cada probabilidad a un factor, por lo tanto aumentan las probabilidades altas y dejan de lado las bajas.
AntNet se ha simulado y en comparación con otros algoritmos de estado es una técnica de ruta distribuida llamada Bellman-Ford.
Otros algoritmos.
Existen otros algoritmos de optimización en estadios de enjambre:
- Optimización de la colonia de la hormiga (Ant Colony Optimization)
- Optimización del enjambre de la partícula (Particle Swarm Optimization)
- Búsqueda estocástica de la difusión (Stochastic diffusion search)
- Gravitacional algoritmo de búsqueda (Gravitational search algorithm)
- Gotas de agua inteligentes (Intelligent Water Drops)
- Rio dinámico de formación (River formation dynamics)
Existen muchos más algoritmos que optimizan los procesos y acciones de emjambre (swarming).
Inteligencia de enjambre aplicada a grupos sociales
Hay varias aplicaciones que se basan en personas reales en lugar de agentes virtuales, pero sin embargo muestran características de los comportamientos de enjambre. Ejemplo de ello es cuando una gran cantidad de personas que interactúan sin ninguna comunicación directa entre ellos, la comunicación indirecta a través de algún tipo de entorno (de aprendizaje), y sus patrones emergentes, no se relacionan con comportamientos individuales.
Hay dos formas que se pueden analizar en grupos sociales desde esta perspectiva:
1) El filtrado colaborativo.
Se basa en la premisa de que las personas que buscan información debe ser capaz de hacer uso de lo que otros ya han encontrado y evaluado.
Los sistemas tradicionales de filtrado colaborativo (Dron, 1999) almacena las preferencias y las evaluaciones de los usuarios con respecto a varios elementos (de las novelas y canciones, a los recursos de aprendizaje en una clase). Esas preferencias permiten a otros usuarios a ver lo que sus compañeros preferidos, y utilizar esta información como guía para sus acciones.
En los últimos años, el crecimiento del comercio electrónico ha estimulado el uso de sistemas de filtrado de colaborar como los sistemas de recomendación. Por lo tanto, el objetivo de un sistema moderno de filtrado colaborativo puede enunciarse como la predicción de la utilidad de un determinado tema para un usuario particular, sobre la base de gustos anteriores del usuario y las opiniones de otros usuarios con gustos similares.
Modernos sistemas de filtrado colaborativo puede ser clasificados en dos tipos: basados en memoria y basados en su modelo. Los primeros en utilizar una base de datos de usuario-elemento para generar una predicción. Estos sistemas utilizan técnicas estadísticas para encontrar un conjunto de usuarios (vecinos) que tienen un perfil similar de acuerdo con el usuario de destino. Modelo basado en algoritmos de filtrado colaborativo proporcionan recomendaciones para un tema concreto, en primer lugar el desarrollo de un modelo de valoraciones. Algoritmos en esta categoría adoptan un enfoque probabilístico y visualizan el proceso de filtrado colaborativo como calcular el valor esperado de una predicción de usuario, teniendo en cuenta su calificación en otros artículos. El proceso de construcción de modelos se realiza mediante diferentes técnicas, tales como las redes bayesianas, el análisis semántico latente o los enfoques basados en reglas.
2) Secuenciación adaptativa de colaboración.
La secuenciación de adaptación es uno de los principales retos en la actualidad en el ámbito de la educación basada en la Web o en cursos virtuales a distancia. Se puede afirmar que el problema de seleccionar el orden en que se presentan un conjunto de unidades para el estudiante (en una secuencia) con el fin de hacer su aprendizaje lo más exitosa posible, teniendo en cuenta las capacidades y necesidades de cada estudiante (personalización). Estos estudiantes diferentes maximizan su aprendizaje con diferentes secuencias de actividades: algunos se beneficiarán de una secuencia con un enfoque de arriba hacia abajo, mientras que otros prefieren lo contrario, secuencias más largas de ejercicios para los temas que se encuentran especialmente difícil puede ser preferible, así como más corto para los conjuntos de temas que ya conocen, y algunos prefieren actividades con una gran cantidad de texto escrito, mientras que otros aprenden más con los recursos gráficos, etc.
Aunque los estudiantes diferentes prefieren diferentes secuencias de aprendizaje, sus preferencias muestran cierto grado de correlación, como en el caso anterior. Por otra parte, el problema de la secuenciación es una de optimización de la ruta («encontrar el camino que maximiza el aprendizaje») como hace las técnicas de swarming planteadas aquí.
Futuro
En cualquier caso, muchas de las aplicaciones más prometedoras de las técnicas de inteligencia de enjambre se están desarrollando en Internet y proceden del ámbito enjambre social. Filtrado colaborativo es un campo activo en algunas aplicaciones comerciales, como el sistema de recomendación Amazon.com (Linden, 2003), mientras que la investigación sobre la secuencia de colaboración puede conducir a una mejor comprensión de la forma en que el usuario navega por la Web.
Aunque el problema de la secuenciación trae similitudes con otros problemas de optimización de ruta, existen diferencias que deben tenerse en cuenta. En primer lugar, el camino tiene que ser optimizado para cada usuario. El camino que es «óptimo» para todo el mundo puede no ser óptima para cada estudiante. Esto es especialmente crítico para los sistemas e-learning. El enfoque adoptado por Gutiérrez (2006) es una mezcla de ambos en colaboración tradicionales de filtrado y sistemas de secuenciación de colaboración, dando a los estudiantes información sobre el desempeño de sus pares y las medidas adoptadas por ellas (como grupo, no individualmente). Este enfoque pone al estudiante en un estado metacognitivo cuando se enfrentan con sus compañeros a los resultados o resolución de probelmas y trae algunas similitudes con el método propuesto en Valigiani (2006), aunque en ese caso la comparación se hace entre los alumnos y el nivel de ejercicios.
Ver el siguiente post con algún video: Swarm Intelligence (15 de febrero de 2011) por Andrés Schuschny.
Referencias:
Abraham, A., Grosan, C., & Ramos, V. (2006). Swarm intelligence in data mining. Springer.
Blum, C., & Merkle, D. (2008). Swarm intelligence: introduction and applications. Springer.
Bonabeau, E., Dorigo, M., & Theraulaz, G. (1999). Swarm intelligence: from natural to artificial systems. Oxford University Press.
Coello, C. A. C., Dehuri, S., & Ghosh, S. (2009). Swarm Intelligence for Multi-objective Problems in Data Mining. Springer.
Dorigo, M. (2010). Swarm Intelligence: 7th International Conference, ANTS 2010, Brussels, Belgium,September 8-10, 2010. Proceedings. Springer.
Dorigo, M., Blum, C., & Birattari, M. (2008). Ant colony optimization and swarm intelligence: 6th international conference, ANTS 2008, Brussels, Belgium, September 22-24, 2008 ; proceedings. Springer.
Dorigo, M., & Stützle, T. (2004). Ant colony optimization. Cambridge, Mass: MIT Press.
Dron, J., Mitchell, R., Siviter, P,& Boyne, C. (1999). CoFIND: Experiment in n-dimensional collaborative filtering. In Proceedings of WebNet 99.
Freire, M. (2007). Encyclopedia of Internet Technologies and Applications. Information Science Publishing.
Gambardella, L. M., Taillard, E., & Agazzi, G. (1999). MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows. Istituto Dalle Molle Di Studi Sull Intelligenza Artificiale. Recuperado a partir de http://portal.acm.org/citation.cfm?id=870474
Huang, Y., & Liu, C. (2009). Applying Adaptive Swarm Intelligence Technology With Structuration in Web-based Collaborative Learning. Computers & Education, 52, 789–799. Recuperado a partir de http://www.scribd.com/doc/31566493/Huang-Applying-Adaptive-Swarm-Intelligence-Technology-With-Structuration-in-Web-based-Collaborative-Learning
Gutiérrez, S., Pardo, A., Delgado, & Kloos, C. (2006). Some ideas for the collaborative search of the optimal learning path. Proceedings of Adaptive Hypermedia 2006.
Gutiérrez, S., Pardo, A., & Delgado, C. (2007). Swarm Intelligence Applications for the Internet. En Encyclopedia of Internet Technologies and Applications. Hershey, PA: Information Science Publishing.
Kennedy, J., Eberhart, R. C., & Shi, Y. (2001). Swarm intelligence. Morgan Kaufmann. Recuperado a partir de http://www.swarmintelligence.org/SIBook/SI.php
Li, F., He, X., & Xu, J. (2010). A new learning model for swarm intelligence based on Q-learning. En Intelligent Control and Automation (WCICA), 2010 8th World Congress on (págs. 2769-2775). Presented at the Intelligent Control and Automation (WCICA), 2010 8th World Congress on. doi:10.1109/WCICA.2010.5554902
Lim, C. P., Jain, L. C., & Dehuri, S. (2009). Innovations in Swarm Intelligence. Springer.
Miller, &. (2007). Swarm Theory. [[National Geographic Magazine]]. Recuperado a partir de http://www7.nationalgeographic.com/ngm/0707/feature5/
Miller, P. (2007). Swarm Theory. Recuperado a partir de http://www7.nationalgeographic.com/ngm/0707/feature5/
Nedjah, N., & Mourelle, L. D. M. (2006). Swarm intelligent systems. Springer.
Surhone, L. M., Timpledon, M. T., & Marseken, S. F. (2010). Swarm Intelligence: Collective Behavior, Decentralization, Self-organization, Artificial Intelligence, Cellular Automaton, Swarm Robotics, Swarm, Ant Colony Optimization, Particle Swarm Optimization. Betascript Publishers.
Swarm intelligence: from natural to artificial systems. (2006). . Oxford University Press.
Tan, Y. (2010). Advances in Swarm Intelligence: First International Conference, ICSI 2010, Beijing, China, June 12-15, 2010, Proceedings. Springer.
Valigiani, G., Lutton, E., Jamont, Y., Biojout, R., & Collet, P. (2006). Automatic rating process to audit a man-hill. WSEAS Transactions on Advances in Engi- neering Education, 3(1), 1-7.
Winkler, R. (2005). Swarm intelligence: review and application. University of Northern Colorado.
Wong, L., & Looi, C. (2010). Swarm intelligence: new techniques for adaptive systems to provide learning support. Interactive Learning Environments. doi:10.1080/10494821003714681
Yao Xinsheng, Xu Guangyin, Cui Yan, Fan Shasha, & Wei Jianguang. (2009). Application of the swarm intelligence in the organization of agricultural products logistics. En Computer Science & Education, 2009. ICCSE ’09. 4th International Conference on (págs. 77-80). Presented at the Computer Science & Education, 2009. ICCSE ’09. 4th International Conference on. doi:10.1109/ICCSE.2009.5228522
Comentarios recientes