Assignment 4: Evolving Cars
- Due Jul 27, 2019 by 11:59pm
- Points 10
- Submitting a file upload
- Available Jul 20, 2019 at 11:59am - Aug 3, 2019 at 11:59pm
Objectives
Learn how to implement Genetic Algorithms with simulation-based fitness functions.
Description
Genetic Algorithms (GA) are a stochastic search method inspired by biological evolution that can be applied to generate complex content with feasibility constraints. In this assignment, you will use a GA to evolve cars to traverse a bumpy terrain. You will implement your own version of BoxCar2D Links to an external site..
For this assignment, you will use a base code Links to an external site. to simulate a race but you have to write a GA to evolve cars for a given number of generations. You GA will be defined as follows:
- Representation
A car is composed of 8 vectors and 2 wheels. All the vectors radiate from a central point (0,0) and are connected with triangles. Vectors are represented by an angle and a magnitude and wheels are represented by a vector index and a radius. The vector index of a wheel represents where it will be placed. With this definition, your phenotype will be as follows:
Angle0 |
Mag0 | Angle1 | Mag1 | Angle2 | Mag2 | Angle3 | Mag3 | Angle4 | Mag4 | Angle5 | Mag5 | Angle6 | Mag6 | Angle7 | Mag7 |
Wheel0 Vertex |
Wheel0 Radius |
Wheel1 Vertex |
Wheel1 Radius |
349.65 |
7.94 | 149.70 | 27.93 | 217.94 | 62.13 | 286.05 | 21.13 | 190.28 | 40.47 | 215.86 | 86.68 | 250.37 | 40.31 | 13.89 | 49.61 | 3 | 39.46 | 1 | 59.08 |
- Fitness Function
The fitness (or score) of a car is given by it's (direct) progress on a race. Using the base code, you can simulate a race using the following code:
terrain = new Terrain(pos.x, pos.y, 100, 100, 1);
race = new Race(terrain, cars, raceOverCallback);
race.start();
Where terrain is a randomly generated bumpy terrain, cars is a list of cars and raceOverCallback is a function that gets called when the race is over. This function passes the final leaderboards as argument so you can use that to get the fitnesses of your cars.
- Reproduction
You will design your own reproduction function. Hint: try using a one or two-point crossover Links to an external site. first.
To accomplish this assignment:
- Clone the base code Links to an external site. from your class GitHub.
- Implement (in "ga.js") the init() population initialization method. Currently, the init() function generates genotypes as random binary arrays. The Car class has a function randomFeatures() that helps you initializing cars.
- Implement (in "ga.js") the rouletteWheel() function to perform probabilistic selection.
- Implement (in "ga.js") the crossover() function to perform your defined crossover operation (e.g. one-point crossover) on a pair of parents.
- Implement (in "ga.js") the mutate() function to mutate your population of cars.
- Implement (in "ga.js") the best() function to return the best car after one generation().
- Instantiate (in sketch.js) a GeneticAlgorithm and call the evolve() function whenever a race is over.
- Show on your canvas (during a race) the GA generation number and the fitness of the previous generation best individual.
(EXTRA)
9. Show on your canvas (during a race) the image of the previous generation best car.
Resources
Submission
Host your source code on Github and upload the following on Canvas:
- A zip file with the final version of your code.
- A link (as a comment to your submission) to this assignment's github page. This page should have examples (.png or .gif) of outputs of your GA with a brief explanation (1 paragraph) of how this GA evolves your cars.