A New Meta-Heuristic for Improving General Multi-Start Procedures

No mundo da otimização, cientistas e engenheiros frequentemente enfrentam um problema que parece simples, mas esconde um labirinto de possibilidades: como posicionar um conjunto de instalações, como armazéns ou torres de celular, para atender uma população dispersa da forma mais eficiente possível. O objetivo é minimizar a distância total que as pessoas devem percorrer para chegar à instalação mais próxima. Isso é conhecido como o problema p-mediana. Como o cenário de soluções possíveis é vasto e irregular, repleto de inúmeros picos locais que parecem ser a melhor resposta, mas que são apenas armadilhas, os pesquisadores dependem de uma estratégia chamada procedimento de multi-início (multi-start). Imagine tentar encontrar o ponto mais alto em uma cadeia de montanhas com neblina, deixando um trilheiro ser solto em um ponto aleatório, permitindo que ele suba até que não consiga mais subir, e então repetindo esse processo milhares de vezes a partir de diferentes pontos de partida. O melhor pico encontrado entre todas essas tentativas é geralmente a resposta. No entanto, mesmo com milhares de tentativas, os trilheiros podem perder o verdadeiro cume porque o terreno é tão complexo.

Dois pesquisadores, Zvi Drezner e Jack Brimberg, propuseram um novo método para ajudar esses trilheiros digitais a encontrar melhores picos sem a necessidade de gastar significativamente mais tempo na busca. Eles chamam essa nova técnica de POST. Em vez de apenas executar a busca milhares de vezes e escolher o único melhor resultado, o POST pega os melhores resultados de um lote de buscas e os utiliza para criar novos pontos de partida híbridos. É um pouco como pegar os traços mais fortes dos melhores trilheiros e combiná-los para criar um novo guia que começa a subida a partir de um local mais promissor. Os pesquisadores testaram este método em quarenta e oito cenários diferentes envolvendo até dez mil pontos de demanda e cem instalações. Eles descobriram que essa nova abordagem melhorou consistentemente as melhores soluções conhecidas para cada um dos casos de teste, encontrando respostas melhores no mesmo tempo aproximado que levaria para realizar a busca padrão.

O cerne do desafio reside na própria natureza do problema. Quando se tenta posicionar instalações em um plano plano para atender a um grupo de pontos, o cenário matemático é incrivelmente acidentado. Ele contém milhões de ótimos locais, que são soluções melhores que seus vizinhos imediatos, mas não as melhores no geral. Algoritmos padrão frequentemente ficam presos nesses picos locais. A maneira tradicional de superar isso é simplesmente executar o algoritmo de busca muitas vezes, partindo de locais aleatórios, esperando que um desses inícios aleatórios caia perto o suficiente do verdadeiro ótimo global para permitir que o algoritmo suba. Os pesquisadores utilizaram um poderoso algoritmo de melhoria chamado CLUST, que é atualmente uma das ferramentas mais eficazes para este trabalho, e o executaram a partir de oitenta mil pontos de partida diferentes em seus testes iniciais.

A inovação no POST é o que acontece após essas execuções iniciais. Em vez de parar assim que o melhor resultado é encontrado, os pesquisadores pegam as cinco melhores soluções distintas de um lote menor de execuções e as tratam como "pais". Eles então criam novas soluções "filhas" misturando as localizações das instalações desses pais. Para fazer isso, eles desenham uma linha imaginária através do centro do grupo combinado de instalações. As instalações do primeiro pai que estão de um lado da linha são emparelhadas com as instalações do segundo pai que estão do outro lado. Isso cria uma nova configuração que herda as forças de ambos os pais. Os pesquisadores geram várias dessas novas configurações, executam o algoritmo de melhoria nelas e veem se elas levam a soluções ainda melhores. Se o fizerem, o processo se repete, usando as novas melhores soluções como os pais para a próxima rodada de mistura.

