4

抱歉,如果我在移动设备上写这篇文章时不清楚,我正在努力让它快点。

我用二进制编码(基因)编写了一个基本的遗传算法,它建立了一个适应度值,并使用锦标赛选择、变异和交叉进行了多次迭代。作为一个基本的命令行示例,它似乎可以工作。

我遇到的问题是在 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 位以显示可用的动作,机器人移动这两个位需要从代理中传递四个位,显示其在墙壁附近的位置。如果移动是要越过墙,则移动不会被认为是无效的,如果移动被移动并且如果找到新的墙,那么适应度就会上升。

是对的吗?

4

2 回答 2

4

如果您想解决特定的迷宫,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.
}

给定这个简单的 a 定义,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;
  }
}
于 2010-02-18T12:25:02.810 回答
0

如果我理解正确,您需要确定您的机器人在 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
于 2010-02-18T11:56:09.647 回答