Approaches to Improve Fairness when Deploying AI-based Algorithms in Hiring – Using a Systematic Literature Review to Guide Future Research - Rieskamp, Jonas; Hofeditz, Lennart; Mirbabaie, Milad; Stieglitz, Stefan (Proceedings of the Annual Hawaii International Conference on System Sciences (HICSS))
Algorithmic fairness in Information Systems (IS) is a concept that aims to mitigate systematic discrimination and bias in automated decision-making. However, previous research argued that different fairness criteria are often incompatible. In hiring, AI is used to assess and rank applicants according to their fit for vacant positions. However, various types of bias also exist for AI-based algorithms (e.g., using biased historical data). To reduce AI’s bias and thereby unfair treatment, we conducted a systematic literature review to identify suitable strategies for the context of hiring. We identified nine fundamental articles in this context and extracted four types of approaches to address unfairness in AI, namely pre-process, in-process, post-process, and feature selection. Based on our findings, we (a) derived a research agenda for future studies and (b) proposed strategies for practitioners who design and develop AIs for hiring purposes.
Keywords: fairness in AI; SLR; hiring; AI implementation; AI-based algorithms

On the Impact of Basic Mutation Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem - Bossek, Jakob; Neumann, Aneta; Neumann, Frank (Proceedings of the Genetic and Evolutionary Computation Conference)
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.
Keywords: dynamic optimization; evolutionary algorithms; re-optimization; weighted traveling salesperson problem

Do Additional Target Points Speed Up Evolutionary Algorithms? - Bossek, Jakob; Sudholt, Dirk (Theoretical Computer Science)
Most runtime analyses of randomised search heuristics focus on the expected number of function evaluations to find a unique global optimum. We ask a fundamental question: if additional search points are declared optimal, or declared as desirable target points, do these additional optima speed up evolutionary algorithms? More formally, we analyse the expected hitting time of a target set OPT{$\cup$}S where S is a set of non-optimal search points and OPT is the set of optima and compare it to the expected hitting time of OPT. We show that the answer to our question depends on the number and placement of search points in S. For all black-box algorithms and all fitness functions with polynomial expected optimisation times we show that, if additional optima are placed randomly, even an exponential number of optima has a negligible effect on the expected optimisation time. Considering Hamming balls around all global optima gives an easier target for some algorithms and functions and can shift the phase transition with respect to offspring population sizes in the (1,{$λ$}) EA on OneMax. However, for the one-dimensional Ising model the time to reach Hamming balls of radius (1/2-{$ϵ$})n around optima does not reduce the asymptotic expected optimisation time in the worst case. Finally, on functions where search trajectories typically join in a single search point, turning one search point into an optimum drastically reduces the expected optimisation time.
Keywords: Evolutionary algorithms; pseudo-Boolean functions; runtime analysis

Pushing the Limits of Computational Combinatorial Constructions (Dagstuhl Seminar 23161) - Moura, Lucia; Nakic, Anamari; Östergård, Patric; Wassermann, Alfred; Weiß, Charlene
This report documents the program and the outcomes of Dagstuhl Seminar 23161 "Pushing the Limits of Computational Combinatorial Constructions". In this Dagstuhl Seminar, we focused on computational methods for challenging problems in combinatorial construction. This includes algorithms for construction of combinatorial objects with prescribed symmetry, for isomorph-free exhaustive generation, and for combinatorial search. Examples of specific algorithmic techniques are tactical decomposition, the Kramer-Mesner method, algebraic methods, graph isomorphism software, isomorph-free generation, clique-finding methods, heuristic search, SAT solvers, and combinatorial optimization. There was an emphasis on problems involving graphs, designs and codes, also including topics in related fields such as finite geometry, graph decomposition, Hadamard matrices, Latin squares, and q-analogs of designs and codes.
Keywords: automorphism groups; combinatorial algorithms; finite geometries; subspace designs

Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem - Nikfarjam, Adel; Neumann, Aneta; Bossek, Jakob; Neumann, Frank (Parallel Problem Solving from Nature (PPSN XVII))
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 literature.
Keywords: Co-evolutionary algorithms; Evolutionary diversity optimisation; Quality diversity; Traveling thief problem

A continuous strategy for collisionless gathering - Li, Shouwei; Markarian, Christine; Meyer auf der Heide, Friedhelm; Podlipyan, Pavel (Theoretical Computer Science)
Over the past decades, the Gathering problem, which asks to gather a group of robots in finite time given some restrictions, has been intensively studied. In this paper, we are given a group of n autonomous, dimensionless, deterministic, and anonymous robots, with bounded viewing range. Assuming a continuous time model, the goal is to gather these robots into one point in finite time. We introduce a simple convergence criterion that defines a new class of algorithms which perform gathering in O(nd) time, where d is the diameter of the initial robot configuration. We show that some gathering algorithms in the literature belong to this class and propose two new algorithms that belong to this class and have quadratic running time, namely, Go-To-The-Relative-Center algorithm (GTRC) and Safe-Go-To-The-Relative-Center algorithm (S-GTRC). We prove that the latter can perform gathering without collision by using a slightly more complex robot model: non oblivious, chiral, and luminous (i.e. robots have observable external memory, as in [8]). We also consider a variant of the Gathering problem, the Near-Gathering problem, in which robots must get close to each other without colliding. We show that S-GTRC solves the Near-Gathering problem in quadratic time and assumes a weaker robot model than the one assumed in the current state-of-the-art.
Keywords: Local algorithms; Distributed algorithms; Collisionless gathering; Mobile robots; Multiagent system

