Add genetic operators to language definitions

[FelipeRosa]

Language definitions should also specify how its programs are transformed through crossover and mutation. These operators should take individuals (with pre-computed fitness and phenotype) and produce new individuals.

[FelipeRosa]

But how should the fitness and phenotype be computed for new individuals? This would require the operators to take the fitness function and problem-specific input set as arguments.

[FelipeRosa]

Yes, ideally it should be done like this:

(deflang arith
  ; language terminals list
  [(const (constant (- (rand-int 10) 5)))
   (var   (input (rand-int 2)))]
  ; language functions list
  [(plus  [e1 e2] (funcall + e1 e2))
   (times [e1 e2] (funcall * e1 e2))])
  ; language genetic operators
  ([i]     (...))
  ([i1 i2] (...))

Note that the mutation operator, for example, needs to be able to generate new random genetic code. Maybe a good solution is to include something like (rand-program max-depth full?) inside the operator's context so that the language argument is already implied as the language being defined.

[FelipeRosa]

What if genetic operators were functions from programs to programs (instead of individuals to individuals)?

This way the operators wouldn't be responsible for computing the generated program's fitness and phenotype and then that program could be used to build an individual?

[FelipeRosa]

Ok, but how would the caller know how the program was built so it could compute the phenotype using the old individuals?

If I used the mutation operator to mutate a program from some individual, how would I know how the operator transformed it?

[FelipeRosa]

What if the operators' definitions could be written like this:

(deflang arith
  [(const (constant (- (rand-int 10) 5)))
   (var   (input (rand-int 2)))]

  [(plus  [e1 e2] (funcall + e1 e2))
   (minus [e1 e2] (funcall - e1 e2))
   (times [e1 e2] (funcall * e1 e2))]

  (mutation [t]
    (let [t1 (rand-program 2 false)
          t2 (rand-program 2 false)
          s  0.0001]
      (plus t (times (constant s) (minus t1 t2)))))

  (crossover [t1 t2]
    (let [a (rand)
          b (- 1 a)]
      (plus (times (constant a) t1) (times (constant b) t2)))))

Given that, we now know how to generate a new program from other programs using only the defined language primitives. But we still need some way to substitute, in mutation for example, t by some constant (parents' phenotypes) if we wanted to computed the program value and also by the parents' programs if we wanted to generate a new program.