Optimization problems

In a genetic algorithm, a population of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem is evolved toward better solutions. Each candidate solution has a set of properties (its chromosomes or genotypes) that can be mutated and altered. Traditionally, solutions are represented in binary as strings of zeros and ones, but other encodings are also possible.

Evolution usually starts from a population of randomly generated individuals, and is an iterative process, with the population in each iteration called a generation. In each generation, the fitness of each individual in the population is evaluated. Fitness is usually the value of the objective function in the optimization problem being solved. The fittest individuals are selected stochastically from the current population, and each individual's genome is modified (recombined "Recombination (evolutionary computing)") and possibly mutated at random) to form a new generation. The new generation of candidate solutions is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when a maximum number of generations has occurred, or a satisfactory fitness level for the population has been reached.

A typical genetic algorithm requires:

1. • A genetic representation of the solution domain.

2. • A fitness function to evaluate the mastery of the solution.

A standard representation of each candidate solution is as an array "(mathematical) Matrix") of bits. Arrays of other types and structures can be used in essentially the same way. The main property that makes these genetic representations convenient is that their parts are easily aligned due to their fixed size, which facilitates simple crossover operations. Variable length representations can also be used, but the implementation of chromosome crossing over is more complex in this case. Tree representations are explored in genetic programming and graph-like representations are explored in evolutionary programming. A mixture of both linear chromosomes and trees is explored in gene expression programming.

Once the genetic representation and fitness function are defined, a GA proceeds to initialize a population of solutions and then improve it by repetitively applying the mutation, crossover, inversion, and selection operators.

The size of the population depends on the nature of the problem, but typically contains several hundred or thousands of possible solutions. Often the initial population is generated randomly, allowing for the full range of possible solutions (the search space). Occasionally, solutions may be "seeded" in areas where optimal solutions are likely to be found.

During each successive generation, a portion of the existing population is selected to raise a new generation. Individual solutions are selected through a fitness-based process, where fitness solutions (as measured by a fitness function) are typically more likely to be selected. Certain selection methods evaluate the suitability of each solution and preferentially select the best solutions. Other methods score only a random sample of the population, as the above process can be time-consuming.

The fitness function is defined on the genetic representation and measures the quality of the represented solution. The fitness function always depends on the problem. For example, in the backpack problem we want to maximize the total value of the objects that can be put in a backpack of some fixed capacity. A representation of a solution can be an array of bits, where each bit represents a different object, and the value of the bit (0 or 1) represents whether or not the object is in the backpack. Not all representations are valid, since the size of the objects may exceed the capacity of the backpack. The fitness of the solution is the sum of values ​​of all objects in the backpack if the representation is valid, or 0 otherwise.

In some problems, it is difficult or even impossible to define the expression of physical condition. In these cases, simulation can be used to determine the value of the fitness function of a phenotype (for example, computational fluid dynamics is used to determine the air resistance of a vehicle whose shape is encoded as the phenotype) or even interactive genetic algorithms.

The next step is to generate a second generation population, from solutions selected through a combination of genetic operators: chromosomal crossing over (also called crossover or recombination) and mutation.

For each new solution that has been produced, a pair of "parent" solutions has been selected for breeding from the previously selected pool. By producing a "breeding" solution using the chromosomal crossover and mutation methods mentioned above, a new solution is created that typically shares many of the characteristics of its "parents." New parents are selected for each new brood, and the process continues until a new population of solutions of appropriate size is generated. Although breeding methods that rely on the use of two parents are more "inspired biology", some research suggests that more than two "parents" can generate higher quality chromosomes.

These processes ultimately result in the next generation of chromosome population, which is different from the initial generation. In general, the average fitness has been increased by this procedure for the population, since only the best organisms from the first generation are selected for breeding, along with a small proportion of less fit solutions. These less fit solutions ensure genetic diversity within the genetic pool of the parents and, therefore, ensure the genetic diversity of the next generation of children.

Opinion is divided on the importance of crossover versus mutation. There are many references in Fogel (2006) that support the importance of mutation-based search.

Although crossover and mutation are known as the main genetic operators, it is possible to use other operators such as reassortment, colonization-extinction or migration in genetic algorithms.

It is worth adjusting parameters such as mutation probability, crossover probability, and population size to find reasonable fits for the kind of problem you are working on. A very small mutation rate can lead to genetic drift (which is non-ergodic in nature). A recombination rate that is too high can lead to premature convergence of the genetic algorithm. Too high a mutation rate can lead to the loss of good solutions, unless elite selection is used.

This generational process is repeated until a termination condition is reached. Common termination conditions are:.

• - A solution is found that satisfies the minimum criteria.

• - A fixed number of generations is reached.

• - The assigned budget is reached (calculation time / money).

• - The fitness of the highest ranked solution is reaching or has reached a plateau such that successive iterations no longer produce better results.

• - Manual inspection.

• - Combinations of the above.

Genetic algorithms are simple to implement, but their behavior is difficult to understand. In particular, it is difficult to understand why these algorithms are often successful in generating high fitness solutions when applied to practical problems. The building block hypothesis (BBH) consists of:.

• - A description of a heuristic that performs adaptation by identifying and recombining "building blocks", that is, low-order, low-length definition schemes with above-average fitness.

• - A hypothesis that a genetic algorithm performs adaptation implicitly and efficiently by implementing this heuristic.

Goldberg describes the heuristic as follows:

Short, low-order, high-fit schemes are sampled, recombined (cross-linked), and resampled to form chains of potentially higher fitness. In a way, by working with these particular schemas (the building blocks), we have reduced the complexity of our problem. Instead of building high-performing chains by trying every conceivable combination, we build better and better chains from the best partial solutions from the last few samples.

"Because highly tuned schemes of low length and low order play such an important role in the action of genetic algorithms, we have already given them a special name: building blocks. As a child creates magnificent fortresses through the arrangement of simple wooden blocks, so does a genetic algorithm seeking to approach optimal performance through the juxtaposition of short, low-order, high-performance schemes, or building blocks."

Despite the lack of consensus regarding the validity of the building block hypothesis, it has been evaluated and used as a reference over the years. Many estimation distribution algorithms, for example, have been proposed in an attempt to provide an environment in which the hypothesis would hold. Although good results have been reported for some classes of problems, skepticism still remains regarding the generality and/or practicality of the building block hypothesis as an explanation of the efficiency of GAs. In fact, there is a reasonable amount of work that attempts to understand its limitations from the perspective of estimating distribution algorithms.

There are limitations to using a genetic algorithm compared to alternative optimization algorithms:

• - Repeated evaluation of the fitness function for complex problems is often the most prohibitive and limiting segment of artificial evolutionary algorithms. Finding the optimal solution to complex three-dimensional and multimodal problems often requires very expensive conditioning function evaluations. In real-world problems such as structural optimization problems, an evaluation of a single function may require several hours to several days of full simulation. Typical optimization methods cannot deal with these types of problems. In this case, it may be necessary to forego exact evaluation and use an approximate fitness that is computationally efficient. It is evident that the amalgamation of approximate models can be one of the most promising approaches to convincingly use GA to solve complex real-life problems.

• - Genetic algorithms do not adapt well to complexity. That is, when the number of elements exposed to mutation is large, there is often an exponential increase in the size of the search space. This makes it extremely difficult to use the technique in problems such as the design of an engine, a house, or an airplane. In order to make such problems tractable to evolutionary search, they must be decomposed into the simplest possible representation. Therefore, we typically see evolutionary algorithms encoding designs for fan blades instead of engines, construction forms instead of detailed construction plans, and airfoils instead of complete aircraft designs. The second complexity problem is the question of how to protect parts that have evolved to represent good solutions from further destructive mutation, particularly when their fitness assessment requires them to combine well with other parts.

• - The “best” solution is only in comparison to other solutions. As a result, the stopping criterion is not clear in each problem.

