Chapter 6
Evaluation

As with any tool, the best way to evaluate a toolkit is to have a large group of developers attempt to use it on a diverse range of applications. Within the limited scope of this thesis, a first approximation at an evaluation is found by applying the toolkit to a few test programs. Assuming the toolkit was not developed with these particular applications in mind, it is a reasonable test for generality.

The test programs described in this chapter were all written using a hybrid of Visual Basic and C++. Visual Basic is a windows programming environment which is very useful for prototyping because it is interpreted and interactive. Another useful aspect is it can be extended through the use of custom controls such as the graph control used in the test programs. In order to use Visual Basic with the SIMBIOSYS framework, the classes have to be compiled into a DLL, a dynamic load library. This is the MS Windows version of a shared library. In addition, trivial wrapper functions written in C have to be linked in for every C++ function and method that is to be accessed from Visual Basic.

Conway's Life

One of the first and simplest artificial life simulations was the game of Life first published in [Gardner 70]. Life isn't really a game in the usual sense, it is an example of a cellular automaton. A two-dimensional surface is occupied by a lattice of cells. At each time step a cell can be in one of a finite number of states. The state at the next time step depends on the cell's current state and the states of the cells around it. In Life, the cell can be in one of two states: alive or dead. A live cell will remain alive if two or three of its neighbors are alive, otherwise it dies. A dead cell will become alive if exactly three of its neighbors are alive, otherwise it stays dead.

The purpose of implementing Life using the SIMBIOSYS framework is to illustrate the use of some of the basic facilities of the toolkit. Three new classes extend the functionality of the SIMBIOSYS framework: LifeSim is derived from bioSimulation, LifeWorld is derived from bioCellWorld, and LifeCell is derived from bioAgent as shown in Figure 36.

Figure 36. Life Class Hierarchy

Class Implementation

The LifeSim constructor takes care of creating and initializing an instance of LifeWorld. The only method LifeSim needs to override is GetData(). In addition to the data provided by its superclass, LifeSim allows clients to retrieve the number of live cells, the number of births in the last generation and the number of deaths in the last generation. All of these are queried from the LifeWorld instance.

The LifeWorld Init() method populates the world with LifeCell instances, one for every discrete location in the world. Since this simulation only executes action cycles, only NextStep() and ResolveAction() need be overridden. NextStep() merely resets the birth and death counters before calling the base class implementation. ResolveAction() honors each cell's intention by killing cells destined to die, and giving life to cells that want to live.

The XformPos() method was overridden for purposes of optimization. Since it is known in advance that all cells have an orientation of 0, there is no need to instantiate a transformation matrix to calculate relative positions. Instead, a simple transposition of the point relative to the cell is done which greatly enhances performance of the simulation.

The largest method by far is the implementation of Redraw(). It makes use of MFC drawing classes to render a frame in offscreen memory. First, various tools needed for drawing are instantiated: a new device context, an offscreen bitmap and brushes used for painting. A live cell and a dead cell are pre-drawn into small bitmaps which are copied to the new frame rather than drawing each cell individually. The background is cleared to black, the a grid is drawn on it. Then for each cell in the world is drawn in the colour according to its current state: grey for dead or green for alive. Once the offscreen bitmap is complete it is copied all at once to the window. This method of frame buffering prevents flickering in the animation.

User Interface

The user interface for Life consists of a map of the world and a graph of the number of live cells in any given generation. The user can start, stop and single step the simulation through a menu. A screendump of the simulation in progress is shown in Figure 37.

Figure 37. Screendump of Life When the application starts up, an instance of LifeSim is created through a call to the DLL. This is kept in a global variable since all interactions through the DLL will need this handle.

The application makes use of a Visual Basic timer control as a clock. When the user selects Start from the Simulation menu, the timer control's interval property is set to 50 milliseconds. Selecting Step from the Simulation menu will reset the interval to 0. When the interval is some positive integer, the timer control's handler is called at the specified interval which calls the application instance's NextStep() method.

After each action cycle, the map is redrawn. When the map (actually a Visual Basic PictureBox control) gets an exposure event, it passes its device context handle to the DLL which relays it to the LifeWorld Redraw method. After the redrawing, the LifeSim instance is queried for the number of live cells in the current generation. This data is passed to the graph control which adds it to the plot.

