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. Her 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)

References

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 at 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)

while there may be some systems that demand that two individuals mate or merge and produce two results, it can still be referred to as "crossover" if they produce only one new result -- the point is that material from one individual was copied into another. A better word than "switching" might have been chosen. (76.118.216.33 (talk) 22:34, 27 August 2010 (UTC))

Typically sub-trees are chosen at random to be participate in crossover. Selection of which are retained in the population is typically done later in the algorithm. August 2023 Bill — Preceding unsigned comment added by W102102 (talk • contribs) 08:58, 11 August 2023 (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.)

Thattommyguy (talk) 02:29, 19 November 2009 (UTC)

Links to implementations?

Is there a reason that these have been removed? —Preceding unsigned comment added by 94.194.88.114 (talk) 00:00, 13 January 2010 (UTC)

Yes. WP:NOT, especially WP:SOAP and WP:NOTLINK, and WP:NPOV. --Ronz (talk) 04:53, 14 February 2013 (UTC)

Lifted from Poli?

YES and We did it!

After discussion with my co-authors, Riccardo Poli and Nic McPhee, more than a year ago, I spent many evenings editing the GP wikipedia entry. Yes the text was heavily based on the text in our book and I added links to pictures on Riccardo's home page.

This gift to Wikipedia entailed a lot of manual effort. It seems a shame to throw it way. No effort has been made to contact any of the authors, or otherwise to find our views of the copyright implications of what I had added to Wikipedia.

Bill

W. B. Langdon, May 4, 2012 — Preceding unsigned comment added by 128.16.7.220 (talk • contribs) 2012-05-04T20:38:26 (UTC)

Original text

Much of this article appears to be lifted directly from Poli et al. A Field Guild to Genetic Programming. There are several references to figures that don't appear in the article and using Google to search for several randomly chosen phrases brings up the Poli document.

The article reads more like a tutorial (e.g. "We strongly encourage doing GP as well as reading") than an encyclopedia entry. Poli et al. appears to be an excellent introduction. Why plagiarize it here rather than give a reference to it? Molinari (talk) 16:37, 13 September 2011 (UTC)

Agreed! This article quadrupled in size, due to one anonymous user Special:Contributions/128.16.7.220, in March and May 2011. I presume this was done while (s)he was a student talking a class in this. Removal/cleanup would be appreciated! linas (talk) 20:21, 14 December 2011 (UTC)

Yikes! I just removed one section that appears to be a verbatim copy of http://cswww.essex.ac.uk/staff/poli/gp-field-guide/42StepbyStepSampleRun.html It violates the license, posted at http://cswww.essex.ac.uk/staff/poli/gp-field-guide/index.html in two ways: fails to attribute, and is a prohibited derivative work.

Specifically, the license is this:

©Riccardo Poli, William B. Langdon, and Nicholas F. McPhee, 2008 This work is licensed under the Creative Commons Attribution-Noncommercial-No Derivative Works 2.0 UK: England & Wales License (see http://creativecommons.org/licenses/by-nc-nd/2.0/uk/). That is: You are free: to copy, distribute, display, and perform the work Under the following conditions: Attribution. You must give the original authors credit. Non-Commercial. You may not use this work for commercial purposes. No Derivative Works. You may not alter, transform, or build upon this work. For any reuse or distribution, you must make clear to others the licence terms of this work. Any of these conditions can be waived if you get permission from the copyright holders. Nothing in this license impairs or restricts the authors' rights.

Am now reviewing the rest. linas (talk) 21:59, 14 December 2011 (UTC)

Shouldn't be a tutorial - needs overhaul

While there is a lot of good info and it's fairly well written, the style of this article is a poor fit for an encyclopedia. To wit, sections like "Getting Started" and "Getting Ready to Run...", and the use of "we". Essentially it's written as a guide for someone wishing to get into genetic programming, when it should just be about the concepts.

The order of sections is also odd: "History" appears in a seemingly random position.

I believe this article needs an overhaul to bring it up to standards. (And I am not qualified to do it.) Mmcculloch (talk) 22:12, 30 November 2011 (UTC)

Agreed! This article quadrupled in size, due to one anonymous user Special:Contributions/128.16.7.220, in March and May 2011. What's worse, most of it seems to be a plagiarization, see comment above. I presume this was done while (s)he was a student talking a class in this. Removal/cleanup would be appreciated! linas (talk) 20:23, 14 December 2011 (UTC)

Roboassess + B class

The robotics project does not use C class assessments.

There also seems to be some over enthusiastic assessing here - there are several paragraphs without references and two whole sections without a single ref. I would suggest projects take a look at this again to see if it really does warrant B class status. Chaosdruid (talk) 10:01, 24 March 2012 (UTC)

Unclear sentence

"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." I'm not sure how to interpret this.--Clevera (talk) 11:19, 10 February 2013 (UTC)

The implementation table has been removed

The implementation table has been removed by http://en.wikipedia.org/wiki/User:Ronz on 04:51, 14 February 2013, I think we should keep it somewhere (creating a sub-page if needed, although right now I think we have enough space in the main article) http://en.wikipedia.org/w/index.php?title=Genetic_programming&diff=538167213&oldid=535497293 Franck Dernoncourt (talk) 17:59, 10 March 2013 (UTC)

I've removed it again. It simply doesn't belong per WP:NOT and WP:EL. --Ronz (talk) 00:35, 26 May 2014 (UTC)

Bibliography

Someone want to go through the history and determine which entries might actually be references? Or maybe it should just be moved here? --Ronz (talk) 21:25, 13 March 2013 (UTC)

Moved below: --Ronz (talk) 00:39, 26 May 2014 (UTC)

Bibliography

• Banzhaf, W., Nordin, P., Keller, R.E., and Francone, F.D. (1998), Genetic Programming: An Introduction: On the Automatic Evolution of Computer Programs and Its Applications, Morgan Kaufmann
• Barricelli, Nils Aall (1954), Esempi numerici di processi di evoluzione, Methodos voll. 6-7, pp. 45–68.
• Brameier, M. and Banzhaf, W. (2007), Linear Genetic Programming, Springer, New York
• Crosby, Jack L. (1973), Computer Simulation in Genetics, John Wiley & Sons, London.
• Cramer, Nichael Lynn (1985), "A Representation for the Adaptive Generation of Simple Sequential Programs" in Proceedings of an International Conference on Genetic Algorithms and their Applications, Grefenstette, John J. (ed.), Carnegie Mellon University
• Fogel, David B. (2000) Evolutionary Computation: Towards a New Philosophy of Machine Intelligence IEEE Press, New York.
• Fogel, David B. (editor) (1998) Evolutionary Computation: The Fossil Record, IEEE Press, New York.
• Forsyth, Richard (1981), BEAGLE A Darwinian Approach to Pattern Recognition Kybernetes, Vol. 10, pp. 159–166.
• Fraser, Alex S. (1957), Simulation of Genetic Systems by Automatic Digital Computers. I. Introduction. Australian Journal of Biological Sciences vol. 10 484-491.
• Fraser, Alex and Donald Burnell (1970), Computer Models in Genetics, McGraw-Hill, New York.
• Holland, John H (1975), Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor
• Korns, Michael (2007), Large-Scale, Time-Constrained, Symbolic Regression-Classification, in Genetic Programming Theory and Practice V. Springer, New York.
• Korns, Michael (2009), Symbolic Regression of Conditional Target Expressions, in Genetic Programming Theory and Practice VII. Springer, New York.
• Korns, Michael (2010), Abstract Expression Grammar Symbolic Regression, in Genetic Programming Theory and Practice VIII. Springer, New York.
• Koza, J.R. (1990), Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems, Stanford University Computer Science Department technical report STAN-CS-90-1314. A thorough report, possibly used as a draft to his 1992 book.
• Koza, J.R. (1992), Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press
• Koza, J.R. (1994), Genetic Programming II: Automatic Discovery of Reusable Programs, MIT Press
• Koza, J.R., Bennett, F.H., Andre, D., and Keane, M.A. (1999), Genetic Programming III: Darwinian Invention and Problem Solving, Morgan Kaufmann
• Koza, J.R., Keane, M.A., Streeter, M.J., Mydlowec, W., Yu, J., Lanza, G. (2003), Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic Publishers
• Langdon, W. B., Genetic Programming and Data Structures, Springer ISBN 0-7923-8135-1
• Langdon, W. B., Poli, R. (2002), Foundations of Genetic Programming, Springer-Verlag ISBN 3-540-42451-2
• Nordin, J.P., (1997) Evolutionary Program Induction of Binary Machine Code and its Application. Krehl Verlag, Muenster, Germany.
• Poli, R., Langdon, W. B., McPhee, N. F. (2008). A Field Guide to Genetic Programming. Lulu.com, freely available from the internet. ISBN 978-1-4092-0073-4. {{cite book}}: External link in |publisher= (help)CS1 maint: multiple names: authors list (link)
• Rechenberg, I. (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis). Reprinted by Fromman-Holzboog (1973).
• Schmidhuber, J. (1987). Evolutionary principles in self-referential learning. (On learning how to learn: The meta-meta-... hook.) Diploma thesis, Institut f. Informatik, Tech. Univ. Munich.
• Smith, S.F. (1980), A Learning System Based on Genetic Adaptive Algorithms, PhD dissertation (University of Pittsburgh)
• Smith, Jeff S. (2002), Evolving a Better Solution, Developers Network Journal, March 2002 issue
• Shu-Heng Chen et al. (2008), Genetic Programming: An Emerging Engineering Tool,International Journal of Knowledge-based Intelligent Engineering System, 12(1): 1-2, 2008.
• Weise, T, Global Optimization Algorithms: Theory and Application, 2008

Article title versus lead

Either the article title or general content are wrong. Genetic programming (see the work of Koza in the 2000's) refers to evolving programs using genetic techniques. Any program can be evolved genetically, though a program for any particular task is normally evolved starting from a population of random programs. The reason we don't start from a highly polished human program is that it usually represents a local maxima, when we're looking for a global optimum. The program to be evolved does not require any kind of genome or any particular structure. The program itself is the genome, more or less. The initial population is run through generations. Each generation involves selection of the fittest to 'reproduce' via crossover and mutation operations. The crossover operation involves splitting the parents at random points and swapping those program segments. Mutation is substituting a selected node in the individual with some other random node. It usually takes only a few generations before the programs are noticeably not random anymore, and by 50 generations, very ingenious solutions to the problem have evolved. Genetically evolved programs are neither short nor elegant.

What this article describes is applying a genetic algorithm to a human-defined vector of values, i.e. a genome. That's a different and equally valid process. The difficulty is that humans select the parameters to be evolved. They often (usually) select poor ones, even irrelevant ones and omit ones that really matter.

The current encyclopedia is a jumble in this area: there are four ostensibly identical articles, this one, Evolutionary programming, Genetic algorithm, and Evolutionary algorithm. Sbalfour (talk) 14:01, 8 May 2019 (UTC)

Actually, the lead is spurious - where in the text does it say what the lead is supposed to summarize? I think we'll just delete the lead, and recreate a proper summary of the text. The lead isn't supposed to contain anything new. Sbalfour (talk) 14:12, 8 May 2019 (UTC)

Ok, I've recreated the lead. Let's go from here. Sbalfour (talk) 14:57, 8 May 2019 (UTC)

Bill

Cartesian genetic programming

I have just restored link to existing Wikipedia article Cartesian genetic programming in "See also" section. Not clear why the link was removed. Certainly Julian Miller (who invented cartesian genetic programming, thought of it as part of genetic programming.

Bill — Preceding unsigned comment added by W102102 (talk • contribs) 09:11, 11 August 2023 (UTC)

Linear genetic programming

Similarly I have restored link to existing Wikipedia article Linear genetic programming in "See also" section.