Algoritmo genetico

Che cos'è

L'evoluzione naturale può essere modellata come un gioco, in cui le ricompense per un organismo che gioca un buon gioco della vita sono la trasmissione del suo materiale genetico ai suoi successori e la sua sopravvivenza continua. ^[2] Nell'evoluzione naturale, il rendimento di un individuo dipende da chi lavora e da chi compete, oltre che dall'ambiente. Gli algoritmi genetici sono una simulazione della selezione naturale su una popolazione di soluzioni candidate a un problema di ottimizzazione (cromosomi, individui, creature o fenotipi).

I candidati sono valutati e incrociati nel tentativo di fare buone soluzioni. Tali soluzioni possono richiedere molto tempo e non sono ovvie per un umano. Si inizia una fase evolutiva con una popolazione di esseri generati casualmente. In ogni generazione, viene valutata la fitness di ogni individuo della popolazione. Alcuni vengono selezionati a caso dalla popolazione attuale (in base alla loro fitness) e modificati (ricombinati ed eventualmente mutati a caso) per formare una nuova popolazione. Il ciclo si ripete con questa nuova popolazione. L'algoritmo termina o dopo che è passato un certo numero di generazioni, o dopo che è stato raggiunto un buon livello di fitness per la popolazione. Se l'algoritmo è terminato per aver raggiunto un numero massimo di generazioni, non significa necessariamente che sia stato ottenuto un buon livello di fitness.

Programmare questo su un computer

Lo pseudocodice è:

1. Inizializzazione: Vengono create alcune possibili soluzioni; molto spesso queste avranno valori casuali
2. Valutazione: Una funzione di fitness assegna un punteggio ad ogni soluzione; il punteggio sarà un numero che dice quanto bene questa soluzione risolve il problema.
3. I seguenti passi vengono eseguiti fino a quando non viene soddisfatto il requisito di fermarsi:
1. Selezione: Scegliere le soluzioni/individui per la prossima iterazione
2. Ricombinazione: Combinare le soluzioni raccolte
3. Mutazione: Cambia casualmente le soluzioni appena create
4. Valutazione: Applicare la funzione di fitness, vedi passo 2.
5. Se il requisito per fermarsi non è soddisfatto, ripartire con il passo di selezione.

Esempio

La descrizione di cui sopra è astratta. Un esempio concreto aiuta.

Applicazioni

In generale

Gli algoritmi genetici sono bravi a risolvere problemi che includono la pianificazione e la programmazione degli orari. Sono stati applicati anche all'ingegneria. Sono spesso usati per risolvere problemi di ottimizzazione globale.

Come regola generale, gli algoritmi genetici potrebbero essere utili in domini problematici che hanno un paesaggio di fitness complesso, in quanto il crossover è progettato per spostare la popolazione lontano dagli ottimali locali in cui un algoritmo tradizionale di hill climbing potrebbe rimanere bloccato. Gli operatori di crossover comunemente usati non possono cambiare una popolazione uniforme. La mutazione da sola può fornire l'ergodicità del processo generale dell'algoritmo genetico (visto come una catena di Markov).

Esempi di problemi risolti da algoritmi genetici includono: specchi progettati per incanalare la luce del sole in un collettore solare, antenne progettate per raccogliere segnali radio nello spazio, metodi di camminata per figure di computer, progettazione ottimale di corpi aerodinamici in campi di flusso complessi

Nel suo Algorithm Design Manual, Skiena sconsiglia gli algoritmi genetici per qualsiasi compito: "È abbastanza innaturale modellare le applicazioni in termini di operatori genetici come mutazione e crossover su stringhe di bit. La pseudobiologia aggiunge un altro livello di complessità tra voi e il vostro problema. In secondo luogo, gli algoritmi genetici richiedono un tempo molto lungo su problemi non banali. [...] L'analogia con l'evoluzione - dove un progresso significativo richiede [sic] milioni di anni - può essere abbastanza appropriata. [...] Non ho mai incontrato alcun problema in cui gli algoritmi genetici mi sembrassero il modo giusto per attaccarlo. Inoltre, non ho mai visto alcun risultato computazionale riportato utilizzando algoritmi genetici che mi abbia favorevolmente impressionato. Continuate a usare l'annealing simulato per le vostre esigenze di ricerca euristica voodoo".

Giochi da tavolo

I giochi da tavolo sono una parte molto rilevante dell'area degli algoritmi genetici applicati a problemi di teoria dei giochi. Gran parte dei primi lavori sull'intelligenza computazionale e i giochi erano diretti verso i classici giochi da tavolo, come il tic-tac-toe,^[3] gli scacchi e la dama. ^{[4] I} giochi da tavolo possono ora, nella maggior parte dei casi, essere giocati da un computer ad un livello superiore a quello dei migliori esseri umani, anche con tecniche di ricerca esaustiva alla cieca. Il Go è una nota eccezione a questa tendenza, e finora ha resistito all'attacco delle macchine. I migliori giocatori di computer di Go ora giocano al livello di un buon principiante. ^{[5][6] Si} dice che la strategia di Go faccia molto affidamento sul riconoscimento dei modelli, e non solo sull'analisi logica come negli scacchi e in altri giochi più indipendenti dal pezzo. L'enorme fattore di ramificazione effettivo richiesto per trovare soluzioni di alta qualità limita pesantemente il look-ahead che può essere usato all'interno di una sequenza di mosse di ricerca.

