Piyush Shukla(neoned71)
By Piyush Shukla in genetic algorithms —

Ant Colony Optimization...Genetic Programming & Pygame

Using DEAP module to learn effective behavioral function for ants with food in the vicinity. The visual representation is generated using PyGame game engine.

Ant Colony Optimization...Genetic Programming & Pygame
Photo by Andre Moura: https://www.pexels.com/photo/black-ants-lining-up-2563028/

Problem Statement that we solve using genetic programming

For an ant, such that if left in an environment, could follow a given algorithm and easily find food and eat and thrive....What is the algorithm(tree) which can be formed using the basic building components given as a Primitive Set(node).

If you are new to genetic algorithms, please head over to this article for the basics. Then head over to this for the Introduction into genetic Programming using DEAP framework.

Please note, that the code for this article is a derivation of the ant colony optimization example, from DEAP evolutionary programming module. We will modify the code to add the visual representation of an ant and the food using pygame module.

Overview

Let's look at the high level steps we will take in this article,

  1. Create an Ant class with methods corresponding to moving, eating, etc.
  2. Setup Pygame: pygame to render ant and the food.
  3. Using Deap: deap to handle all the genetic programming stuff.

Ant Class

Create a class for ant called AntSimulator, that will accommodate movement methods which transforms the position of an ant, and if it so happens that the food is where the ant is then it eats the food and food is disappeared.

class AntSimulator(object):
    direction = ["north","east","south","west"]
    dir_row = [1, 0, -1, 0]
    dir_col = [0, 1, 0, -1]


    def __init__(self, max_moves):
        self.max_moves = max_moves
        self.moves = 0
        self.eaten = 0
        self.routine = None

    def _reset(self):
        self.row = self.row_start 
        self.col = self.col_start 
        self.dir = 1
        self.moves = 0  
        self.eaten = 0
        self.matrix_exc = copy.deepcopy(self.matrix)

    @property
    def position(self):
        return (self.row, self.col, self.direction[self.dir])

    def turn_left(self): 
        if self.moves < self.max_moves:
            self.moves += 1
            self.dir = (self.dir - 1) % 4

    def turn_right(self):
        if self.moves < self.max_moves:
            self.moves += 1    
            self.dir = (self.dir + 1) % 4

    def move_forward(self):
        if self.moves < self.max_moves:
            self.moves += 1
            self.row = (self.row + self.dir_row[self.dir]) % self.matrix_row
            self.col = (self.col + self.dir_col[self.dir]) % self.matrix_col
            if self.matrix_exc[self.row][self.col] == "food":
                self.eaten += 1
            self.matrix_exc[self.row][self.col] = "passed"

    def sense_food(self):
        ahead_row = (self.row + self.dir_row[self.dir]) % self.matrix_row
        ahead_col = (self.col + self.dir_col[self.dir]) % self.matrix_col        
        return self.matrix_exc[ahead_row][ahead_col] == "food"

    def if_food_ahead(self, out1, out2):
        return partial(if_then_else, self.sense_food, out1, out2)

Along with these methods, we also need an ant to play its own algorithm which is constructed using the primitives we have defined(in the section of genetic programming). This is done using run() method. 

   def run(self,routine,individual):
        self._reset()
        global gen
        global start_gen
        if gen >= start_gen:
            print(individual)

        while self.moves < self.max_moves:
            routine()
            if gen >= start_gen:
                renderFunction(self)
        
        

    def parse_matrix(self, matrix):
        self.matrix = list()
        for i, line in enumerate(matrix):
            self.matrix.append(list())
            for j, col in enumerate(line):
                if col == "#":
                    self.matrix[-1].append("food")
                elif col == ".":
                    self.matrix[-1].append("empty")
                elif col == "S":
                    self.matrix[-1].append("empty")
                    self.row_start = self.row = i
                    self.col_start = self.col = j
                    self.dir = 1
        self.matrix_row = len(self.matrix)
        self.matrix_col = len(self.matrix[0])
        self.matrix_exc = copy.deepcopy(self.matrix)

We also need a method to parse our map of the world that has food positions in it. That is why we also created parse_matrix. The matrix parameter is obtained by reading a text file called santafe_trail.txt, which is also taken straight from DEAP module for evolutionary algorithms.

S###............................
...#............................
...#.....................###....
...#....................#....#..
...#....................#....#..
...####.#####........##.........
............#................#..
............#.......#...........
............#.......#........#..
............#.......#...........
....................#...........
............#................#..
............#...................
............#.......#.....###...
............#.......#..#........
.................#..............
................................
............#...........#.......
............#...#..........#....
............#...#...............
............#...#...............
............#...#.........#.....
............#..........#........
............#...................
...##. .#####....#...............
.#..............#...............
.#..............#...............
.#......#######.................
.#.....#........................
.......#........................
..####..........................
................................

This is the map of the world and # are the food placed inside the 2-D plane of the ant. Ant has to maximize its eaten by quickly finding all the food before its lifetime is up, which is 600 steps in my example. Let's initialize our ant.

ant = AntSimulator(600)

In the next step, we shall add code to render the map with food and the ant, along with how well eaten she is.

Pygame

