## Blog: Genetic Algorithms

## A genetic algorithm is a type of evolutionary algorithm. So, in order to understand genetic algorithms, we need to discuss evolutionary algorithms.

An evolutionary algorithm is a meta-heuristic optimization algorithm that applies the principles of evolution to solve problems. The concept of evolution is similar to the one we find in nature. We directly use the problem’s functions and variables to arrive at the solution. But in a genetic algorithm, any given problem is encoded in bit patterns that are manipulated by the algorithm.

The underlying idea in all evolutionary algorithms is that we take a population of individuals and apply the natural selection process. We start with a set of randomly selected individuals and then identify the strongest among them. The strength of each individual is determined using a fitness function that’s predefined. In a way, we use the survival of the fittest approach.

We then take these selected individuals and create the next generation of individuals by recombination and mutation. We will discuss the concepts of recombination and mutation in the next section. For now, let’s think of these techniques as mechanisms to create the next generation by treating the selected individuals as parents.

Once we execute recombination and mutation, we create a new set of individuals who will compete with the old ones for a place in the next generation. By discarding the weakest individuals and replacing them with offspring, we are increasing the overall fitness level of the population. We continue to iterate until the desired overall fitness is achieved.

A genetic algorithm is an evolutionary algorithm where we use a heuristic to find a string of bits that solves a problem. We continuously iterate on a population to arrive at a solution. We do this by generating new populations containing stronger individuals. We apply probabilistic operators such as selection, crossover, and mutation in order to generate the next generation of individuals. The individuals are basically strings, where every string is the encoded version of a potential solution.

A fitness function is used that evaluates the fitness measure of each string telling us how well suited it is to solve this problem. This fitness function is also referred to as an evaluation function. Genetic algorithms apply operators that are inspired by nature, which is why the nomenclature is closely related to the terms found in biology.

#### Fundamental concepts in genetic algorithms

In order to build a genetic algorithm, we need to understand several key concepts and terminology. These concepts are used extensively throughout the field of genetic algorithms to build solutions to various problems. One of the most important aspects of genetic algorithms is randomness. In order to iterate, it relies on the random sampling of individuals. This means that the process is non-deterministic. So, if you run the same algorithm multiple times, you might end up with different solutions.

Let’s talk about population. A population is a set of individuals that are possible candidate solutions. In a genetic algorithm, we do not maintain a single best solution at any given stage. It maintains a set of potential solutions, one of which is the best. But the other solutions play an important role during the search. Since we have a population of solutions, it is less likely that will get stuck in a local optimum. Getting stuck in the local optimum is a classic problem faced by other optimization techniques.

Now that we know about population and the stochastic nature of genetic algorithms, let’s talk about the operators. In order to create the next generation of individuals, we need to make sure that they come from the strongest individuals in the current generation. The mutation is one of the ways to do it. A genetic algorithm makes random changes to one or more individuals of the current generation to yield a new candidate solution. This change is called mutation. Now this change might make that individual better or worse than existing individuals.

The next concept here is recombination, which is also called crossover. This is directly related to the role of reproduction in the evolution process. A genetic algorithm tries to combine individuals from the current generation to create a new solution. It combines some of the features of each parent individual to create this offspring. This process is called crossover. The goal is to replace the weaker individuals in the current generation with offspring generated from stronger individuals in the population.

In order to apply crossover and mutation, we need to have selection criteria. The concept of selection is inspired by the theory of natural selection. During each iteration, the genetic algorithm performs a selection process. The strongest individuals are chosen using this selection process and the weaker individuals are terminated. This is where the survival of the fittest concept comes into play. The selection process is carried out using a fitness function that computes the strength of each individual.

#### Generating a bit pattern with predefined parameters

Now that we know how a genetic algorithm works, let’s see how to use it to solve some problems. We will be using a Python package called `DEAP`

. You can find all the details about it at http://bit.ly/2PTutiH. Let’s go ahead and install it by running the following command on your Terminal:

$ pip3 install deap

