algoritmo genetico

algoritmo genetico

Algoritmo che imita il processo di selezione naturale per mettere in atto una ricerca euristica di soluzione di problemi. L’utilizzazione di tali algoritmi rappresenta uno degli approcci più interessanti nati nel corso degli anni Ottanta del Novecento, nell’ambito delle ricerche sull’intelligenza artificiale. Questi algoritmi sono detti genetici perché considerano l’insieme iniziale dei possibili approcci risolutivi come una popolazione di individui con diversi patrimoni genetici (cioè, stringhe di istruzioni che codificano una possibile soluzione del problema). Con opportuni metodi di incrocio e replicazione, questi individui generano altre soluzioni; un meccanismo di mutazione e di selezione naturale provvede a far prevalere, nel processo riproduttivo, le soluzioni migliori e a determinare, in definitiva, il successo della specie nella risoluzione del problema dato. Il vantaggio di questo metodo dipende dal fatto che, partendo da una pluralità di soluzioni e operando in modo probabilistico (sia l’incrocio sia le mutazioni sono processi probabilistici), è più difficile che si rimanga intrappolati in vicoli ciechi (anche se relativamente efficaci nella soluzione del problema). È chiaro, inoltre, che il metodo si presta bene a essere implementato in modo efficiente su macchine parallele. Un algoritmo genetico consiste, in generale, nella ripetizione continua dei tre passi fondamentali: (a) selezione, ossia scelta delle soluzioni (genitori) da incrociare, in base alla loro qualità, rispetto alla funzione obiettivo del problema; (b) incrocio, cioè ricombinazione di due soluzioni per generarne di nuove; (c) mutazione, ossia modificazione casuale delle soluzioni ottenute (figli). Ciascuno dei tre passi può essere realizzato in molti modi e ciò dà luogo a una grande varietà nella tipologia degli algoritmi genetici. Nel meccanismo di selezione, per es., si può introdurre il concetto di specie e proibire l’incrocio tra specie diverse (rappresentando così il fatto che certi tipi di incroci possano essere sterili). Per quanto valido in molte applicazioni (in particolare nella risoluzione di problemi inversi, come il disegno dell’ala di un aereo a partire dalla portanza richiesta), l’approccio genetico presenta ancora molti aspetti insoddisfacenti, come la lentezza della convergenza verso le soluzioni e i fenomeni di deriva genetica casuale. (*)

→ Intelligenza artificiale; Reti neurali e vita artificiale