Talk:Genetic algorithm

From Wikipedia, the free encyclopedia

	MCB Portal This article is within the scope of the Molecular and Cellular Biology WikiProject. To participate, visit the WikiProject for more information. The current monthly improvement drive is Signal transduction.
Article Grading: The article has not been rated for quality and/or importance yet. Please rate the article and then leave comments here to explain the ratings and/or to identify the strengths and weaknesses of the article..

Doesn't Hubert Dreyfus include genetic algoritms in his 'Strong AI' category, together with neural nets?

Have his 'anti-Strong AI' fellow-travellers John Searle or Roger Penrose ever commented on this?

ericross

---

I was reading this sentence and I don't think it makes sense. "Genetic programming algorithms typically require running time that is orders of magnitude greater than that for genetic algorithms, but they may be suitable for problems that are intractable with genetic algorithms."

Shouldn't the two instances of "genetic algorithms" (one immediately before the comma and the last one) be "non-genetic algorithms"?

I have a feeling that I've somehow misunderstood the topic.. Neoncow 20:53, 5 Oct 2004 (UTC)

"Genetic programming" (GP) is different from "genetic algorithms" (GA) due to historical nomenclature. The sentence is supposed be comparing GPs with GAs, but it's very ambiguous as written. I'll rewrite it. --Lexor|Talk 07:03, 6 Oct 2004 (UTC)

Could this bit of jargon be merged here? Building block hypothesis--nixie 00:50, 23 Mar 2005 (UTC)

The building block hypothesis is not accepted by all people in the field, and is best to remain in its own article. A reference to some of the theoretical hypotheses and observations could possibly be put here (there are some getting lost in the text), only having the BB hypothesis would not be NPOV --Anthony Liekens 02:51, 25 August 2005 (UTC)

Contents 1 Some problems 2 Related techniques 3 Building block hypothesis 4 History of genetic algorithms 5 Observation removed from the main page 6 Local search ?! 7 See Also 8 References 9 GA's now important in statistical experimental design

[edit] Some problems

This article was a very good overview of GAs. But I thought this sentence was a bit misleading:

The pool is sorted, with those having better fitness (representing better solutions to the problem) ranked at the top.

Although fitness numbers serve to rank individuals, actually sorting them is a very expensive process, rarely done in practice. Roulette and tournament selection were both designed to choose higher ranked individuals stochastically, without the need for explicit sorting. --Bytefield 15:06, 23 July 2005 (UTC)

---

I'm sorry, but you're completely wrong: while the Roulette and the Tournament indeed are faster than a complete sort, the sort of even thousands of individuals takes microseconds these days, i.e. is completely irrelevant w.r.t. the computation time for the genetic operators and the evaluation function. The real reason for the Roulette or the Tournament is not their speed, but the fact that they do not "sort" the individuals completely: they leave a small chance for underperforming individuals to end up near the top. This is crucial in avoiding premature convergence, as it gives a chance to reproduce even to individuals that seem no good. Why? Well because we do not know whether they are really "no good" (remember, these are combinatorial problems!). -- EF (efalkena@ulb.ac.be)

---

GAs can rapidly locate good solutions, even for difficult search spaces.

This observation is overly optimistic and general. It should be more carefully worded or more specific. It would be interesting to give an example of a "difficult search space" where GA performs well and alternative methods fail.

---

Agree completely: GAs are by no means guaranteed to "rapidly locate" anything, even in simple search spaces.
The point is, a GA's encoding and operators must be adapted to the search space (i.e. the cost function) it works with to function properly. It must exploit any inherent structure the cost function has. Failing that, the GA will fail lamentably - but succeding that, it will probably beat any other method on that function. --EF (efalkena@ulb.ac.be)

---

I think this sentence should be reconsidered:

Unless the fitness function is handled properly, GAs may have a tendency to converge towards local optima rather than the global optimum of the problem.

I wouldn't say the problem of premature convergence is really due to improper 'handling' of the fitness function (what does 'handled properly' mean anyway?). Perhaps someone with more expertise in this subject could elaborate further, in my experience its the genetic operations that can 'handle' this problem and ensure diverse search across the search space.

To go further, one could mention that premature convergence to a local minima is less an issue in GA than it is in other approaches (gradient search, simulating annealing, etc). -- RK

---

I think I've corrected the first and third problems. I agree with the second one mentioned, but didn't know what to replace it with. — Asbestos | Talk (RFC) 17:12, 23 January 2006 (UTC)

---

[edit] Related techniques

The section on Tabu states that it "moves to the solution with the lowest fitness of those generated". This really sounds wrong and I think it should be "removes the solution with the lowest fitness". I am not an expert but "The enhanced evolutionary tabu search and its application to the quadratic assignment problem" by John F. McLoughlin, III and Walter Cedeño seems to imply this, as well as "The niching method for obtaining global optima and local optima in multimodal functions" by Masako Himeno and Ryutaro Himeno. The both state that the lowest fitness solution is replaced by a new one.

