Example of applying GP in design domain


Task:  Design a beam (2D) for a given span that under a given load has minimum weight.
Assumption:  We just want a 2D shape of the beam so assume a uniform thickness of material.

Representation of shape

  We use a "shape making" instruction.  An example of this is a scripting language of CAD software such as AutoCad.  We can think of a "solution" as a program (or script) to draw the shape of the beam.  Because the span (length) of the beam is given, the other dimension is the geometrical shape, such as, rectangular, triangular, curve. Beside a primitive shape, we can compose them to create a complex shape.  The composition is "union". To reduce the weight we use "cut-out".  The cut-out is a circular shape with varying size.  The shape making script creates a symmetric shape, mirroring on middle vertical axis.  The "script" will be two parts:  the first part is shape creation, the second part is shape modification.
  (beam shape modify)

  This notation represents a tree:

   beam
  /   \
 /     \
shape  modify

For shape creation, the operator is "union" and the terminal is the parameterised shape:
  rectangular(height,width,x,y)
  triangular(height,width,x,y)
  curve(type,x,y)

where x,y is the offset from the origin of the reference frame. (I have not specify what curve type will it be).

For shape modification, the operator is "do" that takes two cut-out operations.  The "cut-out" is circular shape with parameters.
  cut(radius,x,y)

Example

   Here is an example of the "script":

   (beam (union rec(..) trian(...))  (do cut(..) (do cut(..) cut(..)) )

Genetic Programming Steps

1)  Initialise a population of beams.  Create random "beam"
2)  Evaluate the fitness, run the script of each beam, a shape will be created, measure the ability to withstand the given load (using finite element?), then calculate its weight (counting 2D area).
3)  Perform genetic operations: reproduction, recombination, mutation
4)  repeat until satisfy

Genetic operation

The genetic operation must be designed to work with this representation. The recombination must exchange shape with shape and modification with modification.  For parameters, the easiest way is to use "nominal values". They are "prefabricated" constants with symbolic names such as k1, k2 ...
Once a good beam has been evolved we can use Genetic Algorithm to further "tuned" these parameters.  

We can also use "subroutine" as shape modification.  A subroutine is a tree that has a name and can be used as an operator in the shape modification script.  The recombination operator must be aware of these subroutines and "rename" them as necessary when different subroutines are used in one individual.

8 Dec 2010