Interactive Decision Maps

Last updated June 04, 2021

The Interactive Decision Maps technique of multi-objective optimization is based on approximating the Edgeworth-Pareto Hull (EPH) of the feasible objective set, that is, the feasible objective set broadened by the objective points dominated by it. Alternatively, this set is known as Free Disposal Hull. It is important that the EPH has the same Pareto front as the feasible objective set, but the bi-objective slices of the EPH look much simpler. The frontiers of bi-objective slices of the EPH contain the slices of the Pareto front. It is important that, in contrast to the Pareto front itself, the EPH is usually stable in respect to disturbances of data. The IDM technique applies fast on-line display of bi-objective slices of the EPH approximated in advance.

Since the bi-objective slices of the EPH for two selected objectives are extending (or shrinking) monotonically, while the value of one of the other objectives (the "third" objective) changes monotonically, the frontiers of the slices of the EPH, for which the values only of the "third" objective changes, do not intersect. This is why a figure with superimposed bi-objective slices of the EPH looks like an ordinary topographical map and is named the decision map, too. To study the influence of the other (fourth, fifth, etc.) objectives, one can use animation of the decision maps. Such animation is possible due to the preliminary approximating the EPH. Alternatively, one can study various collections of snap-shots of the animation. Computers can visualize the Pareto front in the form of decision maps for linear and nonlinear decision problems for three to about eight objectives. Computer networks are able to bring, for example, Java applets that display graphs of the Pareto fronts on request. Real-life applications of the IDM technique are described in.^[1]

Illustration of the IDM technique

The above figure represents a gray scale copy of a color computer display for a real-life water quality problem^[1] involving five objectives. The decision map consists of four superimposed bi-objective differently colored slices. A palette shows the relation between the values of the "third" objective and colors. Two scroll-bars are related to the values of the fourth and the fifth objectives.

A movement of a scroll-bar results in a change of the decision map. One can move the slider manually. However, the most effective form of displaying information to the DM is based on an automatic movement of the slider, that is, on a gradual increment (or decrement) in the constraint imposed on the value of an objective. A fast replacement of the decision maps offers the effect of animation. Because any reasonable number of scroll-bars can be located on the display, one can explore the influence of the fourth, the fifth (and maybe even the sixth and the seventh etc.) objectives on the decision map.

Approximating the EPH

The EPH must be approximated in the IDM technique before the decision maps are displayed. Methods for approximating the EPH depend on the convexity properties of the EPH. Approximation methods are typically based either on approximation of the EPH by a convex polyhedral set or on approximation of the EPH by a large but finite number of domination cones in objective space with vertices that are close to the Pareto front. The first form can be applied only in the convex problems, while the second form is universal and can be used in general nonlinear problems.^[1]

Approximation and visualization in the case of convex EPH

The EPH approximated by a polyhedral set is described by a system of a finite number of linear inequalities, which must be constructed by the approximation technique. Mathematical theory of optimal polyhedral approximation of convex bodies was developed during recently, and its results can be applied for developing the effective methods for approximating the EPH.^[1] A large number of bi-objective slices of such approximations can be computed and displayed in the form of a decision map in several seconds.

Point-wise approximation of the Pareto front and its visualization

An EPH approximation by a large but finite number of domination cones can be constructed on the basis of any point-wise approximation of the Pareto front, which can be found by using a broad range of techniques from classic single-objective optimization methods ^[2]^[3] up to modern evolutionary methods^[4] Hybrid methods for approximating the EPH based on combination of classic and evolutionary methods can be used, too.^[5] The bi-objective slices of such approximation can be computed very fast as well. Application of these methods results in decision maps that look fairly understandable if the number of approximating points is sufficiently large.

Search for the preferred decision

In the IDM technique, search for the preferred decision is based on identification of a preferred Pareto optimal objective point (feasible goal). Decision maps help the user to identify the goal directly at a tradeoff curve drawn at the computer display. Then, a Pareto optimal decision associated with the goal is found automatically. Detailed discussion of the Pareto front visualization problems is provided in the paper Visualizing the Pareto Frontier (Lotov and Miettinen, 2008).

Related Research Articles

