In this lesson, Introduction to Genetic Algorithms, we are going to learn Genetic Algorithms. Genetic algorithms are widely recognized as one of the most commonly used evolutionary algorithms, in terms of their versatility and applicability. Genetic algorithms (GA) are possibly the first algorithmic models developed to simulate genetic systems. A significant number of well-known optimization problems have been successfully tackled with the help of genetic algorithms. Genetic algorithms are population-based, and many modern evolutionary algorithms are either directly based on genetic algorithms or exhibit significant similarities. Genetic algorithms can deal with complex optimization and learning problems because of their parallel computing structure. Let’s dive into the details of Genetic Algorithms.
The genetic algorithm (GA), which was initially developed by John Holland and his colleagues in the 1960s and 1970s, is a mere model or abstraction of biological evolution that is based on Charles Darwin’s theory of natural selection. It is important to note that Holland was possibly the first to utilize the crossover and recombination, mutation, and selection approaches in the study of adaptive and artificial systems. These genetic operators are deemed to be the integral aspect of the genetic algorithm that is utilized as a problem-solving strategy. Subsequently, numerous variations of genetic algorithms have been created and utilized for a broad array of optimization problems, ranging from graph coloring to pattern recognition, from discrete systems (such as the traveling salesman problem) to continuous systems (e.g., the efficient design of airfoil in aerospace engineering), and from financial markets to multi-objective engineering optimization problems. There are various advantages of genetic algorithms over traditional optimization algorithms, and it is not for us to boast about them. Two of the most notable benefits of using Genetic Algorithms are the ability to deal with complex problems and parallelism. As genetic algorithms are population-based algorithms, multiple offsprings within a population act as independent agents, and the population (or any subgroup) can simultaneously explore the search space in many directions. These characteristics of genetic algorithms give a cutting-edge advantage in handling complex problems of various domains and disciplines. Before getting lost in the realm of genetic algorithms, let’s discuss the major components and implementation of Genetic Algorithms.
Steps involved in the Genetic Algorithms:
Encoding your objective problem: This is the first step before you start implementing the genetic algorithms. Encoding the problem involves representing the candidate solutions to the problem as chromosomes. The encoding scheme determines how the problem variables are mapped onto the chromosome structure. There are several encoding schemes available in the literature on Genetic Algorithms. Some popular encoding schemes are Binary Encoding, Real-valued Encoding, Permutation Encoding, Value Encoding, and Tree Encoding. The choice of encoding scheme depends on the nature of the problem being solved. A well-designed encoding scheme can significantly improve the efficiency and effectiveness of the genetic algorithm, while a poorly designed one can lead to slow convergence and suboptimal solutions. If you want to know more about encoding schemes, click here. ( Encoding Schemes in the Genetic Algorithms)
Initialize Population: Like any other evolutionary algorithms, Genetic algorithms also start the search process by initializing random representative solutions known as individuals in the search space. The set of these random representative solutions or individuals is referred to as the Population. The number of individuals indicates the population size. Each individual has two properties: its location (chromosome composed of genes) and its quality (its fitness). The chromosome represents the encoding system used by the Genetic algorithm to specify the position of the individuals in the search space and fitness is calculated using the given objective function.
Evolution Cycle of Genetic Algorithms: After initializing the population, genetic algorithms modify the initial population to generate a new population using three important operators known as Selection, Crossover, and Mutation. These operators are motivated by genetic principles and try to mimic the process of evolution. In the literature on Genetic algorithms, various Selection, Crossover, and Mutation operators have been proposed. Let’s discuss the basic version of these operators in detail to understand the simple Genetic Algorithm.
Selection in the Genetic Algorithm:
After initialization, the Genetic Algorithms proceed to enter the primary loop. This loop begins with a selection process that emulates natural selection by granting more breeding opportunities to the fittest individuals. The loop culminates with two variation operators: crossover and mutation. These operators imitate natural reproduction by exchanging genes between parents to produce offspring. In the realm of programming, it is necessary to establish another memory to reserve the individuals selected for breeding. This memory is commonly referred to as the mating pool. There are several ways to embed the idea of natural selection, one of which is by using the relative fitness value. Suppose an individual i has fitness value fi . According to natural selection, fitter individuals have more advantages in breeding. So relative fitness value is given as follows:
p_{i} = \frac{f_{i}}{\sum_{i=1}^{popsize} f_{i}} ; i=1,2,...,popsizeRelative fitness value can also be seen as the probability of being selected. For implementing this in your programming environment, a roulette wheel selection mechanism is used. Apart from the above-mentioned selection method, there are more ways to create a mating pool using selection methods like tournament selection, random selection, etc. For a detailed discussion on the selection operator click here.
Variation Operators: Crossover and Mutation
There exist numerous variation operators that facilitate the alteration of information in individuals within the mating pool. When an exchange of information, such as gene exchange, occurs amongst two or more individuals, this variation operator is referred to as crossover or recombination. Conversely, when the genes of a single individual are altered, this variation operator is referred to as a mutation. As for our discussion, we shall be introducing the single-point crossover and bit-flip mutation.
Two new individuals are generated by crossover, which is generally seen as the major exploration mechanism of the Genetic Algorithm. After crossover, the mutation operator is applied. Every individual is mutated with a mutation probability pm called the mutation rate. Provided gene j needs to be mutated, we make a bit-flip change for gene j, i.e., 1 to 0 or 0 to 1. We call this operator a bit-flip mutation.
Small changes are introduced into a chromosome by bit-flip mutation, which could be seen as one local search method and is generally considered a minor exploring mechanism of simple Genetic Algorithms. If every gene of an offspring does not mutate according to probability pm, the mutant is the offspring itself. After the variation operators, a new population is generated. We need to evaluate the fitness of every individual and then replace the old population with the new one. This process is called replacement in Genetic Algorithms. Now, Genetic Algorithm will iterate through the process mentioned above to generate a new population to explore the search space more efficiently.
Summary:
In conclusion, Genetic Algorithms are the most powerful and fundamental evolutionary algorithms. If you want to implement Genetic Algorithms for any application, you just need to understand the following steps.
- Initialize the population with random individuals
- Evaluate the fitness of each individual
- Repeat the following steps until the termination condition is met:
- Select parents for reproduction based on fitness (e.g., using tournament selection or roulette wheel selection)
- Perform crossover to create offspring (e.g., using single-point or multi-point crossover)
- Perform mutation on the offspring (e.g., flip bits or modify values with a small probability)
- Evaluate the fitness of the offspring
- Replace some individuals in the population with the offspring (e.g., using elitism or generational replacement)
- If the termination condition is met, exit the loop
- Return the best individual as the solution
You can find the Python and Matlab code for the Genetic Algorithm here. Leave a comment if you enjoyed learning Genetic Algorithms.