RESEARCH AND DEVELOPMENT
ERCIM News No.33 - April 1998

Geometric Optimization with Genetic Algorithms

by Gábor Renner

Genetic algorithms are used to solve different technical problems (eg in process planning). At SZTAKI, research has started to investigate the application of genetic algorithms in a new field of geometric design. Various techniques and algorithms have been developed to optimize the shape of complicated objects with free-form curves and surfaces. It turned out that much more complex goal functions and constraints can be handled in this way with realistic effort than is possible with the usual analytic or numeric methods.

The design of a part or an assembly for optimal operation is an important issue both from technical and economic point of view. In many cases optimal operation can be achieved by defining optimal shapes and optimal geometrical dimensions. While the function to be optimized can usually be described by simple geometric notions, performing the optimization can be algorithmically and computationally complicated. This is due to the fact that physically or technically relevant optimal conditions can be described by nonlinear functions of the geometric parameters with many local extrema (eg minimum) points. This is the case eg in the design of high quality surfaces where the integral of the curvatures should be minimal, or the distribution of high light curves should be optimal. By using numeric methods a local minimum - which strongly depends on the starting point ­ can be discovered. The solution of the real optimization problem, however, would be the global minimum.

As a consequence of the above problems, CAD/CAM systems available on the market practically do not provide tools for geometric optimization. In most cases the only possibility is to run a trial and error process, ie the value of the goal function for the actual shape is evaluated, and if not satisfactory, a new object with somewhat changed geometrical parameters is computed.

For certain types of complicated geometric optimization problems genetic algorithms offer a reasonable solution. They do not strive to achieve an exact solution, but rather handle a set of potential solutions. Goodness or fitness relevant to the given problem is defined and improved during the process.

The basic concept of genetic algorithms comes from Nature. Instead of searching for a single optimal solution of the optimization problem, a population of candidate solutions is maintained. Individuals in the population have a genetic code (chromosomes) which represents their inheritable properties. New individuals are created from one or two parents, reminiscent of the asexual or sexual reproduction of living organs. While in asexual reproduction only random changes occur in the genetic code of the individuals (mutation), in sexual reproduction the crossover of genes mixes the genetic code (and also the properties of the parents). A fitness measure is defined which reflects the correspondence of an individual to the optimization goal. The population evolves so that it contains more and more fit individuals if the following main assumptions hold:

The genetic process starts with an initial population of individuals (usually generated randomly). New individuals are generated by crossover and mutation and their fitness is evaluated. They are merged into the population which is cut back to its original size by discarding the less fit individuals. The above process runs until an acceptable solution is found, or the diversity of the population decreases so much that there is no hope for further improvement.

We have applied genetic algorithms for shape design and optimization. Individuals are curves or surfaces and the genetic code is the parameter tuple of the curve or surface in a specific representation (eg Bezier or B-spline). Different types of crossover operations (one-point, two-point, cyclic, merging crossover) are applied for creating new elements of the set of curves or surfaces. The fitness is usually determined by two factors: the value of the goal function to be minimized (optimum criteria), and the penalty for violating some geometric constraints.

We have developed several types of genetic algorithms for solving certain problems in free form curve and surface design and shape optimization. According to our experience they have proved to be useful for solving many large scale and sophisticated problems. Investigations and computer experiments are in progress to solve technical problems, such as the design of cams or car-body-, reflector- and turbine blade surfaces.

Please contact:

Gábor Renner - SZTAKI
Tel: +36 1 1868 782
E-mail: renner@sztaki.hu

return to the contents page