Resumo Técnico: Compreendendo Soluções de Aparência Humana em Otimização Combinatória via Aprendizado e Busca

1. Definição do Problema

Problemas de otimização combinatória, como o Problema do Caixeiro Viajante (TSP) Euclidiano, são computacionalmente difíceis (NP-difíceis), mas frequentemente resolvidos por humanos com eficiência próxima à ótima sob severas restrições de tempo e cognitivas. Embora os humanos produzam rotas rotineiramente apenas ~10% mais longas que o ótimo matemático, os algoritmos cognitivos específicos e os princípios geométricos que fundamentam esse desempenho "semelhante ao humano" permanecem obscuros. Modelos computacionais existentes dependem frequentemente de busca exaustiva (computacionalmente cara) ou de heurísticas simples (muitas vezes subótimas e falhando em capturar padrões estruturais humanos). O desafio central é identificar um framework computacional que não apenas resolva o TSP de forma eficiente, mas que também reproduza as assinaturas geométricas específicas e as desvios sistemáticos característicos das soluções humanas.

2. Metodologia

2.1 Coleta de Dados Comportamentais em Larga Escala (tsp150k)

Os autores conduziram o maior experimento comportamental sobre o desempenho humano no TSP até o momento, gerando o dataset tsp150k.

• Participantes: 1.107 participantes.
• Escala: 150.000 instâncias únicas de TSP com mais de 20 milhões de rotas geradas por humanos.
• Níveis de Complexidade: Cinco níveis baseados no número de cidades: 10, 12, 15, 19 e 24 cidades.
• Protocolo: Os participantes resolveram instâncias de TSP online via uma plataforma integrada ao WeChat. Limites de tempo foram definidos como o dobro do número de cidades (ex: 20s para 10 cidades). Nenção de feedback sobre o comprimento da rota foi fornecida durante a tarefa.
• Densidade de Dados: Cada instância recebeu entre 92 e 207 rotas humanas (média de 139), permitindo uma caracterização estatística robusta do comportamento humano.

2.2 Framework de Modelagem Computacional

O estudo avaliou um amplo espaço de hipóteses de modelos computacionais, categorizados em métodos de apenas busca e métodos híbridos de aprendizado e busca.

• Baselines de Apenas Busca:

  • Exato: Concorde (branch-and-cut) para soluções ótimas.
  • Heurísticas: Vizinho Mais Próximo (Nearest Neighbor), Inserção de Casco Convexo Mais Barata (Convex Hull Cheapest Insertion), Maior Ângulo Interior (Largest Interior Angle).
  • Relaxação: Rede Elástica (Elastic Net - gradiente descendente em um anel deformável).

• Modelos de Redes Neurais (Pointer Networks):
  Os autores utilizaram Pointer Networks (RNNs com mecanismos de atenção para apontamento) para definir distribuições de probabilidade sobre rotas válidas. Quatro regimes de treinamento distintos foram testados:

  1. $p_{optimal}$: Aprendizado supervisionado em rotas ótimas (soluções do Concorde).
  2. $p_{RL}$: Aprendizado por Reforço (RL) usando o comprimento negativo da rota euclidiana como recompensa.
  3. $p_{optimal+RL}$: Pré-treinamento supervisionado em rotas ótimas seguido de ajuste fino (fine-tuning) via RL.
  4. $p_{human}$: Aprendizado supervisionado diretamente em rotas humanas (servindo como um limite superior empírico).

• Estratégias de Decodificação:
  Para gerar rotas a partir das políticas treinadas, três estratégias de busca foram aplicadas:

  1. Decodificação Gananciosa (Greedy Decoding): Seleção míope da cidade mais provável seguinte.
  2. Busca em Feixe (Beam Search): Aproximação heurística da sequência completa mais provável.
  3. Amostragem Best-of-N: Amostragem aleatória de $N$ rotas completas e seleção da mais curta.

2.3 Métricas de Avaliação

O desempenho dos modelos foi avaliado em um conjunto de teste retido (50.000 instâncias) usando cinco métricas de similaridade pareadas comparando as rotas do modelo com as rotas humanas:

1. Razão de Sobreposição de Arestas (EOR): Proporção de arestas compartilhadas.
2. Maior Substring Comum (LCS): Comprimento da maior sequência consecutiva de cidades compartilhada.
3. Distância de Levenshtein (LD): Mínimo de edições para transformar uma rota em outra.
4. Distância de Fréchet (FD): Separação espacial entre pontos correspondentes na ordem de travessia.
5. $\tau$ de Kendall: Correlação de rank nas ordens de visitação.

• Análise Geométrica: Oito características geométricas específicas (ex: suavidade, entropia de ângulo de curva, preservação do casco convexo, otimalidade 2-opt) foram extraídas para caracterizar o "balde geométrico" das soluções humanas.

3. Principais Resultados

3.1 Características do Desempenho Humano

• As rotas humanas são próximas do ótimo, mas exibem desvios sistemáticos, ocupando um "balde geométrico próximo ao ótimo".
• Humanos gastam significativamente mais tempo deliberando na posição inicial, sugerindo uma estratégia de "pensar-então-implementar".
• Após ignorar cidades já visitadas, as escolhas humanas da próxima cidade estabilizam em um alto nível de otimalidade local.

