The Creation Wiki is made available by the NW Creation Network
Watch monthly live webcast - Like us on Facebook - Subscribe on YouTube

Genetic algorithm

From CreationWiki, the encyclopedia of creation science
Jump to: navigation, search

Genetic algorithms are search methods that use computer programming to find solutions to combinatorial optimization problems using methods inspired by biological evolution. Because they were inspired by the theory of Evolution,[1] some evolutionists claim them as evidence that microbe to man evolution is possible.

The traditional theory of GA takes on a general level of description that the AG's work by discovering, emphasizing, and recombining building blocks of good solutions in a highly parallel way.[2]

Genetic algorithms differs from more normal optimization and search procedures in four ways[3]:

  • GAs work with a coding of the parameter set, not the parameters themselves.
  • GAs search from a population of points, not a single point.
  • GAs use payoff (objective function) information, not derivatives or other auxiliary knowledge.
  • GAs use probabilistic transition rules, not deterministic rules.

Genetic algorithms start with an initial population, in which the "genes" are usually random. They then follow the same basic pattern:

  1. The population is evaluated based on how well they solve the problem that the algorithm is designed to solve.
  2. The best are selected to reproduce, often with a process similar to recombination.
  3. The offspring are then mutated
  4. The process restarts at #1 unless the program termination condition has been reached.

Algorithm

The genetic algorithm is generally as described in the following algorithm:

function GeneticAlgorithm()
  initializeCurrentPopulation() //→ creates a list of individuals generally randomly
  evaluatesCurrentIndividualsOfPopulation() //→ applies the fitness function for each individual obtaining a value
  while notReachedTheStopCondition() do
     parent_list := selectParents() //→ it selects the parents of the next generation (e.g. roulette method)
     appliesCrossingOverOperator() //→ applies recombination operator (crossing-over)
     appliesMutationOperator() //→ generates mutations (important to avoid local peaks)
     extendPopulation() //→ Extend the current population adding the new generation to it  
     reducePopulation() //→ Reduce the extended population
     evaluatesCurrentIndividualsOfPopulation() //→ applies the fitness function for each individual obtaining a value
  end while 
  return the best individual of the population according to the objective function yielded

Representation

Weighted digraph represented as a chromosome

The chromosomes can be represented in various ways. The most common is the representation by a string of bits. Other representations can be strings, vectors with integer or real (for weights, for example), lists in Lisp, etc.. Another type of representation (less like biological cases) is a representation in the form of trees.

Crossing-over

The recombination procedure (crossing-over) depends on the way the data structure was constructed for chromosome.

One-point crossover

In the most common form, the chromosomes are represented as a string of bits. A more general description of this procedure is as follows:

 function recombination()
  get parents()
  selects a cutoff point // In general, randomly
  perform an exchange between the chromosome's father branch with the chromosome's mother branch
  return two new recombinant individuals

256px-Computational.science.Genetic.algorithm.Crossover.One.Point.svg.png

For example assuming the chromosomes:

011011010101010101011111011 (father)
and
111101001110110011011001100 (mother)

Picks up a cutoff point (e.g. position 8) as follows:

01101101|0101010101011111011 (father)
and
11110100|1110110011011001100 (mother)

exchanges the branches to yield two new individuals:

111101000101010101011111011 (son 1)
and
011011011110110011011001100 (son 2)

Two-point crossover

Two-point crossover use two selected points to perform the slicing of the parent organism strings. Everything between the two points is swapped between the parent organisms, rendering two child organisms:

256px-Computational.science.Genetic.algorithm.Crossover.Two.Point.svg.png

Cut and splice

In the crossover "cut and splice" approach, cutting points are selected separately for each parent. This may result in a change in length of the child organisms.

300px-Computational.science.Genetic.algorithm.Crossover.Cut.and.Splice.svg.png

Multipoint recombination

Some allow the AG's crossing over is established in more than one piece of the chromosomes.

Uniform Crossover

The uniform crossover (UX) does not use crossover points, but determines, through a global parameter, which is the probability of each variable suffer exchange between the parents. One by one the bits are compared and are exchanged depending in a previously established probability commonly 0.5.

