Genetic Algorithms

Genetic AlgorithmsA genetic algorithm is a type of evolutionary algorithm.

So, in order to understand genetic algorithms, we need to discuss evolutionary algorithms.

DammnnBlockedUnblockFollowFollowingMay 8An 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 algorithmsIn 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 parametersNow 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://deap.

readthedocs.

io/en/master.

Let's go ahead and install it by running the following command on your Terminal:$ pip3 install deapNow that the package is installed, let’s quickly test it.

Go into the Python shell by typing the following on your Terminal:$ python3Once you are inside, type the following:>>> import deapIf 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, toolsLet’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 creatorobject for the fitness function and to keep track of the individuals.

The Fitnessclass 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 toolboxThis 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 = 75Create 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.

2Define 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 = 60Evaluate all the individuals in the population using the fitness functions:print('.Starting the evolution process') # Evaluate the entire population fitnesses = list(map(toolbox.

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

fitness.

values = fitStart iterating through the generations:print('.Evaluated', len(population), 'individuals') # Iterate through generations for g in range(num_generations): print(".===== 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.

valuesApply 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.

valuesEvaluate 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[:] = offspringPrint 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(".==== End of evolution")Print the final output:best_ind = tools.

selBest(population, 1)[0] print('.Best individual:.', best_ind) print('.Number 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 evolutionet’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, toolsDefine 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 toolboxDefine 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 = 125We 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 = fitUpdate 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 problemLet’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 — 1The 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, gpCreate 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 / denominatorDefine 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 toolboxDefine 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 = 60Run 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 controllerLet’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, gpCreate 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 = NoneDefine 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) % 4Define the right turning operator:def turn_right(self): if self.

moves < self.

max_moves: self.

moves += 1 self.

direction = (self.

direction + 1) % 4Define 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 toolboxDefine 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 = 50Run 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:.

. More details

Leave a Reply