Excerpt from “Emergence – The Connected Lives of Ants, Brains, Cities, and Software” by Steven Johnson:
On page 58 the author mentions that a DNA coil of a species dictate some kind of form or behavior. The DNA can be referred to as the “genotype” and the form or behavior it dictates is referred to as the “phenotype”.
[pg. 59]
The genetic algorithm was an attempt to capture that process in silicon. Software already has a genotype and phenotype, Holland recognized; there’s the code itself, and then there’s what the code actually does. What if you created a gene pool of different code combinations, then evaluated the success rate of the phenotypes, eliminating the least successful strands? Natural selection relies on a brilliantly simple, but somewhat tautological, criterion for evaluating success: your genes get to pass on to the next generation if you survive long enough to produce a next generation. Holland decided to make that evaluation step more precise: his programs would be admitted to the next generation if they did a better job of accomplishing a specific task – doing simple math, say, or recognizing patterns in visual images. The programmer could decide what the task was; he or she just couldn’t directly instruct the software how to accomplish it. He or she would set up the parameters that defined genetic fitness, then let the software evolve on its own
Holland developed his ideas in the sixties and seventies using mostly paper and pencil – even the more advance technology of that era was far too slow to churn through the thousandfold generations of evolutionary time. But the massively parallel, high-speed computers introduced in the eighties – such as Danny Hillis’s Connection Machine – were ideally suited for exploring the powers of the genetic algorithm. And one of the most impressive GA systems devised for the Connection Machine focused exclusively on simulating the behavior of ants.
It was a program called Tracker, designed in the mideighties by two UCLA professors, David Jefferson and Chuck Taylor. ( Jefferson was in the computer science department, while Taylor was a biologist.) “I got the idea from reading Richard Dawkin’s first book, the Selfish Gene,” Jefferson says today. “That book really transformed me. He makes the point that in order to watch Darwinian evolution in action, all you need are objects that are capable of reproducing themselves, and reproducing themselves imperfectly, and having some sort of resource limitation so that there’s competition. And nothing else matters – it’s a very tiny, abstract axiom that is required to make evolution work. And so it occurred to me that programs have those properties – programs can reproduce themselves. Except that they usually reproduce themselves exactly. But I recognized that if there was a way to have them reproduce imperfectly, and if you had not just one program but a whole population of them, then you could simulate evolution with the software instead of organisms.
After a few small-scale experiment, Jefferson and Taylor decided to simulate the behavior of ants learning to follow a pheromone trail. “Ants were on my mind – I was looking for simple creatures, and E. O. Wilson’s opus on ants had just come out,” Jefferson explains. “What we were really looking for was a simple task that simple creatures perform where it wasn’t obvious how to make a program do it. Somehow we came up with the idea of following a trail – and not just a clean trail, a noisy trail, a broken trail.” The two scientists created a virtual grid of squares, drawing a meandering path of eighty-two squares across it. The goal was to evolve a simple program, a virtual ant, that could navigate the length of the path in a finite amount of time, using only limited information about the path’s twists and turns. At each cycle, an ant had the option of “sniffing” the square ahead of him, advancing forward one square, turning right or left ninety degrees. Jefferson and Taylor gave their ants one hundred cycles to navigate the path; once an ant used up his hundred cycles, the software tallied up the number of squares on the trail he had successfully landed on and gave him a score. An ant that lost his way after square one would be graded 1; an ant that successful completed the trail before the hundred cycles were up would get a perfect score, 82.
The scoring system allowed Jefferson and Taylor to create fitness criteria that determined which ants were allowed to reproduce. Tracker began by simulating sixteen thousand ants – one for each of the connection machine’s processors – with sixteen thousand more or less random strategies for trail navigation. One ant might begin with the strategy of marching straight across the grid; another by switching back and forth between ninety-degree rotations and sniffings; another following more baroque rules. The great preponderance of these strategies would be complete disasters, but a few would allow a stumble across a larger portion of the trail. Those more successful ants would be allowed to mate and reproduce, creating a new generation of sixteen thousand ants ready to tackle the trail.
The path – dubbed the John Muir trail after the famous environmentalist – began with a relatively straightforward section with a handful of right-hand turns and longer straight sections, the steadily grew more complicated. Jefferson says now that he designed it that way because he was worried that early generations would be so incompetent that a more challenging path would utterly confound them. “You have to remember that we had no idea when we started the experiment whether sixteen thousand was anywhere near a large enough population to seek Dawinian evolution,” he explains. “And I didn’t know if it was going to take ten generations, or one hundred generations, or ten thousand generations. There was no theory to guide us quantitatively about either the size of the population in space or the length of the experiment in time.”
Running through one hundred generations took about two hours; Jefferson and Taylor rigged the system to give them real-time updates on the most talented ants of each generation. Like a stock ticker, the Connection Machine would spit out an updated number at the end of each generation: if the best trail followers of one generation managed to hit fifteen squares in a hundred cycles, the Connection Machine would report that 15 was he current record and then move to the next generation. After a few false starts because of bugs, Jefferson and Taylor got the Tracker system to work – and the results exceeded even their most optimistic expectations.
“To our wonderment and utter joy,” Jefferson recalls, “it succeeded the first time. We were sitting there watching these numbers come in: one generation would produce twenty-five, then twenty-five, and then it would be twenty-seven, and then thirty. Eventually we saw a perfect score, after only about a hundred generations. It was mind blowing.” The software had evolved an entire population of expert trail followers, despite the fact that Jefferson and Taylor had endowed their first generation of ants with no skills whatsoever. Rather than engineer a solution to the trail-following problem, the two UCLA professors had evolved a solution; they had created a random pool of possible programs, then built a feedback mechanism that allowed more successful programs to emerge. In fact, the evolved programs were so successful that they’d developed solutions custom-tailored to their environments. When Jefferson and Taylor “dissected” one of the final champion ants to see what trail-following strategies he had developed, they discovered that the software had evolved a preference for making right-hand turns, in response to the three initial turns that Jefferson had built into the John Muir Trail. It was like watching an organism living in water evolving gills: even in the crude, abstract grid of Tracker, the virtual ants evolved a strategy for survival that was uniquely adapted to their environment.
By any measure, Tracker was a genuine breakthrough. Finally the tools of modern computing had advanced to the point where you could simulate emergent intelligence, watch it unfold on the screen in real time, as Turing and Selfridge and Shannon had dreamed of doing years before. And it was only fitting that Jefferson and Taylor had chosen to simulate precisely the organism most celebrated for its emergent behavior: the ant. They began, of course, with the most elemental form of ant intelligence – sniffing for pheromone trails – but the possibilities suggested by the success of Tracker were endless. The tools of emergent software had been harnessed to model and understand the evolution of emergent intelligence in real-world organisms. In fact, watching those virtual ants evolve in on the computer screen, learning and adapting to their environments on their own, you couldn’t help wonder if the division between the real and the virtual was becoming increasingly hazy.