The Differential Evolution (DE) algorithm is one of the most successful evolutionary computation techniques. However, its structure is not trivially translatable in terms of mathematical transformations that describe its population dynamics. In this work, analytical expressions are developed for the probability of enhancement of individuals after each application of a mutation operator followed by a crossover operation, assuming a population distributed radially around the optimum for the sphere objective function, considering the DE/rand/1/bin and the DE/rand/1/exp algorithm versions. These expressions are validated by numerical experiments. Considering quadratic functions given by f(x)=xTDTDx and populations distributed according to the linear transformation D-1 of a radially distributed population, it is also shown that the expressions still hold in the cases when f(x) is separable (D is diagonal) and when D is any nonsingular matrix and the crossover rate is Cr=1.0. The expressions are employed for the analysis of DE population dynamics. The analysis is extended to more complex situations, reaching rather precise predictions of the effect of problem dimension and of the choice of algorithm parameters.

Comparing combinatorial optimization problems is a difficult task. They are defined using different criteria and terms: weights, flows, distances, etc. In spite of this apparent discrepancy, on many occasions, they tend to produce problem instances with similar properties. One avenue to compare different problems is to project them onto the same space, in order to have homogeneous representations. Expressing the problems in a unified framework could also lead to the discovery of theoretical properties or the design of new algorithms. This article proposes the use of the Fourier transform over the symmetric group as the tool to project different permutation-based combinatorial optimization problems onto the same space. Based on a previous study (Kondor, 2010), which characterized the Fourier coefficients of the quadratic assignment problem, we describe the Fourier coefficients of three other well-known problems: the symmetric and nonsymmetric traveling salesperson problem and the linear ordering problem. This transformation allows us to gain a better understanding of the intersection between the problems, as well as to bound their intrinsic dimension.

The traveling tournament problem is a well-known sports league scheduling problem famous for its practical hardness. Given an even number of teams with symmetric distances between their venues, a double round-robin tournament has to be scheduled minimizing the total travel distances over all teams. We consider the most common constrained variant without repeaters and a streak limit of three, for which we study a beam search approach based on a state-space formulation guided by heuristics derived from different lower bound variants. We solve the arising capacitated vehicle routing subproblems either exactly for small- to medium-sized instances up to 18 teams or heuristically also for larger instances up to 24 teams. In a randomized variant of the search, we employ random team ordering and add small amounts of Gaussian noise to the nodes' guidance for diversification when multiple runs are performed. This allows for a simple yet effective parallelization of the beam search. A final comparison is done on the NL, CIRC, NFL, and GALAXY benchmark instances with 12 to 24 teams, for which we report a mean gap difference to the best known feasible solutions of 1.2% and five new best feasible solutions.

Quality diversity algorithms can be used to efficiently create a diverse set of solutions to inform engineers' intuition. But quality diversity is not efficient in very expensive problems, needing hundreds of thousands of evaluations. Even with the assistance of surrogate models, quality diversity needs hundreds or even thousands of evaluations, which can make its use infeasible. In this study, we try to tackle this problem by using a pre-optimization strategy on a lower-dimensional optimization problem and then map the solutions to a higher-dimensional case. For a use case to design buildings that minimize wind nuisance, we show that we can predict flow features around 3D buildings from 2D flow features around building footprints. For a diverse set of building designs, by sampling the space of 2D footprints with a quality diversity algorithm, a predictive model can be trained that is more accurate than when trained on a set of footprints that were selected with a space-filling algorithm like the Sobol sequence. Simulating only 16 buildings in 3D, a set of 1,024 building designs with low predicted wind nuisance is created. We show that we can produce better machine learning models by producing training data with quality diversity instead of using common sampling techniques. The method can bootstrap generative design in a computationally expensive 3D domain and allow engineers to sweep the design space, understanding wind nuisance in early design phases.

Recently, Rowe and Aishwaryaprajna (2019) introduced a simple majority vote technique that efficiently solves Jump with large gaps, OneMax with large noise, and any monotone function with a polynomial-size image. In this paper, we identify a pathological condition for this algorithm: the presence of spin-flip symmetry in the problem instance. Spin-flip symmetry is the invariance of a pseudo-Boolean function to complementation. Many important combinatorial optimization problems admit objective functions that exhibit this pathology, such as graph problems, Ising models, and variants of propositional satisfiability. We prove that no population size exists that allows the majority vote technique to solve spin-flip symmetric functions of unitation with reasonable probability. To remedy this, we introduce a symmetry-breaking technique that allows the majority vote algorithm to overcome this issue for many landscapes. This technique requires only a minor modification to the original majority vote algorithm to force it to sample strings in {0,1}n from a dimension n-1 hyperplane. We prove a sufficient condition for a spin-flip symmetric function to possess in order for the symmetry-breaking voting algorithm to succeed, and prove its efficiency on generalized TwoMax, a spin-flip symmetric variant of Jump, and families of constructed 3-NAE-SAT and 2-XOR-SAT formulas. We also prove that the algorithm fails on the one-dimensional Ising model, and suggest different techniques for overcoming this. Finally, we present empirical results that explore the tightness of the runtime bounds and the performance of the technique on randomized satisfiability variants.

We present an empirical study of a range of evolutionary algorithms applied to various noisy combinatorial optimisation problems. There are three sets of experiments. The first looks at several toy problems, such as OneMax and other linear problems. We find that UMDA and the Paired-Crossover Evolutionary Algorithm (PCEA) are the only ones able to cope robustly with noise, within a reasonable fixed time budget. In the second stage, UMDA and PCEA are then tested on more complex noisy problems: SubsetSum, Knapsack, and SetCover. Both perform well under increasing levels of noise, with UMDA being the better of the two. In the third stage, we consider two noisy multiobjective problems (CountingOnesCountingZeros and a multiobjective formulation of SetCover). We compare several adaptations of UMDA for multiobjective problems with the Simple Evolutionary Multiobjective Optimiser (SEMO) and NSGA-II. We conclude that UMDA, and its variants, can be highly effective on a variety of noisy combinatorial optimisation, outperforming many other evolutionary algorithms.