• - In many problems, GAs may have a tendency to converge towards local optimum or even arbitrary points rather than the global optimum of the problem. This means that they do not "know how" to sacrifice short-term fitness to gain longer-term fitness. The probability of this occurring depends on the shape of the fitness landscape: certain problems may provide an easy climb towards a global optimum, others may make it easier for the function to find the local optimum. This problem can be alleviated by using a different fitness function, increasing the mutation rate, or by using selection techniques that maintain a diverse population of solutions [12], although the free lunch theorem [13] shows that there is no general solution to this problem. A common technique for maintaining diversity is to impose a "niche penalty", in which, any group of individuals of similar similarity (niche radius) has an added penalty, which will reduce the representation of that group in subsequent generations, allowing others to be maintained in the population. This trick, however, may not be effective, depending. of the problem landscape. Another possible technique would be to simply replace part of the population with randomly generated individuals, when the majority of the population is too similar to each other. Diversity is important in genetic algorithms (and in genetic programming) because crossing a homogeneous population does not generate new solutions. In evolution strategies and evolutionary programming, diversity is not essential due to a greater dependence on mutation.

• - Operating on dynamic data sets is difficult, as genomes begin to converge early towards solutions that are no longer valid for subsequent data. Various methods have been proposed to remedy this, by increasing genetic diversity in some way and preventing early convergence, either by increasing the probability of mutation when the quality of the solution drops (called triggered hypermutation) or by occasionally introducing new randomly generated elements into the gene set (called random immigrants). Again, evolution strategies and evolutionary programming can be implemented with a so-called "coma strategy" in which parents are not maintained and new parents are selected only from offspring. This can be more effective in dynamic problems.

• - GAs cannot solve problems where the only correct measure is a right/wrong measure (such as decision problems), since there is no way to converge on the solution (no hill to climb). In these cases, a random search can find a solution as quickly as a GA. However, if the situation allows the success/failure trial to be repeated giving (possibly) different results, then the ratio of successes to failures provides an appropriate measure of fitness.

• - For specific optimization problems and problematic instances, other optimization algorithms may be more efficient than genetic algorithms in terms of convergence speed "Convergence (mathematics)"). Alternative and complementary algorithms include evolution strategies, evolutionary programming, simulated annealing, Gaussian adaptation, hill climbing and swarm intelligence (for example: ant optimization, particle swarm optimization) and methods based on integer linear programming. The suitability of genetic algorithms depends on the amount of knowledge of the problem; Well-known problems often have better, more specialized approaches.

Chromosome representation

The simplest algorithm represents each chromosome as a string of bits. Typically, numeric parameters can be represented by integers, although it is possible to use floating-point representations. Floating point representation is a natural for evolution strategies and evolutionary programming. The notion of real-valued genetic algorithms has been offered but is actually a misnomer because it does not really represent the building block theory that was proposed by John Henry Holland in the 1970s. This theory is not without support, however, based on theoretical and experimental results (see below). The basic algorithm performs crossover and mutation at the bit level. Other variants treat the chromosome as a list of numbers that are indexes in a table of statements, nodes in a linked list, hashes, objects, or any other data structure imaginable. Crossover and mutation are done to respect the boundaries of data elements. For most data types, specific variation operators can be designed. Different types of chromosome data seem to work better or worse for different specific problem domains.

When using bit number representations of integers, Gray coding is often employed. In this way, small changes in the integer can be easily affected by mutations or crossovers. This has been found to help prevent premature convergence at walls called Hamming, in which too many simultaneous mutations (or crossover events) must occur in order to change the chromosome to a better solution.

Other approaches involve using arrays of real-valued numbers instead of bit strings to represent chromosomes. The results from schema theory suggest that in general, the smaller the alphabet, the better the performance, but it was initially surprising to researchers that good results were obtained using real-valued chromosomes. This was explained as the set of real values ​​in a finite population of chromosomes as forming a virtual alphabet (when selection and recombination are dominant) with a much lower cardinality than would be expected from a floating-point representation [14] [15].

An expansion of the genetic algorithm's accessible domain problem can be obtained through the more complex coding solution of clusters by concatenation of several types of genes heterogeneously encoded on a chromosome. [16] This particular approach allows solving optimization problems that require extremely disparate definition domains for the problem parameters. For example, in cascade controller tuning problems, the structure of the inner loop controller may belong to a conventional three-parameter controller, while the outer loop could implement a linguistic controller (such as a fuzzy system) that has an inherently different description. This particular form of coding requires a specialized crossover mechanism that recombines the chromosome per section, and is a useful tool for modeling and simulation of complex adaptive systems, especially evolutionary processes.

Elitism

A practical variant of the general process of building a new population is to allow the best organisms of the current generation to be carried over to the next, unchanged. This strategy is known as elite selection and guarantees that the quality of the solution obtained by the GA will not decrease from one generation to the next.

Parallel implementations

Parallel implementations of genetic algorithms come in two flavors. Coarse-grained parallel genetic algorithms assume a population at each of the computing nodes and migration of individuals between the nodes. Parallel genetic algorithms assume an individual at each processing node that acts with neighboring individuals for selection and reproduction. Other variants, such as genetic algorithms for online optimization problems), introduce time dependence or noise into the fitness function.

Adaptive genetic algorithm

Genetic algorithms with adaptive parameters (adaptive genetic algorithms, AGAs) is another significant and promising variant of genetic algorithms. The probabilities of crossover (pc) and mutation (p.m.) largely determine the degree of accuracy of the solution and the speed of convergence that genetic algorithms can obtain. Instead of using fixed values ​​of pc and p. m., the GAs use the population information in each generation and adaptively adjust the pc and p. m. in order to maintain population diversity as well as to sustain the capacity for convergence. In AGA (adaptive genetic algorithm), the adjustment of pc and p. m. It depends on the fitness values ​​of the solutions. In CAGA (clustering-based adaptive algorithm), through the use of clustering analysis to judge the optimality states of the population, the adjustment of pc and p. m. depends on these optimization states. It can be very effective to combine GA with other optimization methods. GA tends to be pretty good at finding generally good global solutions, but pretty inefficient at finding the last few mutations to find the absolute optimum. Other techniques (such as simple hill climbing) are quite efficient at finding the absolute optimum in a limited region. Alternating GA and hill climbing can improve the efficiency of GA [citation needed] while overcoming the unsoundness of hill climbing.

This means that the rules of genetic variation may have a different meaning in the natural case. For example - provided the steps are stored in consecutive order - crossover can add a series of maternal DNA steps by adding a series of paternal DNA steps and so on. This is like adding vectors that can most likely follow a ridge in the phenotypic landscape. Therefore, the efficiency of the process can be increased by many orders of magnitude. Furthermore, the investment trader has the opportunity to place the steps in consecutive order or any other appropriate order in favor of survival or efficiency.

A variation, in which the population as a whole develops rather than its individual members, is known as genetic group recombination.

A series of variations have been developed to try to improve the performance of GAs in problems with a high degree of fitness epistasis, that is, when the fitness of a solution consists of interacting subsets of its variables. Such algorithms aim to learn (before exploiting) these beneficial phenotypic interactions. As such, they are aligned with the building block hypothesis in the adaptive reduction of disruptive recombination.

Problems that appear to be particularly suited to solution using genetic algorithms include programming problems, and many programming software packages are based on GAs. GAs have also been applied to engineering. Genetic algorithms are often applied as an approach to solving global optimization problems.

As a general rule, genetic algorithms can be useful in problem domains that have a complex fitness landscape, since mixing, that is, mutation in combination with crossover "Recombination (evolutionary computing)"), is designed to move the population further away from the local optimum than a traditional algorithm. Note that commonly used crossover operators cannot change any uniform population. Mutation alone can provide ergodicity of the overall genetic algorithm process (seen as a Markov chain).

Contenido

