Draft version
Contents
Visualization in Multiobjective Optimization The final version will be available at http://dis.ijs.si/tea/research.htm Bogdan Filipič    Tea Tušar CEC Tutorial, Donostia - San Sebastián, June 5, 2017 Computational Intelligence Group Department of Intelligent Systems Jožef Stefan Institute Ljubljana, Slovenia Introduction A taxonomy of visualization methods Visualizing approximation sets Introduction Visualizing EAF values and differences Summary References 2 m
Introduction
Multiobjective optimization problem Minimize f: X → F f: (x1, . . . , xn) {→ (f1(x1, . . . , xn), . . . , fm(x1, . . . , xn)) • X is an π-dimensional decision space ・ F ⊂ R m is an m-dimensional objective space ( m ≥ 2) Conflicting objectives → a set of optimal solutions • Pareto set in the decision space •  Pareto front in the objective space
Introduction
Visualizing solution sets in the objective space • Interested in sets of mutually nondominated solutions called approximation sets • Different from ordinary multidimensional solution sets ・ The focus of this tutorial
Challenges
• High dimension and large number of solutions • Limitations of computing and displaying technologies ・ Cognitive limitations
Introduction
Visualization in multiobjective optimization Useful for different purposes [13] • Analysis of solutions and solution sets • Decision support in interactive optimization • Analysis of algorithm performance
Visualizing solution sets in the decision space
• Problem-specific • If X ⊂ R m , any method for visualizing multidimensional solutions can be used • Not the focus of this tutorial S
Introduction
Visualization can be hard even in 2-D Stochastic optimization algorithms Single run → single approximation set • Multiple runs → multiple approximation sets Visualization of the Empirical Attainment Function (EAF) can be used in such cases 6 Introduction This tutorial is not about • Visualization for decision making purposes [26] • Visualization in the decision space • General multidimensional visualization methods not previously used on approximation sets
This tutorial covers
・Visualization in the objective space ・ Visualization of separate approximation sets [1] • Visualization of EAF values and differences in EAF values [2] 8
A taxonomy of visualization methods
Can be formed based on ・ (Transformed) objective values ・ Distribution of solutions ・ Relations among solutions ・ Relations among objectives • etc. [More on the taxonomy TBA] A taxonomy of visualization methods Visualizing approximation sets 9
Methodology
Comparing visualization methods
• No existing methodology for comparing visualization methods • Propose benchmark approximation sets (analog to benchmark problems in multiobjective optimization) • Visualize the sets using different methods • Observe which set properties are distinguishable after visualization
Benchmark approximation sets
Two different sets that can be instantiated in any dimension [1] • Linear with a uniform distribution of solutions • Spherical with a nonuniform distribution of solutions (more at the corners and less at the center) • Sets are intertwined Size of each set • 2-D: 50 solutions • 3-D: 500 solutions •  4-D: only 300 solutions since most methods cannot handle more 10
Benchmark approximation sets
Visualizing approximation sets
Desired properties of visualization methods •  Preservation of the • Dominance relation • Front shape • Objective range • Distribution of solutions
• Robustness
•  Handling of large sets • Simultaneous visualization of multiple sets • Scalability in number of objectives • Simplicity 11 12
Visualizing approximation sets
Existing methods
Showing only methods previously used in multiobjective optimization ・ General methods • Specific methods – designed for visualizing approximation sets Demonstration on 4-D benchmark approximation sets 14
Scatter plot matrix
Most often • Scatter plot in a 2-D space ・ Matrix of all possible combinations ・ m objectives → m − 1) different combinations
Alternatively
・ Scatter plot in a 3-D space ・ m objectives →  m (m −1)(m −2)  different combinations 6
General methods
• Scatter plot matrix • Bubble chart •  Radial coordinate visualization [16, 36] ・ Parallel coordinates [17] • Heatmaps [29] ・Sammon mapping [30, 33] • Neuroscale [24, 10] ・ Self-organizing maps [18, 27] •  Principal component analysis [39] •  Isomap [31, 21]
Scatter plot matrix
15 17 16
Scatter plot matrix
1, 18
Bubble chart
Preseniation of the rolation
Simultaneou Handling of Scalability Large sets visualization Simplicity
X
Bubble chart
4-D objective space •  Similar to a 3-D scatter plot •  Fourth objective visualized with point size 5-D objective space • Fifth objective visualized with colors
Radial coordinate visualization
Also called RadViz • Inspired from physics •  Objectives treated as anchors, equally spaced around the circumference of a unit circle • Solutions attached to anchors with 'springs' • Spring stiffness proportional to the objective value • Solution placed where the spring forces are in equilibrium 19 21 20
Radial coordinate visualization
dominance relation
Simultaneous Scalability visualization Simplicity 22
Parallel coordinates