Pareto efficiency or Pareto optimality is a situation where no individual or preference criterion can be better off without making at least one individual or preference criterion worse off or without any loss thereof. The concept is named after Vilfredo Pareto (1848–1923), Italian civil engineer and economist, who used the concept in his studies of economic efficiency and income distribution. The following three concepts are closely related:

Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. Optimization problems of sorts arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

Multi-disciplinary design optimization (MDO) is a field of engineering that uses optimization methods to solve design problems incorporating a number of disciplines. It is also known as multidisciplinary system design optimization (MSDO).

In mathematics, nonlinear programming (NLP) is the process of solving an optimization problem where some of the constraints or the objective function are nonlinear. An optimization problem is one of calculation of the extrema of an objective function over a set of unknown real variables and conditional to the satisfaction of a system of equalities and inequalities, collectively termed constraints. It is the sub-field of mathematical optimization that deals with problems that are not linear.

Multiple-criteria decision-making (MCDM) or multiple-criteria decision analysis (MCDA) is a sub-discipline of operations research that explicitly evaluates multiple conflicting criteria in decision making. Conflicting criteria are typical in evaluating options: cost or price is usually one of the main criteria, and some measure of quality is typically another criterion, easily in conflict with the cost. In purchasing a car, cost, comfort, safety, and fuel economy may be some of the main criteria we consider – it is unusual that the cheapest car is the most comfortable and the safest one. In portfolio management, managers are interested in getting high returns while simultaneously reducing risks; however, the stocks that have the potential of bringing high returns typically carry high risk of losing money. In a service industry, customer satisfaction and the cost of providing service are fundamental conflicting criteria.

Genetic fuzzy systems are fuzzy systems constructed by using genetic algorithms or genetic programming, which mimic the process of natural evolution, to identify its structure and parameter.

Kalyanmoy Deb is an Indian computer scientist. Since 2013, Deb has held the Herman E. & Ruth J. Koenig Endowed Chair in the Department of Electrical and Computing Engineering at Michigan State University, which was established in 2001. Deb is a Professor at the Department of Computer Science and Engineering and Department of Mechanical Engineering at Michigan State University. Prior to this position, Deb held the positions of Deva Raj Endowed Chair and Gurmukh and Veena Mehta Endowed Chair in the Department of Mechanical Engineering at the Indian Institute of Technology, Kanpur, India.

In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable.

Multi-objective optimization is an area of multiple criteria decision making that is concerned with mathematical optimization problems involving more than one objective function to be optimized simultaneously. Multi-objective optimization has been applied in many fields of science, including engineering, economics and logistics where optimal decisions need to be taken in the presence of trade-offs between two or more conflicting objectives. Minimizing cost while maximizing comfort while buying a car, and maximizing performance whilst minimizing fuel consumption and emission of pollutants of a vehicle are examples of multi-objective optimization problems involving two and three objectives, respectively. In practical problems, there can be more than three objectives.

Fitness approximation aims to approximate the objective or fitness functions in evolutionary optimization by building up machine learning models based on data collected from numerical simulations or physical experiments. The machine learning models for fitness approximation are also known as meta-models or surrogates, and evolutionary optimization based on approximated fitness evaluations are also known as surrogate-assisted evolutionary approximation. Fitness approximation in evolutionary optimization can be seen as a sub-area of data-driven evolutionary optimization.

MULTICUBE is a Seventh Framework Programme (FP7) project aimed to define innovative methods for the design optimization of computer architectures for the embedded system domain.

OptiY is a design environment providing modern optimization strategies and state of the art probabilistic algorithms for uncertainty, reliability, robustness, sensitivity analysis, data-mining and meta-modeling.

In applied mathematics, multimodal optimization deals with optimization tasks that involve finding all or most of the multiple solutions of a problem, as opposed to a single best solution. Evolutionary multimodal optimization is a branch of evolutionary computation, which is closely related to machine learning. Wong provides a short survey, wherein the chapter of Shir and the book of Preuss cover the topic in more detail.

Benson's algorithm, named after Harold Benson, is a method for solving multi-objective linear programming problems and vector linear programs. This works by finding the "efficient extreme points in the outcome set". The primary concept in Benson's algorithm is to evaluate the upper image of the vector optimization problem by cutting planes.

