  In multiobjective combinatorial optimization, there exists two main classes
of metaheuristics, based either on multiple aggregations, or on a dominance
relation. As in the single objective case, the structure of the search space
can explain the difficulty for multiobjective metaheuristics, and guide the
design of such methods. In this work we analyze the properties of
multiobjective combinatorial search spaces. In particular, we focus on the
features related the efficient set, and we pay a particular attention to the
correlation between objectives. Few benchmark takes such objective correlation
into account. Here, we define a general method to design multiobjective
problems with correlation. As an example, we extend the well-known
multiobjective NK-landscapes. By measuring different properties of the search
space, we show the importance of considering the objective correlation on the
design of metaheuristics.
