Optimización de problemas NP-Completos a través de la auto-organización crítica
Cargando...
Autores
Director
Tipo de contenido
Editor
Document language:
Español
Fecha
Título de la revista
ISSN de la revista
Título del volumen
Documentos PDF
Resumen
La presente tesis explora la Auto-Organización Crítica (SOC) como un paradigma de
optimización “libre de parámetros” para resolver problemas combinatorios NP-difíciles. A
diferencia de las metaheurísticas tradicionales como el Simulated Annealing, que requieren un ajuste experto de calendarios de enfriamiento, investigamos si las dinámicas de
avalancha inherentes a los modelos de pila de arena pueden regular autónomamente el
equilibrio entre exploración y explotación.
La metodología se desarrolla en dos etapas. En la primera, validamos la eficacia de
SOC replicando resultados en problemas con topología estática: modelos de vidrio de espín
(Ising), coloreado de grafos y segmentación de imágenes, demostrando su capacidad para
escapar de mínimos locales. En la segunda etapa, extendemos el marco a problemas de
permutación mediante el Problema del Viajante (TSP). (Texto tomado de la fuente)
Abstract
This thesis investigates Self-Organized Criticality (SOC) as a “parameter-free” metaheuristic for solving NP-hard combinatorial optimization problems. Unlike traditional metaheuristics such as Simulated Annealing, which rely on expert tuning of cooling
schedules, we explore whether the avalanche dynamics inherent in sandpile models can
autonomously regulate the balance between exploration and exploitation.
The methodology is developed in two stages. First, we validate the efficacy of SOC
by replicating results on problems with static topology: Ising spin glass models, graph
coloring, and image segmentation, demonstrating its ability to escape local minima. In
the second stage, we extend the framework to permutation problems via the Traveling
Salesman Problem (TSP).
Descripción
ilustraciones, gráficas