Resumo Técnico: CoEvo-AHD para Otimização Combinatória Acoplada Bi-Componente

1. Definição do Problema

O artigo aborda problemas de Otimização Combinatória (CO) Acoplada Bi-Componente, onde uma solução consiste em dois componentes de decisão semanticamente distintos, mas interdependentes. O desafio central é que a viabilidade ou o valor objetivo de modificar um componente depende inteiramente do estado do outro. Consequentemente, a utilidade de um operador é relacional em vez de intrínseca; um operador que performa bem isoladamente pode degradar a solução global quando acoplado a um estado suboptimal do segundo componente.

Os autores instanciam este framework em dois problemas representativos:

• Traveling Thief Problem (TTP): Acopla roteamento (Problema do Caixeiro Viajante) com empacotamento (Problema da Mochila 0–1). A ordem do percurso afeta a velocidade de viagem com base na carga transportada, enquanto o plano de empacotamento determina o peso carregado em cada etapa.
• Traveling Purchaser Problem (TPP): Acopla seleção de mercado/roteamento com decisões de compra. A ordem de visita e a seleção de mercados determinam as opções de compra e custos viáveis, enquanto as decisões de compra influenciam o valor de visitar mercados específicos.

Métodos existentes de Design Automatizado de Heurísticas (AHD) impulsionados por Grandes Modelos de Linguagem (LLM) tipicamente evoluem heurísticas como unidades algorítmicas isoladas ou estratégias de busca (ex: construção vs. reparo). Esses métodos falham em capturar a complementaridade induzida pela estrutura do problema necessária para problemas bi-componentes acoplados, onde os operadores devem ser co-evoluídos para funcionar sinergicamente através de componentes de solução heterogêneos.

2. Metodologia: CoEvo-AHD

Os autores propõem o CoEvo-AHD, um framework de co-evolução de população dupla impulsionado por LLM, projetado para descobrir e refinar automaticamente pares de operadores de componentes. O framework opera através de quatro estágios:

2.1 Inicialização de População Dupla

Duas populações de operadores separadas são mantidas: $P_A$ para o componente A (ex: operadores de rota) e $P_B$ para o componente B (ex: operadores de empacotamento).

• Inicialização: As populações começam com uma mistura de operadores semente especificados manualmente e operadores gerados por LLM.
• Validação: Todos os operadores gerados passam por validação de sintaxe, interface, execução limitada e viabilidade de componente antes de entrarem na população.
• Interface: Os operadores retornam atualizações candidatas apenas para seu componente específico, dependendo de uma memória de informação compartilhada e ferramentas externas para contexto global.

2.2 Avaliação Cooperativa

Ao contrário dos métodos tradicionais que pontuam operadores isoladamente, o CoEvo-AHD avalia operadores através de execução pareada em soluções completas.

• Seleção: Uma estratégia de Thompson Sampling local seleciona um operador de $P_A$ e um de $P_B$ para cada reinício de busca.
• Otimização Alternada: O par selecionado é invocado alternadamente dentro de uma trajetória de busca. Por exemplo, um operador de rota propõe uma permutação de cidades, que é então passada para um operador de empacotamento (ou vice-versa).
• Reparo e Reconstrução: Como os componentes são acoplados, candidatos intermediários podem ser inviáveis. O framework utiliza um ambiente de problema aumentado por ferramentas para realizar reparo de viabilidade, reconstrução e avaliação do objetivo completo.
• Informação Compartilhada: Um dicionário mutável (shared_info) permite que os operadores troquem sinais de busca suaves (ex: perfis de carga, pistas de inserção de candidatos) sem sobrescrever diretamente a lógica do outro componente.

2.3 Gestão e Evolução da População

O framework emprega um loop de co-evolução para refinar as populações:

• Pontuação: As recompensas são computadas com base na melhoria da solução acoplada completa. Essas recompensas atualizam três estatísticas: pontuações individuais para $o_A$ e $o_B$, e uma pontuação de sinergia pareada ($S_{ij}$) para o par de operadores específico.
• Poda: Operadores de baixo desempenho são removidos de suas respectivas populações.
• Evolução Impulsionada por LLM: As lacunas são preenchidas via três operações evolutivas:
  1. Mutação Intra-componente: Refina um único operador pai.
  2. Crossover Homogêneo Intra-componente: Recombina dois operadores da mesma população.
  3. Crossover Conjunto Cross-Componente: Seleciona o par de melhor desempenho $(o_A^*, o_B^*)$ baseado em pontuações de sinergia e solicita ao LLM que os reescreva como uma entidade unificada e coordenada. Isso incentiva a geração de operadores com protocolos de comunicação compatíveis e suposições de busca complementares.

