BoxCar 2D

Designing the Car

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 Chromosome: Representing the Data

The design of the chromosome is probably the most important step in making a successful genetic algorithm. Each car represents one chromosome, and its layed out like this:

Therefore each chromosome/car has 16 + 3 * 2 = 22 variables, each represented as a real number (or integer) with varying ranges.

In version 2, I've extended the chromosome to add 3 more variables for each wheel (vertex, axle angle, and radius) for a total of 8 possible wheels. This increases the number of variables to 16 + 3 * 8 = 40. However when the user decreases the maximum number of wheels, the chromosome size also decreases to reduce the variables.

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.

Roulette-Wheel Selection

This is the most obvious selection strategy, since it chooses parents 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. Here's an example with a population size of 4:

This screenshot was taken right at the beginning of the 2nd generation (gen 1). the 4 cars got scores of 3.9, 0.2, 6, and 1. Using these it calculates the roulette wheel probabilities:

Then by picking a random number from 0-100 it can immediately see where it falls on the roulette wheel and pick that 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.

You can see the importance of the target score in this example, which stopped one of the cars at 6, to keep the scores in the same range. Even then, that car has a 54.1% chance of being picked each round of selection.

To prevent the algorithm from converging too fast theres a chance it won't use the roulette wheel and just randomly select a mate. For version 1 this was as high as 40%, otherwise the small population didn't lost diversity quickly and it would fall into local optimum.

Tournament Selection

Selection pressure can more be controlled more easily with tournament selection, which really helps keep high scoring individuals from sweeping the population too early. I've modified the concept to make sure every car is the small population gets a chance in the tournament. Here's the idea:

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

Voting

Tournament selection is only implemented in version 2 and it easily allows the addition of user voting. If a car has an upvote it wins the tournament, regardless of its score. If both cars have an upvote the scores decide the winner, same as if neither has an upvote. Downvotes immediately remove that car from the mating pool!

Crossover

Parents	A	B
Children	AB	BA

Here are the associated chromosomes for the cars shown above:

The two cars A and B crossover to produce parents AB and BA. I'm using two point crossover, which means a two random points along the chromosome are selected and everything in between is swapped (as indicated by the colors above). In this case the 3rd position and and the 2nd to last postion are chosen. Most notably, this takes the big wheel from car A and gives it to AB, while AB gets the small wheel. 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, as determined by the mutation rate slider set by the user. 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. By definition at 100% mutation rate, every variable is chosen randomly each generation and no information is retained.

Here's an example using car AB from above:

In this case two variables have mutated, one of the magnitudes describing the car (blue), and the position of one of the wheels (orange). Mutation is performed after crossover for each child.

Torque and Spring Tension

The tension on shock springs and the torque of the wheels is determined automatically by the weight of the car. These values were chosen to produce a fun simulation. The torque is different for each wheel: torque = mass * gravity * sin(maxClimbAngle) / radius.

References

Sign up for email updates. If you want more information check out the canonical Golberg book. Also, the project that inspired this creation qubit.devisland.net/ga. Emanuele Feronato's flash programming with box2d helped me a lot also.

(obligatory xkcd)