E. O. Tuck and L. Lazauskas

3. PREDICTION OF OPTIMAL PARAMETERS

Once we have a theory that gives reasonable predictions of the total resistance, it seems natural to search for "sensible" parameter configurations minimising that resistance. Many engineering design problems can be cast into the form of optimisation problems. For example the problem addressed in this paper can be formulated as
Minimise the real-valued function f(x₁,x₂,...,x_n), with each real parameter x_i subject to (domain) constraints a_i<=x_i<=b_i for some real constants a_i and b_i

Many techniques exist for solving optimisation problems such as the one described above, however, they vary greatly in efficiency and the quality of the final solution for a given number of function evaluations. No single technique is best for all design problems. Gradient-based methods work well with smooth, unimodal functions, but may yield local optima for multimodal functions. Heuristic algorithms can increase search efficiency, but at the expense of guaranteed optimality - they do not always find the global optimum.

3.1 Genetic Algorithms (GAs)

GAs are adaptive search methods that use heuristics inspired by natural population dynamics and the evolution of life. They differ from other search and optimisation schemes in four main respects (Dhingra and Lee 1994):

Search proceeds from a population of points, not from a single point.
They use a coding of the parameters, not the parameters themselves.
Objective function values guide the search process. They do not use gradients or other problem-specific information.
State transition rules are probabilistic, not deterministic.

In the present study, we use a non-traditional GA similar to Eshelman's (1991) CHC, augmented with, among other features, hill-climbing routines, cataclysmic restarts and incest prevention. The resulting computer program, called "GODZILLA" for Genetic Optimisation and Design of Zoomorphs, is described in Lazauskas (1996 in prep.).

3.2 GODZILLA

GODZILLA's general operation can be described quite succintly: create and evaluate new (candidate) designs until some termination criterion is met. Termination can occur when a certain number of designs have been evaluated, or after a prescribed amount of time has elapsed, or when the algorithm seems to be making no further progress.

GODZILLA begins the optimisation process by creating an initial population of (real-valued) design vectors and calculating the total resistance for each design. Initial designs are randomly generated, although the population can also be "seeded" with previously found good designs.

Genetic operators and hill-climbing operators are used to create candidate designs. Genetic operators create new (offspring) vectors from two parent vectors in the population, using heuristics inspired by the recombination of DNA. There are too many varieties to here discuss individual strengths, deficiencies and peculiarities. GODZILLA's primary genetic operator is one gleaned from fuzzy set theory described in Voigt et al (1995). After evaluating the total resistance of the offspring, GODZILLA replaces the worst individual in the population with the offspring if the offspring's total resistance is lower. This replacement strategy guarantees that the best individual in the population is never replaced by an inferior individual.

The method used to select parent vectors from the population can have a substantial influence on the performance of GAs. GODZILLA uses binary tournament selection. In this method, two individuals are selected without replacement from the population. The individual with the lower total resistance becomes the first parent. A second binary tournament determines the other parent.

One form of hill-climbing operator used by GODZILLA, Stochastic Bit-climbing, creates a candidate vector by adding or subtracting small increments from each of the parameters of the best design vector found so far. This allows the program to explore more closely promising regions of the search space found by the genetic operators. GODZILLA also incorporates another hill-climbing technique called the Simplex Search Method. This method, which is not to be confused with the Simplex Method of linear programming, is described in Reklaitis et al (1983).

The field of evolutionary computation is expanding very quickly, and almost all communication occurs via the electronic Internet. The USENET group, comp.ai.genetic, is a very useful and important resource.

Back to Title Page
Previous Section
Next Section