Complexity_ A Guided Tour - Melanie Mitchell [64]
(d) Put the two children in the new population.
4. Once the new population has 200 individuals, return to step 2 with this new generation.
The magic is that, starting from a set of 200 random strategies, the genetic algorithm creates strategies that allow Robby to perform very well on his cleaning task.
The numbers I used for the population size (200), the number of generations (1,000), the number of actions Robby can take in a session (200), and the number of cleaning sessions to calculate fitness (100) were chosen by me, somewhat arbitrarily. Other numbers can be used and can also produce good strategies.
I’m sure you are now on the edge of your seat waiting to find out what happened when I ran this genetic algorithm. But first, I have to admit that before I ran it, I overcame my laziness and constructed my own “smart” strategy, so I could see how well the GA could do compared with me. My strategy for Robby is: “If there is a can in the current site, pick it up. Otherwise, if there is a can in one of the adjacent sites, move to that site. (If there are multiple adjacent sites with cans, I just specify the one to which Robby moves.) Otherwise, choose a random direction to move in.”
This strategy actually isn’t as smart as it could be; in fact, it can make Robby get stuck cycling around empty sites and never making it to some of the sites with cans.
I tested my strategy on 10,000 cleaning sessions, and found that its average (per-session) score was approximately 346. Given that at the beginning of each session, about 50%, or 50, of the sites contain cans, the maximum possible score for any strategy is approximately 500, so my strategy is not very close to optimal.
Can the GA do as well or better than this? I ran it to see. I took the highest-fitness individual in the final generation, and also tested it on 10,000 new and different cleaning sessions. Its average (per-session) score was approximately 483—that is, nearly optimal!
How Does the GA-Evolved Strategy Solve the Problem?
Now the question is, what is this strategy doing, and why does it do better than my strategy? Also, how did the GA evolve it?
Let’s call my strategy M and the GA’s strategy G. Below is each strategy’s genome.
M: 65635365625235325265635365615135315125235325215135315165635365 62523532526563536560503530502523532520503530501513531512523532 5215135315105035305025235325205035305065635356252353252656353 656151353151252353252151353151656353656252353252656353454
G: 25435515325623525105635546115133615415103415611055015005203025 62561322523503251120523330540552312550513361541506652641502665 06012264453605631520256431054354632404350334153250253251352352 045150130156213436252353223135051260513356201524514343432
Staring at the genome of a strategy doesn’t help us too much in understanding how that strategy works. We can see a few genes that make sense, such as the important situations in which Robby’s current site contains a can, such as the second situation (“Empty Empty Empty Empty Can”), which has action 5 (PickUp) in both strategies. Such situations always have action 5 in M, but only most of the time in G. For example, I managed to determine that the following situation
has action 3 (MoveWest), which means Robby doesn’t pick up the can in his current site. This seems like a bad idea, yet G does better than M overall! The key, it turns out, is not these isolated genes, but the way different genes interact, just as has been found in real genetics. And just as in real genetics, it’s very difficult to figure out how these various interactions lead to the overall behavior or fitness.
It makes more sense to look at the actual behavior of each strategy—its phenotype—rather than its genome. I wrote a graphics program to display Robby’s moves when using a given strategy, and spent some time watching the behavior of Robby when he used strategy M and when he used strategy G. Although the two strategies behave similarly in many situations, I found that strategy G employs two tricks that cause it to perform better than strategy