En 1950, Alan Turing propuso una "máquina de aprendizaje" que sería paralela a los principios de la evolución. La simulación por computadora de la evolución comenzó tan pronto como en 1954 con el trabajo de Nils Aall Barricelli"), que utilizaba la computadora en el instituto para el estudio avanzado en Princeton (Nueva Jersey) "Princeton (Nueva Jersey)"). Su publicación de 1954 no fue ampliamente notada. A partir de 1957, el australiano cuantitativo genetista Alex Fraser") publicó una serie de artículos sobre la simulación de la selección artificial de organismos con múltiples loci controlando un rasgo mensurable. A partir de estos comienzos, la simulación por ordenador de la evolución por los biólogos se hizo más común a principios de 1960, y los métodos fueron descritos en los libros de Fraser y Burnell (1970) y Crosby (1973) Las simulaciones de Fraser incluían todos los elementos esenciales de los algoritmos genéticos modernos. Además, Hans-Joachim Bremermann publicó una serie de artículos en los años sesenta que también adoptaron una población de solución a problemas de optimización, sometidos a recombinación, mutación y selección. La investigación de Bremermann también incluyó los elementos de los algoritmos genéticos modernos. Otros destacados primeros pioneros son Richard Friedberg"), George Friedman y Michael Conrad. Muchos de los primeros artículos han sido reimpresos por Fogel (1998).

Aunque Barricelli, en el trabajo que relató en 1963, había simulado la evolución de la capacidad de jugar un juego simple, la evolución artificial se convirtió en un método de optimización ampliamente reconocido como resultado del trabajo de Ingo Rechenberg y Hans-Paul Schwefel en los años 1960 y principios de 1970 - el grupo de Rechenberg fue capaz de resolver problemas complejos de ingeniería a través de estrategias de evolución.Otro enfoque fue la técnica de programación evolutiva de Lawrence J. Fogel, que se propuso para generar inteligencia artificial. La programación evolutiva utilizó originalmente máquinas de estado finito para predecir los entornos y utilizó la variación y la selección para optimizar las lógicas predictivas. Los algoritmos genéticos, en particular, se hicieron populares a través del trabajo de John Henry Holland a principios de los años setenta, y particularmente de su libro Adaptation in Natural and Artificial Systems (1975). Su trabajo se originó con estudios de autómatas celulares, conducidos por Holland y sus estudiantes en la Universidad de Míchigan. Holland introdujo un marco formalizado para predecir la calidad de la próxima generación, conocido como el teorema del esquema de Holland. La investigación en GAs permaneció en gran parte teórica hasta mediados de los años 80, cuando la primera conferencia internacional en algoritmos genéticos fue llevada a cabo en Pittsburgh, Pensilvania.

Commercial products

In the late 1980s, General Electric began selling the world's first genetic algorithm product, a mainframe-based toolbox designed for industrial processes. In 1989, Axcelis, Inc. released Evolver, the first commercial AG product for desktop computers. New York Times technology writer John Markoff wrote about Evolver in 1990, and it remained the only interactive trading algorithm until 1995. Evolver was sold to Palisade in 1997, translated into several languages, and is currently in its sixth version.

Considérese el problema de insertar signos de suma o resta entre los dígitos 9 8 7 6 5 4 3 2 1 para construir una expresión cuyo valor sea 100; no vale añadir, retirar o desordenar a los dígitos. Una solución puede ser 98+7-6+5-4+3-2-1 porque, al evaluar su valor, da exactamente 100.

Hay 9 sitios (uno antes de cada dígito) donde colocar un signo de más (+), un signo de menos (-) o nada (lo cual implicará que dos o más dígitos se unan para formar cantidades mayores; como 98 en el ejemplo anterior, donde se puso "nada" antes del 9 y antes del 8). Existen, por lo tanto, 3 a la 9 = 19683 expresiones distintas (por combinatoria) entre las cuales buscar aquellas con la suma deseada. Es posible desarrollar un algoritmo exhaustivo que las genere todas y, dada la relativa pequeñez de este ejemplo, determinar completamente todas las posibles configuraciones. Sin embargo, este reto se presta para ilustrar los pasos de un proceso genético.

Coding

There is a bijection between the strings of "trits" (ternary digits: 0, 1, 2) of length 9 and the possible sign configurations for each sum. For example, if the convention is adopted that "0" represents "nothing", "1" represents "less", and "2" represents "more", then the string of "trits" 002121211 corresponds to the solution 98+7-6+5-4+3-2-1.

Parent fields

Genetic algorithms are a subfield of:.

• - Evolutionary algorithms.

• - Evolutionary computing.

• - Metaheuristics.

• - Stochastic optimization.

• - Improvement.

Related fields

Evolutionary algorithms are a subfield of evolutionary computing.

• - Evolution strategies (ES, see Rechenberg, 1994) evolve individuals through mutation and intermediate or discrete recombination. ES algorithms are specially designed to solve problems in the real value domain. They use self-adaptation to adjust the search control parameters. The de-randomization of self-adaptation has led to the current Covariance Matrix Adaptation Evolution Strategy (CMA-ES).

• - Evolutionary programming (EP) involves populations of solutions with mutation and selection and arbitrary representations. It uses self-adaptation to adjust parameters, and may include other variation operations, such as combining information from multiple parents.

• - Estimation Distribution Algorithm (EDA) replaces traditional replay operators with model-driven operators. These models are learned from the population using machine learning techniques and represented as Probabilistic Graphical Models, from which new solutions can be sampled [45] [46] or generated from guided chromosome crossing over [47].

• - Gene expression programming (GEP) also uses populations of computer programs. These complex computer programs are encoded in simpler linear chromosomes of fixed length, which are then expressed as expression trees. Expression trees or computer programs evolve because chromosomes undergo mutation and recombination in a manner similar to canonical GA. But thanks to the special organization of GEP chromosomes, these genetic modifications always result in valid computer programs. [48].

• - Genetic programming (GP) is a related technique popularized by John Koza in which computer programs, rather than functional parameters, are optimized. Genetic programming often uses internal tree-based data structures to represent computer programs for adaptation instead of the list structures typical of genetic algorithms.

• - The genetic algorithm clustering (GGA) is an evolution of GA where the focus shifts from individual elements, as in classical GA, to groups or subsets of elements. [49] The idea behind this evolution of GA proposed by Emanuel Falkenauer is that the solution of some complex problems, such as clustering or partition problems where a set of items must be divided into a group of disjoint elements in an optimal way, would be best achieved by taking features from groups of items equivalent to genes. These types of problems include container packing, line balancing, grouping with respect to a distance measure, equal stacks, etc., in which classical GAs demonstrated poor performance. Making genes equivalent to groups involves chromosomes that are generally of variable length, and special genetic operators that manipulate entire groups of elements. For container packaging, in particular, a GGA hybridized with the Martello and Toth Dominance Criterion is possibly the best technique to date.

• - Interactive evolutionary algorithms are evolutionary algorithms that use human evaluation. They are typically applied to domains where it is difficult to design a computational fitness function, for example, evolving images, music, artistic designs, and shapes to fit the aesthetic preference of users.

• - Ant colony optimization (ACO) uses many ants (or agents) equipped with a pheromone model to traverse the solution space and find local productive areas. An estimate of the distribution algorithm is considered.

• - Particle swarm optimization (PSO) is a computational method for multiparametric optimization that also uses a population-based approach. A population (swarm) of candidate solutions (particles) moves in the search space, and the motion of the particles is influenced by both their best-known position and the best-known global position of the swarm. Like genetic algorithms, the PSO method depends on the exchange of information between members of the population. In some problems, PSO is often more computationally efficient than GAs, especially in unconstrained problems with continuous variables.

• - The Memetic algorithm (MA), often called hybrid genetic algorithm, among others, is a population-based method in which solutions are also subject to local improvement phases. The idea of ​​memetic algorithms, which unlike genes, can adapt. In some problem areas they are shown to be more efficient than traditional evolutionary algorithms.

• - Bacteriological algorithms (BA) are inspired by evolutionary ecology and, more specifically, bacteriological adaptation. Evolutionary ecology is the study of living organisms in the context of their environment, with the goal of discovering how they adapt. Its basic concept is that in a heterogeneous environment, there is no individual that fits the entire environment. Therefore, one has to reason at the population level. It is also believed that BAs could be successfully applied to complex positioning problems (cell phone antennas, urban planning, etc.) or data mining. [52].

• - The cultural algorithm (CA) consists of the population component almost identical to that of the genetic algorithm and, in addition, a knowledge component called the belief space.

• - The differential search (DS) algorithm is inspired by the migration of superorganisms.