Simplicity
Parallel coordinates
•  m objectives → m parallel axes • Solution represented as a polyline with vertices on the axes • Position of each vertex corresponds to that objective value •  No loss of information
Heatmaps
・ m objectives → m columns ・ One solution per row ・ Each cell colored according to objective value ・ No loss of information 24
Sammon mapping
Sammon mapping
Sammon mapping

• A non-linear mapping ・ Aims to preserve distances between solutions • d i j distance between solutionsגוּגandגוּגin the objective space • d i j distance between solutions x i in the visualized space • Stress function to be minimized • Minimization by gradient descent or other (iterative) methods Preservation of the Handling of Simultaneous dominance front shape objective distribution Robustness Scalability Large sets visualization of solutions relation range x x d z , − d z , ) 2 x 27 26 Simplicity × 29 28
Neuroscale
・ A non-linear mapping • Aims to minimize the same stress function as Sammon mapping • Uses a radial basis function neural network to model the projection 30
Self-organizing maps
Neuroscale
Preservation of the Handling of Simultaneou front shape objective distribution Scalability large sets visualization of solution relation range Simplicity • Self-organizing maps (SOMs) are neural networks • Nearby solutions are mapped to nearby neurons in the SOM • A SOM can be visualized using the unified distance matrix • Distance between adjacent neurons is denoted with color •  Similar neurons → light color ・ Different neurons (cluster boundaries) → dark color 32
Principal component analysis
• Principal components are linear combinations of objectives that maximize variance (and are uncorrelated with already chosen components) • They are the eigenvectors with the highest eigenvalues of the covariance matrix 34
Principal component analysis
lsomap
• Assumes solutions lie on some low-dimensional manifold and the distances along this manifold should be preserved • Creates a graph of solutions, where only the neighboring solutions are linked • The geodesic distance between any two solutions is calculated as the sum of Euclidean distances on the shortest path between the two solutions • Uses multidimensional scaling to perform the mapping based on these distances distribe 36
Isomap
Summary of the general methods
Specific methods

