SABER UCV >
2) Tesis >
Maestría >

Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/123456789/3568

Título : Una heurística para el problema de interdicción determinística.
Autor : Hernández. M., Sara L.
Palabras clave : heurística
interdicción determinística
redes
algoritmo
espacio de búsqueda
óptimo
flujo máximo
Fecha de publicación : 16-May-2013
Citación : TESIS;I2008 H557 CD
Resumen : El presente trabajo tuvo como propósito desarrollar una heurística para resolver el problema de interdicción determinística, en el cual se busca minimizar el flujo máximo que puede atravesar una red cuando existen limitaciones en la disponibilidad de recursos que pueden destinarse a la inhabilitación de uno o más arcos de dicha red. La capacidad nominal de cada arco y su costo de interdicción pueden variar entre cada arco. Para el desarrollo de la heurística se tomó como base una heurística pre-existente, denominada Probabilistic Solution Discovery Algorithm (PSDA), propuesta por Ramírez-Márquez y Rocco (2008), la cual fue diseñada originalmente para abordar el problema de confiabilidad all-terminal en redes. Un estudio detallado de la misma condujo a identificar las modificaciones necesarias para adaptar dicha heurística al problema de interdicción determinística. La versión modificada, PSDA-INT, fue aplicada a tres tipos de redes: a) problemas de redes ilustrativas, b) problemas de redes con solución óptima conocida y c) problemas de redes con solución óptima desconocida. Los resultados obtenidos se compararon con los reportados en la literatura para las redes que han sido estudiadas desde la óptica de la interdicción. Esta comparación se efectuó en términos de calidad de la solución (valores extremos y promedio) y eficiencia en el espacio de búsqueda. El estudio permitió concluir que el PSDA-INT demostró buena capacidad de búsqueda en los distintos experimentos realizados. Desde el punto de vista de esfuerzo computacional, el PSDA-INT demostró eficiencia debido a que produjo las soluciones a partir de espacios de búsqueda significativamente reducidos con respecto a los que resultarían de la enumeración explícita de las posibles configuraciones de las redes. Esta investigación proporcionará una herramienta para orientar la búsqueda de estrategias destinadas a atenuar las actividades de un adversario que esté operando en un sistema modelable a través de una red.
URI : http://saber.ucv.ve/jspui/handle/123456789/3568
Aparece en las colecciones: Maestría

Ficheros en este ítem:

Fichero Descripción Tamaño Formato
UNA HEURISTICA PARA EL PROBLEMA DE INTERDICCION DETERMINISTICA.pdf1.98 MBAdobe PDFVisualizar/Abrir

Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.

 

Valid XHTML 1.0! DSpace Software Copyright © 2002-2008 MIT and Hewlett-Packard - Comentarios