Talk:Genetic programming

History

I just made some changes to the Genetic programming "history" paragraph, which seemed to include a fair bit of, well, pretty odd historical interpretation:

Steven Smith's thesis does not appear to discuss GP in the tree or string sense: rather, it's largely an extension on Pitt Approach rule systems, which were already well under development at U Pitt (via Ken De Jong) down the road. This isn't to say it's not a useful thesis by any stretch -- for example, it's the first example of "bloat" that I'm aware of -- but it didn't propose any new GPish notion. Anyway, the LCS and Pitt Approach ruleset stuff is very GP in goal and capability, and deserves to be mentioned.

Second, I also have Schmidhuber's thesis and early work, and I do not see anything in it that proposes tree-style GP at all. What it does propose is a sort of string-based representation for GP with GOSUBs of sorts, something which had already been proposed by Nichael Cramer in the same paper that proposed a tree-based representation. Schmidhuber does get credit for the notion of self-modifying programs, a concept which Lee Spector has since run with in PUSH. But that's a relatively small item IMHO. It probably doesn't deserve a major paragraph on the GP page when so much else is missing.

Last, there seems to be quite a bit of confusion about evolutionary programming and genetic programming, etc. My take on it is: EP and GP are (or were, for EP) communities or brands. EP basically was two things: evolution strategies + arbitrary representations. It's since basically been subsumed into ES research-wise. But I think the really important early contribution of Larry Fogel, and one which cannot be understated, was that he developed EP specifically to search for finite-state automata! That is, the very earliest EP work, and indeed the earliest relevant EA work, is basically a genetic programming endeavor.

There seems to be a quite bit of self-promotion in this article: it could really REALLY use a major overhaul by someone knowledgeable, and relatively unbiased, in the field.

-- Sean Luke —Preceding unsigned comment added by Feijai (talk • contribs) 02:36, 20 May 2009 (UTC)

Evolutionary programming

NOTE: this sounds like Evolutionary programming. Genetic Programming is a search technique more than a way to generate new programs.

