Honors Programming Project 11  SOLUTION

Assignment Overview This project will give you experience on design and use of your own classes. Project Description / Specification This project uses a genetic algorithm (GA) to evolve a robot controller that follows a breadcrumb trail. The code for the robot and robot world are provided for you in file world.py. You need to write two classes: ‐ A GA class that runs the genetic algorithm. ‐ An individual class that represents a robot controller. The code we have been working on in lab should be modified and used as part of this project. Additionally, code that implements the world and how a GA uses a matrix to figure out how the robot is moving has been provided for you. 0. Take a look at the world class (provided in world.py). It takes as input a file that represents the robot’s world. World1.txt is an example world. Within the world, ‘dim’ is the number of rows in the world. The number of columns is inferred. Within the world, ‘x’ represents a wall, ‘ b’ represents a breadcrumb (part of the trail), ‘‐‘ represents a space in the room., ‘F’ represent the finishing spot, ‘A’ represents the agent, and ‘=’ represents a square previously visited by the agent. The robot should follow a breadcrumb trail. A robot has 2 wheels – one on its left side and one on it right. Using its wheels, the robot is able to move forward one space, left one space, or right one space. A robot has 3 sensors – one to its left, one ahead of it, and one to its right. You can also query if it is on a breadcrumb, a dash, or the finish mark. More on this later… 1. Create the individual class. Use the code we developed in lab as a starting point. In this case, an individual is going to represent a robot controller as a Braitenberg matrix, which will transform sensor inputs to outputs representing how the wheels should move. The matrix has 2 rows (one for each wheel) and 3 columns (one for each sensor). At a high level, the robot decides how to move by multiplying its sensor values by the matrix (using matrix multiplication) and producing two outputs: (0) how the left wheel should move and (1) how the right wheel should move. This part of the algorithm has been implemented for you. This class should have the following methods: a. __init__ (self) Create a Braitenberg matrix as a list of 6 numbers. Initialize each value in the matrix to be between ‐5 and 5. (This part is similar to Honors Lab Part 1, except for that lab, the individuals were bitstrings.). b. mutate (self, mutation_rate) This method should mutate an individual. Specifically, with the given mutation rate probability, it should change a value in the matrix to a different number between ‐5 and 5. It should produce the new mutated individual as output. (This part of the project is described in Honors Lab 3.) c. crossover (self, other) This method should take in two individuals and using two‐point crossover produce two offspring individuals as output. (This part of the project is described in Honors Lab 3.) d. evalFitness (self) This method is the most complex one. To test how a matrix works at controlling the robot, we need to see how many new squares (‘‐‘) and breadcrumbs (‘b’) the robot visits in 25 moves. Each move: ‐ Get the sensor values from the world ‐ Determine what the robot should do. To help with this part, a function computing how the controller wants to move its wheels based on the present Braitenberg matrix and senor inputs is provided for you in test.py. It is called getActuators. getActuators produces 2 values by multiplying the sensor inputs by the matrix. These 2 values represent what the left wheel does and what the right wheel does. o If the values for both the left and the right wheels are positive, the robot moves 1 square forward. o If the values for the left but not the right wheel are positive, the robot moves 1 square to the right. o If the values for the right but not the left wheel are positive, the robot moves 1 square to the left. Move the agent in the world Check the result. o If the agent is on a breadcrumb it gets 5 points. o If the agent is on a dash it gets 1 point o If the agent is on the finish it gets 10 points. The agent may continue to move about the world after reaching the finish. (You can see the progress of the agent by printing the world.) 2. Create the GA class. Use the code we developed in lab as a starting point and refer to the Wikipedia article to better understand GAs. Your GA should have: This class should have the following methods: a. __init__ (self, popSize, offspringPopSize, mutOffspring, mutBit), where popSize is the population size, offspringPopSize is the number of offspring to create, mutOffspring is the percent of offspring to mutate, and mutBit is the probability a bit is mutated. In this method, initialize a population of size 200. tournamentSelection(self, n, k) (This part of the project is described in Honors Lab 4.) b. run(self) We are going to run the GA for 20 generations. For each generation, we need to: ‐ Create offspring. Create an empty list of individuals. Until you have offspringPopSize individuals, select two parents using tournamentSelection(2,1), cross them over, and add them to the offspring population. Mutate some of the offspring. Mutate mutOffspring percent of the offspring. Add the offspring to their parents’ population. Create the next generation. Using tournamentSelection(2,1) select individuals and add them to the next generation population. Overwrite the original population with the next generation population. Print the best fitness of this population to a file. Once the run is over, print the world of the best individual. c. EXTRA CREDIT: Implement this second selection method and use it, rather than tournament selection to select the parents. fitnessProportionateSelection(self) For this method, we will select organisms proportional to their fitness. This function is sometimes referred to as roulette wheel selection. To perform fitnessProportionateSelection, ‐ sum the fitness values of all the individuals in the population. Pick a randomValue between 0 and the total fitness. Initialize a sumFitness value to 0 For each individual: o sumFitness += fitness of individual o if sumFitness <= randomValue:  Save this individual as selected  Break Return the selected individual 3. Run your GA with the following parameters: a. GA(200, 50, 50, 25) – these parameters should enable you to evolve a working robot. Recall that this translates into: __init__ (self, popSize=200, offspringPopSize=50, mutOffspring=50, mutBit=25), HINTS: 1. Start early. 2. Make sure each method works in isolation. 3. Work on the GA part first. Check that each part works by running it on the all ones problem that we discussed in class prior to moving on to the robot problem.