Will's pick this week is Genetic Packman by Hanan Kavitz.

Here we have a fun application of genetic algorithms. For those of you unfamiliar, a genetic algorithm mimics evolutionary biology by improving the performance of a population of candidate solutions for a particular problem. Candidates have their "fitness" evaluated by defining a quantitative metric for success...the higher (or often lower) the fitness value, the better the solution. Within any given set of possible solutions, some solutions will score better than others. A genetic algorithm seeks better solutions by applying natural selection: the weakest/worst solutions are eliminated while the strongest/best solutions are kept. In a sort of asexual breeding experiment, slight deviations of the best candidates (known as mutants) are created to see if they can be improved upon. By iterating on this strategy of pruning and mutating, the population evolves generation after generation.

Hanan has taken this technique and used it to evaluate paths for his "Packman." Packman is placed at the center of a grid. He can walk north, south, east, or west to the adjacent grid. Each square on the grid is randomly assigned a green or black color. Packman gets a point for every green square he walks over. If he can only make a fixed number of moves, what path should he take to maximize his score?

Hanan's contribution enables you to define the size of the board and number of moves Packman can take. It then evolves a population of 300 paths through 700 generations. It has the option to evaluate the results versus a "greedy" solution that applies a more basic path strategy.

I put Packman in a 40x40 grid and gave him 200 moves. After 5 generations, he scored about 62 points. 695 generations later, he was a lot smarter. The best solution in my population got 95 points. As you run the function, a figure window shows you how the population is doing each generation. In the figure below, the blue dot represents the average score of the entire population, while the black represents the performance of the best solution (scores are negative, so lower is better). As you can observe, pruning and mutating tends to yield better results each generation, but not always.



You also get an entertaining visualization of the best performer. Packman's route gets displayed on the grid. If you're attentive, you will see slight improvements on the route over the three generations presented.



All in all, I am quite pleased with Genetic Packman's packaging. The code is well documented such that it was easy for me to understand what it's doing. It was robust to the various inputs I provided it. For future improvement, it would be fun to enable the user to specify the population size, generation limit, and frequency of green tiles. It isn't too tricky to get into the code and make such changes, but an input would make it that much easier!

Comments
Let us know what you think here or leave a comment for Hanan.