Ant Food Collection Genetic Program

Ant Food Collection Genetic Program
User Guide

The ant program is a Microsoft .NET WinForm program written in C#. Although the .NET Framework has been ported to several Operating Systems, your best bet is to use Windows. You can:

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 update 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 program 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 With 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.