Now that the package is installed, let’s quickly test it. Go into the Python shell by typing the following on your Terminal:

$ python3

Once you are inside, type the following:

>>> import deap

If you do not see an error message, we are good to go.

In this section, we will solve a variant of the One Max problem. The One Max problem is about generating a bit string that contains the maximum number of ones. It is a simple problem, but it’s very helpful in getting familiar with the library as well as understanding how to implement solutions using genetic algorithms. In our case, we will try to generate a bit string that contains a predefined number of ones. You will see that the underlying structure and part of the code is similar to the example used in the `DEAP`

library.

Create a new Python file and import the following:

import random

from deap import base, creator, tools

Let’s say we want to generate a bit pattern of length 75, and we want it to contain `45`

ones. We need to define an evaluation function that can be used to target this objective:

# Evaluation function

def eval_func(individual):

target_sum = 45

return len(individual) - abs(sum(individual) - target_sum),

If you look at the formula used in the preceding function, you can see that it reaches its maximum value when the number of ones is equal to `45`

. The length of each individual is *75*. When the number of ones is equal to `45`

, the return value would be *75.*

We now need to define a function to create the toolbox. Let’s define a `creator`

object for the fitness function and to keep track of the individuals. The `Fitness`

class used here is an abstract class and it needs the `weights`

attribute to be defined. We are building a maximizing fitness using positive weights:

# Create the toolbox with the right parameters

def create_toolbox(num_bits):

creator.create("FitnessMax", base.Fitness, weights=(1.0,))

creator.create("Individual", list, fitness=creator.FitnessMax)

The first line creates a single objective maximizing fitness named `FitnessMax`

. The second line deals with producing the individual. In a given process, the first individual that is created is a list of floats. In order to produce this individual, we must create an `Individual`

class using the `creator`

. The fitness attribute will use `FitnessMax`

defined earlier.

A `toolbox`

is an object that is commonly used in `DEAP`

It is used to store various functions along with their arguments. Let’s create this object:

# Initialize the toolbox

toolbox = base.Toolbox()

We will now start registering various functions to this `toolbox`

. Let’s start with the random number generator that generates a random integer between `0`

and `1`

. This is basically to generate the bit strings:

# Generate attributes

toolbox.register("attr_bool", random.randint, 0, 1)

Let’s register the `individual`

function. The method `initRepeat`

takes three arguments – a container class for the individual, a function used to fill the container, and the number of times we want the function to repeat itself:

# Initialize structures

toolbox.register("individual", tools.initRepeat, creator.Individual,

toolbox.attr_bool, num_bits)

We need to register the `population`

function. We want the population to be a list of individuals:

# Define the population to be a list of individuals

toolbox.register("population", tools.initRepeat, list, toolbox.individual)

We now need to register the genetic operators. Register the evaluation function that we defined earlier, which will act as our fitness function. We want the individual, which is a bit pattern, to have `45`

ones:

# Register the evaluation operator

toolbox.register("evaluate", eval_func)

Register the crossover operator named `mate`

using the `cxTwoPoint`

method:

# Register the crossover operator

toolbox.register("mate", tools.cxTwoPoint)

Register the mutation operator named mutate using `mutFlipBit`

. We need to specify the probability of each attribute to be mutated using `indpb`

:

# Register a mutation operator

toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)

Register the selection operator using `selTournament`

. It specifies which individuals will be selected for breeding:

# Operator for selecting individuals for breeding

toolbox.register("select", tools.selTournament, tournsize=3)

return toolbox

This is basically the implementation of all the concepts we discussed in the preceding section. A toolbox generator function is very common in `DEAP`

and we will use it throughout this article. So it’s important to spend some time to understand how we generated this toolbox.

Define the `main`

function by starting with the length of the bit pattern:

if __name__ == "__main__":

# Define the number of bits

num_bits = 75

Create a toolbox using the function we defined earlier:

# Create a toolbox using the above parameter

toolbox = create_toolbox(num_bits)

We need to seed the random number generator so that we get repeatable results:

# Seed the random number generator

random.seed(7)

