Genetic Packman
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.
Comments
Let us know what you think here or leave a comment for Hanan.
- Category:
- Picks
Comments
To leave a comment, please click here to sign in to your MathWorks Account or create a new one.