Resumen Técnico: Comprensión de las Soluciones de Tipo Humano en la Optimización Combinatoria mediante el Aprendizaje y la Búsqueda

1. Planteamiento del Problema

Los problemas de optimización combinatoria, como el Viajante de Todo en Europa Euclídeo (TSP), son computacionalmente difíciles (NP-duros) pero a menudo son resueltos por humanos con una eficiencia casi óptima bajo severas restricciones de tiempo y cognitivas. Mientras que los humanos producen rutinariamente recorridos solo un ~10% más largos que el óptimo matemático, los algoritmos cognitivos específicos y los principios geométricos que subyacen a este rendimiento "de tipo humano" siguen sin estar claros. Los modelos computacionales existentes suelen depender de una búsqueda exhaustiva (computacionalmente costosa) o de heurísticas simples (a menudo subóptimas y que fallan al capturar patrones estructurales humanos). El desafío central es identificar un marco computacional que no solo resuelva el TSP de manera eficiente, sino que también reproduzca las firmas geométricas específicas y las desviaciones sistemáticas características de las soluciones humanas.

2. Metodología

2.1 Recopilación de Datos Conductuales a Gran Escala (tsp150k)

Los autores llevaron a cabo el experimento conductual más grande sobre el rendimiento humano en el TSP hasta la fecha, generando el conjunto de datos tsp150k.

• Participantes: 1.107 participantes.
• Escala: 150.000 instancias únicas de TSP con más de 20 millones de recorridos generados por humanos.
• Niveles de Complejidad: Cinco niveles basados en el número de ciudades: 10, 12, 15, 19 y 24 ciudades.
• Protocolo: Los participantes resolvieron instancias de TSP en línea a través de una plataforma integrada con WeChat. Los límites de tiempo se fijaron en el doble del número de ciudades (por ejemplo, 20s para 10 ciudades). No se proporcionó retroalimentación sobre la longitud del recorrido durante la tarea.
• Densidad de Datos: Cada instancia recibió entre 92 y 207 recorridos humanos (promedio de 139), lo que permite una caracterización estadística robusta del comportamiento humano.

2.2 Marco de Modelado Computacional

El estudio evaluó un amplio espacio de hipótesis de modelos, categorizados en métodos de solo búsqueda y métodos híbridos de aprendizaje y búsqueda.

• Líneas Base de Solo Búsqueda:

  • Exactos: Concorde (branch-and-cut) para soluciones óptimas.
  • Heurísticas: Vecino Más Cercano (Nearest Neighbor), Inserción más Barata en el Casco Convexo (Convex Hull Cheapest Insertion), Ángulo Interior Máximo (Largest Interior Angle).
  • Relajación: Red Elástica (Elastic Net) (descenso de gradiente sobre un anillo deformable).

• Modelos de Redes Neuronales (Redes de Punteros/Pointer Networks):
  Los autores utilizaron Redes de Punteros (RNNs con mecanismos de puntero basados en atención) para definir distribuciones de probabilidad sobre recorridos válidos. Se probaron cuatro regímenes de entrenamiento distintos:

  1. $p_{optimal}$: Aprendizaje supervisado sobre recorridos óptimos (soluciones de Concorde).
  2. $p_{RL}$: Aprendizaje por Refuerzo (RL) utilizando la longitud negativa del recorrido euclídeo como recompensa.
  3. $p_{optimal+RL}$: Preentrenamiento supervisado en recorridos óptimos seguido de un ajuste fino con RL.
  4. $p_{human}$: Aprendizaje supervisado directamente sobre recorridos humanos (sirviendo como un límite superior empírico).

• Estrategias de Decodificación:
  Para generar recorridos a partir de las políticas entrenadas, se aplicaron tres estrategias de búsqueda:

  1. Decodificación Codiciosa (Greedy Decoding): Selección miope de la siguiente ciudad más probable.
  2. Búsqueda de Haz (Beam Search): Aproximación heurística de la secuencia completa más probable.
  3. Muestreo Best-of-$N$: Muestreo aleatorio de $N$ recorridos completos y selección del más corto.

2.3 Métricas de Evaluación

El rendimiento del modelo se evaluó en un conjunto de prueba reservado (50.000 instancias) utilizando cinco métricas de similitud por pares que comparan los recorridos del modelo con los humanos:

1. Ratio de Solapamiento de Aristas (EOR): Proporción de aristas compartidas.
2. Subcadena Común Más Larga (LCS): Longitud de la secuencia consecutiva de ciudades compartidas más larga.
3. Distancia de Levenshtein (LD): Mínimo de ediciones para transformar un recorrido en otro.
4. Distancia de Fréchet (FD): Separación espacial entre puntos correspondientes en el orden de recorrido.
5. $\tau$ de Kendall: Correlación de rango en los órdenes de visita.

• Análisis Geométrico: Se extrajeron ocho características geométricas específicas (por ejemplo, suavidad, entropía del ángulo de giro, preservación del casco convexo, optimalidad 2-opt) para caracterizar el "cuenco geométrico" de las soluciones humanas.

3. Resultados Clave

3.1 Características del Rendimiento Humano

• Los recorridos humanos son casi óptimos pero exhiben desviaciones sistemáticas, ocupando un "cuenco geométrico casi óptimo".
• Los humanos pasan significamente más tiempo deliberando en la posición inicial, lo que sugiere una estrategia de "pensar y luego implementar".
• Después de ignorar las ciudades previamente visitadas, las elecciones de la siguiente ciudad por parte de los humanos se estabilizan en un alto nivel de optimalidad local.

