Application of Genetic Programming to the Choice of a Structure of Multipoint Approximations

Vassili V. Toropov		Luis F. Alvarez
Department of Civil and Environmental Engineering University of Bradford, Bradford BD7 1DP, West Yorkshire, UK
V.V.Toropov@bradford.ac.uk (OUT)		L.F.Alvarez@bradford.ac.uk (OUT)
http://www.brad.ac.uk/staff/vtoropov (OUT)		http://www.student.brad.ac.uk/lfalvare (OUT)

		Introduction

Nowadays methods based on approximation concepts take dominant position in design optimization and the development of new high quality approximation functions has become a separate problem [2, 13]. The choice of the structure of approximation functions is the subject of this study.

Response surface methodology [11, 12] is a method of constructing approximations of the system behaviour using results of response analyses calculated at a series of points in the design variable space. A mid-range variant of this approach, called the multipoint approximation method (MAM) [5, 14-16] will be used here. One of the main problems in the application of such techniques is the necessity to select a structure of the approximation function.

This study attempts to develop and use a Genetic Programming (GP) methodology for the creation of an approximation function structure of the best possible quality, as part of the multipoint approximation technique.

		Multipoint Approximation Method

According to the MAM, the original optimization problem:

(1)

is replaced by a succession of simpler mathematical programming problems:

(2)

where k is the iteration number. The functions _j^k (x) (j=0,...,M) in each iteration present mid-range approximations of the corresponding original functions F_j (x). The solution of an individual sub-problem becomes a starting point for the next step, the move limits A_i^k and B_i^k are changed and the optimization is repeated iteratively until the optimum is reached.

It is proposed to choose the structure of the functions _j^k (x) using the Genetic Programming methodology.

		Genetic Programming

Genetic Programming [7] is a branch of Genetic Algorithms (GA) [3]. Its basis is the same Darwinian concept of survival of the fittest. The innovation of the GP is the use of more complex structures. While a GA uses a string of numbers to represent the solution, the GP creates computer programs with a tree structure. In our case of design optimization, a program represents an empirical model to be used for approximation of response functions in the original optimization problem. A typical program, representing the expression ( x₁ / x₂ + x₃ )², is shown in Figure 1.

Figure 1. Typical tree structure representing the expression

These randomly generated programs are general and hierarchical, varying in size and shape. GP's main goal is to solve a problem by searching highly fit computer programs in the space of all possible programs that solve the problem. This aspect is the key to finding near global solutions by keeping many solutions that may potentially be close to minima (local or global). The creation of the initial population is a blind random search of the space defined by the problem. In contrast to a GA, the output of the GP is a program, whereas the output of a GA is a quantity.

The programs are composed of elements from a terminal set and a functional set, called nodes.

Terminal Set				Design variables: x1 , x2 , ..., xN.
Functional Set				Mathematical operators that generate the regression model:  { +,  *,  /,  x y,  etc. }

The functional set can be subdivided into binary nodes, which take any two arguments (like addition), and unary nodes, which take one argument, e.g. a square root. All the functions and terminals must be compatible in order to faultlessly pass information between each other (closure property).

		Fitness Function

When selecting randomly a tree to perform any genetic operation, the so-called fitness proportionate method is used here. This method specifies the probability of selection on the basis of the fitness of the solution.

In problems of empirical model building, the most obvious choice for the estimation of the quality of the model is the sum of squares of the difference between the simplified model output (2) and the results of runs of the original model (1) over some chosen plan (design) of experiments. In a dimensionless form this measure of quality of the solution can be presented as follows:

(3)

where, for a given tree, _p = ( x_p ) is the simplified function value corresponding to the p-th point of the plan of experiments and F_p = F ( x_p ) is the original function value at the same point.

If Q(S_i) is the measure of quality of the solution S_i, Q_u is the upper limit on this measure of quality for all N_t members of the population, ntp_max is the maximum allowed number of tuning parameters, ntp_i is the number of tuning parameters contained in the solution S_i and c is a coefficient penalizing the excessive length of the expression, the fitness function (S_i) can be expressed in the following form:

(4)

The probability that the solution (S_i) will be selected is

(5)

Programs with greater fitness values (S_i) have a greater chance of being selected in a subsequent genetic action. Highly fit programs live and reproduce, and less fit programs die.

		Genetic Operators

Model structures evolve through the action of three basic genetic operators: reproduction, crossover and mutation. Figure 2 shows a flowchart of the process.

Figure 2. Flowchart of Genetic Programming methodology

