Showing 1–50 of 135 results for author: Neumann, F

Sliding Window Bi-Objective Evolutionary Algorithms for Optimizing Chance-Constrained Monotone Submodular Functions

Authors: Xiankun Yan, Anneta Neumann, Frank Neumann

Abstract: Variants of the GSEMO algorithm using multi-objective formulations have been successfully analyzed and applied to optimize chance-constrained submodular functions. However, due to the effect of the increasing population size of the GSEMO algorithm considered in these studies from the algorithms, the approach becomes ineffective if the number of trade-offs obtained grows quickly during the optimiza… ▽ More Variants of the GSEMO algorithm using multi-objective formulations have been successfully analyzed and applied to optimize chance-constrained submodular functions. However, due to the effect of the increasing population size of the GSEMO algorithm considered in these studies from the algorithms, the approach becomes ineffective if the number of trade-offs obtained grows quickly during the optimization run. In this paper, we apply the sliding-selection approach introduced in [21] to the optimization of chance-constrained monotone submodular functions. We theoretically analyze the resulting SW-GSEMO algorithm which successfully limits the population size as a key factor that impacts the runtime and show that this allows it to obtain better runtime guarantees than the best ones currently known for the GSEMO. In our experimental study, we compare the performance of the SW-GSEMO to the GSEMO and NSGA-II on the maximum coverage problem under the chance constraint and show that the SW-GSEMO outperforms the other two approaches in most cases. In order to get additional insights into the optimization behavior of SW-GSEMO, we visualize the selection behavior of SW-GSEMO during its optimization process and show it beats other algorithms to obtain the highest quality of solution in variable instances. △ Less

Submitted 12 July, 2024; originally announced July 2024.

Local Optima in Diversity Optimization: Non-trivial Offspring Population is Essential

Authors: Denis Antipov, Aneta Neumann, Frank Neumann

Abstract: The main goal of diversity optimization is to find a diverse set of solutions which satisfy some lower bound on their fitness. Evolutionary algorithms (EAs) are often used for such tasks, since they are naturally designed to optimize populations of solutions. This approach to diversity optimization, called EDO, has been previously studied from theoretical perspective, but most studies considered o… ▽ More The main goal of diversity optimization is to find a diverse set of solutions which satisfy some lower bound on their fitness. Evolutionary algorithms (EAs) are often used for such tasks, since they are naturally designed to optimize populations of solutions. This approach to diversity optimization, called EDO, has been previously studied from theoretical perspective, but most studies considered only EAs with a trivial offspring population such as the $(μ+ 1)$ EA. In this paper we give an example instance of a $k$-vertex cover problem, which highlights a critical difference of the diversity optimization from the regular single-objective optimization, namely that there might be a locally optimal population from which we can escape only by replacing at least two individuals at once, which the $(μ+ 1)$ algorithms cannot do. We also show that the $(μ+ λ)$ EA with $λ\ge μ$ can effectively find a diverse population on $k$-vertex cover, if using a mutation operator inspired by Branson and Sutton (TCS 2023). To avoid the problem of subset selection which arises in the $(μ+ λ)$ EA when it optimizes diversity, we also propose the $(1_μ+ 1_μ)$ EA$_D$, which is an analogue of the $(1 + 1)$ EA for populations, and which is also efficient at optimizing diversity on the $k$-vertex cover problem. △ Less

Submitted 11 July, 2024; originally announced July 2024.

Comments: Open-access version of the same-titled PPSN 2024 paper

Archive-based Single-Objective Evolutionary Algorithms for Submodular Optimization

Authors: Frank Neumann, Günter Rudolph

Abstract: Constrained submodular optimization problems play a key role in the area of combinatorial optimization as they capture many NP-hard optimization problems. So far, Pareto optimization approaches using multi-objective formulations have been shown to be successful to tackle these problems while single-objective formulations lead to difficulties for algorithms such as the $(1+1)$-EA due to the presenc… ▽ More Constrained submodular optimization problems play a key role in the area of combinatorial optimization as they capture many NP-hard optimization problems. So far, Pareto optimization approaches using multi-objective formulations have been shown to be successful to tackle these problems while single-objective formulations lead to difficulties for algorithms such as the $(1+1)$-EA due to the presence of local optima. We introduce for the first time single-objective algorithms that are provably successful for different classes of constrained submodular maximization problems. Our algorithms are variants of the $(1+λ)$-EA and $(1+1)$-EA and increase the feasible region of the search space incrementally in order to deal with the considered submodular problems. △ Less

Submitted 19 June, 2024; originally announced June 2024.

Comments: To appear at PPSN 2024

Sliding Window 3-Objective Pareto Optimization for Problems with Chance Constraints

Authors: Frank Neumann, Carsten Witt

Abstract: Constrained single-objective problems have been frequently tackled by evolutionary multi-objective algorithms where the constraint is relaxed into an additional objective. Recently, it has been shown that Pareto optimization approaches using bi-objective models can be significantly sped up using sliding windows (Neumann and Witt, ECAI 2023). In this paper, we extend the sliding window approach to… ▽ More Constrained single-objective problems have been frequently tackled by evolutionary multi-objective algorithms where the constraint is relaxed into an additional objective. Recently, it has been shown that Pareto optimization approaches using bi-objective models can be significantly sped up using sliding windows (Neumann and Witt, ECAI 2023). In this paper, we extend the sliding window approach to $3$-objective formulations for tackling chance constrained problems. On the theoretical side, we show that our new sliding window approach improves previous runtime bounds obtained in (Neumann and Witt, GECCO 2023) while maintaining the same approximation guarantees. Our experimental investigations for the chance constrained dominating set problem show that our new sliding window approach allows one to solve much larger instances in a much more efficient way than the 3-objective approach presented in (Neumann and Witt, GECCO 2023). △ Less

Submitted 7 June, 2024; originally announced June 2024.

Comments: To appear at PPSN 2024

Evolving Reliable Differentiating Constraints for the Chance-constrained Maximum Coverage Problem

Authors: Saba Sadeghi Ahouei, Jacob de Nobel, Aneta Neumann, Thomas Bäck, Frank Neumann

Abstract: Chance-constrained problems involve stochastic components in the constraints which can be violated with a small probability. We investigate the impact of different types of chance constraints on the performance of iterative search algorithms and study the classical maximum coverage problem in graphs with chance constraints. Our goal is to evolve reliable chance constraint settings for a given grap… ▽ More Chance-constrained problems involve stochastic components in the constraints which can be violated with a small probability. We investigate the impact of different types of chance constraints on the performance of iterative search algorithms and study the classical maximum coverage problem in graphs with chance constraints. Our goal is to evolve reliable chance constraint settings for a given graph where the performance of algorithms differs significantly not just in expectation but with high confidence. This allows to better learn and understand how different types of algorithms can deal with different types of constraint settings and supports automatic algorithm selection. We develop an evolutionary algorithm that provides sets of chance constraints that differentiate the performance of two stochastic search algorithms with high confidence. We initially use traditional approximation ratio as the fitness function of (1+1)~EA to evolve instances, which shows inadequacy to generate reliable instances. To address this issue, we introduce a new measure to calculate the performance difference for two algorithms, which considers variances of performance ratios. Our experiments show that our approach is highly successful in solving the instability issue of the performance ratios and leads to evolving reliable sets of chance constraints with significantly different performance for various types of algorithms. △ Less

Submitted 29 May, 2024; originally announced May 2024.

Sampling-based Pareto Optimization for Chance-constrained Monotone Submodular Problems

Authors: Xiankun Yan, Aneta Neumann, Frank Neumann

Abstract: Recently surrogate functions based on the tail inequalities were developed to evaluate the chance constraints in the context of evolutionary computation and several Pareto optimization algorithms using these surrogates were successfully applied in optimizing chance-constrained monotone submodular problems. However, the difference in performance between algorithms using the surrogates and those emp… ▽ More Recently surrogate functions based on the tail inequalities were developed to evaluate the chance constraints in the context of evolutionary computation and several Pareto optimization algorithms using these surrogates were successfully applied in optimizing chance-constrained monotone submodular problems. However, the difference in performance between algorithms using the surrogates and those employing the direct sampling-based evaluation remains unclear. Within the paper, a sampling-based method is proposed to directly evaluate the chance constraint. Furthermore, to address the problems with more challenging settings, an enhanced GSEMO algorithm integrated with an adaptive sliding window, called ASW-GSEMO, is introduced. In the experiments, the ASW-GSEMO employing the sampling-based approach is tested on the chance-constrained version of the maximum coverage problem with different settings. Its results are compared with those from other algorithms using different surrogate functions. The experimental findings indicate that the ASW-GSEMO with the sampling-based evaluation approach outperforms other algorithms, highlighting that the performances of algorithms using different evaluation methods are comparable. Additionally, the behaviors of ASW-GSEMO are visualized to explain the distinctions between it and the algorithms utilizing the surrogate functions. △ Less

Submitted 18 April, 2024; originally announced April 2024.

Analysis of Evolutionary Diversity Optimisation for the Maximum Matching Problem

