MDO, MOO, Metaheuristics, and Surrogate Modeling Flashcards
What does Methaheuristics mean?
Metaheuristic is characterized as something known, a rule of thumb, or strategy that governs/guides other heuristics to produce solutions beyond those normally generated in quest for local optimality.
What type of data does metaheuristics best apply to?
Multimodal system, discrete variables.
What type of algorithm is metaheuristic (stochastic or deterministic)?
Stochastic - involves selection of random values within design variables enabling access to global optimization.
What are the main types of metaheuristic optimization algorithms?
Simulated Annealing, Genetic Algorithms, Particle Swarm
What is simulated annealing?
A metaheuristic algorithm which is based on the concept of the Boltzman probability distribution form to model change in equilibrium states for given local “temperature” or population size and rate of decreasing state variables.
What is the primary concept of the metropolis criterion?
The concept that when your next state is not a direct reduction it will have a probability of being an acceptable equilibrium point relating to the Boltzman probability distribution.
What is particle swarm optimization?
The algorithm developed to model behavioral swarming based on the concepts of separation, alignment, cohesion in agent based systems. Where the optimization occurs based on finding a particle’s position w.r.t your objective function, and measuring performance over swarm while recording motion information. The concept of inertia and weighted particle attraction to optimization your solution within a neighborhood of points.
What are the three main behavioral trends you see in Particle Swarming functions?
Convergent, Harmonic oscillatory, zigzagging
What are Genetic Algorithms?
A metaheuristic optimization algorithm which is based on the theory that natural selection and survivalist methods evolve the fittest individuals/populations. Application to designs, it represents the selection of individuals for reproduction through probabilistic and stochastic methods to develop a new generation of designs which best meet the criteria of fitness.
What is the general GA algorithm process?
Initialization, selection, crossover-mutation (reproduction), fitness evaluation, replacement
How do you initialize a GA?
Choose an initial population of individuals (of single design variables) by representing all design variables and ranges in binary code within the design space, and randomly sample bits of each chromosome to generate individuals for the population.
What are the methods of GA selection?
Proportional and Tournament:
Proportional selection states that an individuals likelyhood of being selection is proportional to its fitness (Roulette Wheel - pie pieces proportional to fitness w.r.t. objective goals)
Tournament selection
What are the benefits & disavantages of proportional selection in GA?
Gives each candidate a fair change of becoming parent
- Population evolves through gene pool domination if large difference between individuals (no exploration, yes exploitation on fit designs)
- Population evolves to be nearly optimal if small differences between individuals (no exploitation)
What are the benefits & disavantages of Tournament selection in GA?
Overcomes issues of proportional selection by inducing tournamental evolution with probabilistic & random selection for fitness comparisons.
Issues/benefits of Elitism, copying best individuals from one generation to subsequent generations
What is the crossover phase of a GA?
The recombination of two parent individuals into two children in search of global searches in design space through random selection & probability of reproduction.
What happens if no crossover occurs?
Both parents become next children in algorithm.
What are the main types of crossover? Explain general premise
one-point, two-point, uniform:
Premise is given two parents with binary chromosome length ‘L’, point delegates the dividing lines for swapping relevant bits between the parents into new children. (2 point, dividing line and # bits, uniform is probability swap or no swap)
What is the mutation phase of a GA?
Mutation is a form of flipping random bits within children chromosomes to maintain genetic diversity, accounting for some alleles/designs that have been eliminated in gene pool
What is the replacement phase of a GA?
The phase which indicates the proportion of the children which will replace the parents in the next generation of the population formation.
-Random, all children become parents, only best individuals become offspring (elitism)
How do you discretize a continuous variable for binary representation?
- Determine # bits required for spread of data
- Convert base-10 number to base-2.
Range - Upper, lower bound differential
Resolution - discretized step size
N >= ln(Range/Resolution+1)/ln(2)
What is the hamming distance?
A measure of how many bits must be flipped to move between an adjacent designs.
What is a hamming cliff?
Refers to a situation where more than one bit must be flipped to to move from one design to its immediate “neighbor”
What is gray code?
Binary representation in which the hamming distance between two neighboring designs is always 1
What are Multi-Attribute problems?
Problems where there is more than one objective, have multiple attributes that have their individual levels of optimality
What is the difference between single-objective optimization and multi-objective optimization?
Single-Objective problems have a “best” solution, where a Multi-Objective optimization problem return a set of solutions representing relative optimality between competing attributes
What is a-priori multi-objective optimization?
A multi-attribute problem which can be aggregated with a-priori information to build a specified utility function/single-objective function as your objective
What is a-posteriori multi-objective optimization? (MOO)
An optimization problem which generates a set of solutions representing relative optimality between the competing attributes.
What is total ordering?
Total ordering is used by single-objective optimization to determine preferred feasible design based on requirements met
What is partial ordering
Partial ordering is a multi-objective optimization based method to relate comparable elements (designs), where some are incomparable.
What is the goal of multi-objective-optimization?
To find a set of designs that are better than all designs to which they can be compared, but are incomparable to each other.
What practice is used to solve the partial ordering MOO goal?
Pareto Dominance
What are weakly and strongly dominating points in MOO?
In pareto dominance:
- weakly dominating points are better in some attributes and equal in others
- strongly dominating points are better in all attributes
What is an incomparable point in pareto dominance?
If a point is better in some attributes and worse in others than another point, those two points are incomparable. (neither dominates the other)
What is non-dominated/pareto optimal/pareto efficient?
Same thing, non-dominated means a point in the feasible objective space that is not dominated by any other point.
The subset that consists of all non-dominated points in a give set.
Pareto Frontier
What properties doe the points on a Pareto Frontier have?
No attribute can be improved by moving from point to point without worsening at least one other attribute - describes tradeoffs in optimality
True/False:
Pareto Frontier can only be of a discrete set in the feasible objective space?
FALSE:
You can have MOO of continuous and discrete variable sets that make up your feasible objective space
How do you choose a design in MOO?
sample points from pareto frontier
What does a representative sampling of a pareto frontier entail?
- Points sampled from all regions of pareto frontier
- Points are fairly evenly spaced
- Enough points sampled to fulfill a purpose
What are the two general methods used in MOO algorithms to select points?
- Define single-objective subproblems s.t. solution of each problem gives point on pareto frontier by:
- changing objective function or changing constraints - Simultaneously optimize a population of points to iteratively approach the true pareto frontie
What is an Aggregate Objective Function (AOF) Approach for a MOO algorithm?
Building an aggregate single-objective function which weights each attribute defining a subproblem to form a spaced field to yield even sample of pareto frontier
What are the benefits and downfalls of using AOF?
Benefit is it includes constraints on independent vbs/attributes designer can impose, and its a single objective to solve
Downfall is it can only sample regions of pareto frontier with curvature >= AOF curvature
(generally convex, so bad when something is concave)
-leads to irregular sampling
What are other methods of single-objective solutions to MOO problems (Besides AOF)?
Epsilon constraint method -
Normal Boundary intersection
Normal Constraint Method
NSGA-II
What are Non-Domination Levels?
Generalization of how “dominated” vs. “non-dominated” a population member is relative to other members in pop.
0 - population member non-dominated
>0 - increasingly higher level of dominance
What is a Crowding Distance?
Distance to measure how isolated each point in population is.
- calculated among population of same non-domination level, the crowding distance allows us to be preferential to isolated points (largest crowding distance)
What is a Surrogate Model?
A surrogate model is an approximation of the objective functional form f ̃(x),f(x) = f ̃(x)+ϵ(x)
where the error is the difference between the true function and the surrogate model.
What is surrogate modeling?
Surrogate modeling uses an approximation of a much more computationally expensive tool (CFD/FEA) to run larger design space explorations or design optimizations with fewer function calls.
What are common uses of surrogate models?
Optimization, trade space exploration, probabilistic studies, robust design, information transmission.
What do you need to build a surrogate model?
- Sample of points
- Value of objective function f(x) at each sampled point
- Functional approximation form for surrogate
- Systematic way to set parameters in surrogate to “best match” the true function.
What is a common a-priori method of surrogate model design space sampling?
Design of Experiments (DoE)
What is deterministic vs. stochastic (w.r.t. engineering and design of experiments)?
Deterministic is when experiments produce the same results every time because
What are (DoE) Design of Experiments?
Plans/stencils that define design space point exploration for experimental application.
What types of DoE’s are used to create surrogate models?
Structured DoEs, Unstructured:
Full Factorial/Fractional/Orthogonal, Latin Hypercube/Quasi-Monte
What are the primary types of surrogate functional forms?
- Polynomial Response Surface Equations (RSEs)
- Radial Basis Functions (RBFs)
- Gaussian Processes
- Artificial Neural Networks (ANN)
- Support vector machines (SVMs)
What are the general steps of surrogate modeling?
- Sampling (DoE)
- to specify the points x and determine corresponding f(x) - Fitting/Training
- determining unknown parameters in surrogate to best match f (x) - Validating
- comparison between surrogate and f (x) at non training samples
- repeat 1,2 - Prediction
- using model to predict/design
What is an overdetermined problem in surrogate modeling?
If the resulting number of training points is greater than the number of basis functions
What process do we use to fit an overdetermined system?
Minimize sum-squared error (SSE) giving a least squares solution.
What is a perfectly determined system in surrogate modeling? (what does this imply?)
When your solution is square, # training points = # basis functions.
It implies the system is an interpolant (can only predict at those points, no information about the actual behavior of the function)
What is a an underdetermined problem in surrogate modeling?
When number of points is less than the number of basis functions, it is rank deficient/singular,
How do you find a solution to an underdetermined problem?
Use regularization. Underdetermined systems have singular matrix which does not have same solution, use of regularization modifies the objective using a ridge regression.
What type of surrogate model is used to solve an interpolant problem?
Radial Basis Functions - Constructed as interpolating models s.t. m=n
What is a Radial Basis Function?
Class of surrogate model for which the basis function (of which there is only one not ‘n’) depends only on the radial distance between two training points.
What are the primary properties of a Radial Basis Function?
- single functional form of basis function is square & invertible
- fitting error should be zero
- trained/fit same way as polynomials (multiple linear regression)
- implemented as interpolating models (m=n)
What type of problem is an Artificial Neural Network used to solve?
ANN is used as a surrogate model for nonlinear regression fitting in nonlinear optimization problems.
What are the characteristics that define basic topology of an ANN?
Input neurons, number of hidden layers, number of hidden nodes per layer, and the pattern of interconnected nodes-edges (feed-forward vs. feedback)
How does an ANN address basis functions for surrogate models?
ANN uses an activation function - i.e. to approximate smoothed step function (logic of neuron)
What is MDO?
Multidisciplinary Design Optimization - The technical field formally approaching design of complex engineering systems a subset of MDAO
DEF: (for reference if needed)
“A methodology for design of complex systems and subsystem that coherently exploits synergism of mutually interacting phenomena”
What is the difference between Single-level MDO and Multi-level MDO?
Single-level approaches (monolithic architectures) only use one optimizer (at system level), where only disciplinary analysis is embedded in architecture
Multi-level approaches (distributed architecture) use optimizers at both system and subsystem level to address individual analysis optimization. Design process & disciplinary analysis is distributed.
What are the main types of monolithic architectures?
Multidisciplinary Feasible (MDF), Individual Discipline Feasible (IDF), All-at-once (AAO), Simultaneous Analysis and Design (SAND)
What is the motivation for using MDO?
Complex engineering design problems requiring multiple disciplines coupled together, solving two tasks simultaneously:
- Organizing and coordinating disciplines to perform multidisciplinary analysis
- Systematically optimizing the design
What are the distinguishing features of single-level MDO methods?
Non-Hierarchical, analyses computationally inexpensive, no sub-optimization problems embedded within problem formulation, sub optimal solution if more than one exists.
What is Multidisciplinary Feasible?
MDF is a monolithic non-hierarchical MDO that solves full multidisciplinary analysis at each new design point.
What are the advantages and disadvantages of MDF?
Advantages:
- Each new pt always satisfies gov. equations, ensuring feasibility over all disciplines
- Effective if nested iteration converges quickly
- Can use legacy comp. analysis tools w/out modification
Disadvantages:
- Takes a long time
- Sub optimal solution if more than one exists
- Not easily parallelizable
What is Individual Discipline Feasible?
A monolithic, hierarchical
architecture of MDO that solves single-disciplinary feasibility at each iteration of the sub analyses, not MDF until optimizer converges completely.
What are the advantages and disadvantages of IDF?
Advantages:
- Parallelizable
- improves convergence
- more likely to find optimal solution if multiple exist
Disadvantages:
- Taxing with increased variables to control (w/ increased coupling control in optimizer)
- Produces inconsistent solution if optimizer fails to converge
What type of solvers are typically used for MDF?
Root finding algorithms like - Fixed point iterations (FPI)
What is the general process of FPI?
** EASIER IF YOU DRAW
Generally (using 2 coupled subsystems A(x,yb) - B(x,ya)):
- Calculate initial A’s outputs (y,a) with starting design point and guess for B’s outputs (y,b0).
- Calculate B’s outputs (y,b) with design point, and A’s outputs to get true output (y,a).
- Re-calc A’s output with design pt, and B’s output (y,b).
- continue repeating cycle of exchange output-input between coupled disciplines until iteration tolerance met = converged fixed point
What are the main types of distributed architectures of MDO?
Collaborative Optimization (CO), and Analytical Target Cascading (ATC)
What are distributed architectures most useful?
When problem scale is too large for one optimizer, when you have many subsystem-level disciplinary optimizers, when there are highly coupled designs between disciplinary analyses
Explain analysis vs. Design/Optimization
Analysis is determining the response of a system described by a set of design variables, whereas Design/Optimization determines the set of design variable-values that produce the “best” system response
True/False: MDA stems from MDO
False, MDO stems from MDA and the study of both in a multidisciplinary context is MDAO.
What type of convergence does FPI see?
Monotonic - Fixed point attraction to single point
Oscillatory - Infinitely looping around orthogonal curves around attractive FP.
Divergence - diverged solution due to repulsive FP
Multiple FP -
Convergence based on initial guesses, may be suboptimal
How do you improve upon FPI issues?
Relaxation - introduced damping to allow for solution perturbation
What is Collaborative Optimization?
CO is a distributed architectural optimization method of MDO which partitions disciplines into subsystem optimizations with individual analysis
Tasked to minimize system-level objective function while driving each individual optimizer analysis to design consistency via equality constraints on system level
What is Analytical Target Cascading?
ATC is a distributed architectural optimization method of MDO which tends to structure product development industry barriers/boundaries
When do you use Regularization?
To solve underdetermined surrogate models where the number of training points m < n basis functions - gives us a singular matrix for our solution.
What is regularization?
The modification of an underdetermined surrogate model to include a diagonal ridge along the basis function matrix to make it invertible regardless of m
