Assertive Polynomial Evolution

Overview

Below, and in the accompanying PolynomialEvolution example (C++/Cinder), we will develop a set of tools that allows the user to write and graph polynomial expressions as well as apply a group of “assertion constraints” to an evolutionary process that results in the production of a set of lines or curves whose properties meet the user’s desired criteria.

What is a polynomial expression?

Here are some examples of polynomial expressions:

y = x + 2
y = x2
y = 3.5x2 – 5
y = 2x3 – 4x2 + 7x – 2.5

For a general explanation of the concept, see Polynomials on Wikipedia. For our purposes, we will focus on single-variable expressions using only the addition and subtraction operations. This form is easy to encode and allows us to represent a broad range of straight lines and curves in a two-dimensional Cartesian coordinate system.

A data structure to store expressions of the kind described above might look like this:

array< pair< Coefficient, Exponent > >

Each < Coefficient, Exponent > pair will represent a single element in a polynomial expression. So, for example, 3.5x2 would be stored in a pair as: < 3.5, 2.0 >. The array of pairs will together form a complete polynomial expression.

The expression y = 2x3 – 4x2 + 7x – 2.5 would produce the following array:

< 2.0, 3.0 >, < -4.0, 2.0 >, < 7.0, 1.0 >, < -2.5, 0.0 >

Notice that in the above, the constant element “-2.5” is raised to the exponent 0.0 since x0 equals the constant 1. Also notice that we use negative coefficient values in the second and fourth elements to encode subtraction operations rather than the default addition.

To find the y value for any particular x, we simply need to iterate over the array and sum the elements in the following manner:

for( i = 0; i < array.length; i++ )  {  y += array[ i ].Coefficient * pow( x, array[ i ].Exponent )  }

One reason to represent curves with a data structure like the above is that by storing the formula itself, we maintain the ability to reproduce any portion of the curve at any resolution we choose. If we instead stored the data in a “rasterized” form such as an array of discrete two-dimensional coordinates that sample a particular portion of a curve, we would lose the ability to extrapolate other portions or resolutions of the curve.

By representing the curve expression rather than its sample data, we also make it substantially easier to access auxiliary information about the expression (such as its derivative, second derivative, etc.) that might be helpful to the user in ways that we will explore below.

What is an assertion?

In brief, an assertion is a type of programmatic expression used to test whether a piece of software behaves as the programmer expects. Specifically, an assertion is a true-false statement that is expected to always evaluate to true. If the assertion returns false, we say that the assertion has failed (and therefore that there is likely something wrong with the software’s logic). For a general explanation of the concept, see Assertion on Wikipedia. To test whether a function we’ve written has been implemented correctly, let’s say a simple addition function: add( Number, Number ), we would write an assertion like:

assert: add( 2, 2 ) equals 4

To test a function like the above, we would likely create multiple assertions to ensure that the function works with the full range of expected inputs. For example, we should also make sure that the add() function works with negative numbers:

assert: add( -3, 2 ) equals -1

If we take this concept far enough, it’s possible to imagine that we could let an entire software development process be guided by a (possibly very large) set of assertions. This approach to software development is generally called test-driven development (Also see, test-driven development in C++). The basic idea is that the developer breaks the complete set of the application’s desired behaviors into a group of granular test cases and then writes the minimum amount of code required to satisfy each test.

What does this have to do with evolution?

Extending from the concept of test-driven development, it is possible to imagine that if each of an application’s desired behaviors can be distilled into a test that returns a simple statement of either “this was implemented correctly” or “this was not implemented correctly,” then we may not even need a programmer to implement the feature’s underlying logic.

In the spirit of the old “monkey-typewritter” paradigm, if we randomly typed characters for long enough, we should theoretically arrive at a valid C++ implementation of our above add() function. Of course, this would take quite a while, especially for a syntactically complex language like C++. By introducing a bit more structure into this search process, though, we can greatly increase our chances of arriving at a valid solution in a reasonable amount of time.

Much like our earlier work in creating valid Sudoku puzzles using a genetic algorithm, we can imagine that each granular unit of a program or function could be treated as a gene within a sequential genome, which is then evaluated in terms of its success in delivering some particular expected behavior. This extension of genetic algorithms is generally called genetic programming.

One difficulty with genetic programming is that programming languages, much more than a 9×9 Sudoku board, tend to have pretty open-ended capabilities and so the number of correct ways of implementing a given function in a particular programming language is tremendously outweighed by the number of ways that an incorrect or completely invalid expression could be formed. This, of course, could be mitigated by limiting the vocabulary and syntax options available to the genetic programmer. It can also be helped by ensuring that each feature that is subject to an evolutionary testing process is as granular as possible. In other words, given the directive “build a house,” it is much less likely that the computer will arrive at something like what we had in mind than if we break down the directive into small pieces that relate to individual components of this much larger task.