• - Gaussian adaptation (normal or natural adaptation, abbreviated NA to avoid confusion with GA) is intended to maximize the manufacturing performance of signal processing systems. It can also be used for ordinary parametric optimization. It is based on a certain theorem valid for all regions of acceptability and all Gaussian distributions. The efficiency of NA depends on information theory and a certain efficiency theorem. Its efficiency is defined as information divided by the work necessary to obtain the information. Because NA maximizes mean fitness rather than individual fitness, the landscape smoothes out such that the valleys between peaks can disappear. Therefore, it has a certain "ambition" to avoid local peaks in the fitness landscape. NA is also good at scaling sharp ridges by adapting the moment matrix, because NA can maximize the disorder (average information) of the Gaussian while simultaneously keeping the mean fitness constant.

• - Simulated annealing (SA) is a related global optimization technique that traverses the search space by testing random mutations in an individual solution. A mutation that increases fitness is always accepted. A mutation that decreases fitness is accepted probabilistically based on the difference in fitness and a decreasing temperature parameter. In SA jargon, we talk about aiming for lowest energy rather than maximum fitness. SA can also be used within a standard GA algorithm starting with a relatively high mutation rate and decreasing over time along a given schedule.

• - Tabu search (TS) is similar to simulated annealing in that both traverse the solution space testing mutations of an individual solution. While simulated annealing generates only one mutated solution, tabu search generates many mutated solutions and moves to the solution with the lowest energy of those generated. In order to avoid loops and encourage further movement through the solution space, a tabu list of partial or complete solutions is maintained. It is prohibited to move to a solution that contains elements of the tabu list, which is updated as the solution traverses the solution space.

• - Extreme Optimization (EO), unlike GAs, which work with a population of candidate solutions, develops a single solution and makes local modifications to the worst components. This requires that an appropriate representation be selected that allows individual solution components to be assigned a measure of quality ("fitness"). The governing principle behind this algorithm is that of emergent improvement by selectively removing low-quality components and replacing them with a randomly selected component. This is decidedly at odds with a GA that selects good solutions in an attempt to make better solutions.

• - The cross entropy (CE) method generates candidate solutions using a parameterized probability distribution. The parameters are updated by minimizing the cross entropy, to generate better samples in the next iteration.

• - Reactive search optimization (RSO) advocates the integration of sub-symbolic learning techniques into search heuristics to solve complex optimization problems. The word reactive suggests a rapid response to events during searching through an internal online feedback loop for self-tuning of critical parameters. Methodologies of interest for reactive search include machine learning and statistics, particularly reinforcement learning, active or query learning, neural networks, and metaheuristics.

• - Neural networks.

• - Fuzzy logic.

• - Bayesian network.

• - Local minimum/maximum.

• - Artificial Intelligence.

• - Evolutionary Robotics").

• - Emergency "Emergency (philosophy)").

• - Cellular automaton.

• - Santillán Code").

• - Banzhaf, Wolfgang; Nordin, Peter; Keller, Robert; Francone, Frank (1998). Genetic Programming - An Introduction. San Francisco, CA: Morgan Kaufmann. ISBN 978-1558605107.

• - Bies, Robert R.; Muldoon, Matthew F.; Pollock, Bruce G.; Manuck, Steven; Smith, Gwenn; Sale, Mark E. (2006). "The Genetic Algorithm-Based, Hybrid Machine Learning Approach to Model Selection." Journal of Pharmacokinetics and Pharmacodynamics. Netherlands: Springer: 196-221.

• - Carmona, Enrique J.; Fernández, Severino (2020). Fundamentals of Evolutionary Computation. Marcombo. ISBN 978-8426727558.

• - Cha, Sung-Hyuk; Tappert, Charles C. (2009). "Genetic Algorithm for Constructing Compact Binary Decision Trees." Journal of Pattern Recognition Research. 4 (1): 1-13. doi:10.13176/11.44.

• - Eiben, Agoston; Smith, James (2003). Introduction to Evolutionary Computing. Springer. ISBN 978-3540401841.

• - Fraser, Alex S. (1957). "Simulation of Genetic Systems by Automatic Digital Computers, I. Introduction." Australian Journal of Biological Sciences. 10: 484-491.