Another problem is that this text is repeated verbatim across several articles, including Ant colony optimization. I think there needs to be a single "List of localized optimization techniques" referenced from GA, AOC, etc. --Jdz 22:14, 21 February 2006 (UTC)

[edit] Building block hypothesis

This section may need attention. The quote appears to suggest that crossover is used in genetic algorithms to generate variation.

My understanding is that the function of crossover (sexual reproduction) in nature is to cross in sections of genetic code with mutations resulting in advantageous variations and cross out corresponding disadvantageous variations. By recombining two copies of a gene via crossover, the genetic carrier is made more robust to random variation which might result in corrupt code (since both copies would need to be corrupt in the same place to completely corrupt the genetic code). Thus crossover is in fact a way of limiting the effect of variation through mutation and collecting random variations which have increased fitness into a single sequence of genetic code, not a means of generating variation in that code.

I added a link here to Holland's Schema Theorem. I think the author's meaning of this section is to give a hypothesis for why GAs work. The GA uses 'building blocks' or schemas (high fitness but undefined parts of a solution) to 'build' the optimal solution. These schemas then become more frequent in each subsequent generation. The article gives the formula. To make it more complete though, you'd have to dive into literature to find out what is written on the matter, starting with Holland and Goldberg, I guess. 145.53.202.88 11:13, 16 November 2006 (UTC)

[edit] History of genetic algorithms

The history given here credits Holland for introducing genetic algorithms. This is a common misunderstanding. Holland certainly widely publicized these methods among computer scientists, and he did introduce his Schema Theorem. His influence was great. But genetic simulations of evolution had been going on since Barricelli's work of 1954 and Alex Fraser's work of 1957. There were others in that period too: see David Fogel's collection of reprinted papers: 'Evolutionary Computation: The Fossil Record".

In fact by the early 1960's there were many papers in the population genetics literature using simulated evolution, methods that cannot be distinguished from genetic algorithms (they have genotypes, fitnesses, mutation, and recombination). There were even two whole books on how to do genetic algorithms published well before Holland's in 1975:

• Fraser, A. S. and D. Burnell. 1970. Computer Models in Genetics. McGraw-Hill, New York.
• Crosby, J. 1973. Computer Simulation in Genetics. Wiley, New York.

If Holland invented the method, how do we account for its appearance in those books, and the many papers? Even if one restricts the definition of GA to attempts to solve some design problem outside of biology, Nils Aall Barricelli's work did that too.

I would appreciate any reactions. Perhaps I am missing some restriction of the definition of GA that would rule out Fraser's and Barricelli's work (and all the others), and I want to make sure this is acceptable before I modify the Wikipedia entry. -- Joe Felsenstein (whose 1974 paper on evolution of recombination used simulated evolution, and that too is before Holland)

Go ahead, your contribution is welcome. But do read WP:NOR first—if a Wikipedia entry is based on a "common misunderstanding", that is OK. Wikipedia is a tertiary source, and it aims only to collect and reproduce viewpoints, not correct them. You would need another source than you own expertise for the purposes of verfiability. (See also WP:V). And why not get an account, that makes it easier to talk to you. Best, Arbor 10:46, 25 April 2006 (UTC) Later addition: I think Fogel's work certainly qualifies as the type of source I was talking about. Carry on. Arbor 10:47, 25 April 2006 (UTC)

[edit] Observation removed from the main page

• GAs cannot 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 described as having "needle in a haystack" fitness landscapes.

"A needle in a haystack" problem which is referred here is hard to optimize by any method. Binary fitness values are not enough for a problem to be "a needle in a haystack", in addition it should have only one maximum (a needle). It is easy to think of many cases with binary fitness values that GA can optimize well, simplest ones are line patterns on a 2d greed. Anyways, the observation is not correct as stated.

You're right that the NIAH problems usually refer to those with only one solution, but I think the binary fitness part of the problem is significant. Or, rather, the fitness doesn't need to be binary, but there must be a sharp distinction between correct and incorrect, as this is what makes the optimization difficult (as the GA has no slope which it can climb). Anyway, the point of the statement is to say that "problems with binary fitnesses are difficult," not that "NIAH problems are defined as those problems with binary fitness." I think that this is pretty much agreed upon for basic GAs, as GAs need slopes to climb. What exactly do you mean by the "line patterns on a 2d greed" that are easy to optimize? — Asbestos | Talk (RFC) 17:59, 17 July 2006 (UTC)

I've replaced the sentence, but removed the irrelevent needle-in-a-haystack statement. I've added that a random search can typically find such solutions just as fast as a GA in these situations, as a GA is essentially acting as a large random parallel search algorithm. — Asbestos | Talk (RFC) 13:30, 19 July 2006 (UTC)

[edit] Local search ?!

Specifically it falls into the category of local search techniques and is therefore generally an incomplete search.

