Una prima osservazione è che la GA canonica è basata su una rappresentazione di lunghezza fissa (un numero fisso di geni in < em> loci sul cromosoma).
Quindi gli operatori di crossover GA sono simili alla riproduzione biologica biologica: il materiale genetico di madre e padre è combinato in modo tale che i geni del bambino si trovino (approssimativamente) nella stessa posizione in cui si trovavano nei genitori.
È molto diverso dal crossover GP tradizionale basato su albero, che può spostare un sottoalbero in una posizione completamente diversa nella struttura ad albero.
Questa forma di crossover può succedere poiché il GP standard assume una "limitazione" nota come chiusura :
all the variables, constants, arguments for functions and values returned from functions must be of the same data type.
Una rappresentazione basata su AST è una forma di programmazione genetica (strongmente) tipizzata e introduce alcuni vincoli sui possibili punti di attraversamento.
Ogni nodo dell'AST è associato a un tipo e, prima di eseguire il crossover, devi creare un elenco di punti di crossover compatibili:
p1[1] p2[1]
/ \ / \
[2]b i[5] [2]s b[5]
/ \ / \ / \ / \
[3]b [4]f [6]i [7]s [3]i [4]n [6]s [7]i
b(p1): [2, 3] b(p2): [5]
f(p1): [4] f(p2): []
i(p1): [5, 6] i(p2): [3, 7]
s(p1): [7] s(p2): [2, 6]
n(p1): [] n(p2): [4]
Ora:
- seleziona un punto di crossover casuale
[P] da p1
- scambia il sottoalbero
[P] con uno secondario da p2
per es.
- selezione casuale per
p1 è [5]
- sotto-alberi compatibili da
p2 hanno radice in [3] e [7] . La selezione casuale è [7] .
Il risultato del crossover è:
p1 p2
/ \ / \
b i s b
/\ / \ / \
b f b fs i
/ \
i s
I bambini non hanno la stessa forma ma è abbastanza standard in GP.
Questo è un approccio molto di base. Con il tempo devi considerare vari altri aspetti:
-
spesso i punti di crossover non sono selezionati con probabilità uniforme :
typical GP primitive sets lead to trees with an average branching factor
(the num-ber of children of each node) of at least two, so the majority of the nodes will be leaves. Consequently the uniform selection of crossover points lead to crossover operations frequently exchanging only very small amounts of genetic material (i.e. small subtrees); many crossovers may in fact reduce to simply swapping two leaves.
To counter this, Koza (1992) suggested the widely used approach of choosing functions 90% of the time and leaves 10% of the time.
(da A Field Guide to Genetic Programming di Riccardo Poli, William Langdon, Nicholas McPhee, John Koza )
Quindi semplici elenchi di punti di crossover compatibili non potrebbero essere sufficienti.
-
potresti dover utilizzare operatori speciali per ridurre le dimensioni dell'albero (ad esempio Mutazione di sollevamento, Riduzione delle differenze)
-
in alcuni contesti potresti desiderare un operatore crossover che tenda a preservare la posizione del materiale genetico ( omologo ).
es. con crossover omologo di un punto devi analizzare i due alberi genitore dai nodi radice e selezionare il punto di crossover solo dalle parti dei due alberi nella regione comune.
The common region is related to homology, in the sense that the
common region represents the result of a matching process between parent
trees. Within the common region between two parent trees, the transfer of
homologous primitives can happen like it does in a linear bit string genetic
algorithm
("Una guida sul campo alla programmazione genetica")
Il crossover omologo presenta interessanti dettagli di implementazione (dovrebbe essere coordinato con l'elenco dei punti di crossover compatibili con il tipo).
-
La rappresentazione basata su AST può introdurre varie forme di "bias strutturali" che gli operatori di crossover / mutazione devono riconoscere.
Ultimo ma non meno importante ci sono altre rappresentazioni ben adattate per implementare la programmazione genetica tipizzata (anche non basata su albero). Le rappresentazioni lineari possono essere la scelta migliore per alcuni linguaggi di programmazione (è abbastanza semplice realizzare crossover omologo quando si usano rappresentazioni lineari e gli operatori omologhi sono ampiamente usati nel GP lineare).
Due meravigliose risorse gratuite per ulteriori dettagli sono: