One Pager Cheat Sheet

• A Genetic Algorithm (GA) is a **nature-inspired** algorithm used to solve **optimization problems**, belonging to the branch of **approximation algorithms**, which will be learned in this lesson in terms of its source of inspiration, general structure, working, and implementation.
• Optimization is the process of finding the best solution to a problem by formulating it mathematically and then using an optimization algorithm such as GA to minimize/maximize the output of a function to reach the optimal solution.
• We can use an optimization algorithm such as GA to find the optimal solution of the function $f(x_1,x_2)=x_1^2+x_2^2$.
• The process of natural selection is used as an inspiration for Genetic Algorithm (GA), which generates a population of candidate solutions randomly and selects the fittest individuals to produce similar solutions and ensure the survival of better solutions' traits over time.
• GA is a population-based algorithm, where a set of candidate solutions (chromosomes) are evaluated against an objective function (fitness function) to find the optimal solution.
• Genetic Algorithm mimics the process of natural selection with the use of genetic operators, such as crossover, mutation, and selection to generate a population of random solutions which undergo fitness evaluation to arrive at the best solution.
• A solution is typically encoded as a binary string, integer-valued array, floating-point array, or a permutation of a fixed set of elements, depending upon the nature of the problem.
• The population is randomly generated with continuous variables in the range of [-5, 5] in order to begin any Genetic Algorithm (GA) or other Evolutionary Algorithm.
• The fitness of each of the randomly generated chromosomes in the population is calculated and depicted in the figure.
• The crossover operator is used to produce new solutions from existing ones in the Genetic Algorithm, and a suitable selection method is necessary to determine the parents for the crossover, with two popular methods discussed in the literature.
• Selecting the k best solutions from the matting pool is the simplest method for progressing to the next phase of crossover.
• Fitness Proportionate Selection is a method of selecting a solution to crossover such that each solution is assigned a probability of selection based on its fitness.
• The accumulated probability distribution for this population is calculated by summing the fitness of each solution into the sum of fitness of all previous solutions.
• The crossover operator mimics the sexual reproduction of natural selection and exchanges genetic information between two parents to create new offspring, with various methods discussed in the literature.
• One-point crossover randomly chooses one crossover point and creates two children using the first half of one parent and the second half of the other parent.
• Multipoint crossover creates offspring by selecting alternative portions from both parents at multiple crossover points.
• In uniform crossover, each gene for an offspring is chosen with equal probability from both Parents, resulting in the exchanged gene positions in the resulting offspring.
• Mutation is a biological operator that introduces new traits in genetic information and helps maintain diversity to prevent populations from converging prematurely.
• Flip mutation is a type of mutation used with binary crossover, in which a randomly selected bit of the chromosome is flipped.
• Swap mutation is a kind of mutation where two randomly selected genes have their alleles swapped.
• Random initialization is used to re-initialize the discrete values/integers of a gene with a random value from a given range.
• Selection methods are used to decide which solutions will continue into the next generation, such as random selection and proportionate selection which gives better solutions a higher chance of surviving, or merging parents and new offspring, which gives the new generation a mix of both.
• The algorithm terminates when a predefined number of iterations, fitness value, or lack of improvement has been achieved.
• Using the mathematical function $f(x_1,x_2)=x_1^2+x_2^2$, Genetic Algorithm (GA) was implemented in Python to optimize the function.
• The population can be randomly initialized using numpy's function for creating random vectors/arrays.
• An example of the random population is printed below where rows show the chromosomes and columns show the genes.
• The overall fitness of the population is determined by summing up the individual fitness scores.
• Making a matting pool of the best solutions according to the mattingPoolSize variable is essential for successful crossover.
• Crossover is used to generate a predefined number of offspring from selected parents, implementing a single-point method to assign each parent's genes to the corresponding offspring.
• Mutation, with random initialization, is used to randomly initialize each offspring's allele to any continuous value.
• Natural selection occurs through environmental selection, in which weak chromosomes are replaced with new offspring from the previous generation.
• The algorithm of the fitness calculations and environmental selection will be repeated in a loop a total of generations iterations.
• By understanding the source of inspiration behind and the operations used in Genetic Algorithms, readers should be able to implement and solve optimization problems with GA in Python.