Cartesian Genetic Programming and Week Goals 09/11/2017

Research has continued into the details of Cartesian Genetic Programming, or CGP, as well as a proposed outline for this weeks work.

Cartesian Genetic Programming

On looking further, CGP is an implementation of genetic programming using a  directed acyclic graph represented on a graph of nodes.

Cartesian genetic programming uses nodes in a grid-pattern that store a function, and the location of the previous node used on the grid from them. A simple diagram of max(x*y , 3+x*y) on  grid of nodes is shown below:

Graph based programming

When implementing recombination for genetic programming, Miller gives us another diagram with a description:

CGP Recombination

1. A random active node is selected in each parent (crossover point)
2. A subgraph including all the active nodes which are used to compute the output value of the crossover point in the first parent is extracted.
3. The graph is inserted into the second parent to generate the offspring (if the x coordinate of the insertion node in the second parent is not compatible with the width of the subgraph, the subgraph is wrapped around)

The purpose of putting these nodes on a graph is in order to better recombine. The limits of the grid mean that if a subgraph falls off it needs to be wrapped around, and the graph cannot extend certain lengths. It allows for the function calls to be recombined in a limited way.

These also nodes don’t necessarily hold the data one would expect, but rather, the node will contain a genotype that’s genes contain integers of where to get the data. These integers correspond to a function- look up table.

CGP Parts of a Node

In CGP there are two types of genes. A function gene as shown above is #012, and corresponds to a number in the function look-up table. The other is a connection gene, shown above as #103 and #101, which corresponds to an address in a data-structure like an array.

“Nodes take their inputs in a feed-forward manner from either the output of nodes in a previous column or from a program input (which is sometimes called a terminal). The number of connection genes a node has is chosen to be the maximum number of inputs.”

CGP Node Inputs

These outputs will be passed along to the next node for further function calls to be made. Another example of a terminal node would be the node containing “3” in our first example.

Goals

With research done into CGP and Art Theory, we can now begin to develop a more concrete starting hypothesis rooted in the idea of modern art theory. This will primarily be measured in terms of aesthetic shape, line, and color.

As such, our weeks next goal is for

  • Begin development on cellular automata function in our Java environment
  • Develop a preliminary concrete hypothesis

Cited
[1] Julian Miller, What bloat? Cartesian Genetic Programming on Boolean problems. School of Computer Science, University of Birmingham, 2000.
[2] Julian Miller, Cartesian Genetic Programming. Natural Computing Series, 2011

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s