Gli Algoritmi Genetici (GA) si basano su un approccio evolutivo all'IA, in cui vengono utilizzati metodi di evoluzione di una popolazione per ottenere una soluzione ottimale per un determinato problema. Furono proposti nel 1975 da John Henry Holland.
Gli Algoritmi Genetici si basano sulle seguenti idee:
- Le soluzioni valide al problema possono essere rappresentate come geni
- Il crossover ci permette di combinare due soluzioni per ottenere una nuova soluzione valida
- La selezione viene utilizzata per scegliere le soluzioni più ottimali usando una funzione di fitness
- Le mutazioni vengono introdotte per destabilizzare l'ottimizzazione e uscire da un minimo locale
Se vuoi implementare un Algoritmo Genetico, hai bisogno di quanto segue:
- Trovare un metodo per codificare le soluzioni del problema usando geni g∈Γ
- Sul set di geni Γ è necessario definire una funzione di fitness fit: Γ→R. Valori più piccoli della funzione corrispondono a soluzioni migliori.
- Definire un meccanismo di crossover per combinare due geni e ottenere una nuova soluzione valida crossover: Γ2→Γ.
- Definire un meccanismo di mutazione mutate: Γ→Γ.
In molti casi, il crossover e la mutazione sono algoritmi piuttosto semplici per manipolare geni come sequenze numeriche o vettori di bit.
L'implementazione specifica di un algoritmo genetico può variare da caso a caso, ma la struttura generale è la seguente:
- Selezionare una popolazione iniziale G⊂Γ
- Selezionare casualmente una delle operazioni che verranno eseguite in questo passaggio: crossover o mutazione
- Crossover:
- Selezionare casualmente due geni g1, g2 ∈ G
- Calcolare il crossover g=crossover(g1,g2)
- Se fit(g)<fit(g1) o fit(g)<fit(g2) - sostituire il gene corrispondente nella popolazione con g.
- Mutazione - selezionare un gene casuale g∈G e sostituirlo con mutate(g)
- Ripetere dal passaggio 2, fino a ottenere un valore sufficientemente piccolo di fit, o fino a raggiungere il limite sul numero di passaggi.
I compiti tipicamente risolti dagli Algoritmi Genetici includono:
- Ottimizzazione dei programmi
- Impacchettamento ottimale
- Taglio ottimale
- Accelerazione della ricerca esaustiva
Continua il tuo apprendimento nei seguenti notebook:
Vai a questo notebook per vedere due esempi di utilizzo degli Algoritmi Genetici:
- Divisione equa del tesoro
- Problema delle 8 Regine
Gli Algoritmi Genetici vengono utilizzati per risolvere molti problemi, inclusi problemi di logistica e ricerca. Il campo è ispirato da ricerche che hanno unito argomenti di Psicologia e Informatica.
"Gli algoritmi genetici sono semplici da implementare, ma il loro comportamento è difficile da comprendere." fonte Fai una ricerca per trovare un'implementazione di un algoritmo genetico, come la risoluzione di un puzzle Sudoku, e spiega come funziona attraverso uno schema o un diagramma di flusso.
Guarda questo fantastico video che parla di come un computer può imparare a giocare a Super Mario usando reti neurali addestrate con algoritmi genetici. Impareremo di più su come i computer imparano a giocare a giochi simili nella prossima sezione.
Il tuo obiettivo è risolvere la cosiddetta equazione diofantea - un'equazione con radici intere. Ad esempio, considera l'equazione a+2b+3c+4d=30. Devi trovare le radici intere che soddisfano questa equazione.
Questo compito è ispirato da questo post.
Suggerimenti:
- Puoi considerare le radici nell'intervallo [0;30]
- Come gene, considera l'utilizzo della lista dei valori delle radici
Usa Diophantine.ipynb come punto di partenza.