Authors: Jonathan Gadea Harder, Aneta Neumann, Frank Neumann

Abstract: This paper explores the enhancement of solution diversity in evolutionary algorithms (EAs) for the maximum matching problem, concentrating on complete bipartite graphs and paths. We adopt binary string encoding for matchings and use Hamming distance to measure diversity, aiming for its maximization. Our study centers on the $(μ+1)$-EA and $2P-EA_D$, which are applied to optimize diversity. We prov… ▽ More This paper explores the enhancement of solution diversity in evolutionary algorithms (EAs) for the maximum matching problem, concentrating on complete bipartite graphs and paths. We adopt binary string encoding for matchings and use Hamming distance to measure diversity, aiming for its maximization. Our study centers on the $(μ+1)$-EA and $2P-EA_D$, which are applied to optimize diversity. We provide a rigorous theoretical and empirical analysis of these algorithms. For complete bipartite graphs, our runtime analysis shows that, with a reasonably small $μ$, the $(μ+1)$-EA achieves maximal diversity with an expected runtime of $O(μ^2 m^4 \log(m))$ for the small gap case (where the population size $μ$ is less than the difference in the sizes of the bipartite partitions) and $O(μ^2 m^2 \log(m))$ otherwise. For paths, we establish an upper runtime bound of $O(μ^3 m^3)$. The $2P-EA_D$ displays stronger performance, with bounds of $O(μ^2 m^2 \log(m))$ for the small gap case, $O(μ^2 n^2 \log(n))$ otherwise, and $O(μ^3 m^2)$ for paths. Here, $n$ represents the total number of vertices and $m$ the number of edges. Our empirical studies, which examine the scaling behavior with respect to $m$ and $μ$, complement these theoretical insights and suggest potential for further refinement of the runtime bounds. △ Less

Submitted 17 April, 2024; originally announced April 2024.

Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem

Authors: Denis Antipov, Aneta Neumann, Frank Neumann, Andrew M. Sutton

Abstract: The diversity optimization is the class of optimization problems, in which we aim at finding a diverse set of good solutions. One of the frequently used approaches to solve such problems is to use evolutionary algorithms which evolve a desired diverse population. This approach is called evolutionary diversity optimization (EDO). In this paper, we analyse EDO on a 3-objective function LOTZ$_k$, w… ▽ More The diversity optimization is the class of optimization problems, in which we aim at finding a diverse set of good solutions. One of the frequently used approaches to solve such problems is to use evolutionary algorithms which evolve a desired diverse population. This approach is called evolutionary diversity optimization (EDO). In this paper, we analyse EDO on a 3-objective function LOTZ$_k$, which is a modification of the 2-objective benchmark function (LeadingOnes, TrailingZeros). We prove that the GSEMO computes a set of all Pareto-optimal solutions in $O(kn^3)$ expected iterations. We also analyze the runtime of the GSEMO$_D$ (a modification of the GSEMO for diversity optimization) until it finds a population with the best possible diversity for two different diversity measures, the total imbalance and the sorted imbalances vector. For the first measure we show that the GSEMO$_D$ optimizes it asymptotically faster than it finds a Pareto-optimal population, in $O(kn^2\log(n))$ expected iterations, and for the second measure we show an upper bound of $O(k^2n^3\log(n))$ expected iterations. We complement our theoretical analysis with an empirical study, which shows a very similar behavior for both diversity measures that is close to the theory predictions. △ Less

Submitted 18 April, 2024; v1 submitted 17 April, 2024; originally announced April 2024.

Runtime Analyses of NSGA-III on Many-Objective Problems

Authors: Andre Opris, Duc-Cuong Dang, Frank Neumann, Dirk Sudholt

Abstract: NSGA-II and NSGA-III are two of the most popular evolutionary multi-objective algorithms used in practice. While NSGA-II is used for few objectives such as 2 and 3, NSGA-III is designed to deal with a larger number of objectives. In a recent breakthrough, Wietheger and Doerr (IJCAI 2023) gave the first runtime analysis for NSGA-III on the 3-objective OneMinMax problem, showing that this state-of-t… ▽ More NSGA-II and NSGA-III are two of the most popular evolutionary multi-objective algorithms used in practice. While NSGA-II is used for few objectives such as 2 and 3, NSGA-III is designed to deal with a larger number of objectives. In a recent breakthrough, Wietheger and Doerr (IJCAI 2023) gave the first runtime analysis for NSGA-III on the 3-objective OneMinMax problem, showing that this state-of-the-art algorithm can be analyzed rigorously. We advance this new line of research by presenting the first runtime analyses of NSGA-III on the popular many-objective benchmark problems mLOTZ, mOMM, and mCOCZ, for an arbitrary constant number $m$ of objectives. Our analysis provides ways to set the important parameters of the algorithm: the number of reference points and the population size, so that a good performance can be guaranteed. We show how these parameters should be scaled with the problem dimension, the number of objectives and the fitness range. To our knowledge, these are the first runtime analyses for NSGA-III for more than 3 objectives. △ Less

Submitted 18 April, 2024; v1 submitted 17 April, 2024; originally announced April 2024.

Comments: To appear at GECCO 2024

MSC Class: 68Q25; 68Q87; 68W20; 68W40; 68W50 ACM Class: F.2.2; G.3

Using 3-Objective Evolutionary Algorithms for the Dynamic Chance Constrained Knapsack Problem

Authors: Ishara Hewa Pathiranage, Frank Neumann, Denis Antipov, Aneta Neumann

Abstract: Real-world optimization problems often involve stochastic and dynamic components. Evolutionary algorithms are particularly effective in these scenarios, as they can easily adapt to uncertain and changing environments but often uncertainty and dynamic changes are studied in isolation. In this paper, we explore the use of 3-objective evolutionary algorithms for the chance constrained knapsack proble… ▽ More Real-world optimization problems often involve stochastic and dynamic components. Evolutionary algorithms are particularly effective in these scenarios, as they can easily adapt to uncertain and changing environments but often uncertainty and dynamic changes are studied in isolation. In this paper, we explore the use of 3-objective evolutionary algorithms for the chance constrained knapsack problem with dynamic constraints. In our setting, the weights of the items are stochastic and the knapsack's capacity changes over time. We introduce a 3-objective formulation that is able to deal with the stochastic and dynamic components at the same time and is independent of the confidence level required for the constraint. This new approach is then compared to the 2-objective formulation which is limited to a single confidence level. We evaluate the approach using two different multi-objective evolutionary algorithms (MOEAs), namely the global simple evolutionary multi-objective optimizer (GSEMO) and the multi-objective evolutionary algorithm based on decomposition (MOEA/D), across various benchmark scenarios. Our analysis highlights the advantages of the 3-objective formulation over the 2-objective formulation in addressing the dynamic chance constrained knapsack problem. △ Less

Submitted 9 April, 2024; originally announced April 2024.

A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis

Authors: Benjamin Doerr, Joshua Knowles, Aneta Neumann, Frank Neumann

Abstract: We consider whether conditions exist under which block-coordinate descent is asymptotically efficient in evolutionary multi-objective optimization, addressing an open problem. Block-coordinate descent, where an optimization problem is decomposed into $k$ blocks of decision variables and each of the blocks is optimized (with the others fixed) in a sequence, is a technique used in some large-scale o… ▽ More We consider whether conditions exist under which block-coordinate descent is asymptotically efficient in evolutionary multi-objective optimization, addressing an open problem. Block-coordinate descent, where an optimization problem is decomposed into $k$ blocks of decision variables and each of the blocks is optimized (with the others fixed) in a sequence, is a technique used in some large-scale optimization problems such as airline scheduling, however its use in multi-objective optimization is less studied. We propose a block-coordinate version of GSEMO and compare its running time to the standard GSEMO algorithm. Theoretical and empirical results on a bi-objective test function, a variant of LOTZ, serve to demonstrate the existence of cases where block-coordinate descent is faster. The result may yield wider insights into this class of algorithms. △ Less

Submitted 10 April, 2024; v1 submitted 4 April, 2024; originally announced April 2024.

Comments: Accepted at GECCO 2024

Journal ref: GECCO '24: Proceedings of the Genetic and Evolutionary Computation Conference, 493 - 501, 2024. ACM

Evolutionary Multi-Objective Diversity Optimization

Authors: Anh Viet Do, Mingyu Guo, Aneta Neumann, Frank Neumann

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 t… ▽ More 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. △ Less

Submitted 14 January, 2024; originally announced January 2024.

Comments: 12 pages, 3 figures, 3 tables

Enhanced Genetic Programming Models with Multiple Equations for Accurate Semi-Autogenous Grinding Mill Throughput Prediction

Authors: Zahra Ghasemi, Mehdi Nesht, Chris Aldrich, John Karageorgos, Max Zanin, Frank Neumann, Lei Chen

