GP_Final/GP_Basis at master · leforebs95/GP_Final · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
(ns cs253.gp-tidbits)

; Let's say we have a program in the form of a list;
; this one is 5x + (2x - 3) = 7x - 3
(def prog
  '(+ (* x 5) (- (+ x x) 3)))

prog

;(eval prog) ; error: we haven't said what x should be!

;(prog 5) ; error: prog isn't a function, it is just a list

; We need to turn the program into a function, where
; x is the input to the function. Then, we could run it
; on the input.

(defn make-program-into-fn
  "Takes a GP program represented as a list, with input x,
   and transforms it into a function that can be called on an input.
   NOTE: If your GP uses variables other than x, will need to change
         the argument list below to something other than [x]!"
  [program]
  (eval (list 'fn
              '[x]
              program)))

; Now, we can get a function version of prog, and then apply
; it to input 2:
(let [prog-fn (make-program-into-fn prog)]
  (prog-fn 2))

; Q: Let's say the inputs are (range 10)
; How can we get the outputs of the program on those inputs?
; A:
(let [prog-fn (make-program-into-fn prog)]
  (map prog-fn (range 10)))

;========================================

; Next, we'll show how to select a random subtree from
; a program, and how to replace a random subtree with
; a given subtree.

(def instructions
  '{+ 2
    * 2
    - 2
    inc 1})

(defn program-size
  "Finds the size of the program, i.e. number of nodes in its tree."
  [prog]
  (if (not (seq? prog))
    1
    (count (flatten prog))))

(program-size prog)

(defn select-random-subtree
  "Given a program, selects a random subtree and returns it."
  ([prog]
    (select-random-subtree prog (rand-int (program-size prog))))
  ([prog subtree-index]
    (cond
      (not (seq? prog)) prog
      (and (zero? subtree-index)
           (some #{(first prog)} (keys instructions))) prog
      (< subtree-index (program-size (first prog))) (recur (first prog)
                                                           subtree-index)
      :else (recur (rest prog)
                   (- subtree-index (program-size (first prog)))))))

(select-random-subtree prog) ; gives random subtree

(select-random-subtree prog 0) ;gives subtree at index 0
(select-random-subtree prog 1) ;gives subtree at index 1
(select-random-subtree prog 2) ;gives subtree at index 2

(defn replace-random-subtree
  "Given a program and a replacement-subtree, replace a random node
   in the program with the replacement-subtree."
  ([prog replacement-subtree]
      (replace-random-subtree prog replacement-subtree (rand-int (program-size prog))))
  ([prog replacement-subtree subtree-index]
    (cond
      (not (seq? prog)) replacement-subtree
      (zero? subtree-index) replacement-subtree
      :else (map (fn [element start-index]
                   (if (<= start-index
                           subtree-index
                           (+ start-index -1 (program-size element)))
                     (replace-random-subtree element
                                             replacement-subtree
                                             (- subtree-index start-index))
                     element))
                 prog
                 (cons 0 (reductions + (map program-size prog)))))))

prog

(replace-random-subtree prog 99)
; this is a comment