ClubEnsayos.com - Ensayos de Calidad, Tareas y Monografias
Buscar

Algoritmos Geneticos


Enviado por   •  17 de Junio de 2015  •  1.440 Palabras (6 Páginas)  •  139 Visitas

Página 1 de 6

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 en el proceso físico de enfriamiento gradual utilizado en elementos sólidos con el fin de

obtener un estado cristalino de energía mínima. Hemos utilizado este método para disponer de

valores de referencia para comparar los resultados de las técnicas evolutivas, tomando en cuenta

que un esqueleto de su algoritmo se encuentra disponible en la biblioteca de propósito general

para optimización combinatoria utilizada. Asimismo, se ha utilizado el método simulated

annealing para diseñar algoritmos híbridos combinándolo con el mecanismo evolutivo de un

algoritmo genético.

6.3.1. Algoritmo Genético

La formulación clásica de un algoritmo genético fue presentada en el Capítulo 2. Basado en

el esquema genérico de un algoritmo evolutivo presentado en la Figura 2.1, el algoritmo genético

...

Descargar como (para miembros actualizados) txt (11 Kb)
Leer 5 páginas más »
Disponible sólo en Clubensayos.com