A genetic algorithm (GA) is a search technique used in computing to find exact or approximate solutions to optimization and search problems. Computing is usually defined like the activity of using and developing Computer technology Computer hardware and software. An approximation (represented by the symbol ≈ is an inexact representation of something that is still close enough to be useful In Mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function A problem is an obstacle which makes it difficult to achieve a desired goal objective or purpose Genetic algorithms are categorized as global search heuristics. Categorization is the process in which ideas and objects are recognized, differentiated and understood. Global optimization is a branch of Applied mathematics and Numerical analysis that deals with the optimization of a function or a set Genetic algorithms are a particular class of evolutionary algorithms (also known as evolutionary computation) that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover (also called recombination). In Artificial intelligence, an evolutionary algorithm (EA is a Subset of Evolutionary computation, a generic population-based Metaheuristic In Computer science evolutionary computation is a subfield of Artificial intelligence (more particularly Computational intelligence) that involves Evolutionary biology is a sub-field of Biology concerned with the origin of Species from a Common descent, and Descent of species In Genetic algorithms mutation is a Genetic operator used to maintain Genetic diversity from one generation of a population of chromosomes to Selection is the stage of a Genetic algorithm in which individual genomes are chosen from a population for later breeding (recombination or crossover In Genetic algorithms crossover is a Genetic operator used to vary the programming of a chromosome or chromosomes from one generation to the next

Contents 1 Methodology 1.1 Initialization 1.2 Selection 1.3 Reproduction 1.4 Termination 1.5 Pseudo-code algorithm 1.6 Observations 2 Variants 3 Problem domains 4 History 5 Related techniques 6 Building block hypothesis 7 Applications 8 References 9 External links

Methodology

Genetic algorithms are implemented as a computer simulation in which a population of abstract representations (called chromosomes or the genotype or the genome) of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem evolves toward better solutions. Implementation is the realization of an application or execution of a Plan, idea Model, Design, Specification, standard, Algorithm A computer simulation, a computer model or a computational model is a Computer program, or network of computers that attempts to simulate an In Biology a population is the collection of inter-breeding organisms of a particular Species; in Sociology In Genetic algorithms a chromosome (also sometimes called a genome) is a set of parameters which define a proposed solution to the problem that the genetic algorithm The genotype is the genetic constitution of a cell an organism or an individual (i In classical genetics the genome of a Diploid Organism including Eukarya refers to a full set of chromosomes or genes in a Gamete, thereby In optimization (a branch of Mathematics) a candidate solution is a member of a set of possible solutions to a given problem A phenotype is any observable characteristic of an Organism, such as its morphology, Development, biochemical or physiological properties Traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible. The evolution usually starts from a population of randomly generated individuals and happens in generations. In each generation, the fitness of every individual in the population is evaluated, multiple individuals are stochastically selected from the current population (based on their fitness), and modified (recombined and possibly randomly mutated) to form a new population. Stochastic (from the Greek "Στόχος" for "aim" or "guess" means Random. The new population is then used in the next iteration of the algorithm. In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population. If the algorithm has terminated due to a maximum number of generations, a satisfactory solution may or may not have been reached.

Genetic algorithms find application in bioinformatics, phylogenetics, computer science, engineering, economics, chemistry, manufacturing, mathematics, physics and other fields. Bioinformatics is the application of information technology to the field of molecular biology Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their Engineering is the Discipline and Profession of applying technical and scientific Knowledge and Economics is the social science that studies the production distribution, and consumption of goods and services. Chemistry (from Egyptian kēme (chem meaning "earth") is the Science concerned with the composition structure and properties Manufacturing (from Latin manu factura, "making by hand" is the use of tools and labor to make things for use or sale Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and Physics (Greek Physis - φύσις in everyday terms is the Science of Matter and its motion.

A typical genetic algorithm requires two things to be defined:

1. a genetic representation of the solution domain,
2. a fitness function to evaluate the solution domain. Genetic representation is a way of representing solutions/individuals in Evolutionary computation methods A fitness function is a particular type of Objective function that quantifies the optimality of a solution (that is a chromosome) in a Genetic algorithm

A standard representation of the solution is as an array of bits. A bit array (or bitmap, in some cases is an Array Data structure which compactly stores individual bits ( Boolean values. 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, that facilitates simple crossover operation. Variable length representations may also be used, but crossover implementation is more complex in this case. Tree-like representations are explored in Genetic programming and graph-form representations are explored in Evolutionary programming. In Artificial intelligence, genetic programming (GP is an Evolutionary algorithm based methodology inspired by Biological evolution to find Evolutionary programming is one of the four major Evolutionary algorithm paradigms

The fitness function is defined over the genetic representation and measures the quality of the represented solution. The fitness function is always problem dependent. For instance, in the knapsack problem we want to maximize the total value of objects that we can put in a knapsack of some fixed capacity. The knapsack problem is a problem in Combinatorial optimization. A representation of a solution might 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 knapsack. Not every such representation is valid, as the size of objects may exceed the capacity of the knapsack. The fitness of the solution is the sum of values of all objects in the knapsack if the representation is valid, or 0 otherwise. In some problems, it is hard or even impossible to define the fitness expression; in these cases, interactive genetic algorithms are used. Interactive evolutionary computation (IEC or Aesthetic Selection is a general term for methods of Evolutionary computation that use human evaluation

Once we have the genetic representation and the fitness function defined, GA proceeds to initialize a population of solutions randomly, then improve it through repetitive application of mutation, crossover, inversion and selection operators.

Initialization

Initially many individual solutions are randomly generated to form an initial population. The population size depends on the nature of the problem, but typically contains several hundreds or thousands of possible solutions. Traditionally, the population is generated randomly, covering the entire range of possible solutions (the search space). Occasionally, the solutions may be "seeded" in areas where optimal solutions are likely to be found.

Selection

Main article: Selection (genetic algorithm)

During each successive generation, a proportion of the existing population is selected to breed a new generation. Selection is the stage of a Genetic algorithm in which individual genomes are chosen from a population for later breeding (recombination or crossover Selection is the stage of a Genetic algorithm in which individual genomes are chosen from a population for later breeding (recombination or crossover Individual solutions are selected through a fitness-based process, where fitter solutions (as measured by a fitness function) are typically more likely to be selected. Fitness (often denoted w in Population genetics models is a central concept in evolutionary theory. A fitness function is a particular type of Objective function that quantifies the optimality of a solution (that is a chromosome) in a Genetic algorithm Certain selection methods rate the fitness of each solution and preferentially select the best solutions. Other methods rate only a random sample of the population, as this process may be very time-consuming.

Most functions are stochastic and designed so that a small proportion of less fit solutions are selected. Stochastic (from the Greek "Στόχος" for "aim" or "guess" means Random. This helps keep the diversity of the population large, preventing premature convergence on poor solutions. Popular and well-studied selection methods include roulette wheel selection and tournament selection. Fitness proportionate selection, also known as roulette-wheel selection, is a Genetic operator used in Genetic algorithms for selecting potentially useful Tournament selection is one of many methods of selection in Genetic algorithms which runs a "tournament" among a few individuals chosen at random from the population

Reproduction

Main articles: crossover (genetic algorithm) and mutation (genetic algorithm)

The next step is to generate a second generation population of solutions from those selected through genetic operators: crossover (also called recombination), and/or mutation. In Genetic algorithms crossover is a Genetic operator used to vary the programming of a chromosome or chromosomes from one generation to the next In Genetic algorithms mutation is a Genetic operator used to maintain Genetic diversity from one generation of a population of chromosomes to A genetic operator is a process used in Genetic algorithms to maintain Genetic diversity. In Genetic algorithms crossover is a Genetic operator used to vary the programming of a chromosome or chromosomes from one generation to the next In Genetic algorithms mutation is a Genetic operator used to maintain Genetic diversity from one generation of a population of chromosomes to

For each new solution to be produced, a pair of "parent" solutions is selected for breeding from the pool selected previously. By producing a "child" solution using the above methods of crossover and mutation, a new solution is created which typically shares many of the characteristics of its "parents". New parents are selected for each child, and the process continues until a new population of solutions of appropriate size is generated.

These processes ultimately result in the next generation population of chromosomes that is different from the initial generation. Generally the average fitness will have 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, for reasons already mentioned above.

Termination

This generational process is repeated until a termination condition has been reached. Common terminating conditions are

• A solution is found that satisfies minimum criteria
• Fixed number of generations reached
• Allocated budget (computation time/money) reached
• The highest ranking solution's fitness is reaching or has reached a plateau such that successive iterations no longer produce better results
• Manual inspection
• Combinations of the above.

Pseudo-code algorithm

1. Choose initial population
2. Evaluate the fitness of each individual in the population
3. Repeat
   1. Select best-ranking individuals to reproduce
   2. Breed new generation through crossover and mutation (genetic operations) and give birth to offspring
   3. Evaluate the individual fitnesses of the offspring
   4. Replace worst ranked part of population with offspring
4. Until termination

Observations

There are several general observations about the generation of solutions via a genetic algorithm:

• In many problems, GAs may have a tendency to converge towards local optima or even arbitrary points rather than the global optimum of the problem. In Biology a population is the collection of inter-breeding organisms of a particular Species; in Sociology Fitness (often denoted w in Population genetics models is a central concept in evolutionary theory. As commonly used, individual refers to a Person or to any specific object in a collection Reproduction is the Biological process by which new individual Organisms are produced See Breed (song for the song by Nirvana. See Breed (video game for the video game by Brat Designs Generation (from the Greek γενεά) also known as procreation, is the act of producing Offspring. In Genetic algorithms crossover is a Genetic operator used to vary the programming of a chromosome or chromosomes from one generation to the next In Genetic algorithms mutation is a Genetic operator used to maintain Genetic diversity from one generation of a population of chromosomes to In Biology, offspring are the product of Reproduction, a new Organism produced by one or more Parents Collective offspring may be known Local optimum is a term in Applied mathematics and Computer science. In Mathematics, a global optimum is a selection from a given domain which yields either the highest value or lowest value (depending on the objective when a specific This means that it does not "know how" to sacrifice short-term fitness to gain longer-term fitness. The likelihood of this occurring depends on the shape of the fitness landscape: certain problems may provide an easy ascent towards a global optimum, others may make it easier for the function to find the local optima. In Evolutionary biology, fitness landscapes or adaptive landscapes are used to visualize the relationship between Genotypes (or Phenotypes and This problem may be alleviated by using a different fitness function, increasing the rate of mutation, or by using selection techniques that maintain a diverse population of solutions, although the No Free Lunch theorem proves that there is no general solution to this problem. This figure contradicts the text of the article and uses terms that are not defined in the article A common technique to maintain diversity is to impose a "niche penalty", wherein, any group of individuals of sufficient similarity (niche radius) have a penalty added, which will reduce the representation of that group in subsequent generations, permitting other (less similar) individuals to be maintained in the population. This trick, however, may not be effective, depending on the landscape of the problem. Diversity is important in genetic algorithms (and genetic programming) because crossing over a homogeneous population does not yield new solutions. A genetic algorithm (GA is a Search technique used in Computing to find exact or Approximate solutions to optimization and Search In Artificial intelligence, genetic programming (GP is an Evolutionary algorithm based methodology inspired by Biological evolution to find In evolution strategies and evolutionary programming, diversity is not essential because of a greater reliance on mutation. In computer science evolution strategy (ES is an optimization technique based on ideas of adaptation and evolution Evolutionary programming is one of the four major Evolutionary algorithm paradigms
• Operating on dynamic data sets is difficult, as genomes begin to converge early on towards solutions which may no longer be valid for later data. Several methods have been proposed to remedy this by increasing genetic diversity somehow and preventing early convergence, either by increasing the probability of mutation when the solution quality drops (called triggered hypermutation), or by occasionally introducing entirely new, randomly generated elements into the gene pool (called random immigrants). Again, evolution strategies and evolutionary programming can be implemented with a so-called "comma strategy" in which parents are not maintained and new parents are selected only from offspring. In computer science evolution strategy (ES is an optimization technique based on ideas of adaptation and evolution Evolutionary programming is one of the four major Evolutionary algorithm paradigms This can be more effective on dynamic problems.
• GAs cannot effectively solve problems in which the only fitness measure is right/wrong, as there is no way to converge on the solution. (No hill to climb. ) In these cases, a random search may find a solution as quickly as a GA.
• Selection is clearly an important genetic operator, but opinion is divided over the importance of crossover versus mutation. Some argue that crossover is the most important, while mutation is only necessary to ensure that potential solutions are not lost. Others argue that crossover in a largely uniform population only serves to propagate innovations originally found by mutation, and in a non-uniform population crossover is nearly always equivalent to a very large mutation (which is likely to be catastrophic). There are many references in Fogel (2006) that support the importance of mutation-based search, but across all problems the No Free Lunch theorem holds, so these opinions are without merit unless the discussion is restricted to a particular problem. Dr David B Fogel (born February 2, 1964) is a pioneer in Evolutionary computation. This figure contradicts the text of the article and uses terms that are not defined in the article
• Often, GAs can rapidly locate good solutions, even for difficult search spaces. The same is of course also true for evolution strategies and evolutionary programming. In computer science evolution strategy (ES is an optimization technique based on ideas of adaptation and evolution Evolutionary programming is one of the four major Evolutionary algorithm paradigms
• For specific optimization problems and problem instantiations, simpler optimization algorithms may find better solutions than genetic algorithms (given the same amount of computation time). Alternative and complementary algorithms include evolution strategies, evolutionary programming, simulated annealing, Gaussian adaptation, hill climbing, and swarm intelligence (e. In computer science evolution strategy (ES is an optimization technique based on ideas of adaptation and evolution Evolutionary programming is one of the four major Evolutionary algorithm paradigms Simulated annealing (SA is a generic probabilistic Meta-algorithm for the Global optimization problem namely locating a good approximation to the Gaussian adaptation (GA is an Evolutionary algorithm designed for the maximization of manufacturing yield due to statistical deviation of component values of Signal In Computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. Swarm intelligence (SI is Artificial intelligence based on the Collective behavior of decentralized, self-organized systems g. : ant colony optimization, particle swarm optimization). The ant colony optimization Algorithm (ACO introduced by Marco Dorigo in 1992 in his PhD thesis is a probabilistic technique for solving computational Particle swarm optimization (PSO is a Swarm intelligence based Algorithm to find a solution to an optimization problem in a Search space, or model and
• As with all current machine learning problems it is worth tuning the parameters such as mutation probability, recombination probability and population size to find reasonable settings for the problem class being worked on. In biology mutations are changes to the Nucleotide sequence of the Genetic material of an organism A very small mutation rate may lead to genetic drift (which is non-ergodic in nature). In Population genetics, genetic drift is the accumulation of random events that change the makeup of a gene pool slightly but often compound over time A recombination rate that is too high may lead to premature convergence of the genetic algorithm. A mutation rate that is too high may lead to loss of good solutions unless there is elitist selection. There are theoretical but not yet practical upper and lower bounds for these parameters that can help guide selection.
• The implementation and evaluation of the fitness function is an important factor in the speed and efficiency of the algorithm.

Variants

The simplest algorithm represents each chromosome as a bit string. A bit is a binary digit, taking a value of either 0 or 1 Binary digits are a basic unit of Information storage and communication Typically, numeric parameters can be represented by integers, though it is possible to use floating point representations. The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French In Computing, floating point describes a system for numerical representation in which a string of digits (or Bits represents a Real number. The floating point representation is natural to evolution strategies and evolutionary programming. In computer science evolution strategy (ES is an optimization technique based on ideas of adaptation and evolution Evolutionary programming is one of the four major Evolutionary algorithm paradigms The notion of real-valued genetic algorithms has been offered but is really a misnomer because it does not really represent the building block theory that was proposed by Holland in the 1970s. This theory is not without support though, 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 which are indexes into an instruction table, nodes in a linked list, hashes, objects, or any other imaginable data structure. In Computer science, a linked list is one of the fundamental Data structures and can be used to implement other data structures An associative array (also associative container, map, mapping, hash, dictionary, finite map, and in query-processing an In its simplest embodiment an object is an allocated region of storage A data structure in Computer science is a way of storing Data in a computer so that it can be used efficiently Crossover and mutation are performed so as to respect data element boundaries. For most data types, specific variation operators can be designed. Different chromosomal data types seem to work better or worse for different specific problem domains.

When bit strings representations of integers are used, Gray coding is often employed. Name Bell Labs researcher Frank Gray introduced the term reflected binary code in his 1947 patent application remarking that the code had "as In this way, small changes in the integer can be readily effected through mutations or crossovers. This has been found to help prevent premature convergence at so called Hamming walls, 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. Theoretically, the smaller the alphabet, the better the performance, but paradoxically, good results have been obtained from using real-valued chromosomes.

A very successful (slight) variant of the general process of constructing a new population is to allow some of the better organisms from the current generation to carry over to the next, unaltered. This strategy is known as elitist selection.

Parallel implementations of genetic algorithms come in two flavours. Coarse grained parallel genetic algorithms assume a population on each of the computer nodes and migration of individuals among the nodes. Fine grained parallel genetic algorithms assume an individual on each processor node which acts with neighboring individuals for selection and reproduction. Other variants, like genetic algorithms for online optimization problems, introduce time-dependence or noise in the fitness function.

It can be quite effective to combine GA with other optimization methods. GA tends to be quite good at finding generally good global solutions, but quite inefficient at finding the last few mutations to find the absolute optimum. Other techniques (such as simple hill climbing) are quite efficient at finding absolute optimum in a limited region. Alternating GA and hill climbing can improve the efficiency of GA while overcoming the lack of robustness of hill climbing.

An algorithm that maximizes mean fitness (without any need for the definition of mean fitness as a criterion function) is Gaussian adaptation, See Kjellström 1970^[1], provided that the ontogeny of an individual may be seen as a modified recapitulation of evolutionary random steps in the past and that the sum of many random steps tend to become Gaussian distributed (according to the central limit theorem). Gaussian adaptation (GA is an Evolutionary algorithm designed for the maximization of manufacturing yield due to statistical deviation of component values of Signal Ontogeny, as opposed to Phylogeny, refers to the history of an organism from birth as opposed to its genetic makeup The central limit theorem (CLT states that the sum of a sufficiently large number of identically distributed independent Random variables each with finite

This means that the rules of genetic variation may have a different meaning in the natural case. For instance - provided that steps are stored in consecutive order - crossing over may sum a number of steps from maternal DNA adding a number of steps from paternal DNA and so on. This is like adding vectors that more probably may follow a ridge in the phenotypic landscape. Thus, the efficiency of the process may be increased by many orders of magnitude. Moreover, the inversion operator has the opportunity to place steps in consecutive order or any other suitable order in favour of survival or efficiency. inversion In the Mathematics, inversion operator can refer to the Operator which assigns the Inverse element to an element of a group (See for instance [1] or example in travelling salesman problem. The Travelling salesman problem ( TSP) in Operations research is a problem in discrete or Combinatorial optimization. )

Gaussian adaptation is able to approximate the natural process by an adaptation of the moment matrix of the Gaussian. So, because very many quantitative characters are Gaussian distributed in a large population, Gaussian adaptation may serve as a genetic algorithm replacing the rules of genetic variation by a Gaussian random number generator working on the phenotypic level. See Kjellström 1996^[2]

Population-based incremental learning is a variation where the population as a whole is evolved rather than its individual members. In Machine learning and Soft computing, population-based incremental learning (PBIL is a type of Genetic algorithm where the Genotype of an

Problem domains

Problems which appear to be particularly appropriate for solution by genetic algorithms include timetabling and scheduling problems, and many scheduling software packages are based on GAs. GAs have also been applied to engineering. Engineering is the Discipline and Profession of applying technical and scientific Knowledge and Genetic algorithms are often applied as an approach to solve global optimization problems. Global optimization is a branch of Applied mathematics and Numerical analysis that deals with the optimization of a function or a set

As a general rule of thumb genetic algorithms might be useful in problem domains that have a complex fitness landscape as recombination is designed to move the population away from local optima that a traditional hill climbing algorithm might get stuck in. In Evolutionary biology, fitness landscapes or adaptive landscapes are used to visualize the relationship between Genotypes (or Phenotypes and Local optimum is a term in Applied mathematics and Computer science. In Computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search.

History

Computer simulations of evolution started as early as in 1954 with the work of Nils Aall Barricelli, who was using the computer at the Institute for Advanced Study in Princeton, New Jersey. Nils Aall Barricelli (born 1912 died 1993 was a Norwegian-Italian mathematician The Institute for Advanced Study, located in Princeton New Jersey, United States is a center for theoretical research See also Princeton Township New Jersey, Borough of Princeton New Jersey Princeton Borough New Jersey Princeton Township New Jersey this ^{[3] [4]} His 1954 publication was not widely noticed. Starting in 1957 ^[5], the Australian quantitative geneticist Alex Fraser published a series of papers on simulation of artificial selection of organisms with multiple loci controlling a measurable trait. Alex Fraser (1923-2002 was a major innovator in the development of the computer modeling of population genetics and his work has stimulated many advances in genetic research over the past Artificial selection is the intentional breeding for certain traits or combinations of traits over others and is synonymous with " Selective breeding " From these beginnings, computer simulation of evolution by biologists became more common in the early 1960s, and the methods were described in books by Fraser and Burnell (1970)^[6] and Crosby (1973)^[7]. Fraser's simulations included all of the essential elements of modern genetic algorithms. In addition, Hans Bremermann published a series of papers in the 1960s that also adopted a population of solution to optimization problems, undergoing recombination, mutation, and selection. Bremermann's research also included the elements of modern genetic algorithms. Other noteworthy early pioneers include Richard Friedberg, George Friedman, and Michael Conrad. Many early papers are reprinted by Fogel (1998). Dr David B Fogel (born February 2, 1964) is a pioneer in Evolutionary computation. ^[8]

Although Barricelli, in work he reported in 1963, had simulated the evolution of ability to play a simple game,^[9] artificial evolution became a widely recognized optimization method as a result of the work of Ingo Rechenberg and Hans-Paul Schwefel in the 1960s and early 1970s - his group was able to solve complex engineering problems through evolution strategies ^{[10] [11] [12]}. In Artificial intelligence, an evolutionary algorithm (EA is a Subset of Evolutionary computation, a generic population-based Metaheuristic Ingo Rechenberg (born January 20 1934 in Berlin) is a German computer scientist and professor Hans-Paul Schwefel (born December 4, 1940 in Berlin) is a German Computer scientist and professor emeritus at University of Dortmund In computer science evolution strategy (ES is an optimization technique based on ideas of adaptation and evolution Another approach was the evolutionary programming technique of Lawrence J. Fogel, which was proposed for generating artificial intelligence. Dr Lawrence J Fogel (March 2 1928 - February 18 2007 was a pioneer in Evolutionary computation and human factors analysis Evolutionary programming originally used finite state machines for predicting environments, and used variation and selection to optimize the predictive logics. Evolutionary programming is one of the four major Evolutionary algorithm paradigms Genetic algorithms in particular became popular through the work of John Holland in the early 1970s, and particularly his book Adaptation in Natural and Artificial Systems (1975). John Henry Holland ( 2 February, 1929) is an American scientist and Professor of Psychology and Professor of Electrical Engineering and Computer His work originated with studies of cellular automata, conducted by Holland and his students at the University of Michigan. A cellular automaton (plural cellular automata) is a discrete model studied in computability theory, Mathematics, Theoretical biology John Henry Holland ( 2 February, 1929) is an American scientist and Professor of Psychology and Professor of Electrical Engineering and Computer The University of Michigan Ann Arbor ( U of M, U-M, UM or simply Michigan) is a top-ranked Coeducational public research Holland introduced a formalized framework for predicting the quality of the next generation, known as Holland's Schema Theorem. Holland's schema theorem is widely taken to be the foundation for explanations of the power of Genetic algorithms. Research in GAs remained largely theoretical until the mid-1980s, when The First International Conference on Genetic Algorithms was held in Pittsburgh, Pennsylvania.

As academic interest grew, the dramatic increase in desktop computational power allowed for practical application of the new technique. In the late 1980s, General Electric started selling the world's first genetic algorithm product, a mainframe-based toolkit designed for industrial processes. In 1989, Axcelis, Inc. released Evolver, the world's second GA product and the first for desktop computers. Evolver is a software package that allows users to solve a wide variety of Optimization problems using a Genetic algorithm. The New York Times technology writer John Markoff wrote^[13] about Evolver in 1990. John Markoff (born October 24, 1949) is a Journalist best known for his work at the The New York Times, and a book and series of articles

Related techniques

• Ant colony optimization (ACO) uses many ants (or agents) to traverse the solution space and find locally productive areas. The ant colony optimization Algorithm (ACO introduced by Marco Dorigo in 1992 in his PhD thesis is a probabilistic technique for solving computational While usually inferior to genetic algorithms and other forms of local search, it is able to produce results in problems where no global or up-to-date perspective can be obtained, and thus the other methods cannot be applied.

• Bacteriologic Algorithms (BA) inspired by evolutionary ecology and, more particularly, bacteriologic adaptation. Evolutionary eco\logy lies at the intersection of Ecology and Evolutionary biology. Evolutionary ecology is the study of living organisms in the context of their environment, with the aim of discovering how they adapt. Its basic concept is that in a heterogeneous environment, you can’t find one individual that fits the whole environment. So, you need to reason at the population level. BAs have shown better results than GAs on problems such as complex positioning problems (antennas for cell phones, urban planning, and so on) or data mining. ^[14]

• Cross-entropy method The Cross-entropy (CE) method generates candidates solutions via a parameterized probability distribution. The cross-entropy (CE method attributed to Reuven Rubinstein is a general Monte Carlo approach to combinatorial and continuous multi-extremal optimization The parameters are updated via cross-entropy minimization, so as to generate better samples in the next iteration.

• 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. Cultural algorithms (CA are a branch of Evolutionary computation where there is a knowledge component that is called the belief space in addition to the Population

• Evolution strategies (ES, see Rechenberg, 1971) evolve individuals by means of mutation and intermediate and discrete recombination. In computer science evolution strategy (ES is an optimization technique based on ideas of adaptation and evolution ES algorithms are designed particularly to solve problems in the real-value domain. They use self-adaptation to adjust control parameters of the search.

• Evolutionary programming (EP) involves populations of solutions with primarily mutation and selection and arbitrary representations. Evolutionary programming is one of the four major Evolutionary algorithm paradigms They use self-adaptation to adjust parameters, and can include other variation operations such as combining information from multiple parents.

• Extremal optimization (EO) Unlike GAs, which work with a population of candidate solutions, EO evolves a single solution and makes local modifications to the worst components. Extremal Optimization (EO is an optimization heuristic inspired by the Bak-Sneppen model of Self-organized criticality from the field of statistical In Computer science, local search is a Metaheuristic for solving computationally hard optimization problems This requires that a suitable representation be selected which permits individual solution components to be assigned a quality measure ("fitness"). The governing principle behind this algorithm is that of emergent improvement through 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.

• Gaussian adaptation (normal or natural adaptation, abbreviated NA to avoid confusion with GA) is intended for the maximisation of manufacturing yield of signal processing systems. Gaussian adaptation (GA is an Evolutionary algorithm designed for the maximization of manufacturing yield due to statistical deviation of component values of Signal It may also be used for ordinary parametric optimisation. It relies on a certain theorem valid for all regions of acceptability and all Gaussian distributions. The efficiency of NA relies on information theory and a certain theorem of efficiency. Its efficiency is defined as information divided by the work needed to get the information^[15]. Because NA maximises mean fitness rather than the fitness of the individual, the landscape is smoothed such that valleys between peaks may disappear. Therefore it has a certain “ambition” to avoid local peaks in the fitness landscape. NA is also good at climbing sharp crests by adaptation of the moment matrix, because NA may maximise the disorder (average information) of the Gaussian simultaneously keeping the mean fitness constant. Fitness (often denoted w in Population genetics models is a central concept in evolutionary theory.

• Genetic programming (GP) is a related technique popularized by John Koza in which computer programs, rather than function parameters, are optimized. In Artificial intelligence, genetic programming (GP is an Evolutionary algorithm based methodology inspired by Biological evolution to find John R Koza is a Computer scientist and a consulting professor at Stanford University, most notable for his work in pioneering the use of Genetic programming Genetic programming often uses tree-based internal data structures to represent the computer programs for adaptation instead of the list structures typical of genetic algorithms. In Computer science, a tree is a widely-used Data structure that emulates a Tree structure with a set of linked nodes A data structure in Computer science is a way of storing Data in a computer so that it can be used efficiently In Computer science, a list is an ordered collection of entities / Items In the context of Object-oriented programming languages

• Grouping Genetic Algorithm (GGA) is an evolution of the GA where the focus is shifted from individual items, like in classical GAs, to groups or subset of items. ^[16] The idea behind this GA evolution proposed by Emanuel Falkenauer is that solving some complex problems, a. k. a. clustering or partitioning problems where a set of items must be split into disjoint group of items in an optimal way, would better be achieved by making characteristics of the groups of items equivalent to genes. These kind of problems include Bin Packing, Line Balancing, Clustering w. In Computational complexity theory, the bin packing problem is a combinatorial NP-hard problem r. t. a distance measure, Equal Piles, etc. , on which classic GAs proved to perform poorly. Making genes equivalent to groups implies chromosomes that are in general of variable length, and special genetic operators that manipulate whole groups of items. For Bin Packing in particular, a GGA hybridized with the Dominance Criterion of Martello and Toth, is arguably the best technique to date. In Computational complexity theory, the bin packing problem is a combinatorial NP-hard problem

• Harmony search (HS) is an algorithm mimicking musicians behaviors in improvisation process. Harmony search (HS is a Metaheuristic algorithm (also known as Soft computing algorithm or Evolutionary algorithm) mimicking the improvisation process

• Interactive evolutionary algorithms are evolutionary algorithms that use human evaluation. Interactive evolutionary computation (IEC or Aesthetic Selection is a general term for methods of Evolutionary computation that use human evaluation They are usually applied to domains where it is hard to design a computational fitness function, for example, evolving images, music, artistic designs and forms to fit users' aesthetic preference.

• Memetic algorithm (MA), also called hybrid genetic algorithm among others, is a relatively new evolutionary method where local search is applied during the evolutionary cycle. Memetic algorithms (MA represent one of the recent growing areas of research in evolutionary computation The idea of memetic algorithms comes from memes, which–unlike genes–can adapt themselves. A meme (miːm consists of any idea or behavior that can pass from one person to another by learning or imitation In some problem areas they are shown to be more efficient than traditional evolutionary algorithms.

• Simulated annealing (SA) is a related global optimization technique that traverses the search space by testing random mutations on an individual solution. Simulated annealing (SA is a generic probabilistic Meta-algorithm for the Global optimization problem namely locating a good approximation to the A mutation that increases fitness is always accepted. A mutation that lowers fitness is accepted probabilistically based on the difference in fitness and a decreasing temperature parameter. In SA parlance, one speaks of seeking the lowest energy instead of the maximum fitness. SA can also be used within a standard GA algorithm by starting with a relatively high rate of mutation and decreasing it over time along a given schedule.

• Stochastic optimization is an umbrella set of methods that includes GAs and numerous other approaches. Stochastic optimization (SO methods are optimization Algorithms which incorporate probabilistic (random elements either in the problem data (the

• Tabu search (TS) is similar to Simulated Annealing in that both traverse the solution space by testing mutations of an individual solution. Tabu search is a mathematical optimization method belonging to the class of local search techniques 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 prevent cycling and encourage greater movement through the solution space, a tabu list is maintained of partial or complete solutions. It is forbidden to move to a solution that contains elements of the tabu list, which is updated as the solution traverses the solution space.

Building block hypothesis

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

1. A description of an abstract adaptive mechanism that performs adaptation by recombining "building blocks", i. e. low order, low defining-length schemata with above average fitness.
2. A hypothesis that a genetic algorithm performs adaptation by implicitly and efficiently implementing this abstract adaptive mechanism.

(Goldberg 1989:41) describes the abstract adaptive mechanism as follows:

Short, low order, and highly fit schemata are sampled, recombined [crossed over], and resampled to form strings of potentially higher fitness. In Mathematics, in the field of Genetic algorithms a schema, schemata or Holland schemata is a template that identifies a Subset In Genetic algorithms crossover is a Genetic operator used to vary the programming of a chromosome or chromosomes from one generation to the next In a way, by working with these particular schemata [the building blocks], we have reduced the complexity of our problem; instead of building high-performance strings by trying every conceivable combination, we construct better and better strings from the best partial solutions of past samplings.

Just as a child creates magnificent fortresses through the arrangement of simple blocks of wood [building blocks], so does a genetic algorithm seek near optimal performance through the juxtaposition of short, low-order, high-performance schemata, or building blocks.

(Goldberg 1989) claims that the building block hypothesis is supported by Holland's schema theorem. Holland's schema theorem is widely taken to be the foundation for explanations of the power of Genetic algorithms.

The building block hypothesis has been sharply criticized on the grounds that it lacks theoretical justification and experimental results have been published that draw its veracity into question. On the theoretical side, for example, Wright et al. state that

"The various claims about GAs that are traditionally made under the name of the building block hypothesis have, to date, no basis in theory and, in some cases, are simply incoherent"^[17]

On the experimental side uniform crossover was seen to outperform one-point and two-point crossover on many of the fitness functions studied by Syswerda. ^[18] Summarizing these results, Fogel remarks that

"Generally, uniform crossover yielded better performance than two-point crossover, which in turn yielded better performance than one-point crossover"^[19]

Syswerda's results contradict the building block hypothesis because uniform crossover is extremely disruptive of short schemata whereas one and two-point crossover are more likely to conserve short schemata and combine their defining bits in children produced during recombination.

The debate over the building block hypothesis demonstrates that the issue of how GAs "work", (i. e. perform adaptation) is currently far from settled. (See the External Links section for more about this)

Applications

• Artificial Creativity
• Automated design, including research on composite material design and multi-objective design of automotive components for crashworthiness, weight savings, and other characteristics. Computational creativity (also known as artificial creativity, mechanical creativity or creative computation) is a multidisciplinary endeavour that is located Automation ( Ancient Greek: = self dictated) roboticization or industrial automation or Numerical control is the use of Control systems Composite materials (or composites for short are engineered Materials made from two or more constituent materials with significantly different physical or chemical Crashworthiness is the ability of a structure to protect its occupants during an impact
• Automated design of mechatronic systems using bond graphs and genetic programming (NSF). Mechatronics (or Mecha nical and Elec' tronics' Engineering) is the combination of Mechanical engineering, Electronic engineering A bond graph is a graphical description of a physical dynamic system. In Artificial intelligence, genetic programming (GP is an Evolutionary algorithm based methodology inspired by Biological evolution to find
• Automated design of industrial equipment using catalogs of exemplar lever patterns.
• Automated design of sophisticated trading systems in the financial sector.
• Building phylogenetic trees. A phylogenetic tree, also called an evolutionary tree, is a tree showing the Evolutionary relationships among various biological Species or other ^[20]
• Calculation of Bound states and Local-density approximations. In Physics, a bound state is a composite of two or more building blocks ( particles or bodies) that behaves as a single object The local-density approximation (LDA is an approximation of the exchange - correlation (XC energy functional in Density functional theory (DFT by taking
• Chemical kinetics (gas and solid phases)
• Configuration applications, particularly physics applications of optimal molecule configurations for particular systems like C60 (buckyballs). "C60" and "C-60" redirect here For other uses see C60 (disambiguation.
• Container loading optimization.
• Code-breaking, using the GA to search large solution spaces of ciphers for the one correct decryption. Cryptanalysis (from the Greek kryptós, "hidden" and analýein, "to loosen" or "to untie" is the study of methods for In Cryptography, a cipher (or cypher) is an Algorithm for performing Encryption and Decryption &mdash a series of well-defined steps
• Design of water distribution systems.
• Distributed computer network topologies. Topology ( Greek topos, "place" and logos, "study" is the branch of Mathematics that studies the properties of
• Electronic circuit design, known as Evolvable hardware. Evolvable hardware (EH is a new field about the use of Evolutionary algorithms (EA to create Electronics.
• File allocation for a distributed system. Distributed computing deals with Hardware and Software Systems containing more than one processing element or Storage element concurrent
• Parallelization of GAs/GPs including use of hierarchical decomposition of problem domains and design spaces nesting of irregular shapes using feature matching and GAs. Parallel computing is a form of computation in which many instructions are carried out simultaneously operating on the principle that large problems can often A problem domain is a domain where the Parameters defining the boundaries of the domain and sufficient Mappings into a Set of Ranges including Nesting refers to the process of efficiently Manufacturing parts from flat Raw material.
• Game Theory Equilibrium Resolution. Game theory is a branch of Applied mathematics that is used in the Social sciences (most notably Economics) Biology, Engineering,
• Gene expression profiling analysis. ^[21]
• Learning Robot behavior using Genetic Algorithms. A robot is a mechanical or Virtual Artificial agent In practice it is usually an electro-mechanical system which by its appearance or movements
• Learning fuzzy rule base using genetic algorithms.
• Linguistic analysis, including Grammar Induction and other aspects of Natural Language Processing (NLP) such as word sense disambiguation. Grammatical induction, also known as grammatical inference or Syntactic pattern recognition, refers to the process in Machine learning of inducing a Natural language processing ( NLP) is a subfield of Artificial intelligence and Computational linguistics.
• Marketing Mix Analysis
• Mobile communications infrastructure optimization. In Mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function
• Molecular Structure Optimization (Chemistry).
• Multiple criteria production scheduling. ^[22]
• Multiple population topologies and interchange methodologies. Topology ( Greek topos, "place" and logos, "study" is the branch of Mathematics that studies the properties of Methodology (also called manner) is defined as "the analysis of the principles of methods rules and postulates employed by a discipline"

• Operon prediction. An operon is a functioning unit of key Nucleotide sequences including an operator, a common Promoter, and one or more structural Genes, ^[23]
• Optimisation of data compression systems, for example using wavelets.
• Pop music record producer^[24]. Pop music as a genre features a noticeable rhythmic element catchy melodies and hooks, a mainstream style and conventional structure
• Protein folding and protein/ligand docking. Protein folding is the physical process by which a Polypeptide folds into its characteristic and functional three-dimensional structure. In the field of Molecular modeling, docking is a method which predicts the preferred orientation of one molecule to a second when bound to each other to form ^[25]
• Plant floor layout.
• Representing rational agents in economic models such as the cobweb model. The cobweb model or cobweb theory is an Economic model that explains why Prices might be subject to periodic fluctuations in certain types of Markets
• Bioinformatics: RNA structure prediction. Bioinformatics is the application of information technology to the field of molecular biology Ribonucleic acid ( RNA) is a Nucleic acid that consists of a long chain of Nucleotide units ^[26]

• Bioinformatics: [Multiple Sequence Alignment]. Bioinformatics is the application of information technology to the field of molecular biology ^[27]. SAGA is available on: [2].

• Bioinformatics Multiple sequence alignment. Bioinformatics is the application of information technology to the field of molecular biology A multiple sequence alignment (MSA is a Sequence alignment of three or more Biological sequences generally Protein, DNA, or RNA ^[28]

• Scheduling applications, including job-shop scheduling. The objective being to schedule jobs in a sequence dependent or non-sequence dependent setup environment in order to maximize the volume of production while minimizing penalties such as tardiness.
• Selection of optimal mathematical model to describe biological systems.
• Software engineering
• Solid waste management. Software engineering is the application of a systematic disciplined quantifiable approach to the development operation and maintenance of Software.
• Fast food drive-thrus.
• Solving the machine-component grouping problem required for cellular manufacturing systems. Cellular Manufacturing is a model for workplace Design, and is an integral part of Lean manufacturing systems
• Tactical asset allocation and international equity strategies.
• Timetabling problems, such as designing a non-conflicting class timetable for a large university.
• Training artificial neural networks when pre-classified training examples are not readily obtainable (neuroevolution). An artificial neural network (ANN, often just called a "neural network" (NN is a Mathematical model or Computational model based on Biological neural Neuroevolution, or neuro-evolution, is a form of Machine learning that uses Genetic algorithms to train artificial neural networks.
• Traveling Salesman Problem. The Travelling salesman problem ( TSP) in Operations research is a problem in discrete or Combinatorial optimization.
• Finding hardware bugs. ^{[29] [30]}

References

External links

• Using Genetic Algorithms A commercial site.

• Introduction to Genetic Algorithms with interactive Java applets For experimenting with GAs online

• ParadisEO A powerful C++ framework dedicated to the reusable design of metaheuristics, included genetic algorithms.

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

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

• A Fortran code (PIKAIA) with a tutorial by Paul Charbonneau and Barry Knapp, National Center for Atmospheric Research. An excellent tutorial and a versatile public domain code. PIKAIA is also available in a version for Microsoft Excel, as well as a parallel processing version.
• VectorGA A vectorized implementation of a genetic algorithm in Matlab.
• The Dubious History of the Building Block Hypothesis
• Genetic Algorithms in Ruby
• Cross discipline example applications for GAs with references.
• Global Optimization Algorithms - Theory and Application
• Multiobjective Optimization of SLA-aware Service Composition

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic