java - 在 GUI 中使用 GA

Question

抱歉，如果这不是很清楚，因为我是在移动设备上写这篇文章，而且我正在努力让它更快。

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

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

重申一下，我的 GA 表现良好并且包含任何典型 GA 的功能(适应性方法、获取和设置种群、选择、交叉等)，但现在我需要将其插入 GUI 以运行我的迷宫。为了获得一个可以根据 GA 所说的内容向不同方向移动的机器人，需要去哪里？如果可能的话，粗糙的伪代码会很棒

根据要求，Individual 是使用单独的类 (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 位以显示可用的 Action ，为了让机器人移动，需要从代理传递两位，四位显示其在墙壁附近的位置。如果移动要越过一堵墙，则移动不会进行，并且被视为无效；如果移动进行了，并且如果找到了新的墙，则适应度会上升。

是这样吗？

Answer 1

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

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

如果您希望开发您的代理来解决任何迷宫，您需要在您的位串而不是指令序列中编码规则。您可以根据墙壁是否紧邻机器人的后方、前方、左侧或右侧来定义规则；例如

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

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

鉴于此编码，代理可以评估人类通常使用的规则，即“连续跟随左手墙”。显然，如果迷宫没有完全连接，这种方法就会失败，在这种情况下，您需要将更多状态编码到基于规则的方法中(例如，如果经过“旧地”，代理可能会做出不同的 react )。

希望对您有所帮助。

编辑

响应您最近的修改:

我已经对代理“传感器”进行编码以检测它是否靠近墙这一事实与位串(您的基因)无关，也许我与我的示例有些混淆。该基因只编码 Action (向前移动等)不传感器状态。

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

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