Robust-first Computing Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== ULAM demos: Coevolution ======

Evolution can sometimes be seen as occurring between a population of creatures and a fixed environment.  Some creatures do better than others and proliferate, and over time a population emerges that is increasingly well-adapted to that environment.  Then further innovations typically become smaller and rarer and the system's dynamics tends toward a fixed point.

But just as often, the "environment" is a moving target, so solutions that worked in the past may no longer work as well as time passes.  This can happen because of purely external factors like a meteor hitting the planet, or because of the effects of the evolving population's actions --- or, and this is our present concern, because the environment contains //other populations// of creatures that are //also// evolving.  In such circumstances the resulting //coevolutionary// system dynamics can be quite complex, as the evolutionary innovations of one species are foiled by the evolutionary counter-innovations of another species.

In 2002, Dave Ackley developed a coevolution simulation project called //Huegene// for a C++ programming course.  The ULAM Huegene model demonstrated here is a variation of the original //Huegene//, differing in several ways including using an RGB color encoding where the original used HSV.  (Also, perhaps ironically, the primary pedagogical purpose of //Huegene// was to learn about discrete event simulation, but in the MFM, all issues of event scheduling and selection are built into the fundamental architecture,  Huegene in ULAM is a //much// smaller project than it was in C++!) 

===== The Huegene model =====

Suppose there are two species of creatures, the //Plants// and the //Herbivores//, existing in a two-dimensional grid of sites that each can hold one creature.  Plants are immobile, but they spontaneously grow over time and will split into empty adjacent sites if they are large enough.  The Herbivores move randomly and attempt to eat any Plants they stumble over.  Herbivores must eat enough Plants to avoid starving to death, and if they accumulate enough energy they can produce an offspring Herbivore in a neighboring empty site. 
{{ youtube>jQaXtbrVNaU?500x280|Plant vs Herbivore}}

The Plants have genetic information that allows them to appear as any (24 bit RGB) color.  Any given Plant has a fixed color for its whole lifetime, but if it manages to produce an offspring Plant, the child's color will be slightly modified --- "mutated", completely at random --- compared to the parent.  Regardless of their color, all //Plants// are equally efficient at growing and having offspring plants, and so on --- in a world consisting only of //Plants// their colors are completely irrelevant to their evolutionary success.

For their part, the //Herbivores// also have a genetically-specified color, that determines what color Plants they are most likely to eat successfully.  So a "well-adapted" Herbivore will have a color closely matching that of the nearby Plants, while a "well-adapted" Plant will have a color that's far (in terms of the sum of absolute differences in RGB) from the nearby Herbivores.

If we put a single Plant into an empty grid, it will gradually produce a population of Plants around it, with increasingly mutated colors the further we get from the original "Ancestor".  What will happen if we then start dropping Herbivores near the Plant population, until we get one that "catches" --- that can eat the available Plants successfully enough to produce offspring?

The video at right shows one possible result, run in the MFM simulator for several hours of real time and displayed so that about 90 events happen at each site during each second.

===== ULAM source code =====

The ULAM source, not surprisingly, consists of two files: ''Plant.ulam'' and ''Herbivore.ulam''.  The code was not explicitly designed for teaching or to be as simple as possible, but it is presented here in its entirety so people can play around with it as they like. 

<file java Plant.ulam>
/**
   \symmetries all
*/
element Plant {
  typedef Unsigned(8) Channel;
  typedef Channel ARGB[4];
  typedef Channel RGB[3];
  typedef Unsigned(3) Energy;

  EventWindow ew;
  Random random;

  Once once;
  RGB color;
  Energy energy;

  constant Int cMUTATION_DISTANCE = 7;
  Channel mutate(Channel cur) {
    return (Channel) (cur + random.between(-cMUTATION_DISTANCE,cMUTATION_DISTANCE));
  }

  Void behave() {
    if (once.new()) {
      for (Int i = 0; i < 3; ++i) 
        color[i] = (Channel) random.between(Channel.minof,Channel.maxof);
    }
    ++energy;
    if (!ew.isLive(1)) return;
    if (energy == energy.maxof && ew[1] is Empty) {
      energy = Energy.maxof / 2 - 1;
      Self kid = self;
      for (Int i = 0; i < 3; ++i) {
        kid.color[i] = mutate(kid.color[i]);
      }
      ew[1] = kid;
    }
  }


  ARGB getColor(Unsigned selector) {
    ARGB ret;
    ret[0] = 0xff;
    ret[1] = color[0]; 
    ret[2] = color[1]; 
    ret[3] = color[2]; 
    return ret;
  }
  
}

</file>

<file java Herbivore.ulam>
/**
   \symmetries all
*/
element Herbivore {
  typedef Unsigned(8) Channel;
  typedef Channel ARGB[4];
  typedef Channel RGB[3];
  typedef Unsigned(7) Hunger;

  EventWindow ew;
  Random random;

  Once once;
  RGB color;
  Hunger hunger;

  constant Hunger cEAT_PER_ENERGY = 6;
  constant Int cMUTATION_DISTANCE = 10;

  Channel mutate(Channel cur) {
    Int mutOdds = cMUTATION_DISTANCE;
    return (Channel) (cur + random.between(-mutOdds,mutOdds));
  }

  Bool isEdible(RGB us, RGB them) {
    Unsigned sad;
    for (Int i = 0; i < 3; ++i) {
      Int diff = (Int) us[i] - (Int) them[i];
      if (diff < 0) diff = -diff;
      sad += (Unsigned) diff;
    }
    return random.oneIn(sad/50u);
  }

  Void behave() {
    if (once.new()) {
      hunger = hunger.maxof / 2 + 1;
      for (Int i = 0; i < 3; ++i) 
        color[i] = (Channel) random.between(Channel.minof,Channel.maxof);
    }
    if (++hunger == hunger.maxof) {
      Empty e;
      ew[0] = e;
      return;
    }
    if (!ew.isLive(1)) return;
    if (ew[1] is Plant) {
      Plant p = (Plant) ew[1];
      if (isEdible(color, p.color)) {
        hunger -= (Hunger) (p.energy * cEAT_PER_ENERGY);
        if (hunger == hunger.minof) {
          Hunger give = (Hunger) (3 * hunger.maxof / 4 + 1);
          hunger = give;
          Self kid = self;
          hunger = (Hunger) (Hunger.maxof - give);
          for (Int i = 0; i < 3; ++i) {
            kid.color[i] = mutate(kid.color[i]);
          }
          ew[0] = kid;
        }
      } else {
        Empty e;
        ew[0] = e;
      }
      ew[1] = self;
    } else if (ew[1] is Empty || ew[1] is Self) {
      ew.swap(0,1);
    }
  }


  ARGB getColor(Unsigned selector) {
    ARGB ret;
    ret[0] = 0xff;
    if (selector==2u) {
      ret[1] = color[0]; 
      ret[2] = color[1]; 
      ret[3] = color[2]; 
    } else {
      ret[1] = 0;
      ret[2] = 0;
      ret[3] = 0;
    }
    return ret;
  }
  
}

</file>
===== How the video was made =====

<<BY REQUEST>>