Dr. Mark Humphrys

School of Computing. Dublin City University.

Home      Blog      Teaching      Research      Contact

Search:

CA249      CA318      CA425      CA651

w2mind.computing.dcu.ie      w2mind.org

Advanced Topics



Speciation (Geography, Local mating)

Should there be geography in our machine evolution?
i.e. You mate with greater probability with fit creatures nearby in the world rather than with the fittest in the whole population, wherever they are.

ALife researchers have pointed out that global mating means evolution proceeds more slowly than with local mating. The whole population must advance at the same pace, whereas with local mating, little groups can form and intensively explore some specialised avenue. If successful, they then come back and "invade" the rest of the population and wipe them out (either literally, or just by competition).

Researchers are experimenting with raising and lowering geographical barriers in an attempt to encourage periodic formation of species / subspecies (these terms don't necessarily have clear definitions).



Diversion - Speciation

In nature, 2 species can gradually separate from a common ancestral species. Indeed, nothing interesting would exist if this did not happen.

A "species" is defined as a group of creatures that can interbreed with each other and produce fertile offspring.

Speciation cannot happen if, as in most machine evolution experiments, fit individuals breed randomly with other fit individuals across the entire world population. Then the whole population progresses together. There has to be some concept of mating with what is nearby.

e.g. An island gets cut off from mainland. The woodpeckers on the island breed only with others on the island. Gradually their gene pool starts drifting in a different direction to those on the mainland. 5 million years later, sea level goes down and the island is joined again. But now the 2 woodpecker groups cannot breed with each other - 2 species.


The species problem

Turns out to be very hard to define "species".

  • The definition of being able to interbreed only works with sexual reproduction. How do you define species for life that uses asexual reproduction?

  • Ring species - not all individuals can interbreed.

  • The species problem - the problem of defining a species.

"Species" do not exist over time

The concept of species also breaks down if you look at the population over time.

  • Chronospecies - Species that changes slowly over time so that the earlier members probably could not breed with the later members if they were ever brought together.
"Species" do not really exist as you travel back and forth through time. There is no such thing as the "start" of a species. Classifying extinct creatures into species runs the risk of distorting history. e.g. How do we know that what we call early H. sapiens could breed with us, if they were alive today? How do we know they couldn't breed with what we call late H. erectus?

"Species" can only be defined relative to a particular point in time. As you travel back through the ancestors of living species, the definition of the species soon gets confused and has to be revised as you go along.

Anybody who talks about "the first humans" does not understand nature. There is no such thing as "the first humans".





Classifier Systems

Run genetic search on rules of the form:

if x then a

where x is a condition or state of the world, and a is the action we will take in that state. Many rules may fire. Must resolve conflict and choose a rule to follow. Conflict is resolved based largely on the "fitness" of the rule.

Then positive/negative feedback affects the fitness of the rules that were used in the series leading up to the feedback. "Bucket brigade algorithm": similar to starting at the output and back-propagating the error (or the credit).

This feedback affects how likely the rule is to reproduce. The rules reproduce, and children inherit a fitness value based on their parents' fitness. This fitness affects how the rule can compete in the future.

Further Reading - John Holland, "Escaping Brittleness", in Michalski et al, Machine Learning: an Artificial Intelligence approach, Vol.2, 1986, Library 006.31.MIC.
See also Some discussion in my PhD thesis.




Can also view it as pattern matching:

 if x then c

or:

 x -> c

where x is the multi-dimensional input pattern and c is the class it belongs to. Then we use a form of supervised learning, where the teacher is able to return what category x should have been classified in, and the strengths (increased/decreased) and population (strong rules reproduce, weak die) of the rules adjust in response to this feedback. If x = (x1,..,xn), rules may be things like:

 (1,7,3,5,5) -> 0
 (2,3,5,5,5) -> 1

but lot more powerful if we can include wildcards, so rules are of the form:

 (1,*,*,*,5) -> 0
 (2,3,5,*,*) -> 1

Now generalisations can evolve.
Questions - Does the generalisation cover the whole space? Can a point belong to multiple classes?




Genetic Programming

Evolving not just bit strings or similar but actual program code.

Structure the program in a hierarchy. e.g. The expression ( x + (y*3) ):

  +
 / \
x   *
   /  \
  y    3
Conditional expression ( if x < y return 3 else return 4 ):
  IFLTE
 / / \ \
x y   3 4
Can see how can build up complex expressions. IFLTE is basically a function that controls its own interpretation of parameters below it. We can define our own functions.

For program flow of control, LISP lends itself to hierarchical structuring like this, and is the most common language used. ML would probably be good too (though I am not aware of any GP in ML). Other languages more difficult, but they too (Pascal, C, even C++) have been evolved.

Mutation - Pick a subtree. Replace with new random subtree.

Crossover - swap subtrees. Note that, unlike the case with GAs, the 2 trees crossed over can have different topologies to each other. (Crossover is at different point in each.) [Note: Must allow different topology to evolve, otherwise programs are very restricted.]





Some evolved code.
From "Have Your Spaghetti and Eat it Too: Evolutionary Algorithmics and Post-Evolutionary Analysis", Kfir Wolfson et al., Genetic Programming and Evolvable Machines, Volume 12 Issue 2, June 2011.




Evolving 3-D Morphology


Karl Sims



"Evolved Virtual Creatures" movie.
From here.



Framsticks



Framsticks movie.



Co-evolution and Changing fitness landscape

One of the features of Sims' work is that he used co-evolution. Many researchers have found that if the survival problem is too hard at the start, evolution cannot work. Everything has fitness zero and so, if we pick the best to reproduce, we are just picking random individuals. What reproduces is random, and remains random. Nothing evolves.

Even at the start, we need to be able to distinguish the absolute worst from the best of the worst. But if we make survival too easy, then, as the creatures get more competent, they all rapidly attain maximum fitness and we have the same problem of distinguishing them.

One solution is that survival should be easier at the start, and get harder as the creatures get more competent. How can we ensure that the fitness function changes slowly like this? By tying it to the evolution of other creatures. As the other creatures around it improve, the survival problem gets harder, and the creature's population is subject to constant evolutionary pressure.

This has also been found in machine learning for games. If the (initially-random) machine plays a human, it simply loses massively and learns little or nothing. All moves (or all individuals) have fitness zero and are indistinguishable. If it plays itself, however (or rather, another member of the population close to itself), then the least-useless one will win, and slowly, gradually, the learning gets off the ground.




Artificial Life

"Artificial Life" has different meanings, depending on who you talk to, just like "Artificial Intelligence".

"Artificial Intelligence" should mean the field of autonomous machines - machine search, learning, evolution, and all forms of self-modification. But what it has come to mean is often "machines doing what would be seen in a human as intelligent", i.e. a more narrow focus on the rare and occasional symbolic, logical and linguistic reasoning done by the sane, adult, literate H. sapiens.

If that is the meaning of AI, then there is obviously an enormous field not covered by that name, and so this is what "Artificial Life" should cover.

Yet if you go to Artificial Life conferences, you find the field is almost entirely devoted to studying different types of evolution.
See Battling with GA-Joe by Stephen Grand.

Currently the terminology seems to be:

  1. "Artificial Intelligence" - Artificial humans
  2. "Adaptive Behavior" - Artificial animals
  3. "Artificial Life" - Artificial simple life
yet "AI" is often used for the whole thing, while "Agents" is used for any of the 3!




Implicit Fitness functions

The ALife approach to evolution is more radical than the GA one. ALife researchers tend not to have an explicit fitness function solving some problem, but rather set up an environment with some dynamics, and see what emerges. There has been some success in modelling economies, ecologies, and other complex systems this way.



Feeds      HumphrysFamilyTree.com

Bookmark and Share           On Internet since 1987.