Genetic algorithm (GA)
A genetic algorithm (GA) is a computational method inspired by Charles Darwin's theory of natural selection, designed to find optimal solutions to complex problems. It operates by simulating the evolutionary process, where a population of potential solutions undergoes cycles of evaluation, selection, crossover, and mutation. The initial population consists of randomly generated solutions, which are evaluated for their fitness levels, determining how well they address the problem at hand. The more fit solutions are selected to "mate," producing offspring that ideally inherit the best traits from their parents, thus creating potentially superior solutions.
GAs consist of six main steps: initialization, evaluation, selection, crossover, mutation, and repetition, allowing them to refine solutions over multiple generations. This approach is particularly beneficial in fields like engineering and scheduling, where traditional problem-solving methods may be impractical due to the complexity and number of possible solutions. While GAs can rapidly generate a variety of solutions, they can still be time-consuming and may not always yield the optimal solution without human input. Overall, GAs represent a powerful tool for tackling intricate problems by leveraging principles of evolution and adaptation.
On this Page
Genetic algorithm (GA)
A genetic algorithm (GA) is a program, or a set of rules, a computer uses to solve a complicated problem by mimicking Charles Darwin's theory of evolution involving natural selection. A GA can be used to solve very complex problems with many solutions when solving such a problem manually is too time-consuming.
In very basic terms, a GA has a pool of possible solutions to a problem. These solutions are called a "population." Solutions are chosen based on their "fitness level," or how well they solve the problem. Two fit solutions are given a chance to "mate" and produce "children." It is hoped that the children—the new solutions—will be even better than the originals. The process can continue until near-optimal solutions are found. A GA is advantageous because it quickly generates a list of potential solutions, as opposed to just one solution.
GAs were invented by John Holland in the 1960s and were developed by Holland and his students at the University of Michigan. Holland did not originally create GAs to solve problems; he simply wanted to incorporate the mechanisms of natural adaptation into computer programming. Holland describes his process in his book Adaptation in Natural and Artificial Intelligence (1975; revised in 1992). One of Holland's students, John Koza, became one of the first to come up with commercial applications for GAs. Koza wrote several books about genetic programming and was the founder of a company called Scientific Games.
GAs are commonly used in engineering to design products such as aircraft wings. They can also be used to find solutions to very complicated scheduling problems. NASA (National Aeronautics and Space Administration) used GAs to design antennas for its Space Technology 5 Project in which three micro-satellites explored Earth's magnetic fields.
Background
A genetic algorithm (GA) is a kind of evolutionary algorithm (EA), a program designed to advance and perfect itself. Both GAs and EAs get their names from Charles Darwin's Theory of Evolution by Natural Selection (1959). Darwin studied birds he called finches on the Galapagos Islands, a group of fourteen major islands and many smaller islands in the Pacific Ocean off the coast of Ecuador. The Galapagos Islands are isolated from Ecuador and other countries in South America. However, scientists believe that wind and sea currents moved seeds, insects, and possibly birds and animals onto the island. The birds Darwin observed may have been migrating when some of them were blown onto islands by strong wind. Groups of birds landed on different islands, where they were isolated from each other. Over time, the birds developed a beak shape and type that was best suited for the food on their island. Some developed longer, narrower beaks that they used to pick insects out of trees. Others developed stronger, shorter beaks that they used to easily crack nuts.
According to Darwin, the "fittest" birds on each island were the birds with the kind of beak that allowed them to get the most food. The fittest birds survived and thrived. The birds that did not have the proper beak could not get enough food and died.
A GA is based on Darwin's theory. It chooses the "fittest" solutions to a problem and merges them, creating a new and better solution. Solutions that are not fit are not used.
Overview
A genetic algorithm (GA) is a computer program inspired by natural selection that is used to generate optimal (the best) solutions to a problem. A GA has six steps: (1) initialization, (2) evaluation, (3) selection, (4) crossover, (5) mutation, (6) repetition.
A GA begins with initialization when the initial solutions are randomly generated. These solutions make up the population. A population can be any size but most are enormous and include thousands of solutions. Computer programmers usually represent each solution using an array of bits, which is a series of zeroes and ones.
During evaluation, each member of the population is rated and given a fitness level. The higher a solution's fitness level, the better the solution is. The criteria for determining a fitness level may be simple or complex. The time needed to evaluate solutions using simple criteria is much less than the time needed to evaluate solutions using complex criteria. If determining the fitness level for each member of a population is too time-consuming, a programmer might do this for only a random sample.
During selection, the poor solutions—those with low fitness levels—are disregarded and the best solutions are chosen.
Crossover is similar to reproduction. Two "parents" merge to create "children." The parents are two fit solutions; the children are new solutions. It is hoped that the best traits of each parent will be passed on to the children. The goal of crossover is to create solutions that are more fit than the originals.
Mutation adds randomness to the genetics. It makes very small random changes to the parent solutions. This eliminates an outcome of many identical children. Mutation is vital in ensuring that a new population is genetically diverse.
Most GAs are repeated, or run more than once. In other words, the new population that was generated from a GA undergoes evaluation, selection, and so on. Each population is called a generation.
A computer programmer will usually end a GA when a solution is found that is "good enough" depending on the amount of time the programmer has available. A GA is also terminated when an entire population has an acceptable fitness level.
A drawback to GAs is that even though running them is much faster than making manual computations (which may be impossible depending on the complexity of the problem), they are still time-consuming. Another problem is that the sometimes generate many acceptable solutions but not an optimal solution. Overcoming this usually requires human intervention.
Bibliography
Alam, Shafiq. Biologically-Inspired Techniques for Knowledge Discovery and Data Mining. Information Science Reference, 2014.
Dyer, Daniel W. "Chapter 1. The Power of Evolution." Evolutionary Computation in Java, 2010, http://watchmaker.uncommons.org/manual/. Accessed 12 May 2017.
"Genetic Algorithm." Mathworks, 2017. https://www.mathworks.com/discovery/genetic-algorithm.html, Accessed 12 May 2017.
"Genetic Algorithms – Introduction." Tutorials Point, https://www.tutorialspoint.com/genetic‗algorithms/genetic‗algorithms‗introduction.htm. Accessed 19 May 2017.
Jacobson, Lee. "Creating a Genetic Algorithm for Beginners." The Project Spot. 12 Feb. 2012, http://www.theprojectspot.com/tutorial-post/creating-a-genetic-algorithm-for-beginners/3. Accessed 19 May 2017.
Streichert, Felix. "Introduction to Evolutionary Algorithms." University of Tuebingen, http://www.ra.cs.uni-tuebingen.de/mitarb/streiche/publications/Introduction‗to‗Evolutionary‗Algorithms.pdf, Accessed 12 May 2017.
Than, Ker. "What Is Darwin's Theory of Evolution?" LiveScience, 2015, http://www.livescience.com/474-controversy-evolution-works.html. Accessed 12 May 2017.
"The Importance of Algorithms." Topcoder, 2016, https://www.topcoder.com/community/data-science/data-science-tutorials/the-importance-of-algorithms/. Accessed 12 May, 2017.
"Types of Algorithms." Stern.Nyu.edu, http://community.stern.nyu.edu/om/faculty/pinedo/scheduling/shakhlevich/handout09.pdf. Accessed 12 May 2017.
"What Is an Algorithm?" BBC, 2017. http://www.bbc.co.uk/guides/z3whpv4#zqs49j6, Accessed 12 May 2017.
"What Is an Evolutionary Algorithm?" University of Amsterdam, http://www.cs.vu.nl/~gusz/ecbook/Eiben-Smith-Intro2EC-Ch2.pdf. Accessed 12 May 2017.