Genetica algoritmi questione teorica

Question

Attualmente sto leggendo "Intelligenza Artificiale: un approccio moderno". (Russell + Norvig) e "Machine Learning" (Mitchell) - e cercando di imparare le basi del AINN

Per capire alcune cose di base che ho due '' greenhorn domande:

Q1:? In un algoritmo genetico dato il due genitori A e B con i cromosomi 001110 e 101101, rispettivamente, quale delle seguenti prole avrebbe potuto provocare da un crossover di un punto

A: 001101

b: 001110

Q2: Quale dei figli di cui sopra avrebbe potuto il risultato di un crossover a due punti? e perché?

Si prega di avvisare.

Answer 1

Non è possibile trovare i genitori, se non si conosce la funzione inversa-crossover (in modo che AxB => (a, b) e (qualsiasi a) => (A, B)).

Di solito la funzione di crossover 1-punto è:

a = A1 + B2
b = B1 + A2

Anche se si sa a e b non può risolvere il sistema (sistema di 2 equazioni con 4 variabili).

Se si conosce ogni 2 parti di qualsiasi A o / e B allora può essere risolto (sistema di 2 equazioni con 2 variabili). Questo è il caso per la tua domanda quando si forniscono sia A che B.

In generale funzione di crossover non ha funzione inversa e si solo bisogno di trovare la soluzione logicamente o, se conoscete i genitori, eseguire il crossover e confrontare .

Quindi, per rendere una formula generica per voi dovremmo sapere 2 cose:

1. Funzione Crossover.
2. Funzione inversa-crossover.

Il secondo non è di solito usato nel settore del gas in quanto non è richiesto.

---

Ora, mi limiterò a rispondere alle vostre domande.

  

Q1: In un algoritmo genetico dato il   due genitori A e B con il   cromosomi 001110 e 101101,   rispettivamente, quale delle seguenti   prole potrebbe essere il risultato di un   un punto di crossover?

Guardando il a e b riesco a vedere il punto di crossover è qui:

    1    2
A: 00 | 1110
B: 10 | 1101

Di solito il crossover è fatto utilizzando questa formula :

a = A1 + B2
b = B1 + A2

in modo che i bambini sono possibili:

a: 00 | 1101
b: 10 | 1110

, che esclude l'opzione b dalla questione.
Quindi la risposta alla Q1 è il figlio risultato è una: 001101 supponendo dato funzione di crossover

  

Q2: Quali della prole sopra potrebbe   hanno portato da una a due punti   Crossover? e perché?

Guardando la A e B posso vedere i punti di crossover possono essere qui:

    1   2    3
A: 00 | 11 | 10
B: 10 | 11 | 01

Solito Formula per 2-punto di crossover è:

a = A1 + B2 + A3
b = B1 + A2 + B3

Così i bambini sarebbero:

a = 00 | 11 | 10
b = 10 | 11 | 01

confrontandole con le opzioni che ha chiesto (piccola a e b ) possiamo dire la risposta:

Q2. A: Nessuno di un o b potrebbe essere causa di 2 punti crossover con AxB secondo la data funzione di crossover .

---

Anche in questo caso si tratta di non è possibile per rispondere alle vostre domande senza conoscere la funzione di crossover .

Le funzioni che ho fornito sono comuni in GA, ma si può inventare tanti di loro in modo da poter rispondere alla domanda (si veda il commento qui sotto):

Answer 2

Un incrocio punto è quando si effettua un join da ciascun genitore, due punti di crossover è quando si fanno due join. vale a dire due da un genitore e uno dagli altri.

incrocio (wikipedia) per ulteriori informazioni.

Answer 3

Per quanto riguarda la Q1, (a) potrebbe essere stato prodotto da un crossover di un punto, prendendo i bit 0-4 dal padre un po 'e 5 da genitore B. (b) non poteva meno il tuo Crossover algoritmo permette di contributi nulli, vale a dire i contributi madri di peso nullo. In tal caso, genitore A potrebbe contribuire pienamente cromosoma (bit 0-5) e genitore B contribuirebbe zero, cedevole (b).

Per quanto riguarda la Q2, sia (a) e (b) sono possibili. Ci sono alcune combinazioni di prova; troppo noioso da scrivere, ma si può fare il lavoro con carta e penna. : -)