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