128px-Computational.science.Genetic.algorithm.Crossover.Uniform.Crossover.svg.png

Half Uniform Crossover

In the half uniform crossover (HUX) approach, only half of the bits that are different will be exchanged. For this purpose, first it is calculated the number of different bits (Hamming distance) between the parents. The half of this number is the number of bits exchanged between parents to form the childs.

128px-Computational.science.Genetic.algorithm.Crossover.Half.Uniform.Crossover.svg.png

Methods of choice to perform chromosome crossover

To perform the recombination or crossover, two parents at a time need be chosen. Several methods are proposed for this choice among them:

  • Stochastic universal sampling The individual is selected based on their fitness. The probability of an individual being selected increases proportionally to the measure of their fitness in relation to other parent candidates. The individuals are mapped to contiguous segments of a line proportional to their fitness.
  • Roulette wheel selection (SCX) Also known as Fitness-Proportionate Selection. The individual is selected based on their fitness. The probability of an individual being selected increases proportionally to the measure of their fitness in relation to other parent candidates. It differs from stochastic uniform sampling simply by being in a roulette addict rather than a straight line.
  • Boltzmann selection Establishes a variable selection pressure according to the time of the survey solution. Initially, allows the reproduction of individuals with low fitness to maintain population diversity and avoid premature convergence. Over time, increases the selective pressure to favor more and more individuals with the highest fitness.[4]
  • Tournament selection Consists in selecting a number of individuals in the population and make them come into competition for the right to be a parent..
  • Rank selection
  • Truncation selection
  • Steady state selection
  • Local selection

Mutation

The mutation mechanism is not required for the AG's can solve various problems.[5] However, the mutations are a useful mechanism that can be used for the contour of local peaks. Currently, the mutation is a mechanism widely used, especially in modeling applications.

Purpose and Limits

While some evolutionists claim genetic algorithms as evidence that microbe to man evolution is possible, the claims are flawed on several points.

  • Many times, Genetic algorithms start with a random "gene" sets. In the real world an organism with random genes would not live. On the other hand, when genetic algorithms starts with functional and viable solutions this does not fit within the theory of evolution, which reportedly starts from amino acids that were formed in a kind of primordial soup. In the second case, it looks more like the creation model since the early types appear ready.
  • Genetic algorithms have no fatal steps. In the real world genes are complex instructional codes such that combination's that are intermediaries between two viable states can often be fatal. It is much like a computer program, in that has discrete commands, but trying to go from one command to another 1 bit at a time will cause the program to crash.
  • Genetic algorithms place the instructions for critical functions such as reproduction beyond the influence of the mutations, as such no mutation will disrupt those functions. In the real world critical functions can often be destroyed by mutations.
  • Genetic algorithms never produce new capabilities beyond what is pre-programmed into them. Microbe to man evolution requires totally new and complex capabilities to be developed many many times.
  • Genetic algorithms start with fully functional processes designed into them. Microbe to man Evolution requires these processes to be developed from scratch, but they are needed for life.
  • Genetic algorithms are designed by intelligent programmers with a specific problem in mind and fully functional from the start. To properly mimic biological evolution, the "organisms" would need:
    • The "organisms" would have to be a fully functional program, with a detailed programing language that tells it how to do every thing.
    • The "organisms" would have to develop the programing language from scratch with no input from a programmer.
    • The "organisms" would have to develop the entire operating system from scratch with no input from a programmer.
    • The "organisms" would have to develop a system to read and write the programing instructions also from scratch with no input from an intelligent agent.
    • The "organisms" would have to develop and build the computer memory and processor from scratch with no input from an intelligent agent.
  • Genetic algorithms have a narrow definition of fitness. The "fitness" of the "organism" is measured based on how well is fits a specific problem. In the real world organisms ether live or die. If they live long enough, they usually reproduce. According to Wikipedia this is a type of problem that genetic algorithms (GAs) can not effectively solve.
