Genetic Algorithms

Learn about genetic algorithms by exploring their key concepts and functionality, and create art through evolution.

We'll cover the following

Overview

Genetic algorithms are inspired by one of nature's most fascinating processes: evolution. Imagine a child learning to ride a bicycle for the first time. In the beginning, the child tries various methods, each representing a different approach to balancing, pedaling, and steering. Each attempt provides valuable feedback—sometimes, they stay upright, and sometimes they fall. As they practice, they learn which techniques work best and which don’t, gradually refining their skills. They combine successful strategies from different attempts, occasionally experimenting with new adjustments until they master riding smoothly and confidently. This learning process mirrors the principles of a genetic algorithm. Let's dive deeper into the details of this algorithm.

Press + to interact

The algorithm

A genetic algorithm (GA) is a search heuristic to find approximate solutions to optimization and search problems by mimicking the process of natural evolution. Genetic algorithms are particularly useful when dealing with problems where the search space is large, complex, or poorly understood.

Key concepts

  1. Population: A collection of individuals, each representing a possible solution to the problem. The population evolves over time through iterations (known as generations).

  2. Chromosome: A representation of an individual solution, typically encoded as a string of binary digits (0s and 1s), although other encodings (e.g., real numbers, characters) are also used depending on the problem.

  3. Gene: A segment of a chromosome that represents a particular trait of the solution. In a binary encoding, each gene is a bit (0 or 1).

Press + to interact

  1. Fitness function: A function that evaluates and assigns a fitness score to each individual in the population based on how well it solves the problem at hand. The fitness score determines the probability of an individual being selected for reproduction.

  2. Selection: The process of choosing individuals from the current population to create offspring for the next generation. The selection is typically based on fitness scores, with fitter individuals having a higher probability of being selected.

  3. Crossover (recombination): A genetic operator that combines two parent chromosomes to produce offspring. Crossover is like mixing traits from two parents to create a new, unique combination, helping to make each generation more diverse.

Press + to interact

  1. Mutation: A genetic operator that introduces random changes to individual genes in a chromosome, mimicking the process of mutation in biological evolution. Mutation helps maintain genetic diversity and prevents premature convergence to a suboptimal solution.

  2. Termination condition: A condition that determines when the algorithm should stop. Common termination conditions include reaching a maximum number of generations, achieving a satisfactory fitness level, or detecting stagnation in the population's improvement.

Working of a genetic algorithm

The operation of a genetic algorithm involves several iterative steps, typically executed as follows.

Press + to interact

  1. Initialization: Start with a group of random potential solutions (called a population). These could be anything, like random shapes in an art project or numbers in a math problem.

  2. Evaluation: Check how good each solution is by using a "fitness function," which tells us how close it is to the desired result.

  3. Selection: Pick the best solutions to be parents for the next round. The better the solution, the higher its chance to be picked. Some common ways to do this are:

    1. Roulette wheel: Like spinning a wheel, better solutions have a bigger slice of the wheel.

    2. Tournament: Randomly choose a few solutions and pick the best among them.

    3. Rank: List all solutions from best to worst and pick them based on their position.

  4. Crossover: Mix traits from two parents to create new solutions (offspring). Some ways to do this include:

    1. Single-point: Pick one point on both parents and swap everything afterward.

    2. Two-point: Pick two points and swap the bits in between.

    3. Uniform: For each trait, randomly pick from one of the parents.

  5. Mutation: Randomly change a few parts of the new solutions to introduce variety. This step ensures we don’t get stuck with similar solutions.

  6. Replacement: Form a new group of solutions by replacing some or all of the old ones with new ones. This could mean replacing the entire group or just a few.

  7. Termination check: See if we’ve met our goal, like reaching a set number of generations or achieving a certain fitness level. If not, go back to step 2 and repeat.

Example: Maximizing the sum of bits

Let’s explore how a genetic algorithm (GA) works through a simplified example. We aim to maximize the sum of bits in a binary string of length 5. Here’s a step-by-step breakdown of the GA components and process.

Problem setup

  • Objective: Maximize the sum of bits in a binary string of length 5.

  • Population size: 3 individuals, each represented as a binary string (e.g., "10101").

  • Fitness function: The fitness is the total number of 1s in the string (e.g., "10101" has a fitness of 3).

Here is step-by-step the generation of the first population:

Press + to interact
Generating population 1
Generating population 1

The initial population consists of three individuals: "10101" with a fitness of 3, "01100" with a fitness of 2, and "11011" with a fitness of 4. The algorithm starts by sorting these individuals in descending order based on their fitness values, resulting in the sorted order: "11011", "10101", and "01100". Applying elitismElitism involves copying the top-performing individuals (elite individuals) directly to the next generation without any changes. This strategy prevents the loss of the best solutions due to the randomness of selection, crossover, or mutation., the top individual "11011" (fitness 4) is directly preserved for the next generation to ensure that the best solution found so far is retained. Next, the remaining individuals, "10101" and "01100", are selected as parents for crossover. A single-point crossover results in two offspring: "10100" and "01101". After applying a mutation with a small probability, the offspring become "10100" and "00101". The new population for Generation 2 is formed by combining the elite individual "11011" with the newly generated offspring, "10100" and "00101", setting the stage for further evolution in the subsequent generation.

