Mastering Optimization with Python/

...

/

Applying Genetic Algorithms

Applying Genetic Algorithms

Learn to solve a problem using genetic algorithms.

We'll cover the following...

It’s time to solve a problem with a genetic algorithm. Let’s start with something simple. At the end of this chapter, we’ll face more complex problems. But for now, we’re going to minimize the function f(x)=x2f(x) = x^2.

Let’s remember the code template for genetic algorithms:

Press + to interact
import numpy as np
# mutation operation
def mutation(s, Pm):
  pass
# crossover operation
def crossover(p1, p2, Pc)
  pass
# score function
def score(s):
  pass
# generates the initial population with length N
def generate_initial_population(N):
  pass
# determines the best solution
def best_solution(P, score_func)
  scores = list(map(score_func, P))
  index = np.argmax(scores)
  return P[index]
def select_parent(P, score_func):
  scores = list(map(score_func, P))
  score_sum = sum(scores)
  probs = list(map(lambda s: s/score_sum, scores))
  return np.random.choice(P, p=probs)
def genetic_algorithm(target_f, Pm, Pc, N, max_iter):
  P = generate_initial_population(N)
  # placeholders for the best result
  best_solution, best_score = 0, -1e9
  # stop criterion is max_iter reached
  for _ in range(max_iter):
    
    # get best solution in this generation
    best_candidate = best_solution(P, score)
    # keep the best solution found
    if score(best_candidate) > best_score:
      best_solution = best_candidate
      best_score = score(best_candidate)
    newP = []
    # take parents in ordered pairs (first and second, second and third, etc)
    for _ in range(N):
      p1 = select_parent(P, score)
      p2 = select_parent(P, score)
      # produce new child with prob Pc
      c = crossover(p1, p2, Pc)
      # mutate c with probability Pm
      c = mutation(c, Pm)
      newP.append(c)
    
    # make a new generation
    P = newP
  
  # return the best solution and its score
  return best_solution, best_score

We need to implement the following methods:

  • mutation: Receives one solution and a probability and updates that solution with that probability.

  • crossover: Receives two solutions and a probability and creates a new solution with that probability.

  • score: Tells us how good a solution is. The bigger the score, the better the solution. The score should be always a positive number.

  • generate_initial_population: Generates an initial population with the specified size.

So, the very first thing we need to do is to define what a solution looks like. This time it is pretty simple: a solution is just a number. We want to find the number xx that minimizes f(x)f(x). Defining what a solution looks like is not always that ...