It is known that the hardness of the (two-way) number partitioning problem (NPP) variant of the subset-sum problem (SSP) depends on the number and distribution of bits in the set of numbers, but beyond this, it is relatively unexplained for the SSP itself. Thus, we look at the solution space of various problem instances of the SSP using fractal analysis. Two methods to determine the dimension are used. Plotting the fractal dimension over the range and distributions of informational bits, we find that it is correlated with this linear model and also moderately correlated to the hardness of the NPP. This suggests that fractal analysis might be a useful tool in understanding the complexity of combinatorial problems and, we believe, may help further understand the hardness in NP. Finally, we introduce a thought experiment derived from the famous Hilbert’s hotel, which we call Hilbert’s hotel with elevators, to intuitively illustrate how the complexity of the solutions space and the computational hardness may relate across combinatorial problems.

The Frequency Fitness Assignment (FFA) method steers evolutionary algorithms by objective rareness instead of objective goodness. Does this mean the size of the combinatorial search space influences its performance when compared to more traditional evolutionary algorithms? Our results suggest it does. To address to which extent the search space size matters for the effectiveness of the FFA-principle, we compare the algorithms on 420 Job Shop Scheduling Problem (JSSP) instances systematically generated in gridwise sizes. The comparison of the FFA-hillclimber and the standard hillclimber is done in both EQ setting, accepting equally good (or fitness-frequent) solutions, and NOEQ setting, only accepting improvement. FFA-hillclimbers are more successful than standard hillclimbers on smaller problem instances, but not on larger ones. It seems that the ratio between jobs and machines, influences the success of the respective algorithms for fixed computational budgets.

Using genetic programming, we fail in evolving an algorithm that correctly multiplies two 5×5 matrices. We do make progress on the issue however, identifying an experimental setting that could potentially lead to such algorithm which until now, has not been successfully done. We discuss earlier work, experimental results and possible ways forward.

The classical compact double-round robin traveling tournament problem (TTP) asks us to schedule the games of n teams in a tournament such that each team plays against every other team twice, once at home and once away (doubleRoundRobin constraint). The maxStreak constraint prevents teams from having more than three consecutive home or away games. The noRepeat constraint demands that, before two teams can play against each other the second time, they must at least play one other game in between. The goal is to find a game plan observing all of these constraints and having the overall shortest travel length. We define a gamepermutation based encoding that allows for representing game plans with arbitrary numbers of constraint violations and tackle the TTP as a bi-objective problem minimizing both the number of constraint violations and the travel length by applying the well-known NSGA-II. We combine both objectives in a lexicographic prioritization scheme and also apply the randomized local search RLS to this single-objective variant of the problem. We realize that Frequency Fitness Assignment (FFA), which makes algorithms invariant under all injective transformations of the objective function value, would also make optimization algorithms invariant under all lexicographic prioritization schemes for multi-objective problems. The FRLS, i.e., the RLS with FFA plugged in, would therefore solve both possible prioritizations of our TTP variants at once. We thus also explore its performance on the TTP. We find that RLS performs surprisingly well and can find game plans without constraint violations reliably until a scale of 36 teams, whereas FRLS and NSGA-II have an advantage on small- and mid-scale problems.

We consider a two-dimensional orthogonal bin packing problem (2BP) where rectangular items are to be placed into rectangular bins such that their edges are parallel to those of the bins with the aim to require as few bins as possible. Two variants of the problem are analyzed. In the 2BP|O|F, the items have a fixed orientation while in the 2BP|R|F, they can be rotated by 90 degrees. We show that on both variants, a simple randomized local search (RLS) has surprisingly good performance – if the objective function guiding the search is defined suitably. In particular, on the 2BP|O|F, the RLS performs on par with more complicated state-of-the-art metaheuristics. We furthermore investigate plugging Frequency Fitness Assignment (FFA) into the RLS, obtaining the FRLS. FFA has improved the RLS performance on several classical N P-hard optimization problems from operations research, including Max-SAT, the Job Shop Scheduling Problem, and the Traveling Salesperson Problem. This paper is the first negative result for FFA: it cannot improve algorithm performance on the 2BP variants studied. This can be explained by the fact that RLS already performs very well on the instances of the 2DPackLib benchmark set used as the basis of our experiments.

