Gramatical evolution doesn't result on creating good constants

Question

I'm using Grammatical Evolution for symbolic regression tasks (i.e. searching the space of mathematical expressions to find the model that best fits a given dataset).

I'm evolving solutions according to a user-specified grammar:

 (0)
 <expr> ::= <expr> <op> <expr>      (0)
          | <const>                 (1)
          | <var>                   (2)
          | <unop>                  (3)

 (1)     
 <op> ::= *     (0)
        | +     (1)
        | -     (2) 
        | /     (3)

 (2)
 <const> ::= 0.1            (0)
           | 1.0            (1)
           | 10.0           (2)

 (3)
 <var> ::= x                (0) 

 (4)
 <unop> ::= sin             (0)
          | cos             (1) 
          | -               (2)

The population is a collection of arrays of integers. For example:

[0, 1, 2, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1]

is the genotype of the individual +(x, +(1, +(1, 1)) (function $x + 3$).

The translation is performed using the integers to look up the table which describe the BNF grammar:

Step  Sequence  Rule   State
  1      0       0.0   <expr> <op> <expr>
  2      1       1.1   <expr> + <expr>
  3      2       0.2   <var> + <expr>
  4      0       3.0   x + <expr>
  5      0       0.0   x + <expr> <op> <expr>
  6      1       1.1   x + <expr> + <expr>
  7      1       0.1   x + <const> + <expr>
  8      1       0.1   x + 1.0 + <expr>
  9      0       0.1   x + 1.0 + <expr> <op> <expr>
 10      1       1.1   x + 1.0 + <expr> + <expr>
 11      1       0.1   x + 1.0 + <const> + <expr>
 12      1       2.1   x + 1.0 + 1.0 + <expr>
 13      1       0.1   x + 1.0 + 1.0 + <const>
 14      1       2.1   x + 1.0 + 1.0 + 1.0

The fitness function is the reciprocal of the sum, taken over the fitness cases, of the absolute error between the evolved and the target function.

My problem is that, while the algorithm finds the general model, it often has trouble finding the right constants.

For example, if the target function is $x^2 + x - 12$, it finds something like:

$$x^2 + x - (10 + \sin(x))$$

or

$$x^2 + x - (1 + 1) \times (10 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1) \times ((10 - (10 / (1 + 1)) - (10 / (1 + 1 + 1 + 1 + 1)))$$

which is correct but requires a great effort to discover the constant.

Are there efficient techniques for generating numerical constants?

Answer 1

It sounds like you're saying that your approach is able to effectively find the shape of the expression, but it takes it a lot longer to find the right constants.

One possible approach is to generate an expression of the correct shape using your genetic programming method, then fill in the constants using a different method. I would recommend trying numerical optimization techniques. Replace each constant in your expression with a symbolic value $\alpha$. Each different constant (at each different syntactic position) gets its own symbolic value. Then, use numerical optimization to find the value of the constants.

Example 1. For instance, consider your complex expression $x^2 + x - (\text{stuff})$. Replace this with $x^2 + x - \alpha$ (when you have an entire subtree that contains only constants, no variables, replace the entire subtree with a single symbolic value). We now get a function $f(x,\alpha) = x^2 + x - \alpha$. Use the training set $(x_1,y_n),\dots,(x_n,y_n)$ to define an objective function:

$$\Phi(\alpha) = \sum_{i=1}^n (f(x_i,\alpha) - y_i)^2.$$

Finally, use numerical optimization methods to search for $\alpha$ that minimizes $\Phi(\alpha)$. You could try gradient descent, Newton's method, or other techniques. The value for that subtree deriving using genetic programming supplies a reasonable starting point for the search.

Example 2. In some cases, you will have more than one constant. For instance, you might get the expression $x^2 + 2x - 3$. Replace each constant with a symbolic value, so we get $f(x,\alpha,\beta) = x^2 + \alpha x - \beta$. Now you can derive an objective function as above:

$$\Phi(\alpha,\beta) = \sum_{i=1}^n (f(x_i,\alpha,\beta)-y_i)^2,$$

and use optimization methods to search for $\alpha,\beta$ that minimize $\Phi(\alpha,\beta)$.

Answer 2

In Grammatical Evolution there are three well known approaches to the problem of constant creation:

1. expression based (the "traditional" approach). This is what you're using (arithmetic operators are required to produce new constants);

2. digit concatenation. An example is:

       <int> ::= <int><digit> | <digit>
       <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
   

   or

       <catR> ::= <cat> <dot> <cat> | <cat>
       <cat>  ::= <cat> <catT> | <catT>
       <catT> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
       <dot>  ::= .
   

   These allow the creation of constants through the concatenation of digits. Digit concatenation is usually considered superior over the expression based approach;

3. grammatical ephemeral random constants. Generate a number of real values within a prespecified range and add them to the grammar to be used.

       <ephemeral> ::= <ephemeral> <op> <ephemeral> | <ephemeralT>
       <ephemeralT> ::= "x randomly generated real constants"
   

   Random numbers become available to the evolutionary process throughout the lifetime of the experiment (they are part of the grammar itself).

   This gives a better coverage of the search space.

   A variation of this idea requires the introduction of the production rule:

       <constant> ::= ephemeral
   

   The terminal symbol ephemeral carries a special meaning: whenever it is selected during the program's decoding process, the next n bits are decoded into a real number. Afterwards, the decoding process resumes normally past those n decoded bit.

   _{(A New Approach for Generating Numerical Constants in Grammatical Evolution)}

   This effectively decouples the number of bits used to encode the grammar's production rules from the number of bits used to represent a constant.

   There isn't a clear winner between (2) and (3). Both mitigate the problem of constant creation.

Discovering (/tuning) useful numerical constants is a weakness of Genetic Programming (not only of Grammatical Evolution), so you might find useful to explore further the GP literature (especially the mixed approaches GP + local search).

For further details:

• "Analysis of a Digit Concatenation Approach to Constant Creation" by Michael O'Neill, Ian Dempsey, Anthony Brabazon, C.Ryan
• Grammatical Constant Creation by Ian Dempsey, Michael O'Neill and Anthony Brabazon
• A New Approach for Generating Numerical Constants in Grammatical Evolution by Douglas Augusto, Helio Barbosa, André Barreto, Heder Bernardino