Search⌘ K
AI Features
Home
Courses
Mastering Optimization with Python

Applying Genetic Algorithms

Explore how to apply genetic algorithms to minimize functions using Python. Learn to define solutions, implement mutation, crossover, and scoring methods, and generate populations to find optimal outcomes in iterative processes.

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:

Python 3.10.4
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 ...