Búsqueda de puntos débiles en redes de comunicaciones mediante algoritmos metaheurísticos

Abstract

En este TFM se abordará el problema de encontrar un separador mínimo en redes genéricas mediante algoritmos metaheurísticos. Este tipo de algoritmos son capaces de obtener soluciones de alta calidad necesitando tiempos de ejecución reducidos, pero sin garantizar la optimalidad de la solución encontrada. En concreto, se utilizará la metodología Variable Neighborhood Search (VNS), la cual se basa en cambios sistemáticos de vecindad para escapar de óptimos locales. Dicha metodología se ha aplicado con éxito en numerosos problemas de optimización gracias a su versatilidad.

This TFM will address the problem of finding a minimum spacer in generic networks using metaheuristic algorithms. This type of algorithms are capable of obtaining high quality solutions, requiring reduced execution times, but without guaranteeing the optimality of the solution found. Specifically, the Variable Neighborhood Search (VNS) methodology will be used, which is based on systematic neighborhood changes to escape local optima.

En aquest TFM s'abordarà el problema de trobar un separador mínim en xarxes genèriques mitjançant algorismes metaheurístics. Aquest tipus d'algorismes són capaços d'obtenir solucions d'alta qualitat necessitant temps d'execució reduïts, però sense garantir la optimalitat de la solució oposada. En concret, s'utilitzarà la metodologia Variable Neighborhood Search (VNS), la qual es basa en canvis sistemàtics de veïnatge per escapar d'òptims locals. Aquesta metodologia s'ha aplicat amb èxit en nombrosos problemes d'optimització gràcies a la seva versatilitat.