Assistant Professor

Department of CSE

UoK, North Campus,

 Delina, Bla 

Introduction

Genetic algorithm (GA) is a searching technique based on human genetics and natural selection. John Holland developed it in 1975 at the University of Michigan [1]. Genetic algorithm (GA) tries to find the optimal solutions. In GA, the decision variables of a search problem are encoded into finite-length candidates. Genes are the alphabets of chromosomes, and chromosomes are the strings that represent potential solutions to the search problem. For instance, a gene might stand in for a city and a chromosome for a path in a problem like the travelling salesman problem [8]. Unlike conventional optimization methods, GA utilizes parameter coding instead of the actual parameters.

Natural selection is used to create the best chromosomes that solve problems, but in order to do so, we need a way to distinguish among good and bad chromosomes/solutions [9]. The measure may take the form of a subjective function where people select better solutions over inferior ones, or it may take the form of an objective function represented by a computer simulation or a mathematical model. The relative fitness of a candidate solution must be ascertained using the fitness measure; the GA will then use this information to direct the evolution of strong candidate solutions. GA is also used in the field of cryptography, in [13] a genetic algorithm-based technique is used to identify the valuable pixels where the data can be securely hidden in order to hide the information over the image in a sophisticated way.

The idea of the population is another crucial idea in GA. A population of potential solutions is what a genetic algorithm uses, in contrast to conventional search techniques. The population size is a crucial component that impacts the scalability and performance of genetic algorithms. It is often a user-specified quantity. A tiny population size, for instance, could result in early convergence, poor solutions, or local optima. However, a huge population size results in the needless use of precious computing time. Once the chromosomal encoding of the candidate solutions and the definition of a fitness measure to separate the good from the bad solutions are obtained, the following steps are used to begin the process of evolving solutions:

i. Initial Population: Typically, the first set of potential solutions is produced at random throughout the search space. After that, each created candidate solution is represented as a chromosome in a string sequence of length l that corresponds to the problem encoding.

ii. Fitness Evaluation: The fitness values of the potential solutions are assessed in accordance with the objective function after the population has been initialized or an offspring population has been formed. The problem determines the objective function.

iii. Selection: The algorithm is guided by the selection component to distribute more copies of the solutions with better fitness values over the ones with lower ones. This forces the candidate solutions to adhere to the survival-of-the-fittest mechanism as described in natural selection theory. To achieve this goal, numerous selection processes have been put forth, such as elitism, ranking, tournament, and roulette-wheel selection.

iv. Recombination/Crossover: Recombination or Crossover in human biology combines the parental genetic material of two parents with each other, with the possibility that better offsprings shall be produced. The crossover may take place at one or more than one point among the parental chromosomes. The same thing is exploited in the GA with the intuition that parental solutions combine and refine over successive generations and get close to or produce optimal solution/solutions. Chromosomes are typically randomly split and merged in GA, resulting in a child's genes coming from one parent and the other from the other.

v. Mutation: The genetic material can be randomly altered in human biology or in natural evolution due to mistakes in reproduction or other gene distortions caused by environmental factors like gamma radiation. Within GA, mutation can be experienced as an arbitrary reorganization of genes with a specific likelihood, referred to as the mutation probability. Preserving genetic variety and avoiding local optima are two beneficial outcomes. Several static and adaptive mutation strategies are described in the study presented in [12] to help in understanding the nature of genetic algorithms.

vi. Repeat steps 2–5, until a terminating condition is met.

GA parameters:

The GA parameters have a direct relation on the degree of quality of solutions and thus keep the parameter values in balance to improve the overall performance of GA. The four important parameters used in genetic algorithm are as below:

i. Mutation Rate (ρ_m): Mutation rate denoted by ρ_m denotes that how many chromosomes in a certain population shall be mutated [6]. Mutation rate i.e. mutation probability is defined in the range of [0, 1]. The purpose of mutation in the population is to prevent local optima, but if it occurs frequently then genetic algorithm is changed to randomized search [3].

ii. Population Size: The population size of a generation is the total number of individuals inside it. The choice of population size is crucial to the implementation of GA; if the population is small (i.e., the search space is tiny), there may be a local optimal solution or solutions. Similarly, a greater population size (larger search space) results in a high computational time [2]. As a result, the population size should be reasonable.

iii. Crossover Rate (ρ_c): The number of times a chromosome crosses over in a generation that is the chance that the two chromosomes swap genes is known as the crossover rate, often referred to as the crossover probability. A crossover probability of 100% indicates that the progeny are the result of crossover, whereas a crossover probability of 0% indicates that the entire new generation is a copy of the old generation. The crossover rate falls between [0,1] [4].

