Jump to content
  • Advertisement
Sign in to follow this  
choffstein

Representing decision trees as 'genes'

This topic is 4019 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have been working on a design that uses decision trees, made from nodes of logical operators (and, or, not), specific actions, and descriptors. At the end of the day, everything computes to a 'true' or 'false' value to determine if action should be taken. Now, the plan was to create this tree in a random fashion, choosing from ands/ors/nots randomly to link together these specific actions and descriptors. The tree length would be arbitrary (as in, random -- but probability of the tree growing decreasing as the tree got bigger (and exponentially decreasing at that)). Now my issue is this -- each one of these decision trees represents a possible thought process. I am trying to optimize this thought process. My first thought was 'genetic algorithms'. I figured I could use constant values to represent the specific actions and logical operators to create a gene sequence (simply storying the binary tree in an array for mating and mutations). The only issue here is, with the trees being arbitrarily long, it would be impossible for mating to occur -- unless I capped the size at N levels deep and just made an array long enough, using the value 0 for children of a leaf. The other possibility was this: for each tree created, parse all sub trees into parts and store them into the 'parts' drawer. For each part in a tree, that parts' weight value would be equal to the aggregate fitness values for all trees it is in. The higher the weighting on a specific part, the better chance of that part being selected for the next generation. This specific implementation seems like it would be far more costly memory wise than the last, and a bit harder to introduce 'mutations' into (though, I suppose it could be done). Does anybody have any ideas on how to tackle this beast? I know it is a bit obscure, but for the sake of the project I am working on, I can't really say much more. Thanks!

Share this post


Link to post
Share on other sites
Advertisement
Well, the first thing I'd do is search for terms like "genetic algorith" and "decision tree" in google. Doing that brings up some papers that are available online about some of the approaches that have been tried in using genetic algorithms to optimize decision trees.

Usually with genetic algorithms and graphs or trees, there are mutating operators designed to act on entire subtrees. Altering a single node allows for optimization of that particular node, but performing cross-over on nodes that share a common position in a binary tree is almost pointless since different trees might be using that part of the subtree for entirely different purposes. I think I have seen papers that discuss doing things like tracking how effective certain sub-trees or sub-graphs are performing, in the context of evolving neural network topologies.

Share this post


Link to post
Share on other sites
I seem to recall that one of our members (kirkd) has done some work on evolving decision trees. You might consider sending him a pm.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Boolean Algebra (pdf) might be useful for simplifying random expressions.

Summary: ( OR = ∨, AND = ∧, NOT = ¬ )

  • OR is closed: ∀ x, y ∈ B, x ∨ y ∈ B
  • 0 is the identity for OR: x ∨ 0 = 0 ∨ x = x
  • OR is commutative: x ∨ y = y ∨ x
  • OR distributes over AND: x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)
  • AND is closed: ∀ x, y ∈ B, x ∧ y ∈ B
  • 1 is the identity for AND: x ∧ 1 = 1 ∧ x = x
  • AND is commutative: x ∧ y = y ∧ x
  • AND distributes over OR: x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)
  • Complement (a): x ∨ ¬x = 1
  • Complement (b): x ∧ ¬x = 0

Theorems:
  1. x ∨ 1 = 1
  2. x ∧ 0 = 0
  3. ¬0 = 1
  4. ¬1 = 0
  5. x ∨ x = x
  6. x ∧ x = x
  7. ¬(¬x) = x
  8. x ∨ x ∧ y = x
  9. x ∧ (x ∨ y) = x
  10. x ∨ ¬x ∧ y = x ∨ y
  11. x ∧ (¬x ∨ y) = x ∧ y
  12. x ∨ (y ∨ z) = (x ∨ y) ∨ z
  13. x ∧(y ∧ z) = (x ∧ y) ∧ z
  14. ¬(x ∨ y) = ¬x ∧ ¬y
  15. ¬(x ∧ y) = ¬x ∨ ¬y

Share this post


Link to post
Share on other sites
How is your data represented? Do you have a set of pairs, say (X, True), (Y, True), (Z, False) where X, Y, Z are inputs and the second component of your pair is the output?

There's probably a better way to do this than using GA's.

Share this post


Link to post
Share on other sites
Well, because I am utilizing this method for pattern matching (in a broad scope of the word). For example, I want to be able to evolve a tree that can decide whether or not a certain number is within a range. So lets say I give it the range -10 and 10, and then an array like [1, 5, -11, 3, 7, 9]. I want it to go through those numbers, and give back a true false (1/0) based on whether or not it believes the number to be within the range. The fitness function of the tree is basically how many it got right -- and the size of the tree (with much higher weighting on the number correct).

So when you say 'how is your data represented' I am a bit confused. I know you probably think a neural network is more appropriate for this type of pattern classification and learning, but I have more than oversimplified what I am doing (because I cannot say much more).

Thanks.

Share this post


Link to post
Share on other sites
No, I was thinking of building the tree directly, not having to evolve it, using the decision tree learning algorithm. There's probably an outline of it in AI:AMA.

However, if you're sure you want to use GA's, I can see possible ways of getting around the problem with different sized trees. One, obvious, way would be to cap the depth of the tree, and keep it constant. Of course, the complexity of your boolean function will determine the size of your trees, to some extent. I think this is the method Holland (?) used when evolving Lisp programmes, although I may be misremembering.

Share this post


Link to post
Share on other sites
Thanks for remembering, Timkin!

I have indeed worked on evolving decision trees. I won't go into the extreme details of it all here (unless you ask), but the general idea I used was to represent the tree with a linked list. Each node in the tree has three links - parent, left_child, and right_child. The root node of the tree has parent set to NULL and each terminal (leaf) has left_child and right_child set to NULL. This type of structure makes parsing the tree very easy. Regarding crossover or mating of two trees, all you have to do is choose a node from each tree at random, and then swap their parent linkages. This will effectively swap the two subtrees.

I'm more than happy to answer any questions you may have, if I can. As I mentioned, I've been doing decision tree evolution for a long time, so I've probably bumped up against some of the obstacles you'll be bumping up against.

-Kirk

Just in case you're interested, here's a link to the publication I got describing this work: http://pubs.acs.org/cgi-bin/abstract.cgi/jcisd8/2004/44/i03/abs/ci034188s.html

Share this post


Link to post
Share on other sites
I would have a good look at first order logic. You could also build decision trees from an example set. Both methods and others on algorithmically constructing good decision trees can be found in "Artificial Intelligence a modern approach" by Russell and Norvig.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!