Mike Precup and Martin Wickham project scoping

The first known computer simulation of evolution was done by Nils Aall Barricelli in 1954, but it wasn’t until Alex Frasier, a geneticist, suggested it in 1957 that the genetic algorithm (GA) was widely noticed.  The GA became more popular throughout the 1960s and in 1975 John Holland published “Adaptation in Natural and Artificial Systems,” which held in its pages an algorithm to predict the quality of the next generation.  Now, the GA is the basis of some commercial products including Evolver, a program that solves optimization problems.

As you would expect, GAs rely heavily on genetics and Darwinian evolution.  They work in a much simpler manner by removing a small number of items from the population and ranking them, killing off the least fit ones, and “mating” the others.

Our sources so far include the following:  The textbook, wikipedia, and this video.

We are going to make a sort of city planning software that will take a large number of nodes and find the best way to connect them to allow the fastest travel at the minimum cost to build the roads. This is completely doable in a week.  As I write this (Tuesday night), we are almost done with the heuristic judging.

 

Schedule:

Tuesday:  implement random path generation

Wednesday:  implement Bellman-Ford judging

Thursday:  implement heuristic (Bellman-Ford rank {1,2,3} + path-building cost rank {1,2,3})

Friday:  implement genetic inheritance

Saturday:  implement genetic inheritance / Mass testing

Sunday:  fix bugs / run

 

Presentation:

history (3 mins)

how it works (3 mins)

applications (6 mins)

Play Nyan cat (3 mins)

Algorithm (5 mins)

Results (5 mins)

possible error (2 mins)

ways to improve (3 mins)

Leave a Reply

You must be logged in to post a comment.