在 GUI 中使用 GA

Question

很抱歉，如果不清楚，因为我是在移动设备上写这篇文章的，并且我正在努力加快速度。

我编写了一个带有二进制编码（基因）的基本遗传算法，它构建了一个适应度值，并通过使用锦标赛选择、突变和交叉的多次迭代来进化。作为一个基本的命令行示例，它似乎可以工作。

我遇到的问题是在 GUI 中应用遗传算法，因为我正在编写一个迷宫求解程序，该程序使用 GA 来找到穿过迷宫的方法。如何将随机二进制编码基因和适应度函数（将所有二进制值加在一起）转变为控制迷宫周围机器人的方法？我用 Java 构建了一个基本的 GUI，由迷宫般的标签（如网格）组成，可用路线为蓝色，墙壁为黑色。

重申一下，我的 GA 表现良好，并且包含任何典型 GA 的功能（健身方法、获取和设置群体、选择、交叉等），但现在我需要将其插入 GUI 中才能运行我的迷宫。为了让机器人能够根据 GA 的指令向不同方向移动，需要做什么？如果可能的话，粗略的伪代码会很棒

根据要求，使用单独的类（Indiv）构建Individual，所有主要工作都在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 位以显示可用的操作，并且为了让机器人移动这两个位，需要从代理传递四个位来显示其靠近墙壁的位置。如果移动要越过墙壁，则不会进行移动，并且被视为无效；如果进行了移动并且发现了新的墙壁，则适应度会上升。

是这样吗？

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