Genetic Algorithm: Fundamentals and Applications

By Fouad Sabry

What Is Genetic Algorithm

In the fields of computer science and operations research, a genetic algorithm (GA) is a metaheuristic that is modeled after the process of natural selection and is a subcategory of evolutionary algorithms (EA), which are a broader category. By relying on biologically inspired operators like mutation, crossover, and selection, genetic algorithms are often employed to develop high-quality solutions to optimization and search problems. This is accomplished through the use of genetic programming. Applications of GA include, but are not limited to, improving the efficiency of decision trees through optimization, deciphering sudoku puzzles, optimizing hyperparameters, drawing causal inferences, and other similar tasks.

How You Will Benefit

(I) Insights, and validations about the following topics:

Chapter 1: Genetic algorithm

Chapter 2: Genetic programming

Chapter 3: Particle filter

Chapter 4: Schema (genetic algorithms)

Chapter 5: Universal Darwinism

Chapter 6: Metaheuristic

Chapter 7: Learning classifier system

Chapter 8: Rule-based machine learning

Chapter 9: Genetic representation

Chapter 10: Fitness function

(II) Answering the public top questions about genetic algorithm.

(III) Real world examples for the usage of genetic algorithm in many fields.

(IV) 17 appendices to explain, briefly, 266 emerging technologies in each industry to have 360-degree full understanding of genetic algorithm' technologies.

Who This Book Is For

Professionals, undergraduate and graduate students, enthusiasts, hobbyists, and those who want to go beyond basic knowledge or information for any kind of genetic algorithm.

• Language: English
• Publisher: One Billion Knowledgeable
• Release date: Jul 1, 2023

Book preview

Chapter 1: Genetic algorithm

The term genetic algorithm (GA) refers to a metaheuristic that was developed in the fields of computer science and operations research. This metaheuristic was inspired by the process of natural selection, and it is a member of the wider class of evolutionary algorithms (EA). By relying on biologically inspired operators like mutation, crossover, and selection, genetic algorithms are often employed to develop high-quality solutions to optimization and search problems. This is accomplished via the use of genetic programming. optimization of hyperparameters, and so on.

A population of candidate solutions (which may be referred to as people, animals, organisms, or phenotypes) to an optimization problem may be developed using a genetic algorithm in the direction of producing superior answers. Each potential solution has a set of characteristics, also known as its chromosomes or genotype, which are susceptible to mutation and change. Traditionally, solutions are encoded in binary as strings of 0s and 1s, although there are other alternative encodings as well.

The process of evolution often begins with a population of people who have been created at random. Evolution is an iterative process, and the population that exists at the end of each iteration is referred to as a generation. At each generation, every person in the population is analyzed to determine their level of fitness; this level of fitness is often represented by the value of the objective function in the optimization problem that is being solved. To create a new generation, the genomes of existing people are recombined and maybe subjected to random mutations before being chosen at random from the present population to determine which individuals have the most potential for improvement. The newly generated pool of potential answers is thereafter put to use in the subsequent iteration of the process. In most cases, the algorithm comes to an end when one of two conditions is met: either a predetermined maximum number of generations has been created, or a population fitness level that is deemed adequate has been achieved.

The requirements of a typical genetic algorithm are as follows::

an illustration of the solution space based on genetics, a fitness function that may be used to analyze the solution domain.

Each potential answer is often represented as a collection of bits, according to the standard (also called bit set or bit string). Arrays of various types and structures may be used in a manner that is substantially equivalent to how arrays of the type arrays are used. Because of their consistent sizes, the components of these genetic representations are easy to align, which paves the way for straightforward crossover procedures. This is the primary quality that contributes to the convenience offered by these representations of genetic material. It is also possible to employ representations of variable length, albeit the implementation of crossover in this scenario would be more difficult. In genetic programming, we investigate representations in the form of trees, while in evolutionary programming, we investigate representations in the form of graphs. In gene expression programming, we investigate a combination of linear chromosomes and tree-like structures.

After the genetic representation and the fitness function have been specified, a GA will continue to establish a population of solutions and then proceed to enhance it via the repeated application of the mutation, crossover, inversion, and selection operators.

The size of the population is determined by the characteristics of the issue, although it often ranges from several hundred to several thousand different potential solutions. In many cases, the starting population is produced in a random fashion, which makes it feasible to consider every conceivable option (the search space). Sometimes the solutions will be seeded in places where they are most likely to find optimum answers.

A subset of the current population is chosen at the beginning of each succeeding generation in order to serve as the foundation for the next generation. A fitness-based procedure is used to pick individual solutions; in this process, solutions that are more physically fit (as determined by a fitness function) have a greater chance of being chosen. The viability of each potential solution is evaluated by certain selection processes, which then give preference to the most viable options. Because the first technique may take a significant amount of time, the second approaches only rate a representative sample of the population.

The quality of the solution that is represented genetically is evaluated using the fitness function, which is specified over the genetic representation. Always reliant on the task at hand is the fitness function. For example, in the knapsack problem, one desires to maximize the total worth of goods that can be placed into a knapsack of some specific capacity. This may be accomplished by putting as many valuable items as possible into the knapsack. It's possible that an array of bits may be used to represent a solution to a problem. If so, each bit would stand for a separate item, and the value of the bit (either 0 or 1) would indicate whether or not the item was included in the knapsack. The size of the items may be more than the capacity of the knapsack, which means that not every such depiction is legitimate. If the representation is correct, the fitness of the solution is equal to the total of the values of all of the items in the knapsack; otherwise, it is equal to 0.

There are some problems in which it is difficult or even impossible to define the fitness expression; in these situations, a simulation may be used to determine the fitness function value of a phenotype (for instance, computational fluid dynamics may be used to determine the air resistance of a vehicle whose shape is encoded as the phenotype), or even interactive genetic algorithms may be used.

The next stage is to build a second generation population of solutions based on those that were chosen, using a variety of genetic operators, including crossover (which is also known as recombination) and mutation.

From the pool of solutions that were chosen in the previous step, a set of parent solutions is bred to generate a new solution at each iteration of the process. By using the previously described strategies of crossover and mutation, it is possible to generate a new solution that, in most cases, takes on many of the qualities of its parents. This new solution is referred to as a child solution. The procedure continues until a new population of solutions with the necessary size is produced, at which point