Evolving Diverse Sets of Tours for the Travelling Salesperson Problem - Do, Anh Viet; Bossek, Jakob; Neumann, Aneta; Neumann, Frank (Proceedings of the Genetic and Evolutionary Computation Conference)
Evolving diverse sets of high quality solutions has gained increasing interest in the evolutionary computation literature in recent years. With this paper, we contribute to this area of research by examining evolutionary diversity optimisation approaches for the classical Traveling Salesperson Problem (TSP). We study the impact of using different diversity measures for a given set of tours and the ability of evolutionary algorithms to obtain a diverse set of high quality solutions when adopting these measures. Our studies show that a large variety of diverse high quality tours can be achieved by using our approaches. Furthermore, we compare our approaches in terms of theoretical properties and the final set of tours obtained by the evolutionary diversity optimisation algorithm.
Keywords: diversity maximisation; evolutionary algorithms; travelling salesperson problem

Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem - Roostapour, Vahid; Bossek, Jakob; Neumann, Frank (Proceedings of the 2020 Genetic and Evolutionary Computation Conference)
Evolutionary algorithms (EAs) are general-purpose problem solvers that usually perform an unbiased search. This is reasonable and desirable in a black-box scenario. For combinatorial optimization problems, often more knowledge about the structure of optimal solutions is given, which can be leveraged by means of biased search operators. We consider the Minimum Spanning Tree (MST) problem in a single- and multi-objective version, and introduce a biased mutation, which puts more emphasis on the selection of edges of low rank in terms of low domination number. We present example graphs where the biased mutation can significantly speed up the expected runtime until (Pareto-)optimal solutions are found. On the other hand, we demonstrate that bias can lead to exponential runtime if "heavy" edges are necessarily part of an optimal solution. However, on general graphs in the single-objective setting, we show that a combined mutation operator which decides for unbiased or biased edge selection in each step with equal probability exhibits a polynomial upper bound - as unbiased mutation - in the worst case and benefits from bias if the circumstances are favorable.
Keywords: biased mutation; evolutionary algorithms; minimum spanning tree problem; runtime analysis

Approaches for Collaborative Security Defences in Multi Network Environments - Koning, Ralph; Polevoy, Gleb; Meijer, Lydia; de Laat, Cees; Grosso, Paola (2019 6th IEEE International Conference on Cyber Security and Cloud Computing (CSCloud)/ 2019 5th IEEE International Conference on Edge Computing and Scalable Cloud (EdgeCom))
Resolving distributed attacks benefits from collaboration between networks. We present three approaches for the same multi-domain defensive action that can be applied in such an alliance: 1) Counteract Everywhere, 2) Minimize Countermeasures, and 3) Minimize Propagation. First, we provide a formula to compute efficiency of a defense; then we use this formula to compute the efficiency of the approaches under various circumstances. Finally, we discuss how task execution order and timing influence defense efficiency. Our results show that the Minimize Propagation approach is the most efficient method when defending against the chosen attack.
Keywords: computer network security; multinetwork environments; multidomain defensive action; task execution order; timing influence defense efficiency; distributed attacks; collaborative security defence approach; minimize propagation approach; minimize countermeasure approach; counteract everywhere approach; Conferences; Cloud computing; Computer crime; Edge computing; Security; Defense Approaches; Multi-Domain Defense; Collaborative Defense; Defense Algorithms; Computer Networks

On the Complexity of Local Graph Transformations - Scheideler, Christian; Setzer, Alexander (Proceedings of the 46th International Colloquium on Automata, Languages, and Programming)
We consider the problem of transforming a given graph G_s into a desired graph G_t by applying a minimum number of primitives from a particular set of local graph transformation primitives. These primitives are local in the sense that each node can apply them based on local knowledge and by affecting only its 1-neighborhood. Although the specific set of primitives we consider makes it possible to transform any (weakly) connected graph into any other (weakly) connected graph consisting of the same nodes, they cannot disconnect the graph or introduce new nodes into the graph, making them ideal in the context of supervised overlay network transformations. We prove that computing a minimum sequence of primitive applications (even centralized) for arbitrary G_s and G_t is NP-hard, which we conjecture to hold for any set of local graph transformation primitives satisfying the aforementioned properties. On the other hand, we show that this problem admits a polynomial time algorithm with a constant approximation ratio.
Keywords: Graphs transformations; NP-hardness; approximation algorithms

Runtime Analysis of Randomized Search Heuristics for Dynamic Graph Coloring - Bossek, Jakob; Neumann, Frank; Peng, Pan; Sudholt, Dirk (Proceedings of the Genetic and Evolutionary Computation Conference)
We contribute to the theoretical understanding of randomized search heuristics for dynamic problems. We consider the classical graph coloring problem and investigate the dynamic setting where edges are added to the current graph. We then analyze the expected time for randomized search heuristics to recompute high quality solutions. This includes the (1+1) EA and RLS in a setting where the number of colors is bounded and we are minimizing the number of conflicts as well as iterated local search algorithms that use an unbounded color palette and aim to use the smallest colors and - as a consequence - the smallest number of colors. We identify classes of bipartite graphs where reoptimization is as hard as or even harder than optimization from scratch, i. e. starting with a random initialization. Even adding a single edge can lead to hard symmetry problems. However, graph classes that are hard for one algorithm turn out to be easy for others. In most cases our bounds show that reoptimization is faster than optimizing from scratch. Furthermore, we show how to speed up computations by using problem specific operators concentrating on parts of the graph where changes have occurred.
Keywords: dynamic optimization; evolutionary algorithms; running time analysis; theory