Abstract: Semi-autogenous grinding (SAG) mills play a pivotal role in the grinding circuit of mineral processing plants. Accurate prediction of SAG mill throughput as a crucial performance metric is of utmost importance. The potential of applying genetic programming (GP) for this purpose has yet to be thoroughly investigated. This study introduces an enhanced GP approach entitled multi-equation GP (MEGP) fo… ▽ More Semi-autogenous grinding (SAG) mills play a pivotal role in the grinding circuit of mineral processing plants. Accurate prediction of SAG mill throughput as a crucial performance metric is of utmost importance. The potential of applying genetic programming (GP) for this purpose has yet to be thoroughly investigated. This study introduces an enhanced GP approach entitled multi-equation GP (MEGP) for more accurate prediction of SAG mill throughput. In the new proposed method multiple equations, each accurately predicting mill throughput for specific clusters of training data are extracted. These equations are then employed to predict mill throughput for test data using various approaches. To assess the effect of distance measures, four different distance measures are employed in MEGP method. Comparative analysis reveals that the best MEGP approach achieves an average improvement of 10.74% in prediction accuracy compared with standard GP. In this approach, all extracted equations are utilized and both the number of data points in each data cluster and the distance to clusters are incorporated for calculating the final prediction. Further investigation of distance measures indicates that among four different metrics employed including Euclidean, Manhattan, Chebyshev, and Cosine distance, the Euclidean distance measure yields the most accurate results for the majority of data splits. △ Less

Submitted 28 January, 2024; v1 submitted 17 December, 2023; originally announced January 2024.

A Study of Fitness Gains in Evolving Finite State Machines

Authors: Gabor Zoltai, Yue Xie, Frank Neumann

Abstract: Among the wide variety of evolutionary computing models, Finite State Machines (FSMs) have several attractions for fundamental research. They are easy to understand in concept and can be visualised clearly in simple cases. They have a ready fitness criterion through their relationship with Regular Languages. They have also been shown to be tractably evolvable, even up to exhibiting evidence of ope… ▽ More Among the wide variety of evolutionary computing models, Finite State Machines (FSMs) have several attractions for fundamental research. They are easy to understand in concept and can be visualised clearly in simple cases. They have a ready fitness criterion through their relationship with Regular Languages. They have also been shown to be tractably evolvable, even up to exhibiting evidence of open-ended evolution in specific scenarios. In addition to theoretical attraction, they also have industrial applications, as a paradigm of both automated and user-initiated control. Improving the understanding of the factors affecting FSM evolution has relevance to both computer science and practical optimisation of control. We investigate an evolutionary scenario of FSMs adapting to recognise one of a family of Regular Languages by categorising positive and negative samples, while also being under a counteracting selection pressure that favours fewer states. The results appear to indicate that longer strings provided as samples reduce the speed of fitness gain, when fitness is measured against a fixed number of sample strings. We draw the inference that additional information from longer strings is not sufficient to compensate for sparser coverage of the combinatorial space of positive and negative sample strings. △ Less

Submitted 19 October, 2023; originally announced October 2023.

Comments: 12 pages, 3 figures. Submitted to the Australasian Joint Conference on Artificial Intelligence (AJCAI) 2023

Optimizing Chance-Constrained Submodular Problems with Variable Uncertainties

Authors: Xiankun Yan, Anh Viet Do, Feng Shi, Xiaoyu Qin, Frank Neumann

Abstract: Chance constraints are frequently used to limit the probability of constraint violations in real-world optimization problems where the constraints involve stochastic components. We study chance-constrained submodular optimization problems, which capture a wide range of optimization problems with stochastic constraints. Previous studies considered submodular problems with stochastic knapsack constr… ▽ More Chance constraints are frequently used to limit the probability of constraint violations in real-world optimization problems where the constraints involve stochastic components. We study chance-constrained submodular optimization problems, which capture a wide range of optimization problems with stochastic constraints. Previous studies considered submodular problems with stochastic knapsack constraints in the case where uncertainties are the same for each item that can be selected. However, uncertainty levels are usually variable with respect to the different stochastic components in real-world scenarios, and rigorous analysis for this setting is missing in the context of submodular optimization. This paper provides the first such analysis for this case, where the weights of items have the same expectation but different dispersion. We present greedy algorithms that can obtain a high-quality solution, i.e., a constant approximation ratio to the given optimal solution from the deterministic setting. In the experiments, we demonstrate that the algorithms perform effectively on several chance-constrained instances of the maximum coverage problem and the influence maximization problem. △ Less

Submitted 23 September, 2023; originally announced September 2023.

Diverse Approximations for Monotone Submodular Maximization Problems with a Matroid Constraint

Authors: Anh Viet Do, Mingyu Guo, Aneta Neumann, Frank Neumann

Abstract: Finding diverse solutions to optimization problems has been of practical interest for several decades, and recently enjoyed increasing attention in research. While submodular optimization has been rigorously studied in many fields, its diverse solutions extension has not. In this study, we consider the most basic variants of submodular optimization, and propose two simple greedy algorithms, which… ▽ More Finding diverse solutions to optimization problems has been of practical interest for several decades, and recently enjoyed increasing attention in research. While submodular optimization has been rigorously studied in many fields, its diverse solutions extension has not. In this study, we consider the most basic variants of submodular optimization, and propose two simple greedy algorithms, which are known to be effective at maximizing monotone submodular functions. These are equipped with parameters that control the trade-off between objective and diversity. Our theoretical contribution shows their approximation guarantees in both objective value and diversity, as functions of their respective parameters. Our experimental investigation with maximum vertex coverage instances demonstrates their empirical differences in terms of objective-diversity trade-offs. △ Less

Submitted 14 July, 2023; originally announced July 2023.

Comments: Preprint of a paper to be published in IJCAI'23

Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax

Authors: Denis Antipov, Aneta Neumann, Frank Neumann

Abstract: The evolutionary diversity optimization aims at finding a diverse set of solutions which satisfy some constraint on their fitness. In the context of multi-objective optimization this constraint can require solutions to be Pareto-optimal. In this paper we study how the GSEMO algorithm with additional diversity-enhancing heuristic optimizes a diversity of its population on a bi-objective benchmark p… ▽ More The evolutionary diversity optimization aims at finding a diverse set of solutions which satisfy some constraint on their fitness. In the context of multi-objective optimization this constraint can require solutions to be Pareto-optimal. In this paper we study how the GSEMO algorithm with additional diversity-enhancing heuristic optimizes a diversity of its population on a bi-objective benchmark problem OneMinMax, for which all solutions are Pareto-optimal. We provide a rigorous runtime analysis of the last step of the optimization, when the algorithm starts with a population with a second-best diversity, and prove that it finds a population with optimal diversity in expected time $O(n^2)$, when the problem size $n$ is odd. For reaching our goal, we analyse the random walk of the population, which reflects the frequency of changes in the population and their outcomes. △ Less

Submitted 14 July, 2023; originally announced July 2023.

Comments: The full version of the paper accepted to FOGA 2023 conference

Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems

Authors: Anh Viet Do, Aneta Neumann, Frank Neumann, Andrew M. Sutton

Abstract: We study the multi-objective minimum weight base problem, an abstraction of classical NP-hard combinatorial problems such as the multi-objective minimum spanning tree problem. We prove some important properties of the convex hull of the non-dominated front, such as its approximation quality and an upper bound on the number of extreme points. Using these properties, we give the first run-time analy… ▽ More We study the multi-objective minimum weight base problem, an abstraction of classical NP-hard combinatorial problems such as the multi-objective minimum spanning tree problem. We prove some important properties of the convex hull of the non-dominated front, such as its approximation quality and an upper bound on the number of extreme points. Using these properties, we give the first run-time analysis of the MOEA/D algorithm for this problem, an evolutionary algorithm that effectively optimizes by decomposing the objectives into single-objective components. We show that the MOEA/D, given an appropriate decomposition setting, finds all extreme points within expected fixed-parameter polynomial time in the oracle model, the parameter being the number of objectives. Experiments are conducted on random bi-objective minimum spanning tree instances, and the results agree with our theoretical findings. Furthermore, compared with a previously studied evolutionary algorithm for the problem GSEMO, MOEA/D finds all extreme points much faster across all instances. △ Less

Submitted 6 June, 2023; originally announced June 2023.

Comments: 12 pages

On the Impact of Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem

Authors: Jakob Bossek, Aneta Neumann, Frank Neumann

Abstract: Evolutionary algorithms have been shown to obtain good solutions for complex optimization problems in static and dynamic environments. It is important to understand the behaviour of evolutionary algorithms for complex optimization problems that also involve dynamic and/or stochastic components in a systematic way in order to further increase their applicability to real-world problems. We investiga… ▽ More Evolutionary algorithms have been shown to obtain good solutions for complex optimization problems in static and dynamic environments. It is important to understand the behaviour of evolutionary algorithms for complex optimization problems that also involve dynamic and/or stochastic components in a systematic way in order to further increase their applicability to real-world problems. We investigate the node weighted traveling salesperson problem (W-TSP), which provides an abstraction of a wide range of weighted TSP problems, in dynamic settings. In the dynamic setting of the problem, items that have to be collected as part of a TSP tour change over time. We first present a dynamic setup for the dynamic W-TSP parameterized by different types of changes that are applied to the set of items to be collected when traversing the tour. Our first experimental investigations study the impact of such changes on resulting optimized tours in order to provide structural insights of optimization solutions. Afterwards, we investigate simple mutation-based evolutionary algorithms and study the impact of the mutation operators and the use of populations with dealing with the dynamic changes to the node weights of the problem. △ Less

