algoritmi genetici
darwin
evoluzione
agisce su genotipo
non agisce su fenotipo
premia variazione che
promuove adattamento
migliore adattabilità
ad ambiente mutevole
riproduzione
ricombinazione genica
piccole mutazioni causali
del codice genetico
dei materiale genetico
dei genitori
evoluzione più rapida rispetto
a semplice copia dai geni di un
genitore
agisce su
popolazione
processi ciclici e
generazionali
contingenze ambientali
interazioni fra organismi
insieme dei cromosomi
cromosoma insieme dei geni
posizione dei geni
detta locus
diverse configurazioni
dette alleli
risultato finale
dell'evoluzione fetale
migliore fitness
probabilità che viva abbastanza
per riprodursi
selezione naturale
promuove come genitori per la
generazione successiva gli individui
che hanno i fenotipi codificati da particolari genotipi
più adatti
direzionale
aumenta la frequenza di una forma
estrema di un carattere
stabilizzante
favorisce individui portatori di una
forma intermedia di un certo carattere
divergente
favorisce una forma estrema di un carattere
a scapito delle forme intermedie
meccanismi dell'evoluzione
mutazione degli alleli
flusso genetico
variazione frequenza degli alleli
dovuta a movimenti
migratori degli individui
introduzione e rimozione di genotipi
deriva genetica
variazione imprevedibile
nelle frequenze degli alleli
popolazione con piccolo
numero di componenti
algoritmo
iterativo
opera su popolazione
di individui
individui codificano
le soluzioni ad dato problema
individui valutati tramite funzione
che misura la loro capacità di risolvere
il problema
più adatti alla
riproduzione
evoluzione della popolazione
simulata tramite
operatori random
riproduzione
mutazione
usi
programmazione dell'intelligenza artificiale in robotica
biocomputazione
studio dell'evoluzione dei sistemi cellulari paralleli
particolari problemi di gestione e sistemi di ottimizzazione in ingegneria
assunzioni
popolazione infinita
funzione fitness riflette
l'utilità della soluzione
i geni in un cromosoma non interagiscono
significativamente
errori stocastici
deriva genetica
Anche in assenza di qualsiasi pressione di selezione, cioè quando la funzione fitness è costante, membri della popolazione continueranno a convergere verso qualche punto nello spazio di ricerca.
se avviene un aumento della predominanza in alcune generazioni successive, e la popolazione è finita, allora un gene si può propagare a tutti i membri della popolazione
Una volta che un gene converge in questa maniera, il crossover non può introdurre nuovi valori di geni
effetto a catena, in modo tale che, con il procedere delle generazioni, ogni gene diventa eventualmente fissato
tasso di deriva genetica
limite inferiore alla velocità con la quale un un algoritmo genetico può convergere verso la soluzione corretta.
se un gene diventa predominante nella popolazione, allora ha la stessa probabilità sia di diventare più dominante nella generazione successiva, che meno dominante;
teorema degli schemi
sotto determinate ipotesi, gli individui con alti valori di fitness tendono a crescere esponenzialmente nella popolazione attraverso il meccanismo dell'incrocio, assicurando così la convergenza dell'algoritmo genetico verso una soluzione ottimale
reproduce trials
numero di opportunità che ogni individuo riceve è in proporzione al suo fitness
Passando i migliori schemi alla generazione successiva, viene aumentata la probabilità di trovare soluzioni migliori
il teorema considera un alfabeto formato dai simboli [0,1,*];
se si ha un genotipo binario di L elementi, uno schema è una stringa di L simboli
- può indicare al contempo sia 0 che 1
uno schema rappresenta un insieme di stringhe considerando il simbolo *
può essere più o meno adatto a sopravvivere nell'ambiente, a seconda che le stringhe che identifica abbiano una funzione di fitness più o meno elevata
Il crossover e la mutazione alterano gli schemi definiti e possono introdurne di nuovi.
utilizzando una selezione di tipo fitness-proportionate, la distribuzione degli schemi di ricerca, cioè l'aumento o la diminuzione di un particolare schema, avviene in modo molto vicino all'ottimo matematico, ed è indipendente dal problema.
ordine indica il numero di simboli fissati 0 o 1
competizione tra schemi
parallelismo implicito
competizione avviene parallelamente tra
schemi dello stesso ordine (k), formano una
popolazione di 2 elevato a k individui con le stesse
posizioni fissate
ci saranno 2 elevato a lunghezza (L) competizioni in parallelo
l'algoritmo individuerà il migliore schema possibile associato ad ogni possibile posizione fissata, convergendo gradualmente verso lo schema migliore rispetto a tutte le posizioni fissate