Create an initial population of, say, `500`

individuals using the method available in the `toolbox`

object. Feel free to change this number and experiment with it:

# Create an initial population of 500 individuals

population = toolbox.population(n=500)

Define the probabilities of crossing and mutating. Again, these are parameters that are defined by the user. So you can change these parameters and see how they affect the result:

# Define probabilities of crossing and mutating

probab_crossing, probab_mutating = 0.5, 0.2

Define the number of generations that we need to iterate until the process is terminated. If you increase the number of generations, you are giving it more freedom to improve the strength of the population:

# Define the number of generations

num_generations = 60

Evaluate all the individuals in the population using the fitness functions:

print('\nStarting the evolution process')

# Evaluate the entire population

fitnesses = list(map(toolbox.evaluate, population))

for ind, fit in zip(population, fitnesses):

ind.fitness.values = fit

Start iterating through the generations:

print('\nEvaluated', len(population), 'individuals')

# Iterate through generations

for g in range(num_generations):

print("\n===== Generation", g)

In each generation, select the next generation individuals using the selection operator that we registered to the toolbox earlier:

# Select the next generation individuals

offspring = toolbox.select(population, len(population))

Clone the selected individuals:

# Clone the selected individuals

offspring = list(map(toolbox.clone, offspring))

Apply crossover and mutation on the next generation individuals using the probability values defined earlier. Once it’s done, we need to reset the fitness values:

# Apply crossover and mutation on the offspring

for child1, child2 in zip(offspring[::2], offspring[1::2]):

# Cross two individuals

if random.random() < probab_crossing:

toolbox.mate(child1, child2)

# "Forget" the fitness values of the children

del child1.fitness.values

del child2.fitness.values

Apply mutation to the next generation individuals using the corresponding probability value that we defined earlier. Once it’s done, reset the fitness value:

# Apply mutation

for mutant in offspring:

# Mutate an individual

if random.random() < probab_mutating:

toolbox.mutate(mutant)

del mutant.fitness.values

Evaluate the individuals with invalid fitness values:

# Evaluate the individuals with an invalid fitness

invalid_ind = [ind for ind in offspring if not ind.fitness.valid]

fitnesses = map(toolbox.evaluate, invalid_ind)

for ind, fit in zip(invalid_ind, fitnesses):

ind.fitness.values = fit

print('Evaluated', len(invalid_ind), 'individuals')

Replace the population with the next generation individuals:

# The population is entirely replaced by the offspring

population[:] = offspring

Print the stats for the current generation to see how it’s progressing:

# Gather all the fitnesses in one list and print the stats

fits = [ind.fitness.values[0] for ind in population]

length = len(population)

mean = sum(fits) / length

sum2 = sum(x*x for x in fits)

std = abs(sum2 / length - mean**2)**0.5

print('Min =', min(fits), ', Max =', max(fits))

print('Average =', round(mean, 2), ', Standard deviation =',

round(std, 2))

print("\n==== End of evolution")

Print the final output:

best_ind = tools.selBest(population, 1)[0]

print('\nBest individual:\n', best_ind)

print('\nNumber of ones:', sum(best_ind))

The full code is given in the file `bit_counter.py`

. If you run the code, you will see iterations printed to your Terminal. At the start, you will see something like the following:

At the end, you will see something like the following that indicates the end of the evolution:

As seen in the preceding figure, the evolution process ends after 60 generations (zero-indexed). Once it’s done, the best individual is picked and printed on the output. It has 45 ones in the best individual, which is like a confirmation for us because the target sum is 45 in our evaluation function.

#### Visualizing the evolution

et’s see how we can visualize the evolution process. In `DEAP`

, they have used a method called Covariance Matrix Adaptation Evolution Strategy (CMA-ES) to visualize the evolution. It is an evolutionary algorithm that’s used to solve non-linear problems in the continuous domain. CMA-ES technique is robust, well studied, and is considered as state of the art in evolutionary algorithms. Let’s see how it works by delving into the code provided in their source code. The following code is a slight variation of the example shown in the `DEAP`