Submitted 30 May, 2023; originally announced May 2023.

Analysis of the (1+1) EA on LeadingOnes with Constraints

Authors: Tobias Friedrich, Timo Kötzing, Aneta Neumann, Frank Neumann, Aishwarya Radhakrishnan

Abstract: Understanding how evolutionary algorithms perform on constrained problems has gained increasing attention in recent years. In this paper, we study how evolutionary algorithms optimize constrained versions of the classical LeadingOnes problem. We first provide a run time analysis for the classical (1+1) EA on the LeadingOnes problem with a deterministic cardinality constraint, giving… ▽ More Understanding how evolutionary algorithms perform on constrained problems has gained increasing attention in recent years. In this paper, we study how evolutionary algorithms optimize constrained versions of the classical LeadingOnes problem. We first provide a run time analysis for the classical (1+1) EA on the LeadingOnes problem with a deterministic cardinality constraint, giving $Θ(n (n-B)\log(B) + n^2)$ as the tight bound. Our results show that the behaviour of the algorithm is highly dependent on the constraint bound of the uniform constraint. Afterwards, we consider the problem in the context of stochastic constraints and provide insights using experimental studies on how the ($μ$+1) EA is able to deal with these constraints in a sampling-based setting. △ Less

Submitted 29 May, 2023; originally announced May 2023.

Improving Confidence in Evolutionary Mine Scheduling via Uncertainty Discounting

Authors: Michael Stimson, William Reid, Aneta Neumann, Simon Ratcliffe, Frank Neumann

Abstract: Mine planning is a complex task that involves many uncertainties. During early stage feasibility, available mineral resources can only be estimated based on limited sampling of ore grades from sparse drilling, leading to large uncertainty in under-sampled parts of the deposit. Planning the extraction schedule of ore over the life of a mine is crucial for its economic viability. We introduce a new… ▽ More Mine planning is a complex task that involves many uncertainties. During early stage feasibility, available mineral resources can only be estimated based on limited sampling of ore grades from sparse drilling, leading to large uncertainty in under-sampled parts of the deposit. Planning the extraction schedule of ore over the life of a mine is crucial for its economic viability. We introduce a new approach for determining an "optimal schedule under uncertainty" that provides probabilistic bounds on the profits obtained in each period. This treatment of uncertainty within an economic framework reduces previously difficult-to-use models of variability into actionable insights. The new method discounts profits based on uncertainty within an evolutionary algorithm, sacrificing economic optimality of a single geological model for improving the downside risk over an ensemble of equally likely models. We provide experimental studies using Maptek's mine planning software Evolution. Our results show that our new approach is successful for effectively making use of uncertainty information in the mine planning process. △ Less

Submitted 29 May, 2023; originally announced May 2023.

Evolutionary Diversity Optimisation in Constructing Satisfying Assignments

Authors: Adel Nikfarjam, Ralf Rothenberger, Frank Neumann, Tobias Friedrich

Abstract: Computing diverse solutions for a given problem, in particular evolutionary diversity optimisation (EDO), is a hot research topic in the evolutionary computation community. This paper studies the Boolean satisfiability problem (SAT) in the context of EDO. SAT is of great importance in computer science and differs from the other problems studied in EDO literature, such as KP and TSP. SAT is heavily… ▽ More Computing diverse solutions for a given problem, in particular evolutionary diversity optimisation (EDO), is a hot research topic in the evolutionary computation community. This paper studies the Boolean satisfiability problem (SAT) in the context of EDO. SAT is of great importance in computer science and differs from the other problems studied in EDO literature, such as KP and TSP. SAT is heavily constrained, and the conventional evolutionary operators are inefficient in generating SAT solutions. Our approach avails of the following characteristics of SAT: 1) the possibility of adding more constraints (clauses) to the problem to forbid solutions or to fix variables, and 2) powerful solvers in the literature, such as minisat. We utilise such a solver to construct a diverse set of solutions. Moreover, maximising diversity provides us with invaluable information about the solution space of a given SAT problem, such as how large the feasible region is. In this study, we introduce evolutionary algorithms (EAs) employing a well-known SAT solver to maximise diversity among a set of SAT solutions explicitly. The experimental investigations indicate the introduced algorithms' capability to maximise diversity among the SAT solutions. △ Less

Submitted 19 May, 2023; originally announced May 2023.

Comments: To appear at GECCO 2023

Fast Pareto Optimization Using Sliding Window Selection

Authors: Frank Neumann, Carsten Witt

Abstract: Pareto optimization using evolutionary multi-objective algorithms has been widely applied to solve constrained submodular optimization problems. A crucial factor determining the runtime of the used evolutionary algorithms to obtain good approximations is the population size of the algorithms which grows with the number of trade-offs that the algorithms encounter. In this paper, we introduce a slid… ▽ More Pareto optimization using evolutionary multi-objective algorithms has been widely applied to solve constrained submodular optimization problems. A crucial factor determining the runtime of the used evolutionary algorithms to obtain good approximations is the population size of the algorithms which grows with the number of trade-offs that the algorithms encounter. In this paper, we introduce a sliding window speed up technique for recently introduced algorithms. We prove that our technique eliminates the population size as a crucial factor negatively impacting the runtime and achieves the same theoretical performance guarantees as previous approaches within less computation time. Our experimental investigations for the classical maximum coverage problem confirms that our sliding window technique clearly leads to better results for a wide range of instances and constraint settings. △ Less

Submitted 11 May, 2023; originally announced May 2023.

3-Objective Pareto Optimization for Problems with Chance Constraints

Authors: Frank Neumann, Carsten Witt

Abstract: Evolutionary multi-objective algorithms have successfully been used in the context of Pareto optimization where a given constraint is relaxed into an additional objective. In this paper, we explore the use of 3-objective formulations for problems with chance constraints. Our formulation trades off the expected cost and variance of the stochastic component as well as the given deterministic constra… ▽ More Evolutionary multi-objective algorithms have successfully been used in the context of Pareto optimization where a given constraint is relaxed into an additional objective. In this paper, we explore the use of 3-objective formulations for problems with chance constraints. Our formulation trades off the expected cost and variance of the stochastic component as well as the given deterministic constraint. We point out benefits that this 3-objective formulation has compared to a bi-objective one recently investigated for chance constraints with Normally distributed stochastic components. Our analysis shows that the 3-objective formulation allows to compute all required trade-offs using 1-bit flips only, when dealing with a deterministic cardinality constraint. Furthermore, we carry out experimental investigations for the chance constrained dominating set problem and show the benefit for this classical NP-hard problem. △ Less

Submitted 18 April, 2023; originally announced April 2023.

Evolving Reinforcement Learning Environment to Minimize Learner's Achievable Reward: An Application on Hardening Active Directory Systems

Authors: Diksha Goel, Aneta Neumann, Frank Neumann, Hung Nguyen, Mingyu Guo

Abstract: We study a Stackelberg game between one attacker and one defender in a configurable environment. The defender picks a specific environment configuration. The attacker observes the configuration and attacks via Reinforcement Learning (RL trained against the observed environment). The defender's goal is to find the environment with minimum achievable reward for the attacker. We apply Evolutionary Di… ▽ More We study a Stackelberg game between one attacker and one defender in a configurable environment. The defender picks a specific environment configuration. The attacker observes the configuration and attacks via Reinforcement Learning (RL trained against the observed environment). The defender's goal is to find the environment with minimum achievable reward for the attacker. We apply Evolutionary Diversity Optimization (EDO) to generate diverse population of environments for training. Environments with clearly high rewards are killed off and replaced by new offsprings to avoid wasting training time. Diversity not only improves training quality but also fits well with our RL scenario: RL agents tend to improve gradually, so a slightly worse environment earlier on may become better later. We demonstrate the effectiveness of our approach by focusing on a specific application, Active Directory (AD). AD is the default security management system for Windows domain networks. AD environment describes an attack graph, where nodes represent computers/accounts/etc., and edges represent accesses. The attacker aims to find the best attack path to reach the highest-privilege node. The defender can change the graph by removing a limited number of edges (revoke accesses). Our approach generates better defensive plans than the existing approach and scales better. △ Less

Submitted 8 April, 2023; originally announced April 2023.

Towards Self-adaptive Mutation in Evolutionary Multi-Objective Algorithms

Authors: Furong Ye, Frank Neumann, Jacob de Nobel, Aneta Neumann, Thomas Bäck

