3

我正在 Common Lisp (CLISP) 中实现进化算法，但我遇到了问题。

我有一个类似树的类：

(defclass node ()
  ((item :initarg :item :initform nil :accessor item)
   (children :initarg :children :initform nil :accessor children)
   (number-of-descendants :initarg :descs :initform nil :accessor descs)))

还有一些方法：

(defmethod copy-node ((n node))
  (make-instance
   'node
   :item (item n)
   :descs (descs n)
   :children (mapcar #'copy-node (children n))))

(defmethod get-subtree ((n node) nr)
 (gsth (children n) nr))
(defmethod (setf get-subtree) ((val node) (n node) nr)
  (setf (gsth (children n) nr) val))
(defmethod get-random-subtree ((n node))
  (gsth (children n) (random (descs n))))
(defmethod (setf get-random-subtree) ((val node) (n node))
  (setf (get-subtree n (random (descs n))) val))

(defun gsth (lst nr)    
  (let ((candidate (car lst)))
    (cond
      ((zerop nr) candidate)
      ((<= nr (descs candidate)) (gsth (children candidate) (1- nr)))
      (t (gsth (cdr lst) (- nr (descs candidate) 1))))))

(defun (setf gsth) (val lst nr)    
  (let ((candidate (car lst)))
    (cond
      ((zerop nr) (setf (car lst) val))
      ((<= nr (descs candidate))
       (setf (gsth (children candidate) (1- nr)) val))
      (t (setf (gsth (cdr lst) (- nr (descs candidate) 1)) val)))
    val))

我想要做的是从人口中交换两个随机树的两个随机子树。但是当我做这样的事情时：

(defun stdx (population)
  (let ((n (length population))
        (npop))
    (do ((done 0 (+ done 2)))
        ((>= done n) npop)
      (push (stdx2 (copy-node (random-el population))
                   (copy-node (random-el population)))
            npop))))

(defun stdx2 (father mother)
  ;; swap subtrees
  (rotatef (get-random-subtree father)
           (get-random-subtree mother))
  (check-for-cycles father)
  (check-for-cycles mother))

有时会检测到一个循环，这显然不应该发生。

Check-for-cycles 没问题，我也用 (trace) 检测到了循环。我一直在更新后代的数量。

我想（setf get-subtree）有问题。我是 LISP 的新手，我对 setf 扩展不是很好。请帮我。

4

1 回答 1

6

想想这将如何实现：

;; swap subtrees
(rotatef (get-random-subtree father)
         (get-random-subtree mother))

该rotatef表单将被宏观扩展为以下内容：

(let ((a (get-subtree father (random (descs father))))
      (b (get-subtree mother (random (descs mother)))))
  (setf (get-subtree father (random (descs father))) b)
  (setf (get-subtree mother (random (descs mother))) a))

（您可以使用macroexpand它来准确找出您的情况下的扩展。）

换句话说，随机子树将被选择两次（一次在读取时，一次在更新时），这样子树不会相互交换，对子树的引用将被复制到另一棵树的随机位置。

例如，在下图中，算法可能会选择要交换的蓝色和红色子树。但是当涉及到附加它们时，它会将它们放在标有点的点上。

图的下半部分显示了将子树附加到新点后生成的数据结构：您可以看到已经创建了一个循环。

因此，您需要修改代码，以便只选择一次随机子树。像这样的东西，也许：

(let ((a (random (descs father)))
      (b (random (descs mother))))
  (rotatef (get-subtree father a)
           (get-subtree mother b)))
于 2012-12-10T18:11:43.583 回答