library.

Create a new Python file and import the following:

import numpy as np

import matplotlib.pyplot as plt

from deap import algorithms, base, benchmarks, \

cma, creator, tools

Define a function to create the toolbox. We will define a `FitnessMin`

function using negative weights:

# Function to create a toolbox

def create_toolbox(strategy):

creator.create("FitnessMin", base.Fitness, weights=(-1.0,))

creator.create("Individual", list, fitness=creator.FitnessMin)

Create the toolbox and register the evaluation function, as follows:

toolbox = base.Toolbox()

toolbox.register("evaluate", benchmarks.rastrigin)

# Seed the random number generator

np.random.seed(7)

Register the `generate`

and `update`

methods. This is related to the generate-update paradigm where we generate a population from a strategy and this strategy is updated based on the population:

toolbox.register("generate", strategy.generate, creator.Individual)

toolbox.register("update", strategy.update)

return toolbox

Define the `main`

function. Start by defining the number of individuals and the number of generations:

if __name__ == "__main__":

# Problem size

num_individuals = 10

num_generations = 125

We need to define a strategy before we start the process:

# Create a strategy using CMA-ES algorithm

strategy = cma.Strategy(centroid=[5.0]*num_individuals, sigma=5.0,

lambda_=20*num_individuals)

Create the toolbox based on the strategy:

# Create toolbox based on the above strategy

toolbox = create_toolbox(strategy)

Create a `HallOfFame`

object. The `HallOfFame`

object contains the best individual that ever existed in the population. This object is kept in a sorted format at all times. This way, the first element in this object is the individual that has the best fitness value ever seen during the evolution process:

# Create hall of fame object

hall_of_fame = tools.HallOfFame(1)

Register the stats using the `Statistics`

method:

# Register the relevant stats

stats = tools.Statistics(lambda x: x.fitness.values)

stats.register("avg", np.mean)

stats.register("std", np.std)

stats.register("min", np.min)

stats.register("max", np.max)

Define the `logbook`

to keep track of the evolution records. It is basically a chronological list of dictionaries:

logbook = tools.Logbook()

logbook.header = "gen", "evals", "std", "min", "avg", "max"

Define objects to compile all the data:

# Objects that will compile the data

sigma = np.ndarray((num_generations, 1))

axis_ratio = np.ndarray((num_generations, 1))

diagD = np.ndarray((num_generations, num_individuals))

fbest = np.ndarray((num_generations,1))

best = np.ndarray((num_generations, num_individuals))

std = np.ndarray((num_generations, num_individuals))

Iterate through the generations:

for gen in range(num_generations):

# Generate a new population

population = toolbox.generate()

Evaluate individuals using the fitness function:

# Evaluate the individuals

fitnesses = toolbox.map(toolbox.evaluate, population)

for ind, fit in zip(population, fitnesses):

ind.fitness.values = fit

Update the strategy based on the population:

# Update the strategy with the evaluated individuals

toolbox.update(population)

Update the hall of fame and statistics with the current generation of individuals:

# Update the hall of fame and the statistics with the

# currently evaluated population

hall_of_fame.update(population)

record = stats.compile(population)

logbook.record(evals=len(population), gen=gen, **record)

print(logbook.stream)

Save the data for plotting:

# Save more data along the evolution for plotting

sigma[gen] = strategy.sigma

axis_ratio[gen] = max(strategy.diagD)**2/min(strategy.diagD)**2

diagD[gen, :num_individuals] = strategy.diagD**2

fbest[gen] = hall_of_fame[0].fitness.values

best[gen, :num_individuals] = hall_of_fame[0]

std[gen, :num_individuals] = np.std(population, axis=0)

Define the `x`

axis and plot the stats:

# The x-axis will be the number of evaluations

x = list(range(0, strategy.lambda_ * num_generations, strategy.lambda_))

avg, max_, min_ = logbook.select("avg", "max", "min")

plt.figure()

plt.semilogy(x, avg, "--b")

plt.semilogy(x, max_, "--b")

