Optimización De Las Colonias De Hormigas.

OPTIMIZACIÓN DE LAS COLONIAS DE HORMIGAS.

Índice

[pic]

1. Introducción………………………………...............................3

1.1. Comportamiento de las Hormigas en la naturaleza…………………………4

1.2. Las Hormigas Artificiales…………………………………………………..5

1.3. Similitudes y Diferencias Entre las Hormigas Naturales y Artificiales…….6

2. Algoritmo de OCH…………………………………………….82.1. Estructura de un algoritmo de OCH………………………………………...9

2.2. Pasos a seguir para resolver un problema mediante OCH………………....10

2.3. Explicación del algoritmo………………………………………………….11

3. Problema del viajante–Travelling Salesman Problem (TSP)...14

3.1. Planteamiento del problema………………………………………………..14

3.2. Resolución…………………………………………………………………153.2.1. Regla probabilística de transición………………………………..16

3.2.2. Actualización de la feromona……………………………………17
3.2.3. Ejemplo …………………………………………………………..18

4. Distribución en planta orientada a procesos………………….21
4.1. Planteamiento con un ejemplo……………………………………………..21

4.2. Algoritmo…………………………………………………………………..24

4.2.1. Información heurística yrastro de feromona…………………….25

4.2.2. Resolución del algoritmo………………………………………...27

5. Otras aplicaciones de OCH…………………………………..28

5.1. Diseño de un algoritmo de clustering……………………………………...28

5.2. Predicción de la estructura de una proteína………………………………..30

5.3. Buen funcionamiento económico de una estación de energíahidroeléctrica……………..…………………………………………………….31

5.4. Optimización del los movimientos de máquina-herramienta

en soldadura y corte…………………………………………………………….31

5.5. Uso de la OCH para optimizar la segmentación automática de las palabras para el griego antiguo…………………………………………………………..32

6. Conclusión final……………………………………………...35

6. Bibliografía…………………………………………………..36

1. Introducción

[pic]

La existencia de una gran cantidad y variedad de Problemas deOptimización Combinatoria incluidos en la clase NP-completos que necesitan ser resueltos de forma eficiente, impulsó el desarrollo de procedimientos para encontrar buenas soluciones, aunque no fueran óptimas. Estos métodos, en los que la rapidez del proceso es tan importante como la calidad de la solución obtenida, se denominan heurísticos o aproximados. Un método heurístico es un procedimiento pararesolver un problema de optimización bien definido mediante una aproximación intuitiva, en la que la estructura del problema se utiliza de forma inteligente para obtener una buena solución. Luego, con el propósito de obtener mejores resultados que los alcanzados por los heurísticos tradicionales surgen los denominados procedimientos metaheurísticos. Los procedimientos metaheurísticos son una clasede métodos aproximados que están diseñados para resolver problemas difíciles de optimización combinatoria, en los que los heurísticos clásicos no son efectivos. Los metaheurísticos proporcionan un marco general para crear nuevos algoritmos híbridos combinando diferentes conceptos derivados de la inteligencia artificial, la evolución biológica y los mecanismos estadísticos.
Se han desarrolladovarias metaheurísticas para solucionar problemas de optimización, entre ellas se encuentran: la Optimización basada en Colonias de Hormigas, que está incluida en la categoría de los algoritmos bioinspirados o de vida artificial e inteligencia colectiva.

La metaheurística Optimización mediante Colonias de Hormigas (OCH) o Ant Colony Optimization (ACO), propuesta para resolver problemas complejos deoptimización combinatoria tiene su fuente de inspiración en el comportamiento de colonias de hormigas reales.
Esta teoría fue creada en 1990 por Marco Dorigo, director de la investigación para los fondos belgas para la investigación científica (FNRS), y co-director de IRIDIA, el laboratorio de la inteligencia artificial del Université Libre de...