Category Archives: Emergence
Avida
Self-replicating programs have been around for a while. The idea was first conceived by John Von Neumann in 1948 as a thought experiment. The first real instance was a game called Core War developed in the early 80s where programmers would write code to compete for sections of the computer’s memory. The best strategies were those that copied themselves, but these programs were fragile – change one piece of code and they would would cease to function.
Tom Ray’s Tierra in 1991 added some stability to the concept of mutation in a digital environment and showed that evolutionary processes previously only seen in nature can take place in the digital world. This eventually led to the “killer app” of self-replicating program research environments, “Avida”, developed by Charles Ofria at Michigan State University’s Digital Evolution Lab in 2000. Below is an animation showing successive generations of Avida organisms (Avidians) taking over the population as a sample evolution progresses:
At the 2010 Artificial Life XII conference in Odense, Denmark, the MSU team presented a paper describing some of their most recent work, including digital creatures that evolved the ability to follow paths along a grid. The environment was strewn with clues, signposts indicating which way the path would go. After tens of thousands of generations of evolution, the Avidians evolved reflex actions which successfully interpreted the signs as either “turn left” or “turn right”, giving them a survival advantage.
A program with just reflex actions can do quite a lot in a complex environment. What about using “volatile memory”, not just knee-jerk responses to the environment, but ones that depend on context? To encourage the evolution of volatile memory, the researchers put sign posts on the grid that symbolized “repeat last action”. The MSU team showed the Avidians were indeed able to take advantage of this information by evolving the ability to remember their last action.
The ability to remember and recall a single variable in the environment appears trivial, especially for a computer program, but the significance of this research is that no one programmed this behavior. The code which navigates the path and uses volatile memory to its advantage bubbled up from the raw evolutionary stew acting against a carefully crafted artificial environment that allowed such evolutionary pressure to exist.
There are many interesting questions here: Under what circumstances does evolutionary pressure tend to favor the development of micro brain structures? How can we configure artificial environments to evolve more complex bottom-up brains? How does the evolution of such structures manifest in nature?
Avida is a robust open-ended research tool and it is likely we will see many more groundbreaking projects coming from this platform for some time.
More:
Flock of Boids
Large flocks of birds appear to display a collective intelligence as they fly in an organized fashion with an apparently singular motive. Starlings in particular have been observed in flocks reaching hundreds of thousands of individuals generating amazing patterns in their group movement as shown in the video below.
Artificial Life researchers get very excited when complexity can be shown to emerge from very simple rules. One of the early examples of this was developed by Craig Reynolds as part of the 1987 SIGGRAPH conference with a program he called BOIDS. With BOIDS he demonstrated that flocking behavior can emerge naturally if every individual BOID followed three simple rules:
- separation: steer to avoid collisions
- alignment: head in the same direction as your neighbors
- cohesion: head towards the center
BOIDS is an excellent example of emergent behavior, and since been adapted for use in computer graphics and special effects, its first use being the 1992 film “Batman Returns” to render bat swarms and penguin flocks.
More:
Tierra
Tom Ray was a tropical biologist who conducted research in the Costa Rican rain forest from 1974 to 1989. His research focused on the ecologies and evolution of various species living there. Eventually he realized he there was a problem with studying evolution in the wild: it occurs far too slowly to actually observe it. He decided therefore to study evolution in a much faster medium, the digital computer. In 1991, he joined forces with the Santa Fe Institute in New Mexico to develop an evolutionary software platform called Tierra.
Genetic Algorithms, programs that simulate evolution to solve a specific problem, had already been well established, but Tierra was different. It wasn’t optimizing anything in particular. Small chunks of machine code were simply left on their own to replicate and compete for access to the CPU, and that was all. Occasional mutations in the copying process allowed evolution to take place. But, this wasn’t a simulation of evolution, these entities were actually evolving. What emerged from Tierra surprised Tom and most of the Santa Fe research team.
The first thing Tom noticed was that these replicating programs became smaller and smaller. A smaller program could replicate faster and so had an advantage over others. Some became so small that they evolved into parasites, tricking other programs into doing the copying for them. The hosts then evolved mechanisms to resist parasites. Some of the host programs were even able to trick the parasites into helping them. Eventually, a form of cooperation emerged where programs helped each other replicate. Then, free-riders emerged who took advantage of this group trust. All of this robust behavior, previously only observed in nature, emerged from Tierra automatically.
Tierra was groundbreaking for the field of Artificial Life, and inspired many systems like it afterwards, including the very robust evolutionary platform, Avida. Most importantly, it gave a demonstration of real evolution occuring in a medium other than nature.
More:
Hive Mind
A “super-organism” is a group of organisms that act collectively to ensure their own survival. For example, a beehive consisting of thousands of individual bees can be considered a single organism. The hive has a life of its own, usually living 8-10 years, while the individual bees that comprise it live only 1-2 months each. A hive also exhibits division of labor, similar to the organs of an animal, where groups of bees are responsible for specific functions. Reproduction is even specialized within the hive, as the Queen is the only bee allowed to reproduce. Individual worker bees are therefore selfless, working only to ensure the survival of the Queen and her DNA. Like a single cell in your body, a worker bee’s own survival is trivial as compared to the reproductive process of the organism as a whole.
But, does a beehive have a collective mind? For an outside observer, it would appear so. For example, when new sources of nectar are discovered nearby, the entire hive can be rallied into activity, as more foragers are sent to the source, and more storer bees are recruited inside the hive to handle the influx. Also, when it’s time to move the nest, the hive considers optimal locations by sending out scouts. Then, once a suitable location is chosen, the entire hive is quickly relocated in an organized fashion. No single bee has the entire plan. In fact, each bee only has a tiny bit of information about the activities of the hive as a whole, including the Queen. A beehive is therefore a good example of Emergence, where complex behavior can result from the interactions of a set of relatively simpler behaviors.
In the case of beehives, the key to generating complex behavior is based on 1) the concentric organization of the hive, 2) the presence of environmental cues, and 3) bees’ ability to communicate with each other. Hives are organized from the Queen outwards, and this physical organization will dictate an individual bee’s career path. When a bee is born, it stays close to the Queen, grooming it and cleaning nearby cells. Then it can be recruited to storage tasks, taking incoming nectar, pollen, and water and storing it in the honeycomb. Finally, the bee can be recruited to a scouting or foraging role outside the hive. Within the hive, each bee has access to certain “global variables,” such as temperature and nectar throughput. This information, combined with the bees’ ability to communicate with each other through the various “recruitment” dances, results in the complex behavior we see.
Artificial intelligence researchers are interested in emergent behavior as this might be a viable means of creating complex systems that exhibit intelligent behavior. Like the hive, the human brain is comprised of smaller, simpler units, whose individual behavior is simpler to describe. Examples of emergence abound in nature, but also in human societies, economics in particular. No single trader can fully understand the nature of the stock market as a whole, but the collective actions of traders together result in a complex system capable of maintaining efficient prices, and sometimes acting quickly and collectively in response to new economic environments.
More:
- Emergence
- Bee dances: Waggle, Tremble, Grooming
- Eusociality