3.2 Comparación de Rendimiento de Modelos

• Modelos de Solo Búsqueda: Los recorridos óptimos (Concorde) y la Red Elástica superaron a las heurísticas simples y a una línea base humana aleatoria, logrando una alta similitud con los recorridos humanos. Sin embargo, no lograron capturar las firmas específicas de sub-optimalidad humana (por ejemplo, menor suavidad y menor preservación del casco convexo que el óptimo matemático).
• Aprendizaje Supervisado Puro ($p_{human}$): El modelo entrenado directamente en recorridos humanos con Búsqueda de Haz logró la mayor alineación general (Puntuación Agregada: 0.600), estableciendo el límite superior empírico.
• El Mejor Modelo Generalizable ($p_{optimal+RL}$): Entre los modelos no entrenados con datos humanos, el PointerNet preentrenado en recorridos óptimos y ajustado con RL, decodificado mediante muestreo Best-of-$N$ ($N=100$), logró la mayor similitud con los humanos (Puntuación Agregada: 0.600).
  • Este modelo coincidió estrechamente con las características geométricas de los recorridos humanos (Pearson's $r = 0.583$ a través de ocho características) y logró el Error Absoluto Medio más bajo (MAE = 0.021).
  • Reprodujo con éxito la sub-optimalidad característica de los humanos (por ejemplo, la no perfecta preservación del casco convexo) que los resolvedores puramente óptimos pasaron por alto.

3.3 Análisis del Cuenco Geométrico

• Los recorridos humanos son distintos de los recorridos puramente óptimos; exhiben menor suavidad y una menor optimalidad local 2-opt.
• Los modelos $p_{optimal}$ convergen demasiado rápido a la región geométrica óptima, perdiendo las desviaciones humanas.
• Los modelos $p_{RL}$ se concentran demasiado en un conjunto estrecho de recorridos de alta recompensa, careciendo de la diversidad necesaria para que la búsqueda en tiempo de prueba encuentre variaciones similares a las humanas.
• $p_{optimal+RL}$ logra un equilibrio: el preentrenamiento supervisado proporciona un soporte amplio para recorridos geométricamente casi óptimos, mientras que el ajuste fino con RL sesga la distribución hacia caminos más cortos sin eliminar la diversidad. Esto permite que el muestreo Best-of-$N$ converja a una región que se alinea con el comportamiento humano.

4. Contribuciones Clave

1. Conjunto de Datos tsp150k: La creación de un conjunto de datos masivo y de alta calidad que comprende 150.000 instancias de TSP y más de 20 millones de recorridos humanos, permitiendo la caracterización sistemática del comportamiento humano.
2. Identificación de Mecanismos de Tipo Humano: Demostrar que las soluciones de tipo humano no son meras imitaciones de recorridos óptimos, sino que emergen de una combinación específica de aprendizaje supervisado estructurado (adquisición de conocimiento geométrico), aprendizaje por refuerzo (optimización de la eficiencia) y búsqueda en tiempo de prueba (muestreo Best-of-$N$).
3. Caracterización Geométrica: Definir un "cuenco geométrico" para las soluciones humanas, mostrando que los humanos comparten propiedades estructurales con las soluciones óptimas mientras preservan desviaciones sistemáticas (por ejemplo, en suavidad y preservación del casco convexo) que las heurísticas estándar y los resolvedores puramente óptimos no logran capturar.
4. Marco de Modelado Cognitivo: Proponer que la resolución de problemas humanos en espacios combinatorios puede modelarse como un proceso de dos etapas: la adquisición de conocimiento estructural a partir de ejemplos de alta calidad (imitación) y el refinamiento mediante retroalimentación (RL), seguido de la deliberación (búsqueda) en el tiempo de ejecución.

5. Significado y Reivindicaciones

El artículo sostiene que el rendimiento de tipo humano en la optimización combinatoria no surge de heurísticas fijas y diseñadas a mano, sino de una arquitectura computacional que integra el aprendizaje y la búsqueda. Específicamente:

• Sinergia Aprendizaje-Búsqueda: El modelo más preciso del comportamiento humano no es una imitación directa de los datos humanos, sino un modelo entrenado en datos óptimos, refinado por RL y decodificado con búsqueda. Esto sugiere que los humanos pueden adquirir un conocimiento geométrico amplio a través de la exposición a ejemplos de alta calidad y refinar estas representaciones mediante la retroalimentación basada en la experiencia.
• Papel del Cómputo en Tiempo de Prueba: El estudio destaca que el "cómputo en tiempo de prueba" (por ejemplo, el muestreo Best-of-$N$) es un componente crítico y a menudo pasado por alto en el modelado cognitivo. Permite que una red neuronal estática genere la variabilidad de tipo humano en la calidad de las soluciones sin modificar sus pesos, paralelamente a mecanismos como el razonamiento de cadena de pensamiento (chain-of-thought) en los grandes modelos de lenguaje.
• Generalizabilidad: Los hallazgos sugieren que la "lección amarga" de la IA —depender del aprendizaje y la computación en lugar de heurísticas fijas— se aplica a la cognición humana. Las soluciones humanas a problemas complejos pueden reflejar un análogo cognitivo de métodos de propósito general que aprenden de la experiencia y explotan la computación a través de la búsqueda.

Los autores señalan modestamente que, aunque su modelo reproduce las geometrías humanas sin entrenamiento directo en recoros humanos, la fuente de las "demostraciones óptimas" para el aprendizaje supervisado humano sigue siendo una cuestión abierta, involucrando potencialmente el aprendizaje por currículo a partir de instancias más simples.