AI with Python – Genetic Algorithms

AI with Python – Genetic Algorithms

This chapter discusses Genetic Algorithms of AI in detail.

What are Genetic Algorithms?

Genetic Algorithms (GAs) are search based algorithms based on the concepts of natural selection and genetics. GAs are a subset of a much larger branch of computation known as Evolutionary Computation.
GAs were developed by John Holland and his students and colleagues at the University of Michigan, most notably David E. Goldberg. It has since been tried on various optimization problems with a high degree of success.
In GAs, we have a pool of possible solutions to the given problem. These solutions then undergo recombination and mutation (like in natural genetics), produces new children, and the process is repeated for various generations. Each individual (or candidate solution) is assigned a fitness value (based on its objective function value) and the fitter individuals are given a higher chance to mate and yield fitter individuals. This is in line with the Darwinian Theory of Survival of the Fittest.
Thus, it keeps evolving better individuals or solutions over generations, till it reaches a stopping criterion.
Genetic Algorithms are sufficiently randomized in nature, but they perform much better than random local search (where we just try random solutions, keeping track of the best so far), as they exploit historical information as well.

How to Use GA for Optimization Problems?

Optimization is an action of making design, situation, resource and system, as effective as possible. The following block diagram shows the optimization process −

Stages of GA mechanism for optimization process

