Algoritmos Geneticos
Enviado por darken_or • 17 de Junio de 2015 • 1.440 Palabras (6 Páginas) • 113 Visitas
TÉCNICAS EVOLUTIVAS APLICADAS AL
PROBLEMA DE STEINER GENERALIZADO
"Now, here, you see, it takes all the running you can do, to keep in the same place.
If you want to get somewhere else, you must run at least twice as fast as that."
LEWIS CARROLL
Through the Looking-Glass, 1872.
6.1. Introducción
Los resultados obtenidos en el trabajo con la primera propuesta diseñada de un algoritmo
genético paralelo presentaron promisorias perspectivas sobre la aplicación de técnicas
metaheurísticas evolutivas para la resolución del Problema de Steiner Generalizado.
En una instancia de difusión de los resultados preliminares del proyecto se tomó contacto
con el grupo de trabajo en Redes y Técnicas de Optimización Emergente (NEO - Networking and
Emerging Optimization) del Departamento de Lenguajes y Ciencias de la Computación de la
Universidad de Málaga en España, cuyos integrantes se mostraron interesados en el contexto del
problema y el enfoque utilizado para su resolución. Del intercambio de ideas sobre el problema y
los métodos de resolución surgieron diversas propuestas para intentar abordar la resolución del
Problema de Steiner Generalizado mediante otras técnicas evolutivas y de búsqueda global con el
objetivo de obtener resultados de alta eficiencia numérica.
Este capítulo presenta la aplicación de otras metaheurísticas evolutivas y de búsqueda local
para la resolución del Problema de Steiner Generalizado, que complementa al enfoque del
algoritmo genético paralelo específico presentado en el capítulo precedente y tiene como
principal objetivo disponer de nuevos algoritmos para evaluar comparativamente la calidad de las
soluciones obtenidas. Considerando el enfoque utilizado en el capítulo previo, basado en la idea
de mantener la codificación del problema y los operadores evolutivos tan simples como fuera
posible, se diseñaron otros algoritmos aplicados al problema en cuestión. Para la implementación
de los algoritmos se utilizó una biblioteca de propósito general para optimización combinatoria
que provee esqueletos de software de diversos algoritmos para optimización y que permite tratar
de un modo eficiente con los aspectos de paralelismo.
El capítulo comienza ofreciendo los detalles del enfoque del problema, que se corresponden
a los presentados en el capítulo previo para el algoritmo genético paralelo específico. En la
sección siguiente se introducen los algoritmos estudiados: algoritmos genéticos en su formulación
clásica y en su variante CHC, simulated annealing y dos técnicas híbridas que combinan
algoritmos genéticos y simulated annealing, presentando los conceptos de sus implementaciones
seriales y paralelas sobre la biblioteca utilizada. Luego se presenta un detallado análisis de la
calidad de los resultados obtenidos y de la eficiencia computacional para los diferentes algoritmos
al resolver las instancias de prueba presentadas en el capítulo previo. La sección final del capítulo
presenta las conclusiones sobre la aplicación de técnicas metaheurísticas evolutivas para resolver
el problema considerado y líneas abiertas para continuar la investigación en el futuro.
CAPÍTULO 6 TÉCNICAS EVOLUTIVAS APLICADAS AL PROBLEMA DE STEINER GENERALIZADO
102
6.2. Enfoque del problema
El enfoque utilizado para la codificación, implementación y resolución del problema es el
mismo que se utilizó en el trabajo con el algoritmo genético paralelo específico que se presentó
en el capítulo previo.
Se utilizó la codificación binaria simple basada en aristas para representar grafos que
constituyen soluciones factibles del Problema de Steiner Generalizado. Se aplicó la propuesta de
descartar las soluciones no factibles generadas por los operadores evolutivos. Asimismo, se
utilizó el chequeo de factibilidad de dos componentes, la heurística para chequear los grados de
los nodos terminales, combinada con la variante del algoritmo de Ford–Fulkerson para hallar los
caminos entre cada par de nodos terminales del problema.
La función de fitness corresponde a la utilizada en el capítulo anterior para evaluar el costo
del grafo representado, transformando el problema a una maximización.
6.3. Algoritmos considerados en el estudio
Esta sección presenta los algoritmos heurísticos considerados para aplicarse a la resolución
del Problema de Steiner Generalizado en el marco de este trabajo: algoritmos genéticos en su
formulación clásica y en su variante elitista CHC, simulated annealing y dos técnicas híbridas que
combinan algoritmos genéticos y simulated annealing. Se presentan asimismo las características
de las implementaciones paralelas de los algoritmos estudiados.
Simulated annealing no es una técnica evolutiva, sino que es un método de búsqueda local
inspirado
...