Otimização extremal (OE) é um algoritmo metaheurístico para otimização combinatória, introduzido por Stefan Boettcher e Allon G. Percus em 1999. É inspirado no modelo de criticalidade auto-organizada de Bak-Snppen, que descreve como sistemas na natureza evoluem para um estado crítico por meio da remoção repetida de componentes menos aptos. Em otimização, a OE aborda problemas construindo uma solução candidata a partir de um conjunto de variáveis binárias ou valoradas, e então selecionando iterativamente a variável com a pior aptidão local e substituindo-a por um valor aleatório, explorando assim o espaço de soluções por meio de um processo extremal enviesado.
O algoritmo é notável por sua simplicidade e por alcançar soluções de alta qualidade em problemas difíceis sem depender de informações de gradiente. Pertence à classe mais ampla de métodos de computação evolucionária, mas difere dos algoritmos genéticos, que usam reprodução populacional e cruzamento. Em vez disso, a OE usa uma única solução e opera por meio de uma probabilidade de seleção de lei de potência, permitindo ocasionais saltos grandes no espaço de soluções. Esse comportamento estocástico ajuda a escapar de ótimos locais e frequentemente encontra resultados quase ótimos, especialmente para problemas como o problema do caixeiro viajante, particionamento de grafos e o problema do estado fundamental de vidros de spin.
Desenvolvimento Histórico
O método foi apresentado pela primeira vez por Boiss e Percus em 1999 e publicado sob o título "Extremal optimization: Methods derived from co-evolution" no periódico Physical Review Letters. Seu trabalho foi motivado pela observação de que sistemas na natureza, como pilhas de areia e ecossistemas biológicos, se auto-organizam em direção a um estado crítico por meio da eliminação de elementos com desempenho ruim. Isso levou ao desenvolvimento de uma heurística simples baseada em mutação, que contrasta com abordagens mais complexas orientadas por população. Experimentos iniciais demonstraram que a OE podia igualar ou superar o desempenho do recozimento simulado em problemas NP-difíceis de grande escala, estabelecendo seu lugar na literatura de otimização.
Desde sua introdução, a OE foi estendida e aplicada a uma variedade de domínios, incluindo particionamento de grafos em duas partes, coloração de grafos e, mais recentemente, à seleção de características em aprendizado de máquina. Variantes foram propostas para lidar com problemas com restrições e para melhorar a convergência por meio de distribuições de probabilidade adaptativas. Trabalhos também vincularam a OE à dinâmica da criticalidade auto-organizada, fornecendo justificativas teóricas para seu comportamento.
Algoritmo Central e Mecânica
O algoritmo básico da OE funciona da seguinte forma:
- Defina o problema com um espaço de busca onde cada solução possível é composta por um conjunto de variáveis (ou spins) com valores atribuídos.
- Para cada variável, um valor de aptidão local é calculado com base em sua contribuição para o custo ou aptidão geral da solução.
- A cada iteração, a variável com a pior (menor) aptidão local, chamada de variável extremal, é selecionada. Ela recebe então um novo valor aleatório, que pode ser escolhido a partir de um domínio de atribuições possíveis.
- Uma distribuição de probabilidade proporcional a uma lei de potência é frequentemente usada para selecionar a variável a ser atualizada, evitando a seleção apenas do pior, que pode prender o processo. Uma probabilidade de seleção típica para uma variável de classificação r (onde r=1 é a pior) é p(r) ~ r^-τ, com τ geralmente definido em torno de 1.
- Após cada atualização, as aptidões locais das variáveis afetadas são recalculadas, e o processo se repete por um número fixo de iterações ou até que um critério de parada seja atendido.
Uma característica notável é que a OE não usa nenhuma etapa explícita de busca local ou escalada de colina. Em vez disso, a mutação única e o parâmetro tau fornecem o equilíbrio entre exploração e explotação. Um τ menor leva a mudanças mais aleatórias, enquanto um τ maior enviesa a seleção para o melhor entre os piores, o que pode ser útil quando apenas alguns componentes ruins causam o problema. A qualidade da solução final é o maior valor de aptidão local observado em qualquer ponto durante a execução, que é frequentemente rastreado.
Aplicações em Sistemas Computacionais
A OE foi aplicada a uma gama de desafios de otimização. No campo da inteligência-artificial, foi usada para evoluir topologias de redes neurais e ajustar hiperparâmetros, fornecendo uma alternativa aos métodos baseados em gradiente. Em aprendizado-de-máquina, foi aplicada à seleção de características, onde o objetivo é escolher o melhor subconjunto de variáveis preditivas; a OE se sai bem porque as características podem ser tratadas como componentes com aptidão local baseada em sua contribuição para a precisão de validação.
Além disso, a OE é frequentemente usada para resolver instâncias de otimização combinatória, como o problema do empacotamento de contêineres, o agendamento de job-shop e a construção de códigos de correção de erros. Também é usada no projeto de sistemas paralelos e distribuídos, por exemplo, para atribuir tarefas a processadores a fim de minimizar o makespan. Sua falta de informação de gradiente significa que pode ser aplicada a problemas onde o objetivo é descontínuo ou discreto. Quando aplicada à bipartição de grafos, a OE mostrou produzir excelentes resultados de detecção de comunidades, igualando um algoritmo líder de particionamento de grafos.
Relação com Outras Metaheurísticas
A OE compartilha similaridades familiares com algoritmos genéticos e recozimento simulado, mas usa um mecanismo distinto. Algoritmos genéticos mantêm uma população de soluções e usam recombinação e mutação; a OE usa uma única solução. O recozimento simulado modifica a solução inteira por perturbações aleatórias e aceita mudanças de acordo com a temperatura; a OE modifica apenas o pior componente, guiado pela aptidão local. A diferença crítica é que a seleção do componente a ser alterado na OE é determinística (ou aleatória por lei de potência) com base na classificação, não no valor da função objetivo da solução inteira.
Uma conexão teórica com a criticalidade auto-organizada (CAO) significa que a OE reproduz as flutuações de lei de potência vistas em sistemas naturais, o que lhe confere robustez a muitos tipos de paisagens. Em comparações no benchmark clássico (o problema do caixeiro viajante), a OE é competitiva com o recozimento simulado, mas frequentemente requer menos avaliações de função. Na prática, para problemas onde as vizinhanças são definidas pela classificação da aptidão do componente, a OE pode ser eficiente mesmo com uma implementação simples.
Extensões e Variantes
A pesquisa produziu muitas variantes. A mais comum é a tau-OE, onde o parâmetro tau controla a probabilidade de escolher uma variável de classificação mais alta. O valor de tau e o alcance da cauda da lei de potência podem ser ajustados para melhorar a consistência. Outra variante é a escalada de colina probabilística com jitter introduzido na cauda. Outra abordagem, a co-evolução, lida com problemas com componentes interativos, onde mais de uma variável é mutada com base na co-adaptação. Mais recentemente, o algoritmo foi combinado com heurísticas de busca local, resultando em OE híbrida que realiza ajuste fino adicional após a fase de descoberta da OE.
Em aplicações de aprendizado-profundo, uma forma de OE foi usada para ajustar automaticamente a arquitetura de modelos, particularmente em buscas de redes-neurais, embora tenha sido superada por métodos mais complexos. A OE não requer gradientes, tornando-a aplicável a modelos onde gradientes não estão disponíveis ou são caros, como perdas não diferenciáveis. Também é adequada para explorar espaços discretos em problemas de aprendizado por reforço.
Limitações e Pesquisa Aberta
Um desafio chave com a OE é definir o parâmetro tau e o intervalo de valores da lei de potência. Um tau mal escolhido pode levar a uma convergência ruim ou ao caos. Além disso, como modifica apenas uma variável por vez, problemas muito restritos ou com dependências entre variáveis precisam de uma formalização cuidadosa da aptidão para evitar alto custo computacional.
A pesquisa aberta está focada em tornar a OE mais adaptativa, como estimar tau em tempo real ou usar cronogramas de recozimento para tau. Há também trabalho sobre métodos mais avançados de escolha do valor aleatório de substituição para variáveis e o uso da OE em ambientes distribuídos.
Embora o entendimento teórico da OE não seja tão maduro quanto o de outras metaheurísticas, ela é um conceito notável dentro do conjunto de ferramentas de otimização combinatória e computação inspirada na natureza, porque é simples de implementar e robusta a muitos tipos de problemas difíceis. O futuro provavelmente verá mais integrações com otimizadores especializados e mais estudos de suas estatísticas de lei de potência para agendamento e design práticos.
Pesquisadores-Chave e Influências
Os autores originais, Stefan Boettke e All Percus (ambos na época no Instituto Santa Fe), trouxeram a perspectiva da CAO para a otimização. Trabalhos subsequentes de outros grupos, incluindo aqueles na Xerox Parc e na Pesquisa de IA de Berkeley, expandiram a estrutura e a análise do método. Embora não esteja na vanguarda das ferramentas modernas de aprendizado de máquina, permanece uma referência em heurísticas inspiradas na natureza e é frequentemente incluída em materiais de curso sobre computação evolucionária.
Em resumo, a otimização extremal fornece uma estrutura estocástica minimalista, sem gradiente, para aproximar problemas combinatórios difíceis, e tem valor contínuo como conceito e algoritmo tanto em pesquisa teórica quanto em aplicações onde o problema pode ser decomposto em componentes com valores de aptidão individuais.
Limitações e Notas
Para uso prático, aqueles que a experimentarem devem estar cientes de que o método não oferece garantia de otimalidade global, e alguns problemas podem exigir ajuste da distribuição de probabilidade de seleção. Com a configuração adequada, pode ser uma ferramenta de otimização simples, porém eficaz.