Genesys/Tracker

The second test simulation is a re-implementation of the UCLA artificial life group's Genesys/Tracker system [Jefferson 92] mentioned on p.55. An ant is evolved to follow a food trail that gets gradually more and more sparse. Two programmatic representations are compared for evolvability: a finite state machine and an artificial neural net.

Class Implementation

The classes created for the Tracker system make use of every class in the framework. TrackerSim contains an instance of TrackerWorld and AntPopulation. TrackerWorld contains several instances of Food, making up the food trail, and a single instance of Ant at any one time. An ant has a instance of bioHapGType which it uses to create either a bioFSM finite state machine or a bioNNet neural network.

The Tracker simulation makes use of breeding cycles, environment cycles and action cycles. An environment cycle is executed for each ant in a generation. At the beginning of each environment cycle a new TrackerWorld is created with the food instances in a pre-defined path (the "John Muir trail") and the ant is placed at the upper right hand corner facing east, at the beginning of the trail. For each action cycle, the ant looks for a piece of food in the cell directly in front of it. It relays this single bit of information to its program which returns one of four actions: do nothing, turn right, turn left, or move forward. If the ant moves onto a piece of food, the food is removed from the world and the ant's fitness score is incremented. After every 200 action cycles, another environment cycle is executed with the next ant in the generation. After the entire generation has been run through a trial, a breeding cycle is invoked and the process begins again with the next generation.

Figure 38. Tracker Class Hierarchy

User Interface

The Tracker simulation uses a multiple document interface (MDI) with a main window containing the menubar and two child windows, one each for the FSM simulation and the neural net simulation as shown in Figure 39. The child windows are based on the Life interface described in the previous section, consisting of a map of the world, a graph of the ongoing progress of the population, and a panel displaying simulation variables.

Each child window has an instance of TrackerSim associated with it. The TrackerSim constructor takes a parameter which determines whether the ant population uses an instance of bioFSM or bioNNet for their programs.

Figure 39. Screendump of Tracker

A prisoners' dilemma variation

This simulation introduces spatial dynamics into the well-studied iterated prisoners' dilemma problem [Axelrod 87]. Two players are engaged in the game. In each round they make a choice to cooperate or defect. If they both cooperate they both get 3 points, the reward. If they both defect, they get 1 point, the penalty. If one cooperates while her opponent defects, the first gets 5 points, the temptation, and the trusting cooperator gets 0 points, the sucker's payoff. The payoff matrix is encapsulated in Figure 40.

             other cooperates  other defects  
I cooperate         3          0              
I defect            5          1

Figure 40. Payoff for the Prisoners' Dilemma

The question is what should a rational player do? An examination of the payoff matrix shows that if you defect every time you score better than cooperating, no matter what your opponent does. The trouble is that if your opponent reasons the same way, you will both end up with a score of one every round, two less than you could do if you both cooperate. Hence the dilemma [Sigmund 93].

Class Implementation

The classes used in this simulation are a variation of the ones used in the Tracker example. In this implementation two populations, one of ants driven by finite state machines, and one of ants driven by neural networks, evolve in the same world simultaneously. In addition to the movement behaviors displayed by the Tracker ants, turn left, turn right, and move ahead, the ant either cooperates or defects in action cycle. This requires a third output bit from the ant's program.

During an action cycle each ant looks in the cell directly ahead and to the cells on each side for another ant. If it finds one, it looks to see if the ant is currently cooperating or defecting. Therefore it retrieves two bits from each of the cells: 00 if there is nothing there, 10 if there is a defecting ant, and 11 if there is a cooperating ant, for a total of six bits of input.

The world object honors the ant's requests to turn and to move ahead into an empty cell. However an intention to move ahead into a cell containing another ant results in a round of the prisoners' dilemma being played out. The world queries the participating ants' intentions to cooperate or defect, and gives the active ant (the one trying to move) an amount of energy according to the payoff matrix in Figure 40. Energy is expended at one point per action cycle and is only replenished through playing the game with other ants. Each ant starts with a small amount of energy (defaulting to 20 points) so it won't survive very long without engaging other ants in play. When an ant runs out of energy, it dies and is removed from the world. When all the ants have died, a breeding cycle is executed. Some maximum age is also defined for the ants (defaulting to 100) which places an upper boundary on the number of action cycles executed before an breeding cycle can take place.