Simultaneous Handling of distribution Robustness large sets visualization of solutions •  Distance and distribution charts [4] ・ Interactive decision maps [23] ・ Hyper-space diagonal counting [3] ・Two-stage mapping [20] ・ Level diagrams [6] • Hyper-radial visualization [8] ・ Pareto shells [35] • Seriated heatmaps [36] ・ Multidimensional scaling [36] •  Prosections [1] X x 39 38 41 40
Distance and distribution charts
• Plot solutions against their distance to the Pareto front and distance to other solutions • Distance chart • Plot distance to the nearest non-dominated solution • Distribution chart • Sort solutions w.r.t. first objective • Plot distances between consecutive solutions •  For the first/last solution, compute distance to first/last non-dominated solution ・ k solutions → k + 1 distances • All distances normalized to [0, 1] 42
Interactive decision maps
The Edgeworth-Pareto hull (EPH) of an approximation set A contains all points in the objective space that are weakly dominated by any solution in A. Interactive decision maps • Visualize the surface of the EPH, not the actual approximation set • Plot a number of axis-aligned sampling surfaces of the EPH • Color used to denote third objective ・Fixed value of the forth objective 43
Interactive decision maps
Presentation of the dominance front shape objective distribution Handling of Simultaneous Scalability Simplicity rolation range
& 45 44
Distance and distribution charts
Hyper-space diagonal counting
• Inspired by Cantor's proof that shows |N| = |N 2 | = |N 3 |... • Discretize each objective (choose a number of bins) • In the 4-D case •  Enumerate the bins for objectives f 1 and f 2 • Enumerate the bins for objectives f3 and f4 • Plot the number of solutions in each pair of bins 46
Two-stage mapping
Steps
• Split solutions to nondominated and dominated solutions • Compute r as the average norm of nondominated solutions • Find a permutation of nondominated solutions that minimizes implicit dominance errors and sum of distances between consecutive solutions • First stage: distribute nondominated solutions on the circumference of a quarter-circle with radius r in the order of the permutation and with distances proportional to their distances in the objective space Second stage: map each dominated solution to the minimal point of all nondominated solutions that dominate it
Hyper-space diagonal counting
Linear Spherical Preservation of the relation
Scalability Preservation of the Handling of distribution objective Scalability Robustness Large sets of solutions Simplicity 47
Two-stage mapping
49 48
Level diagrams
Level diagrams
dominance Preservation of the front shape objective distribution Robustness of solutions range relation Simplitaneous Handling of Scalability Large sets visualization Simplicity 8 x 8 51 50
Hyper-radial visualization
• Solutions preserve distance (hyper-radius) to the ideal point •  Distances are computed separately for two subsets of objectives • Indifference curves denote points with the same preference
Hyper-radial visualization
rys, dominance relation Preservation of the Handling of Simultaneous front shape objective distribution Scalability Robustness visualization large sets of solations range Simplicity & •  m objectives → m diagrams • Plot solutions with objective f i on the x axis and distance to the ideal point on the y axis 52 53
Pareto shells
Pareto shells
relatio
Simplicity 55
• Use nondominated sorting to split solutions to Pareto shells • Represent solutions in a graph • Connect dominated solutions to those that dominate them (we show only one arrow per dominated solution) 54
Seriated heatmaps
• Heatmaps with rearranged objectives and solutions • Similar objectives and similar solutions are placed together • Ranks are used instead of actual objective values for a more uniform color usage • Similarity can be computed using • Euclidean distance •  Spearman's footrule • Kendall's ↑ metric
Seriated heatmaps
56
Multidimensional scaling
• Classical multidimensional scaling aims at preserving similarities between solutions ・ Here, dominance distance is used to measure similarity • Two solutions are similar if they share dominance relationships with a third solution
[I(( a ; < z ; ) ∧ ( b ; < z ; )) + I(( a ; = z ; ) ∧ ( b ; = z ; )) + I(( ạẓẓẓẓẓẓẓẓẓẓẓẓẓẓẓẓẓẓẓz z D(a, b) − S(a, b; z)) z { a,b } 58
Multidimensional scaling
Preservation of the Handling of Simultaneous coloctive distribution Robustness Scalability vicualization large sets of solutiona range Simplicity 59
Prosections
Presenation of the Handling of Simultaneous coloctive distribution Robustness Scalability visualization large sets relation of solutions range & Simplicity x X
Prosections
• Visualize only part of the objective space • Dimensionality reduction by projection of solutions in a section • Need to choose prosection plane, angle and section width After prosection 60
62
Other (newer) methods
• Tetrahedron coordinates model [5] • Distance-based and dominance-based mappings [11] •  Aggregation trees [12] ・ Trade-off region maps [28] •  Treemaps [37] • MoGrams [32] •  Polar plots [15] ・ Level diagrams with asymmetric norm [7] ・ Visualization following Shneiderman mantra [19] [More on the newer methods TBA] 63
Empirical attainment function
Goal-attainment • Approximation set A • A point in the objective space z is attained by A when z is weakly dominated by at least one solution from A Visualizing EAF values and differences
Empirical attainment function
EAF values [14]
• Algorithm A, approximation sets A1, A2, . . . , Ar • EAF of z is the frequency of attaining z by A 1 , A 2 , . . . , A r ・Summary (or k%-) attainment surfaces 65
Visualization of 3-D EAF
Need to compute and visualize a large number (over 10 000) of cuboids
Exact case
・EAF values: Slicing [2] • EAF differences: Slicing, Maximum intensity projection [38, 2]
Approximated case
•  EAF values: Slicing, Direct volume rendering [9, 2] • EAF differences: Slicing, Maximum intensity projection, Direct volume rendering
Empirical attainment function
Differences in EAF values [22]
• Algorithm A, approximation sets A1, A2, . . . , Ar • Algorithm B, approximation sets B1, B2, . . . , Br • Visualize differences between EAF values
Benchmark approximation sets
Sets of approximation sets
• 5 linear approximation sets with a uniform distribution of solutions (100 solutions in each) • 5 spherical approximation sets with a nonuniform distribution of solutions (100 solutions in each) 66 67
Exact 3-D EAF values and differences
Slicing
・ Visualize cuboids intersecting the slicing plane ・ Need to choose coordinate and angle
Exact 3-D EAF differences
Maximum intensity projection • Volume rendering method for spatial data represented by voxels ・ Simple and efficient ・ No sense of depth, cannot distinguish between front and back
Exact 3-D EAF values and differences
Slicing at φ = 45° at φ = 45° Sph-Lin at φ = 45° 70 69
Exact 3-D EAF differences
Maximum intensity projection • Suitable for visualizing EAF differences (focus on large differences) ・ Sorting w.r.t. EAF differences (smaller to larger) • Plot on top of previous ones 71
The approximated case
Discretization into voxels ・ Discretization of cuboids •  Discretization from the space of EAF values/differences Slicing 73
Approximated 3-D EAF values and differences
Direct volume rendering
• Volume rendering method for spatial data represented by voxels • A transfer function assigns color and opacity to voxel values ・ Enables to see “inside the volume” ・ Requires the definition of the transfer function
Approximated 3-D EAF differences
Maximum intensity projection • Plots produced using Voreen [25, 34] • Some loss of information
Approximated 3-D EAF differences
Direct volume rendering of Lin-Sph 1/5 2/5 3/5 4/5 5/5 1/5 and 5/5 74 75
Approximated 3-D EAF differences
Direct volume rendering of Sph-Lin
77 1/5 and 5/5 78
Summary – Visualization of approximation sets
General methods • Scatter plot matrix • Bubble chart
• Parallel coordinates • Heatmaps • Sammon mapping • Neuroscale •  Self-organizing maps • Principal component analysis • Isomap
Approximated 3-D EAF values
Direct volume rendering of Sph
Summary
• Two-stage mapping • Level diagrams • Hyper-radial visualization • Pareto shells • Seriated heatmaps •  Multidimensional scaling • Prosections
Specific methods
• Distance and distribution charts • Interactive decision maps • Hyper-space diagonal counting
Summary – Visualization of EAFs
Summary
Approximated 3-D case EAF values Exact 3-D case EAF values • Visualization in multiobjective optimization needed for various purposes • Slicing • Slicing •  Direct volume rendering • General methods fail to address the peculiarities of approximation set visualization EAF differences EAF differences • Slicing • Customized methods give more information and are currently gaining attentions ・Maximum intensity projection • Slicing • Maximum intensity projection •  Direct volume rendering The authors acknowledge the financial support from the Slovenian Research Agency (research core funding No. P2-0209 and project No. Z2-8177 Incorporating real-world problems into the benchmarking of multiobjective optimizers). This work is part of a project that has received funding from the European Union's Horizon 2020 research and innovation program under grant agreement No. 692286. SYNERGY Synergy for Smart Multi-Objective Optimization www.synergy-twinning.eu 80 81 82 [1] T. Tušar and B. Filipič. Visualization of Pareto front approximations in evolutionary multiobjective optimization: A critical review and the prosection method. IEEE Transactions on Evolutionary Computation , 19(2):225-245, 2015. [2]   T. Tušar and B. Filipič. Visualizing exact and approximated 3D empirical attainment functions. Mathematical Problems in Engineering, Article ID 569346, 18 pages, 2014. 83 [6] X. Blasco, J. M. Herrero, J. Sanchis, and M. Martínez. A new graphical visualization of n-dimensional Pareto front for decision-making in multiobjective optimization. Information Sciences, 178(20):3908–3924, 2008. [7] X. Blasco, G. Reynoso-Mezab, E. A. Sanchez Perez, and J. V. Sanchez Perez. Asymmetric distances to improve n-dimensional Pareto fronts graphical analysis. Information Sciences, 340-341:228–249, 2016. [8] P.-W. Chiu and C. Bloebaum. Hyper-radial visualization (HRV) method with range-based preferences for multi-objective decision making. Structural and Multidisciplinary Optimization, 40(1–6):97–115, 2010. [3] G. Agrawal, C. L. Bloebaum, and K. Lewis. Intuitive design selection using visualized n-dimensional Pareto frontier. American Institute of Aeronautics and Astronautics, 2005. [4]   K. H. Ang, G. Chong, and Y. Li. Visualization technique for analyzing nondominated set comparison. SEAL ’02, pages 36–40, 2002. [5]   X. Bi and B. Li. The visualization decision-making model of four objectives based on the balance of space vector. IHMSC 2012, pages 365–368, 2014. 84 [9]   K. Engel, M. Hadwiger, J. M. Kniss, C. Rezk-Salama, and D. Weiskopf. Real-time Volume Graphics. A. K. Peters, Natick, MA, USA, 2006. [10] R. M. Everson and J. E. Fieldsend. Multi-class ROC analysis from a multi-objective optimisation perspective. Pattern Recognition Letters, 27(8):918–927, 2006. [11]  J. E. Fieldsend and R. M. Everson. Visualising high-dimensional Pareto relationships in two-dimensional scatterplots. EMO 2013, pages 558–572, 2013. 85 References V [12]  A. R. R. de Freitas, P. J. Fleming, and F. G. Guimaraes. Aggregation trees for visualization and dimension reduction in many-objective optimization. Information Sciences, 298:288–314, 2015. [13] S. Greco, K. Klamroth, J. D. Knowles, and G. Rudolph. Understanding complexity in multiobjective optimization (Dagstuhl seminar 15031). Dagstuhl Reports, pages 96–163, 2015. [14] V. D. Grunert da Fonseca, C. M. Fonseca, and A. O. Hall. Inferential performance assessment of stochastic optimisers and the attainment function. EMO 2001, pages 213–225, 2001. 87 [18] T. Kohonen. Self-Organizing Maps. Springer Series in Information Sciences, 2001. [19]  R. H. Koochaksaraei, R. Enayatifar, and F. G. Guimaraes. A new visualization tool in many-objective optimization problems. HAIS 2016, pages 213–224, 2016. [20]  M. Köppen and K. Yoshida. Visualization of Pareto-sets in evolutionary multi-objective optimization. HIS 2007, pages 156–161, 2007. [15]  Z. He and G. G. Yen. Visualization and performance metric in many-objective optimization. IEEE Transactions on Evolutionary Computation, 20(3):386–402, 2016. [16]  P. E. Hoffman, G. Grinstein, K. Marx, I. Grosse, and E. Stanley. DNA visual and analytic data mining. Conference on Visualization, pages 437–441, 1997. [17]  A. Inselberg. Parallel Coordinates: Visual Multidimensional Geometry and its Applications. Springer, New York, NY, USA, 2009. 88 [21]  F. Kudo and T. Yoshikawa. Knowledge extraction in multi-objective optimization problem based on visualization of Pareto solutions. CEC 2012, 6 pages, 2012. [22]  M. López-Ibáñez, L. Paquete, and T. Stützle. Exploratory analysis of stochastic local search algorithms in biobjective optimization. Experimental Methods for the Analysis of Optimization Algorithms, pages 209–222, 2010. [23] A. V. Lotov, V. A. Bushenkov, and G. K. Kamenev. Interactive Decision Maps: Approximation and Visualization of Pareto Frontier. Kluwer Academic Publishers, Boston, MA, USA, 2004. 89 [24]  D. Lowe and M. E. Tipping Feed-forward neural networks and topographic mappings for exploratory data analysis. Neural Computing & Applications, 4(2):83–95, 1996. [27]  S. Obayashi and D. Sasaki. Visualization and data mining of Pareto solutions using self-organizing map. EMO 2003, pages 796–809, 2003. [28]  R. L. Pinheiro, D. Landa-Silva, and J. Atkin. Analysis of objectives relationships in multiobjective problems using trade-off region maps. GECCO 2015, pages 735–742, 2015. [25]  J. Meyer-Spradow, T. Ropinski, J. Mensmann, and K. H. Hinrichs. Voreen: A rapid-prototyping environment for ray-casting-based volume visualizations. IEEE Computer Graphics and Applications, 29(6):6–13, 2009. [29]  A. Pryke, S. Mostaghim, and A. Nazemi. Heatmap visualisation of population based multi objective algorithms. EMO 2007, pages 361–375, 2007. [26] K. Miettinen. Survey of methods to visualize alternatives in multiple criteria decision making problems. OR Spectrum, 36(1):3–37, 2014. [33] J. Valdes and A. Barton. Visualizing high dimensional objective spaces for multiobjective optimization: A virtual reality approach. CEC 2007, pages 4199--4206), 2007. [30] J. W. Sammon. A nonlinear mapping for data structure analysis. IEEE Transactions on Computers, C-18(5):401–409, 1969. [34] Voreen, Volume rendering engine. http://www.voreen.org/ [31]  J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323, 2000. [35]  D. J. Walker, R. M. Everson, and J. E. Fieldsend. Visualisation and ordering of many-objective populations. CEC 2010, 8 pages, 2010. [32]  K. Trawinski, M. Chica, D. P. Pancho, S. Damas, and O. Cordon. moGrams: A network-based methodology for visualizing the set of non-dominated solutions in multiobjective optimization. CoRR abs/1511.08178, 2015. [36]  D. J. Walker, R. M. Everson, and J. E. Fieldsend. Visualizing mutually nondominating solution sets in many-objective optimization. IEEE Transactions on Evolutionary Computation , 17(2):165–184, 2013. 92 91 94 93 [37]  D. J. Walker. Visualising multi-objective populations with treemaps. GECCO 2015, pages 963–970, 2015. [38] J. W. Wallis, T. R. Miller, C. A. Lerner, and E. C. Kleerup. Three-dimensional display in nuclear medicine. IEEE Transactions on Medical Imaging, 8(4):297–230, 1989. [39]  M. Yamamoto, T. Yoshikawa, and T. Furuhashi. Study on effect of MOGA with interactive island model using visualization. CEC 2010, 6 pages, 2010. 95