lspector / Clojush

The Push programming language and the PushGP genetic programming system implemented in Clojure.
http://hampshire.edu/lspector/push.html
Eclipse Public License 1.0
331 stars 94 forks source link

Document Plush genomes and Push programs in the repo #128

Closed NicMcPhee closed 8 years ago

NicMcPhee commented 9 years ago

I think you should have either (a) a Markdown document in the repo or (b) a repo wiki page that documents Plush genomes and Push programs. My inclination would be towards the former since then the docs are right in the code, but I'm open to other thoughts on the matter.

This might be something I'd be willing to pick up as a semi-outsider.

Vaguery commented 9 years ago

Please!

Vaguery commented 9 years ago

Please?

saulshanabrook commented 8 years ago

I'm gonna try to tackle this

saulshanabrook commented 8 years ago

Key quote from Tom's paper:

In a change from previous versions of PushGP, the most recent version of Clojush does not evolve Push programs directly, but instead uses a separate linear genome representation that we translate into Push programs prior to execution. The new Plush4 genomes are linear sequences of instructions that may have one or more epigenetic markers attached to each instruction. The epigenetic markers affect the translation of the Plush genomes into Push programs. For example, the silent marker is a boolean that tells whether a particular instruction will appear in the translated program.

When evolving Push programs directly, we often found that parenthesis-delimited code blocks would rarely evolve in conjunction with instructions that made use of them. One of the motivations for moving to linear Plush genomes was that we could require that Push instructions that make use of code blocks be followed by them. With this change, every instruction that takes one or more argument from the exec stack implicitly opens one or more code blocks. Additionally, each instruction has a close epigenetic marker that tells the number of code blocks to end after that instruction. Thus, during translation from Plush genome to Push program, an open parenthesis is placed after each instruction that requires a code block, and a matching closing parenthesis is placed after a later instruction with a non-zero close marker. Note that these code blocks can create hierarchically nested Push programs. For example, if a new code block B is opened after the start of code block A, the next close marker will close block B, not block A. If not enough close markers occur by the end of a program to match all opened code blocks, all opened blocks are simply closed.

Another advantage of moving to linear Plush genomes instead of traditional tree genomes or hierarchical Push programs is that it enables simple use of uniform genetic operators. The uniform genetic operators implemented in Clojush are inspired by the operator ULTRA, which was designed for Push programs, requiring them to be translated into a linear form and back [124]. The main crossover operator, alternation, traverses two parents in parallel while copying instructions from one parent or the other to the child. While traversing the parents, copying can jump from one parent to the other with probability specified by the alternation rate parameter. When alternating between parents, the index at which to continue copying may be offset backward or forward some amount based on a random sample from a normal distribution with mean 0 and standard deviation set by the alignment deviation parameter. We also use a uniform mutation operator that traverses a parent and with some probability replaces each instruction with a random one. In order to manipulate the locations of closing parentheses, we include a uniform close mutation operator that may increment or decrement the close epigenetic marker of any given instruction. Finally, we allow genetic operator pipelines that combine multiple operators; for example, we often use alternation followed by uniform mutation, which closely resembles ULTRA [124].

saulshanabrook commented 8 years ago

Why do instructions that take an argument from the exec stack need a code block and not just a normal instruction on it? For example, if my push program was (exec_dup 1) wouldn't this work fine? I would just end up having two 1s on the integer stack on the end. If it was (exec_dup (1 2)) this would also work, turning into ((1 2) (1 2)) and then (1 2 (1 2)) etc.

saulshanabrook commented 8 years ago

I am trying to test translating plush to push programs.

I can't figure out why this fails:

;; Anything you type in here will be executed
;; immediately with the results shown on the
;; right.
(use 'clojush.translate)
(use 'clojush.problems.demos.odd-with-uniform-silence-mutation)
(use 'clojush.individual)

(defn plush_to [plush] (translate-plush-genome-to-push-program (assoc (make-individual) :genome plush) argmap))
(plush_to (list
           {:close 1, :silent false, :instruction 'code_frominteger}
           {:close 0, :silent false, :instruction 'genome_yank}
           {:close 0, :silent false, :instruction 'float_eq}
           {:close 0, :silent false, :instruction 'code_size}))

The last line fails with:

NullPointerException   clojure.lang.Numbers.ops (Numbers.java:1013)
saulshanabrook commented 8 years ago

Thanks @lspector for help getting this working:

;; Anything you type in here will be executed
;; immediately with the results shown on the
;; right.
(use 'clojush.translate)
(use 'clojush.pushgp.pushgp)
(use 'clojush.problems.demos.odd-with-uniform-silence-mutation)

(reset-globals argmap)

(defn plush_to [plush] (translate-plush-genome-to-push-program {:genome plush} @push-argmap))
(plush_to [
           {:close 1, :silent false, :instruction 'code_frominteger}
           {:close 0, :silent false, :instruction 'genome_yank}
           {:close 0, :silent false, :instruction 'float_eq}
           {:close 0, :silent false, :instruction 'code_size}])
thelmuth commented 8 years ago

Why do instructions that take an argument from the exec stack need a code block and not just a normal instruction on it? For example, if my push program was (exec_dup 1) wouldn't this work fine? I would just end up having two 1s on the integer stack on the end. If it was (exec_dup (1 2)) this would also work, turning into ((1 2) (1 2)) and then (1 2 (1 2)) etc.

You are absolutely correct that (exec_dup 1)would work just fine. The problem isn't a syntactic one, but instead is in regards to the evolutionary utility of exec stack instructions being followed by a code block or not. In order for most exec stack instructions to do something interesting, they should be followed by a code block -- for example, looping with a single instruction in the loop usually isn't very helpful. Over many observations when not forcing code blocks after exec instructions we noticed that code blocks rarely appeared in the right places. So, with Plush we ensure that every instruction that uses an item from the exec stack is followed by a code block (or more than one for instructions like exec_if). Of course, the block may only contain one instruction, which would be identical to not having the block.

saulshanabrook commented 8 years ago

@thelmuth That makes sense, thank you for the explanation.

Why do the noop_delete_prev_paren_pair and noop_open_paren instructions exist?

lspector commented 8 years ago

I think that noop_delete_prev_paren_pair exists because while (exec_dup (1)) is nearly equivalent to (exec_dup 1) it does differ in some ways, e.g. the number of execution steps that it takes to evaluate (which may interact with the evalpush-limit) and the way that it may interact with code-manipulating code. So noop_delete_prev_paren_pair exists to make it possible to get things like (exec_dup 1) (and similar structures following other exec instructions).

I think that noop_open_paren exists so that you can get parentheses in places other than after exec instructions, which you might want in the context of various other kinds of code-manipulating code.

thelmuth commented 8 years ago

What Lee said. I haven't ever used these, but Lee wanted them available when I was implementing Plush.

lspector commented 8 years ago

Yep, I didn't want the switch to Plush to mean that some Push programs would be impossible to produce. I have no real evidence that it's important to be able to encode the programs that would otherwise be impossible, but I wanted to ensure that the move to Plush didn't rule things out, and I suspect that noop_open_paren might be important in some cases.

saulshanabrook commented 8 years ago

Added to discourse site: https://push-language.hampshire.edu/t/plush-genomes/279