Giochi per computer

L'algoritmo genetico può essere usato nei giochi per computer per creare intelligenza artificiale (il computer gioca contro di voi). Questo permette un'esperienza di gioco più realistica; se un giocatore umano può trovare una sequenza di passi che portano sempre al successo anche se ripetuti in giochi diversi, non può rimanere una sfida. Al contrario, se una tecnica di apprendimento come un algoritmo genetico per uno stratega può evitare di ripetere gli errori del passato, il gioco avrà più giocabilità.

Gli algoritmi genetici richiedono le seguenti parti:

• Un metodo per rappresentare la sfida in termini di soluzione (ad esempio, instradare i soldati in un attacco in un gioco di strategia)
• Una funzione di fitness o di valutazione per determinare la qualità di un'istanza (per esempio una misura del danno fatto a un avversario in un attacco).

La funzione di fitness accetta un'istanza mutata di un'entità e misura la sua qualità. Questa funzione è personalizzata al dominio del problema. In molti casi, in particolare quelli che coinvolgono l'ottimizzazione del codice, la funzione di fitness può essere semplicemente una funzione di temporizzazione del sistema. Una volta che una rappresentazione genetica e una funzione di fitness sono definite, un algoritmo genetico istanzia i candidati iniziali come descritto prima, e poi migliora attraverso l'applicazione ripetitiva degli operatori di mutazione, crossover, inversione e selezione (come definito in base al dominio del problema).

Limitazioni

Ci sono delle limitazioni nell'uso di un algoritmo genetico rispetto agli algoritmi di ottimizzazione alternativi:

• La valutazione ripetuta della funzione di fitness per problemi complessi è spesso il segmento più limitante degli algoritmi evolutivi artificiali. Trovare la soluzione ottimale a problemi complessi spesso richiede valutazioni della funzione di fitness molto costose. Nei problemi del mondo reale, come i problemi di ottimizzazione strutturale, una singola valutazione della funzione può richiedere da diverse ore a diversi giorni di simulazione completa. I tipici metodi di ottimizzazione non possono affrontare questo tipo di problemi. È spesso necessario utilizzare l'approssimazione, poiché il calcolo della soluzione esatta richiede troppo tempo. Gli algoritmi genetici a volte combinano diversi modelli di approssimazione per risolvere complessi problemi della vita reale.
• Gli algoritmi genetici non scalano bene. Cioè, quando il numero di elementi esposti alla mutazione è grande, c'è spesso un aumento esponenziale della dimensione dello spazio di ricerca. Questo rende estremamente difficile utilizzare la tecnica su problemi come la progettazione di un motore, una casa o un aereo. Per utilizzare gli algoritmi genetici con tali problemi, essi devono essere scomposti nella rappresentazione più semplice possibile. Per questo motivo, vediamo algoritmi evolutivi che codificano progetti di pale di ventilatori invece di motori, forme di edifici invece di piani di costruzione dettagliati, e profili alari invece di interi progetti di aerei. Il secondo problema di complessità è la questione di come proteggere le parti che si sono evolute per rappresentare buone soluzioni da ulteriori mutazioni distruttive, in particolare quando la loro valutazione di fitness richiede che si combinino bene con altre parti.
• La soluzione "migliore" è solo in confronto ad altre soluzioni. Di conseguenza, il criterio di arresto non è chiaro in ogni problema.
• In molti problemi, gli algoritmi genetici hanno la tendenza a convergere verso gli ottimali locali o anche verso punti arbitrari piuttosto che verso l'ottimale globale del problema. Questo significa che l'algoritmo non "sa come" sacrificare il fitness a breve termine per guadagnare il fitness a lungo termine. La probabilità che questo accada dipende dalla forma della funzione di fitness: alcuni problemi rendono facile trovare l'optimum globale, altri possono rendere più facile per la funzione trovare gli optima locali. Questo problema può essere ridotto usando una diversa funzione di fitness, aumentando il tasso di mutazione, o usando tecniche di selezione che mantengono una popolazione diversa di soluzioni. Una tecnica comune per mantenere la diversità è quella di utilizzare una "penalità di nicchia": ogni gruppo di individui di sufficiente somiglianza (raggio di nicchia) ha una penalità aggiunta, che ridurrà la rappresentazione di quel gruppo nelle generazioni successive, permettendo ad altri individui (meno simili) di essere mantenuti nella popolazione. Questo trucco, tuttavia, potrebbe non essere efficace, a seconda del paesaggio del problema. Un'altra tecnica possibile sarebbe quella di sostituire semplicemente una parte della popolazione con individui generati casualmente, quando la maggior parte della popolazione è troppo simile tra loro. La diversità è importante negli algoritmi genetici (e nella programmazione genetica) perché incrociare una popolazione omogenea non produce nuove soluzioni. Nelle strategie di evoluzione e nella programmazione evolutiva, la diversità non è essenziale a causa di una maggiore dipendenza dalla mutazione.
• Operare su set di dati dinamici è difficile, poiché i genomi iniziano a convergere presto verso soluzioni che potrebbero non essere più valide per i dati successivi. Diversi metodi sono stati proposti per risolvere questo problema aumentando la diversità genetica in qualche modo e prevenendo la convergenza precoce, sia aumentando la probabilità di mutazione quando la qualità della soluzione scende (chiamata ipermutazione innescata), o introducendo occasionalmente elementi completamente nuovi, generati casualmente nel pool genico (chiamati immigranti casuali). Ancora, le strategie di evoluzione e la programmazione evolutiva possono essere implementate con una cosiddetta "strategia della virgola" in cui i genitori non sono mantenuti e i nuovi genitori sono selezionati solo dalla prole. Questo può essere più efficace su problemi dinamici.
• Gli algoritmi genetici non possono risolvere efficacemente i problemi in cui l'unica misura di fitness è una singola misura giusta/sbagliata (come i problemi di decisione), poiché non c'è modo di convergere sulla soluzione (nessuna collina da scalare). In questi casi, una ricerca casuale può trovare una soluzione tanto rapidamente quanto un GA. Tuttavia, se la situazione permette che il processo di successo/fallimento sia ripetuto dando (possibilmente) risultati diversi, allora il rapporto tra successi e fallimenti fornisce una misura di fitness adatta.
• Per specifici problemi di ottimizzazione e istanze del problema, altri algoritmi di ottimizzazione possono essere più efficienti degli algoritmi genetici in termini di velocità di convergenza. Algoritmi alternativi e complementari includono strategie di evoluzione, programmazione evolutiva, annealing simulato, adattamento gaussiano, hill climbing, e intelligenza di sciame (ad esempio: ottimizzazione di colonie di formiche, ottimizzazione di sciami di particelle) e metodi basati sulla programmazione lineare intera. L'idoneità degli algoritmi genetici dipende dalla quantità di conoscenza del problema; problemi ben noti spesso hanno approcci migliori e più specializzati.

