Transcript Mixed Integer Problems - the Systems Realization Laboratory

Mixed Integer Problems
•
Most optimization algorithms deal with continuous variables.
•
Branch and Bound and Cutting Plane algorithms are well known
algorithms able to cope with integers.
•
An optimization problem which involves both integers and continuous
variables is called a mixed integer problem.
•
The selection of a material for a pressure vessel out of a set of
discrete choices, coupled with a pressure vessel optimization as you
just did, is a mixed integer problem.
•
Integers can be converted to booleans. This provides some nice
properties which can be exploited, but typically, more variables are
needed to characterize the same integer problem.
Optimization in Engineering Design
Georgia Institute of Technology
Systems Realization Laboratory
Combinatorial Optimization
•
•
•
•
•
•
Combinatorial problems are typically not well handled by cutting plane
and branch and bound.
Examples of combinatorial problems include scheduling and
assignment problems.
For combinatorial problems, often non-classical optimization
approaches are used.
Often heuristics (rules of thumb) are used to limit the choices. In
Operations Research, you may find the term heuristic programming
occasionally.
Knowledge based systems are a well known example of coding
heuristics and some people have connected knowledge bases to
optimization algorithms.
Another approach is based on randomness and probability.
Optimization in Engineering Design
Georgia Institute of Technology
Systems Realization Laboratory
Monte Carlo Methods
•
Monte Carlo methods employ random number generation as part of
the iterative search for the solution of a (combinatorial) optimization
problem.
•
"Classical" Monte Carlo methods are nothing more than codes which
randomly generate solutions and keep track of the best.
•
However, statistical properties can be used to determine whether and
how long it will take the method to find the solution to the given
problem.
•
More "enhanced" methods of growing importance are:
• simulated annealing
• genetic algorithms
Optimization in Engineering Design
Georgia Institute of Technology
Systems Realization Laboratory
Simulated Annealing
•
Basic idea is rooted in thermo-dynamics and the cooling (or annealing)
of a liquid to a crystalline solid state:
• If the liquid (e.g., molten steel) is cooled slowly and allowed to spend
a long time near the freezing temperature, a perfect crystal will form
which has the lowest state of energy.
• If the liquid is not allowed to spend a long time reaching an
equilibrium near its freezing point and/or it is cooled too quickly, then
the material will form a crystal with many defects and a higher internal
energy state (think of quenching of steel; the material may crack).
•
Metropolis applied the same idea to simulate atoms in an equilibrium.
•
The "Metropolis Algorithm" has also been applied to solving
combinatorial optimization problems.
Georgia Institute of Technology
Optimization in Engineering Design
Systems Realization Laboratory
Simulated Annealing – Metropolis Algorithm
•
At each iteration, an “atom” is randomly displaced a small amount.
•
The energy is calculated for each atom and the difference with the energy at its
original location is calculated.
–DE
(
)
kT is
•
The Boltzmann probability factor P = e
calculated where
k = Boltzmann constant,
T = temperature, and
DE = the energy difference between the two atom states.
•
If DE  0 then the new location is accepted.
•
Otherwise, a random number is generated between 0 and 1:
• If the random number is greater than the calculated P, then the higher energy state
is accepted in the hope that the new location may eventually lead to a better
location than the original location.
• Otherwise, the old atomic location is retained and the algorithm generates a new
location.
Optimization in Engineering Design
Georgia Institute of Technology
Systems Realization Laboratory
Simulated Annealing for Combinatorial Optimization
How to convert metropolis algorithm to general combinatorial
optimization algorithm?
• Rather than positioning atoms, one can also position cities in a traveling
schedule (traveling salesman problem), materials in a product, etc.
• Use an objective (or fitness) function instead of energy function.
• Have the temperature T start at a high value so "atoms" (cities, material
choices) can bounce around in the solution space. This causes solutions
to jump out of local valleys.
• As the optimization proceeds, the temperature is lowered and less
solutions with high energy states (or objective functions) are allowed to
remain.
•
Hopefully, this slow freezing gives you the best solution.
Typical problem areas:
Choice of T, solution generation (random or controlled).
Optimization in Engineering Design
Georgia Institute of Technology
Systems Realization Laboratory
Genetic Algorithms (GAs)
•
Originally developed by John Holland.
•
Genetic algorithms are search algorithms based on the
mechanics of natural selection and natural genetics subject to
survival of the fittest among string structures.
•
Genetic algorithms use strings of characters to represent solutions.
These strings are called chromosomes.
•
Each element (character) in such a string is a gene representing a
certain choice of gene (e.g., gene 2 in a chromosome of 5 genes
could represent the material choice for component 2).
•
Most genetic algorithms use binary values for genes.
•
However, integer GAs also exist, and (thus) a gene can also contain
Georgia Institute of Technology
a real value. (HOW?)
Optimization in Engineering Design
Systems Realization Laboratory
Genetic Algorithm Flowchart
Randomly generate a population
of potential solutions
Evaluate
fitness
of
population members
Select
two
parents
from
population based on fitness
Multiple
repeats
in one
iteration
Crossover and
mutation
Produce two children
Evaluate children
no
Optimization in Engineering Design
Is solution "Good"?
yes
Output best solution
found
Georgia Institute of Technology
Systems Realization Laboratory
Parent Selection
Several methods for selecting parents exist. Most common are:
•
Rank ordered selection: A prescribed number of parents is taken for
mating from the top of a rank-ordered list according to fitness function
value.
•
Roulette wheel selection: The sum of the fitness of all members is
calculated and the fitness of each member is normalized to a
percentage of this sum. All members are put on a roulette wheel which
is spun several times to select members on the wheel for mating. The
larger the fitness, the larger the space on the wheel for the member, the
larger the chance of being chosen for mating.
•
Boltzmann distribution: Based on simulated annealing. Instead of
calculating a DE, the difference in fitness values 2 - 1 is calculated. If
a1 is selected as a parent, then a2 is chosen if 2  1. Else, a random
number is generated between 0 and 1, and if the Boltzmann probability
for the differences in fitness is less than this number, then a2 is
accepted as a parent.
Choice of a1: can be the fittest member, or chosen at random, or ...
Optimization in Engineering Design
Georgia Institute of Technology
Systems Realization Laboratory
Mating, Crossover, and Mutation
After parents have been choosen, they mate to produce two children. This
is done by crossing (mixing) the genes of one parent with the genes of
another parent and create two new combinations.
Crossover is used to promote the mixing of good genes within a
population. Methods for crossover:
• One point crossover: a point is determined in the chromosomes of the
parents and the genes on each side of that point are recombined into two
new combinations (children).
• Multipoint crossover: Multiple points are determined for recombining
chromosome substrings.
• Uniform crossover: A flip of a coing determines whether a gene value
of, say, parent 1 is given to child 1 or 2.
Mutation is the random change of one or more of the gene values and
generally occurs with a very small probability. Mutation is used to
promote genetic variations. Various schemes exist.
Optimization in Engineering Design
Georgia Institute of Technology
Systems Realization Laboratory
Some Remarks on Genetic Algorithms
•
•
•
Genetic algorithms (and simulated annealing) are gaining ground as
practical tools.
They are relatively simple and elegant because of their analogy with
Nature.
Public domain and commercial codes exist.
However:
• They have a number of control parameters which affect the efficiency
of solution.
• They typically perform a large number of fitness function evaluations
(although less than an exhaustive search) and this may be
unacceptable.
• They are unconstrained minimization algorithms, thus a penalty
function or a lexicographic approach is required for constrained
minimization problems.
• For a mixed integer problem, you may consider a hybrid GA which
includes a regular optimization algorithm for the real variables.
Optimization in Engineering Design
Georgia Institute of Technology
Systems Realization Laboratory