Multiobjective Optimization

We give an introduction to nonlinear multiobjective optimization by covering some basic concepts as well as outlines of some methods. Because Pareto optimal solutions cannot be ordered completely, we need extra preference information coming from a decision maker to be able to select the most preferred solution for a problem involving multiple conflicting objectives. Multiobjective optimization methods are often classified according to the role of a decision maker in the solution process. In this chapter, we concentrate on noninteractive methods where the decision maker either is not involved or specifies preference information before or after the actual solution process. In other words, the decision maker is not assumed to devote too much time in the solution process.

We give an overview of interactive methods developed for solving nonlinear multiobjective optimization problems. In interactive methods, a decision maker plays an important part and the idea is to support her/him in the search for the most preferred solution. In interactive methods, steps of an iterative solution algorithm are repeated and the decision maker progressively provides preference information so that the most preferred solution can be found. We identify three types of specifying preference information in interactive methods and give some examples of methods representing each type. The types are methods based on trade-off information, reference points and classification of objective functions.

In its current state, evolutionary multiobjective optimization (EMO) is an established field of research and application with more than 150 PhD theses, more than ten dedicated texts and edited books, commercial softwares and numerous freely downloadable codes, a biannual conference series running successfully since 2001, special sessions and workshops held at all major evolutionary computing conferences, and full-time researchers from universities and industries from all around the globe. In this chapter, we provide a brief introduction to EMO principles, illustrate some EMO algorithms with simulated results, and outline the current research and application potential of EMO. For solving multiobjective optimization problems, EMO procedures attempt to find a set of well-distributed Pareto-optimal points, so that an idea of the extent and shape of the Pareto-optimal front can be obtained. Although this task was the early motivation of EMO research, EMO principles are now being found to be useful in various other problem solving tasks, enabling one to treat problems naturally as they are. One of the major current research thrusts is to combine EMO procedures with other multiple criterion decision making (MCDM) () tools so as to develop hybrid and interactive multiobjective optimization algorithms for finding a set of trade-off optimal solutions and then choose a preferred solution for implementation. This chapter provides the background of EMO principles and their potential to launch such collaborative studies with MCDM researchers in the coming years.

In this chapter, we present a new interactive procedure for multiobjective optimization, which is based on the use of a set of value functions as a preference model built by an ordinal regression method. The procedure is composed of two alternating stages. In the first stage, a representative sample of solutions from the Pareto optimal set (or from its approximation) is generated. In the second stage, the Decision Maker (DM) is asked to make pairwise comparisons of some solutions from the generated sample. Besides pairwise comparisons, the DM may compare selected pairs from the viewpoint of the intensity of preference, both comprehensively and with respect to a single criterion. This preference information is used to build a preference model composed of all general additive value functions compatible with the obtained information. The set of compatible value functions is then applied on the whole Pareto optimal set, which results in possible and necessary rankings of Pareto optimal solutions. These rankings are used to select a new sample of solutions, which is presented to the DM, and the procedure cycles until a satisfactory solution is selected from the sample or the DM comes to conclusion that there is no satisfactory solution for the current problem setting. Construction of the set of compatible value functions is done using ordinal regression methods called UTA\(^{\mbox{\scriptsize GMS}}\) and GRIP. These two methods generalize UTA-like methods and they are competitive to AHP and MACBETH methods. The interactive procedure will be illustrated through an example.

In this chapter, we present a new method for interactive multiobjective optimization, which is based on application of a logical preference model built using the Dominance-based Rough Set Approach (DRSA). The method is composed of two main stages that alternate in an interactive procedure. In the first stage, a sample of solutions from the Pareto optimal set (or from its approximation) is generated. In the second stage, the Decision Maker (DM) indicates relatively good solutions in the generated sample. From this information, a preference model expressed in terms of “if ..., then ...” decision rules is induced using DRSA. These rules define some new constraints which can be added to original constraints of the problem, cutting-off non-interesting solutions from the currently considered Pareto optimal set. A new sample of solutions is generated in the next iteration from the reduced Pareto optimal set. The interaction continues until the DM finds a satisfactory solution in the generated sample. This procedure permits a progressive exploration of the Pareto optimal set in zones which are interesting from the point of view of DM’s preferences. The “driving model” of this exploration is a set of user-friendly decision rules, such as “if the value of objective i ₁ is not smaller than \(\alpha_{i_1}\) and the value of objective i ₂ is not smaller than \(\alpha_{i_2}\), then the solution is good”. The sampling of the reduced Pareto optimal set becomes finer with the advancement of the procedure and, moreover, a return to previously abandoned zones is possible. Another feature of the method is the possibility of learning about relationships between values of objective functions in the currently considered zone of the Pareto optimal set. These relationships are expressed by DRSA association rules, such as “if objective j ₁ is not greater than \(\alpha_{j_1}\) and objective j ₂ is not greater than \(\alpha_{j_2}\), then objective j ₃ is not smaller than \(\beta_{j_3}\) and objective j ₄ is not smaller than \(\beta_{j_4}\)”.

