Las cinco comparaciones en el corazón del estudio de reparación, desarrolladas: la destrucción aleatoria ciega gana mientras que todo operador que apunta a los conflictos pierde; la construcción fija el suelo; el recocido simulado es la regla de aceptación más fuerte; y los refinamientos ingeniosos (recarga exacta, reinicios) no aportan nada con este presupuesto.
por Raphaël Anjou
Cinco comparaciones sostienen el estudio de reparación. Cada una aísla una decisión manteniendo las otras cuatro fijas en un bucle de referencia simple: inicio voraz, destruir las celdas en desajuste, recarga voraz, conservar el resultado salvo que pierda puntuación, nunca reiniciar. Todas las puntuaciones son el número medio de aristas concordantes sobre las diez variantes con esquinas fijadas, un solo núcleo, sesenta segundos. La tasa de iteración nunca se compara entre familias.
Cambie solo el tablero desde el que arranca el bucle, y todo lo demás de la ejecución se deriva de él. Una construcción voraz empieza en torno a 348 y el bucle la eleva a una media de 366. Un tablero aleatorio empieza cerca de 18 y el bucle lo eleva unos enormes 308 puntos, hasta una media de 326. Esa elevación mayor no es el bucle haciéndolo mejor; es el bucle haciendo mal el trabajo de la construcción. El inicio aleatorio, tras millones de iteraciones, todavía termina por debajo de donde el inicio voraz empezaba.
Este es el primer resultado del estudio, y el más firme: la construcción es la palanca, la reparación es el pulido. Una construcción voraz de "color más escaso primero" (la heurística de Selby y Riordan según la cual un color escaso debe gastarse allí donde queda forzado) empieza un poco más alto aún y termina en una media de 373, la mejor de los inicios voraces.
La prueba más nítida de este punto es partir de un tablero genuinamente fuerte en lugar de uno voraz. La última variante de tablero de partida entrega al bucle un tablero construido por el break-DFS del estudio DFS: la ejecución dedica sus primeros veinte segundos a hacer backtracking hasta un tablero en torno a 440, y luego lo repara durante los cuarenta restantes. Ese inicio está cien puntos por encima de una construcción voraz, y se propaga directamente hasta la llegada. Es la variante de mayor puntuación de todo el estudio, con una media de 446 (mejor 449), muy por encima de los 402 del bucle de destrucción aleatoria, y zanja la pregunta de construir-y-luego-refinar en torno a la cual gira el resto del estudio: la reparación sí añade unas pocas aristas sobre un tablero fuerte obtenido por backtracking, pero solo unas pocas, y el tablero del que parte decide casi todo. Esta es exactamente la división del trabajo que emplean los récords, y este estudio la reproduce de principio a fin en un núcleo en un minuto: un backtracker para construir un buen tablero, y luego un bucle de reparación para exprimir de él las últimas aristas.
Ahora fijemos el inicio voraz y cambiemos solo qué celdas levanta cada iteración. Este es el eje que porta el resultado más sorprendente del estudio.
El patrón es limpio y merece enunciarse sin rodeos: sobre este inicio voraz mediocre, cuanto más precisamente un operador apunta a las roturas existentes, peor le va, y la destrucción aleatoria ciega gana. Esto es lo contrario de la intuición natural, y de lo que funciona sobre un tablero cercano al récord, donde todo el tablero está próximo al óptimo y donde el ajuste de la comunidad halló que los operadores dirigidos por conflictos y por componentes eran los más valiosos, precisamente porque los pocos desajustes restantes son lo único que queda por corregir. Este estudio nunca alcanza ese régimen. Sesenta segundos sobre un tablero mediocre dejan un amplio margen de mejora en todas partes, y ahí un operador que reataca sin cesar el mismo grupo roto, o que arranca un hueco demasiado grande para reconstruirlo bien, pierden ambos frente a uno que simplemente sigue intentando nuevas regiones pequeñas. El hallazgo no es "la destrucción dirigida por conflictos es mala" sino "qué operador gana depende de lo bueno que ya sea el tablero, y sobre un tablero mediocre, explorar supera tanto a fijarse como a sobredestruir".
Fijemos la destrucción y cambiemos solo la recarga. Romper los empates exactos de puntuación de la recarga voraz con una moneda sembrada, en lugar de forma determinista, añade un poco de exploración y ayuda ligeramente, hasta una media de 365. La comparación más tajante es voraz contra recarga exacta, y hay que montarla con cuidado para que sea una prueba limpia de un solo eje: la recarga exacta solo compensa cuando el hueco es lo bastante pequeño para explorarlo, así que el estudio la empareja con una destrucción pequeña (a lo sumo seis celdas en desajuste) y la compara contra la misma destrucción pequeña recargada vorazmente, de modo que lo único que cambia entre ambas es la recarga. Montada así, la recarga exacta corre en cada iteración en lugar de replegarse a la voraz, reconstruyendo cada hueco pequeño a su verdadero óptimo.
El resultado es un negativo limpio. La recarga exacta (media 360) no supera a la recarga voraz del mismo hueco pequeño (media 363); si acaso queda un matiz por detrás. Dos cosas lo explican. La recarga exacta acepta casi cada iteración, porque una reconstrucción localmente óptima de un hueco de seis celdas casi nunca baja la puntuación, de modo que el bucle deriva lateralmente en lugar de escalar. Y compra esa optimalidad local a alrededor de un tercio del número de iteraciones, de modo que en un minuto fijo explora menos el tablero. Sobre este puzzle, con este presupuesto, una reconstrucción localmente perfecta de una región minúscula no vale lo que cuesta: las reconstrucciones más baratas y ligeramente peores de la recarga voraz, ejecutadas más a menudo, llegan igual de lejos. Esta es la misma pregunta de "la tasa de nodos no es la puntuación" que plantean los motores heurísticos del estudio DFS, y aquí la respuesta cae del lado de más iteraciones, más baratas, lo cual merece consignarse precisamente porque tan a menudo se supone lo contrario.
Fijemos el bucle y cambiemos solo cuándo se conserva un candidato no mejorante. De los cinco ejes, este es el que más mueve la puntuación después del operador de destrucción.
Así que la regla de aceptación es aquí una palanca real, no un detalle: de estricta a recocido hay un vaivén de dieciséis puntos sobre el mismo bucle (361 a 377). Eso merece enunciarse frente a una observación conocida del propio ajuste ALNS de la comunidad: que a lo largo de un amplio rango de temperaturas de recocido las puntuaciones finales eran esencialmente idénticas. Las dos no están en conflicto. Ese ajuste se hizo sobre tableros cercanos al récord, donde el paisaje es un mar de mesetas de puntuación igual y cualquier temperatura acepta casi todo; el tablero de partida mediocre de este estudio todavía tiene estructura cuesta abajo real que explotar, de modo que si la regla dará un paso cuesta abajo para escapar de una meseta importa genuinamente. Qué regla de aceptación gana, como qué operador de destrucción gana, depende de lo bueno que ya sea el tablero.
Fijemos el bucle y cambiemos solo lo que ocurre una vez que se estanca. No hacer nada deja a la ejecución triturando la misma cuenca durante el resto del minuto. Un golpe aleatorio, que desplaza y recarga aleatoriamente un par de docenas de celdas cuando el mejor no se ha movido en un rato, y un retorno al mejor tablero hasta el momento, que reataca al titular, son las dos perturbaciones probadas. Ambas caen a un punto del ancla sin reinicio (365 y 365, frente al 366 del ancla). Este es un resultado nulo limpio: atornillar un detector de estancamiento y una perturbación al bucle voraz-desajuste no lo ayuda, porque la perturbación o bien tira la estructura que hacía bueno al tablero (el golpe) o bien retorna a un tablero en el que el mismo operador ya se ha estancado (el retorno). Ninguna convierte el bucle en un evasor de cuencas; sobre este puzzle, escapar de una cuenca requiere un movimiento distinto de perturbar-y-reparar, que es exactamente lo que explican el muro de rigidez y la estructura de σ-ciclos.
Dos temas atraviesan las cinco comparaciones. El primero es que las dos decisiones que mueven la puntuación son el operador de destrucción y la regla de aceptación, y ambas la mueven en la misma dirección contraintuitiva: las elecciones ganadoras son las que mantienen el bucle explorando en lugar de explotando. La destrucción aleatoria supera a todo operador que apunta a las roturas; el recocido, que da un paso cuesta abajo para abandonar una meseta, supera a toda regla que solo se mueve lateralmente o cuesta arriba. Refinar la recarga y atornillar un reinicio, las dos decisiones que intentan ser más ingeniosas acerca de una región en la que el bucle ya está atascado, no aportan nada.
El segundo es por qué explorar gana aquí mientras que fijarse gana sobre un tablero cercano al récord: el bucle de reparación es un explorador de cuencas, no un evasor de cuencas. Sobre un tablero mediocre hay amplia estructura cuesta abajo en todas partes, de modo que los movimientos que cubren más de ella ganan; sobre un tablero cercano al récord no queda ninguna salvo un único ciclo entrelazado, de modo que los movimientos que lo apuntan con precisión ganan. Ninguno de los dos regímenes permite a perturbar-y-reparar escapar de una cuenca una vez que está en una. Por eso los pipelines de construir-y-luego-refinar que alcanzan los mejores tableros de este proyecto dividen el trabajo como lo hacen: un productor constructivo fuerte para elegir una buena cuenca, y la reparación como último kilómetro dentro de ella, nunca requerida a salir de ella.