In the reproduction stage, a strategy must be adopted as to which programs should die. In this implementation, trees with fitness below the average are killed. The population is then filled with the surviving trees according to fitness proportionate selection.

New programs are created by crossover and mutation, which provide diversity of the population. Crossover (Figure 3) combines good information from two trees (parents) while mutation (Figure 4) protects the model against premature convergence and improves the non-local properties of the search.

Figure 3. Crossover

Figure 4. Mutation

An additional operator, elite transfer, is used to allow a relatively small number of the fittest programs, called the elite, to be transferred unchanged to a next generation, in order to keep the best solutions found so far. As a result, a new population of trees of the same size as the original one is created, but it has a higher average fitness value.

		Implementation

The algorithm has been implemented in C++ following recommendations given in [6] and a sample program presented in [8].

In the process of finding the structure of approximations by the genetic search as described above, it is necessary to address two important problems: the choice of the plan (design) of experiments, and the model tuning (evaluation of tuning parameters) prior to the fitness evaluation.

		Design of Experiments

In this paper, the approach suggested by Audze and Eglais [1] and used later by Rikards [10] is followed. It considers a non-traditional criterion for elaboration of plans of experiments which is not dependent on the mathematical model of the object or process under consideration. The input data for the elaboration of the plan only include the number of factors N (number of design variables) and the number of experiments P. The main principles in this approach are as follows:

The number of levels of factors (same for each factor) is equal to the number of experiments and for each level there is only one experiment.

The points of experiments are distributed as uniformly as possible in the domain of variables. There is a physical analogy with the minimum of potential energy of repulsive forces for a set of points of unit mass, if the magnitude of these repulsive forces is inversely proportional to the distance squared between the points: (6)

The plan of experiment is characterized by a matrix, which contains the levels of factors for each of P experiments. For example, for a number of factors (design variables) N = 2 and P = 10, the matrix is

(7)

The corresponding plan of experiments is shown in Figure 5.

Figure 5. Plan of experiments for N = 2 and P = 10

		Model Tuning

The simplified model is characterized not only by its structure (to be found by the GP) but also by a set of tuning parameters a to be found by model tuning, i.e. the least squares fitting of the model into the set of values of the original response function:

(8)

The allocation of tuning parameters a to an individual tree follows the basic algebraic rules. To identify the parameters of the expression by the nonlinear least-squares fitting, i.e. to solve the optimization problem in (1), a combination of a GA and a nonlinear mathematical programming method [9] is used. The output of the GA is the initial guess for the subsequent derivative-based optimization method which amounts to a variation of the Newton's method in which the Hessian matrix is approximated by the secant (quasi-Newton) updating method. Once the technique comes sufficiently close to a local solution, it normally converges quite rapidly. To promote convergence from poor starting guesses the algorithm uses the adaptive update of the Hessian and, consequently, the algorithm is reduced to either a Gauss-Newton or Levenberg-Marquardt method.

		Example

In order to test the genetic programming algorithm, a three-bar truss optimization problem described in [4] was used. The two design variables x₁ and x₂ describe the cross-sectional areas of individual bars (Figure 6), the objective function is the volume of the material and the constraints limit the stresses in all bars and the displacement of the free node:

Figure 6. Three-bar truss optimization problem

The set of response data was generated using the plan of experiments (7), which was then used to build the global approximations of the objective function and the constraints.

The following parameters have been used:

population size:

Nt = 100

proportion of the elite:

Pe = 0.2

probability of mutation:

Pm = 0.001

	functional set:	binary functions	+, *, /, x y
		unary functions	(...)2, (...), -(...)

terminal set:

design variables

x1 , x2

The output of the algorithm still needs some manual post-processing in order to get rid of those terms in the expression that give a null or tiny contribution, for example when the same value is added and subtracted. It is then suggested to run the problem several times in order to identify, by comparison, the most likely components.

The optimization problem is reduced to the approximated one shown in Table 2.

		Conclusion

It is proposed to use the genetic programming methodology for the creation of approximation functions in the multipoint approximation method. It has been successfully applied to build high quality mid-range and global approximations for test problems, showing potential for complex structural optimization and identification problems.

		Acknowledgement

This research is supported by the Training and Mobility of Researchers (TMR) programme of the European Commission, contract ERBFMBICT961615. Also, authors would like to express their appreciation of support provided by Delft University of Technology, The Netherlands.

The authors thank Dr. Fred van Keulen of Delft University of Technology for many useful discussions.

		References