Review and analyze the genetic algorithm at the website http

Review and analyze the genetic algorithm at the website http://gencar.co/ or http://boxcar2d.com/. Discuss the algorithm’s goals and how it works. Please provide significant details

Solution

Review of boxcar2d

About the program

The program learns to build a car using a genetic algorithm. It starts with a population of 20 randomly generated shapes with wheels and runs each one to see how far it goes. The cars that go the furthest reproduce to produce offspring for the next generation. The offspring combine the traits of the parents to hopefully produce better cars. Now with the button at the bottom left u can choose to input cars and different terrains. This lets people post their results and even design a car by hand.

It uses a physics library called box2D to simulate the effects of gravity, friction, collisions, motor torque, and spring tension for the car. This lets the car be a wide range of shapes and sizes, while still making the simulation realistic. This is based on the AS3 box2D flash port of the library.

How the algorithm works

Each car is a set of 8 randomly chosen vectors: direction and magnitude. All the vectors radiate from a central point (0,0) and are connected with triangles.

For each wheel it randomly chooses a vertex to put the axle on, and picks an axle angle from 0 to 2 pi. If it chooses -1 for the vertex that wheel is turned off. There is nothing to prevent multiple wheels from being on the same vertex.

The design of chromosome:

Each chromosome contains 22 variables, each represented as a real number with varying ranges.

These variables are: CartAngle1, CartMagnitude1, CartAngle2, CartMagnitude2, CartAngle3, CartMagnitude3, CartAngle4, CartMagnitude4, CartAngle5, CartMagnitude5, CartAngle6, CartMagnitude6, CartAngle7, CartMagnitude7, WheelVertex0, AxleAngle0, WheelRadius0, WheelVertex1, AxleAngle1, WheelRadius1.

Selection:

At the end of each generation, pairs of parents have to be selected to produce offspring for the next generation. That\'s the selection process and I\'ve implemented two algorithms.

Selection of the car:

The parents after each generation are chosen based on their fitness scores. Specifically, it finds the sum of all fitness scores for that generation and divides each score by the sum to get the probability. Summing the probabilities creates a wheel we can select from.

Then by picking a random number from 0-100 we can pick the car for mating. Removing the selected car from the process, it repeats to get another car to mate. This process continues n/2 times where n is the population size. In this case n=4 so 2 pairs mate.

Selection pressure can more be controlled more easily with tournament selection, which really helps keep high scoring individuals from sweeping the population too early. The pseudocode:

*for each car A
    *pick a random car B (excluding A)
    *highest score of A and B wins tournament
    *put winner in mating pool
*randomly pick pairs from mating pool for crossover

This is deterministic tournament selection since it always selects the one with the higher score, and with the smallest possible tournament size of 2, the selection pressure is kept as small as possible.

Crossover:

The algorithm uses two point crossover, which means a two random points along the chromosome are selected and everything in between is swapped. Cars are chosen by their scores but theres no guarantee that two high scoring cars will produce high scoring offspring.

Mutation:

In addition to crossover, each generation the chromosomes go through mutation. This means theres a probability that each aspect of the car (or variable in the chromosome) will change. When a variable mutates, a new value is randomly chosen in the desired range. A new random color is also chosen to visually illustrate the mutation.