| Algorithm type | Generational |
|---|---|
| Population size | 1024 |
| Selection method | Tournament of size 3 |
| Elitism | Replace random 2 offspring with previous best |
| Crossover method | Subtree with 90 percent chance to choose an internal node |
| Crossover rate | 80 percent |
| Mutation method | 2 percent chance per node to mutate |
| Operation set | prog-2, prog-3, if-food-ahead |
| Terminal set | left, right, forward |
| Fitness function | Number of food pieces eaten |
| Size control | Size penalty of 0.1 * total applied to fitness |
Not much has changed since Project #2. The genetic program was revamped to imitate “ants” crawling along the Santa Fe Trail, with the goal of finding and eating food. The genetic algorithm, population size, selection method, elitism, crossover method, and crossover rate are the same as previous.
To do this, a map class was implemented which handled the details of
having a 32 by 32 toroidial grid of blank, food, and marked locations.
This map had a position struct for the (x, y) coordinate pair and
direction of the ant, along with the width and height of the grid, and
the current tick count, maximum ticks, score, and maximum score (that
is, available food). Its primary interface was left(), right(),
forward() and look() functions; the first three increment the tick
count, where left() and right() change the ant’s direction,
forward() moves the ant forward and consumes food (incrementing the
score need be), and look() returns a boolean value used by the
if-food-ahead function. The individual’s evaluate function receives
a Map object by value (a copy of the original), and passes that by
reference to the root node’s evaluate function in a while loop
conditioned on the ant being active() (that is, still has ticks
left). Inside the evaluation method, when the maximum number of steps
is reached, it returns. In this way, the ant’s “decision” tree can be
continusouly evaluted while updating the map with the corresponding
movements, with prog-2, prog-3, and if-food-ahead working as
expected (causing more than one move per evalution of the tree).
The mutation sequence is run on every new individual in the offspring
generation. With a two percent chance per node, it mutates a leaf
node into another leaf node, and an internal node into another
internal node. When an internal node of arity three (prog-3) is
mutated into one of arity two (prog-2 and if-food-ahead), the last
child node is popped from its vector to correct the arity.
Conversely, when a node of arity two is mutated into one of arity
three, a new node is created. This node is made with an equal chance
to be “grown” or “fully” generated. Its maximum depth is randomly
chosen from between zero and four. This depth range was chosen with
the consideration that the trees popped in the previous correction may
have been quite large and thus should be compensated for, but I
additionally did not want to introduce unwanted code growth.
The fitness of the ant is the number of food pieces it can eat on the on the Santa Fe Trail subject to the constraint of 600 ticks, where a tick is either turning left or right, or moving forward. As such, this became a maximization algorithm. To control code growth, a size penalty of ten percent of the total tree size is substracted from this fitness when used in comparisons. The adjusted fitness (as presented graphically), is the score (that is, actual number of food pieces eaten, no penalties applied) divided by the total number of food pieces available (in our case, 90).
The graphs are to be found at the end of this report.
- Score: 75
- Elapsed time: 11.55s
- Size: 70
- Iterations: 1024
- Population size: 128
- Initial depth: 6
# 'x' is food and 'o' is ant trail ooxo...o....o...o.....o...oooooo o..o...o....ooooooooooo...o..... o..o...o........o.....o..xox.... oooooooo........o.....o.x.o..ooo o..o........o...o.....o.x.o..o.. o..ooooooooxo...ooooooooooo..o.. o..o......o.o.........o...o..o.. o..o..o...o.o.........o...o..o.. o..o..o...o.o.......x.o...o..o.. o..o..o...o.o.......oooooooooo.. o..o..o...o.o.......o.oooooooooo ...o..o...o.o.......o.....o.o... ...o..o...o.o.......o.....o.ox.. ...o..o...o.o.......o.....o.o... oooo..o...o.o.......o.....oooooo ......o...ooooooooooo..x....o... ......o.....o....x..........o... ooooooo.....o...o...........oooo ......o.....o...o.......x....... ......o.....o...o..........x.... ......o.....o...o............... ......o.....o...o............... ......o.....o...o.........o..... ......o.....o...o.....ox..o..... .oooooooooooo...o.....o...o..... .o....o.....o...o.....o...o..... .o.o..o.....o...o.....o...o..... .o.o..ooooooooooo.....o...o..... .o.o...oooooooooo.....o...o..... .o.o...o....o...o.....o...o..... .oxoxx.o....o...o.....o...o..... .o.o...o....o...o.....o...o.....
- Score: 74
- Elapsed time: 84.7s
- Size: 40
- Iterations: 1024
- Population size: 1024
- Initial depth: 7
# 'x' is food and 'o' is ant trail ooxo...o....o...o.....o...oooooo o..o...o....ooooooooooo...o..... o..o...o........o.....o..xox.... oooooooo........o.....o.x.o..ooo o..o........o...o.....o.x.o..o.. o..ooooooooxo...ooooooooooo..o.. o..o......o.o.........o...o..o.. o..o..o...o.o.........o...o..o.. o..o..o...o.o.......x.o...o..o.. o..o..o...o.o.......oooooooooo.. o..o..o...o.o.......o.oooooooooo ...o..o...o.o.......o.....o.o... ...o..o...o.o.......o.....o.ox.. ...o..o...o.o.......o.....o.o... oooo..o...o.o.......o.....oooooo ......o...ooooooooooo..x....o... ......o.....o....x..........o... ooooooo.....o...o...........oooo ......o.....o...o.......x....... ......o.....o...o..........x.... ......o.....o...o............... ......o.....o...o............... ......o.....o...o.........o..... ......o.....o...o.....ox..o..... .oooooooooooo...o.....o...o..... .o....o.....o...o.....o...o..... .o.o..o.....o...o.....o...o..... .o.o..ooooooooooo.....o...o..... .o.o...oooooooooo.....o...o..... .o.o...o....o...o.....o...o..... .oxoxx.o....o...o.....o...o..... .o.o...o....o...o.....o...o.....
- Score: 78
- Elapsed time: 72.70s
- Size: 54
- Iterations: 1024
- Population size: 1024
- Initial depth: 8
# 'x' is food and 'o' is ant trail oooo...o..............o.o....o.. oooo...o..............o.o....o.. .ooo...o................oxxx.o.. .ooo...o................o....o.. .oooooooooooo...........o....o.. ..ooooooooooooooooooooooo....o.. oooo...o....o.o..........ooooooo ..o....o....o.o..........o...o.. ..o....o....o.o.....x....o...o.. ..o.........o.o.....x....o...o.. ..o.........o.o.....oooooooooo.. ..o.......ooooooooooo....o...... ..o.......o.o.o.....o....o...x.. ..o.......o.ooooooooooo..o...... ..o.......o.o.o.....o.o..oxxx... o.........o.o.o.....o.oooooooooo o.........o.o...oooooooooo...... o.........o.o...o...o.o..o...... o.........o.o...o...o.o.xo...... o.........o.o...o...o.o..o.x.... o.........o.o...o...o.o..o...... o.........o.o...o...o.o..o...... o...........o...o.....o..ox..... o...........o...o.....oooooooooo o..oooooooooo...o.....o..o...... oooo............o.....o.oooooooo oooo............o.....o.oo...... oooo...oooooooooo.....o.o....... oooo...o..............o.o....... oooo...o..............o.o....... oooooooo..............o.o....ooo oooo...o..............o.o....o..
I found that although I could get good fitnesses, I was not able to find parameters that would yield a full solution (fitness of 90). I am in the process of implementing more genetic operators, with the hope that the extra diversity they will provide will help to increase the average fitness. As is clear from the graphs, the average fitness plateaus relatively quickly (although for results two and three, this is because of the excessive number of iterations; the best plateaued as well). Additionally, after inspecting sizes and depths (not represented here due to time constraints), I found that the cause of the lack of diversity was due to small tree sizes, and interestingly low depths. I was onto this when generating the presented results, as I kept increasing the maximum depth for ramped half-and-half. I believe I would get better results by bumping that up further, and adding more genetic matierial to the population. In this way, the individuals may not stagnate, and thus should produce closer to perfect solutions.
In summary: ants are hard.
