Food Collection Genetic Program
User Guide
The ant program is a Microsoft .NET 2.0 WinForm program written in C#.
Although the .NET Framework has been ported to make Operating Systems,
your best bet is to use Windows XP or later.
From Windows, you can get the latest .NET Framework using Windows Update or get it directly from microsoft.com
You can run the program online
here,
or download the
source,
or download the
executable only.
The ant program
The ant program consists of 3 tabs:
- Tab 1: The Evolver - This tab runs the Genetic Program that will evolve solutions
to a particular problem. In this tab you pick the map to use, the set of instructions that
will make up the initial random population of ant programs, and other parameters that
drive the evolver, interpreter and ant behavior.
- Tab 2: The Program - In this tab you can view the solution that you just evolved.
You can also look at some canned solutions or even write your own.
- Tab 3: The Simulator - This tab lets you execute the ant programs. You can choose
to run a program you evolved, one you wrote by hand, or one of the canned solutions included in the program.
You can also design a custom map to run the program on or to use in the Evolver tab.
Note: If you haven't read the
Background page yet, you should do that first.
The Evolver
This tab is the actual Genetic Program. It is used to evolve a solution to a particular problem.
Note: On startup, everything is setup to start evolving a solution to a simple food collection problem.
You just need to click Start Genetic Program.
To evolve your own solution to a more complicated problem, you will need to:
-
Determine what the map will look like. This usually determines the complexity of the problem.
You select the map by using the Load Map combo box. There are some canned maps you can select
or you can design your own map on the 3rd tab of the program. Adding water, obstacles, or heavy
food (food requiring more than 1 ant to lift) will all make the solution more difficult to find.
-
Once you choose your map, you must select the instruction set to go with it.
Check the instructions on the left that you want included in the ant programs.
Any instruction that is not checked will not be used to make the initial population or during mutation.
You can get details on each instruction from the Instruction Set page.
-
At minimum, PickUpFood is required or the ants will not be able to return the food to the nest.
If you uncheck "Automatically Drop Food when the Ant is at the Nest", then you also must include the DropFood instruction.
There are several different statements that allow the ants to move. You will want to include at least one of them.
It is also a good idea to include the Two Statements instruction. The programs are stored in a binary tree,
and this statement allows two different instructions to be executed in a if or else block.
-
If food is hidden behind water then you have two choices.
If trees are placed on the map then you can include the PickUpLeaf and DropLeafInWater statements.
This lets ands gather leaves from the tree to use to make a bridge across the water.
If there are no trees on the map, then you will need to include the MoveIntoWater statement.
This will cause the ants to move into the water and die, which builds an ant bridge for the other ants to cross the water.
-
Other statements are not required but you will want to select some of them to help the ants make decisions.
For example, if you don't include the if ( Food Carried ) statement, then the ant has no way of knowing
if it should start walking to the nest or if it should continue to search for food.
For ideas, see the Results page that includes actual results from the Genetic Program
or the Solutions page that contains some straight forward solutions to some standard problems.
You can also go to the 2nd tab of the program to view some of the included canned solutions.
-
Don't make the problem so difficult that the ants cannot get started. If all of the food is across a river
then most programs will not accomplish anything. If some of the food is near the nest then some of the programs
that can find and pick up that food will have a better fitness that those that cannot, even though neither program
will allow the ants to cross the water. This way, the programs that can pick up the nearby food will get used more
often as "parents" in the crossover operation. Otherwise, a program that is all NoOp's will get treated
the same as a near complete solution that just can't cross the water.
The other sections you need to set up to get started are: Initial Population, Crossover / Mutation,
Fitness Calculations, and Interpreter Options. You can get detailed information on these parameters from the
Parameters page.
-
The Initial Population options are used to make the initial set of random ant programs. This area
lets you configure the number of programs and the relative size of each.
-
Crossover and Mutation are used to make new ant programs (solutions) based on the current population.
Two of the better programs from the population are selected as "parents".
These two programs are used to make two new "children" programs.
Hopefully the child programs will be better (lower fitness) than the parents.
After crossover, mutation is performed on each child. Mutation will randomly change one instruction in the program.
-
The Fitness Calculation parameters are used to grade each program. The lower the fitness, the better.
The fitness parameters determine how much each fitness input variable will effect the fitness grade.
For example, by default returning food to the nest is the most important thing, so it has the highest
value and the greatest effect on fitness.
-
The Interpreter is used to execute the ant program on the given map. The interpreter options effect
the behavior of the ants.
Once you think everything is setup, give it one final check to make sure everything is correct.
It can take hours even on a fast PC to get any type of a solution. You don't want to find out hours
later that you made a mistake.
When everything is set, click the Start Genetic Program button. You should soon see updates in the
set of text boxes on the right. It will first make the Initial Population, which can take over an hour
depending on the number of ants, number of turns per ant, the population size, the average program size
and the speed of your computer. Once the initial population is created the crossover counter will start
to go up. Detailed information on the best solution found so far is provided along with some information
about the average program fitness and size.
You can pause and resume the Genetic Program at any time. You can also udpate any of the options
while the program is paused, including adding or removing ant programs from the population.
Note: Changing parameters will not cause the fitness to be re-evaluated on the existing programs.
The Program
This tab lets you view the program you just evolved, view one of the canned solutions, or create a progarm from scratch.
To view the program you just evolved, go to the "Load a Genetic Program Solution" text box, and select "Load your last Evolved Solution".
Your program will then appear in the program tree above.
To view a premade canned solution, use the same text box to choose one of the other options.
Before making your own solution, you will probably want to start with one of the existing premade solutions.
To modify the solution, select an instruction in the program tree, select an instruction in the list on the left,
and then select one of the four buttons to add, remove, or replace an instruction in the program tree.
The Simulator
The simulator tab will show the ant programs in action. To run an ant program you must select a map and a program solution.
By default, everything is setup with a map and solution for a simple light weight food collection problem.
You can change the map by picking a premade map from the "Load Map" textbox or you can create your own.
You can also choose to use the same map from Tab 1 that was used to evolve an ant program.
To create a map, click on one of the map icons and then click the map to place that item.
Each map must contain a nest for the ants to start on and at least one piece of food.
Use the "Load Solution" text box to choose a solution to run. You can pick the solution you evolved from Tab 1,
a solution you created by hand from Tab 2, or use one of the premade solutions. The premade solutions were
designed to run on one of the premade maps.
| Solution | Map |
|---|
| Simple Light Grouped Food Solution | Three Food(1) Piles |
| Simple Heavy Food Solution | Six Weight Food(1,3,6) Piles
Seven Food(6) Pieces
Ten Food(9) Pieces |
| River Solution w/ Dead Ants | One Food(1) Pile Witd River |
| River Solution w/ Trees | Three Food(1) Piles River Tree |
| Heavy Food w/ River Solution | Six Food(5) Pieces Wall/River |
The sliders on the right control the number of ants, the pheromones, and the amount of turns an
ant will wait for help in trying to lift a heavy piece of food. The Ant Movement Speed can be used
to slow down the ant movement to you can see what they are doing.
When everything is set, click the Test Solution button to start the ants.