On set-based local search for multiobjective combinatorial optimization

Matthieu Basseur (1) , Adrien Goëffon (1) , Arnaud Liefooghe (2, 3) , Sébastien Verel (2, 4)

1 LERIA - Laboratoire d'Etudes et de Recherche en Informatique d'Angers
2 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
3 LIFL - Laboratoire d'Informatique Fondamentale de Lille
4 Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Groupe SCOBI

In this paper, we formalize a multiobjective local search paradigm by combining set-based multiobjective optimization and neighborhood-based search principles. Approximating the Pareto set of a multiobjective optimization problem has been recently defined as a set problem, in which the search space is made of all feasible solution-sets. We here introduce a general set-based local search algorithm, explicitly based on a set-domain search space, evaluation function, and neighborhood relation. Different classes of set-domain neighborhood structures are proposed, each one leading to a different set-based local search variant. The corresponding methodology generalizes and unifies a large number of existing approaches for multiobjective optimization. Preliminary experiments on multiobjective NK-landscapes with objective correlation validates the ability of the set-based local search principles. Moreover, our investigations shed the light to further research on the efficient exploration of large-size set-domain neighborhood structures.

Mots clés: Multiobjective optimization; Set-based multiobjective search; Local search; Hypervolume; Set-domain neighborhood

Domaines: Recherche opérationnelle [math.OC]

Matthieu Basseur, Adrien Goëffon, Arnaud Liefooghe, Sébastien Verel. On set-based local search for multiobjective combinatorial optimization. GECCO 2013 - Genetic and Evolutionary Computation Conference, Jun 2013, Amsterdam, Netherlands. pp.471-478. ⟨hal-00805166⟩