Complexity_ A Guided Tour - Melanie Mitchell [65]
First, consider a situation in which Robby does not sense a can in his current site or in any of his neighboring sites. If Robby is following strategy M, he chooses a random move to make. However, if he is following strategy G, Robby moves to the east until he either finds a can or reaches a wall. He then moves north, and continues to circle the edge of the grid in a counterclockwise direction until a can is encountered or sensed. This is illustrated in figure 9.3 by the path Robby takes under each strategy (dotted line).
FIGURE 9.3. Robby in a ”no-can” wilderness. The dotted lines show the paths he took in my simulation when he was following strategies M (top) and G (bottom).
FIGURE 9.4. Robby in a cluster of cans, using strategy M over four time steps.
Not only does this circle-the-perimeter strategy prevent Robby from crashing into walls (a possibility under M whenever a random move is made), but it also turns out that circling the perimeter is a more efficient way to encounter cans than simply moving at random.
Second, with G the genetic algorithm discovered a neat trick by having Robby not pick up a can in his current site in certain situations.
For example, consider the situation illustrated in figure 9.4a. Given this situation, if Robby is following M, he will pick up the can in his current site, move west, and then pick up the can in his new site (pictures b–d). Because Robby can see only immediately adjacent sites, he now cannot see the remaining cluster of cans. He will have to move around at random until he encounters another can by chance.
In contrast, consider the same starting situation with G, illustrated in figure 9.5a. Robby doesn’t pick up the can in his current site; instead he moves west (figure 9.5b). He then picks up the western-most can of the cluster (figure 9.5c). The can he didn’t pick up on the last move acts as a marker so Robby can “remember” that there are cans on the other side of it. He goes on to pick up all of the remaining cans in the cluster (figure 9.5d–9.5k).
FIGURE 9.5. Robby in the same cluster of cans, using strategy G over eleven time steps. (Continued on next page)
I knew that my strategy wasn’t perfect, but this little trick never occurred to me. Evolution can be pretty clever. GAs often come up with things we humans don’t consider.
Geneticists often test their theories about gene function by doing “knockout mutations,” in which they use genetic engineering techniques to prevent the genes in question from being transcribed and see what effect that has on the organism. I can do the same thing here. In particular, I did an experiment in which I “knocked out” the genes in G that made this trick possible: I changed genes such that each gene that corresponds to a “can in current site” situation has the action PickUp. This lowered the average score of G from its original 483 to 443, which supports my hypothesis that this trick is partly responsible for G’s success.
How Did the GA Evolve a Good Strategy?
The next question is, how did the GA, starting with a random population, manage to evolve such a good strategy as G?
To answer this question, let’s look at how strategies improved over generations. In figure 9.6, I plot the fitness of the best strategy in each generation in my run of the GA. You can see that the best fitness starts out way below zero, rises very quickly until about generation 300, and then improves more slowly for the rest of the run.
FIGURE 9.6. Plot of best fitness in the population versus generation for the run of the GA in which strategy G was evolved.
The first generation consists of 200 randomly generated strategies. As you might expect, all of them are very, very bad. The best one has fitness of only −81 and the worst one has fitness −825.
I looked at the behavior of Robby when using the worst strategy of this generation, on several sessions, each starting with a different environment (configuration of cans). In some environments, Robby makes a few moves, then gets stuck, executing action StayPut again and again, for