Interactive Decision Maps

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).

References

^ ^a ^b ^c ^d 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.

[LotovBushenkov2004-1] 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]