DEV Community: Kavin Bharathi

Genetic Algorithm in action!

Kavin Bharathi — Sat, 22 Oct 2022 13:34:37 +0000

What is the Genetic Algorithm?, to a human!

The Genetic Algorithm is a clever idea used in many fields to solve problems that otherwise take too much computing power or time. It mimics the process of evolution in nature, in a very bare-bones manner. The usage of various processes to evaluate genes, fitness scores, the target really makes it useful in implementing it for various different needs.

What is the Genetic Algorithm?, to a computer!

Now, the computer doesn't understand English or any other communication language for that matter. So how do you implement it in code. I'll be using Python and a library called Pygame, to visualize the Genetic Algorithm.

Setting up the environment

Tools required:

python=3.8 or above
pygame=2.0.2 or above
A good text editor(I'll be using Microsoft Visual Studio Code)
A cup of coffee(or more!)

Building the Pygame display

The pygame display is easy to build. All you have to do is initialize a screen with,

display = pygame.display.set_mode((width, height))

where width and height are the dimensions of your display. Then in a function, initialize a while loop and update the pygame display. The code for the above mentioned is,

import pygame

width = 720
height = 480
display = pygame.display.set_mode((width, height))
pygame.display.set_caption("Genetic Algorithm")

def main():
    run = True
    while run:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                run = False


        pygame.display.flip()

if __name__ == "__main__":
    main()

The structure of the algorithm

The genetic algorithm uses a clever way to mimic the process of evolution in nature. Generally, the are n number of individuals I call genomes. Each genome has a set of "genes" and their behavior is dictated by their genes.

These genes are randomly initialized and are then evaluated on a specific task. For our example, we will be using vertical motion of each individual. Then the best performing genes are selected and a "breeding" process is done in hopes or increasing the pattern of the best performing genes. There is also a process of "mutation" where a small change is done to the genes of the genome to introduce variance and hopefully some helpful genes to boost up the evolution process.

Creating the Genome class:

What I'll be referring to as "Genomes" are the individuals who are going to evolve using the magic of natural selection and mutation to become the best at a specific task(or at least, good enough)

We will create a class called Genome() since we will be using multiple instances of it later on.

class Genome:
    def __init__(self, target):
        self.gene_length = GENE_LENGTH
        self.gene = []
        self.x = width // 2
        self.y = 10
        self.step = 0
        self.target = target
        self.fitness = -1
        self.dead = False
        self.generation = -1

    def draw(self):
        pygame.draw.circle(display, (0, 170, 200), (self.x, self.y), 4)

    def create_genes(self):
        pass

    def move(self):
        pass

    def calc_distance(self):
        pass

    def calc_fitness(self):
        pass

    def crossover(self, partner):
        pass

    def mutate(self):
        pass

Each genome has a target and the performance of the genome is evaluated based on the target. In our case, the target is just a box and the objective of the genome is to reach the box/target.

The performance of a genome is also called the "fitness" of that genome. They are ranked based on their fitness. The step variable is used to step through the gene of the genome and make the moves based on that position of the gene.

The methods the genes are

create_genes: Create the initial genes randomly, consisting of (x, y) ordered pairs each with a random value between -1 and 1.
move: The move function steps through the gene using the step variable and updates the x position and the y position of the genome based on the (x, y) pair in the gene.
calc_distance: This method is used to calculate the distance between the genome and the target. The distance used here is the euclidean distance.
calc_fitness: The fitness is calculated based on the euclidean distance between the genome and the target. Then the distance is normalized between 0 and 1.
crossover: This is one of the important methods in the algorithm. We create new genomes from the genes of old ones. The crossover process in done by intertwining the genes of two parents. For example, let the following genomes be the parents.

Then to breed them, their gene are intertwined to make a new gene of the same length.

By this process, we can multiply the genes that result in a better fitness than poorly performing genes.

mutate: Mutation is also an important step in the genetic algorithm. Generally mutation is done based on a mutation rate, which is a constant. But we can also introduce varying mutation rates if we need to. However, we are going to use a constant mutation rate. Initialize a MUTATION_RATE variable which holds how much percentage of the genes should be mutated. In my code, I've given a 2% chance for mutation. Therefore, my MUTATION_RATE is going to be,

MUTATION_RATE = 0.02

While we are at it, we can also initialize some other important constants like the population size, the gene length etc...

POPULATION_SIZE = 100
MUTATION_RATE = 0.02
GENE_LENGTH = 10000

Now we can populate the genome class with actual code...

class Genome(object):
    def __init__(self, target):
        self.gene_length = GENE_LENGTH
        self.gene = []
        self.x = width // 2
        self.y = 10
        self.step = 0
        self.target = target
        self.fitness = -1
        self.dead = False
        self.generation = -1

    def create_genes(self):
        for _ in range(self.gene_length):
            x_direction = random.uniform(-1, 1)
            y_direction = random.uniform(-1, 1)
            self.gene.append([x_direction, y_direction])

    def draw(self):
        pygame.draw.circle(display, (0, 170, 200),
                           (self.x, self.y), 4)

    def move(self):
        self.x += self.gene[self.step][0]
        self.y += self.gene[self.step][1]
        self.step += 1

        if self.step >= self.gene_length:
            self.fitness = self.calc_fitness()
            self.dead = True

    def calc_distance(self):
        # using pythagoras' theorem to fing the shortest distance between the
        # genome and the give target
        perpendicular = abs(self.target.x - self.x)
        base = abs(self.target.y - self.y)
        dist = math.sqrt(perpendicular**2 + base**2)
        return dist

    def calc_fitness(self):
        # using a fitness function to find the fitness of
        # the specific genome, and use it as the metric to
        # improve it's probability of becoming a parent
        dist = self.calc_distance()
        normalized_dist = dist / height
        fitness = 1 - normalized_dist
        return fitness

    def crossover(self, partner):
        child = Genome(self.target)
        for i in range(self.gene_length):
            if i % 2 == 0:
                child.gene.append(self.gene[i])
            else:
                child.gene.append(partner.gene[i])

        return child

    def mutate(self):
        for i in range(GENE_LENGTH):
            mutation_probability = round(random.uniform(0, 1), 2)
            if mutation_probability < MUTATION_RATE:
                mutated_gene_x = random.uniform(-1, 1)
                mutated_gene_y = random.uniform(-1, 1)
                self.gene[i] = [mutated_gene_x, mutated_gene_y]

Creating the Population class:

A population is just a group of n number of genomes. In our case, a population consists of 100 genomes(POPULATION_SIZE). But, since we need to process the fitness of each genome, breed them, and also keep track of the generation, we'll encapsulate the information in a Population class.

class Population(object):
    def __init__(self, target):
        self.target = target
        self.population = []
        self.generation = 0

    def populate(self):
        pass

    def natural_selection(self):
        pass

    def breed(self):
        pass

The population class is going to hold a target, which will be passed on to the genomes of the population. It also keeps track of the generation and an array of all the genomes in the population.

As usual, we'll go through the methods in the class.

populate: As the name suggests, this method is used to populate the genomes in the population class. In the first generation, the genomes are made with random genes. At the later stages, the genomes are the children of their previous generation.
natural_selection: The natural selection method creates a mating pool, which is essentially just an array of genomes. But the mating pool has genomes whose frequency in the mating pool is directly proportional to the fitness of the genome. So the "fitter" a genome the higher the number of it in the mating pool. Since the fitter genomes are higher in frequency, the chances of them being selected for the mating process is also higher. Hence, the fitter genomes survive longer.

Survival of the fittest.

breed: Finally, the breeding part. Here we are just going to select random individuals from the mating pool generated by the natural_selection method and breed their genes by intertwining their genes as mentioned above.

Hence the code for the methods are,

class Population(object):
    def __init__(self, target):
        self.target = target
        self.population = []
        self.generation = 0

    def populate(self):
        self.population = [Genome(self.target) for _ in range(POPULATION_SIZE)]
        for genome in self.population:
            genome.create_genes()
            genome.generation = self.generation

    def natural_selection(self):
        mating_pool = []
        for genome in self.population:
            fitness_ratio = math.floor(max(genome.fitness, 0) * 100)
            for _ in range(fitness_ratio):
                mating_pool.append(genome)

        return mating_pool

    def breed(self):
        generation_dead = all([genome.dead for genome in self.population])
        if generation_dead:
            self.population = self.natural_selection()
            children = Population(self.target)

            for _ in range(POPULATION_SIZE):
                father_genome = random.choice(self.population)
                mother_genome = random.choice(self.population)
                child_genome = father_genome.crossover(mother_genome)
                child_genome.mutate()
                child_genome.generation = self.generation
                children.population.append(child_genome)

            self.population = children.population
            self.generation += 1

Creating the Target class:

The Target is the object that is going to be the destination for the genomes. We are going to evaluate the fitness of the genomes by calculating the distance between the target and the genome. The smaller the distance, the fitter the genome is. Therefore, the target object is only ever going to need to have two variables, x and y. And a draw method to draw the target to the screen.

class Target(object):
    def __init__(self):
        self.x = width // 2
        self.y = height - 10
        self.width = 20

    def draw(self):
        pygame.draw.rect(display, (0, 200, 170), (
            self.x - self.width // 2, self.y - self.width // 2, self.width, self.width))

Genetic Algorithm!

Finally it is time to see the algorithm work. But before that we have to create the necessary objects and add them to the main function. To do that,

def main():
    run = True
    food = Target()
    population = Population(food)
    population.populate()

    while run:
        display.fill((0, 0, 0))
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                run = False

        for genome in population.population:
            genome.draw()
            genome.move()

        food.draw()
        population.breed()
        pygame.display.flip()


if __name__ == "__main__":
    main()

Now if you run the code, you should see a screen like this,

Over time, you'll see those dots(genomes) get closer and closer to the target. Eventually, by the magic of the genetic algorithm, they'll be able to reach the target consistently. This is just a taste of the genetic algorithm's potential. There is a lot more to explore.

Thank you for reading. Feel free to comment your thoughts and opinions about this article.

My GitHub repo for genetic algorithm
I've added some extra flare to the code as well. :)

The fascinating Wave Function Collapse algorithm.

Kavin Bharathi — Mon, 17 Oct 2022 07:14:20 +0000

What is a wave function and why does it collapse?

Wave function collapse is a algorithm that can procedurally generate images, text, audio and almost anything that follows a pattern of a simple set of initial parameters and a set of rules. But the neat part is, wfc(short for wave function collapse) does all these without any artificial intelligence shenanigans. The output of wfc is a random showcase of the emergent behavior/rules built by you. This emergent behavior is what fascinates me! Now let's dive deeper into the nuances of wfc!

The "wave" in wfc!

In this article we'll talk about image generation only, unless specified otherwise. The "wave function" is the initial state of the image where no pixel or "cell" has been "collapsed" yet. There are many quotes involved in the last sentence, so let's break it down to simpler parts.

The wave function:

The wave function is the grid representation of the to-be generated image. This grid will hold the final image after the implementation of the algorithm is complete. When we say the function is being collapsed, it means that a cell is being assigned a specific sub image. For example,

These tiles are the basic constituents of the final image. Note that by randomly assigning tiles to each cell in the image, we'll not get the desired "pattern" since will cases where tiles connect into nothingness.

To improve this haphazard placement of tiles while also making large scale images efficiently, we use the wave function collapse algorithm.

The "collapse" in wave function:

Finally, it's time for the fun part. I am going to use Python(3.8) in this article, but you can use any language of your choice after you understand the underlying algorithm. Let's go.

Step 1: Building the display

The visualization part is going to be handled by Pygame, a python library for game development. But we'll use it to just display some images onto the screen(and also other little functionalities that'll come later).

To install Pygame,
in windows



pip install pygame

and in unix systems,



pip3 install pygame

To build a basic display,



import pygame
pygame.init()

# global variables
width = 600
height = 600
display = pygame.display.set_mode((width, height))

def main():
    # game loop
    loop = True
    while loop:

        display.fill((0, 0, 0))
        # event handler
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                loop = False

            if event.type == pygame.KEYDOWN:
                if event.key == pygame.K_d:
                    hover_toggle = not hover_toggle

                if event.key == pygame.K_q:
                    loop = False
                    exit()

        # update the display
        pygame.display.flip()

# calling the main function
if __name__ == "__main__":
    main()

Step 2: Creating the Cell class

Each individual "pixel" in the final image is going to be represented as a cell object. Therefore we are going to write a cell class that looks like this,



# Cell class
class Cell:
    def __init__(self, x, y, rez, options):
        self.x = x
        self.y = y
        self.rez = rez
        self.options = options
        self.collapsed = False

    # method for drawing the cell
    def draw(self, win):        
        if len(self.options) == 1:
            self.options[0].draw(win, self.y * self.rez, self.x * self.rez)

    # return the entropy of the cell
    def entropy(self):
        pass

    # update the collapsed variable
    def update(self):
        pass

    # observe the cell/collapse the cell
    def observe(self):
        pass

You'll notice that the methods 'entropy()', 'update()', and 'observe()' lack any actual code in them. Before writing the code let's understand what they actually do.

Entropy:
The entropy of a cell is a way of quantizing the number of choices for a cell. The choices are also called the states of the cell.
Observe:
By observing a cell, we are going to select a random state from all the possible states. This is done after we calculate the possible states by inferring from the nearby cells. This is the crust of the wfc algorithm.
Update:
In essence, update() is used to update the "collapsed" data variable of the cell object. The collapsed variable is True if the number of possible states of the cell is 1(i.e., the length of the options variable is 1) and False if otherwise.

Now, the content of the methods become,



    # return the entropy/the length of options
    def entropy(self):
        return len(self.options)

    # update the collapsed variable
    def update(self):
        self.collapsed = bool(self.entropy() == 1)

    # observe the cell/collapse the cell
    def observe(self):
        try:
            self.options = [random.choice(self.options)]
            self.collapsed = True
        except:
            return

With this the cell class is finally complete.

Step 3: Creating the Tile class

The tile class is used for managing the individual tiles and setting the rules for assembling them in the image. The rules for each tile set may vary, so make sure to update the rulesets if you wanna change the tile set. There is also algorithms to generate rulesets based on the given images. But we'll not cover that in this article.

The tile class is simple. Each tile instance is assigned an index variable and is represented visually by the tile image. The possible tile that can placed above, to the right, below and to the left are stored in self.up, self.right, self.down and self.left data variables respectively. These variables are used to update each cell and make the "collapsing" of the wave function possible.



class Tile:
    def __init__(self, img):
        self.img = img
        self.index = -1
        self.edges = []
        self.up = []
        self.right = []
        self.down = []
        self.left = []

    # draw a single tile
    def draw(self, win, x, y):
        win.blit(self.img, (x, y))

    # set the rules for each tile
    def set_rules(self, tiles):
        for tile in tiles:
            # upper edge
            if self.edges[0] == tile.edges[2]:
                self.up.append(tile)

            # right edge
            if self.edges[1] == tile.edges[3]:
                self.right.append(tile)

            # lower edge
            if self.edges[2] == tile.edges[0]:
                self.down.append(tile)

            # left edge
            if self.edges[3] == tile.edges[1]:
                self.left.append(tile)

Step 4: Creating the Grid class

The grid id going to hold the "wave", i.e., the image grid of the final output. This is the main core of the algorithm. So, let's get started.

The grid is going to hold a width, a height, a resolution variable(rez), a 2D array to hold all the cells in the output and a list of all the options(tiles) in the image.

Hence, the Grid class is initiated by,



class Grid:
    def __init__(self, width, height, rez, options):
        self.width = width
        self.height = height
        self.rez = rez
        self.w = self.width // self.rez
        self.h = self.height // self.rez
        self.grid = []
        self.options = options

And a simple method for displaying the 2D array in image format to the pygame display.



    # draw each cell in the grid
    def draw(self, win):
        for row in self.grid:
            for cell in row:
                cell.draw(win)

Then we need to initiate all the cells in the grid 2D array. We are going to make use of a method called "initiate()" to do that.



    # initiate each spot in the grid with a cell object
    def initiate(self):
        for i in range(self.w):
            self.grid.append([])
            for j in range(self.h):
                cell = Cell(i, j, self.rez, self.options)
                self.grid[i].append(cell)

Now, during each frame/cycle of the program, we are going to loop through all the cells in the grid array and calculate the entropy of each cell. Then we "collapse" the cell with minimum entropy to a single state. "Collapse" refers to the action of arbitrarily selecting a state from the possible options of the cell, based on its neighbors. The entropy of each cell in updated using the update method for every frame.

The heuristic_pick (picking cell with minimum entropy) method is,



    # arbitrarily pick a cell using [entropy heuristic]
    def heuristic_pick(self):

        # shallow copy of a grid
        grid_copy = [i for row in self.grid for i in row]
        grid_copy.sort(key = lambda x:x.entropy())

        filtered_grid = list(filter(lambda x:x.entropy() > 1, grid_copy))
        if filtered_grid == []:
            return None

        least_entropy_cell = filtered_grid[0]
        filtered_grid = list(filter(lambda x:x.entropy()==least_entropy_cell.entropy(), filtered_grid))     

        # return a pick if filtered copy i s not empty
        pick = random.choice(filtered_grid)
        return pick

Finally, we are going to perform the "collapsing" phase of the algorithm. Here we are going to loop through all the cells and update their entropy based on their neighbors. In the initial state, the algorithm will collapse a random cell to a random state. Then on, the cell entropy updates will guide the way. We'll check the top, right, bottom and left neighbors of each cell and change its self.options data variable accordingly. This options variable is used to quantify the entropy of each cell.

The code is given by,



    # [WAVE FUNCTION COLLAPSE] algorithm
    def collapse(self):

        # pick a random cell using entropy heuristic
        pick = self.heuristic_pick()
        if pick:
            self.grid[pick.x][pick.y].options
            self.grid[pick.x][pick.y].observe()
        else:
            return

        # shallow copy of the gris
        next_grid = copy.copy(self.grid)

        # update the entropy values and superpositions of each cell in the grid
        for i in range(len(self.grid)):
            for j in range(len(self.grid[0])):
                if self.grid[i][j].collapsed:
                    next_grid[i][j] = self.grid[i][j]

                else:
                    # cumulative_valid_options will hold the options that will satisfy the "down", "right", "up", "left" 
                    # conditions of each cell in the grid. The cumulative_valid_options is computed by,

                    cumulative_valid_options = self.options
                    # check above cell
                    cell_above = self.grid[(i - 1) % self.w][j]
                    valid_options = []                          # holds the valid options for the current cell to fit with the above cell
                    for option in cell_above.options:
                        valid_options.extend(option.down)
                    cumulative_valid_options = [option for option in cumulative_valid_options if option in valid_options]

                    # check right cell
                    cell_right = self.grid[i][(j + 1) % self.h]
                    valid_options = []                          # holds the valid options for the current cell to fit with the right cell
                    for option in cell_right.options:
                        valid_options.extend(option.left)
                    cumulative_valid_options = [option for option in cumulative_valid_options if option in valid_options]

                    # check down cell
                    cell_down = self.grid[(i + 1) % self.w][j]
                    valid_options = []                          # holds the valid options for the current cell to fit with the down cell
                    for option in cell_down.options:
                        valid_options.extend(option.up)
                    cumulative_valid_options = [option for option in cumulative_valid_options if option in valid_options]

                    # check left cell
                    cell_left = self.grid[i][(j - 1) % self.h]
                    valid_options = []                          # holds the valid options for the current cell to fit with the left cell
                    for option in cell_left.options:
                        valid_options.extend(option.right)
                    cumulative_valid_options = [option for option in cumulative_valid_options if option in valid_options]

                    # finally assign the cumulative_valid_options options to be the current cells valid options
                    next_grid[i][j].options = cumulative_valid_options
                    next_grid[i][j].update()

        # re-assign the grid value after cell evaluation
        self.grid = copy.copy(next_grid)

I've added comments to make it a little more understandable.

But before testing this out, we have make our front-end layer compatible with out algorithm in the back-end.

For that we have to add a little more to our code. First for loading images with padding,



# function for loading images with given resolution/size
def load_image(path, rez_, padding = 0):
    img = pygame.image.load(path).convert_alpha()
    img = pygame.transform.scale(img, (rez_ - padding, rez_ - padding))
    return img

Then, we'll update the main function to initiate and update the grid("wave").




# main game function
def main():
    # loading tile images
    options = []
    for i in range(5):
        # load tetris tile
        img = load_image(f"./assets/{i}.png", rez)

    # edge conditions for tetris tiles
    options[0].edges = [0, 0, 0, 0]
    options[1].edges = [1, 1, 0, 1]
    options[2].edges = [1, 1, 1, 0]
    options[3].edges = [0, 1, 1, 1]
    options[4].edges = [1, 0, 1, 1]

    # update tile rules for each tile
    for i, tile in enumerate(options):
        tile.index = i 
        tile.set_rules(options)

    # wave grid
    wave = Grid(width, height, rez, options)
    wave.initiate()

    # game loop
    loop = True
    while loop:

        display.fill((0, 0, 0))
        # event handler
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                loop = False

            if event.type == pygame.KEYDOWN:
                if event.key == pygame.K_d:
                    hover_toggle = not hover_toggle

                if event.key == pygame.K_q:
                    loop = False
                    exit()

        # grid draw function
        wave.draw(display)

        # grid collapse method to run the alogorithm
        wave.collapse()

        # update the display
        pygame.display.flip()

Finally, call the main function at last,



# calling the main function
if __name__ == "__main__":
    main()

Note that the algorithm is not guaranteed to find the solution. It will fill the image as far as possible. To guarantee a solution, we can use backtracking algorithm and undo previously collapsed cell states and continue until a solution is reached.

Thank you for reading. Feel free to comment your thoughts and opinions about this article.

Github repo for wfc