Genetic algorithms use Darwin’s theory of evolution to optimize. Darwin’s theory of natural selection proposes that the most adapted population members will survive and reproduce, leading to an even more adapted next generation. Crossing and mutation change the structure of chromosomes, which store genetic information. Adaptation in Natural and Artificial Systems, published in 1975, is considered the first genetic algorithm book. Holland invented crossover and recombination operators. This presented adaptive digital systems using mutation, selection, and crossover to solve problems systematically and rigorously. It was built on earlier research and papers by Holland and his University of Michigan colleagues. It is widely used in optimization-related contexts. This research paper discusses the genetic algorithm principle, its advantages and disadvantage, and its real-life applications.
Genetic Algorithm (GA) Principle
The GA (genetic algorithm) is a Darwinian-inspired evolutionary algorithm created by Holland. It combines survival of the fittest with structured chance information exchange. When no solution is known, random solutions are generated. The initial population is this set. The traits are then incorporated into gene sequences that form chromosomes and individuals. Each key corresponds to a person, who is then ranked by how closely they resemble the best. This approach will converge to an ideal outcome via Darwinian natural selection. Like constrained biological systems, the best population members reproduce and pass on their genes to the next generation. Combining the original individuals’ genes creates a new population (parents).
Some people of the new generation may have the best attributes of both parents, making them the best solution. The next generation has children using the same criteria. After this, everyone will have the same genetic makeup. Recent generations are distinct from their ancestors because their genetic information matches the best option. The figure below shows the procedure of the genetic algorithm.
Presentation
Every genetic algorithm component has a dual representation: a presentation of genotype and phenotype. Genotype is how the population is displayed in the computational environment. In comprehending and manipulating a person, a digital instrument must be encoded or represented in binary, integer, or another complicated form. Phenotype, on the other hand, represents the population in the search space corresponding to reality or a representation of the solutions through corresponding absolute values.
Encoding each parameter as a series of bits is the conventional way of transforming a genetic algorithm with several parameters, from phenotypic presentation to genotype presentation. This conversion process takes place when moving from phenotype presentation to genotype presentation. After that, the sequences are joined into a single, extensive sequence called the chromosome. This sequence acts as a representation of the vector that the parameters belong. Therefore, the sequences on the vector represent genes, and each gene’s value
Evaluation of Individual
Evaluation is required to assist in applying for the role that (natural) selection plays in evolution. Each person in a population is assigned a value that helps them distinguish themselves from the other people in the population. This value is referred to as fitness, which determines if the solution represented by the individual is viable or optimal. It is the one that is calculated by the objective function. It is computed using the values that each individual possesses for their parameters. As a result, the accurate function shifts from problem to the problem due to its variability. It also differs depending on whether one wants to maximize or lessen the severity of a situation. As a result, this can determine an objective function value for each individual in the population.
Population
The characteristics of a population include its size, the number of individuals who composes it, its dimension, the number of individual genes, and how they may interact with one another through mating and the production of progeny. Throughout evolution, the size hardly ever changes. It can be as small as one or as large as several thousand. On the other hand, population diversity is measured by the variety of people who make up the group.
Selection Mechanism
Several factors, including internal and external to the species, affect reproduction and survival rates, leading to generational shifts in natural populations. Individuals are chosen based on their predicted likelihood of producing the best outcomes. This process is similar to natural selection in that the strongest and healthiest people tend to increase while the weaker and less prosperous ones tend to die off. However, the selection reduces diversity rather than increasing it because it does not produce new individuals.
Tournament Selection
The pool gene’s exploration (n) and exploitation (N) characteristics are established by the number of participants in each tournament. In matching the number of individuals to fish, there is a need to host an equal number of tournaments. Poorly adapted individuals can be given a greater or lesser chance depending on the value of n. When many people participate, the weakest player is nearly guaranteed to lose. In addition, the population is segmented, and the individuals inside each segment compete with one another. Finally, each subgroup selects a single member to reproduce.
Roulette-wheel selection
Roulette-wheel selection is based on relative fitness, especially on an individual’s chances of getting picked increase or decrease depending on how much their fitness exceeds or falls below that of their contemporaries. This can be thought of as roulette, where each player receives a piece of the wheel, and those physically fit receive greater pieces than those who are not. Every time the wheel is spun, the person in whose area the ball lands is selected randomly.
Scaling selection
A more discriminatory fitness function results from an increase in the average fitness of a population, which in turn enhances the strength of selective pressure. When all people have relatively high fitness, and only tiny variances in fitness distinguish one from another, this strategy can help determine the optimal pick.
Rank-based Selection
At the outset of this selection method, the population is ranked in order of fitness. Then, based on that order, each person perceives himself as part of a specific social class. The worst person will be ranked 1, the next worst will be ranked 2, and so on, all the way up to the best person, who will be ranked N (N is the size of the population). Individual or chromosomal ranking selection is equivalent to random selection, with the difference being that the selection probabilities are proportional to the rank rather than the evaluation value.
Reproduction Operators
Crossing Operator
When two chromosomes exchange their characteristics, this is called a crossover. The crossing operator facilitates the mixing of genes within a population and the consequent application of Darwin’s principle of heredity. The first step in creating a new generation is deciding on a mating couple. The people in each pair are randomly picked from the pool of candidates. The matched people used crossover techniques (P1 and P2).
One can use a one-point crossing, or they can use a two-point crossing. Since there are two types of coding, binary and real, the resulting crossing or reproduction can be either binary or real. One-point crossover involves randomly selecting a crossover level and then switching the tails of the parent individuals to produce offspring. On the other hand, by changing around two sets of genes, or “points,” one can create new varieties, making double-point crossover a more generalized form of single-point crossover. The two crossover points are shown in the figure below;
Uniform crossing is sometimes used, leading to kids with an uneven genetic inheritance. Instead of relying on chromosomal (individual) subgroups, uniform crossover involves giving each gene extra attention. Each chromosome’s inclusion in a child is based on tossing a coin, which is determined by this factor. Each bit in a uniform crossover usually has an equal chance of coming from either parent. The diagram below shows that the odds favor the parents who will have a son with more genetic material.
Mutation Operator
It is similar to crossover, which involves switching one gene on one chromosome with another. The crossover helps the algorithm converge on a high-quality solution, while the mutation allows for diversity and prevents the algorithm from being prematurely convergent. While searching for the best possible answer, the mutation is utilized to avoid the search from settling on a single optimality point. In contrast to the crossover rate, the mutation rate must be set relatively low, usually between 0.001 and 0.01, to avoid a descent into random search and preserve the principle of natural selection and evolutionary change. There are many ways to apply mutation, as follows.
- Bit Flip Mutation: During a bit flip mutation, a random bit or bits are chosen and flipped. This type is employed when dealing with binary representations of GAs.
- Random resetting: This mutation is a refinement of the bit-flip mutation for the encoded integer. It consists of randomly picking a gene and giving it a value within the range of acceptable options.
- Swap mutation entails randomly picking any two chromosomal locations and swapping their respective numerical values. The most common mutation is swap mutation
- Scramble mutation: It works because some genes are picked randomly from all the people (chromosomes), and their values are mixed up.
- Inversion mutation: To create an inversion mutation, one selects a group of genes, like in the scrambling mutation, but instead of shuffling the selection, one inverts the complete chain of those genes.
Stopping/Termination Conditions
In the genetic algorithm, a new generation of solutions is generated. This generation stops when certain conditions are met, such as when the optimal solution according to the fitness results is reached, when a specific number of iterations is reached or when the population’s characteristics remain constant and do not change. The GA keeps creating new generations as long as specific requirements are not met. The maximum number of generations, the ideal solution, and the presence of particular qualities in the population are just a few examples of such circumstances.
Replacement
In each generation, a person should vanish from the population and be replaced by a new one. That decision is made through the replacement operation. The fitness value produced by the fitness function serves as the selection criterion in all cases. From the N + 1 individuals (N population members plus the newborn), this operation will select the N individuals most appropriate for the problem and have the highest similarity value to the target operation. The replacement technique allows for creating a new population and the maintenance of the ranking system based on the degree of individual adaption.
Advantages of Genetic Algorithm
Genetic algorithms are primarily parallel, which is a significant factor. Most algorithms are sequential, meaning they can only look in one direction for potential solutions to a problem at a time. If the solution they find is suboptimal, they must throw away their progress and start over. But since GAs can produce several offspring, they can simultaneously probe the solution space in different directions. Each iteration improves the odds of discovering the best solution since they can quickly discard subpar options and focus on more promising ones.
Genetic algorithms find solutions when the space of all possible solutions is truly big, too vast to search exhaustively in an acceptable length, because of the parallelism that implicitly allows them to analyze multiple schemas. The term “nonlinear” is commonly used to describe the type of problems that fit within this group. A linear problem is one in which each part’s fitness may be improved separately without affecting the wellness of the total system. This is not representative of most issues in the actual world. It is common for a single modification to have far-reaching consequences for the whole system and vice versa: increases in fitness may result from several improvements, some of which would be deleteriously taken alone.
Disadvantages of Genetic Algorithm
Despite their efficacy and strength, genetic algorithms are not a silver bullet for fixing all problems but have some disadvantages. The language used to express potential solutions must be strong because it must be able to withstand unpredictable changes without consistently producing fatal errors. Creating a representation for the problem is the first and most crucial step in developing a genetic algorithm.
The problem of writing the fitness function must be carefully considered so that higher fitness is attainable and does equate to a better solution for the given situation. According to Sivanandam & Deepa, the fitness function is chosen poorly or defined imprecisely. In that case, the genetic algorithm may be unable to find a solution or may end up solving the wrong problem. However, this does not occur naturally. One fitness function in the evolutionary lab is the drive to survive and reproduce. Biological populations that reproduce at a higher rate than their contemporaries are considered more fit, whereas those who fail to do so are considered less.
Lastly, numerous researchers caution against using genetic algorithms for issues that can be solved analytically. It is not that GAs cannot find good answers, but rather that traditional analytic methods take significantly less time and computational effort and, unlike GAs, are usually mathematically guaranteed to produce one perfect solution. Naturally, this problem does not exist in nature because there is no such thing as a mathematically ideal solution to any issue of biological adaptation.
The Application of Genetic Algorithm
Optimizing an objective function within the constraints of a Constraint Satisfaction Problem (CSP) provides the overarching foundation for COPs. Artificial intelligence, combinatorial optimization, complex digital operations, image processing, schedule optimization, and learning neural networks are just a few areas where GA has been used. Since the timetabling problem is NP-hard, a highly abstract idea of heuristics has been introduced to establish a comprehensive mathematical framework to describe it. Genetic algorithms attempt to optimize a function over a discrete structure with numerous independent variables.
The genetic algorithm used to evaluate success in finding optimal solutions and satisfying all constraints is entirely arbitrary. Although the complexity of assignment depends on the number of instances and conditions, genetic algorithms provide the best-case scenarios of reasonable schedule solutions via evolution processes once the objectives and constraints have been stated. This is why a reduced version of the Hybrid Genetic algorithm for building exam schedules at the University of Nottingham is being explored for use in the proposed system. The idea can be extended to match the building of course schedules, even though it was initially devised for test timetabling. This procedure is carried out until all exams can be scheduled without conflict, as shown in the following flowchart;
Like every other genetic algorithm, this algorithm can quickly produce large populations of random feasible exam timetables. Uniquely, the process takes each member of the course population and assigns it to the first period in which the exam may be placed without conflict. The mutation and crossover procedures are then applied to the population to satisfy constraints associated with each course in the assignment.
Conclusion
The research paper offered a foundational understanding of genetic algorithms and a class of heuristic search methods for tackling hard problems. The genetic algorithm’s many operators and parameters, such as mutation, crossover, selection, and choice of population size, prevent the development of a universal approach applicable to all situations; However, this does not prevent genetic algorithms from being very effective. There is a significant need for these algorithms due to speed and efficiency.
References
Abayomi-Alli, O., Abayomi-Alli, A., Misra, S., Damasevicius, R., & Maskeliunas, R. (2019). Automatic examination timetable scheduling using particle swarm optimization and local search algorithm. In Data, engineering, and applications (pp. 119-130). Springer, Singapore.
Ansari, R., & Saubari, N. (2020). Application of genetic algorithm concept on course scheduling.IOP conference series: materials science and engineering (Vol. 821, No. 1, p. 012043). IOP Publishing.
Guediri, A., & Touil, S. (2022). Optimization Using a Genetic algorithm based on DFIG Power Supply for the Electrical Grid. International Journal of Engineering, 35(1), 121-129.
Kılıç, H., & Yüzgeç, U. (2019). Tournament selection-based antlion optimization algorithm for solving quadratic assignment problem.Engineering science and technology, an international journal, 22(2), 673-691.
Mousa, H. M., & El-Sisi, A. B. (2013). Design and implementation of course timetabling system based on genetic algorithm. 2013 8th International Conference on Computer Engineering & Systems (ICCES) (pp. 167-171). IEEE. Web.
Sivanandam, S. N., & Deepa, S. N. (2008). Genetic algorithms. In Introduction to genetic algorithms (pp. 15-37). Springer, Berlin, Heidelberg. Web.
Tan, J. S., Goh, S. L., Kendall, G., & Sabar, N. R. (2021). A survey of the state-of-the-art of optimization methodologies in school timetabling problems.Expert Systems with Applications, 165, 113943.
Alattas, R. J., Patel, S., & Sobh, T. M. (2019). Evolutionary modular robotics: Survey and analysis.Journal of Intelligent & Robotic Systems, 95(3), 815-828.
Kureichik, V. M., & Logunova, J. A. (2019). The Implementation of the Genetic Algorithm Using Cloud-Based Computing on the Internet. In 2019 IEEE East-West Design & Test Symposium (EWDTS) (pp. 1-4). IEEE.
Kramer, O. (2017). Genetic algorithms. In Genetic algorithm essentials (pp. 11-19). Springer, Cham. Web.
García, J. M., Acosta, C. A., & Mesa, M. J. (2020). Genetic algorithms for mathematical optimization. In Journal of Physics: Conference Series (Vol. 1448, No. 1, p. 012020). IOP Publishing. Web.