Olaaa tesis
Páginas: 52 (12768 palabras)
Publicado: 24 de noviembre de 2010
Ant System
Marta Almirón
Trabajo presentado como requisito para optar al título de Máster en Ingeniería de Sistemas
Asesor: D.Sc. Benjamín Barán
Universidad Nacional de Asunción Diciembre-2000MA
INDICE GENERAL
Indice General
1. Introducción 1.1. Consideraciones iniciales................................................................................. 1.2. Técnicas deInteligencia Artificial.................................................................... 1.3. Procesamiento paralelo .................................................................................... 1.4. Revisión Bibliográfica de la Colonia de Hormigas ........................................... 1.5. Objetivos y Organización del presente trabajo ................................................. 2. ElProblema del Cajero Viajante 2.1. Introducción .................................................................................................... 2.2. El Problema NP-Completo .............................................................................. 2.3. Revisión Bibliográfica ..................................................................................... 2.4. Problemasutilizados........................................................................................ 3. Ant System 3.1. Introducción .................................................................................................... 3.2. Principales variables ........................................................................................ 3.3. Distintas versiones de Ant System................................................................... 3.3.1. Ant Density ........................................................................................... 3.3.2. Ant Quantity.......................................................................................... 3.3.3. Ant Cycle .............................................................................................. 3.4.Pseudocódigos................................................................................................. 3.4.1. Ant Density y Ant Quantity ................................................................... 3.4.2. Ant Cycle .............................................................................................. 3.5. Evolución de la matriz de feromonas............................................................... 7 7 8 21 25 28 30 30 31 35 46 49 49 52 55 55 55 55 56 56 58 60
INDICE GENERAL 4. Mejoras propuestas para Ant Quantity 4.1. Problema propuesto ......................................................................................... 4.2. Mejoras introducidas........................................................................................ 4.3. Resultados experimentales............................................................................... 5. Ant Cycle Paralelo 5.1. Paralelismo Asíncrono del Ant Cycle............................................................... 5.2. Variantes implementadas ................................................................................. 5.3. Comparación de las diversas versiones implementadas ....................................5.4. Resultados experimentales ............................................................................... 5.5. Porque se utiliza PVM ..................................................................................... 5.6. Comparación con trabajos anteriores................................................................ 6. Conclusiones 7. Bibliografía 8. Referencias a Páginas Web 64 64 6566 70 71 74 75 77 80 81 84 87 95
Indice de Figuras
1. Complejidad del Problema...................................................................................... 2. Un movimiento 2-opt.............................................................................................. 3. Dos movimientos 3-opt posibles ................................................................................
Marta Almirón
Trabajo presentado como requisito para optar al título de Máster en Ingeniería de Sistemas
Asesor: D.Sc. Benjamín Barán
Universidad Nacional de Asunción Diciembre-2000MA
INDICE GENERAL
Indice General
1. Introducción 1.1. Consideraciones iniciales................................................................................. 1.2. Técnicas deInteligencia Artificial.................................................................... 1.3. Procesamiento paralelo .................................................................................... 1.4. Revisión Bibliográfica de la Colonia de Hormigas ........................................... 1.5. Objetivos y Organización del presente trabajo ................................................. 2. ElProblema del Cajero Viajante 2.1. Introducción .................................................................................................... 2.2. El Problema NP-Completo .............................................................................. 2.3. Revisión Bibliográfica ..................................................................................... 2.4. Problemasutilizados........................................................................................ 3. Ant System 3.1. Introducción .................................................................................................... 3.2. Principales variables ........................................................................................ 3.3. Distintas versiones de Ant System................................................................... 3.3.1. Ant Density ........................................................................................... 3.3.2. Ant Quantity.......................................................................................... 3.3.3. Ant Cycle .............................................................................................. 3.4.Pseudocódigos................................................................................................. 3.4.1. Ant Density y Ant Quantity ................................................................... 3.4.2. Ant Cycle .............................................................................................. 3.5. Evolución de la matriz de feromonas............................................................... 7 7 8 21 25 28 30 30 31 35 46 49 49 52 55 55 55 55 56 56 58 60
INDICE GENERAL 4. Mejoras propuestas para Ant Quantity 4.1. Problema propuesto ......................................................................................... 4.2. Mejoras introducidas........................................................................................ 4.3. Resultados experimentales............................................................................... 5. Ant Cycle Paralelo 5.1. Paralelismo Asíncrono del Ant Cycle............................................................... 5.2. Variantes implementadas ................................................................................. 5.3. Comparación de las diversas versiones implementadas ....................................5.4. Resultados experimentales ............................................................................... 5.5. Porque se utiliza PVM ..................................................................................... 5.6. Comparación con trabajos anteriores................................................................ 6. Conclusiones 7. Bibliografía 8. Referencias a Páginas Web 64 64 6566 70 71 74 75 77 80 81 84 87 95
Indice de Figuras
1. Complejidad del Problema...................................................................................... 2. Un movimiento 2-opt.............................................................................................. 3. Dos movimientos 3-opt posibles ................................................................................
Leer documento completo
Regístrate para leer el documento completo.