Report

High-order Pareto frontier approximation and visualization: 30 years of experience and new trends Abstract of the paper at MCDM 2011 Alexander V. Lotov Dorodnicyn Computing Center of Russian Academy of Sciences and Lomonosov Moscow State University Plan of the talk 1. Few words concerning Pareto frontier visualization 2. Interactive Decision Maps (IDM) technique for visualization of the high-order Pareto frontier 3. Few words about application of IDM in the convex case 4. IDM in the non-linear non-convex case: using of hybrid (classic&genetic) optimization 5. Application of IDM in non-linear non-convex problems: a) study of the cooling equipment for continuous steel casting b) designing the release rules for the Baikal Lake Basin c) development of efficient strategies for AIDS treatment 6. New studies: linearization of response surface, identification of math models This job was carried out by a large group of specialists and students that includes V.Bushenkov, O.Chernykh, G.Kamenev, D.Gusev, L.Bourmistrova, R. Efremov, V.Berezkin, A.Pospelov, and many others. Few words concerning Pareto frontier visualization Notation Let X be the feasible set in decision space, z=(z1, z2,…, zm)= f(x) be the criteria vector, where f(x) is the vector of objective functions. Then, Z=f(X) = feasible set in objective space R m Pareto domination (minimization case) z' z' ' z'i z' 'i , i 1,2,...,m; z' z' ' Non-dominated (efficient, Pareto) frontier P(Z ) z Z : z' Z : z' z emptyset Feasible set in objective space z2 Z=f(X) z1 Non-dominated (Pareto) frontier is visible z2 Z=f(X) z1 Pareto frontier methods (a posteriori preference) methods Pareto frontier methods consist in 1) approximating the Pareto frontier and 2) informing the Decision Maker about it. In contrast to preference-oriented methods, Pareto frontier methods do not require the DM to answer multiple questions concerning his/her preferences, but only inform the DM. Two basic ways for informing the DM about the Pareto frontier • By providing a list of the objective (criterion) points that belong to the Pareto frontier • By visualization of the Pareto frontier Selecting from a large list of objective points (more than one or two dozens) with more than two criteria turned out to be too complicated for a human being. See, for example, the paper • Larichev O. Cognitive Validity in Design of Decision-Aiding Techniques. Journal of Multi-Criteria Decision Analysis, 1992, v.1, n 3. Visualization of the Paretoo frontier can help ”A picture is worth a thousand words” Prof. A.Wierzbicki proved that a picture is worth 10 thousand words Tradeoff information is important for DM z2 f(x*) f(x1) f(x2) z1 We develop the Pareto frontier visualization methods for the high-order problems (m > 2) Two problems must be solved • How to approximate the Pareto frontier? • How to inform the stakeholders about the Pareto frontier? Interactive Decision Maps (IDM) technique solves these problems in highorder MOO problems. Its generic ideas were formulated in 1980 (Lotov, A.V. On the concept of the GRS and its constructing for linear controlled systems. Sov. Phys. Dokl., American Istitute of Physics, 1980, 25(2), 82–84) The IDM technique is based on approximating the feasible objective set Z or its Edgeworth-Pareto Hull (EPH), that is Zp Z m R Sometimes the EPH is called the Free Disposal Hull. It holds P(Z p ) P(Z ) z2 P(Z) f(X) Zp z1 Visualization by usung the IDM tech In this talk, we restrict with visualization of the EPH. The IDM tech is based on the display of biobjective slices of the EPH. Decision map is a collection of overlapped biobjective slices in the case m=3. If for m>3, the IDM technique displays decision maps interactively. Decision maps can be rearranged, animated, zoomed, etc. by the user. This option is based on the approximating the EPH, which has to be completed in advance. Example of the Pareto frontier display for m=5 in the convex case Another example of the Pareto frontier display for m=5 in the convex case by using the matrix of decision maps Application of the IDM tech: Feasible Goals Method (FGM). It is the IDM-supported goal method, in the framework of which the goal is identified at the Pareto frontier. Objective (criterion) tradeoff information helps the decision maker to identify the preferable nondominated objective point (goal) consciously. It is important that the goal located at the Pareto frontier is feasible. Due to it, the associated decision does exist and can be computed. Application of the IDM in the convex case In the convex case polyhedral approximation of the EPH is used. Method and applications are described in Lotov A.V., Bushenkov V.A., and Kamenev G.K. Interactive Decision Maps. Approximation and Visualization of Pareto Frontier. Kluwer Academic Publishers, 2004. Real-life applications of FGM and its modification (Reasonable Goals Method) in the convex case DSS for Water Quality Planning (Russian Federal Programme “Revival of the Volga River”) Searching for trans-boundary air pollution control strategies (jointly with M.Pohjola and V.Kaitala, Finland) Exploration of pollution abatement cost in the Electricity Sector – Israeli case study (Ministry of National Infrastructures of Israel, D.Soloveichik et al.). Web-based Participatory Decision Support for Integrated River Basin Planning (jointly with J.Dietrich and A.H. Schumann, Germany) Water quality planning in rivers of Cataluña (A.L.Udias Moinelo and R.Efremov, Spain, A.Pospelov, Russia) Academic applications in the convex problems • • • • • Development of smart response strategies related to global climate change Environmentally sound agricultural planning in the Netherlands (jointly with S.Orlovski and P.˚van Walsum from IIASA, Austria) Allocation of sea oil platforms and planning the oil fields development (jointly with R.Efremov, Spain, A.Barron Alcantara, Mexico) E-democracy: web-based participatory decision support (jointly with Efremov R., Rios-Insua D.) Etc. IDM in the non-linear non-convex case The main problems that arise in the non-linear case: 1. non-convexity of the EPH; 2. time-consuming processes of global scalar optimization, i.e. computing the support function may require too much time or may be impossible. Approximation of the non-convex EPH Approximation for visualization The EPH is approximated by the set T* that is the union of the non-negative cones zR m with apexes in a finite number of points z of the set Z=f(X). Collection of such points z is called the approximation base and is denoted by T. Important! Multiple slices of such an approximation can be computed and displayed fairly fast. Visualization example for 8 criteria Approximation of the EPH We concentrated our efforts at the methods for approximating the EPH in MOO problems with criterion functions given by black-box models (say, FEM/FDM modules, or different simulation modules). Thus, the Lipschitz constants are unknown (or may not exist at all) and cannot be used in the methods. Actually, the only feasible operation with the module is variation of its inputs and collecting the related outputs. We have developed hybrid methods for approximating the EPH for black-box modules that include: a) random (Monte Carlo) search; b) adaptive and non-adaptive local simulation-based optimization; c) importance sampling (squeezing the search region); d) semi-genetic algorithms. Statistical tests were developed that provide the basis for the stopping rules. Local simulation-based optimization Simulation provides an opportunity to approximate the gradient of a scalar function. It means that it is possible to use various effective gradient-based methods (for example, methods of conjugated gradients) to find local maximum (or minimum) of a scalar function. These methods can be used for ‘improving’ a random decision x by moving the associated criterion point f(x) in the direction of the Pareto frontier. Two-phase method: combination of random search and local optimization Combination of random search and local optimization is often used in scalar optimization. The simplest methods of this kind are multi-start methods, more complicated methods have been proposed, too. Methods of this kind are known as the two-phase methods. We apply two-phase methods as the basic tool for approximation of the Pareto frontier. In our methods the scalarizing function is not given. Several concepts for adaptive selecting of scalarizing functions were proposed by us. Three-phase method The three-phase methods include squeezing of the search region. The methods for adaptive squeezing were proposed. Plastering (semi-genetic) method Plastering method that has some properties of genetic algorithms (as cross-over and selecting of nondominated decisions) is used at the very end of the approximation process. Approximating the EPH using parallel computing The proposed methods have the form that can be used in parallel computing (clusters, supercomputers, grids, etc.) – it is sufficient to separate simulation and Pareto frontier computing. Even cloud computing can be used since methods are nor sensitive to a partial loss of the results of simulation. Two-platform implementation IDM applications in the non-linear non-convex MOO problems a) Multi-objective study of the cooling equipment in continuous casting of steel The research was carried out jointly with K.Miettinen and several other researchers from University of Jyvaskyla. Criteria J1 is the original single optimization criterion: deviation from the desired surface temperature of the steel strand must be minimized. J2 to J5 are the penalty criteria introduced to describe violation of constraints imposed on : -surface temperature (J2 ); -gradient of surface temperature along the strand (J3); -on the temperature after point z3 (J4); and -on the temperature at point z5 (J5). J2 to J5 were considered in this study. Description of the module FEM/FDM module was developed by researchers from University of Jyvaskyla. Properties of the model: 325 control variables that describe intensity of water application. b) Application of the non-linear IDM in the design of the release rules for the hydro power stations in the Baikal Lake basin (encouraged by the group of Prof. R. Soncini-Sessa from Politecnico di Milano) Scheme of the Baikal Lake basin (cascade of hydropower stations) The problem of release rules design for a hydropower stations cascade Water managers develop some rules, which relate the flow through a dam (release) to the current level of the reservoir. The parameters of the release rules must be specified to satisfy the requirements of the industrial, agricultural and municipal users as well as environmental requirements. The main concept in the design of the release rules The approach is based on direct application of the historical inflow data. Then, any particular release rule can be simulated by using a water flow model combined with historical data on inflow through the time period under study (about 100 years). By this, performance indicators for any particular release rule can be estimated. Optimization criteria are based on deviations from : • Required level of electricity production; • Satisfaction of environmental requirements to water use of Baikal; • Absence of floods; • etc. Thus, the objective values must be minimized. Completed study: Pareto frontier for Irkutsk hydropower station The Baikal Lake basin Irkutsk HPS The decision rule was described by 132 parameters, eight objectives were used. After about one hour of computing at a supercomputer an approximation of the EPH was constructed. Visualization • After a few steps of visual study of the EPH in general, it was decided that four objective must have their minimal values y3=y4=y6=y7=0. • The rest of objectives are: y1 is the volume of water released without producing energy y2 is the violation of the NO FLOOD requirement y5 is the violation of a high requirement on energy production y8 is the violation of the requirement to have the level of the Baikal Lake in a corridor set fixed by government Decision map 1 Decision map 2 Decision map 3 Decision map 4 Decision map 5 Selected objective points • • • • • • y1=0.86, y2=0.00, y5=0.77, y8=0.93 y1=0.77, y2=0.22, y5=0.85, y8=0.84 y1=0.85, y2=0.11, y5=0.42, y8=0.88 y1=0.91, y2=0.00, y5=0.42, y8=0.91 y1=0.92, y2=0.11, y5=0.34, y8=0.90 y1=0.89, y2=0.00, y5=0.33, y8=0.93 Value Path Search for effective strategies for HIV therapy The model • n is the number of healthy lymphocytes of CD4+ type, • I1 is the number of lymphocytes infected by the natural HIV virus, • I2 is the number of lymphocytes infected by the mutated HIV virus, • h is the concentration of drug in blood, • u is the intensity of treatment: 0<u<U Objectives • y1 is the drug application during one year • y2 is the maximal concentration of drug in the body • y3 is the number of infected lymphocytes at the very end of the time-period • y4 is the maximal number of infected lymphocytes during the time-period • y5 is the number of healthy lymphocytes at the very end of the time-period • y6 is the maximal number of healthy lymphocytes during the time-period One of the decision maps One of the Pareto optimal therapy strategies The result of the selected Pareto optimal therapy New developments: linearization of response surface and identification of math models Linearization of response surface in Water Quality Rehabilitation Details described in: A. Castelletti, A. Lotov, R. Soncini-Sessa. Visualization-based multi-criteria improvement of environmental decision-making using linearization of response surfaces. Environmental Modelling and Software, v.25, 2010, pp. 1552-1564. Examples of graphs of error function of parameter λ а) l б) в) l l Our Web site • http://www.ccas.ru/mmes/mmeda/