• Home
• Prodotti
  • Insitor
  • Ai42 Opportunitas
  • Financial Master
  • JDentis
• Ricerca
  • Coregistrazione con Algoritmi Genetici
  • Integrazione Volumetrica
  • Ricostruzione Multirisoluzione di Oggetti 3D
• Contatti

Algoritmi Genetici

Gli Algoritmi Genetici (GA) sono metodi adattativi stocastici finalizzati alla risoluzione di problemi di ricerca e ottimizzazione, basati concettualmente sui processi genetici degli organismi biologici che regolano l'evoluzione naturale delle specie.

Di generazione in generazione, le specie si evolvono secondo i principi darwiniani della selezione naturale e della sopravvivenza del migliore. Gli algoritmi genetici, simulando questi processi, modellano le specie come soluzioni del problema e selezionando quelle migliori le ricombinano fra loro, in maniera tale da farle evolvere verso un punto di ottimo, ossia verso la soluzione del problema.

Un algoritmo genetico genera popolazioni di dati in un particolare spazio di soluzioni. Se l'algoritmo genetico è costruito bene, la popolazione converge a una soluzione ottima del problema. Il processo di sviluppo continua fino a quando non viene raggiunta una soluzione ottimale o si verifica una particolare condizione di stop.

Modello

Parti costitutive ed essenziali di ogni algoritmo genetico sono:

Popolazione iniziale di dati

Detti anche individui, sono un insieme di soluzioni generate anche casualmente che il processo evolutivo svilupperà.

Funzione di fitness

Valuta quanto una soluzione sia "buona" per il problema in esame.

Operatore di crossover

Procedura stocastica che crea un nuovo individuo fondendo assieme altri individui.

Operatore di mutazione

Procedura stocastica che modifica di poco una soluzione.

Funzione di selezione

Algoritmo che restituisce l'insieme delle soluzioni "migliori" rispetto alla funzione di fitness adoperando un processo stocastico. Gli individui scelti vengono adoperati per produrre nuove soluzioni usando gli operatori di crossover e di mutazione.

1. si crea una popolazione iniziale di dati casuali. Utilizzando una popolazione di individui, anziché un singolo individuo, diminuisce la probabilità che l'algoritmo possa rimanere "intrappolato" in una soluzione di ottimo locale;
2. si estrae l'insieme degli individui migliori (set of better patterns: SBP) usando la funzione di selezione. In questo modo gli individui migliori hanno più possibilità di incrociarsi con altri e trasmettere le loro "caratteristiche genetiche" alla generazione successiva. Gli individui meno adatti hanno meno probabilità di riprodursi e quindi si estingueranno. La funzione di selezione, favorendo l'accoppiamento tra gli individui più adatti, permette l'esplorazione delle aree più promettenti dello spazio di ricerca;
3. si crea una nuova popolazione di dati efettuando il crossover degli individui appartenenti all' SBP con se stessi. Il crossover produce nuovi individui discendenti che condividono alcune caratteristiche di ciascun genitore. Questa nuova popolazione di possibili soluzioni contiene una proporzione più alta delle caratteristiche migliori della specie, in questo modo dopo molte generazioni tali caratteristiche verranno propagate a tutta la popolazione;
4. si effettua una piccola mutazione su tutta la popolazione di dati. La mutazione porta un po' di "casualità" nella ricerca e aiuta ad assicurare che nessun punto nello spazio delle soluzioni abbia probabilità nulla di essere esaminato;
5. se si trova una soluzione accettabile al problema o se si deve fermare il processo di calcolo, poiché si è raggiunto il numero massimo di iterazioni o è trascorso il tempo disponibile, si esce dall'algoritmo genetico restituendo l'attuale soluzione migliore;
6. altrimenti si torna al punto 2.

Strategie Evolutive

Le strategie evolutive sono una particolare classe di algoritmi genetici: gli individui vengono trattati direttamente come semplici insiemi di variabili numeriche e gli operatori di crossover e di mutazione sono rispettivamente il punto medio e una perturbazione gaussiana i cui parametri statistici vengono anch'essi fatti evolvere.

Questi particolari algoritmi genetici si prestano particolarmente bene, sia in termini di efficienza di calcolo sia di velocità di convergenza alla soluzione, nei casi di ottimizzazione di funzioni regolari e continue.

