---not homework---
I have been playing with LISP (xlispstat) for a while and have been trying
to implement a genetic programming algorythm in it. I am using binary tree
representations of functions (that is an evolved program should consist
entiraly of lists of length 3 whos fist member is a member of the function
set and whos other members are either similar lists or members of the
terminal set.) however at some point though the gp run cons cells start
appearing, oftain containing atoms which dont apear in any of the
functions used in the program or as arguments to the program (the atom
TREE is particularly common)
The most likely function to be causing this is crossover - which performs
most of the work for crossover and mutation (ie. replaces a random subtree
in a tree with some specifies structure.)
(defun crossover (tree &optional (subst nil) (prob-no-recursion .75))
"args: tree &optional (subst nil) (prob-no-recursion .75)
finds a random subtree (not including the entire tree) of tree and returns
it, possibly
after replacing it with subst if subst is non nil.."
(if (< (random 1.0) (expt prob-no-recursion (1- (max-depth tree))))
;; swap with a sub tree
(let ((args (cdr tree))
(rnd (random 2))
(tmp nil))
(if (null subst)
(cond ((= rnd 0) (car args))
(t (second args)))
(cond ((= rnd 0) (setf tmp (car args))
(rplaca args subst)
tmp)
(t (setf tmp (second args))
(rplacd args (list subst))
tmp))))
;; swap with another sub-tree
(let* ((dl (max-depth (second tree)))
(dr (max-depth (third tree)))
(rnd (random (+ dl dr))))
(if (< rnd dl)
(crossover (second tree) subst)
(crossover (third tree) subst)))))
crossover looks fine to me - but i am unshure of my usage of rplaca and
rplacd...
On 27 Jun 2003, Joe Marshall wrote:
>
> Instead of RPLACA and RPLACD, you should use SETF
>
I was under the impression thet using SETF on elements of a list
would not alter the origional structure...
> (setf (car args) subst) instead of (rplaca args subst)
>
> and
>
> (setf (cadr args) subst) instead of (rplacd args (list subst))
>
This did not work when I tried the substitution, however
(setf (second args) subst) worked fine...
>
> You should consider representing the nodes in your tree as defstructs.
>
This unfortunataly did not solve the problem - looks like i will have to
re-implement the program using structures.
Thanks anyway.
Greg