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