Usando GA na GUI

Question

Desculpe se isso não está claro, pois estou escrevendo em um dispositivo móvel e estou tentando ser rápido.

Eu escrevi um algoritmo genético básico com uma codificação binária (genes) que constrói um valor de aptidão e evolui através de várias iterações usando seleção de torneio, mutação e cruzamento.Como exemplo básico de linha de comando, parece funcionar.

O problema que tenho é aplicar um algoritmo genético em uma GUI enquanto escrevo um programa de solução de labirinto que usa o GA para encontrar um método através de um labirinto.Como faço para transformar meus genes codificados binários aleatórios e função de aptidão (adicionar todos os valores binários) em um método para controlar um bot em torno de um labirinto?Eu construí uma GUI básica em Java que consiste em um labirinto de rótulos (como uma grade) com as rotas disponíveis em azul e as paredes em preto.

Para reiterar, meu GA tem um bom desempenho e contém o que qualquer GA típico faria (método de aptidão, obtenção e definição de população, seleção, cruzamento, etc.), mas agora preciso conectá-lo a uma GUI para fazer meu labirinto funcionar.O que precisa ir aonde para obter um bot que possa se mover em direções diferentes dependendo do que o GA diz?Pseudocódigo aproximado seria ótimo, se possível

Conforme solicitado, um Individual é construído utilizando uma classe separada (Indiv), com todo o trabalho principal sendo feito em uma classe Pop.Quando um novo indivíduo é instanciado, uma matriz de inteiros representa os genes desse indivíduo, com os genes sendo escolhidos aleatoriamente em um número entre 0 e 1.A função de aptidão apenas soma o valor desses genes e na classe Pop trata da seleção, mutação e cruzamento de dois indivíduos selecionados.Não há muito mais, o programa de linha de comando apenas mostra a evolução ao longo de n gerações, com a aptidão total melhorando a cada iteração.

EDITAR:Está começando a fazer um pouco mais de sentido agora, embora haja algumas coisas que estão me incomodando...

Como Adamski sugeriu, quero criar um "Agente" com as opções mostradas abaixo.O problema que tenho é onde a sequência de bits aleatórios entra em ação aqui.O agente sabe onde estão as paredes e as organiza em uma string de 4 bits (ou seja,0111), mas como isso afeta a sequência aleatória de 32 bits?(ou seja,10001011011001001010011011010101) Se eu tiver o seguinte labirinto (x é o local de início, 2 é o objetivo, 1 é a parede):

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

Se eu virar à esquerda, estarei na direção errada e o agente sairá completamente do labirinto se avançar.Presumo que a primeira geração da corda será completamente aleatória e evoluirá à medida que a aptidão aumenta, mas não entendo como a corda funcionará dentro de um labirinto.

Então, para esclarecer isso...

A aptidão é o resultado de quando o agente consegue se movimentar e está encostado em uma parede.

Os genes são uma sequência de 32 bits, divididos em 16 conjuntos de 2 bits para mostrar as ações disponíveis e para o robô se mover os dois bits precisam ser passados ​​com quatro bits do agente mostrando sua posição próximo às paredes.Se o movimento for ultrapassar uma parede, o movimento não é feito e é considerado inválido e se o movimento for feito e se uma nova parede for encontrada, a aptidão aumenta.

Isso está certo?

Answer 1

A resposta de BadHorse é boa se você deseja resolver um labirinto específico;você simplesmente interpreta sua sequência de bits como um seqüência de preciso instruções para guiar o agente pelo labirinto.Nesse caso, sua aptidão não é a soma da sequência de bits (como você afirma em sua pergunta), mas sim alguma métrica que mede o sucesso do agente na resolução do problema.Por exemplo, seu condicionamento físico pode ser definido como "distância em linha reta do final do labirinto após processar 20 instruções".

Portanto, ao avaliar cada indivíduo, você permite que ele processe as primeiras 20 instruções de sua sequência de bits e, em seguida, calcule sua aptidão, execute quaisquer cruzamentos/mutações e, em seguida, crie a próxima geração de indivíduos.

Se você deseja desenvolver seu agente para resolver qualquer labirinto você precisa codificar regras em sua sequência de bits, em vez de uma sequência de instruções.Você pode definir regras com base no fato de uma parede estar imediatamente atrás, na frente, à esquerda ou à direita do robô;por exemplo.

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

Isso fornece uma sequência de bits que consiste em 16 ações, cada ação codificada como 2 bits (00 = Mover para frente, 01 = Vire à direita, 10 = Vire à esquerda, 11 = Mover para trás).Ao avaliar seu agente, ele simplesmente determina seu estado atual e usa a sequência de bits como uma tabela de pesquisa para determinar como ele deve responder.Em seguida, ele repete isso um certo número de vezes, após o qual você avalia sua adequação.

Dada esta codificação, o agente poderia avaliar a regra que os humanos normalmente usam, que é "Siga continuamente a parede esquerda".Obviamente, esta abordagem falhará se o labirinto não estiver totalmente conectado e, neste caso, você precisará codificar mais estados em sua abordagem baseada em regras (por exemplo,o agente poderia responder de forma diferente se passasse por "terreno antigo").

Espero que ajude.

EDITAR

Em resposta à sua última edição:

O fato de eu ter codificado os "sensores" do agente que detectam se ele está próximo a uma parede ou não não é relevante para a sequência de bits (seu gene), e talvez eu tenha confundido um pouco as coisas com meu exemplo.O gene apenas codifica as ações (avançar, etc.) não o sensor afirma.

Você deve, portanto, escrever um código para procurar a parte relevante da sequência de bits, dada uma combinação específica de leituras de sensores;por exemplo.

/**
 * 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.
}

Dada esta definição simples de um Gene você poderia incorporar esta classe dentro de um Agent implementação e registro do desempenho do agente com o gene atual “instalado”;por exemplo.

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 bem entendi, você precisa determinar como as ações do seu bot na GUI são representadas pelo resultado do seu algoritmo genético?Acho que determinar a representação que você deseja usar deve ser o seu ponto de partida.Portanto, você precisa criar um mapeamento para cada (grupo de) 'genes' do seu indivíduo para uma determinada ação ou uma determinada mudança no algoritmo de movimento do seu bot.

Assim que você escolher uma representação viável, a implementação será um pouco mais lógica.

Uma representação muito simples do movimento seria deixar os genes codificarem uma determinada rota.Você pode usar blocos de quatro genes para representar as diferentes direções, e então um 0 representa “não se mova nesta direção” e um 1 representa movimento.

Então a representação 01001101 pode ser traduzido como o seguinte padrão de 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