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