CMPM-147-01
Assignment 4: Evolving Cars
Skip To Content
Dashboard
  • Login
  • Dashboard
  • Calendar
  • Inbox
  • History
  • Help
  • Resources
Close
  • My Dashboard
  • CMPM-147-01
  • Assignments
  • Assignment 4: Evolving Cars
2019 Summer Quarter
  • Home
  • Assignments
  • Files
  • Syllabus
  • Quizzes
  • Collaborations
  • Google Drive
  • NameCoach
  • Zoom
  • YuJa
  • Gradescope
  • SETS

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
This assignment was locked Aug 3, 2019 at 11:59pm.

Objectives

Learn how to implement Genetic Algorithms with simulation-based fitness functions.

Description

Jul-21-2019 14-01-45.gif

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:

Screen Shot 2019-07-23 at 8.53.22 AM (2).png

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:

  1. Clone the base code Links to an external site. 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 Links to an external site.

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.
1564297199 07/27/2019 11:59pm
Please include a description
Additional Comments:
Rating max score to > pts
Please include a rating title

Rubric

Find Rubric
Please include a title
Find a Rubric
Title
You've already rated students with this rubric. Any major changes could affect their assessment results.
 
 
 
 
 
 
 
     
Can't change a rubric once you've started using it.  
Title
Criteria Ratings Pts
This criterion is linked to a Learning Outcome Description of criterion
threshold: 5 pts
Edit criterion description Delete criterion row
5 to >0 pts Full Marks blank
0 to >0 pts No Marks blank_2
This area will be used by the assessor to leave comments related to this criterion.
pts
  / 5 pts
--
Additional Comments
This criterion is linked to a Learning Outcome Description of criterion
threshold: 5 pts
Edit criterion description Delete criterion row
5 to >0 pts Full Marks blank
0 to >0 pts No Marks blank_2
This area will be used by the assessor to leave comments related to this criterion.
pts
  / 5 pts
--
Additional Comments
Total Points: 5 out of 5