Un Semplice Esempio di Algoritmo Genetico

È noto che ogni colore possa essere generato a partire dai colori primari Rosso, Verde e Blu (si pensi ad esempio ai colori del monitor). È giustificato dunque rappresentare i colori con terne di valori che indicano nell'ordine la quantità di Rosso, Verde e Blu che li compongono. Lo standard RGB (Red-Green-Blue) funziona proprio in questo modo: i valori per ogni componente vanno da un minimo di 0 ad un massimo di 255. In questo modo avremo il rosso (255,0,0), il verde (0,255,0), il blu (0,0,255), il bianco (255,255,255), il nero (0,0,0), ecc.

Il nostro problema è trovare il colore più scuro. Lo spazio delle soluzioni è quello dei colori RGB, terne di numeri naturali. Il colore più scuro, ovvero la soluzione cercata, è la terna del nero (0,0,0). Sono ora da definire, arbitrariamente ma appropriatamente per il problema posto, le funzioni di selezione e di fitness e gli operatori di mutazione e di crossover.

Nel seguito indicheremo con col (colore), padre e madre le terne di colore (r,g,b) e con col.Red, col.Green, col.Blue rispettivamente le componenti Rossa, Verde, Blu di col. Inoltre useremo la notazione color(r,g,b) per indicare la creazione di un nuovo colore.

Definiamo il fitness di un colore come la somma delle sue tre componenti (per il nostro problema i valori di fitness bassi sono migliori):

fitness (col) = col.Red () + col.Green () + col.Blue ()

L'operatore di crossover crea un colore "figlio" che eredita le prime due componenti dal "padre" e la terza dalla "madre":

crossover (padre, madre) = color (padre.Red (), padre.Green (), madre.Blue ())

La mutazione avviene sommando o sottraendo da ciascuna componente un valore casuale compreso tra 0 e 2:

mutazione (col) = color (
col.Red () + random (-2, 2),
col.Green () + random (-2, 2),
col.Blue () + random (-2, 2)
)

La selezione avviene ordinando gli individui per valore di fitness crescente: il più piccolo verrà selezionato per il crossover tre volte, il secondo ed il terzo due, l'ultimo una soltanto.

Si ricordi che una buona soluzione è un colore la cui funzione di fitness tende a zero. Questo perché abbiamo un problema di minimizzazione, al contrario, se avessimo avuto un problema di massimizzazione, gli individui migliori sarebbero stati quelli con funzione di fitness prossima a 765.

Creiamo ora una popolazione iniziale di quattro colori, in modo casuale.

La funzione di fitness applicata ad ogni elemento della popolazione restituisce i seguenti risultati:

fitness (Colore1) = 23 + 46 + 196  = 265
fitness (Colore2) = 48 + 217 + 2 = 267
fitness (Colore3) = 250 + 134 + 92 = 476
fitness (Colore4) = 7 + 4 + 179 = 190

La funzione di selezione pertanto fornisce nell'ordine:

Effettuiamo ora il crossover accoppiando i colori secondo la funzione di selezione:

Colore5 = crossover (Colore4, Colore1) = (7,4,196)
Colore6 = crossover (Colore4, Colore2) = (7,4,2)
Colore7 = crossover (Colore4, Colore3) = (7,4,92)
Colore8 = crossover (Colore1, Colore2) = (23,46,2)

Si osservi che il numero di individui nella popolazione non è aumentato.

Applichiamo ora l'operatore di mutazione ad ogni individuo generato:

Colore9 = mutazione (Colore5) = (5,4,194)
Colore10 = mutazione (Colore6) = (8,5,2)
Colore11 = mutazione (Colore7) = (6,2,94)
Colore12 = mutazione (Colore8) = (24,48,3)

La nuova popolazione di soluzioni è dunque:

I valori di fitness associati alla nuova popolazione di colori sono:

fitness (Colore9) = 5 + 4 + 194 = 203
fitness (Colore10) = 8 + 5 + 2 = 15
fitness (Colore11) = 6 + 2 + 94 = 102
fitness (Colore12) = 24 + 48 + 3 = 75

Si osservi come il fitness medio della nuova popolazione di soluzioni sia migliorato. Iterando il processo qui mostrato, la popolazione tenderà ad avere una funzione di fitness nulla, come desiderato.