Skip to content
Voltar aos resultados

Algoritmo Genético Baseado em Agentes — Busca Evolucionária Distribuída via Agentes Autônomos

Proposto por
Adamidis, P. & Petridis, V. (early formal treatment); broader community development in 1990s
Ano
1990s
Tipo
Hybrid evolutionary-agent simulation
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?

Um Algoritmo Genético Baseado em Agentes (ABGA) particiona a população de um algoritmo genético em uma rede de agentes autônomos, cada um mantendo uma subpopulação local e evoluindo-a independentemente.

Os agentes trocam indivíduos periodicamente (migração) com base na proximidade ou regras de comunicação, permitindo a exploração paralela do espaço de busca, ao mesmo tempo que preservam a diversidade da população e evitam a convergência prematura.

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

Um algoritmo genético convencional trata toda a população como um único conjunto, o que pode causar convergência rápida para ótimos locais à medida que um genótipo dominante assume o controle. Uma abordagem baseada em agentes, em vez disso, distribui subpopulações entre agentes semi-autônomos dispostos em uma topologia de vizinhança. Cada agente executa sua própria seleção, cruzamento e mutação localmente, e então ocasionalmente compartilha indivíduos de alta aptidão com agentes vizinhos. Isso espelha como a especiação biológica ocorre em populações geograficamente isoladas, mas ocasionalmente conectadas, permitindo que diversas pressões evolutivas atuem em paralelo e recombinem soluções entre nichos.

História

Algoritmos genéticos distribuídos e paralelos surgiram no início dos anos 1990, à medida que pesquisadores buscavam superar a convergência prematura e explorar hardware paralelo. Adamidis e Petridis (1996) formalizaram populações de agentes cooperantes com diferentes comportamentos evolutivos. A estrutura baseada em agentes ganhou força no final dos anos 1990 e 2000, à medida que a modelagem baseada em agentes se espalhava pela ciência computacional, formalizando o modelo de interação autônomo e governado por topologia, agora amplamente aplicado em otimização complexa.

Quando usar

Usar um ABGA quando o espaço de aptidão for acidentado ou multimodal e os GAs padrão convergirem prematuramente de forma consistente; quando hardware paralelo ou distribuído estiver disponível que possa hospedar processos de agentes concorrentes; ou quando a estrutura do problema se mapeia naturalmente para subproblemas semi-independentes (por exemplo, cadeias de suprimentos regionais, políticas multissetoriais). Também apropriado ao explorar o comportamento do algoritmo sob pressões evolutivas heterogêneas. NÃO usar quando o problema tiver um único espaço de aptidão unimodal (GA mais simples é suficiente), quando o overhead da comunicação inter-agentes dominar a computação, quando os tamanhos da população forem muito pequenos para serem particionados de forma significativa, ou quando uma população centralizada for necessária para reprodutibilidade exata.

Limitações e considerações

  • O ajuste da política de migração (taxa, topologia, frequência) adiciona hiperparâmetros que exigem calibração cuidadosa e são dependentes do problema.
  • O overhead de comunicação entre agentes pode anular os benefícios do paralelismo em ambientes de computação de alta latência ou fracamente acoplados.
  • Garantias teóricas de convergência são mais fracas do que para GAs padrão; a análise formal da dinâmica do ABGA permanece uma área de pesquisa aberta.
  • Reproduzir resultados requer a fixação da topologia do agente, cronograma de migração e sementes aleatórias em todos os agentes, complicando a replicação.
  • Se os tamanhos das subpopulações forem muito pequenos, os agentes individuais estão sujeitos à deriva genética, independentemente da migraçã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

  • Mantém maior diversidade populacional do que GAs panmíticos, reduzindo a convergência prematura em espaços de aptidão acidentados.
  • Explora naturalmente infraestrutura de computação paralela ou distribuída para problemas de otimização em larga escala.
  • Configurações heterogêneas de operadores por agente permitem exploração e explotação simultâneas através de diferentes estratégias.
  • A migração de indivíduos aptos entre agentes permite a recombinação entre nichos que pode descobrir novas soluções de alta qualidade.
  • A arquitetura modular facilita a integração de heurísticas específicas do domínio nos loops de evolução de agentes individuais.
  • Escala bem com a dimensionalidade do problema quando as subpopulações podem ser particionadas de forma significativa.

Aplicações

  • Agendamento e logística: problemas distribuídos de job-shop ou roteamento de veículos onde subproblemas geográficos se mapeiam naturalmente para agentes.
  • Otimização de projeto de engenharia: projeto estrutural ou aerodinâmico com espaços de busca multimodais que se beneficiam da exploração paralela de nichos.
  • Simulação de políticas: otimização de parâmetros de políticas em modelos de simulação social onde agentes representam atores regionais ou setoriais.
  • Busca de hiperparâmetros de aprendizado de máquina: ajuste evolutivo paralelo de configurações de modelos em clusters de computação distribuída.
  • Bioinformática: predição de estrutura de proteínas e inferência de redes gênicas em espaços de aptidão de alta dimensionalidade e acidentados.
  • IA de jogos e robótica: evolução de estratégias de comportamento de agentes em ambientes multiagentes com dinâmica coevolucionária.

Como funciona