Evolutionary multiobjective optimization usually attempts to find a good approximation to the complete Pareto optimal front. However, often the user has at least a vague idea about what kind of solutions might be preferred. If such information is available, it can be used to focus the search, yielding a more fine-grained approximation of the most relevant (from a user’s perspective) areas of the Pareto optimal front and/or reducing computation time. This chapter surveys the literature on incorporating partial user preference information in evolutionary multiobjective optimization.

This chapter describes various approaches to the use of evolutionary algorithms and other metaheuristics in interactive multiobjective optimization. We distinguish the traditional approach to interactive analysis with the use of single objective metaheuristics, the semi-a posteriori approach with interactive selection from a set of solutions generated by a multiobjective metaheuristic, and specialized interactive multiobjective metaheuristics in which the DM’s preferences are interactively expressed during the run of the method. We analyze properties of each of the approaches and give examples from the literature.

In this paper we describe various visualization techniques which have been used or which might be useful in the multiple objective decision making framework. Several of the ideas originate from statistics, especially multivariate statistics. Some techniques are simply for illustrating snapshots of a single solution or a set of solutions. Others are used as an essential part of the human-computer interface.

We describe techniques for visualizing the Pareto optimal set that can be used if the multiobjective optimization problem considered has more than two objective functions. The techniques discussed can be applied in the framework of both MCDM and EMO approaches. First, lessons learned from methods developed for biobjective problems are considered. Then, visualization techniques for convex multiobjective optimization problems based on a polyhedral approximation of the Pareto optimal set are discussed. Finally, some visualization techniques are considered that use a pointwise approximation of the Pareto optimal set.

This chapter presents a number of illustrative case studies of a wide range of applications of multiobjective optimization methods, in areas ranging from engineering design to medical treatments. The methods used include both conventional mathematical programming and evolutionary optimization, and in one case an integration of the two approaches. Although not a comprehensive review, the case studies provide evidence of the extent of the potential for using classical and modern multiobjective optimization in practice, and opens many opportunities for further research.

This chapter presents a general overview of parallel approaches for multiobjective optimization. For this purpose, we propose a taxonomy for parallel metaheuristics and exact methods. This chapter covers the design aspect of the algorithms as well as the implementation aspects on different parallel and distributed architectures.

This chapter reviews methods for the assessment and comparison of Pareto set approximations. Existing set quality measures from the literature are critically evaluated based on a number of orthogonal criteria, including invariance to scaling, monotonicity and computational effort. Statistical aspects of quality assessment are also considered in the chapter. Three main methods for the statistical treatment of Pareto set approximations deriving from stochastic generating methods are reviewed. The dominance ranking method is a generalization to partially-ordered sets of a standard non-parametric statistical test, allowing collections of Pareto set approximations from two or more stochastic optimizers to be directly compared statistically. The quality indicator method — the dominant method in the literature — maps each Pareto set approximation to a number, and performs statistics on the resulting distribution(s) of numbers. The attainment function method estimates the probability of attaining each goal in the objective space, and looks for significant differences between these probability density functions for different optimizers. All three methods are valid approaches to quality assessment, but give different information. We explain the scope and drawbacks of each approach and also consider some more advanced topics, including multiple testing issues, and using combinations of indicators. The chapter should be of interest to anyone concerned with generating and analysing Pareto set approximations.

Learning is inherently connected with Interactive Multiobjective Optimization (IMO), therefore, a systematic analysis of IMO from the learning perspective is worthwhile. After an introduction to the nature and the interest of learning within IMO, we consider two complementary aspects of learning: individual learning, i.e., what the decision maker can learn, and model or machine learning, i.e., what the formal model can learn in the course of an IMO procedure. Finally, we discuss how one might investigate learning experimentally, in order to understand how to better support decision makers. Experiments involving a human decision maker or a virtual decision maker are considered.

Many important topics in multiobjective optimization and decision making have been studied in this book so far. In this chapter, we wish to discuss some new trends and challenges which the field is facing. For brevity, we here concentrate on three main issues: new problem areas in which multiobjective optimization can be of use, new procedures and algorithms to make efficient and useful applications of multiobjective optimization tools and, finally, new interesting and practically usable optimality concepts. Some research has already been started and some such topics are also mentioned here to encourage further research. Some other topics are just ideas and deserve further attention in the near future.