Suggestions for using Grammatical Evolution

Limit your search space

Part of the appeal in using such a technique derives from not necessarily knowing the search space of possible solutions. In other words, if you had a better technique that would effectively solve the problem you would use it. So, there can be a tendency to simply try everything that you can imagine, and let grammatical evolution sort it out.

This will not work, because you can easily build a search space that is so enormous, that even with many generations, only a fraction of the space can be evaluated.

Try to use as few choices as you can, but not less than you need. Unfortunately, this is art not science for this choice.

Limit Your Program Size

An equation or code generation machine does not know at the time that what is being produced is useful or not. The code for any particular iteration can end up with a repetitive, degenerate looping of odd functions that have no meaning or usefulness. By limiting the program size, your process can cut off the program generation so that less time is used testing unproductive programs.

Use Program Size as Part of Your Fitness Value

Suppose that your process generates many solutions that are sufficently close to your fitness value, but many of those solutions have code that is fairly convoluted, such as sin(cos(-3.3 * sin(cos(2. * x)))). Push the solution toward simple and elegant approaches by using the size of the program to modify your fitness value.

The generated test program runs within the name space of the genotype. This means that you have access to the self values.

Here is a slight example to illustrate the concept. Just before executing the generated program, a copy is put in the local_bnf of the genotype object. Assume that the purpose of a run is to maximize a fitness_value:

... the rest of your generated program would be above here

#
fitness_value = <some generated value here>

program_size = len(self.local_bnf['program'])

fitness_value /= program_size

Larger programs would decrease the fitness value more than smaller programs, giving your process a basis for favoring smaller solutions. In addition, if a particular function is being built, you could simply parse the program for that function and evaluate on the size of that function alone.

Design Your Fitness Value Approach

Try to design the process to generate fitness values that can move ever closer to an effective solution. Suppose your process was a random process and you simply wait for the best fitness value to show up. Generally speaking, such a process will take longer than a process where the system can learn from previous generations and effectively improve on past generations. So, where possible try to design your process so that the right answer is not just a shot in the dark.

Create Your Own Fitness Class

You can create your own fitness class. For example, a comparison could be made of the distribution of fitness values versus your own criteria. Such a technique might derive from the need to create a family of solutions, rather than just a one.

This technique for doing this could be as follows:

Create a function that accepts the fitness_list and evaluates in some fashion.
Return True to continue processing.
Return False to end the process.
Add the function to the grammatical evolution class.

For example: