Introduction to AI Algorithms Part-2: Genetic Algorithms

7 min readJan 8, 2018

Genetic Algorithms was one of the topics I had studied during my Undergrad which I wished to explore further.

Genetic Algorithms is a problem solving approach which aims to search for an optimal solution for large-scale, complex problems by relying on principles of Evolution and Natural Selection. As proposed by Charles Darwin, living beings evolve over time and improve on their desirable traits; within a population, only the fittest individuals survive. These insights have been applied extensively over a wide range of optimization and search problems across multiple domains such as Cryptography, Game Theory and Quality Control in Software Engineering and serve as the guiding principles for Genetic Algorithms.

Guiding Principles

Genetic Algorithms typically involve a number of candidate solutions for a problem statement referred to as Phenotypes. The basic and foremost procedure involves some or all of these Phenotypes going through an Evolution process leading to an optimal solution. Each Phenotype has a set of properties called its Genotype. These Genotypes are operated upon by one or more Genetic Operators iteratively in order to bring them closer to the optimal solution. It is important to translate the Phenotype’s properties into a Genotype representation which is easy to understand and operate upon.

The Genetic Algorithm involves randomly generating an initial population of individuals and iteratively performing a set of Genetic Operations on them to generate the next population.

Each iteration of the Genetic Algorithm can be broadly divided into the following steps:

Parent Selection- Selecting individuals from the population which are going to combine their genes to generate offsprings. This process could be biased towards the fitter individuals within a population but should also have a degree of randomness in order to maintain diversity in the population and avoid a few individuals dominating over others.
Crossover- This involves combining the selected parents’ characteristics to generate new offsprings.
Mutation- This process involves randomly mutating one of more characteristics of a few members of the population. This process is done to introduce some genetic diversity within the population and to ensure that the offsprings are not exact copies of their parents.
Elimination- This involves discarding a few members of the previous population. Individuals are selected psuedo-randomly to be eliminated from the population. In order to enforce the intuition of Survival of the Fittest, we introduce Eliltism into the algorithm. This step ensures that the fittest members of the population are always carried on to the next generation.

The evaluation of the Genotype’s fitness is done using a Fitness Function. This function serves as an evaluation step which guides the Genetic Algorithm towards the optimal value. The implementation of the Fitness Function depends on problem specific metrics.

Problem Statement

Given a target image, we attempt to reproduce that image by randomly generating polygons of varying shapes and colors on a blank canvas and operating on them by employing principles of Genetic Algorithms.

Implementation Details

Our implementation of the Genetic Algorithm to reproduce a target image using randomly generated polygons has been outlined in the following code:

def scm():
    current_population = Population()
    current_population.generate_initial()

    generation_index = 1
    while True:
        new_population = deepcopy(current_population)
        parents = new_population.select_parents()
        new_population.crossover(parents)
        new_population.mutate()
        new_population.elitism()

        if new_population.get_best_fitness() < current_population.get_best_fitness():
            current_population = new_population

        generation_index += 1

The function’s name stands for Selection, Crossover and Mutation, the three major Genetic Operations employed in each iteration of the algorithm. We start off by generating a random population of 50 Genotypes. We then run an infinite loop where in each iteration we sequentially perform the three Genetic Operations to generate the next population. We also employ Elitism by carrying over the 8 most fit Genotypes to the next population. Rest of the members are selected randomly.

Parent Selection

Parents, who will combine their genes to generate new offsprings, are selected using Stochastic Universal Sampling. SUS is an improvement over Fitness Proportionate Selection since it reduces Selection Bias and does not allow the gene pool to be dominated by only the few fittest members of the population.

