AntEvolver

---

Overview

An ant family is a group of ants that behave in a similar manner (a family is then defined by its behavior). Each ant family is evaluated in a 2-dimensional environment E, for a duration of t time units. At the beginning of each evaluation run, the environment contains $f$₀^E particules of food.

Some family behaviors might cause some ants to pick up food and bring it back to the nest. Other family behaviors might cause some ants to cooperate (using pheromones to transmit information). We want to encourage such behavior and reward the families that have them.

We want to evolve a family that brings back a maximum amount of food from any randomly created environment (actually, what we really want to do is have fun and explore group behavior emergence, but for now let's say we just want to have ants that collect as much food as possible)

The behavior of each ant in a given family is defined by an algorithm. An example of such an algorithm could be from an individual ant's perspective:

• If I'm carrying food, and I'm home, then I should drop the food. However, if I'm carrying food and I'm not home, then I should head towards home, and on the way, I should drop pheromones to help the other ants find their way to the food source.
• If I'm not carrying food, then I should check to see if there is food where I am. If there is, I should pick it up. If there isn't, I should check and see if there is food nearby. If there is food nearby, I should go to where there is food. If there isn't any food nearby, I should check for pheromones from other ants, and follow the trail if I find one. If none of this applies, I might just as well move randomly until it does.

Every ant in a given family behaves the same way, but every family will code a different behavior. The best behaviors (see below for more on the objective function) will then be rewarded by having a higher chance of reappearing in the next round of evaluation.

The example algorithm above is simple algorithm and seems to make sense. But is it really the best one? Does the manner by which ants use their capacity to produce and sense pheromones in that algorithm fully optimize the total gathering of food (team work). Might it not be more efficient if instead of carrying the food straight home, the ants dropped it on the way for other ants to pick up ? Or used a strategy that was more complicated ?

Crossover

The purpose of crossover is the production of a genetically diverse population of behaviors. Because each behavior is coded as a tree, it is imperative that the crossover operator that is used forces the production of syntactically valid offspring.

There are two ways of induring syntactic validity: either by reparing faulty trees that are produced by random crossover or setting rules of formation that prohibit the formation of faulty trees.

It is the second approach that was chosen for this task. The specification of the typed language called Antze that was used can be downloaded here is because during the evolution process In order to evolve behavior that were complicated, ....evolving valid program trees using type theory

The Language

• $PICKUP: (ENV\xx ENVOBJECT)\xx ANT\rarr ENV\xx (ANT\xx ENVOBJECT)$
• $DROP: ENV\xx (ANT\xx ENVOBJECT)->(ENV\xx ENVOBJECT)\xx ANT$
• $MOVELEFT : (ENV\xx ANT)\rarr (ENV\xx ANT)$
• $MOVEFRONT : (ENV\xx ANT)\rarr (ENV\xx ANT)$
• $MOVERIGHT : (ENV\xx ANT)\rarr (ENV\xx ANT)$
• $TURNRIGHT : ANT\rarr ANT$
• $TURNLEFT : ANT\rarr ANT$
• $PRODUCEPHEROMONE : ANT\rarr (ANT\xx ENVOBJECT)$
• $SENSEPHEROMONE : (ENV\xx ANT)\rarr bool$
• $SENSEFOOD : (ENV\xx ANT)\rarr bool$

Each ant can only move forward, to the left or to the right. Likewise, an ant can only sense for food to its right, left or front. The environment is toroidal (north wraps to south and east wraps to west).

The environmnet can do the following:

• $GIVEOBJECT : ENV \rarr (ENV\xx ENVOBJECT)$
• $ADDOBJECT: (ENV\xx ENVOBJECT)\rarr ENV$

In order to avoid behavior evolution that overfits a specific environment, every time a new environment is created, the food distribution and quantity is different. There is no most efficient algorithm that applies to all the environments.

The Evaluation function

Each family is evaluated in $$E by the objective function $$F_g within $$t_g time units. At the beginning of the run, $$E contains $$f⁰_E units of food and $$f^t-1_E at the end. For each families, $$F_g returns a real value proportional to $($f^t-1_E-f⁰_E)/ n_F where $$n_F is the number of ants in the family. The population size (the number of families being evaluated) is $\backslash lambda$

The Software:

The ants behavior is coded in a tree like structure called a CDNAStatement. These are program tree, but they also happen to represent the genotype of the ants. AntEvolver evolves CDNAStatements. It then evaluates each CDNAStatements using an objective function whose primary input is the amount of food a family of ants whose genotype is a particular CDNAStatement gathers. A fitness based non-deterministic selection process is then applied, a bit of mutation is shaked up in the mix and vodka. I mean voila.

Using the software

There are three modes:

• Ant Simulation mode

  In this mode a CDNAStatement (program tree) can be seen in action in the environment. In this mode, the settings for the size of the environment grid and the number of ants can be set by choosing
  View -> Setting in the main menu. There is also a slider rule that allows the setting of the pheromonal strength. The
  file->open/file->save features allows the opening and the saving of DNAStatement files (.ant extension). The Play button on the right toolbar will start the simulation, while the Pause button will pause it.

  When the simulation is paused, the indicator in the toolbar giving the amount of food left in the environment is updated (not while it is running). Make sure that the simulation is paused before changing any settings while a simulation is running.

  • The I button on the left toolbar (simulation should be paused) will reset the environment
  • The Grid button on the left toolbar will toggle grid view
  • The Pheromone View Button on the first Resizable bar will toggle pheromone Viewing ·
  • The G button on the left toolbar (simulation should be paused) will open DNAStatement in the Tree mode
  
  

• Tree mode

  In Tree mode, the CDNAStatement is displayed in a Tree View control. It can be edited by selecting the new statement and right clicking on the tree item that is to be replaced. Hitting the refresh tree button will then validate the new tree. Make sure the tree is refreshed after a compound else statement is introduced in the tree.
  
  

• Evolve Mode

  Creating a new GP is done by selecting
  File->New->Evolver on the main menu. To start the evolution of the GP, simply enter the generation number to which it should evolve in the EvolveTo edit box on the second top toolbar and press the play button.

  Each GP is represented as an entry in the main view, and double clicking on its ID number will open it in Tree Mode. When a GP is selected it can be either:

  • Saved as an ant file: File->save,
  • Ant Simulated directly by pressing the Play Individual button (top toolbar)
  • Viewed as a tree by double clicking on it.