I understand the theory of GP, and I understand how to implement most of it, but I'd like to know how other people have handled certain parts of it. My main question right now is how to pick which branch to mutate or crossover. Should each branch and leaf have equal probability of being picked, or should there be some kind of weighting? Should branches of approximately equal size be chosen for crossover, or does it matter? Also, how should mutation be done? Should both branches and terminals be mutated or only one or the other? If branches are mutated, should the function be changed to a random one with the same number of arguments or should it be changed to a simmilar function (like an arithmatic operator stays arithmetic, logs can turn into e^x, etc)? I would appreciate any info, links, book reccomendations, etc. If it matters, I'm using Lisp =-) [edited by - Extrarius on April 22, 2003 1:36:22 PM]

"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk

Dobbs

164

April 22, 2003 01:39 PM

I''m curious about this as well since I''m in the same situation. Does anyone have any suggestions?

I suspect the answers will basically be "whatever works." A lot of quantitative questions about AI seem to be answered that way, such as "how many hidden layers to put in a NN?".

Anonymous

April 23, 2003 08:57 AM

i used equal probabilities for all branches and both functional and terminal sets. i felt that having different probabilities added unnecessary constraints which might influence the solution.

Extrarius

Author

1,412

April 23, 2003 03:47 PM

quote: Original post by Anonymous Poster
i used equal probabilities for all branches and both functional and terminal sets. i felt that having different probabilities added unnecessary constraints which might influence the solution.

How do you randomly select a node in a tree such that all nodes have an equal probability of being chosen? I''m not really sure how to do that. They way my code does it now is to choose the root node, then randomly choose a child node and set the chosen node to that node if random(0 to 1)<(1 / level) {where level starts at 1 for the root} and repeat for each child until the node being examined has no children, but that only gives them all an equal chance of ending up chosen if the tree is perfectly balanced.

[edited by - Big Brother on January 1, 1984 12:00:00 AM]

"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk

Dobbs

164

April 23, 2003 11:55 PM

I do it by implicitly assigning a unique number n to each node in the tree, such that 0 <= n < (# of nodes in tree). Then I randomly pick a number x in the same range and traverse the tree to find that node numbered x. The implicit numbering system I use is defined inductively:

root=0
for any node numbered n
left child, if it exists, is n+1
right child, if it exists, is n+(# of nodes in left branch)+1

[edited by - Dobbs on April 23, 2003 12:56:38 AM]

pacman2003

122

April 24, 2003 07:59 PM

have u read the tutorial at ai-junkie?

[edited by - pacman2003 on April 24, 2003 9:00:47 PM]

Extrarius

Author

1,412

April 24, 2003 08:36 PM

Yes, I have read it, but it goes over the basics of genetic algorithms and not implementation specific details of genetic programming. I want to hear from people that have implemented GP successfully so I can know what works and what doesn''t, and how specific things are handled by various people.
The only real difference between fups'' GA example and GP is that GP is generally represented as a tree instead of a list. I guess it could be done as a list, but it seems like you would have just as much trouble implementing some things (and depending on how you implemented the list, evolution could be a LOT slower than a ''standard'' tree-based implementation).

"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk

bishop_pass

112

April 24, 2003 11:58 PM

Have you read Karl Sims'' paper?

___________________________________

"The outside of a horse is good for the inside of a man" - Winston Churchill

_______________________________
"To understand the horse you'll find that you're going to be working on yourself. The horse will give you the answers and he will question you to see if you are sure or not."
- Ray Hunt, in Think Harmony With Horses
ALU - SHRDLU - WORDNET - CYC - SWALE - AM - CD - J.M. - K.S. | CAA - BCHA - AQHA - APHA - R.H. - T.D. | 395 - SPS - GORDIE - SCMA - R.M. - G.R. - V.C. - C.F.