A Theoretical Analysis of the Fuzzy K-Means Problem - Blömer, Johannes; Brauer, Sascha; Bujna, Kathrin (2016 IEEE 16th International Conference on Data Mining (ICDM))
One of the most popular fuzzy clustering techniques is the fuzzy K-means algorithm (also known as fuzzy-c-means or FCM algorithm). In contrast to the K-means and K-median problem, the underlying fuzzy K-means problem has not been studied from a theoretical point of view. In particular, there are no algorithms with approximation guarantees similar to the famous K-means++ algorithm known for the fuzzy K-means problem. This work initiates the study of the fuzzy K-means problem from an algorithmic and complexity theoretic perspective. We show that optimal solutions for the fuzzy K-means problem cannot, in general, be expressed by radicals over the input points. Surprisingly, this already holds for simple inputs in one-dimensional space. Hence, one cannot expect to compute optimal solutions exactly. We give the first (1+eps)-approximation algorithms for the fuzzy K-means problem. First, we present a deterministic approximation algorithm whose runtime is polynomial in N and linear in the dimension D of the input set, given that K is constant, i.e. a polynomial time approximation scheme (PTAS) for fixed K. We achieve this result by showing that for each soft clustering there exists a hard clustering with similar properties. Second, by using techniques known from coreset constructions for the K-means problem, we develop a deterministic approximation algorithm that runs in time almost linear in N but exponential in the dimension D. We complement these results with a randomized algorithm which imposes some natural restrictions on the sought solution and whose runtime is comparable to some of the most efficient approximation algorithms for K-means, i.e. linear in the number of points and the dimension, but exponential in the number of clusters.
Keywords: unsolvability by radicals; clustering; fuzzy k-means; probabilistic method; approximation algorithms; randomized algorithms

Inter-Datacenter Scheduling of Large Data Flows - Cohen, R.; Polevoy, Gleb (Cloud Computing, IEEE Transactions on)
Inter-datacenter transfers of non-interactive but timely large flows over a private (managed) network is an important problem faced by many cloud service providers. The considered flows are non-interactive because they do not explicitly target the end users. However, most of them must be performed on a timely basis and are associated with a deadline. We propose to schedule these flows by a centralized controller, which determines when to transmit each flow and which path to use. Two scheduling models are presented in this paper. In the first, the controller also determines the rate of each flow, while in the second bandwidth is assigned by the network according to the TCP rules. We develop scheduling algorithms for both models and compare their complexity and performance.
Keywords: Approximation algorithms; Approximation methods; Bandwidth; Cloud computing; Routing; Schedules; Scheduling

High-Performance Computing for Scheduling Decision Support: A Parallel Depth-First Search Heuristic - Rauchecker, Gerhard; Schryen, Guido (Australasian Conference on Information Systems)
Many academic disciplines - including information systems, computer science, and operations management - face scheduling problems as important decision making tasks. Since many scheduling problems are NP-hard in the strong sense, there is a need for developing solution heuristics. For scheduling problems with setup times on unrelated parallel machines, there is limited research on solution methods and to the best of our knowledge, parallel computer architectures have not yet been taken advantage of. We address this gap by proposing and implementing a new solution heuristic and by testing different parallelization strategies. In our computational experiments, we show that our heuristic calculates near-optimal solutions even for large instances and that computing time can be reduced substantially by our parallelization approach.
Keywords: scheduling; decision support; heuristic; high performance computing; parallel algorithms

Learning Feature-Parameter Mappings for Parameter Tuning via the Profile Expected Improvement - Bossek, Jakob; Bischl, Bernd; Wagner, Tobias; Rudolph, Günter (Proceedings of the Genetic and Evolutionary Computation Conference)
The majority of algorithms can be controlled or adjusted by parameters. Their values can substantially affect the algorithms’ performance. Since the manual exploration of the parameter space is tedious – even for few parameters – several automatic procedures for parameter tuning have been proposed. Recent approaches also take into account some characteristic properties of the problem instances, frequently termed instance features. Our contribution is the proposal of a novel concept for feature-based algorithm parameter tuning, which applies an approximating surrogate model for learning the continuous feature-parameter mapping. To accomplish this, we learn a joint model of the algorithm performance based on both the algorithm parameters and the instance features. The required data is gathered using a recently proposed acquisition function for model refinement in surrogate-based optimization: the profile expected improvement. This function provides an avenue for maximizing the information required for the feature-parameter mapping, i.e., the mapping from instance features to the corresponding optimal algorithm parameters. The approach is validated by applying the tuner to exemplary evolutionary algorithms and problems, for which theoretically grounded or heuristically determined feature-parameter mappings are available.
Keywords: evolutionary algorithms; model-based optimization; parameter tuning

Evaluation of a Multi-Objective EA on Benchmark Instances for Dynamic Routing of a Vehicle - Meisel, Stephan; Grimme, Christian; Bossek, Jakob; Wölck, Martin; Rudolph, Günter; Trautmann, Heike (Proceedings of the Genetic and Evolutionary Computation Conference)
We evaluate the performance of a multi-objective evolutionary algorithm on a class of dynamic routing problems with a single vehicle. In particular we focus on relating algorithmic performance to the most prominent characteristics of problem instances. The routing problem considers two types of customers: mandatory customers must be visited whereas optional customers do not necessarily have to be visited. Moreover, mandatory customers are known prior to the start of the tour whereas optional customers request for service at later points in time with the vehicle already being on its way. The multi-objective optimization problem then results as maximizing the number of visited customers while simultaneously minimizing total travel time. As an a-posteriori evaluation tool, the evolutionary algorithm aims at approximating the related Pareto set for specifically designed benchmarking instances differing in terms of number of customers, geographical layout, fraction of mandatory customers, and request times of optional customers. Conceptional and experimental comparisons to online heuristic procedures are provided.
Keywords: combinatorial optimization; metaheuristics; multi-objective optimization; online algorithms; transportation