Skip to content
Torna ai risultati

Algoritmo Genetico Basato su Agenti — Ricerca Evolutiva Distribuita tramite Agenti Autonomi

Introdotto da
Adamidis, P. & Petridis, V. (early formal treatment); broader community development in 1990s
Anno
1990s
Tipo
Hybrid evolutionary-agent simulation
Famiglia
Simulation / optimization

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

Un Algoritmo Genetico Basato su Agenti (ABGA) partiziona la popolazione di un algoritmo genetico su una rete di agenti autonomi, ciascuno dei quali mantiene una sottopopolazione locale e la evolve indipendentemente.

Gli agenti scambiano periodicamente individui (migrazione) in base alla prossimità o a regole di comunicazione, consentendo l'esplorazione parallela dello spazio di ricerca, preservando al contempo la diversità della popolazione ed evitando la convergenza prematura.

L’intuizione alla base del metodo

Un algoritmo genetico convenzionale tratta l'intera popolazione come un unico pool, il che può causare una rapida convergenza su ottimi locali poiché un genotipo dominante prende il sopravvento. Un approccio basato su agenti distribuisce invece sottopopolazioni su agenti semi-autonomi disposti in una topologia di vicinato. Ciascun agente esegue localmente la propria selezione, crossover e mutazione, quindi occasionalmente condivide individui ad alta fitness con agenti vicini. Ciò rispecchia come avviene la speciazione biologica in popolazioni geograficamente isolate ma occasionalmente connesse, permettendo a diverse pressioni evolutive di agire in parallelo e di ricombinare soluzioni tra nicchie diverse.

Storia

Gli algoritmi genetici distribuiti e paralleli emersero all'inizio degli anni '90, quando i ricercatori cercarono di superare la convergenza prematura e sfruttare l'hardware parallelo. Adamidis e Petridis (1996) formalizzarono popolazioni di agenti cooperanti con diversi comportamenti evolutivi. La formulazione basata su agenti guadagnò slancio tra la fine degli anni '90 e gli anni 2000, con la diffusione della modellazione basata su agenti in tutta la scienza computazionale, formalizzando il modello di interazione autonomo e governato dalla topologia ora ampiamente applicato nell'ottimizzazione complessa.

Quando usarlo

Utilizzare un ABGA quando il panorama della fitness è accidentato o multimodale e i GA standard convergono costantemente prematuramente; quando è disponibile hardware parallelo o distribuito in grado di ospitare processi agenti concorrenti; o quando la struttura del problema si mappa naturalmente su sotto-problemi semi-indipendenti (ad es., catene di approvvigionamento regionali, politiche multisettoriali). Appropriato anche quando si esplora il comportamento dell'algoritmo sotto pressioni evolutive eterogenee. NON utilizzare quando il problema ha un singolo panorama unimodale (un GA più semplice è sufficiente), quando l'overhead della comunicazione inter-agente domina il calcolo, quando le dimensioni della popolazione sono troppo piccole per essere partizionate in modo significativo, o quando è richiesta una popolazione centralizzata per una riproducibilità esatta.

Limiti e considerazioni

  • La messa a punto della politica di migrazione (tasso, topologia, frequenza) aggiunge iperparametri che richiedono un'attenta calibrazione e dipendono dal problema.
  • L'overhead di comunicazione tra agenti può annullare i benefici del parallelismo in ambienti di calcolo ad alta latenza o debolmente accoppiati.
  • Le garanzie teoriche di convergenza sono più deboli rispetto ai GA standard; l'analisi formale delle dinamiche ABGA rimane un'area di ricerca aperta.
  • Riprodurre i risultati richiede la fissazione della topologia degli agenti, dello schema di migrazione e dei semi casuali su tutti gli agenti, complicando la replicazione.
  • Se le dimensioni delle sottopopolazioni sono troppo piccole, i singoli agenti sono soggetti a deriva genetica indipendentemente dalla migrazione.

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Mantiene una maggiore diversità della popolazione rispetto ai GA panmittici, riducendo la convergenza prematura su panorami di fitness accidentati.
  • Sfrutta naturalmente l'infrastruttura di calcolo parallela o distribuita per problemi di ottimizzazione su larga scala.
  • Impostazioni eterogenee degli operatori per agente consentono l'esplorazione e lo sfruttamento simultanei attraverso diverse strategie.
  • La migrazione di individui fitti tra agenti consente la ricombinazione tra nicchie che può scoprire nuove soluzioni di alta qualità.
  • L'architettura modulare facilita l'integrazione di euristiche specifiche del dominio all'interno dei cicli evolutivi dei singoli agenti.
  • Scala bene con la dimensionalità del problema quando le sottopopolazioni possono essere partizionate in modo significativo.

Applicazioni

  • Pianificazione e logistica: problemi distribuiti di job-shop o vehicle routing in cui sotto-problemi geografici si mappano naturalmente agli agenti.
  • Ottimizzazione del design ingegneristico: design strutturale o aerodinamico con spazi di ricerca multimodali che beneficiano dell'esplorazione parallela di nicchie.
  • Simulazione di policy: ottimizzazione dei parametri di policy nei modelli di simulazione sociale in cui gli agenti rappresentano attori regionali o settoriali.
  • Ricerca di iperparametri di machine learning: sintonizzazione evolutiva parallela di configurazioni di modelli su cluster di calcolo distribuiti.
  • Bioinformatica: predizione della struttura proteica e inferenza di reti geniche su panorami di fitness ad alta dimensionalità e accidentati.
  • IA di gioco e robotica: evoluzione di strategie comportamentali degli agenti in ambienti multi-agente con dinamiche co-evolutive.

