Metodo Hormiga

Uso del algoritmo de optimización de
colonia de hormigas - Introducción

Conceptos. Optimización en el diseño de una estructura.

Conceptos
Referencia
Sergio Alonso, Oscar Cordón, Iñaki Fernández de Viana, Francisco Herrera
(Universidad de Granada, España). La Metaheurística de Optimización
Basada en Colonias de Hormigas: Modelos y Nuevos Enfoques. Trabajo
realizado en el marco delproyecto Mejora de Metaheurísticas mediante
Hibridación y sus Aplicaciones, de la Universidad de Granada, España. 2004.
El estudio se refiere a la optimización de problemas combinatorios
complejos. Se trata de problemas de optimización, donde las soluciones
posibles conforman un conjunto discreto (o se puede reducir a éste), y la
optimización minimiza una función dada (por ejemplo, de costos).Cuando
el tamaño del dominio del problema no es muy grande, se puede abordar
con soluciones óptimas globales conocidas como heurísticas. Sin embargo,
en la medida que el dominio aumenta, el problema se vuelve complejo, y
hay que recurrir a soluciones de calidad aunque no sean las óptimas,
denominadas metaheurísticas.
Las técnicas heurísticas son algoritmos basados en el conocimiento deldominio, pero cuando se pretenden aplicar a problemas de gran tamaño no
producen soluciones globales óptimas. Las técnicas metaheurísticas
constituyen métodos aproximados, en situaciones en que las
correspondientes heurísticas no son efectivas.
Un algoritmo es una lista ordenada de operaciones necesarias para obtener
la solución a un problema. En consistencia con las técnicas de optimización(heurísticas y metaheurísticas), se distinguen los algoritmos exactos
(aquellos que pretenden un óptimo global), y los algoritmos aproximados
(que buscan una solución de alta calidad, aunque no necesariamente la
óptima).
Las técnicas metaheurísticas utilizan conceptos de campos diversos como la
genética, la biología, las matemáticas, la física o la neurología, entre otros.
Una de la recientes,es la Optimización basada en Colonias de hormigas
(Ant Colony Optimization, ACO en inglés).

Las colonias de las hormigas
En el comportamiento de las
hormigas se distingue la búsqueda de
alimentos, trazando el camino más
corto entre el hormiguero y el
emplazamiento de alimentos.
El eje de esa búsqueda es el depósito
de feromona como rastro que orienta
el recorrido. Las hormigas prefierenseguir la mayor concentración de
feromona, la misma que se consigue
1

por el recorrido más corto hecho por hormigas (que por esta razón, pueden
repetirlo en forma más seguida). En principio siguen rutas aleatorias, pero
las que han utilizado las de menor longitud pueden regresar más
rápidamente (pues transitan a una velocidad uniforme), y repetir el
camino, dejando una mayor densidadde huellas de feromona. Las
depositadas en las otras rutas se van evaporando, y dejan de tener interés
en los nuevos recorridos. Ello se ilustra en la siguiente figura, adaptada de
las imágenes clásicas para este tema.

Del algoritmo basado en colonias de hormigas
Se simula una colonia de hormigas artificiales que trabajan en grupo y se
comunican a través de rastros de feromona artificial.Cada hormiga
artificial construye una solución al problema recorriendo un grafo de
construcción. Cada arista o tramo del grafo tiene dos tipos de información
que guían el movimiento de la hormiga.
•

La preferencia de moverse desde el nodo r al nodo s en la arista rs.
Esta preferencia se designa con ηrs. El valor no se modifica en el
proceso y es función de la distancia entre los nodos.•

La deseabilidad aprendida del movimiento de r a s. Simula la feromona
o rastro depositado, y se va modificando. Se designa con τrs.

Optimización en el diseño de una estructura
Referencia
Charles V. Camp and Barron J. Bichom (University of Memphis, Memphis,
Tennessee). Design of Space Trusses Using Ant Colony Optimization.
Journal of Structural Engineering, Vol 130, N° 5, May 1,...