Este ciclo de mistura e melhoria é repetido em vários lotes. Os pesquisadores testaram diferentes maneiras de organizar esses lotes. Em uma configuração, eles executaram a busca inicial mil vezes, pegaram os cinco melhores resultados, misturaram-nos e repetiram todo este ciclo setenta vezes. Em outra, executaram a busca dez mil vezes e repetiram o ciclo oito vezes. Em uma terceira, executaram as oitenta mil vezes completas em um único lote. Os resultados mostraram um padrão claro: dividir a busca em lotes menores e refinar repetidamente os melhores resultados encontrados em cada lote produziu resultados melhores do que executar a busca completa de uma só vez. O método que executou mil buscas iniciais e repetiu o ciclo de refinamento setenta vezes produziu as melhorias mais consistentes, encontrando soluções melhores do que qualquer método anterior para todos os quarenta e oito casos de teste.

Os pesquisadores foram cuidadosos para garantir que o tempo extra gasto neste processo de mistura fosse insignificante. Como os novos pontos de partida criados pela mistura já são soluções de alta qualidade, o algoritmo de melhoria converge para um ótimo local muito mais rápido do que faria a partir de um ponto de partida aleatório. O tempo total exigido pelo método POST foi apenas ligeiramente superior ao da abordagem de multi-início padrão, embora tenha encontrado consistentemente resultados superiores. Para os casos de teste uniformes, o novo método melhorou as melhores soluções conhecidas em uma média de 0,062 por cento e, para os casos não uniformes, em 0,068 por cento. Embora essas porcentagens possam parecer pequenas, no contexto de logística de grande escala e planejamento de instalações, elas representam economias significativas de distância e custo.

O estudo também explorou os limites desta abordagem. Os pesquisadores observaram que, se o procedimento de multi-início já tivesse encontrado a solução absolutamente ótima, o método POST não poderia melhorá-la. No entanto, como o problema p-mediana é conhecido por possuir milhões de ótimos locais, é altamente improvável que uma busca padrão encontre a resposta perfeita por acaso. O fato de o POST ter melhorado os resultados em todos os casos sugere que as buscas padrão estavam de fato ficando presas em picos locais que o POST foi capaz de escapar. Os pesquisadores também observaram que aumentar o número de buscas iniciais em um único lote nem sempre levava a melhores resultados; na verdade, os lotes menores com mais repetição tiveram um desempenho melhor. Isso apoia um princípio que eles chamam de "Menos é Mais", sugerindo que é mais eficaz explorar algumas áreas promissoras profundamente e repetidamente do que lançar uma rede ampla uma única vez e esperar pelo melhor.

O sucesso do POST não se limitou a um tipo de problema. Os pesquisadores testaram-no tanto em instâncias uniformes, onde os pontos de demanda estão espalhados uniformemente, quanto em instâncias não uniformes, onde os pontos estão agrupados de formas específicas. Em ambos os cenários, o método superou técnicas anteriores, incluindo os melhores resultados de outros estudos recentes que levaram meses de tempo computacional para serem alcançados. O novo método alcançou esses resultados em uma fração do tempo, sendo que o tempo total de execução para a configuração mais eficaz foi de cerca de treze dias para o conjunto completo de testes. Os pesquisadores também forneceram uma fórmula para estimar como o tempo de execução escalaria com o tamanho do problema, observando que, conforme o número de pontos de demanda aumentava dez vezes, o tempo necessário aumentava cerca de quinze a dezessete vezes, enquanto dobrar o número de instalações aumentava o tempo em menos de um fator de dois.

Olhando para o futuro, os autores sugerem que esta técnica possa ser aplicada a outros problemas de otimização que são atualmente resolvidos usando abordagens de multi-início, como o agrupamento de pontos de dados ou a partição de redes. Eles propõem que pesquisas futuras possam explorar diferentes maneiras de selecionar as soluções "pai", talvez escolhendo-as não apenas pela sua qualidade, mas também pelo quão diferentes são umas das outras, para garantir uma busca mais diversa. Eles também sugerem que aumentar o número de soluções no conjunto de elite usado para a mistura pode produzir resultados ainda melhores, embora isso exigiria mais poder computacional. O estudo conclui que, ao adicionar uma simples etapa de pós-otimização aos algoritmos existentes, os pesquisadores podem melhorar significamente a qualidade das soluções sem um aumento proibitivo de esforço, oferecendo uma nova ferramenta poderosa para lidar com alguns dos problemas de planejamento espacial mais complexos.