Kaisa Miettinen is a Finnish mathematician and the former vice rector of the University of Jyväskylä in Finland. She is a professor of industrial optimization with the Faculty of Information Technology, University of Jyväskylä, Finland. In addition, she heads the Multiobjective Optimization Group.

In applied mathematics, test functions, known as artificial landscapes, are useful to evaluate characteristics of optimization algorithms, such as:

The MOEA Framework is an open-source evolutionary computation library for Java that specializes in multi-objective optimization. It supports a variety of multiobjective evolutionary algorithms (MOEAs), including genetic algorithms, genetic programming, grammatical evolution, differential evolution, and particle swarm optimization. As a result, it has been used to conduct numerous comparative studies to assess the efficiency, reliability, and controllability of state-of-the-art MOEAs.

MINOS is a Fortran software package for solving linear and nonlinear mathematical optimization problems. MINOS may be used for linear programming, quadratic programming, and more general objective functions and constraints, and for finding a feasible point for a set of linear or nonlinear equalities and inequalities.

Multi-objective linear programming is a subarea of mathematical optimization. A multiple objective linear program (MOLP) is a linear program with more than one objective function. An MOLP is a special case of a vector linear program. Multi-objective linear programming is also a subarea of Multi-objective optimization.

References

1 2 3 4 A. V. Lotov; V. A. Bushenkov; G. K. Kamenev (29 February 2004). Interactive Decision Maps: Approximation and Visualization of Pareto Frontier. Springer. ISBN 978-1-4020-7631-2 . Retrieved 29 May 2012.
↑ Kaisa Miettinen (1999). Nonlinear Multiobjective Optimization. Springer. ISBN 978-0-7923-8278-2 . Retrieved 29 May 2012.
↑ Jürgen Branke; Kalyanmoy Deb; Kaisa Miettinen; Roman Slowinski (21 November 2008). Multiobjective Optimization: Interactive and Evolutionary Approaches. Springer. ISBN 978-3-540-88907-6 . Retrieved 1 November 2012.
↑ Kalyanmoy Deb (23 March 2009). Multi-Objective Optimization Using Evolutionary Algorithms. John Wiley & Sons. ISBN 978-0-470-74361-4 . Retrieved 1 November 2012.
↑ Berezkin, V. E.; Kamenev, G. K.; Lotov, A. V. (2006). "Hybrid adaptive methods for approximating a nonconvex multidimensional Pareto frontier". Computational Mathematics and Mathematical Physics. 46 (11): 1918. Bibcode:2006CMMPh..46.1918B. doi:10.1134/S096554250611008X. S2CID 121051510.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[LotovBushenkov2004-1] 1 2 3 4 A. V. Lotov; V. A. Bushenkov; G. K. Kamenev (29 February 2004). Interactive Decision Maps: Approximation and Visualization of Pareto Frontier. Springer. ISBN 978-1-4020-7631-2 . Retrieved 29 May 2012.

[Miettinen1999-2] Kaisa Miettinen (1999). Nonlinear Multiobjective Optimization. Springer. ISBN 978-0-7923-8278-2 . Retrieved 29 May 2012.

[BrankeDeb2008-3] Jürgen Branke; Kalyanmoy Deb; Kaisa Miettinen; Roman Slowinski (21 November 2008). Multiobjective Optimization: Interactive and Evolutionary Approaches. Springer. ISBN 978-3-540-88907-6 . Retrieved 1 November 2012.

[Deb2009-4] Kalyanmoy Deb (23 March 2009). Multi-Objective Optimization Using Evolutionary Algorithms. John Wiley & Sons. ISBN 978-0-470-74361-4 . Retrieved 1 November 2012.

[BerezkinKamenev2006-5] Berezkin, V. E.; Kamenev, G. K.; Lotov, A. V. (2006). "Hybrid adaptive methods for approximating a nonconvex multidimensional Pareto frontier". Computational Mathematics and Mathematical Physics. 46 (11): 1918. Bibcode:2006CMMPh..46.1918B. doi:10.1134/S096554250611008X. S2CID 121051510.

[1]

[2]

[3]

[4]

[5]