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:

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:.

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:.

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:

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:.

Related fields

Evolutionary algorithms are a subfield of evolutionary computing.

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:

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:.

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:.

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:

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:.

Related fields

Evolutionary algorithms are a subfield of evolutionary computing.