Chapter 3 |
Introduction
In this chapter, we are going to use the knowledge we gained from the previous chapter to solve a real world problem using a genetic algorithm. The real world problem we will be working on is designing robotic controllers.
Genetic algorithms are often applied to robotics as a method of designing sophisticated robotic controllers that enable a robot to perform complex tasks and behaviors, removing the need to manually code a complicated robotic controller. Imagine you have built a robot that can transport goods around a warehouse. You have installed sensors, which allow the robot to see its local environment, and you have given it wheels so it can navigate based on input from its sensors. The problem is how you can link the sensor data to motor actions so that the robot can navigate the warehouse.
The field of artificial intelligence where genetic algorithms, and more generally, the ideas of Darwinian evolution are applied to robotics is referred to as evolutionary robotics. This isn’t the only bottom-up approach used for this problem, however. Neural networks are also frequently used to successfully map robotic sensors to outputs by using reinforcement-learning algorithms to guide the learning process.
Typically, a genetic algorithm will evaluate a large population of individuals to locate the best individuals for the next generation. Evaluating an individual is done by running a fitness function that gauges the performance of an individual based on certain pre-defined criteria. However, applying genetic algorithms and their fitness functions to physical robots gives rise to a new challenge; physically evaluating each robotic controller isn’t feasible for large populations. This is due to the difficulty in physically testing each robotic controller and the time it would take to do so. For this reason, robotic controllers are typically evaluated by applying them to simulated models of real, physical robots and environments. This enables quick evaluations of each controller in software that later can be applied to their physical counterparts. In this chapter, we will use our knowledge of binary genetic algorithms to design a robotic controller and begin applying it to a virtual robot in a virtual environment.
The Problem
The problem we are going to solve is designing a robotic controller that can use the robots sensors to navigate a robot successfully through a maze. The robot can take four actions: move one-step forward, turn left, turn right, or, rarely, do nothing. The robot also has six sensors: three on the front, one on the left, one on the right and one on the back.
The maze we are going to explore is comprised of walls that the robot can’t cross and will have an outlined route, shown in Figure 3-1, which we want the robot to follow. Keep in mind that the purpose of this chapter isn’t to train a robot to solve mazes. Our purpose is to automatically program a robot controller with six sensors so that it doesn’t crash into walls; we’re simply using the maze as a complicated environment in which to test our robot controller.
Figure 3-1. The route we want the robot to follow
The robot’s sensors will activate whenever they detect a wall adjacent to the sensor. For example, the robot’s front sensor will activate if it detects a wall in front of the robot.
Implementation
Before You Start
This chapter will build on the code you developed in Chapter 2. Before you start, create a new Eclipse or NetBeans project, or create a new package in your existing project for this book called “chapter3”.
Copy the Individual, Population, and GeneticAlgorithm classes over from Chapter 2 and import them into chapter 3. Make sure to update the package name at the top of each class file! They should all say “package chapter3” at the very top.
In this chapter, you won’t have to modify the Individual and Population classes at all, except for changing the package name to “chapter3”.
However, you will be modifying several methods in the GeneticAlgorithm class. At this point, you should completely delete the following five methods: calcFitness, evalPopulation, isTerminationConditionMet, selectParent, and crossoverPopulation. You’ll rewrite these five methods throughout this chapter, and deleting them right now will help ensure you don’t accidentally reuse Chapter 2’s implementations.
You’ll also be creating a few additional classes this chapter (Robot and Maze, and also the executive RobotController class that contains the program’s main method). If you’re working in Eclipse, it’s easy to create a new class via the File 
New Class menu option. Pay attention to the package name field and make sure it says “chapter3”.
Encoding
Encoding data the right way can often be the trickiest aspect of a genetic algorithm. Let’s start by first defining the problem: we need a binary representation of the robot controller’s complete instruction set for all possible combinations of inputs.
As discussed earlier, our robot will have four actions: do nothing, move forward one step, turn left and turn right. These can be represented in binary as:
- “00”: do nothing
- “01”: move forward
- “10”: turn left
- “11”: turn right
We also have six different on/off sensors giving us 26 (64) possible combinations of sensor inputs. If each action requires 2 bits to encode, we can represent the controller’s response to any possible input in 128 bits. Phrased another way, we have 64 different scenarios our robot can find itself in, and our controller needs to have an action defined for each scenario. Since an action requires two bits, our controller requires 64*2 = 128 bits of storage.
Since genetic algorithm chromosomes are easiest to manipulate as arrays, our chromosome will be a bit array of length 128. In this scenario, with our mutation and crossover methods you don’t need to worry about which particular instruction they’re modifying, they just get to manipulate genetic code. On our end, however, we’ll have to unpack the encoded data before we can use it in the robot controller.
Given that 128 bits is our requirement for representing instructions for 64 different sensor combinations, how should we actually structure the chromosome so that we can pack and unpack it? That is, which combination of sensor inputs does each section of the chromosome correspond to? In what order are the actions? Where can we find the action for the situation “front and front-right sensors are activated” within the chromosome? The bits in the chromosome represent output, but how is input represented?
This will be an unintuitive question (and solution) to many people, so let’s move toward the solution in small steps. The first step might be to consider a simple, human readable list of inputs and outputs:
Sensor #1 (front): on
Sensor #2 (front-left): off
Sensor #3 (front-right): on
Sensor #4 (left): off
Sensor #5 (right): off
Sensor #6 (back): off
Instruction: turn left (action “10” as defined above)
With an additional 63 entries to represent all possible combinations, this format is unwieldy. It’s clear that this type of enumeration won’t work for us. Let’s take another small step by abbreviating everything and translating “on” and “off” to 1 and 0:
#1: 1
#2: 0
#3: 1
#4: 0
#5: 0
#6: 0
Instruction: 10
We’re making progress, but this still doesn’t pack 64 instructions into a 128-bit array. Our next step is to take the six sensor values – the inputs – and encode those further. Let’s line them up from right to left, and drop the word “Instruction” from the output:
#6:0, #5:0, #4:0, #3:1, #2:0, #1:1 => 10
Now let’s drop the numbering of the sensors:
000101 => 10
If we now convert the sensor values’ bit string to decimal, we get the following:
5 => 10
Now we’re onto something. The “5” on the left hand side represents the sensor inputs, and the “10” on the right represents what the robot should do when faced with those inputs (the output). Because we got here from a binary representation of the sensor inputs, there’s only one combination of sensors that can give us the number 5.
We can use the number 5 as the position in the chromosome that represents a combination of sensor inputs. If we were building this chromosome by hand, and we knew that “10” (turn left) is the correct response to “5” (front and front-right sensors detecting a wall), we would place “1” and “0” in the 11th and 12th spots in the chromosome (each action requires 2 bits, and we start counting positions from 0), like so:
xx xx xx xx xx 10 xx xx xx xx (... 54 more pairs...)
In the above fake chromosome, the first pair (position 0) represents the action to take when the sensor inputs total is 0: everything off. The second pair (position 1) represents the action to take when the sensor inputs total 1: only the front sensor detects a wall. The third pair, position 2, represents only the front-left sensor triggered. The fourth pair, position 3, represents both the front and the front-left sensor being active. And so on, until you get to the final pair, position 63, which represents all sensors being triggered.
Another visualization of this encoding scheme is represented in Figure 3-2. The left-most “Sensors” column represents the sensors’ bitfield, which maps to a chromosome position after you convert the bitfield to decimal. Once you’ve converted the sensors’ bitfield to decimal, you can place the desired action at the corresponding location in the chromosome.
Figure 3-2. Mapping the sensor values to actions
This encoding scheme may seem obtuse at first – and the chromosome is not human-readable – but it has a couple of helpful properties. First, the chromosome can be manipulated as an array of bits, rather than a complicated tree structure or hashmap, which makes crossover, mutation and other manipulations much easier. Secondly, every 128-bit value is a valid solution (though not necessarily a good one) – more on this later in the chapter.
Figure 3-2 describes how a typical chromosome can map the robot’s sensor values to actions.
Initialization
In this implementation, we first need to create and initialize a maze to run the robot in. To do this, create the following Maze class to manage the maze. This can be done with the following code. Create a new class in Eclipse by selecting File New Class, and make sure to use the correct package name, especially if you’ve copied files over from Chapter 2.
package chapter3;
import java.util.ArrayList;
public class Maze {
private final int maze[][];
private int startPosition[] = { -1, -1 };
public Maze(int maze[][]) {
this.maze = maze;
}
public int[] getStartPosition() {
// Check if we’ve already found start position
if (this.startPosition[0] != -1 && this.startPosition[1] != -1) {
return this.startPosition;
}
// Default return value
int startPosition[] = { 0, 0 };
// Loop over rows
for (int rowIndex = 0; rowIndex < this.maze.length; rowIndex++) {
// Loop over columns
for (int colIndex = 0; colIndex < this.maze[rowIndex].length; colIndex++) {
// 2 is the type for start position
if (this.maze[rowIndex][colIndex] == 2) {
this.startPosition = new int[] { colIndex, rowIndex };
return new int[] { colIndex, rowIndex };
}
}
}
return startPosition;
}
public int getPositionValue(int x, int y) {
if (x < 0 || y < 0 || x >= this.maze.length || y >= this.maze[0].length) {
return 1;
}
return this.maze[y][x];
}
public boolean isWall(int x, int y) {
return (this.getPositionValue(x, y) == 1);
}
public int getMaxX() {
return this.maze[0].length - 1;
}
public int getMaxY() {
return this.maze.length - 1;
}
public int scoreRoute(ArrayList<int[]> route) {
int score = 0;
boolean visited[][] = new boolean[this.getMaxY() + 1][this.getMaxX() + 1];
// Loop over route and score each move
for (Object routeStep : route) {
int step[] = (int[]) routeStep;
if (this.maze[step[1]][step[0]] == 3 && visited[step[1]][step[0]] == false) {
// Increase score for correct move
score++;
// Remove reward
visited[step[1]][step[0]] = true;
}
}
return score;
}
}
This code contains a constructor to create a new maze from a double int array and public methods to get the start position, check a position’s value and score a route through the maze.
The scoreRoute method is the most significant method in the Maze class; it evaluates a route taken by the robot and returns a fitness score based on the number of correct tiles it stepped on. The score returned by this scoreRoute method is what we’ll use as the individual’s fitness score in the GeneticAlgorithm class’ calcFitness method later.
Now that we have a maze abstraction, we can create our executive class – the class that actually executes the algorithm – and initialize the maze that was shown in Figure 3-1. Create another new class called RobotController, and create the “main” method that the program will boot from.
package chapter3;
public class RobotController {
public static int maxGenerations = 1000;
public static void main(String[] args) {
/**
* 0 = Empty
* 1 = Wall
* 2 = Starting position
* 3 = Route
* 4 = Goal position
*/
Maze maze = new Maze(new int[][] {
{ 0, 0, 0, 0, 1, 0, 1, 3, 2 },
{ 1, 0, 1, 1, 1, 0, 1, 3, 1 },
{ 1, 0, 0, 1, 3, 3, 3, 3, 1 },
{ 3, 3, 3, 1, 3, 1, 1, 0, 1 },
{ 3, 1, 3, 3, 3, 1, 1, 0, 0 },
{ 3, 3, 1, 1, 1, 1, 0, 1, 1 },
{ 1, 3, 0, 1, 3, 3, 3, 3, 3 },
{ 0, 3, 1, 1, 3, 1, 0, 1, 3 },
{ 1, 3, 3, 3, 3, 1, 1, 1, 4 }
});
/**
* We’ll implement the genetic algorithm pseudocode
* from chapter 2 here....
*/
}
}
The maze object we’ve created uses integers to represent different terrain types: 1 defines a wall; 2 is the starting position, 3 traces the best route through the maze, 4 is the goal position and 0 is an empty position that the robot can travel over but isn’t on the route to the goal.
Next, similarly to our previous implementation, we need to initialize a population of random individuals. Each of these individuals should have a chromosome length of 128. As explained earlier, 128 bits allows for us to map all 64 inputs to an action. Since it’s not possible to create an invalid chromosome for this problem, we can use the same random initialization as before – recall that this random initialization occurs in the Individual class constructor, which we copied un-modified from Chapter 2. A robot initialized in such a manner will simply take random actions when presented with different situations, and through generations of evolution, we hope to refine this behavior.
Before stubbing out the familiar genetic algorithm pseudocode from Chapter 2 in our main method, we should make one modification to the GeneticAlgorithm class that we copied from Chapter 2. We’re going to add a property called “tournamentSize” – which we’ll discuss in depth later in this chapter – to the GeneticAlgorithm class and constructor.
Modify the top of your GeneticAlgorithm class to look like this:
package chapter3;
public class GeneticAlgorithm {
/**
* See chapter2/GeneticAlgorithm for a description of these properties.
*/
private int populationSize;
private double mutationRate;
private double crossoverRate;
private int elitismCount;
/**
* A new property we’ve introduced is the size of the population used for
* tournament selection in crossover.
*/
protected int tournamentSize;
public GeneticAlgorithm(int populationSize, double mutationRate, double crossoverRate, int elitismCount,
int tournamentSize) {
this.populationSize = populationSize;
this.mutationRate = mutationRate;
this.crossoverRate = crossoverRate;
this.elitismCount = elitismCount;
this.tournamentSize = tournamentSize;
}
/**
* We’re not going to show the rest of the class here,
* but methods like initPopulation, mutatePopulation,
* and evaluatePopulation should appear below.
*/
}
We’ve made three simple changes: first, we’ve added “protected int tournamentSize” to the class properties. Second, we’ve added “int tournamentSize” as the fifth argument to the constructor. Finally, we’ve added the “this.tournamentSize = tournamentSize” assignment to the constructor.
With the tournamentSize property handled, we can move forward and stub out our pseudocode from Chapter 2. As always, this code will go in the “main” method of the executive class, which in this case we named RobotController.
The code below won’t do anything, of course – we haven’t implemented any of the methods we need yet and have replaced everything with TODO comments. But stubbing the main method out in this manner helps to reinforce the conceptual execution model of a genetic algorithm, and also helps us keep on track in terms of methods we still need to implement; there are seven TODOs in this class that need to be resolved.
Update your RobotController class to look like the following. The maze definition is the same as before, but everything below it is a new addition to this file.
package chapter3;
public class RobotController {
public static int maxGenerations = 1000;
public static void main(String[] args) {
Maze maze = new Maze(new int[][] {
{ 0, 0, 0, 0, 1, 0, 1, 3, 2 },
{ 1, 0, 1, 1, 1, 0, 1, 3, 1 },
{ 1, 0, 0, 1, 3, 3, 3, 3, 1 },
{ 3, 3, 3, 1, 3, 1, 1, 0, 1 },
{ 3, 1, 3, 3, 3, 1, 1, 0, 0 },
{ 3, 3, 1, 1, 1, 1, 0, 1, 1 },
{ 1, 3, 0, 1, 3, 3, 3, 3, 3 },
{ 0, 3, 1, 1, 3, 1, 0, 1, 3 },
{ 1, 3, 3, 3, 3, 1, 1, 1, 4 }
});
// Create genetic algorithm
GeneticAlgorithm ga = new GeneticAlgorithm(200, 0.05, 0.9, 2, 10);
Population population = ga.initPopulation(128);
// TODO: Evaluate population
int generation = 1;
// Start evolution loop
while (/* TODO */ false) {
// TODO: Print fittest individual from population
// TODO: Apply crossover
// TODO: Apply mutation
// TODO: Evaluate population
// Increment the current generation
generation++;
}
// TODO: Print results
}
}
There are only slight differences between this RobotController class and the AllOnesGA class from Chapter 2. The AllOnesGA class didn’t have the “maxGenerations” property, because we knew exactly what the target fitness score was. In this case, however, we’ll learn about a different way to end the evolution loop. The AllOnesGA class didn’t need a Maze class either, but you’ll often find supporting classes like Maze in real genetic algorithm problems. Additionally, this version of the GeneticAlgorithm class takes 5 parameters, not 4, because we’re expecting to introduce a new concept called “tournament selection” in this chapter. Finally, the chromosome length in this example is 128 as opposed to 50 as in Chapter 2. In the last chapter, the chromosome length was arbitrary, but in this case, the chromosome length is meaningful and dictated by the encoding method discussed earlier.
Evaluation
In the evaluation phase, we need to define a fitness function that can evaluate each robotic controller. We can do this by increasing the individual’s fitness for each correct unique move made on the route. Recall that the Maze class we created earlier has a scoreRoute method that performs this evaluation. However, the route itself comes from a robot under autonomous control. So, before we can give the Maze class a route to evaluate, we need to create a Robot that can follow instructions and generate a route by executing those instructions.
Create a Robot class to manage the robot’s functionality. In Eclipse, you can create a new class by selecting the menu option File New Class. Make sure to use the correct package name. Add this code to the file:
package chapter3;
import java.util.ArrayList;
/**
* A robot abstraction. Give it a maze and an instruction set, and it will
* attempt to navigate to the finish.
*
* @author bkanber
*
*/
public class Robot {
private enum Direction {NORTH, EAST, SOUTH, WEST};
private int xPosition;
private int yPosition;
private Direction heading;
int maxMoves;
int moves;
private int sensorVal;
private final int sensorActions[];
private Maze maze;
private ArrayList<int[]> route;
/**
* Initalize a robot with controller
*
* @param sensorActions The string to map the sensor value to actions
* @param maze The maze the robot will use
* @param maxMoves The maximum number of moves the robot can make
*/
public Robot(int[] sensorActions, Maze maze, int maxMoves){
this.sensorActions = this.calcSensorActions(sensorActions);
this.maze = maze;
int startPos[] = this.maze.getStartPosition();
this.xPosition = startPos[0];
this.yPosition = startPos[1];
this.sensorVal = -1;
this.heading = Direction.EAST;
this.maxMoves = maxMoves;
this.moves = 0;
this.route = new ArrayList<int[]>();
this.route.add(startPos);
}
/**
* Runs the robot’s actions based on sensor inputs
*/
public void run(){
while(true){
this.moves++;
// Break if the robot stops moving
if (this.getNextAction() == 0) {
return;
}
// Break if we reach the goal
if (this.maze.getPositionValue(this.xPosition, this.yPosition) == 4) {
return;
}
// Break if we reach a maximum number of moves
if (this.moves > this.maxMoves) {
return;
}
// Run action
this.makeNextAction();
}
}
/**
* Map robot’s sensor data to actions from binary string
*
* @param sensorActionsStr Binary GA chromosome
* @return int[] An array to map sensor value to an action
*/
private int[] calcSensorActions(int[] sensorActionsStr){
// How many actions are there?
int numActions = (int) sensorActionsStr.length / 2;
int sensorActions[] = new int[numActions];
// Loop through actions
for (int sensorValue = 0; sensorValue < numActions; sensorValue++){
// Get sensor action
int sensorAction = 0;
if (sensorActionsStr[sensorValue*2] == 1){
sensorAction += 2;
}
if (sensorActionsStr[(sensorValue*2)+1] == 1){
sensorAction += 1;
}
// Add to sensor-action map
sensorActions[sensorValue] = sensorAction;
}
return sensorActions;
}
/**
* Runs the next action
*/
public void makeNextAction(){
// If move forward
if (this.getNextAction() == 1) {
int currentX = this.xPosition;
int currentY = this.yPosition;
// Move depending on current direction
if (Direction.NORTH == this.heading) {
this.yPosition += -1;
if (this.yPosition < 0) {
this.yPosition = 0;
}
}
else if (Direction.EAST == this.heading) {
this.xPosition += 1;
if (this.xPosition > this.maze.getMaxX()) {
this.xPosition = this.maze.getMaxX();
}
}
else if (Direction.SOUTH == this.heading) {
this.yPosition += 1;
if (this.yPosition > this.maze.getMaxY()) {
this.yPosition = this.maze.getMaxY();
}
}
else if (Direction.WEST == this.heading) {
this.xPosition += -1;
if (this.xPosition < 0) {
this.xPosition = 0;
}
}
// We can’t move here
if (this.maze.isWall(this.xPosition, this.yPosition) == true) {
this.xPosition = currentX;
this.yPosition = currentY;
}
else {
if(currentX != this.xPosition || currentY != this.yPosition) {
this.route.add(this.getPosition());
}
}
}
// Move clockwise
else if(this.getNextAction() == 2) {
if (Direction.NORTH == this.heading) {
this.heading = Direction.EAST;
}
else if (Direction.EAST == this.heading) {
this.heading = Direction.SOUTH;
}
else if (Direction.SOUTH == this.heading) {
this.heading = Direction.WEST;
}
else if (Direction.WEST == this.heading) {
this.heading = Direction.NORTH;
}
}
// Move anti-clockwise
else if(this.getNextAction() == 3) {
if (Direction.NORTH == this.heading) {
this.heading = Direction.WEST;
}
else if (Direction.EAST == this.heading) {
this.heading = Direction.NORTH;
}
else if (Direction.SOUTH == this.heading) {
this.heading = Direction.EAST;
}
else if (Direction.WEST == this.heading) {
this.heading = Direction.SOUTH;
}
}
// Reset sensor value
this.sensorVal = -1;
}
/**
* Get next action depending on sensor mapping
*
* @return int Next action
*/
public int getNextAction() {
return this.sensorActions[this.getSensorValue()];
}
/**
* Get sensor value
*
* @return int Next sensor value
*/
public int getSensorValue(){
// If sensor value has already been calculated
if (this.sensorVal > -1) {
return this.sensorVal;
}
boolean frontSensor, frontLeftSensor, frontRightSensor, leftSensor, rightSensor, backSensor;
frontSensor = frontLeftSensor = frontRightSensor = leftSensor = rightSensor = backSensor = false;
// Find which sensors have been activated
if (this.getHeading() == Direction.NORTH) {
frontSensor = this.maze.isWall(this.xPosition, this.yPosition-1);
frontLeftSensor = this.maze.isWall(this.xPosition-1, this.yPosition-1);
frontRightSensor = this.maze.isWall(this.xPosition+1, this.yPosition-1);
leftSensor = this.maze.isWall(this.xPosition-1, this.yPosition);
rightSensor = this.maze.isWall(this.xPosition+1, this.yPosition);
backSensor = this.maze.isWall(this.xPosition, this.yPosition+1);
}
else if (this.getHeading() == Direction.EAST) {
frontSensor = this.maze.isWall(this.xPosition+1, this.yPosition);
frontLeftSensor = this.maze.isWall(this.xPosition+1, this.yPosition-1);
frontRightSensor = this.maze.isWall(this.xPosition+1, this.yPosition+1);
leftSensor = this.maze.isWall(this.xPosition, this.yPosition-1);
rightSensor = this.maze.isWall(this.xPosition, this.yPosition+1);
backSensor = this.maze.isWall(this.xPosition-1, this.yPosition);
}
else if (this.getHeading() == Direction.SOUTH) {
frontSensor = this.maze.isWall(this.xPosition, this.yPosition+1);
frontLeftSensor = this.maze.isWall(this.xPosition+1, this.yPosition+1);
frontRightSensor = this.maze.isWall(this.xPosition-1, this.yPosition+1);
leftSensor = this.maze.isWall(this.xPosition+1, this.yPosition);
rightSensor = this.maze.isWall(this.xPosition-1, this.yPosition);
backSensor = this.maze.isWall(this.xPosition, this.yPosition-1);
}
else {
frontSensor = this.maze.isWall(this.xPosition-1, this.yPosition);
frontLeftSensor = this.maze.isWall(this.xPosition-1, this.yPosition+1);
frontRightSensor = this.maze.isWall(this.xPosition-1, this.yPosition-1);
leftSensor = this.maze.isWall(this.xPosition, this.yPosition+1);
rightSensor = this.maze.isWall(this.xPosition, this.yPosition-1);
backSensor = this.maze.isWall(this.xPosition+1, this.yPosition);
}
// Calculate sensor value
int sensorVal = 0;
if (frontSensor == true) {
sensorVal += 1;
}
if (frontLeftSensor == true) {
sensorVal += 2;
}
if (frontRightSensor == true) {
sensorVal += 4;
}
if (leftSensor == true) {
sensorVal += 8;
}
if (rightSensor == true) {
sensorVal += 16;
}
if (backSensor == true) {
sensorVal += 32;
}
this.sensorVal = sensorVal;
return sensorVal;
}
/**
* Get robot’s position
*
* @return int[] Array with robot’s position
*/
public int[] getPosition(){
return new int[]{this.xPosition, this.yPosition};
}
/**
* Get robot’s heading
*
* @return Direction Robot’s heading
*/
private Direction getHeading(){
return this.heading;
}
/**
* Returns robot’s complete route around the maze
*
* @return ArrayList<int> Robot’s route
*/
public ArrayList<int[]> getRoute(){
return this.route;
}
/**
* Returns route in printable format
*
* @return String Robot’s route
*/
public String printRoute(){
String route = "";
for (Object routeStep : this.route) {
int step[] = (int[]) routeStep;
route += "{" + step[0] + "," + step[1] + "}";
}
return route;
}
}
This class contains the constructor to create a new Robot. It also contains functions to read the robot’s sensors, to get the robot’s heading and to move the robot around the maze. This Robot class is our way of simulating a simple robot so that we don’t have to run 1,000 generations of evolution on a population of 100 actual robots. You’ll often find classes like Maze and Robot in optimization problems like these, where it’s cost effective to simulate via software before refining your results in production hardware.
Recall that it’s technically the Maze class that evaluates the fitness of a route. However, we still need to implement the calcFitness method in our GeneticAlgorithm class. Rather than calculating the fitness score directly, the calcFitness method is responsible for tying together the Individual, Robot, and Maze classes by creating a new Robot with the Individual’s chromosome (i.e., sensor controller instruction set) and evaluating it against our Maze.
Write the following calcFitness function in the GeneticAlgorithm class. As always, this method can go anywhere in the class.
public double calcFitness(Individual individual, Maze maze) {
int[] chromosome = individual.getChromosome();
Robot robot = new Robot(chromosome, maze, 100);
robot.run();
int fitness = maze.scoreRoute(robot.getRoute());
individual.setFitness(fitness);
return fitness;
}
Here, the calcFitness method accepts two parameters, individual and maze, which it uses to create a new robot and run it through the maze. The robot’s route is then scored and stored as the individual’s fitness.
This code will create a robot, place it in our maze and test it using the evolved controller. The final parameter of the Robot constructor is the max number of moves the robot is allowed to make. This will prevent it from getting stuck in dead ends, or moving around in never ending circles. We can then simply take the score of the robot’s route and return it as the fitness using Maze’s scoreRoute method.
With a working calcFitness method, we can now create an evalPopulation method. Recall from Chapter 2 that the evalPopulation method simply loops over each individual in the population and calls calcFitness for that individual, summing the total population fitness as it goes. In fact, this chapter’s evalPopulation is almost equivalent to Chapter 2’s – but in this case, we also need to pass the maze object to the calcFitness method, so we need a slight modification.
Add the following method to the GeneticAlgorithm class, anywhere you like:
public void evalPopulation(Population population, Maze maze) {
double populationFitness = 0;
for (Individual individual : population.getIndividuals()) {
populationFitness += this.calcFitness(individual, maze);
}
population.setPopulationFitness(populationFitness);
}
The only difference between this version and Chapter 2’s version is the inclusion of “Maze maze” as the second parameter, and also the passing of “maze” as the second parameter to calcFitness.
At this point, you can resolve the two “TODO: Evaluate population” lines in the RobotController’s “main” method. Find the two locations that show:
// TODO: Evaluate population
and replace them with:
// Evaluate population
ga.evalPopulation(population, maze);
Unlike Chapter 2, this method requires passing the maze object as the second parameter. At this point, you should only have five “TODO” comments left in RobotController’s main method. We’ll quickly take care of three more of them in the next section. That’s progress!
Termination Check
The termination check we will use for this implementation is slightly different from the one used in our previous genetic algorithm. Here, we are going to terminate after a maximum number of generations have passed.
To add this termination check, begin by adding the following isTerminationConditionMet method to the GeneticAlgorithm class.
public boolean isTerminationConditionMet(int generationsCount, int maxGenerations) {
return (generationsCount > maxGenerations);
}
This method simply accepts the current generation counter and the maximum generations allowed and returns true or false depending on if the algorithm should terminate or not. Truthfully, this is simple enough that we could use the logic directly in the genetic algorithm loop’s “while” condition – however, in favor of consistency, we’ll always implement the termination condition check as a method in the GeneticAlgorithm class, even if it’s a trivial method like the one above.
Now we can apply our termination check to the evolution loop by adding the following code to RobotController’s main method. We simply pass through the number of generations and the maximum number of generations as parameters.
By adding the termination condition to the “while” statement you’re essentially making the loop functional, so we should also take this opportunity to print out some stats and debug information.
The changes below are straightforward: first, update the “while” conditional to use ga.isTerminationConditionMet. Second, add calls to population.getFittest and System.out.println both in the loop and after it in order to display progress and results.
Here’s what the RobotController class should look like at this point; we’ve just eliminated three more TODOs and only have two left:
package chapter3;
public class RobotController {
public static int maxGenerations = 1000;
public static void main(String[] args) {
Maze maze = new Maze(new int[][] {
{ 0, 0, 0, 0, 1, 0, 1, 3, 2 },
{ 1, 0, 1, 1, 1, 0, 1, 3, 1 },
{ 1, 0, 0, 1, 3, 3, 3, 3, 1 },
{ 3, 3, 3, 1, 3, 1, 1, 0, 1 },
{ 3, 1, 3, 3, 3, 1, 1, 0, 0 },
{ 3, 3, 1, 1, 1, 1, 0, 1, 1 },
{ 1, 3, 0, 1, 3, 3, 3, 3, 3 },
{ 0, 3, 1, 1, 3, 1, 0, 1, 3 },
{ 1, 3, 3, 3, 3, 1, 1, 1, 4 }
});
// Create genetic algorithm
GeneticAlgorithm ga = new GeneticAlgorithm(200, 0.05, 0.9, 2, 10);
Population population = ga.initPopulation(128);
// Evaluate population
ga.evalPopulation(population, maze);
int generation = 1;
// Start evolution loop
while (ga.isTerminationConditionMet(generation, maxGenerations) == false) {
// Print fittest individual from population
Individual fittest = population.getFittest(0);
System.out.println("G" + generation + " Best solution (" + fittest.getFitness() + "): " + fittest.toString());
// TODO: Apply crossover
// TODO: Apply mutation
// Evaluate population
ga.evalPopulation(population, maze);
// Increment the current generation
generation++;
}
System.out.println("Stopped after " + maxGenerations + " generations.");
Individual fittest = population.getFittest(0);
System.out.println("Best solution (" + fittest.getFitness() + "): " + fittest.toString());
}
}
If you were to hit the Run button now, you’d watch the algorithm quickly loop through 1,000 generations (with no actual evolution!) and proudly present to you a very, very bad solution with a fitness of, statistically speaking, most likely 1.0.
This is unsurprising; we still haven’t implemented crossover or mutation! As you learned in Chapter 2, you need at least one of those mechanisms to drive evolution forward, but generally, you want both in order to avoid getting stuck in a local optimum.
We have two TODOs left in the main method above, and fortunately, we can resolve one of them very quickly. The mutation technique we learned in Chapter 2 – bit flip mutation – is also valid for this problem.
When evaluating the feasibility of a mutation or crossover algorithm, you must first consider the constraints on what’s considered a valid chromosome. In this case, for this specific problem, a valid chromosome only has two constraints: it must be binary, and it must be 128 bits long. As long as those two constraints are met, there is no combination or sequence of bits that is considered invalid. So, we’re able to reuse our simple mutation method from Chapter 2.
Enabling mutation is simple, and is the same as in last chapter. Update the “TODO: Mutate population” line to reflect the following:
// Apply mutation
population = ga.mutatePopulation(population);
Try running the program again at this point. The results aren’t spectacular; you may get a fitness score of 5 or 10 after 1,000 generations. However, one thing is clear: the population is now evolving, and we’re getting closer to the finish.
We have only one TODO remaining: crossover.
Selection Method and Crossover
In our previous genetic algorithm, we used roulette wheel selection to choose the parents for a uniform crossover operation. Recall that crossover is a category of techniques used to combine the genetic information of two parents. In this implementation, we are going to use a new selection method called tournament selection and a new crossover method called single point crossover.
Tournament Selection
Like roulette wheel selection, tournament selection provides a method for selecting individuals based on their fitness value. That is, the higher an individual’s fitness the greater the chance that the individual will be chosen for crossover.
Tournament selection selects its parents by running a series of “tournaments”. First, individuals are randomly selected from the population and entered into a tournament. Next, these individuals can be thought to compete with each other by comparing their fitness values, then choosing the individual with the highest fitness for the parent.
Tournament selection requires a tournament size to be defined that specifies how many individuals from the population it should pick to compete in a tournament. As with most parameters, there is a tradeoff in performance depending on the value chosen. A high tournament size will consider a larger proportion of the population. This makes it much more likely to find the higher scoring individuals in the population. Alternately, a low tournament size will select individuals from the population more randomly due to less competition, often picking lower ranking individuals as a result. A high tournament size can lead to a loss of genetic diversity where only the best individuals are being selected as parents. Conversely, a low tournament size can slow progress of the algorithm due to the reduced selection pressure.
Tournament selection is one of the most common selection methods used in genetic algorithms. Its strengths being that it’s a relatively simple algorithm to implement and allows for variable selection pressure by updating the tournament size. It does have limitations however. Consider when the lowest scoring individual is placed into a tournament. It wouldn’t matter what other individuals from the population are added to the tournament, it will never be chosen because the other individuals are guaranteed to have a higher fitness value. This drawback could be resolved by adding a selection probability to the algorithm. For example, if the selection probability is set to 0.6, there would be a 60% chance the fittest individual is selected. If the fittest individual isn’t selected, it will then move on to the second fittest individual and so on until an individual has been picked. While this modification allows even the worst ranking individuals to be selected occasionally, it doesn’t take into account the fitness difference between individuals. For example, if three individuals were chosen for tournament selection, one having a fitness value of 9, one with a fitness value of 2, and the other with a fitness value of 1. In this case, the individual with a fitness value of 2 would be no more likely to be picked if the fitness value was 8. This means occasionally individuals are given unreasonably high or low odds for selection.
We will not implement selection probability in our tournament selection implementation; however, it is an excellent exercise for the reader.
To implement tournament selection add the following code to the GeneticAlgorithm class, anywhere you like:
public Individual selectParent(Population population) {
// Create tournament
Population tournament = new Population(this.tournamentSize);
// Add random individuals to the tournament
population.shuffle();
for (int i = 0; i < this.tournamentSize; i++) {
Individual tournamentIndividual = population.getIndividual(i);
tournament.setIndividual(i, tournamentIndividual);
}
// Return the best
return tournament.getFittest(0);
}
First, we create a new population to hold all the individuals in the selection tournament. Next, individuals are randomly added to the population until its size equals the tournament size parameter. Finally, the best individual from the tournament population is selected and returned.
Single Point Crossover
Single point crossover is an alternative crossover method to the uniform crossover method we implemented previously. Single point crossover is a very simple crossover method in which a single position in the genome is chosen at random to define which genes come from which parent. The genetic information before the crossover position comes from parent1, while the genetic information, after the position, comes from parent2.
Single point crossover is reasonably easy to implement and allows contiguous groups of bits to be transferred from parents more effectively than in uniform crossover. This is a valuable property of crossover algorithms. Consider our specific problem, where the chromosome is an encoded set of instructions based on six sensor inputs, and each instruction is more than one bit long.
Imagine an ideal crossover situation as follows: parent1 is great at the first 32 sensor operations, and parent2 is great at, say, the last 16 operations. If we were to use the uniform crossover technique from Chapter 2, we’d get jumbled bits everywhere! Individual instructions would be changed and corrupted in the crossover due to the uniform crossover choosing bits at random to exchange. The two-bit instructions may not be preserved at all, because one of the two bits per each instruction might get modified. However, single point crossover lets us capitalize on this ideal situation. If the crossover point is directly in the middle of the chromosome, the offspring would end up with 64 uninterrupted bits representing 32 instructions from parent1, and the great 16 instructions from parent2 as well. So, the offspring now excels at 48 of the 64 possible states. This concept is the underpinning of genetic algorithms: that the offspring may be stronger than either parent because it takes the best qualities from both.
Single point crossover is not without its limitations, however. One limitation of single point crossover is that some combinations the parents’ genomes are simply not possible. For example, consider two parents: one with a genome of “00100” and the other with a genome of “10001”. The child “10101” isn’t possible with crossover alone, although the genes required are available in the two parents. Fortunately, we also have mutation as an evolution mechanism, and the genome “10101” is possible if both crossover and mutation are implemented.
Another limitation of single point crossover is that genes toward the left have a bias of coming from parent1, and genes towards the right have a bias of coming from parent2. To address this problem, two-point crossover can be implemented where two positions are used allowing the partition to span the edges of the parent’s genome. We leave two-point crossover as an exercise for the reader.
To implement single point crossover, add the following code to the GeneticAlgorithm class. This crossoverPopulation method relies on the selectParent method you implemented above, and therefore uses tournament selection. Note that there is no requirement to use tournament selection with single point crossover; you can use any implementation of selectParent, however for this problem we’ve chosen tournament selection and single point crossover since they’re both very common and important concepts to understand.
public Population crossoverPopulation(Population population) {
// Create new population
Population newPopulation = new Population(population.size());
// Loop over current population by fitness
for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) {
Individual parent1 = population.getFittest(populationIndex);
// Apply crossover to this individual?
if (this.crossoverRate > Math.random() && populationIndex >= this.elitismCount) {
// Initialize offspring
Individual offspring = new Individual(parent1.getChromosomeLength());
// Find second parent
Individual parent2 = this.selectParent(population);
// Get random swap point
int swapPoint = (int) (Math.random() * (parent1.getChromosomeLength() + 1));
// Loop over genome
for (int geneIndex = 0; geneIndex < parent1.getChromosomeLength(); geneIndex++) {
// Use half of parent1's genes and half of parent2's genes
if (geneIndex < swapPoint) {
offspring.setGene(geneIndex, parent1.getGene(geneIndex));
} else {
offspring.setGene(geneIndex, parent2.getGene(geneIndex));
}
}
// Add offspring to new population
newPopulation.setIndividual(populationIndex, offspring);
} else {
// Add individual to new population without applying crossover
newPopulation.setIndividual(populationIndex, parent1);
}
}
return newPopulation;
}
Note that while we’ve made no mention of elitism in this chapter, it’s still represented above and in the mutation algorithm (which was unchanged from the previous chapter).
Single point crossover is popular both because of its favorable genetic attributes (preserving contiguous genes), and because it’s easy to implement. In the code above, a new population is created for the new individuals. Next, the population is looped over and individuals are fetched in order of fitness. If elitism is enabled, the elite individuals are skipped over and added straight into the new population, otherwise it’s decided whether to crossover the current individual based on the crossover rate. If the individual is chosen for crossover, a second parent is picked using tournament selection.
Next, a crossover point is picked at random. This is the point at which we’ll stop using parent1’s genes and start using parent2’s genes. Then we simply loop over the chromosome, adding parent1’s genes to the offspring at first, and then switching to parent2’s genes after the crossover point.
Now we can invoke crossover in the RobotController’s main method. Adding the line “population = ga.crossoverPopulation(population)” resolves our final TODO, and you should be left with a RobotController class that looks like the following:
package chapter3;
public class RobotController {
public static int maxGenerations = 1000;
public static void main(String[] args) {
Maze maze = new Maze(new int[][] {
{ 0, 0, 0, 0, 1, 0, 1, 3, 2 },
{ 1, 0, 1, 1, 1, 0, 1, 3, 1 },
{ 1, 0, 0, 1, 3, 3, 3, 3, 1 },
{ 3, 3, 3, 1, 3, 1, 1, 0, 1 },
{ 3, 1, 3, 3, 3, 1, 1, 0, 0 },
{ 3, 3, 1, 1, 1, 1, 0, 1, 1 },
{ 1, 3, 0, 1, 3, 3, 3, 3, 3 },
{ 0, 3, 1, 1, 3, 1, 0, 1, 3 },
{ 1, 3, 3, 3, 3, 1, 1, 1, 4 }
});
// Create genetic algorithm
GeneticAlgorithm ga = new GeneticAlgorithm(200, 0.05, 0.9, 2, 10);
Population population = ga.initPopulation(128);
// Evaluate population
ga.evalPopulation(population, maze);
int generation = 1;
// Start evolution loop
while (ga.isTerminationConditionMet(generation, maxGenerations) == false) {
// Print fittest individual from population
Individual fittest = population.getFittest(0);
System.out.println("G" + generation + " Best solution (" + fittest.getFitness() + "): " + fittest.toString());
// Apply crossover
population = ga.crossoverPopulation(population);
// Apply mutation
population = ga.mutatePopulation(population);
// Evaluate population
ga.evalPopulation(population, maze);
// Increment the current generation
generation++;
}
System.out.println("Stopped after " + maxGenerations + " generations.");
Individual fittest = population.getFittest(0);
System.out.println("Best solution (" + fittest.getFitness() + "): " + fittest.toString());
}
}
Execution
At this point, your GeneticAlgorithm class should have the following properties and method signatures:
package chapter3;
public class GeneticAlgorithm {
private int populationSize;
private double mutationRate;
private double crossoverRate;
private int elitismCount;
protected int tournamentSize;
public GeneticAlgorithm(int populationSize, double mutationRate, double crossoverRate, int elitismCount, int tournamentSize) { }
public Population initPopulation(int chromosomeLength) { }
public double calcFitness(Individual individual, Maze maze) { }
public void evalPopulation(Population population, Maze maze) { }
public boolean isTerminationConditionMet(int generationsCount, int maxGenerations) { }
public Individual selectParent(Population population) { }
public Population mutatePopulation(Population population) { }
public Population crossoverPopulation(Population population) { }
}
If your method signatures don’t match the above, or if you’ve accidentally missed a method, or if your IDE shows any errors, you should go back and resolve them now.
Otherwise, click Run.
You should see 1,000 generations of evolution, and hopefully your algorithm ended with a fitness score of 29, which is the maximum for this particular maze. (You can count the number of “Route” tiles – represented by “3” – in the maze definition to get this number.
Recall that the purpose of this algorithm wasn’t to solve a maze, it was to program a robot’s sensor controllers. Presumably, we could now take the winning chromosome at the end of this execution and program it into a physical robot and have a high level of confidence that the sensor controller will make the appropriate maneuvers to navigate not just this maze, but any maze without crashing into walls. There’s no guarantee that this robot will find the most efficient route through the maze, because that’s not what we trained it to do, but it will at the very least not crash.
While 64 sensor combinations may not seem too daunting to program by hand, consider the same problem but in three dimensions: an autonomous flying quadcopter drone may have 20 sensors rather than 6. In this case, you’d have to program for 220 combinations of sensor inputs, approximately one million different instructions.
Summary
Genetic algorithms can be used to design sophisticated controllers, which may be difficult or time consuming for a human to do manually. The robot controller is evaluated by the fitness function, which will often simulate the robot and its environment to save time by not needing to physically test the robot.
By giving the robot a maze and a preferred route, a genetic algorithm can be applied to find a controller that can use the robot’s sensors to successfully navigate the maze. This can be done by assigning each sensor an action in the individual’s chromosome encoding. By making small random changes with crossover and mutation, guided by the selection process, better controllers are gradually found.
Tournament selection is one of the more popular selection methods used in genetic algorithms. It works by picking a pre-decided number of individuals from the population at random, then comparing the chosen individual’s fitness values to find the best. The individual with the highest fitness value “wins” the tournament, and is then returned as the selected individual. Larger tournament sizes lead to high selection pressure, which needs to be carefully considered when picking an optimal tournament size.
When an individual has been selected, it will undergo crossover; one of the crossover methods that could be used is single point crossover. In this crossover method, a single point in the chromosome is picked at random, then any genetic information before that point comes from parent A, and any genetic information after that point comes from parent B. This leads to a reasonably random mix of parent’s genetic information, however often the improved two-point crossover method is used instead. In two-point crossover, a start and end point are picked which are used instead to select the genetic information that comes from parent A and the remaining genetic information then comes from parent B.
Exercises
- Add a second termination condition that terminates the algorithm when the route has been fully explored.
- Run the algorithm with different tournament sizes. Study how the performance is affected.
- Add a selection probability to the tournament selection method. Test with different probability settings. Examine how it affects the genetic algorithm’s performance.
- Implement two-point crossover. Does it improve the results?