Approximating the Pareto-set of the multi-objective minimum spanning tree problem (moMST) is a challenging task, which was tackled multiple times over the last decades, also by applying evolutionary approaches. A very recent work introduced two novel and strongly problem-tailored sub-graph based mutation operators embedded in NSGA-II. The authors show that these operators excel on a large set of problem instances in terms of convergence speed and approximation quality. Essentially, these operators replace sub-trees of solution candidates by applying Kruskal's well-known MST algorithm to a sub-graph of the input graph reduced to scalar edge weights via weighted-sum scalarisation. This work changes the perspective on the working principle of these operators and proposes a more general construction framework. We show that the before mentioned operators can be embedded into this framework, which 'rewires' sub-trees using a generalisation of Kruskal's algorithm. Additionally, we introduce several improvements to the operators reducing their running time significantly without deteriorating their effectiveness, introduce a novel mutation operator, which utilises the framework in an insertion-first approach (contrary to the other operators), and derive theoretical runtime bounds for all considered operators. A short benchmark study demonstrates the effectiveness of the introduced approach.

Motivated by the emergence of large language models, we conduct a benchmark of sentence embeddings used to represent short texts in textual stream clustering. We achieve comparable results by adapting a non-textual stream clustering algorithm to use sentence embeddings compared to textual stream clustering approaches that use other textual representation mechanisms. Benchmarking datasets with differing degrees of preprocessing are used. The results suggest that the chosen approach using sentence embeddings does not perform as well as previous approaches on preprocessed datasets but has more significant potential on less preprocessed datasets. This highlights the need for new and more application-oriented benchmarking datasets for stream clustering. Further, we conduct a case study in the context of social media campaign detection and show that the approaches are able to find traces of orchestrated activities.

We contribute to the efficient approximation of the Pareto-set for the classical NP-hard multiobjective minimum spanning tree problem (moMST) adopting evolutionary computation. More precisely, by building upon preliminary work, we analyze the neighborhood structure of Pareto-optimal spanning trees and design several highly biased sub-graph-based mutation operators founded on the gained insights. In a nutshell, these operators replace (un)connected sub-trees of candidate solutions with locally optimal sub-trees. The latter (biased) step is realized by applying Kruskal's single-objective MST algorithm to a weighted sum scalarization of a sub-graph. We prove runtime complexity results for the introduced operators and investigate the desirable Pareto-beneficial property. This property states that mutants cannot be dominated by their parent. Moreover, we perform an extensive experimental benchmark study to showcase the operator's practical suitability. Our results confirm that the sub-graph-based operators beat baseline algorithms from the literature even with severely restricted computational budget in terms of function evaluations on four different classes of complete graphs with different shapes of the Pareto-front.

Social media can be a mirror of human interaction, society, and historic disruptions. Their reach enables the global dissemination of information in the shortest possible time and, thus, the individual participation of people worldwide in global events in almost real-time. However, these platforms can be equally efficiently used in information warfare to manipulate human perception and opinion formation. Within this paper, we describe a dataset of raw tweets collected via the Twitter Streaming API in the context of the onset of the war, which Russia started in Ukraine on February 24, 2022. A distinctive feature of the dataset is that it covers the period from one week before to one week after Russia invasion of Ukraine. This paper details the acquisition process and provides first insights into the content of the data stream. In addition, the data has been annotated with availability tags, resulting from rehydration attempts at two points in time: directly after data acquisition and shortly before manuscript submission. This may provide information on Twitter moderation policies. Further, we provide a detailed list of other published dataset covering the same topic. On the content level, we can show that our dataset comprises several distinct topics related to the conflict and conspiracy narratives -- topics that deserve more profound investigation. Therefore, the presented dataset is also made available to the community in an extended version with pseudonymized tweet content upon request.

Abstract Single-objective continuous optimization can be challenging, especially when dealing with multimodal problems. This work sheds light on the effects that multi-objective optimization may have in the single-objective space. For this purpose, we examine the inner mechanisms of the recently developed sophisticated local search procedure SOMOGSA. This method solves multimodal single-objective continuous optimization problems based on first expanding the problem with an additional objective (e.g., a sphere function) to the bi-objective domain and subsequently exploiting local structures of the resulting landscapes. Our study particularly focuses on the sensitivity of this multiobjectivization approach w.r.t. (1) the parametrization of the artificial second objective, as well as (2) the position of the initial starting points in the search space. As SOMOGSA is a modular framework for encapsulating local search, we integrate Nelder–Mead local search as optimizer in the respective module and compare the performance of the resulting hybrid local search to its original single-objective counterpart. We show that the SOMOGSA framework can significantly boost local search by multiobjectivization. Hence, combined with more sophisticated local search and metaheuristics, this may help solve highly multimodal optimization problems in the future.