Now, you know how it works. Let's dive deeper into one of its applications.

Example: Crafting art through evolution!

What if a computer could learn to paint, starting with just random shapes and colors, and gradually improving, generation by generation, until it produces something stunning and unique? This is the magic behind generating evolving art with a genetic algorithm—a creative journey where digital art evolves over time. Here is a preview of what we are about to create:

Press + to interact
Transforming random noise into a clear image through iterative adaptation, evolving over generations to closely resemble the target image.
Transforming random noise into a clear image through iterative adaptation, evolving over generations to closely resemble the target image.

Note: This example demonstrates a basic implementation of a genetic algorithm for generating art. For more intricate and complex art, the algorithm may require many more iterations to achieve the desired results. Feel free to experiment by changing the target image and adjusting the parameters such as mutation rate, population size, and number of generations. Playing around with these settings can provide deeper insights into how genetic algorithms can be applied to art generation and allow you to explore a wider range of artistic possibilities.

Steps to generate evolving art with genetic algorithm

Initialization: We create a basic image with a white square in the center as our target art. We also generate a random population of images.

# Initialization
def initialize_population(size, image_size):
    return [np.random.rand(*image_size) for _ in range(size)]
def create_target_image(image_size):
    img = np.ones(image_size)
    center = (image_size[0] // 2, image_size[1] // 2)
    side = min(image_size) // 4
    img[center[0] - side:center[0] + side, center[1] - side:center[1] + side] = 0
    return img
image_size = (100, 100)  # Size of the image
population_size = 200   # Number of images in the population
generations = 100        # Number of iterations
mutation_rate = 0.01     # Rate of mutation
num_samples = 5         # Number of sample images
downscale_factor = 2     # Factor to downscale images for faster plotting
target_image = create_target_image(image_size)
population = initialize_population(population_size, image_size)
Initialization step

  • Lines 2–3: Define the initialize_population method, which generates a list of random images. Each image has dimensions specified by image_size and there are size such images in the population.

  • Lines 5–10: Define the create_target_image method, which generates an image with a black square in the center. The image is initially filled with white pixels, and a central black square of a calculated size is added.

  • Lines 12–17: Set various parameters for the genetic algorithm, including the size of the images, the number of images in the population, the number of iterations, mutation rate, the number of sample images, and a downscale factor for image plotting.

  • Lines 19–20: Generate the target image using create_target_image and initialize the population of images using initialize_population, both based on the previously defined parameters.

Fitness function: Measures how similar an image is to the target. We use a simple pixel-wise difference.

# Fitness Function
def fitness(img, target):
    return np.sum(np.abs(img - target))
Defining the fitness function

  • Lines 2–3: Define the fitness function, which calculates the fitness score of an image compared to a target image. The function computes the sum of absolute differences between the pixels of the img and target, providing a measure of how close the img is to the target (lower values indicate higher fitness).

Selection: Selects the top half of the population based on fitness scores.

# Selection
def select_population(population, scores):
    sorted_indices = np.argsort(scores)
    top_half_indices = sorted_indices[:len(scores) // 2]
    return [population[i] for i in top_half_indices]
Selection phase

  • Lines 2–5: Define the select_population function, which selects the top half of the population based on fitness scores. It first sorts the indices of the population according to their scores, then selects the indices of the top half (with the lowest scores, indicating better fitness). Finally, it returns the corresponding individuals from the population, representing the more fit members.

Crossover: Combines parts of two images to create a new one.

# Crossover
def crossover(parent1, parent2):
    crossover_point = random.randint(0, parent1.size - 1)
    child = np.copy(parent1)
    child.flat[crossover_point:] = parent2.flat[crossover_point:]
    return child
Crossover phase

  • Lines 2–6: Define the crossover function, which combines two parent images to create a child image. It first selects a random crossover point within the range of the parent images. It then copies the first parent image, and replaces the portion of the child image from the crossover point onward with the corresponding portion from the second parent. The result is a new image that combines the features of both parents.

Mutation: Randomly changes some pixels in an image.

# Mutation
def mutate(img, mutation_rate):
    mutation_mask = np.random.rand(*img.shape) < mutation_rate
    img[mutation_mask] = np.random.rand(np.sum(mutation_mask))
    return img
Mutation phase

  • Lines 2–5: Define the mutate function, which introduces random changes to an image based on a mutation rate. It first creates a boolean mask where each pixel is marked for mutation with a probability equal to mutation_rate. Pixels that are marked for mutation are then assigned new random values. The function returns the modified image with mutations applied.

Iteration: Repeats the process for a set number of generations, showing the progression of the generated art.

# Iteration
def downscale_image(img, factor):
    img = Image.fromarray(img)
    new_size = (img.size[0] // factor, img.size[1] // factor)
    img = img.resize(new_size, Image.ANTIALIAS)
    return np.array(img)
sample_images = []
intervals = [i * (generations - 1) // (num_samples - 1) for i in range(num_samples)]
for generation in range(generations):
    scores = [fitness(img, target_image) for img in population]
    selected = select_population(population, scores)
    
    new_population = []
    while len(new_population) < population_size:
        parent1, parent2 = random.sample(selected, 2)
        child = crossover(parent1, parent2)
        child = mutate(child, mutation_rate)
        new_population.append(child)
    
    population = new_population
    
    if generation in intervals:
        sample_images.append(np.mean(population, axis=0))
# Plotting the Results
fig, axes = plt.subplots(1, len(sample_images) + 1, figsize=(15, 5))
# Plot the target image
axes[0].imshow(downscale_image(target_image, downscale_factor), cmap='gray')
axes[0].set_title('Target Image')
axes[0].axis('off')
# Plot sample images
for i, img in enumerate(sample_images):
    axes[i + 1].imshow(downscale_image(img, downscale_factor), cmap='gray')
    axes[i + 1].set_title(f'Gen {intervals[i]}')
    axes[i + 1].axis('off')
plt.show()
Iteration step

  • Lines 2–6: Define the downscale_image function, which reduces the size of an image by a specified factor. It first converts the image to a PIL object, resizes it using anti-aliasing to maintain quality, and then converts it back to a NumPy array.

  • Lines 8–9: Initialize an empty list sample_images to store images at specific generations. Calculate the intervals at which to sample images from the population, evenly spaced over the total number of generations.

  • Lines 11–25: Run the main iteration loop for the genetic algorithm

    • Lines 12–13: Calculate the fitness scores for each image in the population and select the top performers.

    • Lines 15–22: Generate a new population through crossover and mutation of selected images until the population size is met.

    • Line 25: At specified intervals, compute the mean image of the current population and add it to sample_images.

  • Line 28–41: Displays the sampled images over the generations.

Check out this code snippet to execute the full code.

Tweak the number of generations, mutation rate, and population size to unlock the secrets of genetic algorithms!

Press + to interact
import numpy as np
import matplotlib.pyplot as plt
from PIL import Image
import random
# Initialization
def initialize_population(size, image_size):
    return [np.random.rand(*image_size) for _ in range(size)]
def create_target_image(image_size):
    img = np.ones(image_size)
    center = (image_size[0] // 2, image_size[1] // 2)
    side = min(image_size) // 4
    img[center[0] - side:center[0] + side, center[1] - side:center[1] + side] = 0
    return img
image_size = (100, 100)  # Size of the image
population_size = 200   # Number of images in the population
generations = 500   # Number of iterations
mutation_rate = 0.1     # Rate of mutation
num_samples = 5         # Number of sample images
downscale_factor = 2     # Factor to downscale images for faster plotting
target_image = create_target_image(image_size)
population = initialize_population(population_size, image_size)
# Fitness Function
def fitness(img, target):
    return np.sum(np.abs(img - target))
# Selection
def select_population(population, scores):
    sorted_indices = np.argsort(scores)
    top_half_indices = sorted_indices[:len(scores) // 2]
    return [population[i] for i in top_half_indices]
# Crossover
def crossover(parent1, parent2):
    crossover_point = random.randint(0, parent1.size - 1)
    child = np.copy(parent1)
    child.flat[crossover_point:] = parent2.flat[crossover_point:]
    return child
# Mutation
def mutate(img, mutation_rate):
    mutation_mask = np.random.rand(*img.shape) < mutation_rate
    img[mutation_mask] = np.random.rand(np.sum(mutation_mask))
    return img
# Iteration
def downscale_image(img, factor):
    img = Image.fromarray(img)
    new_size = (img.size[0] // factor, img.size[1] // factor)
    img = img.resize(new_size, Image.ANTIALIAS)
    return np.array(img)
sample_images = []
intervals = [i * (generations - 1) // (num_samples - 1) for i in range(num_samples)]
for generation in range(generations):
    print(generation+1,'/',generation)
    scores = [fitness(img, target_image) for img in population]
    selected = select_population(population, scores)
    
    new_population = []
    while len(new_population) < population_size:
        parent1, parent2 = random.sample(selected, 2)
        child = crossover(parent1, parent2)
        child = mutate(child, mutation_rate)
        new_population.append(child)
    
    population = new_population
    
    if generation in intervals:
        sample_images.append(np.mean(population, axis=0))
# Plotting the Results
fig, axes = plt.subplots(1, len(sample_images) + 1, figsize=(15, 5))
# Plot the target image
axes[0].imshow(downscale_image(target_image, downscale_factor), cmap='gray')
axes[0].set_title('Target Image')
axes[0].axis('off')
# Plot sample images
for i, img in enumerate(sample_images):
    axes[i + 1].imshow(downscale_image(img, downscale_factor), cmap='gray')
    axes[i + 1].set_title(f'Gen {intervals[i]}')
    axes[i + 1].axis('off')
plt.savefig("output/final_generation.png")
plt.show()