Sistema de La Colonia de Hormigas
Sistema de La Colonia de Hormigas
Sistema de La Colonia de Hormigas
INTRODUCCIN
Para entender de mejor manera el sistema a estudiar se describe lo que pasa en el mundo real: Se basa en el comportamiento colectivo de una colonia de hormigas, si bien son insectos diminutos y casi ciegos movindose casi al azar, pero son capaces de mostrar comportamientos complejos y realizar tareas complicadas como son encontrar el camino ms corto desde su nido hasta la fuente de alimentos y regresar. Para esto, cuando una hormiga se mueve, deja una seal de olor, depositando una substancia denominada feromona, para que las dems puedan seguirla, si el rastro se divide en dos, una hormiga elige con mayor decisin, el rastro que contiene mayor concentracin de feromona. Dependiendo del entorno que se encuentren va a favorecer a la eliminacin del rastro de los caminos menos transitados provocando la evaporacin de la feromona depositada. Sin embargo, los caminos ms concurridos sufren menos la evaporacin, ya que continan recibiendo feromona de las hormigas con ms frecuencia. [1]
PROCEDIMIENTO (Ant Colony Sistem)
Condicin de Fin
SI
FIN
1 DESARROLLO
1.1 SISTEMA DE HORMIGAS. LA COLONIA DE
Actualizacin de Feromonas
Hay que aclarar que existen varios modelos de Optimizacin Basada en Colonias de Hormigas (OCH) pero son pequeas variantes que se han hecho con el propsito de disminuir el error pero todos se basan inicialmente del algoritmo de Sistema de Hormigas (Ant System AS). Se pueden identificar seis pasos a seguir fundamentales, sin embargo se debe aclarar que stos solo dan una idea general por lo cual vamos a resumir en un diagrama de flujo descrito en la fig. 1.1. [2] 1 En el ltimo proceso de Acciones Daemon Estos pasos son:
1. Representar el problema mediante nodos, que contribuyen secuencialmente a construir una solucin. 2. Definir el significado de los rastros de feromona de una manera adecuada. 2 3. Poner pesos a la informacin heurstica (informacin previa) en cada nodo o cada arco. 4. Desarrollar algoritmos que permitan realizar optimizaciones locales a fin de mejorar el rendimiento.
2
Daemon: Proceso que se ejecuta en segundo plano en vez de ser controlado directamente por el usuario
Heurstica: es un mtodo basado en la experiencia que puede utilizarse como ayuda para resolver problemas de diseo. Tomado de Wikipedia.
.
5. Escoger un algoritmo OCH especfico en nuestro caso el (ACS). 6. Refinar los parmetros del algoritmo de OCH. Es 3 decir, que se deben obtener los valores , , y el nmero de hormigas ptimos, para el problema especfico. [3]
DE
A grandes rasgos indicaremos que un algoritmo por colonias de hormigas est estructurado por tres procesos que se repiten a lo largo de una serie de iteraciones: Construir soluciones, Evaluar soluciones, y Depositar feromonas.
2 CONCLUSINES
Como conclusin del estudio realizado podemos decir que es un sistema con un buen rendimiento que es aplicado para resolver un mayor nmero de problemas de optimizacin combinatoria complejos, como se dijo anteriormente, nace del Sistema de Hormigas, ya que es el ms bsico y simple a partir del cual se desarrollaron algoritmos ms complejos como el ACS, Presentando resultados ms precisos gracias a las mejoras realizadas como lo son: Da mayor importancia a la experiencia acumulada por las hormigas (agentes). La feromona se deposita solo donde hay mayor presencia. Cada hormiga evapora el valor de feromona en cada paso de un nodo hacia otro (dejar rastro). En este trabajo, hemos revisado las ideas bien marcadas de este sistema por parte de varios autores, y todos ellos nos llevan desde la inspiracin biolgica (es decir: lo que pasa en el mundo real) hasta la utilizacin mtodos heursticos para resolver algn tipo de problema computacional, usando los parmetros dados 4 por el usuario . Es decir cuando se presentan problemas en diversos campos como la economa, el comercio, la ingeniera, la medicina, etc. que son muy difciles de resolver en la prctica, y la programacin normal no nos puede ayudar en estos aspectos, se hace uso de este tipo de sistemas, para tratar de entender aspectos como la de experiencia (depsito de feromonas) y muchos otros ms, para tener una mejor solucin es decir tener un rango mnimo de error.
ij -Distancia heurstica entre un nodo i y a un nodo j pij- Es la probabilidad de ramificarse desde un nodo i y
a un nodo j. [4] Donde , , y q0 son parmetros: representa la importancia que se da a las estelas de feromona, representa la importancia de la informacin heurstica ij, y q0 determina la importancia relativa entre explotacin y exploracin: es decir cuanto ms pequeo sea q0, mayor ser probabilidad de usar la regla probabilista descrita anteriormente. [2] Depsito de feromona: En ACS la actualizacin de las estelas de feromona se realiza de forma local y global. La actualizacin local se realiza durante la construccin de soluciones, mientras que la global se realiza tras la fase de construccin de soluciones. Pero razones mayores solo vamos a plantear la frmula: Donde (0 1) es la tasa de evaporacin de gh gb feromonas y J es el valor objetivo de . [1]
3 REFERENCIAS
y son parmetros que determinan la influencia de la feromona que estos se toman de una tabla de parmetros OCH.