Page 37 - 49A Field Guide to Genetic Programming

3.2 Step 2: Function Set 23

3.2.2 Sufficiency
There is one more property that primitives sets should have: sufficiency.
Sufficiency means it is possible to express a solution to the problem at hand
using the elements of the primitive set. 2 Unfortunately, sufficiency can be
guaranteed only for those problems where theory, or experience with other
methods, tells us that a solution can be obtained by combining the elements
of the primitive set.
As an example of a sufficient primitive set consider {AND, OR, NOT, x1, x2,
..., xN}. It is always sufficient for Boolean induction problems, since it can
produce all Boolean functions of the variables x1, x2, ..., xN. An example
of insufficient set is {+, -, *, /, x, 0, 1, 2}, which is unable to represent
transcendental functions. The function exp(x), for example, is transcenden-
tal and therefore cannot be expressed as a rational function (basically, a
ratio of polynomials), and so cannot be represented exactly by any combi-
nation of {+, -, *, /, x, 0, 1, 2}. When a primitive set is insufficient, GP
can only develop programs that approximate the desired one. However, in
many cases such an approximation can be very close and good enough for
the user’s purpose. Adding a few unnecessary primitives in an attempt to
ensure sufficiency does not tend to slow down GP overmuch, although there
are cases where it can bias the system in unexpected ways.

3.2.3 Evolving Structures other than Programs

There are many problems where solutions cannot be directly cast as com-
puter programs. For example, in many design problems the solution is an
artifact of some type: a bridge, a circuit, an antenna, a lens, etc. GP has
been applied to problems of this kind by using a trick: the primitive set is set
up so that the evolved programs construct solutions to the problem. This is
analogous to the process by which an egg grows into a chicken. For example,
if the goal is the automatic creation of an electronic controller for a plant,
the function set might include common components such as integrator,
differentiator, lead, lag, and gain, and the terminal set might contain
reference, signal, and plant output. Each of these primitives, when
executed, inserts the corresponding device into the controller being built.
If, on the other hand, the goal is to synthesise analogue electrical circuits,
the function set might include components such as transistors, capacitors,
resistors, etc. See Section 6.3 for more information on developmental GP
systems.

2
More formally, the primitive set is sufficient if the set of all the possible recursive
compositions of primitives includes at least one solution.