在GUI中使用GA

Question

抱歉，如果这不是很清楚，因为我正在移动设备上写这篇文章，我试图让它变得更快。

我已经用二进制编码(基因)写了一个基本的遗传算法，它建立了一个适应值，并通过几次迭代使用锦标赛选择，变异和交叉进化。作为一个基本的命令行示例，它似乎是有效的。

我遇到的问题是在GUI中应用遗传算法，因为我正在编写一个迷宫求解程序，该程序使用遗传算法通过迷宫找到方法。如何将随机二进制编码的基因和适应度函数(将所有二进制值相加)转换为控制机器人绕过迷宫的方法？我已经用Java构建了一个基本的GUI，它由一个迷宫般的标签(就像一个网格)组成，可用的路线用蓝色表示，墙壁用黑色表示。

重申一下，我的遗传算法执行得很好，包含了任何典型的遗传算法(适应度方法、获取和设置种群、选择、交叉等)，但现在我需要将其插入到GUI中来运行我的迷宫。为了让机器人可以根据GA的说法在不同的方向上移动，需要去哪里？如果可能的话，粗略的伪代码会更好。

按照要求，使用单独的类(Indiv)构建个体，所有主要工作都在Pop类中完成。当一个新的个体被实例化时，一个整型数组表示该个体的基因，这些基因是从0到1之间的数字中随机选取的。适应度函数只是将这些基因的值相加，并在Pop类中处理两个选定个体的选择、突变和交叉。没有太多其他的东西，命令行程序只显示了n代的进化，总的适应度在每次迭代中都在提高。

编辑:现在它开始变得更有意义了，尽管有一些事情困扰着我……

正如Adamski建议的那样，我想用下面显示的选项创建一个“代理”。我的问题是随机位串在哪里起作用。代理知道墙的位置，并将其布置在4位字符串(即0111)中，但这如何影响随机的32位字符串？(例如，10001011011001001010011011010101)如果我有以下迷宫(x是起点，2是目标，1是墙)：

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

如果我向左转，我面对的是错误的方向，如果智能体向前移动，它将完全离开迷宫。我假设第一代字符串是完全随机的，它会随着适应度的增长而演变，但我不知道字符串在迷宫中是如何工作的。

所以，为了弄清楚这件事...

当智能体能够移动并处于墙边时，适合性是结果。

这些基因是一个32位的字符串，分为16组，每组2位，以显示可用动作，机器人移动这两位需要从显示其靠近墙壁的位置的智能体传递4位。如果移动是要经过一堵墙，则不会进行移动，并且被认为是无效的；如果进行了移动，并且发现了新的墙，则适应度会上升。

是那么回事吗？

Answer 1

如果你想解决一个特定的迷宫，BadHorse的答案是很好的；你只需将你的位串解释为一个精确的指令的序列，以引导智能体通过迷宫。在这种情况下，您的适应度不是位字符串的总和(如您在问题中所述)，而是衡量代理在解决问题方面有多成功的某个度量。例如，你的适合度可能被定义为“在处理了20条指令后，从迷宫末端到直线的距离”。

因此，当评估每个个体时，您允许它处理来自您的位串的前20条指令，然后计算其适应度，执行任何交叉/突变，然后创建下一代个体。

如果你想开发你的代理来解决任何迷宫，你需要在你的位串中编码规则，而不是指令序列。你可以根据墙是在机器人的后面、前面、左边还是右边来定义规则；

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

这为您提供了一个由16个动作组成的位串，每个动作编码为2位(00 =向前移动，01 =右转，10 =向左转，11 =向后移动)。在评估代理时，它只是确定它的当前状态，并使用位串作为查找表来确定它应该如何响应。然后，它重复这一过程一定次数，然后评估其适合度。

考虑到这种编码，智能体可以评估人类通常使用的规则，即“不断地沿着左手边的墙走”。显然，如果迷宫没有完全连接，这种方法将失败，在这种情况下，你需要将更多的状态编码到基于规则的方法中(例如，如果走到“老地方”，智能体可能会做出不同的反应)。

希望这能有所帮助。

编辑

为回应您的最新编辑：

事实上，我已经编码了代理“传感器”来检测它是否靠近墙壁，这与位串(您的基因)无关，也许我有点混淆了我的示例。该基因只编码动作(向前移动等)，而不编码()传感器状态。

因此，您应该编写代码来查找给定传感器读数的特定组合的位串的相关部分；

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

根据这个简单的Gene定义，您可以将这个类嵌入到Agent实现中，并记录在当前基因“已安装”的情况下代理是如何执行的；

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

如果我理解正确的话，您需要确定您的机器人在GUI中的操作是如何由您的遗传算法的结果表示的？我认为确定你想要使用的表示形式应该是你的起点。因此，你需要为你的个体中的每一个(一组)“基因”创建一个映射到你的机器人的运动算法中的某个动作或某个变化。

一旦你选择了一个可行的表示，实现就会更符合逻辑。

运动的一个非常简单的表示是让基因硬编码特定的路线。你可以用四个基因块来代表不同的方向，然后0代表“不要朝这个方向移动”，1代表移动。

则表示01001101可以被转换为以下运动模式：

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