GAs can not effectively solve problems in which there is no way to judge the fitness of an answer other than right/wrong, as there is no way to converge on the solution. These problems are often called "needle in a haystack" problems.[6]

In a given environment an organism has two answers by which its fitness for evolution is judged: live or die (right or wrong). Thus, real world organisms have no way to converge on a solution.

Furthermore General Evolution requires an increase genetic diversity from a single cell to the vast variety of life we observes in the world, but genetic algorithms start a maximum diversity and narrow it to a solution. This actually means that genetic algorithms go in the opposite of General Evolution theory.

While some evolutionists claim genetic algorithms as evidence that microbe to man Evolution is possible, it is clear that they do not adequately represent biology and as such show nothing about plausibility of microbe to man Evolution.

Popular Evolutionist Example

One example touted by Evolutionists is an "artificial life" program called Avida[7]. Despite the claims about this program, it does not come anywhere near showing the possibility of microbe to man Evolution. One flaw is that each bit of the "genome"[8] makes up a complete command, and one that is actually encoded outside the genome; this does not fit the genomes of real organisms. According to Meyer, the program do not simulates how the information necessary to produce the first body may have originated from[9]

Unlike most genetic algorithm programs Avida[7] does include two reproduction commands as part of its "genome"[8] but they only tell the "organism" when to reproduce and what mode (sexual or asexual) to use. In both cases the actual instructions are outside the "genome"[8] and are thus unaffected by mutation. This does allow for a mutation that renders an "organism" sterile, but no mutation changes the pre-programmed instructions inside each command.

These "artificial organisms" do not develop new abilities, that are not designed into the program, but simply rearrange existing abilities. Avida[7] starts with a created kind of "organism" and only produces varieties of that organism, in perfect agreement with Creation science.

Some GA not truly mimic the nature

Many problems for which the technique of genetic algorithms can be used have a typical problem regarding the operation of crossover: elements on a chromosome can be in a different order but must be the same set of elements. A typical example of this is the use of GA for solving the traveling salesman problem. While the order of cities visited can vary, all cities must be visited. In a typical crossover, the children generated by each set of parents often ends with duplicate cities while some cities are not on the list. An example can be seen in the figure below. The two parents (p1 and p2) generate two offspring chromosomes (o1 and o2). In this example, the o1 chromosome lacks the elements 3, 5 and 7 while having the elements 1, 6 and 9 twice. The o2 chromosome lacks the elements 1, 6 and 9 while having the elements 3, 5 and 7 twice.

Ag1.png

To solve this problem several variations of crossover have been developed. It will be present two examples that keep the set elements: PMX and OX. There are other methods (e.g. cycle crossover CX, order-based crossover OBX, position-based crossover PBX, subtour exchange crossover, heuristic crossover) but for the purposes of this Article shall not be discussed here.

Partialy-mapped crossover (PMX)

Pmx.png

The PMX builds an offspring by choosing a subsequence of a tour from one parent preserving the order and position of as many positions as possible from the other parent.[10] First, a subsequence is delimited by two cut points. After this, the segments between the cut points are swapped (the positions in yellow). It was extract from the segment that was swapped a series of mappings. In the example shown: 1\leftrightarrow 8, 9\leftrightarrow 5, 8\leftrightarrow 7 and 6\leftrightarrow 3. The second step is to fill the positions for which there is no conflict. In the example shown, the positions 4 and 2 in both chromosomes (the positions in blue). The third and final step is to use the mappings to fill the remaining positions (the positions in green). Note that when using the mapping 1\leftrightarrow 8 in the vector o1 a conflict occurs again so one must apply the mapping 8\leftrightarrow 7 in order to obtain a number not repeated.

Order crossover (OX)

Ox.png

