Cluster Prevention in Evolutionary Diversity Optimization for Parallel Machine Scheduling

Genetic and Evolutionary Computation Conference (GECCO), pp. 340–348

Abstract

This paper addresses the prevention of undesired clusters in solution sets generated by evolutionary diversity optimization (EDO), which seeks to compute diverse solutions of high quality. We demonstrate that employing ℓp-norms when designing a diversity measure based on pairwise comparisons discourages clusters in a population, in accordance with the intuitive notion of diversity. Furthermore, we propose a novel diversity measure specifically tailored for parallel machine scheduling, leveraging direct sequential relationships between job pairs. Through experimental validation, we demonstrate that integrating our diversity measure into an established evolutionary algorithm yields highly diverse solution sets and show that the use of ℓp-norms leads to solution sets exhibiting higher robustness than established methods, enabling better adaptability to subsequent modifications of the model.

Authors 2

1. Dominic Wittner Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

2. Jakob Bossek

   Paderborn University

   Affiliation as printed

   Universität Paderborn, Paderborn, Germany