lunedì 5 gennaio 2015

Algoritmo genetico

Un algoritmo genetico genera la soluzione di un problema facendo evolvere (in senso genetico) un insieme di soluzioni candidate in modo da ottenere la soluzione migliore, facendo estinguere le peggiori. Per poter realizzare un algoritmo genetico, è necessario partire da un gruppo di possibili soluzioni del problema. Ad ogni individuo viene corrisposta una soluzione, la popolazione è composta da un insieme di individui, ovvero da un insieme di soluzioni. Ogni individuo è composto da un suo cromosoma, un insieme di geni (bit) che ne codifica la soluzione. Per definire la qualità di un individuo, si definisce una funzione con lo scopo di assegnargli un valore. Questa funzione viene comunemente chiamata fitness. Un valore migliore di fitness indica una migliore soluzione. Una volta ottenuto il valore di fitness gli individui sono ordinati in base ad essa. Gli individui più promettenti vengono selezionati come genitori. Partendo dai genitori viene creata la generazione successiva, questa avrà le caratteristiche di entrambi i genitori (incrocio), oppure potrà avere dei cambiamenti casuali (mutazione). La nuova generazione prende il posto della vecchia ed il ciclo si ripete. Esiste inoltre anche una funzione che viene chiamata crossover, consiste nella generazione di una nuova soluzione mescolando quelle precedenti. L’algoritmo continua fino a quando non si verifica una delle condizioni imposte al sistema.

Nessun commento:

Posta un commento