What to Expect

This is the first article in a series that I will be writing, and today marks the beginning. This series aims to learn the theory about Genetic Algorithms (GAs) and put the acquired knowledge into practice using Python.

We will combine theory and practice, and each article will take us a step closer to our goal. Therefore, we’ll focus our efforts on dissecting, but not exhausting, the topics surrounding Genetic Algorithms.

The articles will have modular structures, where we will discuss biological (albeit briefly) and mathematical concepts, in addition to implementing them.

The primary reference, initially, is “Algoritmos Genéticos”.

Some abbreviations we’ll use:

• EA: Evolutionary Algorithm
• CI: Computational Intelligence
• GA: Genetic Algorithm

As a tip, to avoid getting too lost at the beginning, I suggest you research two things: what optimization is and what heuristics are.

With that said, let’s start our journey with GAs by answering the following question:

What Are Evolutionary Algorithms?

They are algorithms that use computational models inspired by natural evolutionary processes to solve complex problems. They arise from the actions of individuals interacting with each other and with the environment, producing through these interactions a collective intelligence aimed at solving these problems. Generally, these individuals perform very simple tasks, but within a collective context, they can solve highly complex problems.

The evolution of species, the search for food by a colony of bees or birds, and the response of an immune agent to the invasion of pathogens, essentially involve searching in high-dimensional spaces with highly complex functions, requiring cooperation from the individuals within this environment for constant adaptation.

With this in mind, it’s believed that we can be inspired by these mechanisms in a way that builds other computational mechanisms capable of solving highly complex problems.

What Are Genetic Algorithms?

As you’ve probably already noticed, GAs are part of evolutionary algorithms, and they are a search technique that metaphorically represents the biological process of the natural evolution of species and genetics (Hello, Darwin. Hello Mendel, how are you?).

GAs are heuristic techniques for global optimization.

To get a general idea, optimization is the field of knowledge whose techniques aim to determine the extremes (maxima or minima) of functions in defined domains.

“How to transform Darwin’s ideas into algorithms?” (Holland, 2000)

The main idea is that the evolutionary process helps to have a set of individuals that are adapted to the environment where they are. Darwin showed that natural evolution relies on two basic mechanisms: selection and reproduction with variation.

In summary, selection will ensure that individuals who best adapt to the environment will also have a greater probability of survival, and consequently, will propagate their characteristics to future generations. Reproduction with variation will ensure that the offspring of these individuals are not an exact copy of their parents. This creates what we call evolution in the population over generations.

A highlight needs to be made: natural evolution is not a process exclusively aimed at achieving an optimal solution. What it does is a competition between individuals and through the process of survival, only the fittest tend to survive. It is possible, though very uncommon, for a generation to have worse individuals than past generations.

But in these algorithms, what indicates whether an individual is good or not? As already mentioned in the optimization description, we use functions (the function we want to optimize) to calculate what we call evaluation. From this evaluation, we determine if an individual is good or not.

Just as in nature, the information is encoded in chromosomes, and reproduction will cause the population to evolve. In GAs, reproduction occurs similarly to sexual reproduction to ensure the combination of two different genomes, thus causing diversity within the population. In addition to reproduction, GAs also involve mutation, which occurs less frequently compared to reproduction but ensures the population doesn’t become homogeneous due to the reproduction of the fittest individuals.

Reproduction and mutation will be applied to the selected individuals, with the fittest being selected more frequently to keep the best traits in the population. For this reason, the less fit individuals are discarded, leading to rapid convergence in the algorithm. We call this phenomenon genetic convergence, characterized by low diversity in the population. When this happens, reproduction will not generate diversity, leaving only mutation to do so. The greater the loss of diversity, the faster the convergence.

What Will We See in Part 2?

Much of what has been covered in this part may still leave you a little confused, but in Part 2, we will delve deeper into many of the terms introduced here. So, for the next part, you can expect:

• Terminology
• The No Free Lunch Theorem
• Search
• Schema/structure of a GA

See you soon!