Estudio empírico de operadores de cruzamiento en un algoritmo genético aplicado al problema de steiner generalizado

Abstract

El Problema de Steiner Generalizado modela el diseño de redes de comunicaciones confiables en las cuales se exigen requisitos de conexión entre nodos distinguidos, que garanticen con alta probabilidad la comunicación entre sí. Es un problema NP difícil, para el cual pocos algoritmos han sido propuestos. Los algoritmos evolutivos se han utilizado como metaheurísticas alternativas a los métodos exactos para resolver complejos problemas de optimización. Siguiendo este enfoque, hemos propuesto trabajar con algoritmos genéticos para la resolución del Problema de Steiner Generalizado. La calidad de las soluciones obtenidas al utilizar un algoritmo genético depende de múltiples factores, entre los que se pueden destacar los operadores de recombinación y mutación utilizados. El objetivo de este trabajo es estudiar desde un punto de vista empírico la influencia de diferentes operadores de cruzamiento en un algoritmo genético para la resolución del Problema de Steiner Generalizado. Se presentan y comparan los resultados obtenidos utilizando cruzamientos de N puntos y variantes paramétricas del cruzamiento uniforme.