Archivers for the Set of Approximate Solutions on Multi-objective Optimization

11:30 am - 11:50 am 23 Wednesday


Set Oriented Numerics

In a variety of applications in industry and finance one is faced with the problem that several objectives have to be optimized concurrently leading to a multi-objective optimization problem(MOP). A common goal for such problems is to identify the set of optimal solutions (the so-called Pareto set, denote by \(P_Q\)) and its image in objective space, the Pareto front. Hereby optimality is typically defined on the concept of dominance. Moreover, in certain situations it may be beneficial for the decision maker (DM) to consider in addition to the optimal solutions also nearly optimal ones, which are alternatively called approximate solutions or \(\epsilon\)-efficient solutions. The reason for this is that by this the number of valid options for the current setting may increase (note that if two points \(x\) and \(y\) are near in objective space,i.e., if \(F(x)\approx F(y)\), this does not have to hold in parameter space. In fact, \(x\) and \(y\) can differ significantly depending on properties of \(F\) such as (quasi-) periodicities or symmetries).

All of the works dealing with approximate solutions in multi-objective optimization are based on the concept of \(\epsilon\)-dominance which has been introduced in [3, 9]. \(\epsilon\)-dominance or \(\epsilon\)-efficiency has been studied and used by many researchers, e.g. to allow (or tolerate) nearly optimal solutions [3], [9], to approximate the set of optimal solutions \(P_Q\)[4], or in order to discretize this set [2, 7, 8].\(\epsilon\)-efficient solutions have also been used to tackle a variety of real world problems including portfolio selection problems [10], a location problem [1], or a minimal cost flow problem [4].

To tap the full potential of the additional consideration of approximate solutions \((P_{Q,\epsilon})\) against the ‘sole’ consideration of the optimal solutions it is required to maintain a representation of the entire set \(P_{Q,\epsilon}\). The challenge in this case is that for the consideration of a problem with \(n\) parameters and \(k\) objectives, the set \(P_{Q,\epsilon}\) forms an \(n\)-dimensional object while \(P_Q\) is under some mild regularity assumptions on \(F\) ‘only’ \((k-1)\)-dimensional (\(n>>k\) can be assumed). Hence, for the effective extension from \(P_Q\) to \(P_{Q,\epsilon}\) as the basis for the decision making process a suitable discretization of the latter set is essential.

In this work, we design and investigate archiving strategies aiming for the approximation of this set. We will show that the first archiving strategy converges under certain assumptions on the generator in the probabilistic sense toward \(P_{Q,\epsilon}\). We present and investigate further a possible discretization strategies to maintain a finite size representation of \(P_{Q,\epsilon}\) in the limit in both parameter and objective space. We also give bounds on the approximation quality and on the cardinality of the limit solution set. Finally, we make a comparative study on some test problems in order to visualize the effect of all strategies. Preliminary studies of this work can be found in [5, 6].


[1] R. Blanquero and E. Carrizosa. A. d.c. biobjective location model.Journal of Global Optimization,23(2):569–580, 2002.

[2] M. Laumanns, L. Thiele, K. Deb, and E. Zitzler. Combining convergence and diversity in evolutionarymultiobjective optimization.Evolutionary Computation, 10(3):263–282, 2002.

[3] P. Loridan.-solutions in vector minimization problems.Journal of Optimization, Theory and Application, 42:265–276, 1984.

[4] G. Ruhe and B. Fruhwirt.-optimality for bicriteria programs and its application to minimum cost flows.Computing, 44:21–34, 1990.

[5] O. Schütze, C. A. Coello Coello, and E.-G. Talbi. Approximating the-efficient set of an MOP withstochastic search algorithms. In A. Gelbukh and A. F. Kuri Morales, editors,Mexican InternationalConference on Artificial Intelligence (MICAI-2007), pages 128–138. Springer-Verlag Berlin Heidelberg,2007.

[6] O. Schütze, C. A. Coello Coello, E. Tantar, and E.-G. Talbi. Computing finite size representations of the set of approximate solutions of an mop with stochastic search algorithms. InGECCO ’08:Proceedings of the 10th annual conference on Genetic and evolutionary computation, pages 713–720,New York, NY, USA, 2008. ACM.

[7] O. Schütze, M. Laumanns, C. A. Coello Coello, M. Dellnitz, and E.-G. Talbi. Convergence of stochastic search algorithms to finite size Pareto set approximations.Journal of Global Optimization, 41(4):559–577, 2008.

[8] O. Schütze, M. Laumanns, E. Tantar, C. A. Coello Coello, and E.-G. Talbi. Computing gap free Pareto front approximations with stochastic search algorithms. To appear in Evolutionary Computation,2007.

[9] D. J. White. Epsilon efficiency.Journal of Optimization Theory and Applications, 49(2):319–337,1986.

[10] D. J. White. Epsilon-dominating solutions in mean-variance portfolio analysis.European Journal ofOperational Research, 105(3):457–466, 1998.

Carlos Hernandez