MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design

Imagine que você está tentando resolver um quebra-cabeça enorme e bagunçado, como organizar a rota de entrega de um caminhão com centenas de paradas ou arrumar uma mala com os itens mais valiosos possíveis. Estes são "problemas de otimização combinatória", e eles são notoriamente difíceis porque o número de maneiras possíveis de organizar as peças é tão grande que nem mesmo os supercomputadores mais rápidos conseguem verificar todas elas. Por décadas, os seres humanos tentaram escrever "regras de bolso" especiais (chamadas heurísticas) para resolver esses quebra-cabeças rapidamente. Mas aqui está a pegadinha: uma regra que funciona perfeitamente para uma cidade com um layout de ruas em grade pode falhar miseravelmente em uma cidade com estradas sinuosas e circulares. Esta é a realidade do "No Free Lunch" (Não Existe Almoço Grátis): não existe uma única regra mágica que funcione para todas as situações.

Recentemente, cientistas começaram a usar "Grandes Modelos de Linguagem" (LLMs) — o mesmo tipo de IA que escreve histórias e responde perguntas — para inventar essas regras automaticamente. No entanto, a maioria desses experimentos de IA era como treinar um aluno usando apenas um único livro didático pequeno. A IA ficaria muito boa em resolver os problemas daquele livro específico, mas se você lhe desse um quebra-cabeça ligeiramente diferente, ela ficaria confusa. Era como ensinar um chef a fazer uma omelete perfeita, mas usando apenas ovos de uma fazenda específica; se você desse a ele ovos de uma fazenda diferente, a omelete poderia desmoronar. A forma antiga de treinar essas IAs também dependia de um feedback muito simples, como um professor apenas dizendo "Bom trabalho" ou "Mau trabalho", sem explicar por que ou onde ocorreu o erro.

Apresentamos o MOSAIC, um novo framework desenvolvido por pesquisadores do Georgia Institute of Technology. Pense no MOSAIC não como um único aluno tentando memorizar um livro didático, mas como uma biblioteca massiva e viva onde diferentes regras de "especialistas" são treinadas para diferentes tipos de quebra-cabeças. Em vez de apenas pedir a uma IA para "criar uma regra melhor", o MOSAIC estabelece um jogo de gato e rato de alto risco. Ele coloca as regras atuais da IA contra uma equipe de criadores de quebra-cabeças "adversários". Esses criadores de quebra-cabeças também são IA, e o único trabalho deles é criar os quebra-cabeças mais difíceis e confusos, especificamente projetados para quebrar as regras atuais. Quando uma regra falha, o sistema não diz apenas "você perdeu". Ele usa uma árvore de decisão inteligente para descobrir exatamente que tipo de quebra-cabeça quebrou a regra e, então, armazena esse quebra-cabeça e a lição aprendida em uma "célula" específica de uma grade gigante. Com o tempo, essa grade se preenche com uma coleção diversa de especialistas: uma regra para cidades em grade, outra para bairros agrupados, outra para rotas longas e sinuosas. O sistema então usa essas lições armazenadas para evoluir regras ainda melhores, criando uma equipe de especialistas onde cada um é mestre de seu próprio território específico.

Os pesquisadores testaram essa ideia em três problemas clássicos: o Problema do Caixeiro Viajante (encontrar a rota mais curta), o Problema da Mochila (empacotar o maior valor possível) e o Problema de Roteamento de Veículos Capacitados (entregar mercadorias com espaço limitado no caminhão). Eles descobriram que o MOSAIC superou consistentemente outros métodos de IA de última geração. Enquanto outros métodos tinham dificuldades quando os quebra-cabeças mudavam ligeiramente, o "time de especialistas" do MOSAIC lidava com as mudanças com facilidade, muitas vezes encontrando soluções que eram significativamente mais próximas da resposta perfeita. Por exemplo, no Problema do Caixeiro Viajante, a melhor equipe de regras do MOSAIC foi até 22% mais precisa do que o próximo melhor método.

Talvez ainda mais emocionante seja o fato de que os quebra-cabeças "adversários" criados pelo MOSAIC foram muito mais diversos e desafiadores do que os criados pelos métodos tradicionais. O sistema conseguiu cobrir 33% mais do "espaço de características" (os diferentes tipos de estruturas de quebra-cabeças) do que os métodos anteriores, o que significa que aprendeu a lidar com uma variedade muito maior de cenários do mundo real. O estudo sugere que, ao tratar o problema como uma batalha de coevolução — onde os quebra-cabeças ficam mais difíceis para expor fraquezas, e as regras ficam mais inteligentes para corrigi-las — podemos construir uma IA que não apenas memoriza alguns exemplos, mas que realmente entende o cenário do problema. É uma mudança de treinar um gênio único que sabe tudo sobre uma coisa, para construir uma comunidade diversa de especialistas que sabem um pouco sobre tudo, e muito sobre seu próprio canto do mundo.