# Impact of diversity on bounded archives for multi-objective local search

Amadeu Almeida Coco, Cyprien Borée, Julien Baste, Laetitia Jourdan, Lucien Mousin

► To cite this version:

Amadeu Almeida Coco, Cyprien Borée, Julien Baste, Laetitia Jourdan, Lucien Mousin. Impact of diversity on bounded archives for multi-objective local search. 25ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Université de Picardie Jules Verne; Laboratoire Modélisation, Information & Systèmes; Société Française de Recherche Opérationnelle et d'Aide à la Décision, Mar 2024, Amiens, France. hal-04778714

HAL Id: hal-04778714

https://hal.science/hal-04778714v1

Submitted on 12 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
Impact of diversity on bounded archives for multi-objective
local search

Amadeu A. Coco¹, Cyprien Borée², Julien Baste¹, Laetitia Jourdan¹, Lucien Mousin¹,²

¹ ORKAD, CRISTAL, UMR 9189, CNRS, Centrale Lille, Université de Lille, Lille, France
{amadeu.almeidacoco, julien.baste, laetitia.jourdan}@univ-lille.fr

² FGES, Lille Catholic University, F-59000, Lille, France
cyprien.boree@tuta.io, lucien.mousin@univ-catholille.fr

**Keywords** : multi-objective optimization, bounded archive, solution diversity, local search

Metaheuristics are widely adopted for addressing Multi-Objective Optimization Problems (MOOP) [1]. Applied in scenarios where traditional optimization techniques are impractical, these approaches have recently seen substantial development [6], resulting in effective and versatile algorithms. Despite their success, challenges persist, including exponential growth in the number of non-dominated solutions and a tendency to disproportionately focus on a subset of the Pareto Front, impacting solution diversity.

This study addresses two critical challenges mentioned in the previous paragraph. To deal with the exponential growth, the use of bounded archives [6] is employed as a strategic mechanism for managing the increasing number of non-dominated solutions. As for the second challenge, an extensive examination of solution diversity algorithms presented in the literature [3, 4] is undertaken. After noting that the existing approaches primarily focus on diversity within the objective space, this work introduces novel methods that address diversity in the solution space, aiming to demonstrate the efficacy of this avenue for enhancing the overall efficiency of metaheuristics tailored for solving MOOP.

A MOOP is described by a set of at least two objective functions, and a set of constraints defines a polytope in the solution space. In a MOOP, given two solutions, $S_1$ and $S_2$, $S_1$ dominates $S_2$ if, for every objective function $f_i(S)$, $f_i(S_1) \le f_i(S_2)$, and there exists at least one objective function $f_j(S)$ such that $f_j(S_1) < f_j(S_2)$. A solution is non-dominated if no other solution dominates it. A solution is deemed Pareto optimal in a MOOP if there is no feasible solution that dominates it. The Pareto front refers to the set of Pareto-optimal points, representing solutions that are non-dominated regarding the defined objectives. In a MOOP, archives, as data structures, manage non-dominated solutions, aiding convergence analysis and Pareto front exploration. Bounded archives, with a set solution limit, are the focus due to their critical role in balancing diverse representation and addressing challenges of exponential solution increase. To better represent the Pareto Front, solutions in an archive must exhibit high diversity. This study aims to advance MOOP metaheuristics by developing novel approaches that effectively enhance solution diversity within bounded archives.

