Un algoritmo heurístico basado en homotopía de caminos

Autor: Martín Manuel de Jesús Hernández Torres
Coautor(es): José-Fernando Camacho-Vallejo Lilia Alanís López
Un algoritmo heurístico basado en homotopía de caminos Martín Hernández-Torres1, José-Fernando Camacho-Vallejo1, Lilia Alanís López1 1Facultad de Ciencias Físico-Matemáticas, Universidad Autónoma de Nuevo León, Monterrey, México. ∗ Correo electrónico: martin.hernandezto@uanl.edu.mx En esta charla se mostrará la aplicación de algunos conceptos de topología discreta para diseñar una heurística capaz de resolver de buena manera problemas combinatorios. En particular, se usan homotopías de caminos para explorar el espacio de solución asociado a un problema binario de programación matemática. Una ε-cadena α en X es una secuencia finita de puntos α = {x0,x1,...,xn-1,xn} tal que d(xi-1, xi) < ε para i = 1,..., n. Por ejemplo, sea X = {0,1}^10 el 10mo-espacio binario con la siguiente métrica: para x = (x1,...,x10), y = (y1,...,y10); d(x, y) = Σ_(i=1)^10|xi−yi|. Entonces α = {x1, x2, x3, x4, x5} donde x1 = (0,1,1,1,1,0,0,0,0,1) x2 = (1,1,1,1,0,0,1,1,0,0) x3 = (0,1,0,1,1,1,0,1,0,0) x4 = (0,1,1,1,1,1,0,0,1,0) x5 = (1,0,1,1,1,0,0,0,1,1) es una 6-cadena. Esto se confirma al calcular las siguientes distancias: d(x1, x2) = 5, d(x2, x3) = 5, d(x3, x4) = 3, d(x4, x5) = 4. Un movimiento básico de una ε-cadena se realiza al agregar o remover un solo punto, pero cumpliendo que los puntos de inicio o fin se mantengan sin cambio, y más aún, que la cadena resultante siga siendo una ε-cadena. Si dos ε-cadenas (a y ß) tiene los mismos puntos iniciales y finales se dice que son ε-homotópicas si hay una secuencia finita de ε-cadenas, llamada ε-homotopía. H = {α = γ0, γ1, ..., γk−1, γk = β}; tal que cada γi difiere de γi−1 por un movimiento básico. Estos conceptos se pueden ver con mayor detalle en Wilkins (2011) Nosotros vamos a considerar esos conceptos de topología para diseñar un algoritmo heurístico que cumpla con dichos requisitos de las ε-cadenas. La finalidad es mostrar que se pueden combinar dos áreas un tanto separadas de las matemáticas (topología y optimización combinatoria) y que este heurístico puede ser una buena opción para resolver problemas binarios. El algoritmo propuesto consiste de dos fases principales: inicialización e intensificación. En la primera fase, se busca construir dos conjuntos de soluciones que sean ε-cadenas y que se cumpla la homotopía entre ambos conjuntos. La forma de la construcción dependerá del problema en cuestión. La segunda fase es donde se busca mejorar la métrica seleccionada para clasificar la calidad de cada conjunto. Durante las búsquedas locales se deben de cumplir todos los criterios para que el conjunto en cuestión siga siendo una ε-cadena. Para mostrar el desempeño del algoritmo se aplicó a tres problemas combinatorios clásicos: el problema de la mochila, el problema del conjunto de cobertura y el problema de asignación generalizada. Se resolvieron varias instancias para cada problema y se le aplicó una adaptación especializada de la heurística propuesta. En todos los casos se mostró que el algoritmo funciona de buena manera obteniendo soluciones de buena calidad para la gran mayoría de las instancias (el óptimo para varias de ellas) en un tiempo de cómputo razonable. Referencias Wilkins, J. Discrete Geometric Homotopy Theory and Critical Values of Metric Spaces. A Dissertation Presented for the Doctor of Philosophy Mathematics. The University of Tennessee, Knoxville, I (1):2–29, 2011. 51 Congreso Nacional de la Sociedad Matemática Mexicana 21 al 26 de octubre de 2018 - Villahermosa, Tabasco