Algoritmo genetico
28px|left Questo articolo sembra trattare lo stesso argomento di Algoritmi genetici. Vedi anche le altre pagine da unire.
Algoritmo genetico
Gli algoritmi genetici sono una particolare classe di algoritmi utilizzati in diversi campi, tra cui l'intelligenza artificiale.
Sono chiamati algoritmi genetici perché mutuano la terminologia dalla genetica, branca della biologia.
Il loro obiettivo è applicare l'evoluzione all'informatica. Un tipico algoritmo genetico parte da un certo numero di possibili soluzioni chiamate popolazione e provvede a farle evolvere. La loro evoluzione viene ottenuta attraverso una parziale ricombinazione delle soluzioni e attraverso delle mutazioni introdotte casualmente nella popolazione di partenza. Finita la fase di evoluzione la popolazione delle soluzioni viene analizzata e vengono tenute solo le soluzioni che meglio risolvono il problema. Queste soluzioni subiranno una nuova fase di evoluzione e cosi via. Alla fine ci si aspetta di trovare una popolazione di soluzioni che riescano a risolvere adeguatamente il problema posto. Non vi è modo di decidere a priori se l'algoritmo sarà effettivamente in grado di trovare una soluzione accettabile. Di norma gli algoritmi genetici vengono utilizzati per problemi di ottimizzazione per i quali non si conoscono algoritmi di complessità lineare o polinomiale.
| Indice |
Funzionamento
La soluzione del problema viene codificata in una struttura, di solito una stringa, detta gene.
Inizialmente viene creato un certo numero di geni in maniera casuale e si definisce una funzione che restituisce la "bontà" di un gene come soluzione del problema, detta funzione di fitness. L'algoritmo consiste nell'applicazione di operazioni, descritte più in basso, che tendono a modificare la popolazione dei geni, nel tentativo di migliorarli in modo da ottenere una soluzione sempre migliore.
L'evoluzione procede quindi in passi, per ognuno di questi viene per prima cosa eseguito un ordinamento dei geni sulla base del risultato della funzione di fitness. Vengono poi eseguite le operazioni su un numero di geni stabilito dai parametri dell'algoritmo, che in generale determinano quanti geni devono subire crossover e mutazioni, e in quale misura.
Operazioni
Crossover
In base a un coefficiente stabilito inizialmente, alcune parti dei geni risultati migliori vengono scambiate, nell'ipotesi che questo possa migliorare il risultato della funzione di fitness nel successivo "passo evolutivo".
Sperimentalmente si può vedere come in generale questo non succeda subito, ma il miglioramento diventa apprezzabile solo dopo un certo numero di passi. Questo a meno di casi fortunati, ovviamente.
Mutazione
La mutazione consiste nella modifica casuale di alcune parti dei geni con valore di fitness più basso, in base a coefficienti definiti inizialmente. Queste modifiche puntano a migliorare il valore della funzione per il gene in questione.
Categoria:Algoritmi
Categoria:Intelligenza artificiale