Estudio del problema Min-SA y algunas variantes: Algoritmos y heurísticas.
Loading...
Date
2025
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción
Abstract
Los grafos con signos son grafos en los que cada arista se asigna un signo positivo o negativo. Estos grafos se utilizan para representar diversas estructuras, siendo una de las aplicaciones más comunes el modelado de redes sociales o relaciones sociales. En este tipo de representación, las aristas con signos positivos representan una buena relación entre los vértices que conectan, mientras que las aristas con signos negativos representan una mala relación.
Kermarrec y Thraves en [16] plantearon el problema: dado un grafo con signos, ¿existe un embedding en el espacio métrico de la línea euclidiana tal que cada vértice esté más cerca de todos los vértices con los que tiene una buena relación (vértices unidos por aristas positivas) que de aquellos con los que tiene una mala relación (vértices unidos por aristas negativas)? A este problema se le conoce con el nombre de problema de Sitting Arrangement (SA), el cual ha sido ampliamente estudiado.
Pardo, Soto y Thraves, en [25], motivados por el problema SA, buscaron una solución para la versión de optimización del problema SA en la recta euclidiana. Así, se planteó el problema MinSA, que consiste en minimizar el número de errores producidos en un embedding en el espacio métrico de la línea euclidiana. Este problema ha sido abordado mediante enfoques teóricos y heurísticos. Una heurística, que resuelve con buenos resultados el problema MinSA, es la heurística BVNS.
En esta tesis, un objetivo es mejorar los resultados del BVNS implementando algoritmos genéticos combinados con la técnica estadística t-Distributed Stochastic Neighbor Embedding (t-SNE). Por medio de experimentos, se busca encontrar los mejores parámetros tanto para el algoritmo genético como para el t-SNE, para luego, comparar el rendimiento del algoritmo obtenido con el BVNS. Además, otro objetivo de esta tesis, es implementar tanto el algoritmo genético obtenido como el BVNS en dos problemas planteados en esta tesis, los cuales nacen del problema SA.
Description
Tesis presentada para optar al título de Ingeniero/a Civil Matemático/a.
Keywords
Algoritmos genéticos, Heurística, Encajes (Matemáticas)