Algoritmo genetico: differenze tra le versioni

Versione delle 11:36, 22 feb 2024

Versione attuale delle 10:17, 8 mag 2024

(Una versione intermedia di uno stesso utente non è mostrata)

Riga 37:

=== La codifica ===

Come accennato, le soluzioni al problema considerato, siano questeesse quelle casuali di partenza o quelle derivate da evoluzione, devono essere codificate con qualche tecnica.

Le codifiche più diffuse sono:

Riga 51:

=== La logica di selezione ===

A causa di complessi fenomeni di interazione non lineare ([[epistaticità]]), non è dato per scontato né che da due soluzioni promettenti ne nasca una terza più promettente né che da due soluzioni con valori di fitness basso ne venga generata una terza con valore di fitness più basso. Per ovviare a questi problemi, durante la scelta delle soluzioni candidate all'evoluzione, oltre che sul parametro ottenuto dalla funzione di fitness ci si basa anche su particolari tecniche di "selezione". Le più comuni sono:

*''Selezione a roulette'': la probabilità che una soluzione venga scelta per farla evolvere è direttamente proporzionale al valore restituito dalla funzione di fitness. Questa tecnica presenta dei problemi nel caso in cui ci siano delle grosse differenze di valori perché le soluzioni peggiori verrebbero selezionate troppo raramente.

*''Selezione per categoria'': simile alla selezione per roulette ma la valutazione è effettuata in maniera proporzionale alla somma del valore della funzione di fitness per ogni coppia possibile di soluzioni. Il problema presentato da questa tecnica di scelta è rappresentato dalla lentezza di convergenza nel caso in cui ci siano delle differenze troppo piccole tra coppie di soluzioni candidate.

Riga 66:

=== Il crossover ===

Per semplicità, durante la spiegazione del crossover, si farà riferimento alle codifiche vettoriali ma il procedimento per le codifiche ad albero è simile ed invece che essere applicato ai campi dei vettori viene applicato ai nodi dell'albero. In base ad un [[operatore (matematica)|operatore]] stabilito inizialmente, alcune parti dei geni delle soluzioni candidate all'evoluzione vengono mescolate per ricavare nuove soluzioni.

In base ad un [[operatore (matematica)|operatore]] stabilito inizialmente, alcune parti dei geni delle soluzioni candidate all'evoluzione vengono mescolate per ricavare nuove soluzioni.

Gli operatori più comunemente utilizzati sono:

Line 77 ⟶ 76:

*Crossover uniforme: consiste nello scambiare casualmente dei bit tra le soluzioni candidate all'evoluzione. Si segnala l'esistenza anche di crossover uniformi parziali ossia dei crossover uniformi dove lo scambio di bit è limitato ad una percentuale fissa o dinamica dei cromosomi candidati all'evoluzione.

*Crossover aritmetico: consiste nell'utilizzare un'operazione aritmetica per creare la nuova soluzione. (es. [[Algebra di Boole#XOR|XOR]] o un [[Algebra di Boole#AND|AND]]).

Non è detto che il crossover debba avvenire ad ogni iterazione dell'algoritmo genetico. Generalmente la frequenza di crossover è regolata da un apposito parametro comunemente denominato <math>p_c</math>.