Um, sure, GAs don't always find the global optimum, but what method does? I can't think much more global method than GA which uses the whole search space as opposed to true local methods which search only the neighborhoods of the given solution candidate. Consider a hill climber local algorithm for example, it halts when it reaches a local optimum. GAs may stall in such position, but in theory they should eventually escape from it.--JyriL ^talk 06:38, 2 August 2006 (UTC)

A method that always finds the global optimum is one that searches every possibility, which a GA doesn't do. I assume that this is the distinction implied by the difference between a global search and a local search. — Asbestos | Talk (RFC) 14:52, 3 August 2006 (UTC)

No, that's the different between complete(?) and incomplete search methods (or do you mean the difference between deterministic and stocastic methods?). Most global optimization methods, including GAs, belong to the latter as the former is usually impossible to implement.--JyriL ^talk 16:37, 3 August 2006 (UTC)

Sorry — I wasn't clear. I wasn't saying that a GA was a local searching algorithm, rather that this was probably what the original author of the sentence had in mind (plus I was answering the "what method does?" rhetorical question). I agree that a GA is not a local searching algorithm. For the record, complete searches are not impossible to implement, in fact they are many times easier to program than a GA (any problem that is solvable by a GA can be solved by a brute-force search). The problem is that they take too long compared to any stochastic method. Anyway: yes, the offending sentence is incorrect, and should go (though the part about it being incomplete is correct). — Asbestos | Talk (RFC) 18:25, 3 August 2006 (UTC)

OK, I was afraid I've made a grand misunderstanding on the issue. ;) "Implement" was wrong word, I meant exactly what you said.--JyriL ^talk 18:30, 3 August 2006 (UTC)

---

Can someone write the article in simple words please.

How do you mean that please, be more specific ? Tulkolahten 12:08, 16 November 2006 (UTC)

[edit] See Also

Evolutionary Strategies are mentioned in the Related Techniques section. The See Also section is currently redundant and should be removed.Keki Burjorjee 07:36, 30 January 2007 (UTC)

[edit] References

The references section has gotten quite long. Many of the references describe applications of GAs or boutique genetic algorithms and aren't cited in the body of the article. I suggest removing the following ones.

   * Fentress, Sam W (2005), Exaptation as a means of evolving complex solutions, MA Thesis, University of Edinburgh. (pdf)
   * Harvey, Inman (1992), Species Adaptation Genetic Algorithms: A basis for a continuing SAGA, in 'Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life', F.J. Varela and P. Bourgine (eds.), MIT Press/Bradford Books, Cambridge, MA, pp. 346-354.
   * Hicks, C., (2006), A Genetic Algorithm tool for optimising cellular or functional layout in the capital goods industry., International Journal of Production Economics, 104(2), 598-614.
   * Kjellström, G. Network Optimization by Random Variation of component values. Ericsson Technics, vol. 25, no. 3, pp. 133-151, 1969.
   * Kjellström, G. Optimization of electrical Networks with respect to Tolerance Costs. Ericsson Technics, no. 3, pp. 157-175, 1970.
   * Kjellström, G. & Taxén, L. Stochastic Optimization in System Design. IEEE Trans. on Circ. and Syst., vol. CAS-28, no. 7, July 1981.
   * Kjellström, G. On the Efficiency of Gaussian Adaptation. Journal of Optimization Theory and Applications, vol. 71, no. 3, Dec. 1991.
   * Kjellström, G. & Taxén, L. Gaussian Adaptation, an evolution-based efficient global optimizer; Computational and Applied Mathematics, In, C. Brezinski & U. Kulish (Editors), Elsevier Science Publishers B. V., pp 267-276, 1992.
   * Kjellström, G. Evolution as a statistical optimization algorithm. Evolutionary Theory 11:105-117 (January, 1996).
   * Kjellström, G. The evolution in the brain. Applied Mathematics and Computation, 98(2-3):293-300, February, 1999.
   * Pongcharoen, P., Hicks, C., Braiden, P.M. and Stewardson, D., (2002), Determining Optimum Genetic Algorithm Parameters for Scheduling the Manufacture and Assembly of Complex Products. International Journal of Production Economics, 78(3), 311-322.

Jasper53 07:58, 30 January 2007 (UTC)

My intension is to supply an article about Gaussian adaptation that was used already in 1969 for the maximization of manufacturing yield of signal processing systems. Later it turned out that yield is not very far from the mean fitness of populations of living organisms.

Kjells 16:07, 30 January 2007 (UTC)

I do not feel that the Kjellstrom references will be helpful to someone who is seeking to understand what GAs are and how they work. The references might be more appropriate in an article about the history of evolutionary algorithms.

Text about Gaussian adaptation as a genetic algorithm has been added among GA-Variants, and two referneces to Kjellström has been introduced again. But, of cource, the same references may be found in the article about Gaussian adaptation.

Kjells 20:09, 21 March 2007 (UTC)

[edit] GA's now important in statistical experimental design

Dfarrar 22:15, 21 March 2007 (UTC)

• Dfarrar, you created a section title but no section? Pete St.John 15:24, 22 March 2007 (UTC)