Transcript Hamiltonian Cycles on Symmetrical Graphs

CS 285
MEMS Design using
Genetic Algorithms
Carlo H. Séquin
EECS Computer Science Division
University of California, Berkeley
Genetic Algorithms

Pursue several design variations in parallel
(many phenotypes in each generation)

Evaluate their “fitness”
(how well they meet the various design
objectives  Pareto set)

Use best designs to “breed” new off-springs
(by modifying / combining their genes)

Expectation: Good traits will stick around,
bad solution will be weeded out ...
The “genome” is the ultimate
parameterization of a design,
given the proper procedure
to interpret that code
 Without
the proper framework,
the genome is meaningless.
(e.g., human DNA on a planet
in the Alpha-Centauri System)
An Experiment
Let ME students design a MEMS resonator

Students (initially) had no IC experience

Good programmers
 Excited
about Genetic Algorithms
Micro-Electromechanical Systems
MEMS
 Created
with a somewhat
enhanced fabrication
technology used for
integrated circuits.
 Many
nifty devices and
systems have been built:
motors, steerable mirrors,
accelerometers, chemo
sensors ...
The Design of a MEMS Resonator

Filters
 Accelerometers

Gyroscopes
Prevent horizontal
oscillations !
Resonate vertically
at desired frequency
Basic MEMS Elements
Beam
Anchor to substrate
H-shaped center mass
Comb drive
A General Set-Up for Optimization
 Poly-line
suspensions at 4 corners.
 Adjust
resonant frequency F

Get Kx Ky into OK ranges

Minimize layout area
Need an Electro-Mechanical Simulator !
“SUGAR”
“SPICE for the MEMS World”
(open source just like SPICE)
DESIGN
Fast,
Simple,
Capable.
MEASUREMENT
SIMULATION
A Possible Phenotype

Adjust resonant frequency to 10.0 ± 0.5 kHz

Bring Kx / Ky into acceptable range ( >10 )

Minimize size of bounding box; core fixed
MEMS Actually Built and Measured
Genetic Algorithm in Action !
 Area
= 0.181 mm2; Kx/Ky = 12
Use 4-Fold Symmetry !
 1st-order
compensation of fabrication variations
Using 4-fold Symmetry
 Faster
search ! Area = 0.171 mm2; Kx/Ky = 12
X,Y-Symmetry; Axis-Aligned Beams
 Area
= 0.211 mm2; Kx/Ky = 118
Introduce Serpentine Element
Wv
Wh
Lh

Lv
N=3
A higher-order composite subsystem
with only five parameters: N , Lh, Wh, Lv, Wv
Proper Use of Serpentine Sub-Design
 That
is what we had in mind ...
Proper Use of Serpentine Element
Reduce

Area =X-dimension
0.143 mm2;
of
Kxlayout
/Ky = 11
by introducing more serpentine loops
Trying to Reduce Area
soft Kx
 Area
= 0.131 mm2;
flare out
Kx/Ky = 4 !!
Increasing Stiffness Kx

Connecting bars suppress horizontal oscillations

But branched suspensions may not be expressible
in genome ( = underlying data structure ).
Using Cross-Linked Serpentines
 Area
= 0.126 mm2; Kx/Ky = 36
Why Does the G.A. Not Find This ?
 Lack
of expressibility of genome.
 Solution
space too large, too rugged ...
 Sampling
 Samples
is too sparse !
are not driven to local optima.
“Holey” Fitness Space

Open-ended engineering problems have complicated,
higher-dimensional solution / fitness spaces.
A Rugged Solution Space
 No
phenotype is on the top of a peak
 Good
intermediate solutions may get lost
20. 1.
Generation
Generation
– drifting
– a random
higher
sampling
ground
50. Generation
– clustered
neartohigh
mountains
What really happened here ?

Major improvement steps came by
engineering insights.

Genetic algorithm found good solutions
for the newly introduced configurations.

With few enough parameters & clear objectives,
greedy optimization may be more efficient.

With complex multiple objectives,
G.A. may have advantage of parallel exploration.
What Are Genetic Algorithms Good For ?

Exploring unknown territory

Generating a first set of ideas

Showing different subsystem solutions
How can this be harnessed most effectively
in an engineering design environment ?
Uncharted Territory
 Task:
 How
Design a robot that climbs trees !
do you get started ??
Making G.A. Useful for Engineering
Selection of
good starting
phenotypes
Visualization
G.A.
Selective
breeding

Suggestive
editing
Greedy
Optimization
G.A. by itself is not a good engineering tool
OPASYN
A Compiler for CMOS Operational Amplifiers
H.Y. Koh, C.H. Séquin, P.R. Gray, 1990
Synthesizing on-chip operational amplifiers
to given specifications and IC layout areas.
1. Case-based reasoning (heuristic pruning)
selects from 5 proven circuit topologies.
2. Parametric circuit optimization to meet specs.
3. IC Layout generation based on macro cells.
MOS Operational Amplifier (1 of 5)
Only five crucial design parameters !
Op-Amp Design (OPASYN, 1990)
Multiple Objectives:

power dissipation (mW)

output voltage swing (V)

output slew rate (V/nsec)

open loop gain ()

settling time (nsec)

unity gain bandwidth (MHz)

1/f-noise (V*Hz-½)

total layout area (mm2)
“Cost” of Design
= weighted sum
of deviations
OPASYN Search Method
Fitness
Hard design constraints
Design-parameter
spaceascent
Regular sampling
followed by gradient
Cost
MOS Op-Amp Layout
 Following
circuit synthesis & optimization,
other heuristic optimization procedures produce
layout with desired aspect ratio.
Synthesis in Established Fields

Filter design and MOS Op-Amp synthesis
have well-established engineering practices.

Efficiently parameterized designs as wellas
robust and efficient design procedures exist.

Experience is captured in special-purpose
programs and used for automated synthesis.

But what if we need to design something
in “uncharted engineering territory” ?