APLICACIÓN DE GRAFOS EN INTELIGENCIA COLECTIVA EN LA BUSQUEDA DEL CAMINO MAS RAPIDO

                               UNIVERSIDAD NACIONAL DEL ALTIPLANO[pic 1]

                                    MAESTRIA EN INGENIERIA DE SISTEMAS

APLICACIÓN DE GRAFOS EN INTELIGENCIA COLECTIVA EN LA BUSQUEDA DEL CAMINO MAS RAPIDO

GCH

CFW

CCM

RESUMEN

La inteligencia colectiva o de enjambre es el estudio del comportamiento colectivo en sistemas auto organizados y descentralizados, en este artículo se va experimentar a  las hormigas donde realizan diferentes movimientos a fin de encontrar el camino más corto para llegar a sus alimentos, en este artículo tiene como objetivo seleccionar el camino más corto de entre varios caminos hacia sus alimentos. En este artículo se aplicará fórmulas matemáticas o más conocido como el algoritmo ACO, y grafos para simular su recorrido de las hormigas. Para la experimentación se utilizará el programa Microsoft Excel. Como resultado se obtuvo  que el comportamiento de la hormiga se puede comprender utilizando el algoritmo ACO, en este caso se logró experimentar el comportamiento de una hormiga al elegir un camino más corto para llegar a sus alimentos.

Palabras clave: Inteligencia colectiva-Inteligencia de enjambre. –Algoritmo ACO –Grafo.-Hormigas.

.

TÍTULO DEL ARTÍCULO EN INGLÉS

ABSTRACT

Collective or swarm intelligence corresponds to a group of techniques that are based on the study of collective behavior in self-organized and decentralized systems, in which ants perform different movements in order to find the shortest way to reach their food. , in this work, it aims to understand how they find the shortest path between several paths to their food, mathematical formulas better known as ACO algorithm will be applied, and graphs to simulate their path of ants. The Microsoft Excel program will be used for data processing. Leading to conclude that the behavior of the ant can be understood using the ACO algorithm, in this case it was possible to experience the behavior of an ant by choosing a shorter path to reach their food.

Keywords Collective Intelligence-Swarm Intelligence. –Algorithm ACO –Graph.-Ants.

1. INTRODUCCIÓN

Una de las aplicaciones más comunes de la inteligencia artificial (IA) es la búsqueda de la solución óptima en problemas de alta complejidad, tanto en espacios continuos como discretos. ( Muñoz & Caicedo, 2008)

Según Hertz y Kobler (2000), las técnicas utilizadas para resolver problemas complejos de optimización combinatoria han evolucionado progresivamente de métodos constructivos a métodos de búsqueda local y finalmente a algoritmos basados en poblaciones. Además los métodos basados en poblaciones tienen la ventaja adicional de ser capaces de combinar buenas soluciones en orden de obtener unas mejores, ya que se considera que las buenas soluciones comparten componentes con las soluciones óptimas se les conoce como algoritmos de computación evolutiva (Evolutionary Computation – EC). Los algoritmos de EC comprenden un conjunto de técnicas iterativas que manejan una población de individuos que son evolucionados (modificados) mediante una serie de reglas que han sido claramente especificadas. la EC representa un amplio grupo de técnicas, básicamente dividida en dos ramas, cuyas diferencias fundamentales se encuentran en la aplicación de diferentes técnicas: los algoritmos evolutivos (Evolutionary Algorithms – EA) y la inteligencia de enjambres (Swarm Intelligence – SI).  ( Muñoz, López, & Caicedo, 2008)

INTELIGENCIA DE EJAMBRES O COLECTIVA:

La Inteligencia de Enjambres (Swarm Intelligence, SI) estudia el comportamiento colectivo de sistemas compuestos por muchos individuos (el swarm) interactuando localmente y con su entorno.  ( Martens & Fawcett, 2011)Los swarms inherentemente usan formas de control descentralizadas y de auto-organizaci´on para alcanzar sus objetivos.

Existen algoritmos orientados a Map-Reduce de las metaheurísticas ACO, PSO, CS y GSO. A continuación mostramos sus características:

ACO: Es una meta heurística poblacional inspirada en el comportamiento de la búsqueda de alimento de una especie de hormigas. Las hormigas inicialmente exploran el área alrededor del nido en una manera aleatoria. Cuando una hormiga encuentra una fuente de comida, esta evalúa la calidad y la cantidad de la misma y la lleva al nido, depositando en el entorno una sustancia química denominada feromona, dependiendo de la cantidad y la calidad de la comida encontrada  ( Dorigo & Blum, 2005).

BCA: Se inspira en el comportamiento de  búsqueda de alimento de las abejas productoras de miel, realizando un tipo de búsqueda de vecindad combinada con una búsqueda aleatoria  ( Pham & Ghanbarzadeh, 2006).

CS: Se basa en el comportamiento parasito de algunas especies de cucos a la hora de depositar sus huevos en nidos ajenos. Los huevos del cuco han evolucionado en forma y color hasta imitar a los huevos del pájaro dueño del nido. Si dicho pájaro descubre que el huevo no es suyo, lo tira o abandona el nido, construyendo un nido en otro lugar. Si el huevo del cuco eclosiona el ciclo se repite (Yang & Deb, 2009).

FWA: Es un nuevo algoritmo SI inspirado en el fenómeno de explosión de los fuegos artificiales. El proceso de optimización es guiado por las explosiones de un swarm de fuegos artificiales. El fuego con mejor fitness genera más chispas dentro de un rango pequeño. Para mejorar la búsqueda son necesarios más recursos de computación en las mejores zonas del espacio de búsqueda y menos en las peores zonas de dicho espacio de búsqueda  (Randall & Lewis, 2002).

Se basa en la metáfora del comportamiento de hormigas para buscar y encontrar los caminos posibles más cortos entre las fuentes de comida y hormiguero. También se basa en la conducta de auto organización, el alineamiento de aves de vuelo, rebaños y cardúmenes.

1. Ilustración 1: Diagrama de flujo del proceso de ACO

[pic 2]

OPTIMIZACIÓN POR COLONIA DE HORMIGAS

La optimización por colonia de hormigas (ACO) es una familia de algoritmos derivados del trabajo realizado por Dorigo et al., (1991a), basada en el comportamiento social de las hormigas, las cuales usan una forma de comunicación basada en sustancias químicas denominadas feromonas Estas sustancias, depositadas por la hormiga al avanzar por un camino, ejercen una acción sobre la decisión de las hormigas precedentes, las cuales escogen el camino que posea una mayor concentración de sustancia, permitiendo que encuentren la ubicación de las fuentes de alimento así como su nido. Se ha demostrado que los rastros de feromona permiten lentamente la optimización distribuida en la cual cada agente sencillo realiza una pequeña contribución en la búsqueda de la mejor solución.

...