• - Goldberg, David (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley Professional. ISBN 978-0201157673.

• - Goldberg, David (2002). The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Norwell, MA: Kluwer Academic Publishers. ISBN 978-1402070983.

• - Fogel, David. Evolutionary Computation: Toward the New Philosophy of Machine Intelligence (3rd ed.). Piscataway, NJ: IEEE Press. ISBN 978-0471669517.

• - Hingston, Philip; Barone, Luigi Michalewicz, Zbigniew (2008). Design by Evolution: Advances in Evolutionary Design. Springer. ISBN 978-3540741091.

• - Holland, John (1992). Adaptation in Natural and Artificial Systems. Cambridge, MA: MIT Press. ISBN 978-0262581110.

• - Koza, John (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: MIT Press. ISBN 978-0262111706.

• - Michalewicz, Zbigniew (1996). Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag. ISBN 978-3540606765.

• - Mitchell, Melanie (1996). An Introduction to Genetic Algorithms Cambridge, MA: MIT Press. ISBN 9780585030944.

• - Poly, R.; Langdon, W.B.; McPhee, N.F. (2008). A Field Guide to Genetic Programming. Lulu.com, freely available from the internet. ISBN 978-1-4092-0073-4.

• - Rechenberg, Ingo (1994): Evolutionsstrategie '94, Stuttgart: Fromman-Holzboog.

• - Schmitt, Lothar M; Nehaniv, Chrystopher L; Fujii, Robert H (1998), Linear analysis of genetic algorithms, Theoretical Computer Science 208: 111-148.

• - Schmitt, Lothar M (2001), Theory of Genetic Algorithms, Theoretical Computer Science 259: 1-61.

• - Schmitt, Lothar M (2004), Theory of Genetic Algorithms II: models for genetic operators over the string-tensor representation of populations and convergence to global optimality for arbitrary fitness functions under scaling, Theoretical Computer Science 310: 181-231.

• - Schwefel, Hans-Paul (1974): Numerische Optimierung von Computer-Modellen (PhD thesis). Reprinted by Birkhäuser (1977).

• - Vose, Michael (1999). The Simple Genetic Algorithm: Foundations and Theory. Cambridge, MA: MIT Press. ISBN 978-0262220583.

• - Whitley, Darrell (1994). "A genetic algorithm tutorial." Statistics and Computing. 4 (2): 65-85. Doi:10.1007/BF00175354.

Resources

• - (broken link) This website describes several genetic algorithms along with their programming codes and how they can be used to find the optimal point of a process.

• - Application of genetic algorithms to the optimization of composite material laminates.

• - A Practical Genetic Algorithm Tutorial Programming step by step a Genetic Algorithm.

• - Introduction to Genetic Algorithms with interactive Java applets.

• - Genetic algorithms tutorial Archived October 28, 2005 at the Wayback Machine.

• - A simple tutorial in Spanish about genetic algorithms.

• - Introduction to Genetic Algorithms.

• - Genetic algorithms and evolutionary computing.

• - Robot with Navigation System based on Genetic Algorithms.

• - Genetic algorithms in Ruby.

• - Arquimedex.com Simple and practical explanation of genetic algorithms.

• - Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming, freely available via Lulu.com, ISBN 978-1-4092-0073-4.

• - Global Optimization Algorithms - Theory and Application Archived September 11, 2008 at the Wayback Machine.

• - Degree Thesis Work.

• - Implementation of the 8 queens problem in JAVA.

Tutorials

• - Genetic Algorithms - Computer programs that "evolve" in ways that resemble natural selection can solve complex problems even their creators do not fully understand An excellent introduction to GA by John Holland and with an application to the Prisoner's Dilemma.

• - An online interactive GA tutorial for a reader to practice or learn how a GA works: Learn step by step or watch global convergence in batch, change the population size, crossover rates/bounds, mutation rates/bounds and selection mechanisms, and add constraints.

• - A Genetic Algorithm Tutorial by Darrell Whitley Computer Science Department Colorado State University An excellent tutorial with lots of theory.

• - "Essentials of Metaheuristics", 2009 (225 p). Free open text by Sean Luke.

• - Global Optimization Algorithms – Theory and Application Archived September 11, 2008 at the Wayback Machine.

Optimization problems

In a genetic algorithm, a population of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem is evolved toward better solutions. Each candidate solution has a set of properties (its chromosomes or genotypes) that can be mutated and altered. Traditionally, solutions are represented in binary as strings of zeros and ones, but other encodings are also possible.

Evolution usually starts from a population of randomly generated individuals, and is an iterative process, with the population in each iteration called a generation. In each generation, the fitness of each individual in the population is evaluated. Fitness is usually the value of the objective function in the optimization problem being solved. The fittest individuals are selected stochastically from the current population, and each individual's genome is modified (recombined "Recombination (evolutionary computing)") and possibly mutated at random) to form a new generation. The new generation of candidate solutions is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when a maximum number of generations has occurred, or a satisfactory fitness level for the population has been reached.

A typical genetic algorithm requires:

1. • A genetic representation of the solution domain.

2. • A fitness function to evaluate the mastery of the solution.

A standard representation of each candidate solution is as an array "(mathematical) Matrix") of bits. Arrays of other types and structures can be used in essentially the same way. The main property that makes these genetic representations convenient is that their parts are easily aligned due to their fixed size, which facilitates simple crossover operations. Variable length representations can also be used, but the implementation of chromosome crossing over is more complex in this case. Tree representations are explored in genetic programming and graph-like representations are explored in evolutionary programming. A mixture of both linear chromosomes and trees is explored in gene expression programming.

Once the genetic representation and fitness function are defined, a GA proceeds to initialize a population of solutions and then improve it by repetitively applying the mutation, crossover, inversion, and selection operators.

The size of the population depends on the nature of the problem, but typically contains several hundred or thousands of possible solutions. Often the initial population is generated randomly, allowing for the full range of possible solutions (the search space). Occasionally, solutions may be "seeded" in areas where optimal solutions are likely to be found.

During each successive generation, a portion of the existing population is selected to raise a new generation. Individual solutions are selected through a fitness-based process, where fitness solutions (as measured by a fitness function) are typically more likely to be selected. Certain selection methods evaluate the suitability of each solution and preferentially select the best solutions. Other methods score only a random sample of the population, as the above process can be time-consuming.

The fitness function is defined on the genetic representation and measures the quality of the represented solution. The fitness function always depends on the problem. For example, in the backpack problem we want to maximize the total value of the objects that can be put in a backpack of some fixed capacity. A representation of a solution can be an array of bits, where each bit represents a different object, and the value of the bit (0 or 1) represents whether or not the object is in the backpack. Not all representations are valid, since the size of the objects may exceed the capacity of the backpack. The fitness of the solution is the sum of values ​​of all objects in the backpack if the representation is valid, or 0 otherwise.

In some problems, it is difficult or even impossible to define the expression of physical condition. In these cases, simulation can be used to determine the value of the fitness function of a phenotype (for example, computational fluid dynamics is used to determine the air resistance of a vehicle whose shape is encoded as the phenotype) or even interactive genetic algorithms.

The next step is to generate a second generation population, from solutions selected through a combination of genetic operators: chromosomal crossing over (also called crossover or recombination) and mutation.

For each new solution that has been produced, a pair of "parent" solutions has been selected for breeding from the previously selected pool. By producing a "breeding" solution using the chromosomal crossover and mutation methods mentioned above, a new solution is created that typically shares many of the characteristics of its "parents." New parents are selected for each new brood, and the process continues until a new population of solutions of appropriate size is generated. Although breeding methods that rely on the use of two parents are more "inspired biology", some research suggests that more than two "parents" can generate higher quality chromosomes.

These processes ultimately result in the next generation of chromosome population, which is different from the initial generation. In general, the average fitness has been increased by this procedure for the population, since only the best organisms from the first generation are selected for breeding, along with a small proportion of less fit solutions. These less fit solutions ensure genetic diversity within the genetic pool of the parents and, therefore, ensure the genetic diversity of the next generation of children.

Opinion is divided on the importance of crossover versus mutation. There are many references in Fogel (2006) that support the importance of mutation-based search.

Although crossover and mutation are known as the main genetic operators, it is possible to use other operators such as reassortment, colonization-extinction or migration in genetic algorithms.

It is worth adjusting parameters such as mutation probability, crossover probability, and population size to find reasonable fits for the kind of problem you are working on. A very small mutation rate can lead to genetic drift (which is non-ergodic in nature). A recombination rate that is too high can lead to premature convergence of the genetic algorithm. Too high a mutation rate can lead to the loss of good solutions, unless elite selection is used.

This generational process is repeated until a termination condition is reached. Common termination conditions are:.

• - A solution is found that satisfies the minimum criteria.

• - A fixed number of generations is reached.

• - The assigned budget is reached (calculation time / money).

• - The fitness of the highest ranked solution is reaching or has reached a plateau such that successive iterations no longer produce better results.

• - Manual inspection.

• - Combinations of the above.

Genetic algorithms are simple to implement, but their behavior is difficult to understand. In particular, it is difficult to understand why these algorithms are often successful in generating high fitness solutions when applied to practical problems. The building block hypothesis (BBH) consists of:.

• - A description of a heuristic that performs adaptation by identifying and recombining "building blocks", that is, low-order, low-length definition schemes with above-average fitness.

• - A hypothesis that a genetic algorithm performs adaptation implicitly and efficiently by implementing this heuristic.

Goldberg describes the heuristic as follows:

Short, low-order, high-fit schemes are sampled, recombined (cross-linked), and resampled to form chains of potentially higher fitness. In a way, by working with these particular schemas (the building blocks), we have reduced the complexity of our problem. Instead of building high-performing chains by trying every conceivable combination, we build better and better chains from the best partial solutions from the last few samples.

"Because highly tuned schemes of low length and low order play such an important role in the action of genetic algorithms, we have already given them a special name: building blocks. As a child creates magnificent fortresses through the arrangement of simple wooden blocks, so does a genetic algorithm seeking to approach optimal performance through the juxtaposition of short, low-order, high-performance schemes, or building blocks."

Despite the lack of consensus regarding the validity of the building block hypothesis, it has been evaluated and used as a reference over the years. Many estimation distribution algorithms, for example, have been proposed in an attempt to provide an environment in which the hypothesis would hold. Although good results have been reported for some classes of problems, skepticism still remains regarding the generality and/or practicality of the building block hypothesis as an explanation of the efficiency of GAs. In fact, there is a reasonable amount of work that attempts to understand its limitations from the perspective of estimating distribution algorithms.

There are limitations to using a genetic algorithm compared to alternative optimization algorithms:

• - Repeated evaluation of the fitness function for complex problems is often the most prohibitive and limiting segment of artificial evolutionary algorithms. Finding the optimal solution to complex three-dimensional and multimodal problems often requires very expensive conditioning function evaluations. In real-world problems such as structural optimization problems, an evaluation of a single function may require several hours to several days of full simulation. Typical optimization methods cannot deal with these types of problems. In this case, it may be necessary to forego exact evaluation and use an approximate fitness that is computationally efficient. It is evident that the amalgamation of approximate models can be one of the most promising approaches to convincingly use GA to solve complex real-life problems.

• - Genetic algorithms do not adapt well to complexity. That is, when the number of elements exposed to mutation is large, there is often an exponential increase in the size of the search space. This makes it extremely difficult to use the technique in problems such as the design of an engine, a house, or an airplane. In order to make such problems tractable to evolutionary search, they must be decomposed into the simplest possible representation. Therefore, we typically see evolutionary algorithms encoding designs for fan blades instead of engines, construction forms instead of detailed construction plans, and airfoils instead of complete aircraft designs. The second complexity problem is the question of how to protect parts that have evolved to represent good solutions from further destructive mutation, particularly when their fitness assessment requires them to combine well with other parts.

• - The “best” solution is only in comparison to other solutions. As a result, the stopping criterion is not clear in each problem.

• - In many problems, GAs may have a tendency to converge towards local optimum or even arbitrary points rather than the global optimum of the problem. This means that they do not "know how" to sacrifice short-term fitness to gain longer-term fitness. The probability of this occurring depends on the shape of the fitness landscape: certain problems may provide an easy climb towards a global optimum, others may make it easier for the function to find the local optimum. This problem can be alleviated by using a different fitness function, increasing the mutation rate, or by using selection techniques that maintain a diverse population of solutions [12], although the free lunch theorem [13] shows that there is no general solution to this problem. A common technique for maintaining diversity is to impose a "niche penalty", in which, any group of individuals of similar similarity (niche radius) has an added penalty, which will reduce the representation of that group in subsequent generations, allowing others to be maintained in the population. This trick, however, may not be effective, depending. of the problem landscape. Another possible technique would be to simply replace part of the population with randomly generated individuals, when the majority of the population is too similar to each other. Diversity is important in genetic algorithms (and in genetic programming) because crossing a homogeneous population does not generate new solutions. In evolution strategies and evolutionary programming, diversity is not essential due to a greater dependence on mutation.

• - Operating on dynamic data sets is difficult, as genomes begin to converge early towards solutions that are no longer valid for subsequent data. Various methods have been proposed to remedy this, by increasing genetic diversity in some way and preventing early convergence, either by increasing the probability of mutation when the quality of the solution drops (called triggered hypermutation) or by occasionally introducing new randomly generated elements into the gene set (called random immigrants). Again, evolution strategies and evolutionary programming can be implemented with a so-called "coma strategy" in which parents are not maintained and new parents are selected only from offspring. This can be more effective in dynamic problems.

• - GAs cannot solve problems where the only correct measure is a right/wrong measure (such as decision problems), since there is no way to converge on the solution (no hill to climb). In these cases, a random search can find a solution as quickly as a GA. However, if the situation allows the success/failure trial to be repeated giving (possibly) different results, then the ratio of successes to failures provides an appropriate measure of fitness.

• - For specific optimization problems and problematic instances, other optimization algorithms may be more efficient than genetic algorithms in terms of convergence speed "Convergence (mathematics)"). Alternative and complementary algorithms include evolution strategies, evolutionary programming, simulated annealing, Gaussian adaptation, hill climbing and swarm intelligence (for example: ant optimization, particle swarm optimization) and methods based on integer linear programming. The suitability of genetic algorithms depends on the amount of knowledge of the problem; Well-known problems often have better, more specialized approaches.