Abstract: Parameter control has succeeded in accelerating the convergence process of evolutionary algorithms. While empirical and theoretical studies have shed light on the behavior of algorithms for single-objective optimization, little is known about how self-adaptation influences multi-objective evolutionary algorithms. In this work, we contribute (1) extensive experimental analysis of the Global Simple… ▽ More Parameter control has succeeded in accelerating the convergence process of evolutionary algorithms. While empirical and theoretical studies have shed light on the behavior of algorithms for single-objective optimization, little is known about how self-adaptation influences multi-objective evolutionary algorithms. In this work, we contribute (1) extensive experimental analysis of the Global Simple Evolutionary Multi-objective Algorithm (GSEMO) variants on classic problems, such as OneMinMax, LOTZ, COCZ, and (2) a novel version of GSEMO with self-adaptive mutation. To enable self-adaptation in GSEMO, we explore three self-adaptive mutation techniques from single-objective optimization and use various performance metrics, such as hypervolume and inverted generational distance, to guide the adaptation. Our experiments show that adapting the mutation rate based on single-objective optimization and hypervolume can speed up the convergence of GSEMO. Moreover, we propose a GSEMO with self-adaptive mutation, which considers optimizing for single objectives and adjusts the mutation rate for each solution individually. Our results demonstrate that the proposed method outperforms the GSEMO with static mutation rates across all the tested problems. This work provides a comprehensive benchmarking study for MOEAs and complements existing theoretical runtime analysis. Our proposed algorithm addresses interesting issues for designing MOEAs for future practical applications. △ Less

Submitted 8 May, 2023; v1 submitted 8 March, 2023; originally announced March 2023.

Comments: submitted to FOGA 2023

Evolutionary Multi-Objective Algorithms for the Knapsack Problems with Stochastic Profits

Authors: Kokila Perera, Aneta Neumann, Frank Neumann

Abstract: Evolutionary multi-objective algorithms have been widely shown to be successful when utilized for a variety of stochastic combinatorial optimization problems. Chance constrained optimization plays an important role in complex real-world scenarios, as it allows decision makers to take into account the uncertainty of the environment. We consider a version of the knapsack problem with stochastic prof… ▽ More Evolutionary multi-objective algorithms have been widely shown to be successful when utilized for a variety of stochastic combinatorial optimization problems. Chance constrained optimization plays an important role in complex real-world scenarios, as it allows decision makers to take into account the uncertainty of the environment. We consider a version of the knapsack problem with stochastic profits to guarantee a certain level of confidence in the profit of the solutions. We introduce the multi-objective formulations of the profit chance constrained knapsack problem and design three bi-objective fitness evaluation methods that work independently of the specific confidence level required. We evaluate our approaches using well-known multi-objective evolutionary algorithms GSEMO and NSGA-II. In addition, we introduce a filtering method for GSEMO that improves the quality of the final population by periodically removing certain solutions from the interim populations based on their confidence level. We show the effectiveness of our approaches on several benchmarks for both settings where the knapsack items have fixed uniform uncertainties and uncertainties that are positively correlated with the expected profit of an item. △ Less

Submitted 2 March, 2023; originally announced March 2023.

Comments: 14 pages, 1 figure

Limited Query Graph Connectivity Test

Authors: Mingyu Guo, Jialiang Li, Aneta Neumann, Frank Neumann, Hung Nguyen

Abstract: We propose a combinatorial optimisation model called Limited Query Graph Connectivity Test. We consider a graph whose edges have two possible states (On/Off). The edges' states are hidden initially. We could query an edge to reveal its state. Given a source s and a destination t, we aim to test s-t connectivity by identifying either a path (consisting of only On edges) or a cut (consisting of only… ▽ More We propose a combinatorial optimisation model called Limited Query Graph Connectivity Test. We consider a graph whose edges have two possible states (On/Off). The edges' states are hidden initially. We could query an edge to reveal its state. Given a source s and a destination t, we aim to test s-t connectivity by identifying either a path (consisting of only On edges) or a cut (consisting of only Off edges). We are limited to B queries, after which we stop regardless of whether graph connectivity is established. We aim to design a query policy that minimizes the expected number of queries. Our model is mainly motivated by a cyber security use case where we need to establish whether an attack path exists in a network, between a source and a destination. Edge query is resolved by manual effort from the IT admin, which is the motivation behind query minimization. Our model is highly related to monotone Stochastic Boolean Function Evaluation (SBFE). There are two existing exact algorithms for SBFE that are prohibitively expensive. We propose a significantly more scalable exact algorithm. While previous exact algorithms only scale for trivial graphs (i.e., past works experimented on at most 20 edges), we empirically demonstrate that our algorithm is scalable for a wide range of much larger practical graphs (i.e., Windows domain network graphs with tens of thousands of edges). We propose three heuristics. Our best-performing heuristic is via reducing the search horizon of the exact algorithm. The other two are via reinforcement learning (RL) and Monte Carlo tree search (MCTS). We also derive an anytime algorithm for computing the performance lower bound. Experimentally, we show that all our heuristics are near optimal. The exact algorithm based heuristic outperforms all, surpassing RL, MCTS and 8 existing heuristics ported from SBFE and related literature. △ Less

Submitted 18 December, 2023; v1 submitted 25 February, 2023; originally announced February 2023.

Journal ref: AAAI 2024

Benchmarking Algorithms for Submodular Optimization Problems Using IOHProfiler

Authors: Frank Neumann, Aneta Neumann, Chao Qian, Viet Anh Do, Jacob de Nobel, Diederick Vermetten, Saba Sadeghi Ahouei, Furong Ye, Hao Wang, Thomas Bäck

Abstract: Submodular functions play a key role in the area of optimization as they allow to model many real-world problems that face diminishing returns. Evolutionary algorithms have been shown to obtain strong theoretical performance guarantees for a wide class of submodular problems under various types of constraints while clearly outperforming standard greedy approximation algorithms. This paper introduc… ▽ More Submodular functions play a key role in the area of optimization as they allow to model many real-world problems that face diminishing returns. Evolutionary algorithms have been shown to obtain strong theoretical performance guarantees for a wide class of submodular problems under various types of constraints while clearly outperforming standard greedy approximation algorithms. This paper introduces a setup for benchmarking algorithms for submodular optimization problems with the aim to provide researchers with a framework to enhance and compare the performance of new algorithms for submodular problems. The focus is on the development of iterative search algorithms such as evolutionary algorithms with the implementation provided and integrated into IOHprofiler which allows for tracking and comparing the progress and performance of iterative search algorithms. We present a range of submodular optimization problems that have been integrated into IOHprofiler and show how the setup can be used for analyzing and comparing iterative search algorithms in various settings. △ Less

Submitted 2 February, 2023; originally announced February 2023.

Runtime Performance of Evolutionary Algorithms for the Chance-constrained Makespan Scheduling Problem

Authors: Feng Shi, Xiankun Yan, Frank Neumann

Abstract: The Makespan Scheduling problem is an extensively studied NP-hard problem, and its simplest version looks for an allocation approach for a set of jobs with deterministic processing times to two identical machines such that the makespan is minimized. However, in real life scenarios, the actual processing time of each job may be stochastic around the expected value with a variance, under the influen… ▽ More The Makespan Scheduling problem is an extensively studied NP-hard problem, and its simplest version looks for an allocation approach for a set of jobs with deterministic processing times to two identical machines such that the makespan is minimized. However, in real life scenarios, the actual processing time of each job may be stochastic around the expected value with a variance, under the influence of external factors, and the actual processing times of these jobs may be correlated with covariances. Thus within this paper, we propose a chance-constrained version of the Makespan Scheduling problem and investigate the theoretical performance of the classical Randomized Local Search and (1+1) EA for it. More specifically, we first study two variants of the Chance-constrained Makespan Scheduling problem and their computational complexities, then separately analyze the expected runtime of the two algorithms to obtain an optimal solution or almost optimal solution to the instances of the two variants. In addition, we investigate the experimental performance of the two algorithms for the two variants. △ Less

Submitted 2 July, 2023; v1 submitted 21 December, 2022; originally announced December 2022.

Scalable Edge Blocking Algorithms for Defending Active Directory Style Attack Graphs

Authors: Mingyu Guo, Max Ward, Aneta Neumann, Frank Neumann, Hung Nguyen

Abstract: Active Directory (AD) is the default security management system for Windows domain networks. An AD environment naturally describes an attack graph where nodes represent computers/accounts/security groups, and edges represent existing accesses/known exploits that allow the attacker to gain access from one node to another. Motivated by practical AD use cases, we study a Stackelberg game between one… ▽ More Active Directory (AD) is the default security management system for Windows domain networks. An AD environment naturally describes an attack graph where nodes represent computers/accounts/security groups, and edges represent existing accesses/known exploits that allow the attacker to gain access from one node to another. Motivated by practical AD use cases, we study a Stackelberg game between one attacker and one defender. There are multiple entry nodes for the attacker to choose from and there is a single target (Domain Admin). Every edge has a failure rate. The attacker chooses the attack path with the maximum success rate. The defender can block a limited number of edges (i.e., revoke accesses) from a set of blockable edges, limited by budget. The defender's aim is to minimize the attacker's success rate. We exploit the tree-likeness of practical AD graphs to design scalable algorithms. We propose two novel methods that combine theoretical fixed parameter analysis and practical optimisation techniques. For graphs with small tree widths, we propose a tree decomposition based dynamic program. We then propose a general method for converting tree decomposition based dynamic programs to reinforcement learning environments, which leads to an anytime algorithm that scales better, but loses the optimality guarantee. For graphs with small numbers of non-splitting paths (a parameter we invent specifically for AD graphs), we propose a kernelization technique that significantly downsizes the model, which is then solved via mixed-integer programming. Experimentally, our algorithms scale to handle synthetic AD graphs with tens of thousands of nodes. △ Less

