Genetic Algorithm (GA) is based on the process of biological evolution, which includes chromosome representation, fitness selection, and biologically inspired operators [1]. As an optimization problem solver, a genetic algorithm uses the natural selection of the fittest chromosomes. This algorithm reflects the process of natural selection, where the fittest individuals are selected for reproduction to produce offspring for the next generation.
In the computer world, genetic material is represented by strings of bits, while natural selection is modeled by fitness functions. The selection operator is then used to choose the parents that will produce the next generation. Crossover and mutation operations represent the mating process among parents. Figure 1 below illustrates the flow of the GA method.
Figure 1: Flowchart of Genetic Algorithm
In genetic algorithms, a chromosome is a set of parameters that defines a proposed solution to the problem the algorithm is trying to solve. The set of all solutions is known as the population. Chromosomes are often represented as binary strings, although many other data structures can also be used. Finding a suitable representation of the problem domain for a chromosome is an important consideration, as a good representation will simplify the search by reducing the search space. Conversely, a poor representation will result in a larger and more complex search space.
Below is a simple example of defining a chromosome.
Figure 2: Chromosome Representation Example
The first step in generating the initial population is to determine the size of the original image chromosome, 𝑛 n. For example, the size of the chromosome depends on the number of gray levels in the image that have more than 50 pixels. The gray levels with more than 50 pixels for Image 1 are 0, 12, 35, 58, 105, 120, 188, 201, 220, and 255, while for Image 2 they are 0, 15, 97, 178, 223, and 255. Therefore, the chromosome size for Image 1 is 8, while for Image 2 it is 6.
After that, an array of random numbers of size 𝑛 n is generated within the range of 0 to 255. The numbers in this array are then sorted in ascending order.
Figure 3: Initial Population Generation
A genetic operator is a mechanism used in genetic algorithms to guide the algorithm toward an optimal solution. The three primary types of genetic operators are mutation, crossover, and selection:
Selection of the best chromosomes is performed based on the fitness value of each solution, in order to choose parents for reproduction.
Crossover involves randomly selecting genes from each parent and exchanging them to produce new individuals.
Mutation randomly changes the value of certain genes to introduce variability.
For example, in Figure 4 below, the crossover point is indicated by the black line. All genes beyond that point in the chromosome are swapped between the two parents to produce new chromosomes O1 and O2.
Figure 4: Crossover Operation Example
Figure 5 illustrates a mutation operation, where the genes with values of 54 and 197 are changed to 62 and 191, respectively.
Figure 5: Mutation Operation Example
[1] S. Katoch, S. S. Chauhan, and V. Kumar, “A review on genetic algorithm: past, present, and future,” Multimedia Tools and Applications, vol. 80, no. 5, pp. 8091–8126, Feb. 2021
[2] M. S. Yadav, S. A. Giri, and V. C. Momale, “Sizing analysis of louvered fin flat tube compact heat exchanger by genetic algorithm,” Applied Thermal Engineering, vol. 125, pp. 1426–1436, Oct. 2017