APPLICATION OF GENETIC PROGRAMMING TO THE CHOICE OF STRUCTURE OF MULTIPOINT APPROXIMATIONS

Vassili V. Toropov, Luis F. Alvarez

Department of Civil and Environmental Engineering
University of Bradford, Bradford, West Yorkshire, BD7 1DP, UK

E-mail: V.V.Toropov@bradford.ac.uk , L.F.Alvarez@bradford.ac.uk
URL: http://www.brad.ac.uk/staff/vtoropov



1. 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], [7]. The choice of the structure of approximation functions is the subject of this study.

Response surface methodology [6] is a method of constructing approximations of the system behaviour using results of the response analysis calculated at a series of points in the design variable space. A mid-range variant of this approach, called the multipoint approximation method (MAM) [8-11] 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.


2. GENETIC PROGRAMMING

Genetic Programming [3] is a branch of Genetic Algorithms (GA). Their basis is the same Darwinian concept of survival of the fittest. The innovation of GPs is the use of more complex structures. While GAs use a string of numbers to represent a solution, the GP creates computer programs with a tree structure as 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 initial population is a blind random search of the space defined by the problem.

In our case of design optimization, the program, created by a GP, represents an empirical model to be used for approximation of response functions in the original optimization problem. The programs are composed of elements from a terminal set and a functional set, called nodes. The terminal set consists of N design variables x1 , x2 , ..., xN . The functional set contains the mathematical operators that will be used to generate the regression model, e.g. {+, *, /, power, square, square root, negation, ...}.


2.1. Fitness Function

In problems of empirical model building, the fitness function shall quantify the difference between the response predicted by the original (complex) model and the approximate (simplified) model. A simple choice of the fitness function, which is used in this work, is the sum of squares of the difference between the simplified model output and the results of runs of the original model over some chosen plan (design) of experiments:


(1)

where, for a given tree, is the simplified function value corresponding to the k-th point of the plan of the experiments, is the original function value at the same point and C is a large constant.


2.2. Genetic Operators

Model structures evolve through the action of three basic genetic operators: reproduction, crossover and mutation.

Crossover and mutation provide diversity of the population. Crossover (figure 2) combines good information from two trees (parents) while mutation protects the model against premature convergence and improves the non-local properties of the search (figure 3). In the reproduction stage, a strategy must be adopted as to which programs should die. In this simple implementation, trees with fitness below the average are killed. The population is then filled with the surviving trees according to fitness proportionate selection. Finally, a relatively small number of the fittest programs, called the elite, is selected to be transferred unchanged to a next generation. 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. Figure 4 shows a flowchart of the process.

Figure 2. Crossover


Figure 3. Mutation


Figure 4. Flowchart of Genetic Programming


3. IMPLEMENTATION

The algorithm has been implemented in C++ following a sample program presented in [4].

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.


3.1. Design of Experiments

In this paper, the approach suggested by Audze and Eglais [1] and used later by Rikards [5] 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 plan of experiment is characterized by a matrix which contains the levels of factors for each of K experiments. For example, for a number of factors (design variables) N = 2 and K = 10, the matrix is


The corresponding plan of experiments is shown in Fig. 5.

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


3.2. 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:

(2)

The allocation of tuning parameters a to an individual tree follows basic algebraic rules. To identify the parameters of the expression by the nonlinear least squares fitting, i.e. to solve the optimization problem (2), a combination of a random search technique and a nonlinear optimization method based on the minimization of the I2 norm of a vector function (least squares) is used.


5. 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 both with and without the addition of numerical noise showing potential for complex structural optimization and identification problems.


REFERENCES

1. Audze, P. and Eglais, V. New approach to planning out of experiments. Problems of Dynamics and Strength, v. 35, 104-107, 1977, Zinatne, Riga (in Russian).
2. Barthelemy, J.-F.M. and Haftka, R.T. Approximation concepts for optimum structural design - a review. Structural Optimization, 5, 129-144, 1993
3. Koza, J.R. Genetic Programming: On the programming of computers by means of natural selection. MIT Press, 1992
4. Kuhlmann, H. and Hollick, M. Genetic programming in C/C++. CSE99/CIS899. Final Report, May 1995
5. Rikards, R. Elaboration of optimal design models for objects from data of experiments. In: Optimal design with advanced materials, The Frithiof Niordson volume. Proceedings of the IUTAM Symposium, Lyngby, Denmark, 18-20 August 1992. Pedersen, P. (ed.), pp. 113-130, Elsevier, 1993
6. Roux, W.J.; Stander, N. and Haftka, R.T. Response surface approximations for structural optimization, Proc. 6th AIAA/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, Bellevue WA, September 4-6 1996, Part 2, pp. 565-578, AIAA, 1996
7. Sobieszanski-Sobieski, J. and Haftka, RT. Multidisciplinary aerospace design optimization: Survey of recent developments. Structural Optimization, v. 14, pp. 1-23, 1997
8. Toropov, V.V. Simulation approach to structural optimization, Structural Optimization, v. 1, 37-46, 1989
9. Toropov, V.V.; Filatov, A.A.; Polynkin, A.A. Multiparameter structural optimization using FEM and multipoint explicit approximations. Structural Optimization, vol. 6, 7-14, 1993
10. Toropov, V.V.; van Keulen, F.; Markine, V.L.; de Boer, H. Refinements in the multi-point approximation method to reduce the effects of noisy responses. 6th AIAA/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, Bellevue WA, September 4-6 1996, Part 2, pp. 941-951, AIAA, 1996
11. van Keulen, F. and Toropov, V.V. New developments in structural optimization using adaptive mesh refinement and multi-point approximations, Engineering Optimization, v. 29, 217-234, 1997