Un algoritmo memético multipoblacional y un algoritmo memético celular para el problema del árbol de cobertura mínimo generalizado.

Abstract

En esta Tesis, se diseñan dos propuestas de solución para el problema de conectividad conocido como el árbol de cobertura mínimo generalizado (GMSTP por sus siglas en inglés) mediante un algoritmo memético multipoblacional y un algoritmo memético celular. Se realiza una parametrización para cada algoritmo considerando aquellos factores considerados más importantes y que puedan afectar de mayor forma el desempeño del algoritmo a través de un análisis de los parámetros más relevantes. Para el cálculo de resultados se utilizan instancias disponibles y utilizadas en la literatura, las cuales muestran gran eficiencia del algoritmo en la calidad y tiempo comparables, principalmente en lo relativo a instancias medianas y grandes donde los autores previos presentan escasos resultados, lo que permite a ambos algoritmos propuesto convertirse en una alternativa viable para resolver éste tipo de problema.