Submitted 2 December, 2022; originally announced December 2022.

Theoretical Study of Optimizing Rugged Landscapes with the cGA

Authors: Tobias Friedrich, Timo Kötzing, Frank Neumann, Aishwarya Radhakrishnan

Abstract: Estimation of distribution algorithms (EDAs) provide a distribution - based approach for optimization which adapts its probability distribution during the run of the algorithm. We contribute to the theoretical understanding of EDAs and point out that their distribution approach makes them more suitable to deal with rugged fitness landscapes than classical local search algorithms. Concretely, we ma… ▽ More Estimation of distribution algorithms (EDAs) provide a distribution - based approach for optimization which adapts its probability distribution during the run of the algorithm. We contribute to the theoretical understanding of EDAs and point out that their distribution approach makes them more suitable to deal with rugged fitness landscapes than classical local search algorithms. Concretely, we make the OneMax function rugged by adding noise to each fitness value. The cGA can nevertheless find solutions with n(1 - ε) many 1s, even for high variance of noise. In contrast to this, RLS and the (1+1) EA, with high probability, only find solutions with n(1/2+o(1)) many 1s, even for noise with small variance. △ Less

Submitted 24 November, 2022; originally announced November 2022.

Comments: 17 pages, 1 figure, PPSN 2022

MSC Class: 68W50

Runtime Analysis of the (1+1) EA on Weighted Sums of Transformed Linear Functions

Authors: Frank Neumann, Carsten Witt

Abstract: Linear functions play a key role in the runtime analysis of evolutionary algorithms and studies have provided a wide range of new insights and techniques for analyzing evolutionary computation methods. Motivated by studies on separable functions and the optimization behaviour of evolutionary algorithms as well as objective functions from the area of chance constrained optimization, we study the cl… ▽ More Linear functions play a key role in the runtime analysis of evolutionary algorithms and studies have provided a wide range of new insights and techniques for analyzing evolutionary computation methods. Motivated by studies on separable functions and the optimization behaviour of evolutionary algorithms as well as objective functions from the area of chance constrained optimization, we study the class of objective functions that are weighted sums of two transformed linear functions. Our results show that the (1+1) EA, with a mutation rate depending on the number of overlapping bits of the functions, obtains an optimal solution for these functions in expected time O(n log n), thereby generalizing a well-known result for linear functions to a much wider range of problems. △ Less

Submitted 11 August, 2022; originally announced August 2022.

Comments: To appear at PPSN 2022. arXiv admin note: text overlap with arXiv:2109.05799

Computing High-Quality Solutions for the Patient Admission Scheduling Problem using Evolutionary Diversity Optimisation

Authors: Adel Nikfarjam, Amirhossein Moosavi, Aneta Neumann, Frank Neumann

Abstract: Diversification in a set of solutions has become a hot research topic in the evolutionary computation community. It has been proven beneficial for optimisation problems in several ways, such as computing a diverse set of high-quality solutions and obtaining robustness against imperfect modeling. For the first time in the literature, we adapt the evolutionary diversity optimisation for a real-world… ▽ More Diversification in a set of solutions has become a hot research topic in the evolutionary computation community. It has been proven beneficial for optimisation problems in several ways, such as computing a diverse set of high-quality solutions and obtaining robustness against imperfect modeling. For the first time in the literature, we adapt the evolutionary diversity optimisation for a real-world combinatorial 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. We also introduce a mutation operator biased towards diversity maximisation. Finally, we demonstrate the importance of diversity for the aforementioned problem through a simulation. △ Less

Submitted 28 July, 2022; originally announced July 2022.

Comments: To appear at PPSN 2022

Analysis of Quality Diversity Algorithms for the Knapsack Problem

Authors: Adel Nikfarjam, Anh Viet Do, Frank Neumann

Abstract: Quality diversity (QD) algorithms have been shown to be very successful when dealing with problems in areas such as robotics, games and combinatorial optimization. They aim to maximize the quality of solutions for different regions of the so-called behavioural space of the underlying problem. In this paper, we apply the QD paradigm to simulate dynamic programming behaviours on knapsack problem, an… ▽ More Quality diversity (QD) algorithms have been shown to be very successful when dealing with problems in areas such as robotics, games and combinatorial optimization. They aim to maximize the quality of solutions for different regions of the so-called behavioural space of the underlying problem. In this paper, we apply the QD paradigm to simulate dynamic programming behaviours on knapsack problem, and provide a first runtime analysis of QD algorithms. We show that they are able to compute an optimal solution within expected pseudo-polynomial time, and reveal parameter settings that lead to a fully polynomial randomised approximation scheme (FPRAS). Our experimental investigations evaluate the different approaches on classical benchmark sets in terms of solutions constructed in the behavioural space as well as the runtime needed to obtain an optimal solution. △ Less

Submitted 28 July, 2022; originally announced July 2022.

Comments: To appear at PPSN 2022

Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem

Authors: Adel Nikfarjam, Aneta Neumann, Jakob Bossek, Frank Neumann

Abstract: Recently different evolutionary computation approaches have been developed that generate sets of high quality diverse solutions for a given optimisation problem. Many studies have considered diversity 1) as a mean to explore niches in behavioural space (quality diversity) or 2) to increase the structural differences of solutions (evolutionary diversity optimisation). In this study, we introduce a… ▽ More Recently different evolutionary computation approaches have been developed that generate sets of high quality diverse solutions for a given optimisation problem. Many studies have considered diversity 1) as a mean to explore niches in behavioural space (quality diversity) or 2) to increase the structural differences of solutions (evolutionary diversity optimisation). In this study, we introduce a co-evolutionary algorithm to simultaneously explore the two spaces for the multi-component traveling thief problem. The results show the capability of the co-evolutionary algorithm to achieve significantly higher diversity compared to the baseline evolutionary diversity algorithms from the the literature. △ Less

Submitted 28 July, 2022; originally announced July 2022.

Comments: To appear at PPSN 2022

Evolutionary Time-Use Optimization for Improving Children's Health Outcomes

Authors: Yue Xie, Aneta Neumann, Ty Stanford, Charlotte Lund Rasmussen, Dorothea Dumuid, Frank Neumann

Abstract: How someone allocates their time is important to their health and well-being. In this paper, we show how evolutionary algorithms can be used to promote health and well-being by optimizing time usage. Based on data from a large population-based child cohort, we design fitness functions to explain health outcomes and introduce constraints for viable time plans. We then investigate the performance of… ▽ More How someone allocates their time is important to their health and well-being. In this paper, we show how evolutionary algorithms can be used to promote health and well-being by optimizing time usage. Based on data from a large population-based child cohort, we design fitness functions to explain health outcomes and introduce constraints for viable time plans. We then investigate the performance of evolutionary algorithms to optimize time use for four individual health outcomes with hypothetical children with different day structures. As the four health outcomes are competing for time allocations, we study how to optimize multiple health outcomes simultaneously in the form of a multi-objective optimization problem. We optimize one-week time-use plans using evolutionary multi-objective algorithms and point out the trade-offs achievable with respect to different health outcomes. △ Less

Submitted 23 June, 2022; originally announced June 2022.

Comments: Has been accepted by PPSN2022

Evolutionary Algorithms for Limiting the Effect of Uncertainty for the Knapsack Problem with Stochastic Profits

Authors: Aneta Neumann, Yue Xie, Frank Neumann

Abstract: Evolutionary algorithms have been widely used for a range of stochastic optimization problems in order to address complex real-world optimization problems. We consider the knapsack problem where the profits involve uncertainties. Such a stochastic setting reflects important real-world scenarios where the profit that can be realized is uncertain. We introduce different ways of dealing with stochast… ▽ More Evolutionary algorithms have been widely used for a range of stochastic optimization problems in order to address complex real-world optimization problems. We consider the knapsack problem where the profits involve uncertainties. Such a stochastic setting reflects important real-world scenarios where the profit that can be realized is uncertain. We introduce different ways of dealing with stochastic profits based on tail inequalities such as Chebyshev's inequality and Hoeffding bounds that allow to limit the impact of uncertainties. We examine simple evolutionary algorithms and the use of heavy tail mutation and a problem-specific crossover operator for optimizing uncertain profits. Our experimental investigations on different benchmarks instances show the results of different approaches based on tail inequalities as well as improvements achievable through heavy tail mutation and the problem specific crossover operator. △ Less

Submitted 12 April, 2022; originally announced April 2022.

Coevolutionary Pareto Diversity Optimization

