Analysis of Algorithms for Multi-Objective Min-Max Optimization
Explore the comparison of two algorithms for multi-objective min-max optimization in the field of mechanical and aerospace engineering. The study delves into design under uncertainty, evidence theory, and methodology, providing insights into MACS and IDEA approaches. Learn about initialization techniques and the cross-check process involved in these optimization strategies.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
ANALYSIS OF TWO ALGORITHMS FOR MULTI-OBJECTIVE MIN-MAX OPTIMIZATION Simone Alicino Prof. Massimiliano Vasile Department of Mechanical and Aerospace Engineering University of Strathclyde, Glasgow, UK BIOMA 2014 13thSeptember 2014, Ljubljana, Slovenia
Design under uncertainty d, u f(d,u) Model of the System f aleatory pdf u u Bel/Pl epistemic bba m3 m1 u m2 f 2
Evidence theory Belief and Plausibility that f(u) < ? 1 2 3 4 Bel(f < ) = m( 1) + m( 2) = 0.4 m( 2) = 0.1 m( 1) = 0.3 m( 3) = 0.4 m( 4) = 0.2 Pl(f < ) = m( 1) + m( 2) + m( 3) = 0.8 3
Methodology ???= min max u u ??1d d,u u ,max u u ??2d d,u u , ,max u u ???d d,u u d d ? MACS2 Population-based search Pareto ranking + Tchebycheff scalarization Exploitation: sampling of neighborhood Exploration: differential evolution Archive IDEA Population-based search Hybrid DE + MBH Improves local convergence Avoids stagnation MACS ???= min ? 1 d d ????? d d,u u , ,???? d d,u u 1 d d? ???? ???? ? IDEA 1 ???? = max u u ??1d d?,u u CROSS-CHECKS To rank ?(d d1,u u1) and ? d d2,u u2, check ? d d1,u u2 and ?(d d2,u u1) Increase prob. of finding global maxima ? ???? = max u u ???d d?,u u 4
Initialization MACS Individualistic Actions Cross-Check INITIALIZATION Initial population is randomly generated (LHS) in the search Min-Max Selection INDIVIDUALISTIC ACTIONS Child generated by random moves (pattern search) of each agent. Social individuals domain D. Social Actions SUBPROBLEM SELECTION update of the composition of the social population and their associated scalar All other individuals Cross-Check Min-Max Selection SOCIAL ACTIONS Child generated by interaction (DE) of agents with neighbours or global archive. subproblems. Validation Cross-Check GLOBAL ARCHIVE an external repository in which non-dominated solutions are stored. The archive is kept below a maximum size. Subproblem selection Archive resize 5
MACS: Cross-check f2 If agent in the population dominates or is dominated by the archive ?(d d,u u) ??(d d?,u u?) ?12(d d,u u?) ?21(d d?,u u) f1 ?12d d,u u? > ? d d,u u u u u u?,? ?12 ?21??,u u > ????,?? u u? u u,?? ?21 6
MACS: Min-max selection f f u unew D U d dnew d d??? d d,u u??? u u ? d d,u u??? > ? d d,u u u u u u??? d d??? d d,u u??? u u ? d d???,u u < ? d d,u u d d d d??? d d??? d d, u u??? u u d d d d???,u u u u??? otherwise 7
MACS: Validation f2 Run global optimization over U ?? u u? > ??u u? u u? u u?,?? ?? until ??= ?? ?2 f1 8
MACSminmax Initialization INITIALIZATION Initial population is randomly generated (LHS) and U-archive is initialized. MO GLOBAL MINIMIZATION Performed by MACS2 on d space, and uses u s stored in U-archive (internal cross- check). MO minimization MACS2 Cross-Check Archive min solutions ARCHIVE MAXIMA Store in U-archive solution of IDEA only if it is better than solution of MACS2 (maximization might fail to find global optimum) SO maximizations IDEA SO GLOBAL MAXIMIZATION Performed by IDEA on u space, for each di solution of MO global minimization Archive max solutions FINAL CROSS-CHECK Local search to refine accuracy of U-archive Cross-Check Dominance 9
MACSminmax: restoration Archived maximum Candidate minimum in d Selected minimum in d Solution 10
Comparison MACS MACSminmax Local search vs. cross-check for every agent of the minimization Initialization Initialization Individualistic Actions MO minimization MACS2 Cross-Check Cross-Check Both implement similar mechanisms to increase probability of archiving global maxima Min-Max Selection Archive min solutions Social Actions SO maximizations IDEA Cross-Check Archive max solutions Min-Max Selection Validation Cross-Check Global vs. local search, same purpose: make sure that each d is associate to a global maximum u Cross-Check Dominance Subproblem selection Archive resize 11
Performance metrics ?? ?? ?? ?? 1 Convergence ?????= min ? ??100 ?? ?=1 ?? ?? ?? ?? 1 Spreading ????= min ? ??100 ?? ?=1 ?????= Pr ?????< ????? Success rate ????= Pr ????< ???? 12
Test cases Settings MACS2 200n function evaluations 10 agents 5 (1/2) social agents F = 1 CR = 0.1 IDEA 200n function evaluations 5 agents F = 1 CR = 0.1 13
Test case 1 ?=2 2 ?1= ???? ?=1 ?=2 ?2= 5 ?? 1 + cos?? + ?? 1 1 + sin?? ?=1 Max f1 Max f2 Mconv Mspr pconv / tconv pspr / tspr MACS 100% 100% 0.2 1.7 100 / 0.5 79 / 2 MACSminmax 100% 100% 0.2 1.3 100 / 0.5 100 / 2 14
Test case 2 ?=8 2 ?1= ?? ?? ?=1 ?=8 ?2= 2? ?? cos ?? ?? ?=1 Max f1 Max f2 Mconv Mspr pconv / tconv pspr / tspr MACS 100% 65% 0.5 16.1 100 / 1 0 / 2 MACSminmax 100% 60% 0.6 2.0 100 / 1 64 / 2 15
Test case 3 ?=8 2 ?1= ?? ?? ?=1 ?=8 ?? 3?? sin??+ ?? 22 ?2= ?=1 Max f1 Max f2 Mconv Mspr pconv / tconv pspr / tspr MACS 100% 100% 0.6 7.5 46 / 0.5 3 / 2 MACSminmax 100% 100% 0.1 0.3 100 / 0.5 100 / 2 16
Test case 4 ?=2 ?1= 2? ?? cos ?? ?? ?=1 ?=2 ?2= ?? ?? cos 3?? 5?? ?=1 Max f1 Max f2 Mconv Mspr pconv / tconv pspr / tspr MACS 100% 91.3% 0.3 0.9 83 / 0.5 97 / 2 MACSminmax 100% 85.7% 0.4 1.0 77 / 0.5 91 / 2 17
Test case 5 ?=4 ?1= 2? ?? cos ?? ?? ?=1 ?=4 ?? 3?? sin??+ ?? 22 ?2= ?=1 Max f1 Max f2 Mconv Mspr pconv / tconv pspr / tspr MACS 98.6% 54.1% 1.2 5.8 48 / 1 60 / 6 MACSminmax 92.8% 87.6% 2.7 8.0 24 / 1 42 / 6 18
Test case 6 ?=1 ?1= ??+ ??cos 3?? ??5 ? + 5 ?=1 ?=1 ?2= ?? ?? cos 3?? 5?? ?=1 Max f1 Max f2 Mconv Mspr pconv / tconv pspr / tspr MACS 100% 100% 0.3 1.2 95 / 0.5 97 / 2 MACSminmax 100% 100% 0.3 2.0 91 / 0.5 63 / 2 19
Test case 7 ?=8 2 ?1= ?? ?? ?=1 ?=8 ?2= 2? ?? cos ?? ?? ?=1 ?=8 ?? 3?? sin??+ ?? 22 ?2= Max f1 Max f2 Max f2 Mconv Mspr pconv / tconv pspr / tspr ?=1 MACS 100% 100% 95.3% 5.0 9.3 50 / 5 8 / 5 MACSminmax 100% 100% 98.3 4.6 2.1 66 / 5 100 / 5 20
Conclusions Worst-case design Evidence Theory to model epistemic uncertainty Maximization of Belief function: worst-case scenario design Two multi-objective algorithms Cross-checks to increase probability to find global maximum MACS : bi-level algorithm, modification of MACS2 MACSminmax: restoration methodology, works with any MO/SO algorithm Test cases 6 bi- and 1 three- objective cases, with different dimensions and complexity Global fronts identified, with good to excellent accuracy Comparable performance between MACS and MACSminmax Limitations Limited number of cases, objectives, and dimensions Test suite: neither fronts, nor global maxima analytically known (difficult to assess performance) 21
Evidence theory Belief and Plausibility that f(u) < ? 23
Computational approach 1. Worst-case solution (Bel = 1) (best d that gives the minimum of the maxima of f over u) Above this point the design is certainly feasible given the current information. 1 Pl Bel 24
Results 25
Fronts 26
