Skip to content
Voltar aos resultados

Otimização Multi-Objetivo Baseada em Agentes — Busca evolucionária descentralizada através de objetivos concorrentes

Proposto por
Bonabeau, Dorigo, Theraulaz; Coello Coello et al.
Ano
1990s–2000s
Tipo
Simulation-driven multi-objective search
Família
Simulation / optimization

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

A otimização multi-objetivo baseada em agentes (ABMOO) incorpora agentes autônomos em um ambiente de simulação e evolui seu comportamento ou parâmetros para otimizar simultaneamente dois ou mais objetivos conflitantes, produzindo uma fronteira de Pareto eficiente de soluções em vez de um único ótimo.

É adequada para sistemas adaptativos complexos onde os objetivos emergem de interações em nível micro, em vez de equações de forma fechada.

A intuição por trás do método

Em vez de escrever uma função objetivo global, a ABMOO permite que uma população de agentes interagentes explore o espaço de soluções por meio de regras locais e comportamento emergente. Cada agente representa uma solução candidata ou um tomador de decisão; o sistema é executado em simulação, os resultados são medidos em cada objetivo, e um mecanismo de seleção de Pareto mantém as soluções não dominadas vivas ao longo das gerações. Como o "landscape" de aptidão é avaliado por meio de simulação, a ABMOO pode lidar com funções objetivo não lineares, estocásticas e dependentes de trajetória que desafiam o tratamento analítico. O resultado é uma frente de Pareto diversa que mostra a estrutura completa de "trade-off" entre objetivos concorrentes.

História

A otimização multi-objetivo baseada em agentes surgiu no final dos anos 1990 e início dos anos 2000, quando pesquisadores combinaram estruturas de modelagem baseada em agentes (NetLogo, Repast, MASON) com algoritmos evolucionários multi-objetivo. Trabalhos fundamentais de Bonabeau, Dorigo e Theraulaz sobre inteligência de "swarm" e de Coello Coello et al. sobre otimização evolucionária multi-objetivo estabeleceram as bases teóricas que são combinadas na ABMOO. A abordagem ganhou força na ciência de sistemas complexos, planejamento urbano e gestão ecológica ao longo dos anos 2000 e 2010.

Quando usar

Use ABMOO quando o comportamento do sistema emerge de interações de agentes e não pode ser capturado por equações de forma fechada, quando dois ou mais objetivos entram em conflito e os tomadores de decisão precisam da fronteira completa de "trade-off", e quando a estocasticidade ou a dependência de trajetória tornam a otimização analítica intratável. Ideal para o desenho de políticas em sistemas sociais, ecológicos ou de cadeia de suprimentos. Não use quando um único objetivo é suficiente, quando existe um "solver" analítico rápido baseado em gradiente, quando o orçamento computacional é severamente restrito (avaliações de simulação são caras), ou quando os objetivos podem ser combinados em uma utilidade escalar sem perda de "insight".

Limitações e considerações

  • Computacionalmente caro: cada avaliação de aptidão requer a execução de uma simulação completa baseada em agentes, multiplicando o custo pelo tamanho da população e pela contagem de gerações.
  • Os resultados são estocásticos; a frente de Pareto pode mudar entre as execuções, exigindo múltiplas execuções independentes e agregação estatística.
  • A validade do modelo depende fortemente do realismo das regras dos agentes e do ambiente de simulação; "garbage-in" leva a frentes de Pareto enganosas.
  • A "sintonia" de hiperparâmetros (tamanho da população, taxa de cruzamento, duração da simulação) não é trivial e é específica do problema.
  • Interpretar e agir sobre uma frente de Pareto de alta dimensão permanece um desafio sem ferramentas adicionais de apoio à decisão.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Lida com "landscapes" de objetivos não lineares, emergentes e dependentes de trajetória que resistem à formulação de forma fechada.
  • Produz uma frente de Pareto completa, dando aos tomadores de decisão visibilidade explícita dos "trade-offs" em vez de um único ponto.
  • Acomoda naturalmente a estocasticidade "mediando" replicações de simulação dentro da avaliação de aptidão.
  • Escala para populações de agentes heterogêneos com diversas regras de comportamento e topologias de interação.
  • Compatível com algoritmos multi-objetivo estabelecidos (NSGA-II, MOEA/D, MOPSO) como o "driver" de otimização.

Aplicações

  • Planejamento de tráfego urbano e uso do solo onde os "trade-offs" de investimento em infraestrutura (custo vs. congestionamento vs. emissões) emergem das decisões dos agentes residentes.
  • Otimização da resiliência da cadeia de suprimentos equilibrando custo, tempo de espera e risco de interrupção entre agentes fornecedores em rede.
  • Gestão ecológica encontrando políticas de colheita ou conservação Pareto-ótimas que equilibram o rendimento econômico e os objetivos de biodiversidade.
  • Desenho de intervenção epidêmica otimizando a cobertura vacinal versus os "trade-offs" da atividade econômica por meio de simulações de agentes populacionais.
  • Gestão de redes de energia coordenando agentes "prosumers" para minimizar simultaneamente custo, emissões de carbono e instabilidade da rede.
  • Avaliação de políticas sociais identificando conjuntos de parâmetros de políticas que melhoram conjuntamente os resultados de equidade e eficiência em modelos sociais baseados em agentes.