The impact of the Gabriel subgraph of the visibility graph on the gathering of mobile autonomous robots - Li, Shouwei; Meyer auf der Heide, Friedhelm; Podlipyan, Pavel (Theoretical Computer Science)
In this paper, we reconsider the well-known discrete, round-based Go-To-The-Center algorithm due to Ando, Suzuki, and Yamashita [2] for gathering n autonomous mobile robots with limited viewing range in the plane. Remarquably, this algorithm exploits the fact that during its execution, many collisions of robots occur. Such collisions are interpreted as a success because it is assumed that such collided robots behave the same from now on. This is acceptable under the assumption that each robot is represented by a single point. Otherwise, collisions should be avoided. In this paper, we consider a continuous Go-To-The-Center algorithm in which the robots continuously observe the positions of their neighbors and adapt their speed (assuming a speed limit) and direction. Our first results are time bounds of O(n2) for gathering in two dimensions Euclidean space, and Θ(n) for the one dimension. Our main contribution is the introduction and evaluation of a continuous algorithm which performs Go-To-The-Center considering only the neighbors of a robot with respect to the Gabriel subgraph of the visibility graph, i.e. Go-To-The-Gabriel-Center algorithm. We show that this modification still correctly executes gathering in one and two dimensions, with the same time bounds as above. Simulations exhibit a severe difference of the behavior of the Go-To-The-Center and the Go-To-The-Gabriel-Center algorithms: Whereas lots of collisions occur during a run of the Go-To-The-Center algorithm, typically only one, namely the final collision occurs during a run of the Go-To-The-Gabriel-Center algorithm. We can prove this “collisionless property” of the Go-To-The-Gabriel-Center algorithm for one dimension. In two-dimensional Euclidean space, we conjecture that the “collisionless property” holds for almost every initial configuration. We support our conjecture with measurements obtained from the simulation where robots execute both continuous Go-To-The-Center and Go-To-The-Gabriel-Center algorithms.
Keywords: Local algorithms; Distributed algorithms; Collisionless gathering; Mobile robots; Multiagent system

Peeking beyond peaks: Challenges and research potentials of continuous multimodal multi-objective optimization - Grimme, Christian; Kerschke, Pascal; Aspar, Pelin; Trautmann, Heike; Preuss, Mike; Deutz, André H.; Wang, Hao; Emmerich, Michael (Computers & Operations Research)
Multi-objective (MO) optimization, i.e., the simultaneous optimization of multiple conflicting objectives, is gaining more and more attention in various research areas, such as evolutionary computation, machine learning (e.g., (hyper-)parameter optimization), or logistics (e.g., vehicle routing). Many works in this domain mention the structural problem property of multimodality as a challenge from two classical perspectives: (1) finding all globally optimal solution sets, and (2) avoiding to get trapped in local optima. Interestingly, these streams seem to transfer many traditional concepts of single-objective (SO) optimization into claims, assumptions, or even terminology regarding the MO domain, but mostly neglect the understanding of the structural properties as well as the algorithmic search behavior on a problem’s landscape. However, some recent works counteract this trend, by investigating the fundamentals and characteristics of MO problems using new visualization techniques and gaining surprising insights. Using these visual insights, this work proposes a step towards a unified terminology to capture multimodality and locality in a broader way than it is usually done. This enables us to investigate current research activities in multimodal continuous MO optimization and to highlight new implications and promising research directions for the design of benchmark suites, the discovery of MO landscape features, the development of new MO (or even SO) optimization algorithms, and performance indicators. For all these topics, we provide a review of ideas and methods but also an outlook on future challenges, research potential and perspectives that result from recent developments.
Keywords: Multimodal optimization; Multi-objective continuous optimization; Landscape analysis; Visualization; Benchmarking; Theory; Algorithms

Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms - Bossek, Jakob; Neumann, Aneta; Neumann, Frank (Proceedings of the Genetic and Evolutionary Computation Conference)
In practise, it is often desirable to provide the decision-maker with a rich set of diverse solutions of decent quality instead of just a single solution. In this paper we study evolutionary diversity optimization for the knapsack problem (KP). Our goal is to evolve a population of solutions that all have a profit of at least (1 - {$ϵ$}) {$·$} OPT, where OPT is the value of an optimal solution. Furthermore, they should differ in structure with respect to an entropy-based diversity measure. To this end we propose a simple ({$μ$} + 1)-EA with initial approximate solutions calculated by a well-known FPTAS for the KP. We investigate the effect of different standard mutation operators and introduce biased mutation and crossover which puts strong probability on flipping bits of low and/or high frequency within the population. An experimental study on different instances and settings shows that the proposed mutation operators in most cases perform slightly inferior in the long term, but show strong benefits if the number of function evaluations is severely limited.
Keywords: evolutionary algorithms; evolutionary diversity optimization; knapsack problem; tailored operators

Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem - Bossek, Jakob; Neumann, Frank (Proceedings of the Genetic and Evolutionary Computation Conference)
In the area of evolutionary computation the calculation of diverse sets of high-quality solutions to a given optimization problem has gained momentum in recent years under the term evolutionary diversity optimization. Theoretical insights into the working principles of baseline evolutionary algorithms for diversity optimization are still rare. In this paper we study the well-known Minimum Spanning Tree problem (MST) in the context of diversity optimization where population diversity is measured by the sum of pairwise edge overlaps. Theoretical results provide insights into the fitness landscape of the MST diversity optimization problem pointing out that even for a population of {$μ$} = 2 fitness plateaus (of constant length) can be reached, but nevertheless diverse sets can be calculated in polynomial time. We supplement our theoretical results with a series of experiments for the unconstrained and constraint case where all solutions need to fulfill a minimal quality threshold. Our results show that a simple ({$μ$} + 1)-EA can effectively compute a diversified population of spanning trees of high quality.
Keywords: evolutionary algorithms; evolutionary diversity optimization; minimum spanning tree; runtime analysis