on `atom-generators` and biases

[Vaguery]

One point of "manglish resistance" I've just identified in the "hard" problem I've been setting up is the unexpected way atom-generators is defined in many problems I've examined.

Intuitively—that is, from the stance of a new user examining the examples to emulate their "best practices"—setting up the atom-generators list should in some sense preserve the visible probabilities they imply. So for example in many cases I've looked at, the resulting probability that an input or ERC is created is no higher than the probability that any given instruction is used.

I understand that evolutionary search can "fix" any shortfall, and that one doesn't want to "bias" the search towards obvious needs, but I can't imagine it's a good thing for random mutation (for example) to tend towards the elimination of ERCs in all cases, which is the case in several problem setups I've looked at.

Here's an example from the digits problem

(def digits-atom-generators
  (concat (list
            \newline
            ;;; end constants
            (fn [] (- (lrand-int 21) 10))
            ;;; end ERCs
            (tag-instruction-erc [:integer :boolean :string :char :exec] 1000)
            (tagged-instruction-erc 1000)
            ;;; end tag ERCs
            'in1
            ;;; end input instructions
            )
          (registered-for-stacks [:integer :boolean :string :char :exec :print])))

In other words: if there's only one copy of each input or ERC function (as is true here), and hundreds of instructions (about 127 in this case), then all the actual ERCs and inputs will tend to be eliminated by mutation, and scant to begin with.

alternative:

I'd suggest an approach that takes a list of collections, and calls each one of the root items with equal probability, and then samples from that. So a list like the one above would produce 1/6 newlines, 1/6 inputs, 1/6 instructions, and so forth.

[Vaguery]

By the way, I've just checked this, and the qualitative behavior of the problem I'm working through is completely different when I increase the proportional representation of inputs and ERCs.

[thelmuth]

What you've described is really easy to do in the current system. For example, see the Digital Multiplier problem's atom-generators here. Here, 1/2 the time it picks a boolean instruction and 1/2 the time it picks an input or output instruction.

Basically, you just make a list of functions, where each function returns an instruction. The functions could be anything, but in the simplest case they'd just return a random thing from a list of instructions. Push will then pick one of your functions uniformly, run it, and use the instruction that's returned. This would do exactly what you describe -- give equal probability to each function, and then have the functions sample however they like.

This can be even more general if you want to. You could just define a single function (in a list, so that it gets selected 100% of the time) that assigns explicit probabilities/weights to each instruction. This would look something like this:

(def atom-generators
(list (fn [] (let [weights {:integer_add 5
                                    :integer_sub 2
                                    (fn [] (- (lrand-int 21) 10)) 50 ; This is an integer ERC with weight 50
                                    ...}]
               ; now pick random integer between 0 and sum of weights, and use it to select instruction
               )

Please excuse my pseudocode.

As you say, there will obviously be different results for different probabilities of using each atom-generator. I think Lee has at times simply thrown in multiple copies of generators that seem important. I usually just use 1 of each and let evolution sort it out.

[Vaguery]

I usually just use 1 of each and let evolution sort it out.

Yes, except :8ball: the founder effect is a perfectly valid kind of evolution, and does the opposite of what one really wants.

[thelmuth]

Does your :8ball: tell you which instructions evolution will think it doesn't need but actually needs a lot of? Mine doesn't, so if yours does I'd love to borrow it sometime :stuck_out_tongue_winking_eye:

[Vaguery]

Autoconstruct! :)

[Vaguery]

Joking aside you've done the "birthday polynomial without numbers" problem, right? I always make every GP class do that one. Set up a simple symbolic regression problem for the function y=YYYY + MM*x + DD*x^2, where YYYYMMDD is your birthday. Run it with all the instructions but no ERCs.

(adding that to my problem set)