Scribd
Upload
5 views116 pages

Genetic Algorithm Complete PDF

Genetic Algorithms (GAs) are optimization techniques inspired by natural selection, used to find optimal solutions to complex problems. They operate through a process involving a population of candidate solutions that evolve over generations via selection, crossover, and mutation. GAs are particularly effective for NP-Hard problems and situations where traditional methods fail, delivering good-enough solutions quickly.

Uploaded by

manigates1381
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
5 views116 pages

Genetic Algorithm Complete PDF

Genetic Algorithms (GAs) are optimization techniques inspired by natural selection, used to find optimal solutions to complex problems. They operate through a process involving a population of candidate solutions that evolve over generations via selection, crossover, and mutation. GAs are particularly effective for NP-Hard problems and situations where traditional methods fail, delivering good-enough solutions quickly.

Uploaded by

manigates1381
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
Genetic Algorithm ™~ hee ee | Introduction * Genetic Algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection. * Itis frequently used to find optimal or near- optimal solutions to difficult problems which otherwise would take a lifetime to solve. * Itis frequently used to solve optimization problems, in research, and in machine learning. Genetic Algorithm Pseudo Code Genetic Algorithm : a Genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection . A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation. INTRODUCTION TO OPTIMIZATION = Optimization is the process of making something better. In any process, we have a set of inputs and a set of outputs as shown in the following figure. Set of Inputs —=—=—=>| Process fm set of outputs * Optimization refers to finding the values of inputs in such a way that we get the best output values. The definition of best varies from problem to problem, but in mathematical terms, it refers to maximizing or minimizing one or more objective functions, by varying the input parameters. + The set of all possible solutions or values which the inputs can take make up the search space. In this search space, lies a point or a set of points which gives the optimal solution. The aim of optimization is to find that point or set of points in the search space. What are Genetic Algorithms? = Nature has always been a great source of inspiration to all mankind. Genetic Algorithms (GAs) are search based algorithms based on the concepts of natural selection and genetics. GAs are a subset of a much larger branch of computation known as Evolutionary Computation. = GAs were developed by John Holland and his students and colleagues at the University of Michigan, most notably David E. Goldberg and has since been tried on various optimization problems with a high degree of success. = In GAs, we have a pool or a population of possible solutions to the given problem. These solutions then undergo recombination and mutation (like in natural genetics), producing new children, and the process is repeated over various generations. Each individual (or candidate solution) is assigned a fitness value (based on its objective function value) and the fitter individuals are given a higher chance to mate and yield more fitter individuals. This is in line with the Darwinian Theory of Survival of the Fittest. = In this way we keep evolving better individuals or solutions over generations, till we reach a stopping criterion. * Genetic Algorithms are sufficiently randomized in nature, but they perform much better than random local search (in which we just try various random solutions, keeping track of the best so far), as they exploit historical information as well. GA MOTIVATION Genetic Algorithms have the ability to deliver a good-enough solution fast-enough. This makes genetic algorithms attractive for use in solving optimization problems. The reasons why GAs are needed are as follows — Y Solving Difficult Problems v Failure of Gradient Based Methods Y Getting a Good Solution Fast Solving Difficult Problems : In computer science, there is a large set of problems, which are NP-Hard. What this essentially means is that, even the most powerful computing systems take a very long time (even years!) to solve that problem. In such a scenario, GAs prove to be an efficient tool to provide usable near-optimal solutions in a short amount of time. Failure of Gradient Based Methods : Traditional calculus-based methods work by starting at a random point and by moving in the direction of the gradient, till we reach the top of the hill. This technique is efficient and works very well for single-peaked objective functions like the cost function in linear regression. But, in most real-world situations, we have a very complex problem called as landscapes, which are made of many peaks and many valleys, which causes such methods to fail, as they suffer from ig figure. an inherent tendency of getting stuck at the local optima as shown in the follo nce Fenton ae Getting a Good Solution Fast : Some difficult problems like the Travelling Salesperson Problem (TSP), have real- world applications like path finding and VLSI Design. Now imagine that you are using your GPS Navigation system, and it takes a few minutes (or even a few hours) to compute the optimal path from the source to destination. Delay in such real world applications is not acceptable and therefore a good-enough solution, which is delivered fast is what is required. GENETIC ALGORITHMS - FUNDAMENTALS This section introduces the basic terminology required to understand GAs. Also, a generic structure of GAs is presented in both pseudo- code and graphical forms. Basic Terminology Before beginning a discussion on Genetic Algorithms, it is essential to be familiar with some basic terminology which will be used throughout this tutorial. Population — A population is a group of individuals or Chromosomes and each individual is a candidate solution to The problem. sIt is a subset of all the possible (encoded) solutions to the given problem. The population for a GA is analogous to the population for human beings except that instead of human beings, we have Candidate Solutions representing human beings. *Chromosomes —A Chromosome is An individual that contains a set of parameters known as Genes (take a look at the figure above). +A chromosome is one such solution to the given problem. “Gene — A Chromosome Contains a list of Parameters , this parameters we call them genes.A gene is one element position of a chromosome. sallele — It is the value a gene takes for a particular chromosome. Initial Random Population (First Generation) Measu: Randomly pick parents, weighted by fitness values (roulette whee!) fon mate? siren by production rossing over genes a from each parent Ocassionally, randomly Mutation ‘mutate one gene Notion of Natural Selection The process of natural selection starts with the selection of fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the fittest individuals will be found. This notion can be applied for a search problem. We consider a set of solutions for a problem and select the set of best ones out of them. Five phases are considered in a genetic algorithm. L Initial population [Link] function [Link] [Link] [Link] Initial Population The process begins with a set of individuals which is called a Population. Each individual is a solution to the problem you want to solve. An individual is characterized by a set of parameters (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution). In a genetic algorithm, the set of genes of an individual is represented using a string, in terms of an alphabet. Usually, binary values are used (string of 1s and 0s). We say that we encode the genes in a chromosome. Gene Chromosome Population Fitness Function The fitness function determines how fit an individual is (the ability of an individual to compete with other individuals). It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score. Selection The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation. Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chance to be selected for reproduction. Crossover Crossover is the most significant phase in a genetic algorithm. For each pair of parents to be mated, a crossover point is chosen at random from within the genes. For example, consider the crossover point to be 3 as shown below. At OoO/O;}O}O0O/;/O0O/0 A2 1 1 1 1 1 1 Crossover point Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached. A1 | O Oo};O;|O/0 TTT A2 1 Exchanging genes among parents The new offspring are added to the population AS [1{/1]|1]|0/0/0 ASB |O/}/0/0/1]1{1 Mutation In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This implies that some of the bits in the bit string can be flipped. Before Mutation AS 1/1/1|O0|0/;0 After Mutation AS 1},17{|0O/1 1|90 Mutation occurs to maintain diversity within the population and prevent premature convergence. Termination The algorithm terminates if the population has converged (does not produce offspring which are significantly different from the previous generation). Then it is said that the genetic algorithm has provided a set of solutions to our problem. Notes: The population has a fixed size. As new generations are formed, individuals with least fitness die, providing space for new offspring. The sequence of phases is repeated to produce individuals in each new generation which are better than the previous generation. Genetic Algorithm START Generate the initial population Compute fitness REPEAT Selection Crossover Mutation Compute fitness UNTIL population has converged STOP Figure 2: Basi structure of Genetic Algorithm 82 Consider the following : (a) Evolution (b) Selection (c) Reproduction (d) Mutation Which of the following are found in genetic algorithms? 1, 2. Bi (0), (¢) and (d) only (0) and (d) only (a), (b), (©) and (d) (a), (b) and (d) only 82 Consider the following : (a) Evolution (b) Selection (c) Reproduction (d) Mutation Which of the following are found in genetic algorithms? 1, 2. Bi (), ©) and @ only (b) and (@) only (a), (b), (©) and (2) (2), (b) and (¢) only [Link] : 5330723780 Arrange the following steps in proper sequence involved in a Genetic Algorithm: (A) Selection (B) Initialization (C) Crossover (D) Mutation (&) Evaluation Choose the correct answer from the options given below: (1) (A), (8), (C), (0), (E) (2) (E), (A), (B), (D), (C) (3) (B), (E), (A), (C), (D) (4) (A), (C), (8), (0), (E) UGC NET AUG- 2024 [Link] : 5330723780 Arrange the following steps in proper sequence involved in a Genetic Algorithm: (A) Selection (B) Initialization (C) Crossover (D) Mutation (E) Evaluation Choose the correct answer from the options given below: (1) (A), (8), (C), (0), (E) (2) (E), (A), (B), (D), (C) (3) (@), (©), (A), (©), (0) (4) (A); (C), (B), (0), (E) UGC NET AUG- 2024 Question ID: 97 Given below are two statements: Statement |: A genetic algorithm is a stochastic hill-climbing search in which a large population of states is maintained Statement II: In nondeterministic environments, agents can apply AND-OR search to generate contingent plans that reach the goal regardless of which outcomes occur during ‘execution. In the light of the above statements, choose the correct answer from the options given below Both Statement | and Statement Il are true Both Statement | and Statement II are false Statement | is correct but Statement Il is false Statement | is incorrect but Statement Il is true gom> UGC NET 2020 Question ID: 97 Given below are two statements: Statement I: A genetic algorithm is a stochastic hill-climbing search in which a large population of states is maintained Statement II: In nondeterministic environments, agents can apply AND-OR search to generate contingent plans that reach the goal regardless of which outcomes occur during execution. In the light of the above statements, choose the correct answer from the options given below A. Both Statement I and Statement Il are true B. Both Statement | and Statement Il are false C. Statement | is correct but Statement Il is false D. Statement | is incorrect but Statement II is true UGC NET 2020 79. For the following Parents in figure (1) and (2) FXG ono = o10 Figure 1 Fc 10101111 Pz 4010 m Figure 2 10101 010 Which is correct? 1) Figure (2) is the two point crossover of figure (1) 2) Figure (2) is one point crossover of figure (1) 3) Figure (2) is N point crossover of figure (1) 4) Figure (2) is uniform crossover of figure (1) UGC NET JUNE - 2024 79. For the following Parents in figure (1) and (2) 10110 010 Figure 1 [cae to101 Pz 4010 m Figure 2 10101 010 Which is correct? 1) Figure (2) is the two point crossover of figure (1) 3) Figure (2) is N point crossover of figure (1) 4) Figure (2) is uniform crossover of figure (1) UGC NET JUNE - 2024 Let the population of chromosomes in genetic algorithm is represented in terms of binary ‘number, The strength of fitness of a chromosome in decimal form, x, is given by Ste ei The population is given by Pwvhere: (110, (1000, (1000, 0000) ce NET Dee 2019 The strength of fitness of chromosome (11000) 1s () 4 () 576 (3) M4 () 492 The population of chromosome in genetic algorithm is represent in term of binary number. The strength of fitness of chromosome in decimal form of x The population is given by P=((01101),(11000),(01000),(10011)} P X -Value f(x)=X42 01101 13 169 11000 24 576 01000 8 64 10011 19 361 Sum 1170 S F(X)= F00/ E F(x) Strength of fitness of chromosome (11000) is where f(x)=x"2 = (11000) / £(01101)+f(11000)+f(01000)+f(10011) = 576/169+576+64+361 =576/1170 =0.492 Let the population of chromosomes in genetic algorithm is represented in terms of binary number. The strength of fitness of a chromosome in decimal form, x, is given by Sfte)=£”herefitye st Sf) The population is given by Pwhere: P= {(01101, (11000), (01000), (10011)} ‘The strength of fitness of chromosome (11000) is (24 (2) 576 @) M4 4 927 UGC NET Dec 2019 ‘The order of schema 2107101? and 2720??1 are and respectively. Q) 53 Q) 52 (3) 15 (4) 87 UGC NET Dec 2019 Aschema is a set of binary strings that match the template which is made up of 1’s , 0's and *s where * matches with either 0 or 1. The order of schema is the number of its fixed bits i.e. number of bits that that are either 0 or 1. Explanation: Given schema is: 2102101? and ??70?771 CASE 1: For ?10?101?, number of bits that are either 0 or 1 are 5. So, order of this schema is 5. CASE 2: For ???0??1, number of bits that are fixed are 2. So, order of schema is 2. The order of schema 2107101? and 720271 are and respectively. (53 Q) 52 3) 1 (4) 87 Question ID : 87827025027 In a genetic algorithm optimization problem the fitness function is defined as f(x)=x? — 4x + 4. Given a population of four individuals with values of X={1.5, 2.0, 3.0, 4.5} What is the fitness value of the individual that will be selected as the parent for reproduction in one generation? 1. 2.25 2. 6.0 3. 0.0 4. 6.25 UGC NET CS 7" December 2023 Question ID : 87827025027 In a genetic algorithm optimization problem the fitness function is defined as f(x)=x? — 4x + 4. Given a population of four individuals with values of X={1.5, 2.0, 3.0, 4.5} What is the fitness value of the individual that will be selected as the parent for reproduction in one generation? 1. 2.25 2. 6.0 3. 0.0 4. 6.25 UGC NET CS 7" December 2023 fony= 2v- 4t Ir fsr= (Ws WIS + 22S - 6442 0725 £22) =(29V— Ha0 Fe HBT =0 (is) = (eoy-4h30 t= TIPE | Las) = (ASH SH 2028 “1B T T OS The true “fitness” of aschema His taken by averaging over all possible values in the “don't care” positions , but this is effectively sampled by the population, giving an estimated fitness f(H, 0). S(H.=> L(x) “mH t) A population of size 400, consists of 123 copies of genome 0001 (with fitness 0.12), 57 copies of genome 1111 (with fitness 0.23), 201 copies of genome 1010 (with fitness 0.56) and 19 copies of genome 0110 (with fitness 0.43). What is the estimated fitness of schema 1 *** ? (A) 0.4870 (B) 0.4880 (C) 0.4877 (D) 0.5870 A population of size 400, consists of 123 copies of genome 0001 (with fitness 0.12), ind 19 copies of genome 0110 (with fitness 0.43). What is the estimated fitness of schema 1 *** ? iB Biba Answer: The estimated fitness of schema 1*** is: (C) 0.4877 A(H, t) = (57*0.23+201*0.56)/(57+201) = 0.4870 (D) 0.5870 O Genotype - Genotype is the population in the computation space. In the computation space, the solutions are represented in a way which can be easily understood and manipulated using a computing system. Phenotype - Phenotype is the population in the actual real world solution space in which solutions are represented in a way they are represented in real world situations. Q Decoding and Encoding - For simple problems, the phenotype and genotype spaces are the same. However, in most of the cases, the phenotype and genotype spaces are different. Decoding is a process of transforming a solution from the genotype to the phenotype space, while encoding is a process of transforming from the phenotype to genotype space. Decoding should be fast as it is carried out repeatedly in a GA during the fitness value calculation. : For example, consider the 0/1 Knapsack Problem. The Phenotype space consists of solutions which just contain the item numbers of the items to be picked. : However, in the genotype space it can be represented as a binary string of length n (where n is the number of items). A 0 at position x represents that xt item is picked while a 1 represents the reverse. This is a case where genotype and phenotype spaces are different. Q Fitness Function - A fitness function simply defined is a function which takes the solution as input and produces the suitability of the solution as the output. In some cases, the fitness function and the objective function may be the same, while in others it might be different based on the problem. QO Genetic Operators - These alter the genetic composition of the offspring. These include crossover, mutation, selection, etc. BASIC STRUCTURE The basic structure of a GA is as follows — We start with an initial population (which may be generated at random or seeded by other heuristics), select parents from this population for mating. Apply crossover and mutation operators on the parents to generate new off-springs. And finally these off- springs replace the existing individuals in the population and the process repeats. In this way genetic algorithms actually try to mimic the human evolution to some extent. Each of the following steps are covered as a separate chapter later in this tutorial Population initialization + Fitness Function Calculation « ve Mutation « Survivor Selection + Terminate and Return A generalized pseudo-code for a GA is explained in the following program — GAC) initialize population find fitness of population while (termination criteria is reached) do parent selection crossover with probability pc mutation with probability pm decode and fitness calculation survivor selection find best return best GENOTYPE REPRESENTATION * One of the most important decisions to make while implementing a genetic algorithm is deciding the representation that we will use to represent our solutions. It has been observed that improper representation can lead to poor performance of the GA. = Therefore, choosing a proper representation, having a proper definition of the mappings between the phenotype and genotype spaces is essential for the success of a GA. GENOTYPE REPRESENTATION The genotype representation can be denoted by the following : > Binary Representation >» Real Valued Representation > Integer Representation > Permutation Representation Binary Representation : = This is one of the simplest and most widely used representation in GAs. In this type of representation the genotype consists of bit strings. For some problems when the solution space consists of Boolean decision variables yes or no, the binary representation is natural. Take for example the 0/1 Knapsack Problem. If there are n items, we can represent a solution by a binary string of n elements, where the x" element tells whether the item x is picked (1) or not (0). Binary Representation .... " For other problems, specifically those dealing with numbers, we can represent the numbers with their binary representation. The problem with this kind of encoding is that different bits have different significance and therefore mutation and crossover operators can have undesired consequences. This can be resolved to some extent by using Gray Coding, as a change in one bit does not have a massive effect on the solution. Real Valued Representation : = For problems where we want to define the genes using continuous rather than discrete variables, the real valued representation is the most natural. = represents a Chromosome as a set of values , for Example we can use this encoding to optimize a neural network , to find the best weights and biases for our network = The precision of these real valued or floating point numbers is however limited to the computer. Integer Representation : = For discrete valued genes, we cannot always limit the solution space to binary yes or no. For example, if we want to encode the four distances North, South, East and West, we can encode them as {0,1,2,3}. In such cases, integer representation is desirable. Permutation Representation / Order Encoding: = Each Chromosome represents a sequence of Elements . = In many problems, the solution is represented by an order of elements. In such cases permutation representation is the most suited. = Aclassic example of this representation is the travelling salesman problem (TSP). In this the salesman has to take a tour of all the cities, visiting each city exactly once and come back to the starting city. The total distance of the tour has to be minimized. The solution to this TSP is naturally an ordering or permutation of all the cities and therefore using a permutation representation makes sense for this problem. ‘Common encoding strategies used in genetic algorithms: Genetic algorithms (GAs) can handle a wide variety of problems by using different encoding strategies to represent candidate solutions. The choice of encoding depends on the problem characteristics, solution representation, and the type of operations performed during the optimization process. Here are some ‘common encoding strategies used in genetic algorithm ‘[Link] Encoding 1. In binary encoding, each candidate solution (individual) is represented as a string of binary digits (0s and 1s). 2. This encoding is suitable for problems where the solution can be represented as a binary string, such as optimization problems with binary decision variables. 3. Operations like crossover and mutation are straightforward to implement with binary encoding. Integer Encoding: 1. In integer encoding, candidate solutions are represented as strings of integers. 2. Each integer in the string represents a decision variable or a component of the solution. 3, Integer encoding is suitable for problems where solutions can be represented by discrete values. 4, Crossover and mutation operations need to be designed carefully to ensure that the resulting solutions remain valid and feasible. [Link]-Valued Encoding: 1. Real-valued encoding represents candidate solutions as vectors of real numbers. 2. This encoding is used for continuous optimization problems where the decision variables can take on any real value within a specified range. 3, Real-valued encoding is flexible and can handle a wide range of optimization problems. 4, Crossover and mutation operations need to preserve the continuity of solutions and respect any constraints on variable ranges. [Link] Encoding: 1. Permutation encoding is used for problems where the order of elements matters, such as scheduling, routing, and sequencing problems. 2. Candidate solutions are represented as permutations of a set of elements. 3. This encoding ensures that each element apoears exactly once in the solution. 4. Crossover and mutation operations for permutation encoding typically involve swapping, insertion, wersion, or other permutation-based operations. [Link] Encoding: 1. Tree encoding represents candidate solutions as hierarchical structures, such as trees or graphs. 2. This encoding is suitable for problems where solutions can be represented as hierarchical structures, such as symbolic regression, expression trees, and program synthesis. 3. Crossover and mutation operations for tree encoding involve subtree crossover and subtree mutation to exchange or modify subtrees within the hierarchical structure. [Link] Encoding: Gray encoding is a variation of binary encoding where consecutive numbers are encoded in such a way that only one bit changes at a time. 2. This encoding can help prevent disruptive changes during mutation and crossover operations, leading to smoother transitions between solutions. These are some of the most common encoding strategies used in genetic algorithms. The choice of encoding depends on the problem domain, the structure of the candidate solutions, and the requirements of the optimization process. Experimentation and domain knowledge are often necessary to determine the most suitable encoding for a given problem. Question ID : 87827025071 Arrange the following encoding strategies used in Genetic Algorithms(GAs) in the correct sequence starting from the initial step and ending with the final representation of solutions: [Link] Encoding [Link] valued Encoding [Link] Encoding [Link] coding Choose the correct answer from the options given below 1. p,B,A,c 2. B,D,A,c 3.¢,D,A,8 4.B,C,A,D UGC NET CS 7** December 2023 Question ID : 87827025071 Arrange the following encoding strategies used in Genetic Algorithms(GAs) in the correct sequence starting from the initial step and ending with the final representation of solutions: A. Binary Encoding [Link] valued Encoding [Link] Encoding [Link] coding Choose the correct answer from the options given below 1. [Link] 2. B,D, A, Cc UGC NET CS 7** December 2023 Various types of Encoding Techniques at a glance [Link] Encoding: 1, It is placed at the initial step because permutation encoding is often used when the problem involves a permutation of elements, such as scheduling or routing problems. The initial representation of solutions might be best suited for permutation encoding if the problem naturally involves the order of elements. [Link] Coding: 1. It is placed in the intermediate step. Gray coding can be applied as a variation of binary encoding, especially if a smooth transition between solutions is desired during mutation and crossover operations. It's typically used after permutation encoding because the problem domain might require specific orderings that are better handled by permutation encoding first. [Link] Encoding: 1. It is placed in the third position, suggesting that after initial permutation encoding and any intermediate Gray coding, the solution representation might be transformed into binary encoding. This could be the case if subsequent genetic operations (such as crossover and mutation) are best applied with binary encoding. Valued Encoding: 1. It is placed at the end, suggesting that after any necessary transformations from binary encoding, the final representation of solutions might be in real-valued encoding. This could be the case if the problem involves continuous optimization where decision variables can take on any real value within a specified range. So, the given sequence suggests a progression from initial representation tailored to the problem's permutation nature, to a potential intermediate transformation for smoother genetic operations, followed by binary encoding for genetic operations, and finally real-valued encoding for the final representation of solutions in continuous optimization problems. GENETIC ALGORITHMS - POPULATION Population is a subset of solutions in the current generation. It can also be defined as a set of chromosomes. There are several things to be kept in mind when dealing with GA population — + The diversity of the population should be maintained otherwise it might lead to premature convergence. The population size should not be kept very large as it can cause a GA to slow down, while a smaller population might not be enough for a good mating pool. Therefore, an optimal population size needs to be decided by trial and error. The population is usually defined as a two dimensional array of size population, size x, chromosome size. Population Initialization : There are two primary methods to initialize a population in a GA. They are - = Random Ini solutions. = Heuristic initialization — Populate the initial population using a known heuristic for the problem. lization - Populate the initial population with completely random It has been observed that the entire population should not be initialized using a heuristic, as it can result in the population having similar solutions and very little diversity. It has been experimentally observed that the random solutions are the ones to drive the population to optimality. Therefore, with heuristic initialization, we just seed the population with a couple of good solutions, filling up the rest with random solutions rather than filling the entire population with heuristic based solutions. It has also been observed that heuristic initialization in some cases, only effects the initial fitness of the population, but in the end, it is the diversity of the solutions which lead to optimality. Population Models : There are two population models widely in use — Steady State In steady state GA, we generate one or two off-springs in each iteration and they replace one or two individuals from the population. A steady state GA is also known as Incremental GA. Generational In a generational model, we generate n off-springs, where n is the population size, and the entire population is replaced by the new one at the end of the iteration. Genetic Algorithms - Fitness Function Q The fitness function simply defined is a function which takes a candidate solution to the problem as input and produces as output how fit our how good the solution is with respect to the problem in consideration. Q Calculation of fitness value is done repeatedly in a GA and therefore it should be sufficiently fast. A slow computation of the fitness value can adversely affect a GA and make it exceptionally slow. Q In most cases the fitness function and the objective function are the same as the objective is to either maximize or minimize the given objective function. However, for more complex problems with multiple objectives and constraints, an Algorithm Designer might choose to have a different fitness function. = A fitness function should possess the following characteristics - = The fitness function should be sufficiently fast to compute. Q It must quantitatively measure how fit a given solution is or how fit individuals can be produced from the given solution. Q In some cases, calculating the fitness function directly might not be possible due to the inherent complexities of the problem at hand. In such cases, we do fitness approximation to suit our needs. Q The following image shows the fitness calculation for a solution of the 0/1 Knapsack. It is a simple fitness function which just sums the profit values of the items being picked (which have a 1), scanning the elements from left to right till the knapsack is full. 0j1/2|3|4/5/6 Item Number (2 [2 [8 [5 [4 Jo [2] Profit values PiEBEIsI[2[s] Weight Values Knapsack capacity = 15 Total associated profit = 18 Last item not picked as it exceeds knapsack capacity Genetic Algorithms - Parent Selection + Selection is the process of selecting parents to generate the Child we call it also offspring that will be a part of the next generation , There are several selection methods among the most used we have + Parent Selection is the process of selecting parents which mate and recombine to create off-springs for the next generation. Parent selection is very crucial to the convergence rate of the GA as good parents drive individuals to a better and fitter solutions. = However, care should be taken to prevent one extremely fit solution from taking over the entire population in a few aenerations, as this leads to the solutions being close to one another in the solution space thereby leading to a loss of diversity. Maintaining good diversity in the population is extremely crucial for the success of a GA. This taking up of the entire population by one extremely fit solution is known as premature convergence and is an undesirable condition in a GA. Fitness Proportionate Selection Fitness Proportionate Selection is one of the most popular ways of parent selection. In this every individual can become a parent with a probability which is proportional to its fitness. Therefore, fitter individuals have a higher chance of mating and propagating their features to the next generation. Therefore, such a selection strategy applies a selection pressure to the more fit individuals in the population, evolving better individuals over time. Consider a circular wheel. The wheel is divided into n pies, where n is the number of individuals in the population. Each individual gets a portion of the circle which is proportional to its fitness value. +Elitism Selection : Elitism Selection Consists of Selecting Top K chromosomes to pass them To The Next Generation without making any any changes to them . +Roulette Wheel Selection : each parent is represented in The wheel with a portion depends on his Fitness Value , The Parent with the Best Fitness Value have the best chance to be selected . Som oven ‘jad > f Roulette Wheel Selection : QQ In a roulette wheel selection, the circular wheel is divided as described before. A fixed point is chosen on the wheel circumference as shown and the wheel is rotated, The region of the wheel which comes in front of the fixed point is chosen as the parent. For the second parent, the same process is repeated. Foes [eremesone (ys a] 0 6 | 32 ca oar tw Fos Spin the roulette Qt is clear that a fitter individual has a greater pie on the wheel and therefore a greater chance of landing in front of the fixed point when the wheel is rotated. Therefore, the probability of choosing an individual depends directly on its fitness. Implementation wise, we use the following steps - + Calculate S = the sum of a finesses. + Generate a random number between 0 and S. + Starting from the top of the population, keep adding the finesses to the partial sum P, till P Stochastic Universal Sampling (SUS) : Q Stochastic Universal Sampling is quite similar to Roulette wheel selection, however instead of having just one fixed point, we have multiple fixed points as shown in the following image. Therefore, all the parents are chosen in just one spin of the wheel. Also, such a setup encourages the highly fit individuals to be chosen at least once. foomosome] FEN Value 3 [32 Fined Point Fued point [ei [az ee F—[03 Spin sign SE ca It is to be noted that fitness proportionate selection methods don't work for cases where the fitness can take a negative value. “Tournament Selection : The First Thing We do is we choose a Number k that represents The Tournament Pool Size , then We select K individuals from The Current Population and we put Them into the Pool , After This we Choose The Best Individual from our Poo! (The Individual that have the best Fitness Value ) [aaa fs a sce on [ae 2 jee a — [ “a a 8 [oe oe I 109 e Tournament Pool of ‘sek Tournament Selection In K-Way tournament selection, we select K individuals from the population at random and select the best out of these to become a parent. The same process is repeated for selecting the next parent. Tournament Selection is also extremely popular in literature as it can even work with negative fitness values. eke tot parent Rank Selection : Rank Selection also works with negative fitness values and is mostly used when the individuals in the population have very close fitness values (this happens usually at the end of the run). + This leads to each individual having an almost equal share of the pie (like in case of fitness proportionate selection) as shown in the following image and hence each individual no matter how fit relative to each other has an approximately same probability of getting selected as a parent. + This in turn leads to a loss in the selection pressure towards fitter individuals, making the GA to make poor parent selections in such situations. seed ater + In this, we remove the concept of a fitness value while selecting a parent. However, every individual in the population is ranked according to their fitness. The selection of the parents depends on the rank of each individual and not the fitness. The higher ranked individuals are preferred more than the lower ranked ones. Chromosome Fitness Value Rank A 81 1 8 8.0 4 c 8.05 2 > 7.95 6 E 8.02 3 F 7.99 5 Random Selection In this strategy we randomly select parents from the existing population. There is no selection pressure towards fitter individuals and therefore this strategy is usually avoided. Here are some well-known parent selection methods used in evolutionary algorithms (EAs) or genetic algorithms (GAs): 1. Roulette Wheel Selection (Fitness Proportionate Selection) +How it works: Individuals are selected based on their fitness proportion relative to the population. A “roulette wheel” is simulated, where each slice corresponds to an individual, with sizes proportional to their fitness. “Use case: Works well when fitness values are significantly different. -Drawback: Can struggle when fitness values are very similar (low selective pressure). 2. Tournament Selection +How it works: A random subset of individuals is chosen, and the one with the highest fitness within the subset is selected. This process is repeated to choose multiple parents. “Use case: Simple and efficient; allows control of selection pressure via the tournament size. -Drawback: If the tournament size is too small, selection may be too random; if too large, it can lead to premature convergence. 3. Rank Selection +How it works: Individuals are ranked based on their fitness. Selection probabilities are assigned based on rank rather than raw fitness. +Use case: Avoids issues with fitness proportionate selection when there are large differences in fitness. -Drawback: Computationally expensive for large populations due to ranking, 4. Steady State Selection -How it works: A few individuals are replaced in each generation instead of replacing the entire population. Parents are selected based on fitness, and offspring replace less fit individuals. “Use case: Maintains diversity and avoids drastic changes between generations. -Drawback: Slower convergence compared to generational replacement methods. 5. Boltzmann Selection -How it works: Uses a temperature parameter (as in simulated annealing) to control the selection pressure. At high temperatures, selection is more random, and at low temperatures, it becomes fitness-driven. “Use case: Useful when gradual intensification of selection pressure is needed, -Drawback: Requires tuning the temperature parameter. 6, Stochastic Universal Sampling (SUS) +How it works: A single roulette wheel is spun with multiple equally spaced pointers to select multiple individuals in one step. “Use case: Provides a more stable and less biased selection compared to simple roulette wheel selection. -Drawback: Slightly more complex to implement than basic roulette wheel selection. 7. Truncation Selection -How it works: Selects a fixed percentage of the top individuals (e.g., the top 50% based on fitness) -Use case: Ensures strong selection pressure and simplicity. -Drawback: Risks losing diversity and premature convergence. 8. Random Selection -How it works: Parents are chosen randomly, without considering fitness. “Use case: Typically used as a baseline for comparison or to maintain diversity. +Drawback: Does not favor fitter individuals, leading to slow convergence. 9. Fitness Threshold Selection How it works: Only individuals whose fitness exceeds a certain threshold are considered for selection, “Use case: Focuses on high-performing individuals. -Drawback: Can lead to a loss of diversity if the threshold is too restrictive. 10. Linear Ranking Selection +How it works: Assigns selection probabilities linearly based on rank. Higher-ranked individuals have proportionally higher probabilities of selection. “Use case: Avoids extreme bias toward the best individual, which can occur in fitness proportionate methods. “Drawback: Still computationally expensive for large populations. 19. Which one of the following is not a specified method that is used for the selection of parents? (1) Steady state selection (2) Tournament selection (3) Boltzmann selection (4) Elitism KSET-NOV- 2024 19. Which one of the following is not a specified method that is used for the selection of parents? (1) Steady state selection (2) Tournament selection (3) Boltzmann selection -Tournament selection, Boltzmann selection, and Steady state selection are commonly used parent selection methods in genetic algorithms. +Elitism, however, is not a parent selection method — it is a replacement strategy used to preserve the best individuals from one generation to the next. It ensures that the best solutions are carried over without being lost due to stochastic selection KSET-NOV- 2024 GENETIC ALGORITHMS - CROSSOVER Introduction to Crossover : The crossing operation is the Process of reproduction of new chromosomes from the parent chromosomes (parents are selected from the old population Using A Selection Method ) , There are several crossing methods among the most used we have : The crossover operator is analogous to reproduction and biological crossover. In this more than one parent is selected and one or more off-springs are produced using the genetic material of the parents. Crossover is usually applied in a GA with a high probability p, . > One Point Crossover : a random Point is chosen to be The CrossOver Point , then we fill the child with genes from both parents .In this one-point crossover, a random crossover point is selected and the tails of its two parents are swapped to get new off-springs. == a EXAMPLE 1 EXAMPLE 2: Cross point > Multi Point Crossover *a random two Points are chosen to be The Cross Over Points , then we fill the child with genes from both parents . Multi point crossover is a generalization of the one-point crossover wherein alternating segments are swapped to get new off-springs. EXAMPLE 1: => EXAMPLE 2: 5 > Uniform Crossover : In a uniform crossover, we don't divide the chromosome into segments, rather we treat each gene separately. In this, we essentially flip a coin for each chromosome to decide whether or not it will be included in the off-spring. We can also bias the coin to one parent, to have more genetic material in the child from that parent. we flip a coin for each genes in our two parents to decide whether or not it'll be included in the off- spring (Child ). Example 1 vers [2] alafalaisi716 Example 2 EEREEEEREE = BEEBE Uniform crossover + Arandom subset is chosen + The subset is taken from parent 1 and the other bits from parent 2. Subset: BAABBAABBB (Randomly generated) Parents: 1010001110 0011010010 Offspring: 0011001010 1010010110 » Davis Order Crossover (OX1) : OX1 is used for permutation based crossovers with the intention of transmitting information about relative ordering to the off-springs. It works as follows — + Create two random crossover points in the parent and copy the segment between them from the first parent to the first offspring. + Now, starting from the second crossover point in the second parent, copy the remaining unused numbers from the second parent to the first child, wrapping around the list. + Repeat for the second child with the parents role reversed. Davis Order Crossover (OX1) :we Choose two random crossover points in the first parent and we copy that segment into the Child , then we fill the rest of genes in our child with the genes from the second Parent . { 21411[81315 71/6 | — G1 oftpring or chia > PRDBEEED] Repeat the same pracedure to get the second child There exist a lot of other crossovers like Partially Mapped Crossover (PMX), Order based crossover (OX2), Shuffle Crossover, Ring Crossover, etc. Whole Arithmetic Recombination : we use this two formula to forms our two children .. Child Child2 = uxt (Lea)y uxt (-a)y Then we Choose The Best Child (The Child with The Best Fitness Value ). Poros: | 274111813151716 6148151813/4.213]2_ — mor aistelaraiaiais | | stazivaiatstasteis ottspring Crossover Points ze his Genetic Algorithms - Mutation Introduction to Mutation : In simple terms, mutation may be defined as a small random tweak in the chromosome, to get a new solution. It is used to maintain and introduce diversity in the genetic population and is usually applied with a low probability p,,. If the probability is very high, the GA gets reduced to a random search. Mutation is the part of the GA which is related to the exploration of the search space. It has been observed that mutation is essential to the convergence of the GA while crossover is not. Mutation Operators : In this section, we describe some of the most commonly used mutation operators. Like the crossover operators, this is not an exhaustive list and the GA designer might find a combination of these approaches or a problem-specific mutation operator more useful. Bit Flip Mutation : In this bit flip mutation, we select one or more random bits and flip them. This is used for binary encoded GAs. ep > IEE Random Resettin; Random Resetting is an extension of the bit flip for the integer representation. In this, a random value from the set of permissible values is assigned to a randomly chosen gene. Swap Mutation : In swap mutation, we select two positions on the chromosome at random, and interchange the values. This is common in permutation based encodings. ME > LEER Scramble Mutation : Scramble mutation is also popular with permutation representations. In this, from the entire chromosome, a subset of genes is chosen and their values are scrambled or shuffled randomly. TTS] > FEDERE Inversion Mutation : In inversion mutation, we select a subset of genes like in scramble mutation, but 8/9 instead of shuffling the subset, we merely invert the entire string in the subset. fs a3 ]e]5 fe] |2]9 o/s fe] |e )ay2]7|e]9 various types of mutation operators at a glance In genetic algorithms, various types of mutation operators can be employed, each tailored to the specific characteristics of the problem being solved and the encoding scheme used for representing individuals. Here are some common types of mutation operators: [Link] Flip Mutation: This is typically used with binary encoding. In bit flip mutation, randomly selected bits in the chromosome are flipped, changing 0s to 1s and vice versa. This simple mutation operator introduces small changes to the chromosome. [Link] Mutation: Swap mutation is commonly used with permutation encoding, where the chromosome represents a permutation of elements. In swap mutation, two randomly selected positions in the chromosome are swapped. This operation can help in exploring different permutations of elements. [Link] Mutation: Scramble mutation is also used with permutation encoding. In this mutation operator. a subset of genes (or elements) within the chromosome is randomly selected and then shuffled. This shuffling introduces randomness and can lead to exploration of new regions in the search space. 4,nsertion Mutation: Insertion mutation is applicable to permutation encoding. In this mutation operator, a randomly selected gene is removed from its current position and reinserted at a different randomly chosen position within the chromosome. This operation can help in exploring different insertion points. [Link] Mutation: Inversion mutation is another mutation operator commonly used with permutation encoding. In this mutation, 2 subset of genes within the chromosome is selected, and the order of genes in that subset is reversed. This operation can lead to exploration of neighboring solutions. [Link]-Uniform Mutation: Non-uniform mutation adjusts the mutation rate dynamically based on the progress of the genetic algorithm. Initially, the mutation rate might be high to encourage exploration, but as the algorithm progresses, the mutation rate decreases to allow exploitation of promising regions. [Link] Mutation: Gaussian mutation is often used with real-valued encoding. In this mutation operator, a small random value drawn from a Gaussian distribution is added to each gene in the chromosome. This mutation introduces small continuous changes to the chromosome. Question ID : 87088 Which of the following is not a mutation operator in a genetic algorithm? A. Random resetting B. Scramble C. Inversion D. Difference Choose the correct answer from options given below: 4. Aand B only 2. Band D only 3. Cand D only aces UGC NET CS 17% June 2023 Question ID : 87088 Which of the following is not a mutation operator in a genetic algorithm? A. Random resetting B. Scramble C. Inversion D. Difference Choose the correct answer from options given below: A and B only B and D only C and D only D only pepe UGC NET CS 17% June 2023 GENETIC ALGORITHMS - SURVIVOR SELECTION + Selection is the process of selecting parents to generate the Child we call it also offspring that will be a part of the next generation , There are several selection methods among the most used we have : + The Survivor Selection Policy determines which individuals are to be kicked out and which are to be kept in the next generation. It is crucial as it should ensure that the fitter individuals are not kicked out of the population, while at the same time diversity should be maintained in the population. * Some GAs employ Elitism. In simple terms, it means the current fittest member of the population is always propagated to the next generation. Therefore, under no circumstance can the fittest member of the current population be replaced, + The easiest policy is to kick random members out of the population, but such an approach frequently has convergence issues, therefore the following strategies are widely used. Age Based Selection : "In Age-Based Selection, we dont have a notion of a fitness. It is based on the premise that each individual is allowed in the population for a finite generation where it is allowed to reproduce, after that, it is kicked out of the population no matter how good its fitness is. * For instance, in the following example, the age is the number of generations for which the individual has been in the population. The oldest members of the population i.e. P4 and P7 are kicked out of the population and the ages of the rest of the members are incremented by one. Fitness Based Selection : = In this fitness based selection, the children tend to replace the least fit individuals in the population. The selection of the least fit individuals may be done using a variation of any of the selection policies described before tournament selection, fitness proportionate selection, etc. = For example, in the following image, the children replace the least fit individuals P1 and P10 of the population. It is to be noted that since P1 and P9 have the same fitness value, the decision to remove which individual from the population is arbitrary. Genetic Algorithms - Termination Condition The termination condition of a Genetic Algorithm is important in determining when a GA run will end. It has been observed that initially, the GA progresses very fast with better solutions coming in every few iterations, but this tends to saturate in the later stages where the improvements are very small. We usually want a termination condition such that our solution is close to the optimal, at the end of the run. Usually, we keep one of the following termination conditions — + When there has been no improvement in the population for x iterations. + When we reach an absolute number of generations. + When the objective function value has reached a certain pre-defined value. * For example, in a genetic algorithm we keep a counter which keeps track of the generations for which there has been no improvement in the population. Initially, we set this counter to zero. Each time we dont generate off-springs which are better than the individuals in the population, we increment the counter. + However, if the fitness any of the off-springs is better, then we reset the counter to zero. The algorithm terminates when the counter reaches a predetermined value. = Like other parameters of a GA, the termination condition is also highly problem specific and the GA designer should try out various options to see what suits his particular problem the best. Termination Criteria : The Reproduction process is repeated until a termination condition has been reached , common terminating conditions are . *A solution is found that satisfies minimum criteria . +Fixed number of generations reached . Allocated budget (computation time/money) reached . -Manual inspection . +Combinations of the above . ADVANTAGES OF GAs GAs have various advantages which have made them immensely popular. These include : a. Does not require any derivative information (which may not be available for many real-world problems). Is faster and more efficient as compared to the traditional methods. Has very good parallel capabilities. Optimizes both continuous and discrete functions and also multi-objective problems. Provides a list of good solutions and not just a single solution. Always gets an answer to the problem, which gets better over the time. Useful when the search space is very large and there are a large number of parameters involved. LIMITATIONS OF GAs Like any technique, GAs also suffer from a few limitations. These include - a. GAs are not suited for all problems, especially problems which are simple and for which derivative information is available. b. Fitness value is calculated repeatedly which might be computationally expensive for some problems. c. Being stochastic, there are no guarantees on the optimality or the quality of the solution. d. If not implemented properly, the GA may not converge to the optimal solution. Genetic Algorithms - Application Areas Genetic Algorithms are primarily used in optimization problems of various kinds, but they are frequently used in other application areas as well. + Optimization - Genetic Algorithms are most commonly used in optimization problems wherein we have to maximize or minimize a given objective function value under a given set of constraints. The approach to solve Optimization problems has been highlighted throughout the tutorial. + Economies - GAs are also used to characterize various economic models like the cobweb model, game theory equilibrium resolution, asset pricing, etc. + Neural Networks - GAs are also used to train neural networks, particularly recurrent neural networks. + Parallelization - GAs also have very good parallel capabilities, and prove to be very effective means in solving certain problems, and also provide a good area for research. + Image Processing - GAs are used for various digital image processing (DIP) tasks as well like dense pixel matching. + Vehicle routing problems - With multiple soft time windows, multiple depots and a heterogeneous fleet. + Scheduling applications ~ GAs are used to solve various scheduling problems as well, particularly the time tabling problem. +Machine Learning - as already discussed, genetics based machine learning (GBML) is a niche area in machine learning. + Robot Trajectory Generation - GAs have been used to plan the path which a robot arm takes by moving from one point to another. + Parametric Design of Aircraft - GAs have been used to design aircrafts by varying the parameters and evolving better solutions. + DNA Analysis - GAs have been used to determine the structure of DNA using spectrometric data about the sample. + Multimodal Optimization - GAs are obviously very good approaches for multimodal optimization in which we have to find multiple optimum solutions. + Traveling salesman problem and its applications - GAs have been used to solve the TSP, which is a well-known combinatorial problem using novel crossover and packing strategies.

You might also like