plt.semilogy(x, min_, "-b")

plt.semilogy(x, fbest, "-c")

plt.semilogy(x, sigma, "-g")

plt.semilogy(x, axis_ratio, "-r")

plt.grid(True)

plt.title("blue: f-values, green: sigma, red: axis ratio")

Plot the progress:

plt.figure()

plt.plot(x, best)

plt.grid(True)

plt.title("Object Variables")

plt.figure()

plt.semilogy(x, diagD)

plt.grid(True)

plt.title("Scaling (All Main Axes)")

plt.figure()

plt.semilogy(x, std)

plt.grid(True)

plt.title("Standard Deviations in All Coordinates")

plt.show()

The full code is given in the file `visualization.py`

. If you run the code, you will see four screenshots. The first screenshot shows various parameters:

The second screenshot shows object variables:

The third screenshot shows scaling:

The fourth screenshot shows standard deviations:

You will see the progress printed on the Terminal. At the start, you will see something like the following:

As seen from the preceding figure, the values keep decreasing as we progress. This indicates that it’s converging.

#### Solving the symbol regression problem

Let’s see how to use genetic programming to solve the symbol regression problem. It is important to understand that genetic programming is not the same as genetic algorithms. Genetic programming is a type of evolutionary algorithm in which the solutions occur in the form of computer programs. Basically, the individuals in each generation would be computer programs and their fitness level corresponds to their ability to solve problems. These programs are modified, at each iteration, using a genetic algorithm. In essence, genetic programming is the application of a genetic algorithm.

Coming to the symbol regression problem, we have a polynomial expression that needs to be approximated here. It’s a classic regression problem where we try to estimate the underlying function. In this example, we will use the expression: *f(x) = 2x³ — 3x² + 4x — 1*

The code discussed here is a variant of the symbol regression problem given in the `DEAP`

library. Create a new Python file and import the following:

import operator

import math

import random

import numpy as np

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

Create a division operator that can handle divide-by-zero error gracefully:

# Define new functions

def division_operator(numerator, denominator):

if denominator == 0:

return 1

return numerator / denominator

Define the evaluation function that will be used for fitness calculation. We need to define a callable function to run computations on the input individual:

# Define the evaluation function

def eval_func(individual, points):

# Transform the tree expression in a callable function

func = toolbox.compile(expr=individual)

Compute the mean squared error (MSE) between the function defined earlier and the original expression:

# Evaluate the mean squared error

mse = ((func(x) - (2 * x**3 - 3 * x**2 - 4 * x + 1))**2 for x in points)

return math.fsum(mse) / len(points),

Define a function to create the toolbox. In order to create the toolbox here, we need to create a set of primitives. These primitives are basically operators that will be used during the evolution. They serve as building blocks for the individuals. We are going to use basic arithmetic functions as our primitives here:

# Function to create the toolbox

def create_toolbox():

pset = gp.PrimitiveSet("MAIN", 1)

pset.addPrimitive(operator.add, 2)

pset.addPrimitive(operator.sub, 2)

pset.addPrimitive(operator.mul, 2)

pset.addPrimitive(division_operator, 2)

pset.addPrimitive(operator.neg, 1)

pset.addPrimitive(math.cos, 1)

pset.addPrimitive(math.sin, 1)

We now need to declare an ephemeral constant. It is a special terminal type that does not have a fixed value. When a given program appends such an ephemeral constant to the tree, the function gets executed. The result is then inserted into the tree as a constant terminal. These constant terminals can take the values `-1`

, `0`

or `1`

:

pset.addEphemeralConstant("rand101", lambda: random.randint(-1,1))

The default name for the arguments is `ARGx`

. Let’s rename it `x`

. It’s not exactly necessary, but it’s a useful feature that comes in handy:

pset.renameArguments(ARG0='x')

We need to define two object types — fitness and an individual. Let’s do it using the `creator`

:

creator.create("FitnessMin", base.Fitness, weights=(-1.0,))

creator.create("Individual", gp.PrimitiveTree, fitness=creator.FitnessMin)

