On the Use of Survival Selection Methods for Evolutionary Diversity Optimisation
Authors: Adel Nikfarjam, Jakob Bossek, Aneta Neumann, Frank Neumann
Organizations: Optimisation and Logistics School of Computer Science Adelaide University · Department of Computer Science Machine Learning and Optimisation Paderborn University
Generating a diverse set of high quality solutions for an optimisation problem has been studied extensively in recent years by the evolutionary computation community. A paradigm that has received increasing attention is evolutionary diversity optimisation (EDO), where the goal is to maximise the diversity of a solution set subject to quality constraints. Since the contribution of each solution to the diversity of the population depends on other solutions and can change dramatically if several solutions in the population are modified simultaneously, most EDO approaches generate a single new solution per generation and discard the solution with the least contribution to diversity, ensuring a steady increase in population diversity over successive generations until convergence. In this study, we aim to answer two questions: (1) Is generating multiple solutions in each generation beneficial for EDO? (2) How can this be achieved efficiently, given that conventional survival selection methods do not work well in EDO due to the dependency of a solution's contribution to diversity on other solutions?
Multi-objective optimization (MOO) has emerged as a powerful approach to solving complex optimization problems involving multiple objectives. In many practical scenarios, function evaluations are unavailable or prohibitively expensive, necessitating optimization solely based on a fixed offline dataset. In this setting, known as offline MOO, the goal is to find out the Pareto set without access to the true objective functions. This setting suffers from the out-of-distribution (OOD) issue, where the surrogate model is not accurate for unseen designs. Due to the OOD issue, surrogate errors may cause the optimizer to select solutions that do not lie on the true Pareto front and are biased toward its extremes. To address this, this paper proposes Diversity-driven Offline Multi-Objective Optimization (DOMOO), which aims to find out a diverse and high-quality set of solutions. First, DOMOO incorporates an accumulative risk control module that estimates the potential risk of candidate solutions and alleviates the OOD issue between the training data and the generated solutions. In addition, a nested Pareto set learning (PSL) strategy is proposed to jointly learn preference and PSL parameters, then optimize them, enabling adaptation to diverse Pareto front geometries. To further enhance solution quality, we design a diversity-driven selection strategy that extracts a representative and well-distributed set of final solutions. To achieve this diversity-driven selection strategy, we propose IGDoffline, a tailored indicator for the offline setting that considers both diversity and convergence, and avoids the bias of hypervolume indicator. Extensive experiments on synthetic and real-world benchmarks show that DOMOO achieves the best average rank across tasks in both convergence and diversity among the compared methods.
The integration of Large Language Models (LLMs) with evolutionary computation has emerged as a powerful paradigm for automated heuristic design in combinatorial optimization. However, existing approaches suffer from mode collapse, converging to homogeneous populations that lack semantic diversity and fail to explore the full algorithmic space. We propose Quality-Diversity Evolution (QDEvo), a multi-objective framework that integrates Quality-Diversity optimization with LLM-driven heuristic search, maintaining an unbounded archive of semantically diverse algorithms using pre-trained code embeddings and incorporating hierarchical self-reflection to guide the evolutionary process. Extensive experiments across standard benchmarks and real-world industrial applications demonstrate that QDEvo significantly outperforms state-of-the-art methods in both Hypervolume and Inverted Generational Distance metrics. Our framework enables the discovery of heuristics that are simultaneously high-performing, computationally efficient, and semantically diverse, providing practitioners with a rich portfolio of solutions for complex optimization problems.
Nam Do Khanh, Nhat Nguyen Tran Minh, Dat Pham Vu Tuan +2
Biological evolution sustains complex dynamics without any fitness function, yet virtually all evolutionary algorithms depend on one. Genesis is an open-source platform designed to test, empirically, what an artificial system needs to sustain evolutionary dynamics after complete fitness removal. Evolution in Genesis is governed by physical constraints, relational dominance, and adaptive regulation - no scalar fitness, no designer-specified objectives. Across experiments totalling over one million evolutionary generations, Genesis has: (i) shown that constraint-driven selection can sustain evolutionary activity after complete fitness removal (7/12 runs; Wilson 95% CI [30.2%, 82.5%]; p<0.01, Cohen's d=1.47 vs. baselines); (ii) produced a sham-controlled negative result demonstrating that niche construction alone does not break the complexity plateau; and (iii) provided preliminary evidence that speciation-protected niche construction initiates structural diversification that unprotected secretion cannot. These findings establish empirical boundaries for fitness-free evolution and open a new direction: meta-evolution of physics, in which the laws governing an evolutionary system are themselves evolved.