Chromosome representation

The simplest algorithm represents each chromosome as a string of bits. Typically, numeric parameters can be represented by integers, although it is possible to use floating-point representations. Floating point representation is a natural for evolution strategies and evolutionary programming. The notion of real-valued genetic algorithms has been offered but is actually a misnomer because it does not really represent the building block theory that was proposed by John Henry Holland in the 1970s. This theory is not without support, however, based on theoretical and experimental results (see below). The basic algorithm performs crossover and mutation at the bit level. Other variants treat the chromosome as a list of numbers that are indexes in a table of statements, nodes in a linked list, hashes, objects, or any other data structure imaginable. Crossover and mutation are done to respect the boundaries of data elements. For most data types, specific variation operators can be designed. Different types of chromosome data seem to work better or worse for different specific problem domains.

When using bit number representations of integers, Gray coding is often employed. In this way, small changes in the integer can be easily affected by mutations or crossovers. This has been found to help prevent premature convergence at walls called Hamming, in which too many simultaneous mutations (or crossover events) must occur in order to change the chromosome to a better solution.

Other approaches involve using arrays of real-valued numbers instead of bit strings to represent chromosomes. The results from schema theory suggest that in general, the smaller the alphabet, the better the performance, but it was initially surprising to researchers that good results were obtained using real-valued chromosomes. This was explained as the set of real values ​​in a finite population of chromosomes as forming a virtual alphabet (when selection and recombination are dominant) with a much lower cardinality than would be expected from a floating-point representation [14] [15].

An expansion of the genetic algorithm's accessible domain problem can be obtained through the more complex coding solution of clusters by concatenation of several types of genes heterogeneously encoded on a chromosome. [16] This particular approach allows solving optimization problems that require extremely disparate definition domains for the problem parameters. For example, in cascade controller tuning problems, the structure of the inner loop controller may belong to a conventional three-parameter controller, while the outer loop could implement a linguistic controller (such as a fuzzy system) that has an inherently different description. This particular form of coding requires a specialized crossover mechanism that recombines the chromosome per section, and is a useful tool for modeling and simulation of complex adaptive systems, especially evolutionary processes.

Elitism

A practical variant of the general process of building a new population is to allow the best organisms of the current generation to be carried over to the next, unchanged. This strategy is known as elite selection and guarantees that the quality of the solution obtained by the GA will not decrease from one generation to the next.

Parallel implementations

Parallel implementations of genetic algorithms come in two flavors. Coarse-grained parallel genetic algorithms assume a population at each of the computing nodes and migration of individuals between the nodes. Parallel genetic algorithms assume an individual at each processing node that acts with neighboring individuals for selection and reproduction. Other variants, such as genetic algorithms for online optimization problems), introduce time dependence or noise into the fitness function.

Adaptive genetic algorithm

Genetic algorithms with adaptive parameters (adaptive genetic algorithms, AGAs) is another significant and promising variant of genetic algorithms. The probabilities of crossover (pc) and mutation (p.m.) largely determine the degree of accuracy of the solution and the speed of convergence that genetic algorithms can obtain. Instead of using fixed values ​​of pc and p. m., the GAs use the population information in each generation and adaptively adjust the pc and p. m. in order to maintain population diversity as well as to sustain the capacity for convergence. In AGA (adaptive genetic algorithm), the adjustment of pc and p. m. It depends on the fitness values ​​of the solutions. In CAGA (clustering-based adaptive algorithm), through the use of clustering analysis to judge the optimality states of the population, the adjustment of pc and p. m. depends on these optimization states. It can be very effective to combine GA with other optimization methods. GA tends to be pretty good at finding generally good global solutions, but pretty inefficient at finding the last few mutations to find the absolute optimum. Other techniques (such as simple hill climbing) are quite efficient at finding the absolute optimum in a limited region. Alternating GA and hill climbing can improve the efficiency of GA [citation needed] while overcoming the unsoundness of hill climbing.

This means that the rules of genetic variation may have a different meaning in the natural case. For example - provided the steps are stored in consecutive order - crossover can add a series of maternal DNA steps by adding a series of paternal DNA steps and so on. This is like adding vectors that can most likely follow a ridge in the phenotypic landscape. Therefore, the efficiency of the process can be increased by many orders of magnitude. Furthermore, the investment trader has the opportunity to place the steps in consecutive order or any other appropriate order in favor of survival or efficiency.

A variation, in which the population as a whole develops rather than its individual members, is known as genetic group recombination.

A series of variations have been developed to try to improve the performance of GAs in problems with a high degree of fitness epistasis, that is, when the fitness of a solution consists of interacting subsets of its variables. Such algorithms aim to learn (before exploiting) these beneficial phenotypic interactions. As such, they are aligned with the building block hypothesis in the adaptive reduction of disruptive recombination.

Problems that appear to be particularly suited to solution using genetic algorithms include programming problems, and many programming software packages are based on GAs. GAs have also been applied to engineering. Genetic algorithms are often applied as an approach to solving global optimization problems.

As a general rule, genetic algorithms can be useful in problem domains that have a complex fitness landscape, since mixing, that is, mutation in combination with crossover "Recombination (evolutionary computing)"), is designed to move the population further away from the local optimum than a traditional algorithm. Note that commonly used crossover operators cannot change any uniform population. Mutation alone can provide ergodicity of the overall genetic algorithm process (seen as a Markov chain).

Contenido