Authors: Aneta Neumann, Denis Antipov, Frank Neumann

Abstract: Computing diverse sets of high quality solutions for a given optimization problem has become an important topic in recent years. In this paper, we introduce a coevolutionary Pareto Diversity Optimization approach which builds on the success of reformulating a constrained single-objective optimization problem as a bi-objective problem by turning the constraint into an additional objective. Our new… ▽ More Computing diverse sets of high quality solutions for a given optimization problem has become an important topic in recent years. In this paper, we introduce a coevolutionary Pareto Diversity Optimization approach which builds on the success of reformulating a constrained single-objective optimization problem as a bi-objective problem by turning the constraint into an additional objective. Our new Pareto Diversity optimization approach uses this bi-objective formulation to optimize the problem while also maintaining an additional population of high quality solutions for which diversity is optimized with respect to a given diversity measure. We show that our standard co-evolutionary Pareto Diversity Optimization approach outperforms the recently introduced DIVEA algorithm which obtains its initial population by generalized diversifying greedy sampling and improving the diversity of the set of solutions afterwards. Furthermore, we study possible improvements of the Pareto Diversity Optimization approach. In particular, we show that the use of inter-population crossover further improves the diversity of the set of solutions. △ Less

Submitted 11 April, 2022; originally announced April 2022.

The Compact Genetic Algorithm Struggles on Cliff Functions

Authors: Frank Neumann, Dirk Sudholt, Carsten Witt

Abstract: The compact genetic algorithm (cGA) is an non-elitist estimation of distribution algorithm which has shown to be able to deal with difficult multimodal fitness landscapes that are hard to solve by elitist algorithms. In this paper, we investigate the cGA on the CLIFF function for which it has been shown recently that non-elitist evolutionary algorithms and artificial immune systems optimize it in… ▽ More The compact genetic algorithm (cGA) is an non-elitist estimation of distribution algorithm which has shown to be able to deal with difficult multimodal fitness landscapes that are hard to solve by elitist algorithms. In this paper, we investigate the cGA on the CLIFF function for which it has been shown recently that non-elitist evolutionary algorithms and artificial immune systems optimize it in expected polynomial time. We point out that the cGA faces major difficulties when solving the CLIFF function and investigate its dynamics both experimentally and theoretically around the cliff. Our experimental results indicate that the cGA requires exponential time for all values of the update strength $K$. We show theoretically that, under sensible assumptions, there is a negative drift when sampling around the location of the cliff. Experiments further suggest that there is a phase transition for $K$ where the expected optimization time drops from $n^{Θ(n)}$ to $2^{Θ(n)}$. △ Less

Submitted 11 April, 2022; originally announced April 2022.

Comments: accepted at GECCO 2022

Defending Active Directory by Combining Neural Network based Dynamic Program and Evolutionary Diversity Optimisation

Authors: Diksha Goel, Max Ward, Aneta Neumann, Frank Neumann, Hung Nguyen, Mingyu Guo

Abstract: Active Directory (AD) is the default security management system for Windows domain networks. We study a Stackelberg game model between one attacker and one defender on an AD attack graph. The attacker initially has access to a set of entry nodes. The attacker can expand this set by strategically exploring edges. Every edge has a detection rate and a failure rate. The attacker aims to maximize thei… ▽ More Active Directory (AD) is the default security management system for Windows domain networks. We study a Stackelberg game model between one attacker and one defender on an AD attack graph. The attacker initially has access to a set of entry nodes. The attacker can expand this set by strategically exploring edges. Every edge has a detection rate and a failure rate. The attacker aims to maximize their chance of successfully reaching the destination before getting detected. The defender's task is to block a constant number of edges to decrease the attacker's chance of success. We show that the problem is #P-hard and, therefore, intractable to solve exactly. We convert the attacker's problem to an exponential sized Dynamic Program that is approximated by a Neural Network (NN). Once trained, the NN provides an efficient fitness function for the defender's Evolutionary Diversity Optimisation (EDO). The diversity emphasis on the defender's solution provides a diverse set of training samples, which improves the training accuracy of our NN for modelling the attacker. We go back and forth between NN training and EDO. Experimental results show that for R500 graph, our proposed EDO based defense is less than 1% away from the optimal defense. △ Less

Submitted 4 January, 2023; v1 submitted 7 April, 2022; originally announced April 2022.

Comments: Added reference [12] on page 3 and 4. Corrected spelling EVC to VEC on page 10

Journal ref: Proceedings of the Genetic and Evolutionary Computation Conference, 2022, Pages 1191 to 1199

Evolutionary Diversity Optimisation for The Traveling Thief Problem

Authors: Adel Nikfarjam, Aneta Neumann, Frank Neumann

Abstract: There has been a growing interest in the evolutionary computation community to compute a diverse set of high-quality solutions for a given optimisation problem. This can provide the practitioners with invaluable information about the solution space and robustness against imperfect modelling and minor problems' changes. It also enables the decision-makers to involve their interests and choose betwe… ▽ More There has been a growing interest in the evolutionary computation community to compute a diverse set of high-quality solutions for a given optimisation problem. This can provide the practitioners with invaluable information about the solution space and robustness against imperfect modelling and minor problems' changes. It also enables the decision-makers to involve their interests and choose between various solutions. In this study, we investigate for the first time a prominent multi-component optimisation problem, namely the Traveling Thief Problem (TTP), in the context of evolutionary diversity optimisation. We introduce a bi-level evolutionary algorithm to maximise the structural diversity of the set of solutions. Moreover, we examine the inter-dependency among the components of the problem in terms of structural diversity and empirically determine the best method to obtain diversity. We also conduct a comprehensive experimental investigation to examine the introduced algorithm and compare the results to another recently introduced framework based on the use of Quality Diversity (QD). Our experimental results show a significant improvement of the QD approach in terms of structural diversity for most TTP benchmark instances. △ Less

Submitted 6 April, 2022; originally announced April 2022.

Comments: To appear at GECCO 2022

Exploring the Feature Space of TSP Instances Using Quality Diversity

Authors: Jakob Bossek, Frank Neumann

Abstract: Generating instances of different properties is key to algorithm selection methods that differentiate between the performance of different solvers for a given combinatorial optimization problem. A wide range of methods using evolutionary computation techniques has been introduced in recent years. With this paper, we contribute to this area of research by providing a new approach based on quality d… ▽ More Generating instances of different properties is key to algorithm selection methods that differentiate between the performance of different solvers for a given combinatorial optimization problem. A wide range of methods using evolutionary computation techniques has been introduced in recent years. With this paper, we contribute to this area of research by providing a new approach based on quality diversity (QD) that is able to explore the whole feature space. QD algorithms allow to create solutions of high quality within a given feature space by splitting it up into boxes and improving solution quality within each box. We use our QD approach for the generation of TSP instances to visualize and analyze the variety of instances differentiating various TSP solvers and compare it to instances generated by a $(μ+1)$-EA for TSP instance generation. △ Less

Submitted 12 April, 2022; v1 submitted 4 February, 2022; originally announced February 2022.

Niching-based Evolutionary Diversity Optimization for the Traveling Salesperson Problem

Authors: Anh Viet Do, Mingyu Guo, Aneta Neumann, Frank Neumann

Abstract: In this work, we consider the problem of finding a set of tours to a traveling salesperson problem (TSP) instance maximizing diversity, while satisfying a given cost constraint. This study aims to investigate the effectiveness of applying niching to maximize diversity rather than simply maintaining it. To this end, we introduce a 2-stage approach where a simple niching memetic algorithm (NMA), der… ▽ More In this work, we consider the problem of finding a set of tours to a traveling salesperson problem (TSP) instance maximizing diversity, while satisfying a given cost constraint. This study aims to investigate the effectiveness of applying niching to maximize diversity rather than simply maintaining it. To this end, we introduce a 2-stage approach where a simple niching memetic algorithm (NMA), derived from a state-of-the-art for multi-solution TSP, is combined with a baseline diversifying algorithm. The most notable feature of the proposed NMA is the use of randomized improvement-first local search instead of 2-opt. Our experiment on TSPLIB instances shows that while the populations evolved by our NMA tend to contain clusters at tight quality constraints, they frequently occupy distant basins of attraction rather than close-by regions, improving on the baseline diversification in terms of sum-sum diversity. Compared to the original NMA, ours, despite its simplicity, finds more distant solutions of higher quality within less running time, by a large margin. △ Less

Submitted 18 April, 2022; v1 submitted 25 January, 2022; originally announced January 2022.

Comments: 14 pages

Practical Fixed-Parameter Algorithms for Defending Active Directory Style Attack Graphs

Authors: Mingyu Guo, Jialiang Li, Aneta Neumann, Frank Neumann, Hung Nguyen