NP-hard problems are infamous for having highly varying and extreme runtimes for different problem instances. This study quantifies the instance hardness of NP-hard protein folding problem instances within the HP-model. A custom dataset is generated, consisting of 1000 problem instances of lengths 10, 15, 20, and 25, totalling to 4000 instances. The computational costs for solving a problem instance using a depth-first branch and bound algorithm are measured. The resulting hardness distributions can all be characterized by a probit function regardless of the corresponding protein length. Knowing the instance hardness distribution makes it possible to extrapolate the range of expected runtimes for larger problem instances. As a result, it allows for a prediction before folding a protein.

Genetic algorithms might not be able to solve the HP-protein folding problem because creating random individuals for an initial population is very hard, if not impossible. The reason for this, is that the expected number of constraint violations increases with instance size when randomly sampling individuals, as we will show in an experiment. Thereby, the probability of randomly sampling a valid individual decreases exponentially with instance size. This immediately prohibits resampling, and repair mechanisms might also be non-applicable. Backtracking could generate a valid random individual, but it runs in exponential time, and is therefore also unsuitable. No wonder that previous approaches do not report how (often) random samples are created, and only address small instances. We contrast our findings with TSP, which is also NP-hard, but does not have these problems.

The hardness of the partition problem does not only depend on the number of integers in the problem instance, but also on their magnitude, measured in informational bits. In this work, we will show that also the exact distribution of informational bits among the integers influences the hardness for at least one exact and three heuristic algorithms.

In this work We consider and discuss the problems which come with trying to explain human and machine intelligence.How explainable artificial intelligence research is being carried out, the pitfalls and limitations of current approaches and the bigger question of whether we need explanations for trusting inherently complex and large intelligent systems, whether artificial or not.

Unlike other NP-hard problems, the constraints on the traveling tournament problem are so pressing that it’s hardly possible to randomly generate a valid solution, for example, to use in a genetic algorithm’s initial population. In this study, we randomly generate solutions, assess the numbers of constraint violations, and extrapolate the results to predict the required number of samples for obtaining a single valid solution for any reasonable instance size. As it turns out, these numbers are astronomical, and we finish the study by discussing the feasibility of efficient sampling of valid solutions to various NP-hard problems.

In 2021, evolutionary algorithms found the hardest-known yes and no instances for the Hamiltonian cycle problem. These instances, which show regularity patterns, require a very high number of recursions for the best exact backtracking algorithm (Vandegriend-Culberson), but don't show up in large randomized instance ensembles. In this paper, we will demonstrate that these evolutionarily found instances of the Hamiltonian cycle problem are hard for all major backtracking algorithms, not just the Vandegriend-Culberson. We compare performance of these six algorithms on an ensemble of 91,000 randomized instances plus the evolutionar-ily found instances. These results present a first glance at universal hardness for this NP-complete problem. Algorithms, source code, and input data are all publicly supplied to the community.

In recent years, the field of Evolutionary Algorithms has seen a tremendous increase in novel methods. While these algorithmic innovations often show excellent results on relatively limited domains, they are less often rigorously cross-tested or compared to other state-of-the-art developments. Two of these methods, quite similar in their appearance, are the Fireworks Algorithm and Plant Propagation Algorithm. This study compares the similarities and differences between these two algorithms, from both quantitative and qualitative perspectives, by comparing them on a set of carefully chosen benchmark functions. The Fireworks Algorithm outperforms the Plant Propagation Algorithm on the majority of these, but when the functions are shifted slightly, Plant Propagation gives better results. Reasons behind these surprising differences are presented, and comparison methods for evolutionary algorithms are discussed in a wider context. All source code, graphs, test functions, and algorithmic implementations have been made publicly available for reference and further reuse.