def select_parents(self):   # Stochastic Universal Sampling
    total_fitness = self.compute_total_fitness()
    point_distance = total_fitness / NUMBER_OF_PARENTS
    start_point = uniform(0, point_distance)
    points = [start_point + i * point_distance for i in range(NUMBER_OF_PARENTS)]

    parents = set()
    while len(parents) < NUMBER_OF_PARENTS:
        shuffle(self.genotypes)
        i = 0
        while i < len(points) and len(parents) < NUMBER_OF_PARENTS:
            j = 0
            while j < len(self.genotypes):
                if self.get_subset_sum(j) > points[i]:
                    parents.add(self.genotypes[j])
                    break
                j += 1
            i += 1

    return list(parents)

In our implementation of SUS, we calculate the interval size based on the total fitness of the population and the number of parents we need to select. Then we randomly generate evenly-spaced points on a scale and select the parent in whose region the point lies. This provides for a fair representation of both fit and relatively unfit members in the parent set and helps in maintaining a healthy competition in the population.

Crossover

Having selected the parents, we combine their characteristics to generate new children. This is done by a technique known as Single Point Crossover. Here we represent the parents as sequences of points and randomly select a point from which we combine both the parents’ genes to generate two distinct children.

def crossover(self, parents):
    shuffle(parents)
    for i in range(0, NUMBER_OF_PARENTS, 2):
        parents[i], parents[i + 1] = self.generate_crossover_children(parents[i], parents[i + 1])

def generate_crossover_children(self, parent_1, parent_2):    # Single Point Crossover
    crossover_point = randrange((4 * NUMBER_OF_POLYGONS) / 10, (6 * NUMBER_OF_POLYGONS) / 10 + 1)
    child_1, child_2 = Genotype(), Genotype()
    f = lambda par, child, i: child.polygons.append(par.polygons[i])
    for i in range(crossover_point):
        f(parent_1, child_1, i)
        f(parent_2, child_2, i)
    for i in range(crossover_point, NUMBER_OF_POLYGONS):
        f(parent_1, child_2, i)
        f(parent_2, child_1, i)
    child_1.mutate()
    child_2.mutate()
    return child_1, child_2

After generating the children, we also Mutate them slightly to incorporate some diversity into our gene pool.

Mutation

Additionally, we also Mutate a few members of the current population with a pre-defined Mutation Probability. Each population instance has twenty Genotypes. Further, each Genotype has fifty polygons. Lastly, each polygon consists of three to five points and a color represented by its RGBA value.

The Mutation step involves randomly selecting a few Genotypes within a population. Within each Genotype, we randomly select a few polygons to Mutate. For each selected polygon, we either randomly generate new points for it or change its color to a new random value.

Evaluating Fitness

Each Genotype represents a randomly generated image. Its fitness is determined by calculating the root squared error for each of its pixels with respect to the target image. This gives a fair estimate of how close the generated image is to the target image.

def compute_fitness(self):
    if self.image is None:
        self.generate_image()

    self.fitness = get_image_error(self.image)def get_image_error(image1):
    error = 0.0
    for x in range(IMAGE_WIDTH):
        for y in range(IMAGE_HEIGHT):
            rgb1, rgb2 = image1.getpixel((x, y)), IMAGE_MATRIX[x][y]
            delta = 0.0
            for i in range(3):
                delta += pow(rgb1[i] - rgb2[i], 2)
            error += float(sqrt(delta))

    return error

Challenges Faced

One of the major challenges faced during this project was to optimize the algorithm’s performance given it involved several computationally expensive operations. One major performance improvement was achieved by storing the pixel values for the target image in a matrix rather than calculating it every time we needed to evaluate a Genotype’s fitness.

Other challenges included configuring various parameters such as Population Size and Mutation Probability in order to avoid premature convergence.

The Python script containing the Algorithm was run on a temporary Heroku Dyno. The generated images were saved to a Dropbox folder at regular intervals to save the progress for when the Dyno restarts.

Results

The algorithm produces half decent results in some cases. For most of the complex images, it fails to move beyond a local maxima in terms of the fitness achieved. This is primarily due to the algorithm’s inability to perceive the finer details within an image while evaluating fitness.