Abstract: Active Directory is the default security management system for Windows domain networks. We study the shortest path edge interdiction problem for defending Active Directory style attack graphs. The problem is formulated as a Stackelberg game between one defender and one attacker. The attack graph contains one destination node and multiple entry nodes. The attacker's entry node is chosen by nature.… ▽ More Active Directory is the default security management system for Windows domain networks. We study the shortest path edge interdiction problem for defending Active Directory style attack graphs. The problem is formulated as a Stackelberg game between one defender and one attacker. The attack graph contains one destination node and multiple entry nodes. The attacker's entry node is chosen by nature. The defender chooses to block a set of edges limited by his budget. The attacker then picks the shortest unblocked attack path. The defender aims to maximize the expected shortest path length for the attacker, where the expectation is taken over entry nodes. We observe that practical Active Directory attack graphs have small maximum attack path lengths and are structurally close to trees. We first show that even if the maximum attack path length is a constant, the problem is still $W[1]$-hard with respect to the defender's budget. Having a small maximum attack path length and a small budget is not enough to design fixed-parameter algorithms. If we further assume that the number of entry nodes is small, then we derive a fixed-parameter tractable algorithm. We then propose two other fixed-parameter algorithms by exploiting the tree-like features. One is based on tree decomposition and requires a small tree width. The other assumes a small number of splitting nodes (nodes with multiple out-going edges). Finally, the last algorithm is converted into a graph convolutional neural network based heuristic, which scales to larger graphs with more splitting nodes. △ Less

Submitted 24 December, 2021; originally announced December 2021.

Run-of-Mine Stockyard Recovery Scheduling and Optimisation for Multiple Reclaimers

Authors: Hirad Assimi, Ben Koch, Chris Garcia, Markus Wagner, Frank Neumann

Abstract: Stockpiles are essential in the mining value chain, assisting in maximising value and production. Quality control of taken minerals from the stockpiles is a major concern for stockpile managers where failure to meet some requirements can lead to losing money. This problem was recently investigated using a single reclaimer, and basic assumptions. This study extends the approach to consider multiple… ▽ More Stockpiles are essential in the mining value chain, assisting in maximising value and production. Quality control of taken minerals from the stockpiles is a major concern for stockpile managers where failure to meet some requirements can lead to losing money. This problem was recently investigated using a single reclaimer, and basic assumptions. This study extends the approach to consider multiple reclaimers in preparing for short and long-term deliveries. The engagement of multiple reclaimers complicates the problem in terms of their interaction in preparing a delivery simultaneously and safety distancing of reclaimers. We also consider more realistic settings, such as handling different minerals with different types of reclaimers. We propose methods that construct a solution step by step to meet precedence constraints for all reclaimers in the stockyard. We study various instances of the problem using greedy algorithms, Ant Colony Optimisation (ACO), and propose an integrated local search method determining an efficient schedule. We fine-tune and compare the algorithms and show that the ACO combined with local search can yield efficient solutions. △ Less

Submitted 22 December, 2021; originally announced December 2021.

On the Use of Quality Diversity Algorithms for The Traveling Thief Problem

Authors: Adel Nikfarjam, Aneta Neumann, Frank Neumann

Abstract: In real-world optimisation, it is common to face several sub-problems interacting and forming the main problem. There is an inter-dependency between the sub-problems, making it impossible to solve such a problem by focusing on only one component. The traveling thief problem~(TTP) belongs to this category and is formed by the integration of the traveling salesperson problem~(TSP) and the knapsack p… ▽ More In real-world optimisation, it is common to face several sub-problems interacting and forming the main problem. There is an inter-dependency between the sub-problems, making it impossible to solve such a problem by focusing on only one component. The traveling thief problem~(TTP) belongs to this category and is formed by the integration of the traveling salesperson problem~(TSP) and the knapsack problem~(KP). In this paper, we investigate the inter-dependency of the TSP and the KP by means of quality diversity~(QD) approaches. QD algorithms provide a powerful tool not only to obtain high-quality solutions but also to illustrate the distribution of high-performing solutions in the behavioural space. We introduce a MAP-Elite based evolutionary algorithm using well-known TSP and KP search operators, taking the TSP and KP score as the behavioural descriptor. Afterwards, we conduct comprehensive experimental studies that show the usefulness of using the QD approach applied to the TTP. First, we provide insights regarding high-quality TTP solutions in the TSP/KP behavioural space. Afterwards, we show that better solutions for the TTP can be obtained by using our QD approach and it can improve the best-known solution for a number of TTP instances used for benchmarking in the literature. △ Less

Submitted 3 January, 2023; v1 submitted 16 December, 2021; originally announced December 2021.

Novelty-Driven Binary Particle Swarm Optimisation for Truss Optimisation Problems

Authors: Hirad Assimi, Frank Neumann, Markus Wagner, Xiaodong Li

Abstract: Topology optimisation of trusses can be formulated as a combinatorial and multi-modal problem in which locating distinct optimal designs allows practitioners to choose the best design based on their preferences. Bilevel optimisation has been successfully applied to truss optimisation to consider topology and sizing in upper and lower levels, respectively. We introduce exact enumeration to rigorous… ▽ More Topology optimisation of trusses can be formulated as a combinatorial and multi-modal problem in which locating distinct optimal designs allows practitioners to choose the best design based on their preferences. Bilevel optimisation has been successfully applied to truss optimisation to consider topology and sizing in upper and lower levels, respectively. We introduce exact enumeration to rigorously analyse the topology search space and remove randomness for small problems. We also propose novelty-driven binary particle swarm optimisation for bigger problems to discover new designs at the upper level by maximising novelty. For the lower level, we employ a reliable evolutionary optimiser to tackle the layout configuration aspect of the problem. We consider truss optimisation problem instances where designers need to select the size of bars from a discrete set with respect to practice code constraints. Our experimental investigations show that our approach outperforms the current state-of-the-art methods and it obtains multiple high-quality solutions. △ Less

Submitted 14 December, 2021; originally announced December 2021.

Time Complexity Analysis of Evolutionary Algorithms for 2-Hop (1,2)-Minimum Spanning Tree Problem

Authors: Feng Shi, Frank Neumann, Jianxin Wang

Abstract: The Minimum Spanning Tree problem (abbr. MSTP) is a well-known combinatorial optimization problem that has been extensively studied by the researchers in the field of evolutionary computing to theoretically analyze the optimization performance of evolutionary algorithms. Within the paper, we consider a constrained version of the problem named 2-Hop (1,2)-Minimum Spanning Tree problem (abbr. 2H-(1,… ▽ More The Minimum Spanning Tree problem (abbr. MSTP) is a well-known combinatorial optimization problem that has been extensively studied by the researchers in the field of evolutionary computing to theoretically analyze the optimization performance of evolutionary algorithms. Within the paper, we consider a constrained version of the problem named 2-Hop (1,2)-Minimum Spanning Tree problem (abbr. 2H-(1,2)-MSTP) in the context of evolutionary algorithms, which has been shown to be NP-hard. Following how evolutionary algorithms are applied to solve the MSTP, we first consider the evolutionary algorithms with search points in edge-based representation adapted to the 2H-(1,2)-MSTP (including the (1+1) EA, Global Simple Evolutionary Multi-Objective Optimizer and its two variants). More specifically, we separately investigate the upper bounds on their expected time (i.e., the expected number of fitness evaluations) to obtain a $\frac{3}{2}$-approximate solution with respect to different fitness functions. Inspired by the special structure of 2-hop spanning trees, we also consider the (1+1) EA with search points in vertex-based representation that seems not so natural for the problem and give an upper bound on its expected time to obtain a $\frac{3}{2}$-approximate solution, which is better than the above mentioned ones. △ Less

Submitted 10 October, 2021; originally announced October 2021.

Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables

Authors: Frank Neumann, Carsten Witt

Abstract: Chance constrained optimization problems allow to model problems where constraints involving stochastic components should only be violated with a small probability. Evolutionary algorithms have been applied to this scenario and shown to achieve high quality results. With this paper, we contribute to the theoretical understanding of evolutionary algorithms for chance constrained optimization. We st… ▽ More Chance constrained optimization problems allow to model problems where constraints involving stochastic components should only be violated with a small probability. Evolutionary algorithms have been applied to this scenario and shown to achieve high quality results. With this paper, we contribute to the theoretical understanding of evolutionary algorithms for chance constrained optimization. We study the scenario of stochastic components that are independent and Normally distributed. Considering the simple single-objective (1+1)~EA, we show that imposing an additional uniform constraint already leads to local optima for very restricted scenarios and an exponential optimization time. We therefore introduce a multi-objective formulation of the problem which trades off the expected cost and its variance. We show that multi-objective evolutionary algorithms are highly effective when using this formulation and obtain a set of solutions that contains an optimal solution for any possible confidence level imposed on the constraint. Furthermore, we prove that this approach can also be used to compute a set of optimal solutions for the chance constrained minimum spanning tree problem. In order to deal with potentially exponentially many trade-offs in the multi-objective formulation, we propose and analyze improved convex multi-objective approaches. Experimental investigations on instances of the NP-hard stochastic minimum weight dominating set problem confirm the benefit of the multi-objective and the improved convex multi-objective approach in practice. △ Less

Submitted 9 August, 2022; v1 submitted 13 September, 2021; originally announced September 2021.

Comments: Conference version has been published at IJCAI 2022