Assignment 4: Evolving Cars

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. 

For this assignment, you will use a base code  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:

- 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 first. 

To accomplish this assignment:

1. Clone the base code from your class GitHub.
2. 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.
3. Implement (in "ga.js") the  rouletteWheel()  function to perform probabilistic selection.
4. Implement (in "ga.js") the crossover() function  to perform your defined crossover operation (e.g. one-point crossover) on a pair of parents.
5. Implement (in "ga.js") the mutate() function to mutate your population of cars.
6. Implement (in "ga.js")  the best() function to return the best car after one generation().
7. Instantiate (in sketch.js) a GeneticAlgorithm and call the evolve() function whenever a race is over.
8. 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

• BoxCar2D Genetic Algorithm

Submission

Host your source code on Github and upload the following on Canvas:

1. A zip file with the final version of your code.
2. 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.