The code required for Pygame setup incudes,

import pygame
pygame.init()
scale=10
window = pygame.display.set_mode((800, 600))

def renderFunction(ant):
    window.fill((255, 255, 255))
    for i in range(len(ant.matrix_exc)):
        for j in range(len(ant.matrix_exc[ant.row])):
            if ant.matrix_exc[i][j] == "food":
                pygame.draw.circle(window,(34,34,23),(i*scale,j*scale),5)
    pygame.draw.circle(window,(244,34,23),(ant.row*scale,ant.col*scale),10)
    pygame.draw.circle(window,(244,34,23),(ant.row*scale,ant.col*scale),ant.eaten,2)
    pygame.time.wait(100)
    pygame.display.update()

This is not a tutorial on Pygame by any angle, but then we do not need that much to go on. Let me explain what we are doing here,

  1. Importing pygame an initializing it by calling its pygame.init() function.
  2. Creating a window  object, setting the resolution to 800x600.
  3. Create a render function which, in each call, renders all the food as black dots and the ant by its red dot. To denote how eaten the ant is, I have used a red hollow circle which has it's radius as ant.eaten.
  4. We then sleep for 100ms in between the loop and then update the display, pygame.display.update().

Now we go ahead and add the genetic programming code.

Deap: Genetic Programming Setup

First add the imports and some basic utility functions to be added as primitives,

from deap import algorithms
from deap import base
from deap import creator
from deap import tools
from deap import gp

def progn(*args):
    for arg in args:
        arg()

def prog2(out1, out2): 
    return partial(progn,out1,out2)

def prog3(out1, out2, out3):     
    return partial(progn,out1,out2,out3)

def if_then_else(condition, out1, out2):
    out1() if condition() else out2()

Let's construct the primitives set required by the deap framework.

pset = gp.PrimitiveSet("MAIN", 0)
pset.addPrimitive(ant.if_food_ahead, 2)
pset.addPrimitive(prog2, 2)
pset.addPrimitive(prog3, 3)

# also add ant methods to move to our set of primitives.
pset.addTerminal(ant.move_forward)
pset.addTerminal(ant.turn_left)
pset.addTerminal(ant.turn_right)

Creating the toolbar which will be a container for all the functions used during the evolution process.



creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", gp.PrimitiveTree, fitness=creator.FitnessMax)

toolbox = base.Toolbox()

# Attribute generator
toolbox.register("expr_init", gp.genFull, pset=pset, min_=1, max_=10)

# Structure initializers
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.expr_init)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

# some functions to keep track of the generation, although it does not work as expected.
funcCalled=0
gen=0
start_gen=50


def evalArtificialAnt(individual):
    global funcCalled
    global gen
    # Transform the tree expression to functional Python code
    routine = gp.compile(individual, pset)
    # Run the generated routine
    ant.run(routine,individual)
    #we keep an account of 300 population and then increment the generation counter
    if funcCalled==300:
        funcCalled=0
        gen+=1
        print("gen incremented:",gen)
    funcCalled+=1
            # print(self.moves)
       
    return ant.eaten,

toolbox.register("evaluate", evalArtificialAnt)
toolbox.register("select", tools.selTournament, tournsize=7)
toolbox.register("mate", gp.cxOnePoint)
toolbox.register("expr_mut", gp.genFull, min_=0, max_2)
toolbox.register("mutate", gp.mutUniform, expr=toolbox.expr_mut, pset=pset)

This code is very to the code example present in the Symbolic Regression Article. So now, we give the last remaining main() which will kick start the process.

def main():
    random.seed(69)

    with  open("santafe_trail.txt") as trail_file:
      ant.parse_matrix(trail_file)

    pop = toolbox.population(n=300)
    hof = tools.HallOfFame(1)
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", numpy.mean)
    stats.register("std", numpy.std)
    stats.register("min", numpy.min)
    stats.register("max", numpy.max)

    algorithms.eaSimple(pop, toolbox, 0.5, 0.2, 200, stats, halloffame=hof)

    return pop, hof, stats

if __name__ == "__main__":
    main()

Now, with tha we are all set to start training, we shall see the screen after 70-80 generations because of a condition inside the renderFrame function.

Results

Execute the code by saving it to the file ant_gp.py and let us begin,

$ python3 ant_gp.py

The result is in this video,

One of the corresponding algorithms that is learnt by the ant is shown below,

prog2(
	prog2(
    	if_food_ahead(
        	prog3(
            	move_forward,
                move_forward,
                turn_left
               ),
               prog2(
               	turn_right,
                turn_right
                )
             ),
          if_food_ahead(
          	move_forward,
            if_food_ahead(
            	move_forward,
                turn_right
                )
             )
          ),
          prog2(
          	turn_left,
            turn_right
          )
)

Full Source Code: My Github Page!

Conclusion

We started with 300 individual functions which defined the brain of the ants. We recursively called the function again for the given time steps, recording the position the ants move to.

Every time an ant eats a food item, its ant.eaten value gets incremented and the best eaten value ants are selected for mating for the next generation.

We saw that the 32nd generation ants are capable enough to eat all the food available in the map.

Sign up for the blog-newsletter! I promise that we do not spam...