Storia

Nel 1950, Alan Turing propose una "macchina di apprendimento" che avrebbe messo in parallelo i principi dell'evoluzione. La simulazione computerizzata dell'evoluzione iniziò già nel 1954 con il lavoro di Nils Aall Barricelli, che utilizzava il computer all'Institute for Advanced Study di Princeton, New Jersey. La sua pubblicazione del 1954 non fu molto notata. A partire dal 1957, il genetista quantitativo australiano Alex Fraser pubblicò una serie di articoli sulla simulazione della selezione artificiale di organismi con loci multipli che controllano un tratto misurabile. Da questi inizi, la simulazione al computer dell'evoluzione da parte dei biologi divenne più comune nei primi anni '60, e i metodi furono descritti nei libri di Fraser e Burnell (1970) e Crosby (1973). Le simulazioni di Fraser includevano tutti gli elementi essenziali dei moderni algoritmi genetici. Inoltre, Hans-Joachim Bremermann pubblicò una serie di articoli negli anni '60 che adottavano anche una popolazione di soluzioni a problemi di ottimizzazione, sottoposti a ricombinazione, mutazione e selezione. La ricerca di Bremermann includeva anche gli elementi dei moderni algoritmi genetici. Altri pionieri degni di nota sono Richard Friedberg, George Friedman e Michael Conrad. Molti dei primi articoli sono ristampati da Fogel (1998).

Anche se Barricelli, in un lavoro riportato nel 1963, aveva simulato l'evoluzione della capacità di giocare un semplice gioco, l'evoluzione artificiale divenne un metodo di ottimizzazione ampiamente riconosciuto come risultato del lavoro di Ingo Rechenberg e Hans-Paul Schwefel negli anni '60 e nei primi anni '70 - il gruppo di Rechenberg fu in grado di risolvere complessi problemi di ingegneria attraverso strategie di evoluzione. Un altro approccio fu la tecnica di programmazione evolutiva di Lawrence J. Fogel, che fu proposta per generare intelligenza artificiale. La programmazione evolutiva originariamente usava macchine a stati finiti per prevedere gli ambienti, e usava la variazione e la selezione per ottimizzare le logiche predittive. Gli algoritmi genetici in particolare sono diventati popolari attraverso il lavoro di John Holland nei primi anni '70, e in particolare il suo libro Adaptation in Natural and Artificial Systems (1975). Il suo lavoro ebbe origine dagli studi sugli automi cellulari, condotti da Holland e dai suoi studenti all'Università del Michigan. Holland ha introdotto un quadro formalizzato per prevedere la qualità della generazione successiva, noto come teorema dello schema diHolland. La ricerca sui GA è rimasta in gran parte teorica fino alla metà degli anni '80, quando la Prima Conferenza Internazionale sugli Algoritmi Genetici si è tenuta a Pittsburgh, Pennsylvania.