On Aug 21, 12:05 pm, Jan Rychter <j...@rychter.com> wrote: > think crossover in genetic programming (this is actually what I need > this for). > > --J.
Hi, I've written a genetic programming framework in Clojure, it might be of interest if you're looking for some inspiration: http://bitbucket.org/svdm/clojuregp/src/ Though I experimented with using zippers initially, I ended up not using them for the fundamental tree operations like the one discussed here. I found zippers to be quite a bit slower than more low level approaches for traversing trees, which becomes significant in typical GP experiments where things like subtree replacement are used a large number of times. After some experimentation I settled on an approach using an atom to keep track of the current node's index in the tree, while walking it depth-first, rebuilding it as we go. If the index matches the one we want to replace, we cons on the replacement node instead of the old one. This turns out to be pretty fast, but it's a bit of a monstrosity, what with the mutable state, etc. I've been meaning to replace it with something nicer, but haven't found a good alternative yet. Here it is: (defn tree-replace [idx new-node tree] (let [i (atom -1) r-fn (fn do-replace [node] (swap! i inc) (cond (= @i idx) new-node (> @i idx) node (coll? node) (cons (first node) (doall (map do-replace (next node)))) :else node))] (r-fn tree))) Also available here if it gets mangled: http://bitbucket.org/svdm/clojuregp/src/tip/src/cljgp/breeding.clj#cl-111 The index of each node is equal to its index in a tree-seq created as follows: (tree-seq coll? next tree) In action: user> (def tree1 '(- 100 99)) #'user/tree1 user> (def tree2 '(+ (* 1 2) (- 3 4))) #'user/tree2 user> (tree-seq coll? next tree2) ((+ (* 1 2) (- 3 4)) (* 1 2) 1 2 (- 3 4) 3 4) user> (tree-replace 1 tree1 tree2) (+ (- 100 99) (- 3 4)) user> (tree-replace 2 tree1 tree2) (+ (* (- 100 99) 2) (- 3 4)) user> (tree-replace 0 tree1 tree2) (- 100 99) So that's one way of doing it. Not the prettiest, but it does what I need it to. I'm not sure it does exactly what you want though, because: user> (tree-replace 3 '(7 8 (9 10)) '(1 2 (3 4 5) 6)) (1 2 (3 (7 8 (9 10)) 5) 6) Compared to: > should produce => '(1 2 (3 7 8 (9 10) 6)) I'm kind of wondering why you want the replacement subtree (tree2 if you will) to be spliced "flat" into the original tree like that. It seems to me that such an operation would not actually do a subtree replacement in the typical genetic programming sense. I've tried to illustrate what I mean in a little diagram: http://i30.tinypic.com/hsizkh.png Regards, Stefan PS. I hope this ends up in the right place, I'm new to mailing list posting. Apologies in advance if I accidentally break something. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~----------~----~----~----~------~----~------~--~---