En 1950, Alan Turing propuso una "máquina de aprendizaje" que sería paralela a los principios de la evolución. La simulación por computadora de la evolución comenzó tan pronto como en 1954 con el trabajo de Nils Aall Barricelli"), que utilizaba la computadora en el instituto para el estudio avanzado en Princeton (Nueva Jersey) "Princeton (Nueva Jersey)"). Su publicación de 1954 no fue ampliamente notada. A partir de 1957, el australiano cuantitativo genetista Alex Fraser") publicó una serie de artículos sobre la simulación de la selección artificial de organismos con múltiples loci controlando un rasgo mensurable. A partir de estos comienzos, la simulación por ordenador de la evolución por los biólogos se hizo más común a principios de 1960, y los métodos fueron descritos en los libros de Fraser y Burnell (1970) y Crosby (1973) Las simulaciones de Fraser incluían todos los elementos esenciales de los algoritmos genéticos modernos. Además, Hans-Joachim Bremermann publicó una serie de artículos en los años sesenta que también adoptaron una población de solución a problemas de optimización, sometidos a recombinación, mutación y selección. La investigación de Bremermann también incluyó los elementos de los algoritmos genéticos modernos. Otros destacados primeros pioneros son Richard Friedberg"), George Friedman y Michael Conrad. Muchos de los primeros artículos han sido reimpresos por Fogel (1998).

Aunque Barricelli, en el trabajo que relató en 1963, había simulado la evolución de la capacidad de jugar un juego simple, la evolución artificial se convirtió en un método de optimización ampliamente reconocido como resultado del trabajo de Ingo Rechenberg y Hans-Paul Schwefel en los años 1960 y principios de 1970 - el grupo de Rechenberg fue capaz de resolver problemas complejos de ingeniería a través de estrategias de evolución.Otro enfoque fue la técnica de programación evolutiva de Lawrence J. Fogel, que se propuso para generar inteligencia artificial. La programación evolutiva utilizó originalmente máquinas de estado finito para predecir los entornos y utilizó la variación y la selección para optimizar las lógicas predictivas. Los algoritmos genéticos, en particular, se hicieron populares a través del trabajo de John Henry Holland a principios de los años setenta, y particularmente de su libro Adaptation in Natural and Artificial Systems (1975). Su trabajo se originó con estudios de autómatas celulares, conducidos por Holland y sus estudiantes en la Universidad de Míchigan. Holland introdujo un marco formalizado para predecir la calidad de la próxima generación, conocido como el teorema del esquema de Holland. La investigación en GAs permaneció en gran parte teórica hasta mediados de los años 80, cuando la primera conferencia internacional en algoritmos genéticos fue llevada a cabo en Pittsburgh, Pensilvania.

Commercial products

In the late 1980s, General Electric began selling the world's first genetic algorithm product, a mainframe-based toolbox designed for industrial processes. In 1989, Axcelis, Inc. released Evolver, the first commercial AG product for desktop computers. New York Times technology writer John Markoff wrote about Evolver in 1990, and it remained the only interactive trading algorithm until 1995. Evolver was sold to Palisade in 1997, translated into several languages, and is currently in its sixth version.

Considérese el problema de insertar signos de suma o resta entre los dígitos 9 8 7 6 5 4 3 2 1 para construir una expresión cuyo valor sea 100; no vale añadir, retirar o desordenar a los dígitos. Una solución puede ser 98+7-6+5-4+3-2-1 porque, al evaluar su valor, da exactamente 100.

Hay 9 sitios (uno antes de cada dígito) donde colocar un signo de más (+), un signo de menos (-) o nada (lo cual implicará que dos o más dígitos se unan para formar cantidades mayores; como 98 en el ejemplo anterior, donde se puso "nada" antes del 9 y antes del 8). Existen, por lo tanto, 3 a la 9 = 19683 expresiones distintas (por combinatoria) entre las cuales buscar aquellas con la suma deseada. Es posible desarrollar un algoritmo exhaustivo que las genere todas y, dada la relativa pequeñez de este ejemplo, determinar completamente todas las posibles configuraciones. Sin embargo, este reto se presta para ilustrar los pasos de un proceso genético.

Coding

There is a bijection between the strings of "trits" (ternary digits: 0, 1, 2) of length 9 and the possible sign configurations for each sum. For example, if the convention is adopted that "0" represents "nothing", "1" represents "less", and "2" represents "more", then the string of "trits" 002121211 corresponds to the solution 98+7-6+5-4+3-2-1.

Parent fields

Genetic algorithms are a subfield of:.

• - Evolutionary algorithms.

• - Evolutionary computing.

• - Metaheuristics.

• - Stochastic optimization.

• - Improvement.

Related fields

Evolutionary algorithms are a subfield of evolutionary computing.

• - Evolution strategies (ES, see Rechenberg, 1994) evolve individuals through mutation and intermediate or discrete recombination. ES algorithms are specially designed to solve problems in the real value domain. They use self-adaptation to adjust the search control parameters. The de-randomization of self-adaptation has led to the current Covariance Matrix Adaptation Evolution Strategy (CMA-ES).

• - Evolutionary programming (EP) involves populations of solutions with mutation and selection and arbitrary representations. It uses self-adaptation to adjust parameters, and may include other variation operations, such as combining information from multiple parents.

• - Estimation Distribution Algorithm (EDA) replaces traditional replay operators with model-driven operators. These models are learned from the population using machine learning techniques and represented as Probabilistic Graphical Models, from which new solutions can be sampled [45] [46] or generated from guided chromosome crossing over [47].

• - Gene expression programming (GEP) also uses populations of computer programs. These complex computer programs are encoded in simpler linear chromosomes of fixed length, which are then expressed as expression trees. Expression trees or computer programs evolve because chromosomes undergo mutation and recombination in a manner similar to canonical GA. But thanks to the special organization of GEP chromosomes, these genetic modifications always result in valid computer programs. [48].

• - Genetic programming (GP) is a related technique popularized by John Koza in which computer programs, rather than functional parameters, are optimized. Genetic programming often uses internal tree-based data structures to represent computer programs for adaptation instead of the list structures typical of genetic algorithms.

• - The genetic algorithm clustering (GGA) is an evolution of GA where the focus shifts from individual elements, as in classical GA, to groups or subsets of elements. [49] The idea behind this evolution of GA proposed by Emanuel Falkenauer is that the solution of some complex problems, such as clustering or partition problems where a set of items must be divided into a group of disjoint elements in an optimal way, would be best achieved by taking features from groups of items equivalent to genes. These types of problems include container packing, line balancing, grouping with respect to a distance measure, equal stacks, etc., in which classical GAs demonstrated poor performance. Making genes equivalent to groups involves chromosomes that are generally of variable length, and special genetic operators that manipulate entire groups of elements. For container packaging, in particular, a GGA hybridized with the Martello and Toth Dominance Criterion is possibly the best technique to date.

• - Interactive evolutionary algorithms are evolutionary algorithms that use human evaluation. They are typically applied to domains where it is difficult to design a computational fitness function, for example, evolving images, music, artistic designs, and shapes to fit the aesthetic preference of users.

• - Ant colony optimization (ACO) uses many ants (or agents) equipped with a pheromone model to traverse the solution space and find local productive areas. An estimate of the distribution algorithm is considered.

• - Particle swarm optimization (PSO) is a computational method for multiparametric optimization that also uses a population-based approach. A population (swarm) of candidate solutions (particles) moves in the search space, and the motion of the particles is influenced by both their best-known position and the best-known global position of the swarm. Like genetic algorithms, the PSO method depends on the exchange of information between members of the population. In some problems, PSO is often more computationally efficient than GAs, especially in unconstrained problems with continuous variables.

• - The Memetic algorithm (MA), often called hybrid genetic algorithm, among others, is a population-based method in which solutions are also subject to local improvement phases. The idea of ​​memetic algorithms, which unlike genes, can adapt. In some problem areas they are shown to be more efficient than traditional evolutionary algorithms.

• - Bacteriological algorithms (BA) are inspired by evolutionary ecology and, more specifically, bacteriological adaptation. Evolutionary ecology is the study of living organisms in the context of their environment, with the goal of discovering how they adapt. Its basic concept is that in a heterogeneous environment, there is no individual that fits the entire environment. Therefore, one has to reason at the population level. It is also believed that BAs could be successfully applied to complex positioning problems (cell phone antennas, urban planning, etc.) or data mining. [52].

• - The cultural algorithm (CA) consists of the population component almost identical to that of the genetic algorithm and, in addition, a knowledge component called the belief space.

• - The differential search (DS) algorithm is inspired by the migration of superorganisms.

