CISUC - Clusters of non-dominated solutions in multiobjective combinatorial optimization
CISUC

Clusters of non-dominated solutions in multiobjective combinatorial optimization

Authors

Abstract

This paper presents an analysis on the level of clustering of approximate non-dominated solutions for several instances of the Biobjective Travelling Salesman Problem and the Biobjective Quadratic Assignment Problem. The sets of approximate non-dominated solutions are identified by high performing stochastic local search algorithms. A cluster is here defined as a set of non-dominated solutions such that for any solution of the set there is at least one other that is at a maximum distance k for a given neighborhood function. Of particular interest is to find k for which all approximate non-dominated solutions are in a single cluster. The results obtained from this analysis indicate that the degree of clustering depends strongly on the problem but also on the type of instances of each problem. These insights also suggest that different general-purpose search strategies should be used for the two problems and also for different instance features.

Subject

Multiobjective Optimization

Book Chapter

Multiobjective Programming and Goal Programming: Theoretical Results and Practical Applications, Springer Verlag, January 2009

Cited by

Year 2015 : 1 citations

 A feature-based performance analysis in evolutionary multiobjective optimization
A Liefooghe, S Verel, F Daolio, H Aguirre
Evolutionary Multicriterion Optimization, 2015

Year 2014 : 1 citations

 Sebastien Verel, Arnaud Liefooghe, Jeremie Humeau, Laetitia Jourdan, Clarisse Dhaenens, On the Effect of Connectedness for Biobjective Multiple and Long Path Problems,LION 5

Year 2012 : 1 citations

 S Verel, A Liefooghe, L Jourdanâ?¦, On the structure of multiobjective combinatorial search space:< i> MNK-landscapes with correlated objectives, European Journal of Operations Research, 2012

Year 2011 : 7 citations

 S Verel, A Liefooghe, L Jourdanâ?¦, Analyzing the effect of objective correlation on the efficient set of MNK-landscapes, Learning and Intelligent …, 2011

 J Gorski, K Klamroth, S Ruzika, Connectedness of efficient solutions in multiple objective combinatorial optimization, Journal of optimization theory and …, 2011

 S Verel, A Liefooghe, L Jourdanâ?¦, Pareto local optima of multiobjective NK-landscapes with correlated objectives, Evolutionary Computation …, 2011

 J. Gorski, K. Klamroth, S. Ruzika, Connectedness of Efficient Solutions in Multiple Objective Combinatorial Optimization, Journal of Optimization Theory and Applications, 150, 3, 475-497, 2011.

 Sébastien Verel, Arnaud Liefooghe, Laetitia Jourdan and Clarisse Dhaenens, Pareto Local Optima of Multiobjective NK-Landscapes with Correlated Objectives, 11th European Conference on Evolutionary Computation in Combinatorial Optimisation, LNCS 6622, pp 226-237, 2011.

 Sébastien Vérel, Arnaud Liefooghe, Laetitia Jourdan, Clarisse Dhaenens: Analyzing the Effect of Objective Correlation on the Efficient Set of MNK-Landscapes. LION 2011: 116-130

 Sébastien Vérel, Arnaud Liefooghe, Jérémie Humeau, Laetitia Jourdan, Clarisse Dhaenens: On the Effect of Connectedness for Biobjective Multiple and Long Path Problems. LION 2011: 31-45

Year 2010 : 5 citations

 T Lust, J Teghem, Two-phase Pareto local search for the biobjective traveling salesman problem, Journal of Heuristics, 2010

 J Gorski, Multiple objective optimization and implications for single objective optimization, Publication/NA, 2010

 T Lust, New metaheuristics for solving MOCO problems: application to the knapsack problem, the traveling salesman problem and IMRT optimization, Publication/NA, 2010

 J. Gorski, Multiple Objective Optimization and Implications for Single Objective Optimization, PhD thesis, University of Wuppertal, Germany, 2010.

 T. Lust, J. Teghem, Two-phase Pareto local search for the biobjective traveling salesman problem, Journal of Heuristics, 16(3), 475-510, 2010.

Year 2009 : 2 citations

 J Dubois-Lacoste, A study of Pareto and two-phase local search algorithms for biobjective permutation flowshop scheduling, Master's thesis, IRIDIA, Université Libre de …, 2009

 T. Lust,: New metaheuristics for solving MOCO problems: application to the knapsack, traveling salesman problems and IMRT optimization. PhD Thesis, University of Mons, Belgium, 2009.

Year 2006 : 1 citations

 J Gorski, K Klamroth, S Ruzika, Connectedness of efficient solutions in multiple objective combinatorial optimization, Publication/NA, 2006

Year 1999 : 1 citations

 CAC Coello, List of references on evolutionary multiobjective optimization, Laboratorio Nacional de Informática Avanzada, …, 1999