Recent advances in the visualization of continuous multimodal multi-objective optimization (MMMOO) landscapes brought a new perspective to their search dynamics. Locally eficient (LE) sets, often considered as traps for local search, are rarely isolated in the decision space. Rather, intersections by superposing attraction basins lead to further solution sets that at least partially contain better solutions. The Multi-Objective Gradient Sliding Algorithm (MOGSA) is an algorithmic concept developed to exploit these superpositions. While it has promising performance on many MMMOO problems with linear LE sets, closer analysis of MOGSA revealed that it does not sufficiently generalize to a wider set of test problems. Based on a detailed analysis of shortcomings of MOGSA, we propose a new algorithm, the Multi-Objective Landscape Explorer (MOLE). It is able to efficiently model and exploit LE sets in MMMOO problems. An implementation of MOLE is presented for the bi-objective case, and the practicality of the approach is shown in a benchmarking experiment on the Bi-Objective BBOB testbed.

Traditionally, visualizing benchmark problems is an integral task in the domain of evolutionary algorithms development. Researchers get inspired for new search heuristics by challenges observed in functional landscapes. Moreover, landscape characteristics, features, and even terminology to describe them are derived from visualizations. And most importantly, benchmark designers need visualizations for identifying diverse problems that potentially challenge different aspects of optimization algorithms. As easy as it is to visualize single-objective problems, until recently there were hardly any approaches for gaining similar insights for multi-objective problems. Also, there have been no seamlessly accessible tools to support such visualizations. This article presents a comprehensive overview of the available visualization techniques from literature, including two interactive techniques to visualize 3-D problems, as well as two novel techniques which are suitable to scale some visualization properties to even higher-dimensional spaces. All presented techniques are integrated into a single tool, the moPLOT-dashboard, which enables users to perform landscape analyses in an interactive manner. Finally, the value of the tool and the visualizations is demonstrated in a series of usage scenarios on well-known benchmark problems.

We consider a dynamic bi-objective vehicle routing problem, where a subset of customers ask for service over time. Therein, the distance traveled by a single vehicle and the number of unserved dynamic requests is minimized by a dynamic evolutionary multi-objective algorithm (DEMOA), which operates on discrete time windows (eras). A decision is made at each era by a decision-maker, thus any decision depends on irreversible decisions made in foregoing eras. To understand effects of sequences of decision-making and interactions/dependencies between decisions made, we conduct a series of experiments. More precisely, we fix a set of decision-maker preferences D and the number of eras ntand analyze all |D|ntcombinations of decision-maker options. We find that for random uniform instances (a) the final selected solutions mainly depend on the final decision and not on the decision history, (b) solutions are quite robust with respect to the number of unvisited dynamic customers, and (c) solutions of the dynamic approach can even dominate solutions obtained by a clairvoyant EMOA. In contrast, for instances with clustered customers, we observe a strong dependency on decision-making history as well as more variance in solution diversity.

In practice, e.g. in delivery and service scenarios, Vehicle-Routing-Problems (VRPs) often imply repeated decision making on dynamic customer requests. As in classical VRPs, tours have to be planned short while the number of serviced customers has to be maximized at the same time resulting in a multi-objective problem. Beyond that, however, dynamic requests lead to the need for re-planning of not yet realized tour parts, while already realized tour parts are irreversible. In this paper we study this type of bi-objective dynamic VRP including sequential decision making and concurrent realization of decisions. We adopt a recently proposed Dynamic Evolutionary Multi-Objective Algorithm (DEMOA) for a related VRP problem and extend it to the more realistic (here considered) scenario of multiple vehicles. We empirically show that our DEMOA is competitive with a multi-vehicle offline and clairvoyant variant of the proposed DEMOA as well as with the dynamic single-vehicle approach proposed earlier.

Research has shown that for many single-objective graph problems where optimum solutions are composed of low weight sub-graphs, such as the minimum spanning tree problem (MST), mutation operators favoring low weight edges show superior performance. Intuitively, similar observations should hold for multi-criteria variants of such problems. In this work, we focus on the multi-criteria MST problem. A thorough experimental study is conducted where we estimate the probability of edges being part of non-dominated spanning trees as a function of the edges' non-domination level or domination count, respectively. Building on gained insights, we propose several biased one-edge-exchange mutation operators that differ in the used edge-selection probability distribution (biased towards edges of low rank). Our empirical analysis shows that among different graph types (dense and sparse) and edge weight types (both uniformly random and combinations of Euclidean and uniformly random) biased edge-selection strategies perform superior in contrast to the baseline uniform edge-selection. Our findings are in particular strong for dense graphs.

We continue recent work on the definition of multimodality in multiobjective optimization (MO) and the introduction of a test bed for multimodal MO problems. This goes beyond well-known diversity maintenance approaches but instead focuses on the landscape topology induced by the objective functions. More general multimodal MO problems are considered by allowing ellipsoid contours for single-objective subproblems. An experimental analysis compares two MO algorithms, one that explicitly relies on hypervolume gradient approximation, and one that is based on local search, both on a selection of generated example problems. We do not focus on performance but on the interaction induced by the problems and algorithms, which can be described by means of specific characteristics explicitly designed for the multimodal MO setting. Furthermore, we widen the scope of our analysis by additionally applying visualization techniques in the decision space. This strengthens and extends the foundations for Exploratory Landscape Analysis (ELA) in MO.