3.2 Comparação de Desempenho dos Modelos

• Modelos de Apenas Busca: Rotas ótimas (Concorde) e a Rede Elástica superaram heurísticas simples e um baseline humano aleatório, alcançando alta similaridade com as rotas humanas. No entanto, falharam em capturar assinaturas específicas de subotimalidade humana (ex: menor suavidade e preservação mais fraca do casco convexo do que o ótimo matemático).
• Aprendizado Puramente Supervisionado ($p_{human}$): O modelo treinado diretamente em rotas humanas com Beam Search alcançou o maior alinhamento geral (Pontuação Agregada: 0,600), estabelecendo o limite superior empírico.
• O Melhor Modelo Generalizável ($p_{optimal+RL}$): Entre os modelos não treinados em dados humanos, o PointerNet pré-treinado em rotas ótimas e ajustado via RL, decodificado via amostragem Best-of-N ($N=100$), alcançou a maior semelhança humana (Pontuação Agregada: 0,600).
  • Este modelo correspondeu de perto às características geométricas das rotas humanas (Pearson's $r = 0,583$ através de oito características) e alcançou o menor Erro Médio Absoluto (MAE = 0,021).
  • Ele reproduziu com sucesso a subotimalidade característica humana (ex: preservação de casco convexo não perfeita) que os solvers puramente ótimos perderam.

3.3 Análise do Balde Geométrico

• As rotas humanas são distintas das rotas puramente ótimas; elas exibem menor suavidade e menor otimalidade local 2-opt.
• Modelos $p_{optimal}$ convergem rápido demais para a região geométrica ótima, perdendo os desvios humanos.
• Modelos $p_{RL}$ tornam-se excessivamente concentrados em um conjunto estreito de rotas de alta recompensa, carecendo da diversidade necessária para que a busca em tempo de teste encontre variações semelhantes às humanas.
• $p_{optimal+RL}$ estabelece um equilíbrio: o pré-treinamento supervisionado fornece suporte amplo para rotas geometricamente próximas do ótimo, enquanto o ajuste fino por RL enviesa a distribuição para caminhos mais curtos sem eliminar a diversidade. Isso permite que a amostragem Best-of-N converja para uma região que se alinha com o comportamento humano.

4. Principais Contribuições

1. Dataset tsp150k: A criação de um dataset massivo e de alta qualidade contendo 150.000 instâncias de TSP e mais de 20 milhões de rotas humanas, permitindo a caracterização sistemática do comportamento humano.
2. Identificação de Mecanismos Semelhantes aos Humanos: Demonstração de que soluções de aparência humana não são meras imitações de rotas ótimas, mas emergem de uma combinação específica de aprendizado supervisionado estruturado (aquisição de conhecimento geométrico), aprendizado por reforço (otimização para eficiência) e busca em tempo de teste (amostragem Best-of-N).
3. Caracterização Geométrica: Definição de um "balde geométrico" para soluções humanas, mostrando que humanos compartilham propriedades estruturais com soluções ótimas enquanto preservam desvios sistemáticos (ex: em suavidade e preservação de casco convexo) que heurísticas padrão e solvers puramente ótimos falham em capturar.
4. Framework de Modelagem Cognitiva: Proposição de que a resolução de problemas humanos em espaços combinatórios pode ser modelada como um processo de dois estágios: aquisição de conhecimento estrutural a partir de exemplos de alta qualidade (imitação) e refinamento via feedback (RL), seguido de deliberação (busca) em tempo de teste.

5. Significância e Alegações

O artigo afirma que o desempenho semelhante ao humano em otimização combinatória não surge de heurísticas fixas e manuais, mas de uma arquitetura computacional que integra aprendizado e busca. Especificamente:

• Sinergia Aprendizado-Busca: O modelo mais preciso do comportamento humano não é uma imitação direta de dados humanos, mas um modelo treinado em dados ótimos, refinado por RL e decodificado com busca. Isso sugere que humanos podem adquirir amplo conhecimento geométrico através da exposição a exemplos de alta qualidade e refinar essas representações através de feedback baseado em experiência.
• Papel do Computo em Tempo de Teste: O estudo destaca que o "computo em tempo de teste" (ex: amostragem Best-of-N) é um componente crítico, frequentemente negligenciado, na modelagem cognitiva. Ele permite que uma rede neural estática gere variabilidade semelhante à humana na qualidade da solução sem modificar seus pesos, paralelamente a mecanismos como o raciocínio de cadeia de pensamento (chain-of-thought) em grandes modelos de linguagem.
• Generalização: As descobertas sugerem que a "lição amarga" (bitter lesson) da IA — confiar em aprendizado e computação em vez de heurísticas fixas — aplica-se à cognição humana. As soluções humanas para problemas complexos podem refletir um análogo cognitivo de métodos de propósito geral que aprendem com a experiência e exploram o computo através da busca.

Os autores observam modestamente que, embora seu modelo reproduza geometrias humanas sem treinamento direto em rotas humanas, a origem das "demonstrações ótimas" para o aprendizado supervisionado humano permanece uma questão aberta, possivelmente envolvendo aprendizado de currículo a partir de instâncias mais simples.