english Icono del idioma   español Icono del idioma  

Por favor, use este identificador para citar o enlazar este ítem: https://hdl.handle.net/20.500.12008/22384 Cómo citar
Título: GRASP Heuristics for the stochastic weighted graph fragmentation problem
Autor: Rosenstock Cukrowicz, Nicole
Título Obtenido: Magíster en Investigación de Operaciones
Facultad o Servicio que otorga el Título: Universidad de la República (Uruguay). Facultad de Ingeniería
Tutor: Robledo, Franco
Romero, Pablo
Piccini, Juan
Tipo: Tesis de maestría
Palabras clave: Optimización combinatoria, Path Relinking, Nodos críticos, GRASP, Complejidad computacional
Descriptores: COMPLEJIDAD COMPUTACIONAL
Fecha de publicación: 2018
Resumen: Critical nodes play a major role in network connectivity. Identifying them is important to design efficient strategies to prevent malware or epidemics spread through a network. In this context, the Stochastic Weighted Graph Fragmentation Problem (SWGFP) is a combinatorial optimization problem that belongs to the N P − Complete class. Its objective consists in minimizing the impact of a random attack on a singleton, choosing appropiately a set of nodes to immunize given a restricted budget. In the SWGFP, it is assumed that the attack follows a known probability law and that it affects the whole connected component of the attacked node. In this thesis, a GRASP enriched with Path Relinking algorithm is developed to solve the SWGFP. Its performance is studied under three attack scenarios and compared with a GRASP variant that was previously developed in literature and with a Random heuristic for the problem that picks a set of nodes uniformly at random. Computational experiments show that the algorithm based on Independent Sets which is developed in this thesis, outperforms the other two, with lower expected loss scores and higher robustness.

Los nodos críticos juegan un rol fundamental en la conectividad de las redes. Su identificación es importante para el diseño de estrategias eficientes para prevenir que tanto un software malicioso como una epidemia se propaguen por la red. En este contexto, el Stochastic Weighted Graph Fragmentation Problem (SWGFP) es un problema de optimización combinatoria perteneciente a la clase de problemas NP−Completos. El objetivo consiste en miniminizar el impacto de un ataque aleatorio en un nodo de la red, seleccionando adecuadamente nodos a inmunizar con un presupuesto acotado. En el SWGFP se asume que el ataque sigue una ley de probabilidad conocida en los nodos, y que afecta a toda la componente conexa del nodo seleccionado. En esta tesis se desarrolla una solución GRASP enriquecida con Path-Relinking para abordar el SWGFP. Se estudia el rendimiento de la propuesta ante tres escenarios de ataque, en comparación con una variante de GRASP anteriormente desarrollada de la literatura y una heurística aleatoria o Random para el problema en la cual los nodos son elegidos al azar. Los experimentos computacionales muestran que el algoritmo basado en Conjuntos Independientes que se desarrolla en esta tesis, presenta un mejor desempeño que los dos restantes, con valores inferiores del número esperado de pérdidas y mayor robustez.
Editorial: Udelar.FI
ISSN: 1688-2792
Citación: Rosenstock Cukrowicz, N. GRASP Heuristics for the stochastic weighted graph fragmentation problem [en línea]. Tesis de maestría. Montevideo : Udelar. FI. INCO, 2018.
Licencia: Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0)
Aparece en las colecciones: Tesis de posgrado - Instituto de Computación

Ficheros en este ítem:
Fichero Descripción Tamaño Formato   
ROS19.pdf1,19 MBAdobe PDFVisualizar/Abrir


Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons Creative Commons