The Adaptive Grid Archiving (AGA) [3] introduces an approach to deal with solution archives in MOOP. Using a grid-based framework, AGA partitions the objective space, categorizing solutions into distinct spatial regions. As the archive reaches capacity, AGA prioritizes preserving non-dominated solutions from less congested areas while removing solutions from densely populated regions, ensuring well-distributed solutions along the Pareto front for enhanced diversity and quality. The Hypervolume Archiving (HA) algorithm [4] adapts the hypervolume metric for bounding archives. When the archive is full, a new non-dominated solution is admitted if it increases the hypervolume more than an existing solution. The hypervolume, in this context, calculates the volume occupied between the non-dominated solutions in the archive and the nadir point, representing the worst values for each objective among Pareto front solutions, assessing diversity and coverage within the archive in MOOP.
Upon examining AGA and HA, two key insights emerge. Firstly, in bounded archives, a new solution $X'$ is admitted at capacity only if it surpasses another solution according to a diversity criterion. This optimizes solution diversity within the algorithmic framework. Secondly, many archiving methods focus solely on the objective space, neglecting the solution space in addressing diversity. For various MOOP, especially in scenarios like cutting-stock problems, where diverse solutions are crucial, archiving algorithms rooted in the solution space become essential for tackling MOOP challenges effectively.

In [3, 4], solution diversity was measured as the Euclidean distance between non-dominated solutions, optimizing when neighbor solutions are maximally distant. However, diversity in the solution space requires a distinct metric, hereafter referred to as the solution metric. This metric is a function quantifying the distance between any two non-dominated solutions, with properties defining (i) indiscernibility; (ii) non-negativity; (iii) symmetry; and (iv) the triangle inequality. In this study, two novel archiving algorithms that address the non-dominated solutions of a Pareto front on the solution space are proposed. When the archive is full, it removes the solution that contributes the least following a solution metric. The two employed solution metrics are the Hamming and Jaccard distances. From now on, those archiving algorithms are referred as Hamming Archiving Algorithm (HAM) and Jaccard Archiving Algorithm (JAC).

The computational experiments use an Intel Xeon CPU W3520 with a 2.67 GHz clock speed, 24 cores, and 8 GB of RAM, operating on Linux. Archiving algorithms are implemented in C++ and compiled with GNU g++ 7.5.0. These methods are tested on the bi-objective Travelling Salesman Problem using the Pareto Local Search Heuristic within the MH-Builder [5], limiting the maximum archive size. The instance set comprises 27 complete graphs with up to 2000 nodes. The results using a ranking analysis with Demšar statistical test [2] show that HAM consistently emerged as the top-performing algorithm on average, except for instances with 500 nodes, where HA outperformed HD. This pattern suggests HAM's superiority in larger instances, typical in real-world applications.

This study explores solution diversity algorithms in bounded archives for multi-objective metaheuristics, focusing on challenges related to non-dominated solution growth and a subset of the Pareto Front. The proposed methodologies (HAM and JAC) prioritize solution space exploration, with HAM notably effective in enhancing diversity, particularly in larger instances. The research underscores HAM's potential for improving MOOP-solving metaheuristics efficiently. Future research should include extensive testing of HAM and JAC across diverse multi-objective problems and their integration with other metaheuristics.

## References

[1] Aymeric Blot, Marie-Éléonore Kessaci, and Laetitia Jourdan. Survey and unification of local search techniques in metaheuristics for multi-objective combinatorial optimisation. *Journal of Heuristics*, 24:853–877, 2018.

[2] Janez Demšar. Statistical comparisons of classifiers over multiple data sets. *The Journal of Machine learning research*, 7:1–30, 2006.

[3] Joshua Knowles and David Corne. Properties of an adaptive archiving algorithm for storing nondominated vectors. *IEEE Transactions on Evolutionary Computation*, 7(2):100–116, 2003.

[4] Joshua D Knowles, David W Corne, and Mark Fleischer. Bounded archiving using the lebesgue measure. In *The 2003 Congress on Evolutionary Computation, 2003. CEC'03.*, volume 4, pages 2490–2497. IEEE, 2003.

[5] ORKAD Team, CRISTAL, University of Lille. MH-builder framework, 2023.

[6] Carlos Segura, Joel Chacón Castillo, and Oliver Schütze. The importance of diversity in the variable space in the design of multi-objective evolutionary algorithms. *Applied Soft Computing*, 136:110069, 2023.