1 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Multidisciplinary System Design Optimization (MSDO) Multiobjective Optimization (II) Lecture 17 April 5, 2004 by Prof. Olivier de Weck 2 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics MOO 2 Lecture Outline Lecture 2 (today) ? Alternatives to Weighted Sum (WS) Approach Multiobjective Heuristic Programming Utility Function Optimization Physical Programming (Prof. Messac) Application to Space System Optimization Lab Preview (Friday 4-9-2003 – Section 1) 3 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Weighted Sum (WS) Approach 1 z i MOi i i w JJ sf = = | utopia Max(J 1 ) Min(J 2 ) miss this concave region Pareto front convert back to SOP LP in J-space easy to implement scaling important ! weighting determines which point along PF is found misses concave PF w 2 >w 1 w 1 >w 2 J-hyperplane J* i J* i+1 4 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Weighted Square Sum Approach 22 11 2 2 J wJ wJ=+ Obj. Fun. Line J1 J2 Ref: Messac 5 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Compromise Programming (CP) Obj. Fun. Line 11 2 2 nn JwJ wJ=+ 55 This allows “access” to the non-convex part of the Pareto front 6 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Multiobjective Heuristics Pareto ranking scheme Allows ranking of population without assigning preferences or weights to individual objectives Successive ranking and removal scheme Deciding on fitness of dominated solutions is more difficult. Pareto ranking for a minimization problem. Pareto Fitness - Ranking Recall: Multiobjective GA This number comes from the D-matrix 7 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Example Multiobjective GA () 2 11 1 1 ,..., 1 exp n ni i fx x x n = ao §· =? ? ? ?? ¨? ?1 ?? | Minimization Objective 1 Objective 2 () 2 11 1 1 ,..., 1 exp n ni i fx x x n = ao §· =? ? + ?? ¨? ?1 ?? | No mating restrictions With mating restrictions 8 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Double Peaks Example: MO-GA Multiobjective Genetic Algorithm Generation 1 Generation 10 9 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Utility Function Approach Decision maker has utility function This function might or might not be known mathematically U maps objective vector to the real line : z U →\MOLP: MONLP: () { } max ,US=∈JJ Cxx () () { } max ,UfS=∈JJ x x (0,0) (0,4) (3,0) = = = 1 2 3 x x x { } {} 112 21 12 12 12 max max s.t. 4x 3 12 , 0 where 2 J xx Jx x xx UJJ =+ = +≤ ≥ = x 1 x 2 c 1 x 2 c 2 x 3 x 1 S U=24 U=18 Example: 10 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Utility Function Shapes J i U i J i U i U i J i U i J i Monotonic increasing decreasing Strictly Concave Convex Concave Convex Non-monotonic Cook: Smaller-is-better (SIB) Larger-is-better (LIB) Nominal-is -better (NIB) Range -is-better (RIB) - Messac: Class 1S Class 2S Class 3S Class 4S 11 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Example: Room Control Optimization Want: - temperature in ideal range 68-72 oF - humidity above 56% is undesirable Assume: temperature humidity T H = = 1 2 cx cx U T T [oF] 68 72 undesirable ideal U H H [%] 56 undesirable ideal Formulate as a MOLP { } {} 11 2 1 1 2 2 112 min min s.t. 68 72 56 , , , , 0 dd d d d d ddd ?+ + ? + + ??+ + +≥ ?≤ ?≤ ≤≥ 1 1 cx cx cx Ax b x Using deviational variables 12 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Aggregated Utility The total utility becomes the weighted sum of partial utilities: Attribute J i customer 1 customer 2 customer 3 Caution: “Utility” is a surrogate for “value”, but while “value” has units of [$], utility is unitless. interviews Combine single utilities into overall utility function: Steps: MAUA 1. Identify Critical Objectives/Attrib. 2. Develop Interview Questionnaire 3. Administer Questionnaire 4. Develop Agg. Utility Function 5. Analyze Results (performance i) U i (J i ) ki’s determined during interviews K is dependent scaling factor … sometimes called multi-attribute utility analysis (MAUA) 1.0 E.g. two utilities combined: () 12 12 1 2 1 1 2 2 ,()()()()UJ J KkkUJUJ kUJ kUJ=++ For 2 objectives: 1212 (1 ) /K kkkk=?? 13 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Notes about Utility Maximization Utility maximization is very common and well accepted Usually U is a non-linear combination of objectives J Physical meaning of aggregate objective is lost (no units) Need to obtain a mathematical representation for U(J i ) for all I to include all components of utility Utility function can vary drastically depending on decision maker …e.g. in U.S. Govt change every 3-4 years 14 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Physical Programming Classify Each Design Objective SOFT Class-1S Smaller-Is-Better, i.e. minimization. Class-2S Larger-Is-Better, i.e. maximization. Class-3S Value-Is-Better. Class-4S Range-Is-Better. HARD Class-1H Must be smaller. Class-2H Must be larger. Class-3H Must be equal. Class-4H Must be in range. Ref: Prof. Achille Messac, RPI 15 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Quantify Preference for Each Design Metric Ex: Mass of Beam Highly Desirable < 250 (kg) Desirable 250 - 275 Tolerable 275 - 300 Undesirable 300 - 325 Highly Undesirable 325 - 350 Unacceptable > 350 Physical Programming 16 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Mass Quantity M i nim ized Inside Cod e Physical Programming 18 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Preference Function of Each Objective Cost (preference) is on the vertical axis, and will be minimized. The value of the design metric (obj) is on the horizontal axis. The designer chooses limits of several ranges for each design metric. Each range defines relative levels of desirability within a given design metric (obj). We then have a preference function for each design metric. These preference functions are added to form an aggregate preference function. GU S 19 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics μ i (x) ≤ v i5 min x P(μ)= 1 n sc Σ i =1 n sc P i [μ i (x)] (for soft classes) (for class 1S metrics) (for class 2S metrics) (for class 3S metrics) (for class 4S metrics) (for class 1H metrics) (for class 2H metrics) (for class 3H metrics) (for class 4H metrics) (for des. variable. constraints) Subject to μ i (x) ≥ v i5 v i5L ≤ μ i (x) ≤ v i5R v i5L ≤ μ i (x) ≤ v i5R μ i (x) ≤ v i,max μ i (x) ≥ v i,min μ i (x)=v i,val v i,min ≤ μ i (x) ≤ v i,max x j,min ≤ x j ≤x j,max Physical Programming Problem Model Nomenclature here μ is used similar to J in the class 20 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Application to System Design Multiobjective Problem: – Minimize Cost AND Maximize Performance Simultaneously Which design is best according to these decision criteria? Key Point: Multi-Objective problems can have more than one solution! Single objective problems have only one true solution. 0 500 1000 1500 2000 0 0.5 1 1.5 2 Multi-Objective Illustration Performance (total # images) L i f e c ycl e C o st ( $ b i l l i o n s) Design 3 Design 2 Design 4 Design 1 Design 5 (500,$0.5B) (1400,$0.8B) (2000,$1.5B) (1600,$1.8B) (1000,$1.3B) Optimize Architecture of Terrestrial Planet Finder (TPF) Mission (expected Launch 2011) 21 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics The Pareto Boundary In a two-dimensional trade space (I.e. two decision criteria), the Pareto Optimal set represents the boundary of the most design efficient solutions. 0 500 1000 1500 2000 2500 3000 3500 4000 800 1000 1200 1400 1600 1800 2000 2200 Performance (total # of images) Li f e c ycl e C o s t ( $ M ) TPF System Trade Space Pareto-Optimal Front Dominated Solutions Non-Dominated Solutions $2M/Image $1M/Image $0.5M/Image $0.25M/Image 4AP - 1D SSI - 4m Dia - 1AU 4AP - 1D SCI - 1m Dia - 1AU SSI SCI 22 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics TPF Pareto Optimal Set # “Images” LCC ($B) Orbit (AU) # Apert.’s Architecture Apert. Diam. (m) 502 0.743 1.5 4 SCI-1D 1 577 0.762 2.0 4 SCI-1D 1 651 0.767 2.5 4 SCI-1D 1 1005 0.768 1.5 4 SCI-1D 2 1114 0.788 2.0 4 SCI-1D 2 1171 0.790 2.5 4 SCI-1D 2 1195 0.807 1.5 6 SCI-1D 2 1292 0.811 1.5 6 SCI-2D 2 1317 0.830 1.5 8 SCI-1D 2 1424 0.836 2.0 4 SCI-1D 3 1426 0.838 1.5 8 SCI-2D 2 1464 0.867 2.5 6 SCI-2D 2 1631 0.877 1.5 6 SCI-1D 3 1684 0.881 1.5 6 SCI-2D 3 1687 0.932 2.0 6 SCI-1D 3 1828 0.936 2.0 6 SCI-2D 3 1881 0.980 1.5 8 SCI-2D 3 1978 0.982 1.5 6 SCI-1D 4 2035 1.086 2.0 8 SCI-2D 3 2132 1.112 1.5 8 SCI-1D 4 2285 1.120 1.5 8 SCI-2D 4 2328 1.190 2.5 6 SCI-2D 4 2398 1197 3.0 6 SCI-2D 4 2433 1.212 4.0 6 SCI-2D 4 2472 1.221 4.5 6 SCI-2D 4 2482 1.227 5.0 6 SCI-2D 4 2487 1.232 5.5 6 SCI-2D 4 2634 1.273 2.5 8 SCI-2D 4 2700 1.280 3.0 8 SCI-2D 4 2739 1.288 3.5 8 SCI-2D 4 2759 1.296 4.0 8 SCI-2D 4 2772 1.305 4.5 8 SCI-2D 4 2779 1.312 5.0 8 SCI-2D 4 2783 1.317 5.5 8 SCI-2D 4 2788 1.569 3.0 6 SSI-2D 4 2844 1.609 3.5 6 SSI-2D 4 2872 1.655 4.0 6 SSI-2D 4 2988 1.691 2.0 8 SSI-1D 4 3177 1.698 2.5 8 SSI-1D 4 3289 1.739 3.0 8 SSI-1D 4 3360 1790 3.5 8 SSI-1D 4 3395 1.850 4.0 8 SSI-1D 4 3551 1.868 2.5 10 SSI-1D 4 3690 1.919 3.0 10 SSI-1D 4 Family 4 ap. SCI-1D 1 m Diam. Family 8 ap. SCI-2D 4 m Diam. Family 8 ap. SSI-1D 4 m Diam. Intersection of Multiple Families Family 4 ap. SCI-1D 2 m Diam. Family 6 ap. SCI-2D 4 m Diam. Family 6 ap. SSI-2D 4 m Diam. Family 10 ap. SSI-1D 4 m Diam. Transition from SCI to SSI Designs Mission Cost & Performance Low Medium High 23 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Multi-Objective Optimization Example: Broadband Communication Satellite Constellation Goal: Determine with minimal computational effort a 4- dimensional Pareto optimal set. Broadband Design Goals: To simultaneously – Minimize Lifecycle Cost – Maximize Lifecycle Performance (# T1 minutes provided) – Maximize # Satellites in View Over Market Served – Maximize Coverage Over Populated Globe Key Question: Is it better to find and then combine a series of 2- dimensional P-optimal sets or attempt to simultaneously optimize all of the metrics of interest. Pareto Optimality: A set of design architectures in which the systems engineer cannot improve one metric of interest without adversely affecting at least one other metric of interest. This set quantitatively captures the trades between the design decision criteria. 24 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics The Broadband GINA Model Inputs (Design Vector) Key Outputs Throughput Lifecycle Cost Market Capture Revenues Net Present Value Availability Cost Per T1 Minute # Orbital Planes …. Constellation Altitude Payload & S/C Bus Launch & Operations Market Analysis Orbital Dynamics Link Budgets Systems GINA MATLAB Models Antenna Power 1 2 3 4 5 6 7 8 9 10 0 10 20 30 40 50 60 70 80 90 100 Economic Analysis …. Inclination # S/C per Plane …. Antenna Area …. 25 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Case 1 – Multi-Objective Optimization Objective: Minimize LCC & Maximize Performance Optimization Formulation & Pareto Plots # Pareto Optimal Designs Found (60 Iterations) 126412 4-Dimensional P-Opt.LCC vs. Global Population Coverage LCC vs. Mean # Satellites in View LCC vs. Performance 10 1 10 1 Objective: Constraints: Isolati () AND on 90% ( / 4 4 ) . y y y y Subje M ct to MAE Eb No in Max φΓ ΨΓ = = | | ≥ ≥ 5 min db 6.0 db Integrity 10 Rate 1.54 Mbps Per Link Availability 10 ( Link Margin BER R P ε ? ≥ ≤ ≥ ≥ D ) 98%Coverage ≥ 26 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Case 2 – Multi-Objective Optimization Objective: Minimize LCC & Maximize Mean # Satellites in View # Pareto Optimal Designs Found (60 Iterations) 115118 4-Dimensional P-Opt.LCC vs. Global Population Coverage LCC vs. Mean # Satellites in View LCC vs. Performance 10 1 480 1 1 Objective: Constraints: () A Isolation 90% ND 48 0 y y n ij j i Sub Min SIV n M jec ME a to A x t φΓ = = = | | | ≥ 5 min /4.4 db 6.0 db Integrity 10 Rate 1.54 Mbps Per Link Availability 10 Eb No Link Margin BER R ε ? ≥ ≥ ≤ ≥ ≥ D ( ) 98%P Coverage ≥ Optimization Formulation & Pareto Plots 27 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Case 3 – Multi-Objective Optimization Objective: Minimize LCC & Maximize Global Population Coverage # Pareto Optimal Designs Found (60 Iterations) 4443 4-Dimensional P-Opt.LCC vs. Global Population Coverage LCC vs. Mean # Satellites in View LCC vs. Performance Optimization Formulation & Pareto Plots 10 1 480 240 1 1 () AND 480 2 Objective: Constraints: Isolation 90% 40 y y ij j i Subject to M Min C M E V A O ax φΓ = = = | | ≥ | 5 min / 4.4 db 6.0 db Integrity 10 Rate 1.54 Mbps Per Link Availability 10 Eb No Link Margin BER R ε ? ≥ ≥ ≤ ≥ ≥ D ( ) 98%P Coverage ≥ 28 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Case 4 – Multi-Objective Optimization Objective: 4-Dimensional Simultaneous Optimization # Pareto Optimal Designs Found (180 Iterations) 445916 4-Dimensional P-Opt.LCC vs. Global Population Coverage LCC vs. Mean # Satellites in View LCC vs. Performance 10 1 10 1 480 1 1 480 1 () AND ( ) AND AND 480 Objective: y y y y n ij j i ij j Min Max SIV n Max COV Max φΓ ΨΓ = = = = = | | | | | 240 1 Constraints: 048 240 i= | # Optimization Formulation & Pareto Plots 29 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics (PA PB) PC Multi-Objective Optimization Comparison # 4-D Pareto Optimal Design Architectures Found 44P-Opt.4-D Simultaneous Optimization4 39(A U B) U CUnion of All Explored Designs3 21(PA U PB) U PCUnion of P-Opt. Sets2 1(PA PB) PC Intersection of P-Opt. Sets1 Size of Pareto Optimal Set Mathematical Representation Approach#  *Each case required the same amount of computational effort = 180 iterations.  (PA U PB) U PC PA PCPB {TS} (A U B) U C A CB {TS}PA PCPB {TS} 30 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Observations Combining a sequence of 2-D Pareto Optimal sets via {Set Theory} is a viable approach for finding n- dimensional P-optimal sets of design architectures. However, it appears to be more computationally efficient to formulate a single n-dimensional multi- objective optimization problem, despite the difficulty in visualizing the solution (can’t plot on orthogonal axes, can plot on “radar plot.”) 31 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics N-Dimensional Problems The same principles of Pareto Optimality hold for a trade space with any number n dimensions (I.e. any number of decision criteria). 3 Criteria Example for Space-Based Radar – Minimize(Lifecycle Cost) AND – Minimize(Maximum Revisit Time) AND – Maximize(Target Probability of Detection) 32 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Four Basic Tensions (Trade-offs) in Product/System Development Performance Schedule Risk Cost One of the main jobs of the system designer (together with the system architect) is to identify the principle tensions and resolve them Ref: Maier and Rechtin, “The Art of Systems Architecting”, 2000 33 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Multiobjective Optimization and Isoperformance Non-dominated solutions occur, where Isoperformance curves are tangent to each other Pareto-optimal Curve Tensions in Engineering System Design can be quantified J1 J2 34 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Vector Optimization and Game Theory x1 x2 J1 contours J2 contours Prisoner’s Dilemma Region (cooperative) Pareto Front (The Contract Curve) Nash Equilibrium (uncooperative) 35 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics In Practice Inefficient solutions are not candidates for optimality In practice a “near-optimal” solution is acceptable Solutions that satisfactorily terminate the decision process are called “final solutions” Multiple Criteria Decision Making (MCDM) Multiattribute Decision/Utility Analysis Multicriteria Optimization* - small # of alternatives - environment of uncertainty - resolving public policy problems - e.g. nuclear power plant siting, airport runway extensions ... - large # of feasible alternatives - deterministic environment - less controversial problems - business and design problems Ref: Keeney & Raiffa, 1976 36 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Lecture Summary Two fundamental approaches to MOO – Scalarization of multiple objectives to a single combined objective (e.g. Utility Theory) – Pareto Approach with a posteriori selection Methods for computing Pareto Front – Weighted Sum Approach (and variants) – Design Space Exploration + Pareto Filter – Normal Boundary Intersection (NBI) – Multiobjective Heuristic Algorithms Resolving Tradeoffs are an essential part of System Optimization 37 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics References Edgeworth, F.Y., Mathematical Psychics, P. Keagan, London, England, 1881. Pareto, V., Manuale di Economia Politica, Societa Editrice Libraria, Milano, Italy, 1906. Translated into English by A.S. Schwier as Manual of Political Economy, Macmillan, New York, 1971. Ehrgott, M., Multicriteria Optimization, Springer-Verlag, New York, NY, 2000. Stadler, W., “A Survey of Multicriteria Optimization, or the Vector Maximum Problem,” Journal of Optimization Theory and Applications, Vol. 29, pp. 1-52, 1979. Stadler, W. “Applications of Multicriteria Optimization in Engineering and the Sciences (A Survey),” Multiple Criteria Decision Making – past Decade and Future Trends, ed. M. Zeleny, JAI Press, Greenwich, Connecticut, 1984. Stadler, W., Multicriteria Optimization in Engineering and in the Sciences, Plenum Press, New York, NY, 1988. Steuer, Ralph, “Multiple Criteria Optimization - Theory, Computation and Application”, 1985 38 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Lab#3: Friday - MO in iSIGHT iSIGHT is set up to do Weighted Sum optimization Note Weights and Scale Factors in Parameters Table 39 ? Massachusetts Institute of Technology - Prof. de Weck and Prof. Willcox Engineering Systems Division and Dept. of Aeronautics and Astronautics Lab #3: Multiobjective Optimization Game Task: Find an optimal layout for a new city, which comprises 5x5 sqm and 50’000 inhabitants that will satisfy multiple disparate stakeholders. 5 miles 5 miles Stakeholder groups: a) Local Greenpeace Chapter b) Chamber of Commerce c) City Council (Government) d) Resident’s Association e) State Highway Commission What layout should be chosen ? A B Commercial Zone (shops, restaurants, industry) Recreational Zone (parks, lakes, forest) Residential Zone (private homes, apartments) 1 2 3 0 Vacant Zone