Resumo Técnico: CoupleEvo

Definição do Problema

Sistemas de otimização do mundo real frequentemente consistem em múltiplos subproblemas fortemente acoplados, onde as soluções devem ser coordenadas para alcançar um desempenho global elevado. Esses problemas acoplados combinam frequentemente dois ou mais subproblemas NP-difíceis, como no Problema de Roteamento de Inventário (IRP) ou no Problema de Pré-estocagem de Unidades de Carga Multi-robô Multi-bay (MR-MUPMP). Embora a otimização de subproblemas isoladamente frequentemente produza resultados globais subótimos, a otimização simultânea totalmente integrada é frequentemente intratável computacionalmente devido ao crescimento combinatório do espaço de soluções conjunto.

As existentes estruturas de design automatizado de heurísticas impulsionadas por Modelos de Linguagem de Grande Escala (LLM) estão atualmente limitadas a configurações de problema único, evoluindo uma única heurística para um único objetivo. Há uma lacuna na literatura quanto ao design sistemático de múltiplas heurísticas interagentes para problemas de otimização acoplados, especificamente carecendo de uma estratégia de coordenação evolutiva para gerenciar as interdependências entre subproblemas.

Metodologia: CoupleEvo

Os autores propõem o CoupleEvo, a primeira estrutura impulsionada por LLM para design automatizado de heurísticas em problemas de otimização acoplados. A estrutura opera dentro de um contexto iterativo de Busca em Grande Vizinhança (LNS), onde o LLM é encarregado de gerar heurísticas de destruição para cada subproblema, enquanto as heurísticas de reparo permanecem determinísticas.

Estratégias de Coordenação Evolutiva

O CoupleEvo introduz três estratégias distintas para governar a busca evolutiva através de subproblemas interdependentes:

1. Evolução Sequencial: As heurísticas são evoluídas para um subproblema após o outro. A evolução do subproblema $k$ prossegue por um número fixo de gerações, enquanto todos os outros subproblemas utilizam suas heurísticas de melhor desempenho atuais (fixas). Isso oferece simplicidade conceitual, mas arrisca convergência prematura, onde a primeira heurística evoluída restringe o espaço de busca para os subproblemas subsequentes.
2. Evolução Iterativa: A evolução alterna entre subproblemas ao longo de múltiplas rodadas de controle. Em cada rodada, o algoritmo percorre todos os subproblemas, refinando suas heurísticas com base nos melhores desempenhos da rodada anterior. Essa estratégia visa prevenir o ajuste excessivo (overfitting) a um único subproblema e mantém a flexibilidade para coordenação.
3. Evolução Integrada: As heurísticas para todos os subproblemas são evoluídas simultaneamente. O LLM é instruído a gerar uma tupla completa de heurística (código e pensamentos para todos os subproblemas) em uma única etapa. Embora isso modele explicitamente as interdependências, aumenta a complexidade da busca e impõe demandas mais altas às capacidades generativas do LLM.

Detalhes de Implementação

• LLM: A estrutura utiliza o modelo de código aberto Qwen3-coder:30b.
• Prompting: O sistema emprega um conjunto de estratégias de prompt adaptadas de trabalhos anteriores (EoH, ReEvo), incluindo prompts de inicialização (I1), exploração (E1, E2) e modificação (M1, M2).
• Avaliação: A aptidão (fitness) é calculada com base no valor objetivo das instâncias do problema acoplado. Para o IRP, a aptidão é a lacuna relativa em relação a uma linha de base HGS de última geração; para o MR-MUPMP, é o valor objetivo médio.
• Configuração Experimental: A estrutura foi testada em dois domínios:
  • IRP: Integrando gestão de inventário e roteamento de veículos.
  • MR-MUPMP: Integrando busca de movimentos (sequenciamento de realocação) e roteamento de veículos com precedências.
  • Todas as estratégias receberam um orçamento evolutivo igual (40 gerações no total) para garantir comparação justa.

Contribuições Principais