The OX builds an offspring by choosing a subsequence of a tour from one parent preserving the relative order of the positions from the other parent.[10] Using the same example of the previous algorithm it was cut the array in two points. Starting from the second point of one parent the positions of the other parent are copied in the same order, disregarding the symbols that are already present. Reaching the end of the string, one continue from the beginning of the string. In the example above, it was filled the o2 chromosome following the sequence 6\rightarrow 9\rightarrow 1\rightarrow 4\rightarrow 2\rightarrow 8\rightarrow 5\rightarrow 7\rightarrow 3 and filling the positions not yet present. It will be filled the positions showed in red: 4,2,5,7 and 3. We do the same for the o1 chromosome folowing the list 4\rightarrow 2\rightarrow 7\rightarrow 5\rightarrow 3\rightarrow 1\rightarrow 9\rightarrow 8\rightarrow 6 and filling the positions not yet present. It will be filled the positions showed in red: 4,2,1,9 and 6.

Magic square

Example of a Magic Square with n=3. The sum of the rows, columns and diagonals always results in the same number

Another example where the genetic algorithm needs to be adapted differently from what occurs on nature is the problem of finding a magic square of side n. According to Tao Xie & Lishan Kang , a simple evolutionary algorithm hardly succeeds in constructing magic squares of orders more than 10, and the evolving efficiency and the success rate are also extremely low.[11] What the authors have proposed in their paper to achieve success in generating magic squares was a genetic algorithm in two steps, the second step with heuristics designed to not destroy the sum obtained in rows and columns, again differently from what occurs in nature.[11]

Conclusion

The PMX and OX crossovers are made to deal with the problem posed at the beginning of this section. They solve the problem well avoiding duplicate or missing values​​. But this crossover mechanism is not found in cells. The crossover found in cells not have mechanisms that retain the same information in a different order such as these. Thus, these examples can not be used to support the claims of evolutionists that genetic algorithms are a computational example of how new information can be constructed in nature. If the traveling salesman problem was solved with GA using crossover found in nature it could never converge to a solution. Or would lead an extremely large time comparable to random trials. Other example of GA that do not follow the mechanisms of nature are the GA used to obtain successfully magic squares as shown previously.

References

  1. Lawrence Davis, ed. (1991). Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold. p. 2. ISBN 0-442-00173-8. 
  2. Mitchell, Melaine (2001). An Introduction to Genetic Algorithms. Cambridge, Massachusetts: The MIT Press. p. 27. ISBN 0-262-63185-7. 
  3. Goldberg, David E. (1989). Genetic Algorithms: in Search, Optimization, and Machine Learning. Reading, Massachusetts: Addison-Wesley. pp. 7. ISBN 0-201-15767-5. 
  4. Ichihara, Jorge de Araújo. "Capítulo III:Algoritmos genéticos". http://www.eps.ufsc.br/teses98/ichihara/cap3.html. Retrieved November 11, 2012. 
  5. Poli, Riccardo; Langdon, William B.; McPhee, Nicholas F.; Koza, John R. (contributor) (2008). A Field Guide to Genetic Programming. Estados Unidos da América: Editing made ​​by the authors. p. 42-43. ISBN 978-1-4092-0073-4. 
  6. Genetic algorithm By Wikipedia
  7. 7.0 7.1 7.2 Avida: The Digital Life Platform Michigan State University, Accessed March, 16 2011.
  8. 8.0 8.1 8.2 A guided tour of an ancestor and its hardware by Avida: The Digital Life Platform, Michigan State University, Accessed March 16, 2011.
  9. Meyer, Stephen C (2009). Signature in the Cell: DNA and the Evidence for Intelligent Design. New York: HarperCollins Publishers. p. 289. ISBN 978-0-06-147278-7. 
  10. 10.0 10.1 Michalewicz, Zbigniew (1996). Genetic Algorithms+Data Structures=Evolution Programs (Third, Revised and Extended ed.). Berlin/New York: Springer-Verlag. p. 216-220. ISBN 3-540-60676-9. 
  11. 11.0 11.1 Xie, Tao; Kang, Lishan (8-12 Dec. 2003). "An evolutionary algorithm for magic squares". Evolutionary Computation, 2003. CEC '03. (Changsha, China: Coll. of Comput. Sci., Nat. Univ. of Defense Technol.) 2: 906 - 913. ISBN 0-7803-7804-0. 

External Links