Genetic Algorithm
Genetic Algorithm is a computational technique inspired by the process of natural selection and evolution. It involves generating a population of potential solutions to a problem, then using selection, crossover, and mutation operations to evolve and improve these solutions over successive generations. This approach is often used to find optimal or near-optimal solutions to complex optimization and search problems.
8 Key excerpts on "Genetic Algorithm"
- Anindya Ghosh, Prithwiraj Mal, Abhijit Majumdar(Authors)
- 2019(Publication Date)
- CRC Press(Publisher)
...9 Genetic Algorithm 9.1 Introduction The term optimization may be defined as the process of obtaining the best possible result out of all the conditions and available means. There is scarcely any area of scientific concern where optimization has not made its dent. With the advent of high-speed computational techniques, optimization algorithms have empowered scientists and technologists from diverse engineering disciplines where the emphasis is on maximizing or minimizing a certain objective. Focusing attention in the sphere of textile engineering, a rapidly increasing use of the optimization technique is now well recognized in machine design, process parameter setting, and engineering design of fibers, yarns, fabrics, and composites. The field of optimization has changed over the last few decades with the introduction of a number of nontraditional optimization algorithms that are based on the concept of natural phenomena. Of these, the Genetic Algorithm mimics nature’s evolutionary principles to drive its search toward an optimal solution. One of the most striking differences between the Genetic Algorithm and classical optimization algorithms is that the latter use a point-by-point approach, where one solution in each iteration is modified to a different (hopefully better) solution, and eventually the outcome becomes a local optimized solution, whereas the Genetic Algorithm works with a population of solutions in each iteration, instead of a single solution. As multiple solutions are processed concomitantly, it is likely that the expected final solution of the Genetic Algorithm may be a global optimized solution. The Genetic Algorithm is a heuristic search algorithm that proceeds by randomly generating an initial population of individuals. Each individual is represented by a binary-coded string or chromosome encoding a possible solution in the data space...
eBook - ePub- Xin-She Yang(Author)
- 2020(Publication Date)
- Academic Press(Publisher)
...Chapter 6: Genetic Algorithms Abstract Genetic Algorithm is one of the first evolutionary algorithms, which paces the way for contemporary evolutionary computation. This chapter introduces the basic principle of the Genetic Algorithm and its fundamental genetic operators: crossover, mutation, and selection. Keywords Algorithm; crossover; elitism; Genetic Algorithm; mutation; optimization; selection Genetic Algorithms are among the most popular evolutionary algorithms in terms of the diversity of their applications. A vast majority of well-known optimization problems have been tried by Genetic Algorithms. In addition, Genetic Algorithms are population-based, and many modern evolutionary algorithms are directly or indirectly based on Genetic Algorithms or have some strong similarities. 6.1 Introduction The Genetic Algorithm (GA), developed by John Holland and his collaborators in the 1960s and 1970s (Holland, 1975 ; De Jong, 1975), is a model or abstraction of biological evolution based on Charles Darwin's theory of natural selection. Holland was probably the first to use the crossover and recombination, mutation, and selection in the study of adaptive and artificial systems. These genetic operators form the essential part of the Genetic Algorithm as a problem-solving strategy. Since then, many variants of Genetic Algorithms have been developed and applied to a wide range of optimization problems, from graph coloring to pattern recognition, from discrete systems (such as the travelling salesman problem) to continuous systems (e.g., the efficient design of airfoil in aerospace engineering), and from financial markets to multi-objective engineering optimization. There are many advantages of Genetic Algorithms over traditional optimization algorithms. Two most notable are: the ability of dealing with complex problems and parallelism...
eBook - ePubIntelligent Systems for Engineers and Scientists
A Practical Guide to Artificial Intelligence
- Adrian A. Hopgood(Author)
- 2021(Publication Date)
- CRC Press(Publisher)
...Chapter 7 Genetic Algorithms for Optimization DOI: 10.1201/9781003226277-7 7.1 Introduction: Evolutionary Algorithms Evolutionary algorithms are a special family of optimization algorithms. Instead of striving to improve a single trial solution, like the techniques presented in Chapter 6, they maintain a population of candidate solutions. The population as a whole evolves toward the optimum, although the population may contain many poor solutions, especially during the early stages of evolution. In common with simulated annealing, evolutionary algorithms are generally designed to start with an exploration phase. During this phase, the population roams the search space seeking good quality regions. As there is a population of candidate solutions, several regions can be explored at the same time. As evolution progresses, the algorithm migrates from exploration to exploitation, that is, seeking the peak fitness of the region that is assumed, by this stage, to contain the global optimum. Genetic Algorithms (GAs) are the most popular type of evolutionary algorithm and will be described in detail in this chapter. GAs use only binary representations of candidate solutions, whereas no such restriction applies to the broader category of evolutionary algorithms. Evolutionary algorithms have been inspired by natural evolution, the process by which successive generations of animals and plants are modified so as to approach an optimum form. Each offspring has different features from its parents; it is not a perfect copy. If the new characteristics are favorable, the offspring is more likely to flourish and pass its characteristics to the next generation, via natural selection. However, an offspring with unfavorable characteristics is likely to die without reproducing...
eBook - ePubGenetic Algorithms and their Applications
Proceedings of the Second International Conference on Genetic Algorithms
- John J. Grefenstette, John J. Grefenstette(Authors)
- 2013(Publication Date)
- Psychology Press(Publisher)
...In this paper, we will concentrate onGenetic Algorithms, a class of adaptive algorithms invented by John Holland [8], to solve (or partially solve) this problem.Genetic Algorithms differ from more standard search algorithms (e.g., gradient descent, controlled random search, hill-climbing, simulated annealing [9] etc.) in that the search is conducted using the information of apopulationofstructuresinstead of that of a single structure. The motivation for this approach is that by considering many structures as potential candidate solutions, the risk of getting trapped in a local optimum is greatly reduced.Genetic Algorithms have been applied with great success by De Jong [4] to a wide variety of functions defined over object spaces of the formRn, i.e., each structurexconsists of n real numbersx[1]…x[n]. Only recently have there been attempts to apply Genetic Algorithms to other optimization problems such has the Traveling Salesman Problem (TSP) [6,7], Bin Packing [13], Job Scheduling [2,3]. An important observation made by Grefenstette et.al. [7] was that to successfully apply Genetic Algorithms to such problems, heuristic information has to be incorporated into the Genetic Algorithm; in particular they proposed a heuristic crossover operator and showed the dramatic improvement as compared to crossover operators which did not such heuristic information. In this paper, we continue the efforts of [7]. InSection 2we identify several problems which need to be overcome to successfully apply Genetic Algorithms to optimization problems other than the standard function optimization problems. InSections 3and4we illustrate the validity of our approach by providing Genetic Algorithms for the Traveling Salesman Problem and the Sliding Block Puzzle [12].2...
- James A. Momoh(Author)
- 2017(Publication Date)
- CRC Press(Publisher)
...15 Genetic Algorithms 15.1 Introduction In many engineering disciplines a large spectrum of optimization problems has grown in size and complexity. In some instances, the solution to complex multidimensional problems by using classical optimization techniques is sometimes difficult or expensive. This realization has led to an increased interest in a special class of searching algorithm, namely, evolutionary algorithms (EAs) [ 1, 3 ]. In general, these are referred to as stochastic optimization techniques and their foundations lie in the evolutionary patterns observed in living things. In this area of operational research, there exist several primary branches: Genetic Algorithms (GAs) Evolutionary programming (EP) Evolutionary strategies (ES) To date the GA is the most widely known technology. This optimization technique has been applied to many complex problems in the fields of industrial and operational engineering. In power systems, well-known applications include unit commitment, economic dispatch, load forecasting, reliability studies, and various resource allocation problems. 15.1.1 General Structure of GAs The typical structure of GAs was described by Goldberg [ 4 ]. Essentially, GAs are referred to as stochastic search techniques that are based on the Darwinian thinking of natural selection and natural genetics. In general, GAs start with an initial set of random solutions that lie in the feasible solution space. This random cluster of solution points is called a population. Each solution in the population represents a possible solution to the optimization problem and is therefore called a chromosome. The chromosome is a string of symbols based on the uniqueness of two-state machines; they are commonly binary bit strings. 15.2 Definition and Concepts Used in Genetic Computation GAs have their foundation both in natural biological genetics and in modern computer science (Table 15.1)...
eBook - ePubMachine Learning
An Algorithmic Perspective, Second Edition
- Stephen Marsland(Author)
- 2014(Publication Date)
- Chapman and Hall/CRC(Publisher)
...Of the two versions of each gene (one from each parent) one allele (variation) is selected. Hence, children have similarities with their parents, and there is lots of genetic inheritance. However, there are also random mutations, caused by copying errors when the chromosome material is reproduced, which means that some things do change over time. Real genetics is obviously a lot more complicated than this, but we are taking only the things that we want for our model. FIGURE 10.1 Each adult in the mating pair passes one of their two chromosomes to their offspring. The Genetic Algorithm shows many of the things that are best and worst about machine learning: it is often, but not always, very effective, it has an array of parameters that are crucial, but hard to set, and it is impossible to guarantee that it will find a result that is any good at all. Having said all that, it often works very well, and it has become a very popular algorithm for people to use when they have no idea of any other way to find a reasonable solution. In the terms that we saw at the end of the previous chapter, Genetic Algorithms perform both exploitation and exploration, so that they can make incremental improvements to current good solutions, but also find radically new solutions, some of which may be better than the current best. We will also look briefly at two other topics in this chapter, a variation of the Genetic Algorithm that acts on trees that represent computer programs that is known as Genetic Programming, and a set of algorithms that use sampling from a probability distribution rather than an evolving population in order to find better solutions. 10.1 The Genetic Algorithm (GA) The Genetic Algorithm is a computational approximation to how evolution performs search, which is by producing modifications of the parent genomes in their offspring and thus producing new individuals with different fitness...
eBook - ePubInnovative Research Methodologies in Management
Volume I: Philosophy, Measurement and Modelling
- Luiz Moutinho, Mladen Sokele, Luiz Moutinho, Mladen Sokele(Authors)
- 2017(Publication Date)
- Palgrave Macmillan(Publisher)
...Moreover, it must be stressed that EA aim at good but not necessarily optimal solutions for a given application problem. This is in line with other heuristic approaches. In management practice it is often sufficient to find good solutions within reasonable time. Evolutionary Algorithms are also termed “Evolutionary Computation”, and rank among computational intelligence (or soft computing) methods. They also belong to the more general class of metaheuristics, which Sörensen and Glover (2013) define in the following way: “A metaheuristic is a high-level problem-independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. The term is also used to refer to a problem-specific implementation of a heuristic optimization algorithm according to the guidelines expressed in such a framework.” 1 In their “history of metaheuristics”, Sörensen et al. (2016, p. 3) identify five distinct periods, starting with the pre-theoretical period (until c. 1940), during which heuristics and even metaheuristics are used but not formally studied, followed by the early period (c. 1940–c. 1980), during which the first formal studies on heuristics appear, and the method-centric period (c. 1980–c. 2000), during which the field of metaheuristics truly takes off and many different methods are proposed. They argue that we currently witness the framework-centric period (c. 2000–now), during which the insight grows that metaheuristics are more usefully described as frameworks, and not as methods. The final scientific period (the future) then is characterized by the design of metaheuristics becoming a science instead of an art, with the focus shifting from performance to understanding. Particularly important for our understanding here is the framework-centric view (Sörensen et al. 2016, p. 10)...
eBook - ePub- Altaf Q. H. Badar(Author)
- 2021(Publication Date)
- CRC Press(Publisher)
...It also developed other characteristics like the fast swallowing of meat, managing high heart rate, etc. which were necessary for it to survive. Here, survival was the objective and the objective function was to run fast. The faster a cheetah could run, the fitter it became and the more its chances of passing on the genes to the next generation. This same methodology has been implemented in the Genetic Algorithm. Genetic Algorithm (GA) tries to implement the same evolving behavior/process of nature to find the optimal solution. GA was one of the first bioinspired EOA. It can also be observed from overall research publications that GA is one of the most researched and implemented EOA. GA has innumerable variants and hybrids in the research domain. The terminology involved in GA shall be covered in later sections. However, it is necessary to again mention here that fit/fitness value/objective function value are to be considered as one and the same throughout the chapter. These terms shall determine which possible solutions from the pool of available solutions are better than the remaining solutions. John Holland [ 136 ] describes the formulation of GA as an EOA on the principles of natural evolution. 3.2 TERMINOLOGY The word “genetics” comes from the Greek word “genesis” which means “to grow”. Let us explore some more biological terminologies which will come in handy for understanding GA. Chromosome : The genetic information of any naturally living organism is stored in a chromosome. The chromosome itself is made up of several smaller parts called genes. A chromosome is represented in Fig 3.1 Genes : Genes are responsible to determine the characteristics of an individual. A gene represents a single independent feature/input variable. The relation between a chromosome and a gene is shown in Fig 3.2. Allele : The possible values that a gene can have for a particular characteristic are called alleles...
