Evolutionary Multi-Objective Diversity Optimization
- URL: http://arxiv.org/abs/2401.07454v1
- Date: Mon, 15 Jan 2024 03:59:42 GMT
- Title: Evolutionary Multi-Objective Diversity Optimization
- Authors: Anh Viet Do, Mingyu Guo, Aneta Neumann, Frank Neumann
- Abstract summary: We treat this problem as a bi-objective optimization problem, which is to obtain a range of quality-diversity trade-offs.
We present a suitable general implementation scheme that is compatible with existing evolutionary multi-objective search methods.
The resulting non-dominated populations exhibit rich qualitative features, giving insights into the optimization instances and the quality-diversity trade-offs they induce.
- Score: 14.930208990741129
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Creating diverse sets of high quality solutions has become an important
problem in recent years. Previous works on diverse solutions problems consider
solutions' objective quality and diversity where one is regarded as the
optimization goal and the other as the constraint. In this paper, we treat this
problem as a bi-objective optimization problem, which is to obtain a range of
quality-diversity trade-offs. To address this problem, we frame the
evolutionary process as evolving a population of populations, and present a
suitable general implementation scheme that is compatible with existing
evolutionary multi-objective search methods. We realize the scheme in NSGA-II
and SPEA2, and test the methods on various instances of maximum coverage,
maximum cut and minimum vertex cover problems. The resulting non-dominated
populations exhibit rich qualitative features, giving insights into the
optimization instances and the quality-diversity trade-offs they induce.
Related papers
- Illuminating the Diversity-Fitness Trade-Off in Black-Box Optimization [9.838618121102053]
In real-world applications, users often favor structurally diverse design choices over one high-quality solution.
This paper presents a fresh perspective on this challenge by considering the problem of identifying a fixed number of solutions with a pairwise distance above a specified threshold.
arXiv Detail & Related papers (2024-08-29T09:55:55Z) - Solving the Food-Energy-Water Nexus Problem via Intelligent Optimization Algorithms [46.48853432592689]
Food-Energy-Water systems are intricately linked among food, energy and water that impact each other.
They usually involve a huge number of decision variables and many conflicting objectives to be optimized.
In this paper, we solve a Food-Energy-Water optimization problem by using the state-of-art intelligent optimization methods and compare their performance.
arXiv Detail & Related papers (2024-04-10T06:19:19Z) - Evolutionary Solution Adaption for Multi-Objective Metal Cutting Process
Optimization [59.45414406974091]
We introduce a framework for system flexibility that allows us to study the ability of an algorithm to transfer solutions from previous optimization tasks.
We study the flexibility of NSGA-II, which we extend by two variants: 1) varying goals, that optimize solutions for two tasks simultaneously to obtain in-between source solutions expected to be more adaptable, and 2) active-inactive genotype, that accommodates different possibilities that can be activated or deactivated.
Results show that adaption with standard NSGA-II greatly reduces the number of evaluations required for optimization to a target goal, while the proposed variants further improve the adaption costs.
arXiv Detail & Related papers (2023-05-31T12:07:50Z) - Multi-Objective GFlowNets [59.16787189214784]
We study the problem of generating diverse candidates in the context of Multi-Objective Optimization.
In many applications of machine learning such as drug discovery and material design, the goal is to generate candidates which simultaneously optimize a set of potentially conflicting objectives.
We propose Multi-Objective GFlowNets (MOGFNs), a novel method for generating diverse optimal solutions, based on GFlowNets.
arXiv Detail & Related papers (2022-10-23T16:15:36Z) - Computing High-Quality Solutions for the Patient Admission Scheduling
Problem using Evolutionary Diversity Optimisation [10.609857097723266]
We adapt the evolutionary diversity optimisation for a real-world problem, namely patient admission scheduling.
We introduce an evolutionary algorithm to achieve structural diversity in a set of solutions subjected to the quality of each solution.
arXiv Detail & Related papers (2022-07-28T14:26:45Z) - Coevolutionary Pareto Diversity Optimization [13.026567958569965]
We introduce a coevolutionary Pareto Diversity Optimization approach.
In particular, we show that the use of inter-population crossover further improves the diversity of the set of solutions.
arXiv Detail & Related papers (2022-04-12T00:52:13Z) - Evolutionary Diversity Optimisation for The Traveling Thief Problem [11.590506672325668]
We introduce a bi-level evolutionary algorithm to maximise the structural diversity of the set of solutions.
We empirically determine the best method to obtain diversity.
Our experimental results show a significant improvement of the QD approach in terms of structural diversity for most TTP benchmark instances.
arXiv Detail & Related papers (2022-04-06T10:13:55Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
We propose to reformulate the result diversification problem as a bi-objective search problem, and solve it by a multi-objective evolutionary algorithm (EA)
We theoretically prove that the GSEMO can achieve the optimal-time approximation ratio, $1/2$.
When the objective function changes dynamically, the GSEMO can maintain this approximation ratio in running time, addressing the open question proposed by Borodin et al.
arXiv Detail & Related papers (2021-10-18T14:00:22Z) - An Analysis of Phenotypic Diversity in Multi-Solution Optimization [118.97353274202749]
We show that multiobjective optimization does not always produce much diversity, multimodal optimization produces higher fitness solutions, and quality diversity is not sensitive to genetic neutrality.
An autoencoder is used to discover phenotypic features automatically, producing an even more diverse solution set with quality diversity.
arXiv Detail & Related papers (2021-05-10T10:39:03Z) - EOS: a Parallel, Self-Adaptive, Multi-Population Evolutionary Algorithm
for Constrained Global Optimization [68.8204255655161]
EOS is a global optimization algorithm for constrained and unconstrained problems of real-valued variables.
It implements a number of improvements to the well-known Differential Evolution (DE) algorithm.
Results prove that EOSis capable of achieving increased performance compared to state-of-the-art single-population self-adaptive DE algorithms.
arXiv Detail & Related papers (2020-07-09T10:19:22Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.