The following is a sequence of steps of GA mechanism when used for optimization of problems.

  • Step 1 − Generate the initial population randomly.
  • Step 2 − Select the initial solution with best fitness values.
  • Step 3 − Recombine the selected solutions using mutation and crossover operators.
  • Step 4 − Insert an offspring into the population.
  • Step 5 − Now, if the stop condition is met, return the solution with their best fitness value. Else go to step 2.
    Step 1 − Generate the initial population randomly.
    Step 2 − Select the initial solution with best fitness values.
    Step 3 − Recombine the selected solutions using mutation and crossover operators.
    Step 4 − Insert an offspring into the population.
    Step 5 − Now, if the stop condition is met, return the solution with their best fitness value. Else go to step 2.

    Installing Necessary Packages

    For solving the problem by using Genetic Algorithms in Python, we are going to use a powerful package for GA called DEAP. It is a library of novel evolutionary computation framework for rapid prototyping and testing of ideas. We can install this package with the help of the following command on command prompt −

    pip install deap

    If you are using anaconda environment, then following command can be used to install deap −

    conda install -c conda-forge deap

    Implementing Solutions using Genetic Algorithms

    This section explains you the implementation of solutions using Genetic Algorithms.

    Generating bit patterns

    The following example shows you how to generate a bit string that would contain 15 ones, based on the One Max problem.
    Import the necessary packages as shown −

    import random
    from deap import base, creator, tools

    Define the evaluation function. It is the first step to create a genetic algorithm.

    def Evalfunc(i):
    targetSum = 15
    return len(i) - abs(sum(i) - targetSum),

    Now, create the toolbox with the right parameters −

    def create_toolbox(nbits):
    creator.create("FitnessMax", base.Fitness, weights=(1.0,))
    creator.create("Individual", list, fitness=creator.FitnessMax)

    Initialize the toolbox

    toolbox = base.Toolbox()
    toolbox.register("attr_bool", random.randint, 0, 1)
    toolbox.register("individual", tools.initRepeat, creator.Individual,
    toolbox.attr_bool, nbits)
    toolbox.register("population", tools.initRepeat, list, toolbox.individual)

    Register the evaluation operator −

    toolbox.register("evaluate", Evalfunc)

    Now, register the crossover operator −

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

    Register a mutation operator −

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

    Define the operator for breeding −

    toolbox.register("select", tools.selTournament, tournsize = 3)
    return toolbox
    if __name__ == "__main__":
    no_bits = 45
    toolbox = create_toolbox(no_bits)
    population = toolbox.population(n = 500)
    probab_crossing, probab_mutating = 0.5, 0.2
    num_generations = 10
    print('nEvolution process starts')

    Evaluate the entire population −

    Fit = list(map(toolbox.evaluate, population))
    for ind, fit in zip(population, Fit):
    ind.Fit.values = fit
    print('nEvaluated', len(population), 'individuals')

    Create and iterate through generations −

    for g in range(num_generations):
    print("n- Generation", g)

    Selecting the next generation individuals −

    Offspring =, len(population))

    Now, clone the selected individuals −

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

    Apply crossover and mutation on the offspring −

    for c1, c2 in zip(Offspring[::2], Offspring[1::2]):
    if random.random() < probab_crossing:
    toolbox.mate(c1, c2)

    Delete the fitness value of child


    Now, apply mutation −

    for m in Offspring:
    if random.random() < probab_m:

    Evaluate the individuals with an invalid fitness −

    invalid_indviduals = [i for iin Offspring if not i.Fitness.valid]
    Fitnesses = map(toolbox.evaluate, invalid_indviduals)
    for i, fit in zip(invalid_indviduals, Fitnesses):
    ind.Fitness.values = fit
    print('Evaluated', len(invalid_indviduals), 'individuals')

    Now, replace population with next generation individual −

    population[:] = Offspring

    Print the statistics for the current generations −

    fits = [i.Fitness.values[0] for i in population]
    Length = len(population)
    Mean = sum(fits) / length
    Sum_2 = sum(x*x for x in fits)
    Std = abs(Sum_2 / Length - Mean**2)**0.5
    print('Min =', min(fits), ', Max =', max(fits))
    print('Average =', round(mean, 2), ', Standard deviation =',
    round(std, 2))
    print("n- Evolution ends")

    Print the final output −

    bestInd = tools.selBest(population, 1)[0]
    print('nBest individual:n', bestInd)
    print('nNumber of ones:', sum(bestInd))
    Following would be the output:
    Evolution process starts
    Evaluated 500 individuals
  • Generation 0
    Evaluated 295 individuals
    Min = 32.0 , Max = 45.0
    Average = 40.29 , Standard deviation = 2.61
  • Generation 1
    Evaluated 292 individuals
    Min = 34.0 , Max = 45.0
    Average = 42.35 , Standard deviation = 1.91
  • Generation 2
    Evaluated 277 individuals
    Min = 37.0 , Max = 45.0
    Average = 43.39 , Standard deviation = 1.46
    … … … …
  • Generation 9
    Evaluated 299 individuals
    Min = 40.0 , Max = 45.0
    Average = 44.12 , Standard deviation = 1.11
  • Evolution ends
    Best individual:
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1,
    1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0,
    1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1]
    Number of ones: 15

    ### Symbol Regression Problem
    It is one of the best known problems in genetic programming. All symbolic regression problems use an arbitrary data distribution, and try to fit the most accurate data with a symbolic formula. Usually, a measure like the RMSE (Root Mean Square Error) is used to measure an individual’s fitness. It is a classic regressor problem and here we are using the equation 5x3-6x2+8x=1. We need to follow all the steps as followed in the above example, but the main part would be to create the primitive sets because they are the building blocks for the individuals so the evaluation can start. Here we will be using the classic set of primitives.
    The following Python code explains this in detail −

    import operator
    import math
    import random
    import numpy as np
    from deap import algorithms, base, creator, tools, gp
    def division_op(n, d):
    if d == 0:
    return 1
    return n / d
    def eval_function(indi, points):
    func = toolbox.compile(expr=indi)
    return math.fsum(mse) / len(points),
    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(divisionop, 2)
    pset.addPrimitive(operator.neg, 1)
    pset.addPrimitive(math.cos, 1)
    pset.addPrimitive(math.sin, 1)
    pset.addEphemeralConstant("rand101", lambda: random.randint(-1,1))
    pset.renameArguments(ARG0 = 'x')
    creator.create("FitnessMin", base.Fitness, weights = (-1.0,))
    toolbox = base.Toolbox()
    toolbox.register("expr", gp.genHalfAndHalf, pset=pset, min
    =1, max_=2)
    toolbox.register("population",tools.initRepeat,list, toolbox.individual)
    toolbox.register("compile", gp.compile, pset = pset)
    toolbox.register("evaluate", eval_function, points = [x/10. for x in range(-10,10)])
    toolbox.register("select", tools.selTournament, tournsize = 3)
    toolbox.register("mate", gp.cxOnePoint)
    toolbox.register("exprmut", 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
    if name == "main":
    toolbox = create_toolbox()
    population = toolbox.population(n = 450)
    hall_of_fame = tools.HallOfFame(1)
    stats_fit = tools.Statistics(lambda x:
    stats_size = tools.Statistics(len)
    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)
    probab_crossover = 0.4
    probab_mutate = 0.2
    number_gen = 10
    population, log = algorithms.eaSimple(population, toolbox,
    probab_crossover, probab_mutate, number_gen,
    stats = mstats, halloffame = hall_of_fame, verbose = True)

    Note that all the basic steps are same as used while generating bit patterns. This program will give us the output as min, max, std (standard deviation) after 10 number of generations.
AI with Python – Reinforcement Learning (Prev Lesson)
(Next Lesson) AI with Python – Computer Vision