CMPM-147-01
    Assignment 4: Evolving Cars
    Skip To Content
    Dashboard
    • Login
    • Dashboard
    • Calendar
    • Inbox
    • Help
    Close
    • My Dashboard
    • CMPM-147-01
    • Assignments
    • Assignment 4: Evolving Cars
    2019 Summer Quarter
    • Home
    • Assignments
    • Files
    • Syllabus
    • Quizzes
    • Collaborations
    • Google Drive
    • Zoom
    • Student Experience of Teaching

    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 15 days
    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. 

    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:

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

    Rubric

     
     
     
     
     
     
     
         
    Can't change a rubric once you've started using it.  
    Find a Rubric
    Find Rubric
    Title
    You've already rated students with this rubric. Any major changes could affect their assessment results.
    Title
    Criteria Ratings Pts
    Edit criterion description Delete criterion row
    This criterion is linked to a Learning Outcome Description of criterion
    threshold: 5 pts
    Edit rating Delete rating
    5 to >0 pts
    Full Marks
    blank
    Edit rating Delete rating
    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