From reading the genetic programming FAQ, it sounds like this is actually describing genetic programming. From another FAQ (http://www.faqs.org/faqs/ai-faq/genetic/part2/section-3.html), I get the impression genetic programming and evolutionary programming are synonymous, but I'm not sure. You may be thinking of genetic algorithms. Could an actual expert straighten us out? -- Janet Davis

Not sure if this is the right place to do it, but evolutionary programming (EP) and genetic programming (GP) are distinctly different creatures. Evolutionary Programming is much older than GP and was instigated in a time were 'Programming' ment 'Recipe' (viz. Linear Programming, Dynamic Programming, Quadratic Programming). In this day and age, and with Genetic Programming, the word actually points to creating 'computer programs'. Evolutionary programming is a recipe to perform evolution, Genetic Programming is a method to create computer programs.

About the current article. I'm a bit baffled about the statement that hill-climbing has a solid theory behind it. There is theory, but it mainly says it will fail when things get rough. The fact that GP doesn't have such theory (in fact it has, for different gradations of rough), makes it less suitable? I'll contemplate what to do with this. -Maarten Keijzer-

Anyone care to vote on the Discipulus link (2nd para)? Is it an advert or is it relevant? / Bob MacCallum

The article refered to Lisp as a declarative language, but Lisp is imperative (and a little functional) to my understanding. However, I'm not familiar with the referenced system so I don't know how best to correct the reference in the text. -Steve Post-

I edited that part out. -Michael Gospatrick-

Genetic programming is an implementation of an evolutionary algorithm (also caled an evolutionary computation method) in which the solution representation is a compter program. This is quite different from evolutionary programming in whch the solution representation is effectively a vector of values representing variables in a pre determined program structure. Because the representation is a computer program this is often refered to as an automatic programming method, perhaps it would be more clear to say that it is a search through a program space guided by evolutionary principles. I personally think the Discipulus link is an advert but also relevent....... -Peter Day-

-The text of the page could be straight from the back-cover of koza's book. It's language is so similar and higlights koza's achievements pretty much in the same way he himself does in his book. The following is particularly disturbing example of this: These results include the replication or infringement of several post-year-2000 inventions[citation needed], and the production of two patentable new inventions. 130.233.31.110 17:40, 9 March 2007 (UTC)

- I second the comment above - there are several disturbing points in this article - I think someone knowledgeable should review, and if needed, step up to put a "neutrality dispute" tag on this article - It seems to me it presents a one-man view, with a lot of advertising too - dr.falko -

Meta-genetic programming impossible? -- need reference

Would be nice to have a reference following the words "critics argued that this is theoretically impossible" in the paragraph describing Meta-genetic programming... —The preceding unsigned comment was added by Knomegnome (talk • contribs) 22:00, 1 February 2007.

I wrote that because of a Usenet post in which I presented my ideas on Meta-GP. They were not well received. I disagree with the critics (Inman Harvey & xanthian@well.com) but wanted to appear even handed.

- Michael Gospatrick -

The general problem of MGP -is- unsolvable because you are talking about an unconstrained, recursive system. There simply must be constraints, and even given the constraints there is no guarantee that an evolved GP will be better than a created one. Possible, but not guaranteed. I believe the best direction to go in for MGP is to work on generic classes on fitness, evolve a GP to fit that class, then use that GP to evolve subclasses. So, AI walking could be evolved with the MGP. The most efficient at it after X generations is then used to evolve running, jumping, climbing, etc. You could then use these GP to seed new GP that are used to simulate more complex or related behaviors, and so on. There is no guarantee that the Meta GP will be better than a created one, however, because there isn't any way to know that the GP you have at the end isn't just really good at evolving the thing you've already accomplished. It is simply something that seems intuitively correct through our own experience as humans, and might be shown to be generally true through exhaustion.

In other words, there is need to experiment. Knomegnome 22:00, 1 February 2007 (UTC)

Fair enough. Experimentation and exploration are my goals, not defending the status quo. If they prove Meta-Genetic Programming to be a farce, so be it.

- Michael Gospatrick - —The preceding unsigned comment was added by 24.125.150.61 (talk • contribs) 09:33, 22 February 2007. -- wrp103 (Bill Pringle) 10:00, 22 February 2007 (UTC)

Please remember to sign your posts, and not interweave them within an existing discussion. It makes it hard to follow the thread. wrp103 (Bill Pringle) 10:00, 22 February 2007 (UTC)

I'll try to correct the Meta-GP section, citing Schmidhuber's original work, pointing out that standard GP suffers from the same problem:

Meta-Genetic Programming is the technique of evolving a genetic programming system using genetic programming itself. . It proposes that chromosomes, crossover, and mutation were themselves evolved, therefore like their real life counterparts should be allowed to change on their own rather than being determined by a human programmer. Meta-GP was proposed by Jürgen Schmidhuber in 1987 . His recursive but terminating algorithm avoids infinite recursion and halting problems. [...] For general problem classes there may be no way to show that Meta GP will reliably produce results more efficiently than a created algorithm other than exhaustion. The same holds for standard GP and other search algorithms, of course.

That's not what "halting problem" means--Was that an automated edit? 65.183.135.231 (talk) 01:26, 29 October 2008 (UTC)

Algorithms 19:54, 4 June 2007 (UTC)

What are the most popular GP packages?

In the links section it mentions a few GP implementations as "possibly most used" and all of them are implemented in C++.

I thought lilGP (C) and ECJ (Java) were the most popular. -Warren Henning

In my experience I would agree with that the above - lilGP and ECJ are certainly the most cited. Although I have known quite a few students to use Sara Silva's matlab based GPLab (http://gplab.sourceforge.net/) - Peter Day —Preceding unsigned comment added by 212.183.134.129 (talk) 17:18, 8 August 2008 (UTC)

effeiciency

Increases in the efficiency and speed of genetic programming (linear) were being made in the late 20th century, particularly via automatic induction of machine code. http://www.aimlearning.com/aigp31.pdf Rogerfgay 11:20, 4 December 2007 (UTC)

Adding Value to the Genetic Programming Entry

Comments on improving the article:

1 - The section on chromosome representation. Whilst a large proportion of GP practitioners do use tree representations in their work, there are other choices, such as linear, grammar and graph representations and a swift flick through "Genetic Programming: An Introduction..." (Banzhaf et al.) will tell you all about these representations. In addition to this, this section does not reflect the relative difficulty in dealing with representations and the impact one can have on GP by tinkering with representations. There is a good book by Franz Rotlauf "Representations for Genetic and Evolutionary Algorithms" which studies some of these issues in more detail. What is concerning about this section is that it is very limited to System X uses representation Y rather than dealing with academic issues in representation. I would rather see a section dealing with academic issues of representating programs and software to implement GP discussed elsewhere in the article.

2 - The descriptions of the genetic operators are very simplistic and do not mention basic process descriptions, (simple examples: for instance the different choices of swap points during crossover and the many different types of mutation suggested in Koza's 1992 book "On the programming of computers by natural selection").

3 - There is no mention of the selection process and this is a big part of genetic programming. Again there are several methods for this process.

4 - There is no mention of several other issues within the field, such as multi-objective GP, program initialisation techniques, code bloat, relative value of crossover versus mutation and other topics such as distributed/parallel GP.

5 - The advert on reference 6 should be removed and replaced with the title of the article to which it refers.

6 - The section "possibly most used (software)" should be removed and all references put in the implementation section.

7 - Anyone who is serious about learning more about GP should be pointed at the GP bibliography as this provides a huge database of all the latest academic papers in the field, maintained by three domain experts.

As for some of the issues in the talk section:

Evolutionary programming - My own interpretation and as some people have mentioned of evolutionary computation is that it is older than GP and forms part of a general recipe. What I would add is that GP is aimed at the evolution of programs and that these programs are evaluated through execution or interpreted simulation of execution to assess fitness. This factor does set GP aside from other fields in evolutionary computation.

Meta Genetic Programming - Whilst I am sure these are valuable academic contributions, this is a relatively small subsection of what this article could be. This section may well have a place, but maybe not so prominent and after all the other basic GP details have been covered.

Popular GP packages:

lilGP and ECJ - Sean Luke (et al.)'s ECJ does seem to appear in a lot of academic publications these days.

Any feedback on these comments are welcome - I believe this article could be made a lot more informative with multiple contributions.

-Lawrence Beadle- —Preceding unsigned comment added by Loz777 (talk • contribs) 21:31, 5 June 2008 (UTC)

Crossover confusion

I am wondering if this part of the article is quite right:

Crossover is applied on an individual by simply switching one of its nodes with another node from another individual in the population. With a tree-based representation, replacing a node means replacing the whole branch. [...]

The following code suggests a simple implementation of individual deformation using crossover:

individual.Children[randomChildIndex] = otherIndividual.Children[randomChildIndex];

The part about switching one of its nodes with another made me think of swapping two nodes, but the single line of pseudocode makes the crossover one-way. This is add odds with other stuff I have read about generalized genetic algorithm crossover. I was expecting something more like:

temporaryNode = individual.Children[randomChildIndex];

individual.Children[randomChildIndex] = otherIndividual.Children[randomChildIndex];

otherIndividual.Children[randomChildIndex] = temporaryNode;

Can anyone explain which of these is correct? Thanks! CosineKitty (talk) 01:26, 4 July 2008 (UTC)

Link cleanup

I think the links could be cleaned up by removing the distinction between "most popular implementations" and the rest. Instead, links should be divided into general implementations (toolboxes) and demos (rocket landing, ect.)

74.177.149.149 (talk) 02:28, 19 November 2009 (UTC)