Figure 41. Dilemma Class Hierarchy

User Interface

The user interface for the Dilemma simulation is based on the previous two simulations, consisting of a map of the world, a graph of the evolutionary progress and a panel displaying the current simulation state. As in the Tracker simulation, ants are displayed as triangles pointing in their respective orientations, however they are assigned different colours depending on whether they are FSM ants or neural network ants. In addition they are given a white or black outline corresponding to whether they are currently cooperating of defecting. This simple use of colour gives the observer a remarkably good idea of the dynamics of the interactions. For instance, it is possible to see groups of defectors form stationary clusters as shown in Figure 42.

Figure 42. Screendump from Dilemma

Code Re-use

One measure of functionality is how much of the library is re-used in applications. Though counting lines of code is a notoriously bad metric, it is at least roughly correlated with the amount of effort put into a simulation. Figure 43 shows all the classes that were used in the three test simulations. Below the name of each class is a code showing which simulations used it along with the lines of code in the class implementation.

Figure 43. Code Reuse Table 9 shows a comparison between the total lines of code in each of the three test simulations, and how much of the implementation resides in the SIMBIOSYS library. There are two points worth noting when trying to interpret the numbers in Table 9. The calculations assume the applications exercise all the methods of each class in the library which isn't necessarily the case. In addition, the numbers only loosely reflect the amount of effort saved on coding the application but don't take into account the effort saved on designing the architecture of the simulation which can be quite significant.

            total lines of     lines in        percentage in         
            code               library         library               
Life        1319               934             70.8%                 
Tracker     2448               1829            74.7%                 
Dilemma     2485               1829            73.6%

Table 9. Code Reuse

Comparison with Existing Systems

This section places the SIMBIOSYS toolkit within the context of the simulation framework developed in Chapter 2. The simulation model attributes are applied to each of the test simulations in turn and summarized in Table 10. The simulation implementation attributes are applied to the class framework as a whole as shown in Table 11.

The world in the Life simulation is a 2-D discrete space-oriented environment. The abstraction level of the organisms is on the level of an abstract cell (level 3) and, since this was the only level simulated, the abstraction depth is zero. The physics and biology were both minimal: class A.

The Tracker simulation built with the SIMBIOSYS framework has the same model attributes as the original simulation described on .

The Prisoner's Dilemma system simulates two competing populations giving it an abstraction level of 6 and a depth of 2. The world is basically the same as the one used for the Tracker system: a 2-D discrete space but with the addition of collision detection which moves it to a class B physics. The genetic algorithm uses global competition and mating corresponding to a class B biology.

     System       Abstr.  Abstr.   Metaphysics                    Physics   Biology   
                  level   depth                                                       
Life                3     0        2-D     discrete    space       A         A         
Tracker             5     0        2-D     discrete    structure   A         B         
Dilemma             6     2        2-D     discrete    structure   B         B

Table 10. SimBioSys Model Attributes

The current implementation of the SIMBIOSYS framework is written in C++ for Microsoft Windows. The level of data gathering and visualization reflected in the test simulations is average compared to the systems surveyed in Chapter 2. However the main aspect that differentiates the SIMBIOSYS framework from other systems is the level of extensibility. The base classes of the library encapsulate aspects common to many artificial life simulations and they are designed to be specialized to the specific requirements of novel simulations.

     System       Portability          Extensibility   Data          Visualization    
                                                       Gathering                      
SimBioSys           Windows    C++     E               3             3

Table 11. SimBioSys Implementation Attributes

Summary

Though the test simulations show a fair variation in abstraction level they are quite similar in their respective metaphysics, physics and biology. A more comprehensive evaluation of the SIMBIOSYS framework would include simulations employing different types of worlds, perhaps one- or three-dimensional, and more sophisticated interactions on the physical and biological level.