Shape Representations and Evolution Schemes

Marc Schoenauer

TL;DR

This paper explores how different ways of representing shapes in evolutionary computation (EC) impact the design of optimal structures. The authors introduce and compare novel "Voronoi" and "H-representations" against the traditional bit-array method, demonstrating that these new approaches significantly outperform the older one, especially for complex 2D and 3D design problems.

What Problem Does This Paper Address?

The core challenge this paper tackles is finding the optimal shape for a structure that minimizes weight while meeting specific mechanical requirements, a field known as Topological Optimum Design (TOD). Traditional methods for TOD, like the homogenization method, are powerful but limited to linear elasticity and struggle with complex loading scenarios. Evolutionary Computation (EC) offers a more flexible approach, but its effectiveness is heavily dependent on how the "genotype" (the representation of the shape) maps to the "phenotype" (the actual shape and its mechanical properties). The paper highlights that the standard bit-array representation, while simple, becomes computationally prohibitive and scales poorly as the complexity of the mechanical model or the desired accuracy increases, especially for 3D shapes. This limitation hinders the ability of EC to tackle more realistic and challenging TOD problems.

Methods

The paper introduces two novel representations for shapes:

  • Voronoi Representation: This method uses a variable-length list of "Voronoi sites" (points) to define a shape. The design domain is partitioned into Voronoi cells, and each cell's label (0 or 1) determines if it's material or void. This representation is independent of any mesh used for mechanical analysis, allowing for a dissociation between shape representation and fitness evaluation.
  • H-Representation: This approach starts with the design domain as entirely material and then defines "holes" (elementary shapes like rectangles) to remove material. Similar to the Voronoi representation, it's variable-length and mesh-independent.

These new representations are compared against the traditional Bit-array Representation, where the design domain is discretized into a fixed grid of elements, each assigned a binary value. The paper also discusses the impact of "epistasis" (how genes interact) and "symmetry" (how the representation relates to the optimal solution) of these representations on evolutionary algorithms. The authors employ standard evolutionary schemes like Genetic Algorithms (GA) and Evolutionary Strategies (ES) to evaluate these representations on a benchmark TOD problem (a cantilever plate).

Datasets

The paper uses a benchmark problem: the 2x1 cantilever plate. This is a standard test case in topological optimization, where a plate is fixed on one side and subjected to forces on the other. The authors do not introduce new datasets but rather use this established benchmark to evaluate their proposed representations. The "dataset" in this context refers to the various configurations of this benchmark problem, including different displacement limits (strong vs. weak constraints) and penalty parameters for the fitness function.

Key Insights and Ideas

  • Representation is King (for EC in TOD): The paper strongly emphasizes that the choice of representation is a critical factor in the success of evolutionary algorithms for complex problems like TOD. A poor representation can severely limit performance, even with sophisticated evolutionary operators.
  • Mesh Independence is Crucial: The Voronoi and H-representations decouple the shape representation from the mesh used for mechanical analysis. This is a significant advantage, as it allows for higher accuracy in fitness evaluation without proportionally increasing the complexity of the genotype.
  • Epistasis Matters: The degree of epistasis in a representation influences how effectively evolutionary operators can explore the search space. The paper suggests that high epistasis, as seen in the Voronoi representation, can sometimes be detrimental, while the H-representation strikes a better balance.
  • Symmetry Can Be a Double-Edged Sword: The alignment of the representation's symmetry with that of the optimal solution can impact convergence speed.
  • GA vs. ES Nuances: The paper observes that GAs tend to outperform ES under strong constraints, possibly because ES's elitism can lead it to get stuck in local optima.

Key Results

  • Voronoi and H-representations Outperform Bit-array: Both the Voronoi and H-representations consistently and significantly outperformed the traditional bit-array representation in terms of both computational cost and the quality of the obtained solutions.
  • H-representation is Generally Superior: The "Hole" representation demonstrated slightly better performance than the "Plate" representation in most cases, suggesting a favorable balance of epistasis and symmetry for this specific problem.
  • GA Advantage in Strong Constraints: Genetic Algorithms showed a notable advantage over Evolutionary Strategies when dealing with strong displacement constraints, a tendency that diminished with weaker constraints.
  • No Absolute Conclusions: The authors acknowledge that due to the multitude of interacting parameters (representation, evolutionary scheme, problem instance), it's difficult to draw absolute conclusions.

Limitations and Future Work

  • Complexity of TOD as a Testbed: The authors admit that the TOD problem, with its many interacting parameters, is too complex to serve as an ideal testbed for evaluating shape representations.
  • Need for Simpler, Tunable Testbeds: They suggest the need for simpler, unconstrained problems with tunable difficulty and known solutions to better isolate the impact of representation.
  • Exploring Other Representations: Future work could investigate representations based on splines (common in CAD), L-systems (for plant-like structures), and fractal theory (Iterated Function Systems).
  • Fitness Variance and Distance Correlation: The paper points to theoretical frameworks like fitness variance and fitness distance correlation as valuable tools for guiding future systematic experiments and understanding problem difficulty.
  • Further Investigation of Epistasis and Symmetry: More in-depth studies are needed to fully understand the interplay between epistasis, symmetry, and evolutionary operators.

Summary updated

Abstract

The choice of a representation i.e. the definition of the search space, is of vital importance in all Evolutionary Optimization processes. In the context of Topological Optimum Design in Structural Mechanics, this paper investigates possible representations for evolutionary shape design.
BibTeX
@inproceedings{schoenauer1996shape,
  author = {Marc Schoenauer},
  title = {{Shape Representations and Evolution Schemes}},
  booktitle = {Evolutionary Programming},
  year = {1996},
}

Loading related content...

Figure