• - Gaussian adaptation (normal or natural adaptation, abbreviated NA to avoid confusion with GA) is intended to maximize the manufacturing performance of signal processing systems. It can also be used for ordinary parametric optimization. It is based on a certain theorem valid for all regions of acceptability and all Gaussian distributions. The efficiency of NA depends on information theory and a certain efficiency theorem. Its efficiency is defined as information divided by the work necessary to obtain the information. Because NA maximizes mean fitness rather than individual fitness, the landscape smoothes out such that the valleys between peaks can disappear. Therefore, it has a certain "ambition" to avoid local peaks in the fitness landscape. NA is also good at scaling sharp ridges by adapting the moment matrix, because NA can maximize the disorder (average information) of the Gaussian while simultaneously keeping the mean fitness constant.

• - Simulated annealing (SA) is a related global optimization technique that traverses the search space by testing random mutations in an individual solution. A mutation that increases fitness is always accepted. A mutation that decreases fitness is accepted probabilistically based on the difference in fitness and a decreasing temperature parameter. In SA jargon, we talk about aiming for lowest energy rather than maximum fitness. SA can also be used within a standard GA algorithm starting with a relatively high mutation rate and decreasing over time along a given schedule.

• - Tabu search (TS) is similar to simulated annealing in that both traverse the solution space testing mutations of an individual solution. While simulated annealing generates only one mutated solution, tabu search generates many mutated solutions and moves to the solution with the lowest energy of those generated. In order to avoid loops and encourage further movement through the solution space, a tabu list of partial or complete solutions is maintained. It is prohibited to move to a solution that contains elements of the tabu list, which is updated as the solution traverses the solution space.

• - Extreme Optimization (EO), unlike GAs, which work with a population of candidate solutions, develops a single solution and makes local modifications to the worst components. This requires that an appropriate representation be selected that allows individual solution components to be assigned a measure of quality ("fitness"). The governing principle behind this algorithm is that of emergent improvement by selectively removing low-quality components and replacing them with a randomly selected component. This is decidedly at odds with a GA that selects good solutions in an attempt to make better solutions.

• - The cross entropy (CE) method generates candidate solutions using a parameterized probability distribution. The parameters are updated by minimizing the cross entropy, to generate better samples in the next iteration.

• - Reactive search optimization (RSO) advocates the integration of sub-symbolic learning techniques into search heuristics to solve complex optimization problems. The word reactive suggests a rapid response to events during searching through an internal online feedback loop for self-tuning of critical parameters. Methodologies of interest for reactive search include machine learning and statistics, particularly reinforcement learning, active or query learning, neural networks, and metaheuristics.

• - Neural networks.

• - Fuzzy logic.

• - Bayesian network.

• - Local minimum/maximum.

• - Artificial Intelligence.

• - Evolutionary Robotics").

• - Emergency "Emergency (philosophy)").

• - Cellular automaton.

• - Santillán Code").

• - Banzhaf, Wolfgang; Nordin, Peter; Keller, Robert; Francone, Frank (1998). Genetic Programming - An Introduction. San Francisco, CA: Morgan Kaufmann. ISBN 978-1558605107.

• - Bies, Robert R.; Muldoon, Matthew F.; Pollock, Bruce G.; Manuck, Steven; Smith, Gwenn; Sale, Mark E. (2006). "The Genetic Algorithm-Based, Hybrid Machine Learning Approach to Model Selection." Journal of Pharmacokinetics and Pharmacodynamics. Netherlands: Springer: 196-221.

• - Carmona, Enrique J.; Fernández, Severino (2020). Fundamentals of Evolutionary Computation. Marcombo. ISBN 978-8426727558.

• - Cha, Sung-Hyuk; Tappert, Charles C. (2009). "Genetic Algorithm for Constructing Compact Binary Decision Trees." Journal of Pattern Recognition Research. 4 (1): 1-13. doi:10.13176/11.44.

• - Eiben, Agoston; Smith, James (2003). Introduction to Evolutionary Computing. Springer. ISBN 978-3540401841.

• - Fraser, Alex S. (1957). "Simulation of Genetic Systems by Automatic Digital Computers, I. Introduction." Australian Journal of Biological Sciences. 10: 484-491.

• - Goldberg, David (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley Professional. ISBN 978-0201157673.

• - Goldberg, David (2002). The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Norwell, MA: Kluwer Academic Publishers. ISBN 978-1402070983.

• - Fogel, David. Evolutionary Computation: Toward the New Philosophy of Machine Intelligence (3rd ed.). Piscataway, NJ: IEEE Press. ISBN 978-0471669517.

• - Hingston, Philip; Barone, Luigi Michalewicz, Zbigniew (2008). Design by Evolution: Advances in Evolutionary Design. Springer. ISBN 978-3540741091.

• - Holland, John (1992). Adaptation in Natural and Artificial Systems. Cambridge, MA: MIT Press. ISBN 978-0262581110.

• - Koza, John (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: MIT Press. ISBN 978-0262111706.

• - Michalewicz, Zbigniew (1996). Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag. ISBN 978-3540606765.

• - Mitchell, Melanie (1996). An Introduction to Genetic Algorithms Cambridge, MA: MIT Press. ISBN 9780585030944.

• - Poly, R.; Langdon, W.B.; McPhee, N.F. (2008). A Field Guide to Genetic Programming. Lulu.com, freely available from the internet. ISBN 978-1-4092-0073-4.

• - Rechenberg, Ingo (1994): Evolutionsstrategie '94, Stuttgart: Fromman-Holzboog.

• - Schmitt, Lothar M; Nehaniv, Chrystopher L; Fujii, Robert H (1998), Linear analysis of genetic algorithms, Theoretical Computer Science 208: 111-148.

• - Schmitt, Lothar M (2001), Theory of Genetic Algorithms, Theoretical Computer Science 259: 1-61.

• - Schmitt, Lothar M (2004), Theory of Genetic Algorithms II: models for genetic operators over the string-tensor representation of populations and convergence to global optimality for arbitrary fitness functions under scaling, Theoretical Computer Science 310: 181-231.

• - Schwefel, Hans-Paul (1974): Numerische Optimierung von Computer-Modellen (PhD thesis). Reprinted by Birkhäuser (1977).

• - Vose, Michael (1999). The Simple Genetic Algorithm: Foundations and Theory. Cambridge, MA: MIT Press. ISBN 978-0262220583.

• - Whitley, Darrell (1994). "A genetic algorithm tutorial." Statistics and Computing. 4 (2): 65-85. Doi:10.1007/BF00175354.

Resources

• - (broken link) This website describes several genetic algorithms along with their programming codes and how they can be used to find the optimal point of a process.

• - Application of genetic algorithms to the optimization of composite material laminates.

• - A Practical Genetic Algorithm Tutorial Programming step by step a Genetic Algorithm.

• - Introduction to Genetic Algorithms with interactive Java applets.

• - Genetic algorithms tutorial Archived October 28, 2005 at the Wayback Machine.

• - A simple tutorial in Spanish about genetic algorithms.

• - Introduction to Genetic Algorithms.

• - Genetic algorithms and evolutionary computing.

• - Robot with Navigation System based on Genetic Algorithms.

• - Genetic algorithms in Ruby.

• - Arquimedex.com Simple and practical explanation of genetic algorithms.

• - Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming, freely available via Lulu.com, ISBN 978-1-4092-0073-4.

• - Global Optimization Algorithms - Theory and Application Archived September 11, 2008 at the Wayback Machine.

• - Degree Thesis Work.

• - Implementation of the 8 queens problem in JAVA.

Tutorials

• - Genetic Algorithms - Computer programs that "evolve" in ways that resemble natural selection can solve complex problems even their creators do not fully understand An excellent introduction to GA by John Holland and with an application to the Prisoner's Dilemma.

• - An online interactive GA tutorial for a reader to practice or learn how a GA works: Learn step by step or watch global convergence in batch, change the population size, crossover rates/bounds, mutation rates/bounds and selection mechanisms, and add constraints.

• - A Genetic Algorithm Tutorial by Darrell Whitley Computer Science Department Colorado State University An excellent tutorial with lots of theory.

• - "Essentials of Metaheuristics", 2009 (225 p). Free open text by Sean Luke.

• - Global Optimization Algorithms – Theory and Application Archived September 11, 2008 at the Wayback Machine.