1. Estrutura CoupleEvo: A formulação da primeira estrutura impulsionada por LLM que estende o design automatizado de heurísticas de configurações de problema único para problemas de otimização acoplados com múltiplos subproblemas NP-difíceis interdependentes.
2. Estratégias Evolutivas: A proposta e investigação sistemática de três estratégias de coordenação (Sequencial, Iterativa, Integrada) que definem como as heurísticas para subproblemas interagentes são geradas e refinadas.
3. Avaliação Abrangente: Avaliação experimental extensa em dois domínios representativos de otimização acoplada, fornecendo insights empíricos sobre os trade-offs entre estabilidade de convergência, complexidade de busca e qualidade da solução.

Resultados Experimentais

O estudo avaliou as três estratégias em 6 execuções por estratégia para ambos IRP e MR-MUPMP.

• Decomposição vs. Integração: Estratégias baseadas em decomposição (Sequencial e Iterativa) demonstraram consistentemente convergência mais estável e maior qualidade de solução em comparação com a estratégia Integrada.
• Estratégia Sequencial: Exhibiu melhoria rápida de aptidão inicial ao evoluir o primeiro subproblema. No entanto, a convergência frequentemente desacelerou ou estagnou ao mudar para o segundo subproblema, sugerindo que a primeira heurística evoluída restringiu o espaço de busca. Alcançou o melhor desempenho médio para MR-MUPMP.
• Estratégia Iterativa: Mostrou uma trajetória mais gradual, mas consistentemente crescente. Ao alternar o foco, mitigou o ajuste excessivo prematuro e manteve a adaptabilidade. Alcançou os melhores valores mínimos e medianos de aptidão para MR-MUPMP e os resultados mais estáveis (menor amplitude) para IRP.
• Estratégia Integrada: Sofreu com o aumento da complexidade de busca e alta variabilidade. Embora algumas execuções tenham alcançado resultados competitivos, a estratégia geralmente exibiu desempenho mais fraco e variância maior, indicando dificuldade em refinar consistentemente tuplas de heurísticas de alta qualidade para problemas acoplados.

Benchmarking

As heurísticas evoluídas de melhor desempenho (CoupleLNS) foram comparadas contra a literatura estabelecida:

• IRP: O CoupleLNS superou metaheurísticas clássicas (MH) em uma média de 5,61%. Alcançou resultados competitivos contra a Busca Genética Híbrida (HGS) de última geração, com uma lacuna média de 2,96%, sem depender de extensa engenharia específica do problema.
• MR-MUPMP: Comparado a uma abordagem sequencial baseada em etapas (SBS) usando A* ótimo, o CoupleLNS teve qualidade de solução ligeiramente inferior em instâncias solucionáveis, mas resolveu com sucesso todas as instâncias dentro do limite de tempo, enquanto o SBS falhou em algumas. Quando comparado a um SBS* adaptado (usando uma heurística guiada por LLM), o CoupleLNS o superou em uma média de 5,01%.

Significado e Afirmações

O artigo afirma que o CoupleEvo demonstra o potencial do design automatizado de heurísticas impulsionado por LLM para problemas complexos de otimização acoplada. A descoberta primária é que coordenar a busca evolutiva através de subproblemas interdependentes é crítico; estratégias baseadas em decomposição (sequencial e iterativa) são atualmente mais eficazes do que a evolução integrada para esses tipos específicos de problemas.

Os autores posicionam seu trabalho não como um substituto para métodos clássicos, mas como uma abordagem complementar. Eles sugerem que métodos baseados em LLM podem evoluir componentes de heurística altamente ajustados e específicos do problema que aprimoram estruturas existentes como o LNS. O trabalho destaca que, embora a evolução integrada seja teoricamente atraente para capturar interações entre componentes, as capacidades atuais de LLM e a complexidade de busca favorecem estratégias que decompõem o problema enquanto mantêm coordenação iterativa.

As direções de pesquisa futura identificadas pelos autores incluem adaptar a estrutura para problemas com mais de dois subproblemas, melhorar a estabilidade da estratégia integrada e desenvolver estratégias de coordenação adaptativas que alternam dinamicamente entre problemas de otimização.