Plushy is a linear genome representation for Push programs.
Push programs may contain nested parenthesized expressions, like this:
(in1 0 integer_eq exec_if (1 "zero") (2 "not zero"))
These are represented without nesting in Plushy genomes, like this:
(in1 0 integer_eq exe_if 1 "zero" CLOSE 2 "not zero" CLOSE)
This linear format makes it easier to write genetic variation operators that have certain desirable properties, like uniformity.
When using the Plushy representation, one must specify, for each instruction, how many parenthesized expressions (also called “code blocks”) should follow each instance of that instruction. For example, for translating the expression above, the translator must know that each instance of exec_if should be followed by two code blocks. The translator then adds closing parentheses where indicated by CLOSE genes, with additional parentheses added to the end of the program if necessary.
Plushy genomes can also include SKIP genes, each of which will cause the following gene to be skipped over during translation. For example, the Plushy (1 SKIP 2 3) translates to the Push program (1 3).
History and links
In the earliest Push-based genetic programming systems, genetic variation was performed directly on the nested Push program structures, using operators similar to those used in Koza-style tree-based genetic programming.
When it became clear that uniform variation could be helpful, a generic operator called ULTRA was developed which still operated on possibly-nested Push programs, but translated them into linear sequences prior to variation, and back into Push programs afterwards. Details of the ULTRA operator, along with a rationale for preferring uniform variation, can be found here.
It soon became clear that it would be simpler and better to use linear genomes throughout the evolutionary process, translating genomes into programs only when they needed to be run for the sake of assessment. The genome format developed for this purpose was called Plush, with the “l” added to Push to indicate Linearity. Plush uses “epigenetic markers” to indicate the placement of closing parentheses, and potentially for other purposes as well. Details of the Plush representation are described here and here.
While Plush provides benefits over previous representations for Push programs, the epigenetic markers add complexity to the representation scheme and to software that manipulates genomes. Plushy was developed as a simpler alternative that seems to provide all of the advantages of Plush, but without the unnecessary complexity of epigenetic markers. The “y” at the end of the name indicates that it is not Plush, but it is close. Details of the Plushy representation, and comparison of the utility of Plush vs. Plushy representations, can be found here.