2.4 Ambiente Aumentado por Ferramentas

Para evitar que os LLMs gerem código de baixo nível ineficiente ou propenso a erros, o framework encapsula operações principais (ex: computação de delta de busca local, reconstrução gulosa, verificações de viabilidade) em ferramentas padronizadas e chamáveis. Isso permite que os operadores gerados por LLM foquem no design de vizinhança de alto nível e na coordenação entre componentes.

3. Principais Contribuições

1. Formulação do Problema: O artigo formula o AHD impulsionado por LLM especificamente para CO acoplada bi-componente, definindo a utilidade do operador como relacional e necessitando de avaliação conjunta através de componentes de decisão heterogêneos.
2. Framework CoEvo-AHD: Uma arquitetura de co-evolução inovadora apresentando:
   • Populações de operadores específicas por componente.
   • Avaliação baseada em execução pareada para capturar interações entre componentes.
   • Pontuação de sinergia pareada para guiar a seleção de pares de operadores complementares.
   • Crossover conjunto cross-componente para evoluir operadores mutuamente compatíveis.
3. Comunicação Estruturada e Ferramental: A introdução de um protocolo de comunicação inter-componente estruturado e um ambiente aumentado por ferramentas que padroniza operações específicas do problema, permitindo que os LLMs gerem lógica heurística de alto nível e robusta.

4. Resultados Experimentais

O framework foi avaliado nos benchmarks TTP e TPP contra heurísticas tradicionais de última geração e baselines recentes baseados em LLM.

• Traveling Thief Problem (TTP):

  • O CoEvo-AHD alcançou os melhores resultados em instâncias de pequeno a médio porte (TTP20, TTP50), superando baselines como MATLS, S5 e CoCo.
  • Em instâncias maiores (TTP100, TTP200), alcançou o segundo melhor valor médio geral, ficando atrás apenas do CoCo, mas superando significativamente o MATLS e o S5.
  • Isso sugere que o framework captura efetivamente o acoplamento em espaços de busca menores, mas enfrenta desafios de profundidade de busca em instâncias muito grandes.

• Traveling Purchaser Problem (TPP):

  • O CoEvo-AHD demonstrou uma vantagem geral pronunciada, alcançando os melhores resultados em cinco escalas de instâncias (incluindo escalas grandes como 150×100 e 150×150) e o segundo melhor em outras três.
  • Reduziu o valor objetivo médio em aproximadamente 2,76% em comparação com o segundo melhor baseline (TA) e até 11,42% em comparação ao ALNS.
  • Os resultados indicam que o framework é particularmente eficaz em explorar a sinergia entre decisões de roteamento e de compra no TPP.

• Estudos de Ablação:

  • A remoção da co-evolução de população dupla (evoluindo apenas um componente) causou uma degradação significativa de desempenho (ex: queda de ~11% no TPP), confirmando que otimizar componentes isoladamente é insuficiente.
  • A remoção do ambiente aumentado por ferramentas também levou a quedas de desempenho (~5,5% no TTP), destacando a importância de interfaces padronizadas para confiabilidade e eficiência.

5. Significância e Alegações

O artigo alega que o CoEvo-AHD representa uma mudança no AHD impulsionado por LLM, de gerar papéis algorítmicos isolados para modelar a complementaridade de operadores induzida pela estrutura do problema. Ao co-evoluir explicitamente populações de operadores heterogêneos e avaliá-los através de execução conjunta, o framework aborda a limitação de métodos existentes que não conseguem lidar com o forte acoplamento entre subestruturas de decisão.

Os autores posicionam este trabalho como um passo em direção a um design de heurística automatizado mais generalizável para problemas de otimização complexos do mundo real, onde os componentes da solução são profundamente interdependentes. Eles observam modestamente que, embora o framework seja altamente competitivo, ainda há espaço para melhorias na profundidade de busca e robustez para instâncias de escala muito grande, e trabalhos futuros visarão estender o framework para problemas com mais de dois componentes acoplados.