Come rappresentare un percorso per un algoritmo genetico?

Question

voglio usare un GA per determinare il percorso ottimale da A a B, soddisfacendo determinate condizioni (lunghezza, numero di giri, ecc.)

Un esempio di un percorso è il seguente: Up 4, Sinistra 8, Giù 3, Destra 3, Giù 1, Sinistra 10, in crescita del 4, Sinistra 1, Up 3

Il problema è che io non so davvero un buon modo per rappresentare le informazioni di questo tipo in un buon modo per l'uso in un GA, soprattutto perché i percorsi hanno una lunghezza variabile.

Qualcuno ha una buona idea di come fare qualcosa di simile?

Answer 1

Non sono sicuro di quello che il tuo problema è la rappresentazione, così ho il sospetto di avere questa domanda da un equivoco di stringa di cromosomi di un GA. Teoricamente parlando, la stringa di cromosomi non deve essere ricombinati in modo esplicito sui confini interi se si prende il passaggio aggiuntivo di demarcare i tuoi geni individuali, che ti permettono di ricombinare in modo gene-by-gene. Questo risolve il problema di un gene a lunghezza variabile, come la tua "percorso". I geni di lunghezza variabile è solo una questione di aggiungere un'altra variante al metodo di mutazione, in particolare "usa questo elemento o nuke questo elemento" oltre al "elemento uso da A o elemento da B" standard se il gene è fragili in discreto elementi, come il vostro percorso è.

Answer 2

Sembra che si desidera veramente di utilizzare qualcosa come il href="http://en.wikipedia.org/wiki/A*_algorithm" rel="nofollow noreferrer"> A * algoritmo di ottimizzazione , che è comunemente usato (con buoni risultati) per il percorso-scoperta. È possibile specificare qualsiasi funzione euristica che ti piace, al fine di ottenere la soluzione appropriata.

Answer 3

userei U, D, L, R ....

Quindi, "Up 4, Sinistra 8, Giù 3, Destra 3, Giù 1, Sinistra 10, Up 4, Sinistra 1, Up 3" potrebbe essere:

UUUULLLLLLLLDDDRRRDLLLLLLLLLLUUUULUUU

Sarebbe molto più facile da allevare le stringhe come questo.

Per A (15 caratteri) e B (3 caratteri), la mia funzione di riproduzione tra A & B sarebbe quello di:

• Scegliere la lunghezza casuale desiderata (len) tra 1 e MAX (LEN (A), LEN (B)) {tra 1 e 15}
• Scegli un punto (s) diviso casuale compreso tra 1 e Len.
• Scegliere se A o B per andare prima in modo casuale.
• prendere la prima s caratteri da quello di andare prima, e l'ultimo (len-s) caratteri da l'altro.

Answer 4

GA supporta i cromosomi con lunghezza variabile. Individuo reale può essere molto complessa. ad esempio può contenere un numero di bit di lunghezza fissa, stringa di caratteri (senza lunghezza fissa), e forse alcuni set di coppie di numeri complessi coniugati. Inoltre coniugati numeri complessi coppie devono sempre mantenere alcune condizioni. Si può fare, ma la più complessa individuo ottiene, le operazioni più complesse genetiche ottenere (ad esempio si incrociano, mutazione). Probabilmente la funzione Fitness sarebbe prendere alcune più righe di codice. Ma è ancora possibile.

Forse, come ha suggerito che si poteva scegliere il numero codificato rappresentazione percorso, ma può ancora essere fatto con il tuo esempio codificato come Osama ALASSIRY suggerito: UUUULLLLLLLLDDDRRRDLLLLLLLLLLUUUULUUU
.  Per cross over:

• lascia operatore mutando leggere corrente lenght1 di dato individuo,
• generare due numeri casuali X1, Y1, sia x1, y1 =
• fare lo stesso per i singoli 2, ora avete due coppie (x1, y1) e (x2, y2),
• copia da individuo 1 ciò è tra X1 e Y1, e inserirla individuale 2 tra i valori x2 e y2. Nuova versione di Individual 2 può cambiare la sua lunghezza come numero di geni tra X1Y1 e X2Y2 può essere diversa, ma che è ok,
• quello che era in versione originale del singolo 2 tra X2Y2 dovrebbe essere inserita in nuova versione del singolo 1 fra X1Y1 (la sua lunghezza cambierà anche),

Per chiarire:
genitore A: UUUULLLLLLLLDDDRRRDLLLLLLLLLLUUUULUUU
genitore B: DRRRRLULUDDDR
si generano coppie casuali Paira (4,18), pairB (0,5) supponendo che si contano geni da 0 si scambia seguenti stringhe:
UUUU LLLLLLLLDDDRRRD LLLLLLLLLLUUUULUUU
DRRRRL ULUDDDR
Così, dopo cross over si ottiene
UUUU DRRRRL LLLLLLLLLLUUUULUUU
LLLLLLLLDDDRRRD ULUDDDR
Ora che hai appena fatto attraversare. è possibile utilizzare anche un punto di taglio, o moltiplicare punti.

Per quanto riguarda la mutazione:

• generare il numero tra 0 e la lunghezza dei singoli,
• generare numero compreso tra 1-4 e aggiornare quel gene. (Se 1 generato cambiare a U, 2-D, 3-L, 4-R)

hai appena fatto mutazione. Si può anche mutare più di un gene.

Ma come ho detto, ci sono altre possibilità.

Answer 5

Per me questo suona molto simile al problema del commesso viaggiatore , non quella pagina contiene alcune informazioni utili?