Come funziona

Come funziona

1

Definire la topologia degli agenti: specificare il numero di agenti (sottopopolazioni), la loro struttura di vicinato (anello, griglia, grafo small-world o completamente connesso) e il protocollo di comunicazione che governa quando e come gli agenti scambiano individui. Ciascun agente è un'entità computazionale autonoma con il proprio pool di cromosomi.

2

Inizializzare la sottopopolazione locale di ciascun agente con cromosomi generati casualmente (o soluzioni seme). Impostare la dimensione della popolazione locale, gli operatori genetici (tipo e tasso di crossover, tasso di mutazione) e il meccanismo di selezione (a torneo, roulette, basato su rango) indipendentemente per ciascun agente o uniformemente su tutti gli agenti.

3

Ciascun agente esegue indipendentemente diverse generazioni di selezione, crossover e mutazione sulla propria sottopopolazione locale. Operando in parallelo (o pseudo-parallelo in simulazione sequenziale), gli agenti esplorano diverse regioni dello spazio di soluzione sotto configurazioni di operatori potenzialmente diverse, preservando la diversità nell'intero sistema.

4

Agli intervalli di migrazione definiti, gli agenti condividono un sottoinsieme dei loro individui più fitti con agenti vicini secondo la politica di migrazione (ad es., invia i migliori, ricevi-sostituisci i peggiori). Il tasso di migrazione e la topologia modellano l'equilibrio tra sfruttamento locale ed esplorazione globale; una migrazione troppo frequente collassa la diversità, una migrazione troppo rara spreca l'architettura distribuita.

5

Tutti i cromosomi importati ed evoluti localmente vengono valutati rispetto alla funzione di fitness condivisa. Gli agenti possono applicare una pressione selettiva locale dopo la migrazione per integrare gli individui ricevuti nella loro popolazione, scartando potenzialmente gli incumbent meno fitti. La valutazione della fitness è il costo computazionale dominante.

6

Terminare quando viene soddisfatto un criterio di arresto globale (massimo numero di generazioni, convergenza della migliore fitness tra gli agenti o tempo trascorso). Raccogliere la migliore soluzione trovata tra tutti gli agenti come output finale. Riportare le curve di convergenza per agente per diagnosticare la diversità della popolazione e l'efficacia della migrazione.

Errori comuni

  • Impostare un tasso di migrazione troppo elevato collassa la diversità delle sottopopolazioni in un unico pool de facto, eliminando il principale vantaggio dell'architettura basata su agenti.
  • Ignorare la progettazione della topologia del vicinato: una topologia completamente connessa causa una rapida convergenza; un anello con una frequenza di migrazione inadeguata può lasciare gli agenti isolati e stagnanti.
  • Valutare la fitness solo localmente senza una funzione di fitness globale condivisa porta gli agenti a ottimizzare obiettivi incompatibili.
  • Confondere ABGA con GA multi-obiettivo: ABGA è una variante architetturale per l'efficienza della ricerca, non intrinsecamente un metodo multi-obiettivo — ABGA multi-obiettivo richiede macchinari Pareto aggiuntivi.
  • Fermarsi alla convergenza del singolo agente piuttosto che alla convergenza globale può far perdere soluzioni migliori ancora in evoluzione in altri agenti.

Domande frequenti

In che modo un ABGA differisce da un GA parallelo standard?

Un GA parallelo standard distribuisce tipicamente la valutazione della fitness di un'unica popolazione centralizzata su più processori. Un ABGA assegna a ciascun agente una sottopopolazione autonoma con il proprio ciclo evolutivo; l'interazione avviene solo tramite migrazione esplicita, non tramite un pool condiviso. Questa distinzione preserva pressioni selettive indipendenti per agente.

Quale topologia di migrazione dovrei scegliere?

Le topologie ad anello e a griglia sono punti di partenza standard: limitano il flusso di migrazione e preservano la diversità. Le topologie small-world (pochi collegamenti a lungo raggio aggiunti a un anello) accelerano la propagazione di buone soluzioni senza collassare la diversità. Le topologie completamente connesse dovrebbero generalmente essere evitate a meno che non si desideri un comportamento di rapida convergenza.

Quanti agenti e quale dimensione della sottopopolazione è appropriata?

Una euristica comune è 4-16 agenti con sottopopolazioni di 20-50 individui ciascuna, per una popolazione totale paragonabile a quella che userebbe un GA standard. Troppi pochi agenti annullano il vantaggio di diversità dell'architettura; troppi agenti con sottopopolazioni minuscole soffrono di deriva. È necessaria una messa a punto empirica sul problema specifico.

L'ABGA può essere utilizzato per l'ottimizzazione multi-obiettivo?

Sì, ma è necessario aggiungere macchinari Pareto aggiuntivi (come la classificazione NSGA-II all'interno di ciascun agente). L'architettura dell'agente aiuta quindi a mantenere un'approssimazione più diversificata della frontiera di Pareto. Questa è la base delle varianti ABGA multi-obiettivo.

Un ABGA è garantito per trovare l'ottimo globale?

No. Come tutti i GA, gli ABGA sono euristici e non forniscono alcuna garanzia di ottimalità globale. La migliore preservazione della diversità aumenta la probabilità di evitare ottimi locali in pratica, ma le garanzie di convergenza non sono più forti rispetto ai GA standard e costituiscono una questione di ricerca teorica attiva.

Metodi correlati

Fonti

  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.

    Apri il riferimento della pubblicazione
    Copiato.
  2. Genetic algorithm. Wikipedia.

    Apri il riferimento della pubblicazione
    Copiato.