We analyze the effects of including local search techniques into a multi-objective evolutionary algorithm for solving a bi-objective orienteering problem with a single vehicle while the two conflicting objectives are minimization of travel time and maximization of the number of visited customer locations. Experiments are based on a large set of specifically designed problem instances with different characteristics and it is shown that local search techniques focusing on one of the objectives only improve the performance of the evolutionary algorithm in terms of both objectives. The analysis also shows that local search techniques are capable of sending locally optimal solutions to foremost fronts of the multi-objective optimization process, and that these solutions then become the leading factors of the evolutionary process.

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.

In this paper, we address the problem of finding well-performing workload exchange policies for decentralized Computational Grids using an Evolutionary Fuzzy System. To this end, we establish a noninvasive collaboration model on the Grid layer which requires minimal information about the participating High Performance and High Throughput Computing (HPC/HTC) centers and which leaves the local resource managers completely untouched. In this environment of fully autonomous sites, independent users are assumed to submit their jobs to the Grid middleware layer of their local site, which in turn decides on the delegation and execution either on the local system or on remote sites in a situation-dependent, adaptive way. We find for different scenarios that the exchange policies show good performance characteristics not only with respect to traditional metrics such as average weighted response time and utilization, but also in terms of robustness and stability in changing environments.

In our work, we utilize a competitive Co-evolutionary Algorithm in order to optimize the parameter set of a Fuzzy System for job exchange in Computational Grids. In this domain, the providers of High Performance Computing (HPC) centers strive for minimizing the response time for their own customers by trying to distribute workload to other sites in the Grid environment. The Fuzzy System is used for steering each site's decisions whether to distribute or accept workload in a beneficial, yet egoistic direction. This scenario is particularly suited for the application of a competitive CA: Grid sites' Fuzzy Systems are modeled as species, which evolve in different populations. While each species tries to minimize the response time for locally submitted jobs, their individuals' fitness is determined within the commonly shared ecosystem. Using real workload traces and Grid setups, we show that the opportunistic cooperation leads to significant improvements for both each Grid site and the overall system.

In our work, we address the problem of workload distribution within a computational grid. In this scenario, users submit jobs to local high performance computing (HPC) systems which are, in turn, interconnected such that the exchange of jobs to other sites becomes possible. Providers are able to avoid local execution of jobs by offering them to other HPC sites. In our implementation, this distribution decision is made by a fuzzy system controller whose parameters can be adjusted to establish different exchange behaviors. In such a system, it is essential that HPC sites can only benefit if the workload is equitably (not necessarily equally) portioned among all participants. However, each site egoistically strives only for the minimization of its own jobs' response times regularly at the expense of other sites. This scenario is particularly suited for the application of a competitive coevolutionary algorithm: the fuzzy systems of the participating HPC sites are modeled as species that evolve in different populations while having to compete within the commonly shared ecosystem. Using real workload traces and grid setups, we show that opportunistic cooperation leads to significant improvements for each HPC site as well as for the overall system.

This paper examines the job exchange between parallel compute sites in a decentralized grid scenario. Here, the local scheduling system remains untouched and continues normal operation. In order to establish the collaboration and interaction between sites in a grid context, a middleware layer that is responsible for the migration of jobs is supplemented. Independent users are assumed to submit their jobs to their site-local middleware layer, which in turn can request jobs for execution from alien sites. The simulation results are obtained using real workload traces and compared to the performance of the EASY Backfilling algorithm in an equal single-site scenario. It is shown that collaboration between site is beneficial for all high utilized participants as it is possible to achieve shorter response times for jobs compared to the best single-site scheduling results.

In this paper, we introduce a methodology for the approximation of optimal solutions for a resource allocation problem in the domain of Grid scheduling on High Performance Computing systems. In detail, we review a real-world scenario with decentralized, equitable, and autonomously acting suppliers of compute power who wish to collaborate in the provision of their resources. We exemplarily apply NSGA-II in order to explore the bounds of maximum achievable benefit. To this end, appropriate encoding schemes and variation operators are developed while the performance is evaluated. The simulations are based upon recordings from real-world Massively Parallel Processing systems that span a period of eleven months and comprise approximately 100,000 jobs. By means of the obtained Pareto front we are able to identify bounds for the maximum benefit of Grid computing in a popular scenario. For the first time, this enables Grid scheduling researchers to rank their developed real-world strategies.

In this paper, we utilize a predator-prey model in order to identify characteristics of single-objective variation operators in the multi-objective problem domain. In detail, we analyze exemplarily Gaussian mutation and simplex recombination to find explanations for the observed behaviorswithin this model. Then, both operators are combinedto a new complex one for the multi-objective case in order to aggregate the identified properties. Finally, we show that (a) characteristic properties can still be observed in the combination and (b) the collaboration of those operators is beneficial for solving an exemplary multi-objective problem regarding convergence and diversity.

In this article, new variation operators for evolutionary multi-objective algorithms (EMOA) are proposed. On the basis of a predator-prey model theoretical considerations as well as empirical results lead to the development of a new recombination operator, which improves the approximation of the set of efficient solutions significantly. Furtheron, it is shown that applying speciation to the analysed model makes it possible to handle even more complex problems.