Búsqueda de parámetros por algoritmo genético para Metaheuristica de Colonia de Hormigas para la resolución de problemas Set Covering

PONTIFICIA UNIVERSIDAD CATÓLICA DE VALPARAÍSO
FACULTAD DE INGENIERÍA
ESCUELA DE INGENIERÍA INFORMÁTICA








Búsqueda de parámetros por algoritmo genético para Metaheuristica de Colonia de Hormigas para la resolución de problemas Set Covering
MII 790 – Seminario de Tesis



Alumno: Mauricio Daza Rodenas
Profesor Guía: Broderick Crawford L.





Octubre de 2010
Resumen
Existen problemas deoptimización combinatoria complejos en diversos campos como la economía, el comercio, la ingeniería, la industria o la medicina. Sin embargo, a menudo estos problemas son muy difíciles de resolver en la práctica. El estudio de esta dificultad inherente para resolver dichos problemas tiene cabida en el campo de la teoría de las Ciencias de la Computación, ya que muchos de ellos pertenecen a la clasede problemas NP-duros, lo que significa que no existe un algoritmo conocido que los resuelva en un tiempo polinomial [1].
El problema de cobertura Set Covering pertenece a la rama de los problemas n-p duros y consiste en encontrar la solución optima con el menor costo posible a un problema con distintas soluciones.
Para la resolución de este tipo de problemas se presenta una metaheuristicarelativamente reciente es la optimización basada en colonias de hormigas, la cual se rige por el comportamiento que presentan las hormigas a la hora de encontrar el camino más corto entre el hormiguero y la comida.
Esta metaheuristica requiere ciertos parámetros para funcionar, los cuales deben ser introducidos a mano por el usuario y hacer varios experimentos para encontrar los parámetros que entreguenun valor más cercano al óptimo. Uno de los objetivos de este trabajo es generar estos más óptimos parámetros de forma automática mediante un algoritmo genético.















1 Tabla de contenido

1. Capítulo I 4
1.1 Introducción 4
1.2 Definición de objetivos general(es) y específicos 5
Objetivo General 5
Objetivos específicos 5
2. Capitulo II 6
1.3 Formulación del problema de Set Cobering (SCP)6
3. Capitulo III 9
1.4 Estado del arte 9
4. Capítulo IV 11
Solución Propuesta 11
1.5 METAHEURÍSTICA DE OPTIMIZACIÓN MEDIANTE COLONIAS DE HORMIGAS 11
1.6 ALGORITMOS DE LA METAHEURISTICA ACO 13
Algoritmo Sistema de Hormigas 13
Algoritmo Sistema Colonia de Hormigas 14
C. Algoritmo Sistema de Hormigas MAX-MIN 15
ACO para la resolución de SCP 15
ACS 16
Ecuaciones utilizadas en el algoritmo. 17Información Heurística. 22
Mejoramiento Posterior. 24
5. Capitulo V 26
Estructura multinivel 26
6. Capítulo VI 27
Algoritmos Genéticos 27
Introducción 27
Reseña Histórica 28
Algoritmo Genético 29
Métodos de Selección 30
1.7 Ventajas 38
1.8 Limitaciones 39
1.9 Aplicaciones 39
7. Conclusiones 40
8. Referencias 41


2 Capítulo I

Introducción
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 procedimientopara resolver 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 [1]. 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 unaclase de 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...