Algorithm Research 09/06/2017

I began today by studying the individual algorithms that make up out project.

  • L-system fractals
  • Cellular automata
  • Cartesian genetic programming

We begin by looking into one of the books listed in our sources “Math and Art, an Introduction to Visual Mathematics”

L-System Fractals

The book began by showing a simple fractal that branches outward twice from the original line. Each new line formed is 1/2 the original lines length, and the two lines split 60 degrees out from the original lines trajectory. However, the book also gets into the idea of non-deterministic fractals. The book does this by randomizing one value, the angles between branches, in its algorithm. This creates a randomized version of the original L-fractal. (1)

L-fractals would be an easy start to mess with in our program, and looking back from my genetic programming research, would be a good place to start experimenting with that. We could in theory, implement a simple genetic program with points on a screen, and use that to create a non-deterministic fractal.

Cellular Automata

Unlike L-systems, cellular automata operates on a grid, and not on a plane. The book gives us rule 18: for every square s in the second row iterated over, if the square immediately above it is filled in, leave square s blank. If the square above s to the left xor to the right is filled in, fill in s. However, if the square above s to the left and the square above s to the right is filled in, leave s blank. Otherwise leave s blank. These rules, of course can be played with. The book uses rule 18 to obtain a shape similar to the Sierpinski triangle. However, it also lists different rules that can be applied in different manners. In fact, iterating over square s based on those above it is not the only option. You can also base whether or not to fill in square s based on its surrounding neighbors on all sides.

Cellular automata isn’t just something that can grow outward, it can also change  inwardly if you take into consideration John Convey’s “Game of Life” with it. Where squares can actually turn white as well as black. This introduces Rule 123/45, where a square s that is black will only stay black if it has less than or equal to three neighbors, and become white otherwise, and a white square will only turn black if it has 4 or 5 black squares near it.

Cellular automata is so vast the book says, that to explore every iteration of cellular automata using not just the immediate neighbors of s, but also all those sharing a vertical corner, would take billions of years, and have 2^512 possible combinations. In artistic terms of our project, cellular automata could offer unique combinations and potentially be judged positively on an artistic metric.

Cartesian Genetic Programming

The important component to this project however, is Cartesian Genetic programming. This is an entirely new concept to both me an Taylor, and as started looking in sources written be Julian Miller.

Julian Miller defined Cartesian Genetic Programming as follows:

Cartesian Genetic Picture

“In CGP a program is represented as a rectangular array of nodes. The nodes represent any operation on the data seen at its inputs, and may implement any convenient programming construct (if, switch, OR, * etc.). All the inputs, whether primary data, node inputs, node outputs, or program outputs are sequentially indexed by integer. The function of the nodes are also sequentially indexed by integers. ” (Julian Miller 3 Cartesian Genetic Programming)

Evolutionary Algorithms

In Miller’s paper, it begins to describe concepts of genotypes, phenotypes, genes, mutation, and ….. These concepts are frequently used in biology, but are not so often used in Computer science terms. For this, I began looking at another book called Cartesian Genetic Programming by Julian Miller more clearly outlining the beginning of these terms, and evolutionary algorithms in general.

Chromosomes: A string of symbols, sometimes called genotypes

Genes: The symbols used in the chromosomes, they might be a list of integers, coordinates, or letter.

Initial Population: A series of randomly generated chromosomes

Fitness: A numerical representation of how “good” each chromosome is.

Parents: Members of the population that participate in recombination and create new children.

Children: The newly produced chromosomes from recombination.

Recombination: Selecting individual symbols from the parent chromosomes and recombining them into new children chromosomes.

Repair procedure: When recombination makes an incorrect permutation and must be adjusted.

Mutation: Randomly altering the chromosomes

Although we are still looking into understanding evolutionary algorithms and Cartesian genetic programming, it looks promising to potentially evolving art on our own metric.


[1] Sash Kalajdzievski, Math and Art: An Introduction to Visual Mathematics. Chapter 3, Similarities, Fractals, and Cellular Automata, CRC Press, 2008

[2] Julian Miller, What bloat? Cartesian Genetic Programming on Boolean problems. School of Computer Science, University of Birmingham, 2000.

[3] Julian Miller, Cartesian Genetic Programming. Natural Computing Series, 2011

One thought on “Algorithm Research 09/06/2017

Leave a Reply

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

You are commenting using your 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 )

Google+ photo

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

Connecting to %s