iv. Number of generations: It means the number of times we have to iterate GA. In some cases we require hundreds of iterations and in some cases we might require more, depending upon the type and complexity of the problem.

Optimization:

The process of improving anything is called optimization. Optimization is the process of determining input values so as to provide the best possible output values. The term "best" has different meanings for different problems. It means, mathematically speaking, that you can change the amount of inputs to maximize or minimize the value of the object function. Search space is the set of all potential solutions. There is a point, or combination of points, in this search space that provides the best answer. To discover that solution is the goal of optimization. GA tries to find optimal solutions for a wide range of problems [10].

Algorithm: Genetic Algorithm

1. Initially,  select the population at random

2. Do Until Convergence

i. Determine each individual’s  fitness within the population

ii. Select the population using the selection operator, remove the remaining individuals from the population

iii. Crossover the chosen individuals and include their progeny in the population.

iv. Mutate population members at random.

3. Select the best individual to serve as the answer after convergence.

Genetic algorithm steps

i.Initial Population: The initial population of chromosomes (solutions) is created and we use  the particular chromosome Encoding scheme as per the problem.

ii. Evaluation: Based on the problem's objective function, assess each chromosome's fitness. The GA can examine each chromosome's performance in the population with the help of the fitness function.

iii. Selection: A population's chromosomes are chosen to be the parents of its progeny. In accordance with Darwin's theory of evolution, the most fit individuals should prevail and procreate. The following are the different ways that parents can choose which chromosomes to crossover.

a. Roulette Wheel Selection: The proportionate reproductive operator, which selects a chromosome from the mating pool with a probability proportional to fitness, is the most widely employed reproduction operator. As a result, the population's i^th chromosome is chosen with a probability proportional to its fitness value, F_i. The probability of each i^th chromosome is given by:

 

Where, n = size of the population. It is anticipated that the roulette wheel selection will favor those with better fitness values over other candidates. Another variant of roulette wheel selection is improved roulette wheel selection [11].

b. Tournament selection: The chromosomal population participates in a tournament competition held under the tournament selection approach. The most fit individual is the best individual, or the tournament winner. The process is continued until the desired population size is attained, with the winners being added to the mating pool for the creation of new progeny.

c. Rank Selection: Rank selection first ranks the chromosomes according to their fitness values and then selects the high fitness chromosomes to go in the mating pool. The low fitness chromosomes are deleted and are replaced by the high fitness chromosomes to make the population size same.

d. Elitism: A tiny percentage of the better chromosomes are copied into the next generation unaltered, which is known as elitism. The rest is handled in the usual way.

Recombination (Crossover): The Crossover operator is applied to the mating pool with the hope that it would create better offsprings to go in the next generations [7]. There are different types of crossover operations in genetic algorithm.

a. Single-Point Crossover: In single-point crossover, a random position w.r.t to chromosome length is selected that decide the crossover site and the exchange of genes takes place as shown below.

b. Two-Point Crossover: In two-point crossover, two random positions w.r.t to chromosome length are selected that decide the two crossover sites and the exchange of genes takes place as shown below.

c. Multi-Point Crossover: In muti-point crossover, random positions w.r.t to chromosome length are selected that decide the crossover sites (even & odd) and exchange of genes takes place as shown below.

Mutation: In GA, mutation can be realized as a random deformation of genes with a certain probability known as mutation probability. The positive effect is preservation of genetic diversity and can also avoid the local optima. Mutation is vital to ensuring genetic diversity within the population. The mutation rate shall be very low in the range [0,1].

Termination Condition: Iteration after iteration, at last genetic algorithm has to stop with an optimal or a near optimal solution in hand, there are several termination conditions [5] that are used:

a. Meet a predefined number of generations.

b. Convergence towards an optimal solution

c. No improvements in the best fitness magnitude

GA Flow Chart: The following fig-1 shows the flow chart of genetic algorithm:

Fig-1: GA Flow chart

Applications of GA:

i. Design (semiconductor layout)

ii. Scheduling (resource allocation) 

iii. Robotics (trajectory planning)

iv. Machine Learning (designing Neural networks)

v. DSP (filter design)

vi. Game Playing (poker, checkers)

vii. Combinatorial optimization (TSP)

viii. Image Processing (segmentation)

Examples:

Example-1: Use Genetic algorithm to Maximize the function f(x) = x² ,  where x  varies between 1 to 31

Sol: For this problem the objective is to maximize the value of function f(x) = x^2.

Iteration 1^st:

Form the chromosomes as binary strings. Take an initial chromosome population of size 4. Choose a random population of four strings as under.

Ch[1] = 0 1 1 0 1

Ch[2] = 1 1 0 0 0

Ch[3] = 0 1 0 0 0

Ch[4] = 1 0 0 1 1

Fitness of the chromosomes is calculated by f(x) = x² as shown in column number 4 of the table

1. The selection of parental chromosomes for the mating pool is determined by Roulette Wheel selection method. In the mating pool single point crossover operation is used.

Table-1: Iteration-1, Steps of GA for f(x)

After crossover is over mutation is randomly performed as under:

Total No. of genes = genes per chromosomes * No. of Chromosomes

=4x6

=24

Suppose we define ρ_m 10%, it is expected that 10% (0.1) of total genes in the population shall be mutated. Therefore No. of mutations = 0.1 * 24 = 2.4 ≈ 2

Generate Two Random Numbers between 1-24, say: 12 and 22 (Two Gene Positions) Again generate the two random numbers between 1-30, say 1 and 7 (Two New Genes)
Iteration 2^nd: Table-2 delineates the 2^nd iteration:

Table-2: Iteration-2, Steps of GA for f(x)

After running successive generations, solution is/may converged and best chromosome may/is obtained.

Chromosome = [1 1 1 1 1]

This means that: (1 1 1 1 1 )₂=(31)₁₀ Objective function: f(x) = x²

= 31 x 31 = 961

Summary:

Evolutionary algorithms like genetic algorithm apply the rules of nature i.e. evolution through selection of fittest individuals, the individuals represent the solutions to a particular problem. Genetic algorithm is robust kind of evolutionary algorithm that is applied to wide variety of optimization problems. GA promises convergence and lead towards the optimality or near optimality.
References:

1. Holland, J.H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence; MIT Press: Cambridge, MA, USA, 1975.

2. Roeva,O. Fidanova,S. Paprzycki,M. Influence of the population size on the genetic algorithm performance in case of cultivation process modelling. In Proceedings of the IEEE Conference on Computer Science and Information Systems, Kraków, Poland, 8–11 September 2013; pp. 371–376.

3. Razali, N.M. Geraghty, J. Genetic algorithm performance with different selection strategies in solving TSP. In Proceedings of the world congress on engineering, London, UK, 6–8 July 2011; pp. 1–6.

4. De Jong,K.; Spears, W. A formal analysis of the role of multi-point crossover. Ann. Math. Artif. Intell. 1992, 5, 1–26.

5. Safe, M. Carballido, J. Ponzoni, I. Brignole, N. On stopping criteria for genetic algorithms. In Brazilian Symposium on Artificial Intelligence; Springer: Berlin/ Heidelberg, Germany, 2004; pp. 405–413.

6. Hassanat, Ahmad, Khalid Almohammadi, Esra’A. Alkafaween, Eman Abunawas, Awni Hammouri, and VB Surya Prasath. "Choosing mutation and crossover ratios for genetic algorithms—a review with a new dynamic approach." Information 10, no. 12 (2019): 390.

7. Hassanat, Ahmad BA, and Esra’A. Alkafaween. "On enhancing genetic algorithms using new crossovers." International Journal of Computer Applications in Technology 55, no. 3 (2017): 202-212.

8. Singh, A.; Singh, R. Exploring travelling salesman problem using genetic algorithm. Int. J. Eng. Res. Technol. 2014, 3, 2032–2035.

9. Mirjalili, Seyedali, and Seyedali Mirjalili. "Genetic algorithm." Evolutionary Algorithms and Neural Networks: Theory and Applications (2019): 43-55.

10. Jafari, M., and S. A. Mahmodzade Hoseyni. "Optimization of infinite orthotropic plates with hypotrochoid cutout under tensile loading using genetic algorithm." Journal of Reinforced Plastics and Composites 36, no. 5 (2017): 360-376.

11. Yu, Fengrui, Xueliang Fu, Honghui Li, and Gaifang Dong. "Improved roulette wheel selection-based genetic algorithm for TSP." In 2016 International conference on network and information systems for computers (ICNISC), pp. 151-154. IEEE, 2016.

12. Rajakumar, B. R. "Static and adaptive mutation techniques for genetic algorithm: a systematic comparative analysis." International Journal of Computational Science and Engineering 8, no. 2 (2013): 180-193.

13. Sethi, Pratiksha, and V. Kapoor. "A Secured System for Information Hiding in Image Steganography using Genetic Algorithm and Cryptography." International Journal of Computer Applications 975, no. 8887 (2016).