Talk:Genetic programming

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..^[1] 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.^[2] 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)

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)

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)

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)

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)

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)

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)

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)

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)

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

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)

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

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)

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