Como funciona

Como funciona

1

Enumere m objetivos f_1, ..., f_m (todos a serem minimizados ou maximizados) e variáveis de decisão codificadas no genoma ou conjunto de regras de cada agente. Defina as restrições e o ambiente de simulação que converte as decisões dos agentes em resultados observáveis.

2

Inicialize uma população de N agentes com genomas aleatórios ou "semeados" heuristicamente. O genoma de cada agente codifica os parâmetros ou regras comportamentais que a otimização ajustará ao longo das gerações.

3

Execute a simulação baseada em agentes por T passos de tempo. Ao final de cada execução, leia os valores dos objetivos f_1(x), ..., f_m(x) para cada agente ou para o sistema coletivo. Múltiplas replicações podem ser "mediadas" para gerenciar o ruído estocástico.

4

Aplique a ordenação não dominada: classifique os agentes por dominância de Pareto. Um agente x domina y se x não é pior em todos os objetivos e estritamente melhor em pelo menos um. Mantenha a frente não dominada (frente de Pareto) e use a distância de aglomeração ("crowding distance") ou a contribuição de hipervolume para manter a diversidade.

5

Aplique operadores genéticos (cruzamento, mutação) ou atualizações de velocidade estilo "swarm" à população sobrevivente. Novos agentes candidatos herdam, recombinam ou perturbam os genomas dos membros da frente de Pareto, e então reentram na simulação para avaliação.

6

Após um critério de parada (orçamento de gerações, convergência de hipervolume ou limite de tempo de execução) ser atingido, retorne a frente de Pareto final como o conjunto de soluções. Visualize os "trade-offs" usando gráficos de dispersão no espaço objetivo ou diagramas de coordenadas paralelas para interpretação do tomador de decisão.

Erros comuns

  • Executar poucas replicações de simulação por avaliação de agente infla o ruído e corrompe a classificação de Pareto — sempre teste a suficiência da replicação primeiro.
  • Convergência prematura para uma região estreita da frente de Pareto devido a mecanismos de diversidade insuficientes; use explicitamente a distância de aglomeração ou a seleção baseada em hipervolume.
  • Confundir o objetivo de otimização com o próprio modelo de simulação; garanta que as regras dos agentes representem o sistema real, não o resultado desejado.
  • Ignorar as restrições de orçamento computacional e especificar tamanhos de população ou contagens de gerações que são inviáveis para o tempo de execução da simulação.
  • Apresentar a frente de Pareto bruta aos tomadores de decisão sem filtragem ou visualização de apoio à decisão, levando à paralisia da análise.

Perguntas frequentes

Como a ABMOO difere de um algoritmo genético multi-objetivo padrão?

Em um MOEA padrão, a aptidão é calculada analiticamente ou por meio de uma função rápida. Na ABMOO, a aptidão é calculada executando uma simulação completa baseada em agentes, tornando cada avaliação muito mais cara, mas permitindo "landscapes" de objetivos que dependem de dinâmicas emergentes, interativas e estocásticas.

Qual algoritmo multi-objetivo funciona melhor como o otimizador na ABMOO?

O NSGA-II é o mais amplamente utilizado devido à sua ordenação não dominada e distância de aglomeração. MOEA/D e MOPSO também são comuns. A escolha depende da forma e dimensionalidade da frente de Pareto; não há uma melhor escolha universal — faça um "benchmark" em uma pequena execução primeiro.

Quantas replicações de simulação devo executar por avaliação de agente?

O suficiente para reduzir o ruído, de modo que as comparações de dominância de Pareto sejam confiáveis. Uma heurística comum é executar até que o coeficiente de variação de cada objetivo caia abaixo de 5–10%. Isso pode exigir 10–50 replicações, dependendo da estocasticidade do sistema.

A ABMOO pode lidar com mais de dois objetivos?

Sim, mas o desempenho se degrada à medida que a contagem de objetivos aumenta (a maldição da dimensionalidade na dominância de Pareto). Além de três objetivos, considere algoritmos de muitos objetivos, como NSGA-III ou MOEA/D, e use técnicas de visualização de redução de dimensionalidade para a frente resultante.

Quando devo preferir a otimização robusta em vez da ABMOO padrão?

Quando o próprio ambiente de simulação é incerto (incerteza de parâmetros, incerteza estrutural), use variantes robustas que avaliam os agentes sob múltiplos cenários ambientais e otimizam o pior caso ou o desempenho de Pareto esperado, em vez de uma única frente determinística.

Métodos relacionados

Fontes

  1. Bonabeau, E., Dorigo, M., & Theraulaz, G. (2002). Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press.

    ISBN: 9780195131598
    Copiado.
  2. Coello Coello, C. A., Lamont, G. B., & Van Veldhuizen, D. A. (2007). Evolutionary Algorithms for Solving Multi-Objective Problems (2nd ed.). Springer.

    ISBN: 9780387332543
    Copiado.