Create the `toolbox`

and `register`

the functions. The registration process is similar to previous sections:

toolbox = base.Toolbox()

toolbox.register("expr", gp.genHalfAndHalf, pset=pset, min_=1, max_=2)

toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.expr)

toolbox.register("population", tools.initRepeat, list, toolbox.individual)

toolbox.register("compile", gp.compile, pset=pset)

toolbox.register("evaluate", eval_func, points=[x/10. for x in range(-10,10)])

toolbox.register("select", tools.selTournament, tournsize=3)

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)

toolbox.decorate("mate", gp.staticLimit(key=operator.attrgetter("height"), max_value=17))

toolbox.decorate("mutate", gp.staticLimit(key=operator.attrgetter("height"), max_value=17))

return toolbox

Define the `main`

function and start by seeding the random number generator:

if __name__ == "__main__":

random.seed(7)

Create the `toolbox`

object:

toolbox = create_toolbox()

Define the initial population using the method available in the `toolbox`

object. We will use `450`

individuals. The user defines this number, so you should feel free to experiment with it. Also define the `hall_of_fame`

object:

population = toolbox.population(n=450)

hall_of_fame = tools.HallOfFame(1)

Statistics are useful when we build genetic algorithms. Define the stats objects:

stats_fit = tools.Statistics(lambda x: x.fitness.values)

stats_size = tools.Statistics(len)

Register the stats using the objects defined previously:

mstats = tools.MultiStatistics(fitness=stats_fit, size=stats_size)

mstats.register("avg", np.mean)

mstats.register("std", np.std)

mstats.register("min", np.min)

mstats.register("max", np.max)

Define the crossover probability, mutation probability, and the number of generations:

probab_crossover = 0.4

probab_mutate = 0.2

num_generations = 60

Run the evolutionary algorithm using the above parameters:

population, log = algorithms.eaSimple(population, toolbox,

probab_crossover, probab_mutate, num_generations,

stats=mstats, halloffame=hall_of_fame, verbose=True)

The full code is given in the file `symbol_regression.py`

. If you run the code, you will see the following on your Terminal at the start of the evolution:

At the end, you will see the following:

#### Building an intelligent robot controller

Let’s see how to build a robot controller using a genetic algorithm. We are given a map with the targets sprinkled all over it. The map looks like this:

There are 124 targets in the preceding map. The goal of the robot controller is to automatically traverse the map and consume all those targets. This program is a variant of the artificial ant program given in the `deap`

library.

Create a new Python file and import the following:

import copy

import random

from functools import partial

import numpy as np

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

Create the class to control the robot:

class RobotController(object):

def __init__(self, max_moves):

self.max_moves = max_moves

self.moves = 0

self.consumed = 0

self.routine = None

Define the directions and movements:

self.direction = ["north", "east", "south", "west"]

self.direction_row = [1, 0, -1, 0]

self.direction_col = [0, 1, 0, -1]

Define the reset functionality:

def _reset(self):

self.row = self.row_start

self.col = self.col_start

self.direction = 1

self.moves = 0

self.consumed = 0

self.matrix_exc = copy.deepcopy(self.matrix)

Define the conditional operator:

def _conditional(self, condition, out1, out2):

out1() if condition() else out2()

Define the left turning operator:

def turn_left(self):

if self.moves < self.max_moves:

self.moves += 1

self.direction = (self.direction - 1) % 4

Define the right turning operator:

def turn_right(self):

if self.moves < self.max_moves:

self.moves += 1

self.direction = (self.direction + 1) % 4

Define the method to control how the robot moves forward:

def move_forward(self):

if self.moves < self.max_moves:

self.moves += 1

self.row = (self.row + self.direction_row[self.direction]) %

self.matrix_row

self.col = (self.col + self.direction_col[self.direction]) %

self.matrix_col

if self.matrix_exc[self.row][self.col] == "target":

self.consumed += 1

self.matrix_exc[self.row][self.col] = "passed"

