Utilizzando GA in GUI

Question

Scusate se questo non è chiaro come sto scrivendo questo su un dispositivo mobile e sto cercando di fare in fretta.

Ho scritto un algoritmo di base genetica con una codifica binaria (geni) che costruisce un valore di fitness e si evolve attraverso diverse iterazioni con torneo di selezione, la mutazione e crossover. Come un esempio di base della riga di comando sembra funzionare.

Il problema che ho è con l'applicazione di un algoritmo genetico all'interno di una GUI come sto scrivendo un programma di labirinto-solving che utilizza il GA di trovare un metodo attraverso un labirinto. Come posso attivare il mio binario a caso i geni codificati e funzione di fitness (aggiungere tutti i valori binari insieme) in un metodo per controllare un bot in un labirinto? Ho costruito una GUI di base in Java costituito da un dedalo di etichette (come una griglia) con i percorsi disponibili sia in blu e le pareti di essere in nero.

Per ribadire la mia GA si comporta bene e contiene quello che qualsiasi tipico GA sarebbe (metodo di idoneità, ottenere e impostare la popolazione, la selezione, crossover, ecc), ma ora ho bisogno di collegarlo a una GUI per ottenere il mio labirinto in esecuzione. Che ha bisogno di andare dove al fine di ottenere un bot che può muoversi in direzioni diverse a seconda di quello che dice il GA? pseudocodice di massima sarebbe bello se possibile

Come richiesto, un individuo è costruito utilizzando una classe separata (indiv), con tutto il lavoro principale è fatto in una classe di Pop. Quando un nuovo individuo viene istanziata un array di int rappresentare i geni di detto individuo, con i geni che sono presi a caso da un numero compreso tra 0 e 1. La funzione di fitness aggiunge solo insieme al valore di questi geni e nel Pop classe gestisce selezione , la mutazione e il crossover di due individui selezionati. Non c'è molto altro da esso, il programma a riga di comando mostra appena evoluzione nel n generazioni con l'idoneità totale migliorare su ogni iterazione.

EDIT: Si comincia a fare un po 'più senso ora, anche se ci sono alcune cose che mi stanno di sorvegliare i ...

Come Adamski ha suggerito che voglio creare un "agente" con le opzioni indicate di seguito. Il problema che ho è dove la stringa di bit casuale entra in gioco qui. L'agente sa dove le pareti sono e lo ha disposto in una stringa 4 bit (cioè 0111), ma in che modo incide la stringa casuale a 32 bit? (Vale a dire 10001011011001001010011011010101) Se ho il seguente labirinto (x è il luogo di partenza, 2 è l'obiettivo, 1 è il muro):

x 1 1 1 1
0 0 1 0 0
1 0 0 0 2

Se io giro a sinistra sto affrontando nel modo sbagliato e l'agente si sposta completamente fuori dal labirinto se si muove in avanti. Suppongo che la prima generazione della stringa sarà completamente casuale e si evolverà quanto riguarda l'idoneità cresce, ma non ottengo come la stringa lavorerà all'interno di un labirinto.

Quindi, per ottenere questo diritto ...

Il fitness è il risultato di quando l'agente è in grado di muoversi ed è da un muro.

I geni sono una stringa di 32 bit, suddivisi in 16 gruppi di 2 bit per mostrare le azioni disponibili e per il robot per spostare i due bit devono essere passati con quattro bit dall'agente proiezioni sua posizione vicino alle pareti. Se la mossa è di andare oltre un muro la mossa non è fatto e si è ritenuta non valida e se il movimento è fatto e se un nuovo muro si trova quindi l'idoneità va in su.

È giusto?

Answer 1

La risposta di BadHorse è buono se si vuole risolvere un labirinto specifico; è sufficiente intepret tua stringa di bit come un sequenza di precise istruzioni per guidare l'agente attraverso il labirinto. In questo caso la forma fisica non è la somma della stringa di bit (come indicare nella sua domanda), ma piuttosto un po 'di metrica misurare quanto successo l'agente era nella soluzione del problema. Per esempio, la vostra forma fisica potrebbe essere definito come " distanza in linea retta dalla fine del labirinto dopo l'elaborazione di 20 istruzioni ".

Quindi, al momento di valutare ogni singolo si permettono di elaborare i primi 20 istruzioni dalla stringa di bit e quindi calcolare la sua forma fisica, eseguire una crossover / mutazioni e quindi creare la prossima generazione di individui.

Se si desidera sviluppare il vostro agente per risolvere qualsiasi labirinto è necessario codificare le regole all'interno della vostra stringa di bit piuttosto che una sequenza di istruzioni. Si potrebbe definire regole basate sul fatto che una parete era immediatamente dietro, davanti, a sinistra oa destra del robot; per es.

FBLR Action
0000 Move Forward
0001 Move Forward
0010 Turn Right
etc

