Допис з розмови Newby(ish)

Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.icl.net!newsfeed.fjserv.net!xara.net!gxn.net!server6.netnews.ja.net!newsfeed.ed.ac.uk!avenger.inf.ed.ac.uk!s9905774
From: Gregory Rickeard <s9905...@sms.ed.ac.uk>
Newsgroups: comp.lang.lisp
Subject: Newby(ish)
Date: Fri, 27 Jun 2003 11:45:45 +0100
Organization: Edinburgh University
Lines: 50
Message-ID: <Pine.LNX.4.44.0306271132520.26288-100000@avenger.inf.ed.ac.uk>
NNTP-Posting-Host: avenger.inf.ed.ac.uk
Mime-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Trace: scotsman.ed.ac.uk 1056710747 6985 129.215.155.67 (27 Jun 2003 10:45:47 GMT)
X-Complaints-To: usenet@scotsman.ed.ac.uk
NNTP-Posting-Date: Fri, 27 Jun 2003 10:45:47 +0000 (UTC)
X-X-Sender: s9905...@avenger.inf.ed.ac.uk

---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...