Define a method to sense the target. If you see the target ahead, then update the matrix accordingly:

def sense_target(self):

ahead_row = (self.row + self.direction_row[self.direction]) % self.matrix_row

ahead_col = (self.col + self.direction_col[self.direction]) % self.matrix_col

return self.matrix_exc[ahead_row][ahead_col] == "target"

If you see the target ahead, then create the relevant function and return it:

def if_target_ahead(self, out1, out2):

return partial(self._conditional, self.sense_target, out1, out2)

Define the method to run it:

def run(self,routine):

self._reset()

while self.moves < self.max_moves:

routine()

Define a function to traverse the input map. The symbol `#`

indicates all the targets on the map and the symbol `S`

indicates the starting point. The symbol `.`

denotes empty cells:

def traverse_map(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("target")

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.direction = 1

self.matrix_row = len(self.matrix)

self.matrix_col = len(self.matrix[0])

self.matrix_exc = copy.deepcopy(self.matrix)

Define a class to generate functions depending on the number of input arguments:

class Prog(object):

def _progn(self, *args):

for arg in args:

arg()

def prog2(self, out1, out2):

return partial(self._progn, out1, out2)

def prog3(self, out1, out2, out3):

return partial(self._progn, out1, out2, out3)

Define an evaluation function for each individual:

def eval_func(individual):

global robot, pset

# Transform the tree expression to functional Python code

routine = gp.compile(individual, pset)

Run the current program:

# Run the generated routine

robot.run(routine)

return robot.consumed,

Define a function to create the toolbox and add primitives:

def create_toolbox():

global robot, pset

pset = gp.PrimitiveSet("MAIN", 0)

pset.addPrimitive(robot.if_target_ahead, 2)

pset.addPrimitive(Prog().prog2, 2)

pset.addPrimitive(Prog().prog3, 3)

pset.addTerminal(robot.move_forward)

pset.addTerminal(robot.turn_left)

pset.addTerminal(robot.turn_right)

Create the object types using the fitness function:

creator.create("FitnessMax", base.Fitness, weights=(1.0,))

creator.create("Individual", gp.PrimitiveTree, fitness=creator.FitnessMax)

Create the `toolbox`

and `register`

all the operators:

toolbox = base.Toolbox()

# Attribute generator

toolbox.register("expr_init", gp.genFull, pset=pset, min_=1, max_=2)

# Structure initializers

toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.expr_init)

toolbox.register("population", tools.initRepeat, list, toolbox.individual)

toolbox.register("evaluate", eval_func)

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)

return toolbox

Define the `main`

function and start by seeding the random number generator:

if __name__ == "__main__":

global robot

# Seed the random number generator

random.seed(7)

Create the robot controller object using the initialization parameter:

# Define the maximum number of moves

max_moves = 750

# Create the robot object

robot = RobotController(max_moves)

Create the `toolbox`

using the function we defined earlier:

# Create the toolbox

toolbox = create_toolbox()

Read the map data from the input file:

# Read the map data

with open('target_map.txt', 'r') as f:

robot.traverse_map(f)

Define the population with `400`

individuals and define the `hall_of_fame`

object:

# Define population and hall of fame variables

population = toolbox.population(n=400)

hall_of_fame = tools.HallOfFame(1)

Register the stats:

# Register the stats

stats = tools.Statistics(lambda x: x.fitness.values)

stats.register("avg", np.mean)

stats.register("std", np.std)

stats.register("min", np.min)

stats.register("max", np.max)

Define the crossover probability, mutation probability, and the number of generations:

# Define parameters

probab_crossover = 0.4

probab_mutate = 0.3

num_generations = 50

Run the evolutionary algorithm using the parameters defined earlier:

# Run the algorithm to solve the problem

algorithms.eaSimple(population, toolbox, probab_crossover,

probab_mutate, num_generations, stats,

halloffame=hall_of_fame)

The full code is given in the file `robot.py`

. If you run the code, you will get the following on your Terminal:

Towards the end, you will see the following:

*Source: Artificial Intelligence on Medium*