Questo vi dà una stringa di bit che consiste di 16 azioni, ogni azione codificato come 2 bit (00 = sposta in avanti, 01 = girare a destra, 10 = girare a sinistra, 11 = tornare indietro). Nel valutare il vostro agente determina semplicemente il suo stato attuale e utilizza la stringa di bit come una tabella di ricerca per determinare come si dovrebbe rispondere. E poi ripete questo un certo numero di volte dopo quel punto si valuta la sua forma fisica.

Dato questo codifica l'agente potrebbe valutare la regola gli esseri umani utilizzano in genere che è "Seguire la parete sinistra di continuo". Ovviamente questo approccio fallirà se il labirinto non è completamente collegata e in questo caso è necessario codificare più Stato nelle vostre regole approccio (ad esempio, l'agente potrebbe rispondere in modo diverso se andare oltre "vecchio campo").

La speranza che aiuta.

Modifica

In risposta alla sua ultima modifica:

Il fatto che ho codificato dell'agente "sensori" Rilevare se è vicino ad una parete o meno non è rilevante per la stringa di bit (il vostro gene), e forse ho le cose un po 'confuso con il mio esempio. Il gene codifica solo le azioni (andare avanti, etc.) non gli stati del sensore.

Si dovrebbe quindi scrivere il codice per look-up la parte relativa alla stringa di bit data una particolare combinazione di letture del sensore; per es.

/**
 * Enumeration describing the four available actions to the agent
 * and methods for decoding a given action from the "bit" string
 * (actually represented using booleans).
 */
public enum Action {
  MOVE_FORWARD, REVERSE, TURN_LEFT, TURN_RIGHT

  Action decodeAction(boolean b1, boolean b2) {
    Action ret;

    if (b1) {
      ret = b2 ? Action.MOVE_FORWARD : Action.TURN_LEFT;
    } else {
      ret = b2 ? Action.TURN_RIGHT : Action.REVERSE;
    }

    return ret;
  }
}

/**
 * Class encapsulating the 32-bit "bit string" represented using booleans.
 * Given the state of the four agent inputs the gene will provide a specific
 * action for the agent to perform.
 */
public class Gene {
  private final boolean[] values = new boolean[32];

  public Action getActionForSensorInputs(boolean wallInFront,
    boolean wallBehind, boolean wallToLeft, boolean wallToRight) {

    int i=0;

    // Encode the four sensor inputs as a single integer value by
    // bitwise-ORing each sensor value with a power of 2.
    // The encoded value will be in the range [0, 15].
    if (wallToRight) {
      i |= 0x01;
    }

    if (wallToLeft) {
      i |= 0x02;
    }

    if (wallBehind) {
      i |= 0x04;
    }

    if (wallInFront) {
      i |= 0x08;
    }

    // The look-up index is i * 2 because each action is encoded as 2
    // booleans.
    int index = i * 2;

    // Retrieve the two action bits from the bit string.
    boolean b1 = this.values[index];
    boolean b2 = this.values[index + 1];

    // Finally decode the action to perform.
    return Action.decodeAction(b1, b2);
  }

  // TODO: Add method to support crossover and mutation with other Genes.
}

Data questa semplice definizione di un Gene si potrebbe incorporare questa classe all'interno di un'implementazione Agent e registrare come l'agente esegue con il gene corrente "installato"; per es.

private enum Direction { NORTH, SOUTH, EAST, WEST };

public class Agent {
  private final Geneva gene;
  private final int x; // x position in maze;
  private final int y; // y position in maze;
  private Direction currentDirection;

  public double evaluate() {
    double fitness;

    // Perform up to 20 actions and then evaluate fitness.
    for (int i=0; i<20; ++i) {
      // TODO Determine sensor inputs.

      Action action = gene.getActionForSensorInputs(...);

      // TODO: Now apply action to update agent's state.
      // If agent has reached goal exit loop and return fitness 1.0 (max fitness).
      // If agent has exited the maze then exit loop and return 0.0 (min fitness).
    }

    // Calculate fitness after 100 steps taken.  For example could be
    // calculated as sqrt((goal.x - x) ^ 2 + (goal.y - y) ^ 2).

    return fitness;
  }
}

Answer 2

Se ho capito bene, è necessario determinare come le azioni del vostro bot nella GUI sono rappresentati dal risultato della vostra algoritmo genetico? Penso che la determinazione della rappresentazione che si desidera utilizzare dovrebbe essere il punto di partenza. Quindi è necessario creare una mappatura per ogni (gruppo di) 'geni' nel vostro individuo di una certa azione o di un certo cambiamento nell'algoritmo di movimento del vostro bot.

Non appena hai scelto una rappresentazione valida, l'attuazione sarà un po 'più logico.

Una molto semplice rappresentazione del movimento sarebbe quello di lasciare che i geni a livello di codice un determinato percorso. È possibile utilizzare blocchi di quattro geni per rappresentare le diverse direzioni, e poi un 0 rappresenta 'non si muovono in questa direzione' e 1 rappresenta in movimento.

Poi il 01001101 rappresentazione potrebbe essere tradotto come il seguente schema di movimento:

stand still
go one step east
stand still
stand still
go one step north
go one step east
stand still
go one step west