Polynomial expressions offer a wide variety of outputs (at least of a particular kind), but have a straightforward vocabulary and syntax. For this reason, polynomial expressions are a good candidate medium to explore some of the above ideas. Polynomial expressions can be employed in many areas of computational design thinking – both directly and abstractly. In a literal sense, we might use them to represent lines and curves that we would like to draw to the screen. In a slightly more abstracted sense, we could a polynomial expression to control an animation timing a la Robert Penner’s Easing Functions.

To enable the user to guide the evolution of polynomial expressions towards a specific set of traits, we will create a small domain-specific language (DSL) – “programming language” with a relatively limited vocabulary and syntax that is geared towards solving a specific type of problem. Our DSL will provide a set of comparative assertions that can be applied to two polynomial expressions (or to the derivatives of these expressions) within a given parameter range. These assertions include:

A is equal to B
A is not equal to B
A is greater than B
A is greater than or equal to B
A is less than B
A is less than or equal to B

This allows us to add an assertion constraint to our evolutionary process, which tells the computer that we are looking for a polynomial function where:

y is greater than or equal to 0.0 in the x range [ 0.0 .. 1.0 ]

This assertion would be true of numerous polynomial functions including:

y = x
y = x2
y = x3
(to name just a few)

However, it would not be true for:

y = -x
y = -x2
y = -x3
(to name just a few)

As we can see from the above, a single assertion may help to eliminate a huge set of undesired outputs, but is not likely to be sufficient in completely describing what we’re looking for. For this reason, our DSL should allow us to attach numerous assertions to the search, favoring outputs that satisfy as many of the assertions as possible.

Furthermore, since polynomial expressions describe continuous functions and since we are including a parameter range in our assertions, there is no reason that our assertions need to take a strict binary form in stating their success or failure.

For example, given the expression y = x3, the assertion:

y is greater than or equal to 0.0 in the x range [ -1.0 .. 1.0 ]

will be false in the x range [ -1.0 .. 0.0 ) and true in the range [ 0.0 .. 1.0 ]. If our assertion output were strictly binary, we would be forced to return false here, even though the assertion was in fact successful for half of the range. We can easily reason that being successful for half of the range may suggest that we’re at least “on the right track” and would therefore be losing some forward momentum in our search by discarding this result entirely. Therefore, in our system, we have setup assertions to return a floating point value where 0.0 represents complete failure, 1.0 represents complete success and everything in between represents some level of partial success. This continuous score will diminish the “all-or-nothing” quality of the binary assertion outputs.

What are derivatives and how do they relate to this?

According to Wikipedia, “In calculus, the derivative is a measure of how a function changes as its input changes.  Loosely speaking, a derivative can be thought of as how much one quantity is changing in response to changes in some other quantity.”

We can probably already see how this might apply to our polynomial assertion language. The derivative of a polynomial expression provides some key “meta-data” about the function’s behavior over a given input range. The user could potentially employ this information to further articulate the desired characteristics of the evolutionary output. For instance, if we were designing an expression that will be used to control an animation timing, we might want to specify that the animated value never change too rapidly. Such a specification could be easily made in our DSL by applying a comparative assertion to the derivative of the candidate polynomial and a line or curve that represents the maximum allowable rate of change for the given parameter range.

We could further extend the capabilities of our DSL by adding other ways of assessing the meta-properties of a given expression. For example, an expression’s second-derivative (the derivative of the expression’s derivative) might be useful. But for the time being, our DSL will only support polynomial expressions and their first derivatives.

Here is a video of the polynomial evolution process being applied to a set of two assertions:

The assertions (depicted with yellow lines in the video) are as follows:

the derivative of the candidate expression is less than the value of 2x+2 in [ -10.0 .. 10.0 ]
the derivative of the candidate expression is greater than the value of 2x-2 in [ -10.0 .. 10.0 ]

[vimeo clip_id=78572655 width=600 height=600 ]

This results in an output expression (depicted in cyan) that closely matches the expression y = x2 (depicted in green), the curve we were secretly hoping to achieve.

Wrapping Up and Moving Forward

Given that the concepts of polynomials, derivatives and so forth are somewhat abstracted from how we would generally be thinking about lines, curves and control functions in a design environment, it might also be nice to abstract our domain language even further towards a form that is more easily parsed by a human. Something like the following would be useful:

assert: the curve should be very steep in the in the x range [ 0.0 .. 1.0 ]

In some ways, it doesn’t seem too insurmountable to achieve something like this. But, there are some additional considerations that we would have to factor into our system. Most notably, “very steep” is a relative concept. We can much more easily construct a way of dealing with a statement like “A is more steep than B.” But saying that a curve should be “very steep” will mean different things to different users for different curves and parameter ranges. To achieve useful results, we would need to find a way of addressing how these various contexts influence the meaning of “steepness.”

In the case of polynomial expression creation, since the output has an inherently visual nature, perhaps it would be best to works towards ways of allowing the user to encode assertions in explicitly visual ways. We’ll keep an eye towards that as we move forward.

Leave a Reply