Como funciona

1

Definir a topologia dos agentes: especificar o número de agentes (subpopulações), sua estrutura de vizinhança (anel, grade, grafo de mundo pequeno ou totalmente conectado) e o protocolo de comunicação que rege quando e como os agentes trocam indivíduos. Cada agente é uma entidade computacional autônoma com seu próprio conjunto de cromossomos.

2

Inicializar a subpopulação local de cada agente com cromossomos gerados aleatoriamente (ou soluções semeadas). Definir o tamanho da população local, os operadores genéticos (tipo e taxa de cruzamento, taxa de mutação) e o mecanismo de seleção (torneio, roleta, baseado em ranking) independentemente para cada agente ou uniformemente entre todos os agentes.

3

Cada agente executa independentemente várias gerações de seleção, cruzamento e mutação em sua subpopulação local. Operando em paralelo (ou pseudo-paralelo em simulação sequencial), os agentes exploram diferentes regiões do espaço de solução sob configurações de operadores potencialmente diferentes, preservando a diversidade em todo o sistema.

4

Em intervalos de migração definidos, os agentes compartilham um subconjunto de seus indivíduos mais aptos com agentes vizinhos de acordo com a política de migração (por exemplo, enviar os melhores, receber e substituir os piores). A taxa de migração e a topologia moldam o equilíbrio entre exploração local e exploração global; migração muito frequente colapsa a diversidade, migração muito rara desperdiça a arquitetura distribuída.

5

Todos os cromossomos importados e evoluídos localmente são avaliados em relação à função de aptidão compartilhada. Os agentes podem aplicar pressão de seleção local após a migração para integrar indivíduos recebidos em sua população, potencialmente descartando incumbentes menos aptos. A avaliação de aptidão é o custo computacional dominante.

6

Terminar quando um critério de parada global for atendido (número máximo de gerações, convergência da melhor aptidão entre os agentes ou tempo decorrido). Coletar a melhor solução encontrada entre todos os agentes como saída final. Relatar curvas de convergência por agente para diagnosticar a diversidade da população e a eficácia da migração.

Erros comuns

  • Definir a taxa de migração muito alta colapsa a diversidade das subpopulações em um único conjunto de fato, eliminando a principal vantagem da arquitetura de agentes.
  • Ignorar o projeto da topologia de vizinhança: uma topologia totalmente conectada causa convergência rápida; um anel com frequência de migração inadequada pode deixar os agentes isolados e estagnados.
  • Avaliar a aptidão apenas localmente, sem uma função de aptidão global compartilhada, leva os agentes a otimizar objetivos incompatíveis.
  • Confundir ABGA com GA multiobjetivo: ABGA é uma variante arquitetônica para eficiência de busca, não inerentemente um método multiobjetivo — ABGA multiobjetivo requer mecanismos de Pareto adicionais.
  • Parar na convergência de um agente individual em vez de convergência global pode perder soluções melhores que ainda estão evoluindo em outros agentes.

Perguntas frequentes

Como um ABGA difere de um GA paralelo padrão?

Um GA paralelo padrão geralmente distribui a avaliação de aptidão de uma única população centralizada entre processadores. Um ABGA dá a cada agente uma subpopulação autônoma com seu próprio loop evolutivo; a interação ocorre apenas através de migração explícita, não através de um pool compartilhado. Essa distinção preserva pressões seletivas independentes por agente.

Qual topologia de migração devo escolher?

Topologias de anel e grade são pontos de partida padrão: elas limitam o fluxo de migração e preservam a diversidade. Topologias de mundo pequeno (alguns links de longo alcance adicionados a um anel) aceleram a propagação de boas soluções sem colapsar a diversidade. Topologias totalmente conectadas geralmente devem ser evitadas, a menos que se deseje um comportamento de convergência rápida.

Quantos agentes e qual tamanho de subpopulação é apropriado?

Uma heurística comum é de 4 a 16 agentes com tamanhos de subpopulação de 20 a 50 indivíduos cada, para uma população total comparável ao que um GA padrão usaria. Poucos agentes anulam a vantagem de diversidade da arquitetura; muitos agentes com subpopulações minúsculas sofrem deriva. É necessário ajuste empírico no problema específico.

O ABGA pode ser usado para otimização multiobjetivo?

Sim, mas mecanismos de Pareto adicionais (como ranking NSGA-II dentro de cada agente) devem ser adicionados. A arquitetura de agentes então ajuda a manter uma aproximação mais diversa da frente de Pareto. Esta é a base de variantes ABGA multiobjetivo.

Um ABGA tem garantia de encontrar o ótimo global?

Não. Como todos os GAs, os ABGAs são heurísticos e não oferecem garantia de otimalidade global. A preservação aprimorada da diversidade aumenta a probabilidade de evitar ótimos locais na prática, mas as garantias de convergência não são mais fortes do que para GAs padrão e são uma questão de pesquisa teórica ativa.

Métodos relacionados

Fontes

  1. Adamidis, P., & Petridis, V. (1996). Co-operating populations with different evolution behaviors. Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC 1996), 188-191. IEEE.

    Abrir referência da publicação
    Copiado.
  2. Genetic algorithm. Wikipedia.

    Abrir referência da publicação
    Copiado.