Somatic Contiguous Hypermutations (CHM) are a popular variation operator used in artificial immune systems for optimisation tasks. Theoretical studies have shown that CHM operators can lead to considerable speed-ups in the expected optimisation time compared to the traditional standard bit mutation (SBM) operators used in evolutionary computation for both single-objective and multi-objective problems where it is advantageous to mutate large contiguous areas of the genotype representing the candidate solutions. These speed-ups can make the difference between polynomial and exponential runtimes, but come at the expense of the CHM operator being considerably slower than the SBM operator in easy hillclimbing phases of the optimisation process, when small areas of the genotype have to be mutated for progress to be made. In this paper we present a Fast CHM operator that is asymptotically just as fast as traditional SBM for hillclimbing yet maintains the efficacy of the standard CHM operator when large jumps in the search space are required to make progress efficiently. We demonstrate such efficacy on all applications were CHM has been previously studied in the literature.

Recent work has shown that Inverse Tournament Selection operators within steady-state evolutionary algorithms (EAs) allow to control the selective pressure much more accurately than in generational EAs. However, to achieve low selective pressures, large tournament sizes are required which come at the cost of prohibitive expected times for the population to escape from local optima. To this end, we propose a hybrid selection mechanism that leads to considerable speed-ups in the expected time to escape from local optima while permitting to keep the selective pressure arbitrarily low and the use of large population sizes. The mechanism simply switches between Inverse Elitist selection and Uniform selection when it detects that the population is stuck on local optima, and switches back when an improving solution is found. We prove its effectiveness for the TruncatedTwomaxk and RidgeWithBranchesj benchmarks from the literature by providing super-linear speed-ups over the (μ+1) EA with any fixed selective pressure.

In this article, we present the first rigorous theoretical analysis of the generalisation performance of a Geometric Semantic Genetic Programming (GSGP) system. More specifically, we consider a hill-climber using the GSGP Fixed Block Mutation (FBM) operator for the domain of Boolean functions. We prove that the algorithm cannot evolve Boolean conjunctions of arbitrary size that are correct on unseen inputs chosen uniformly at random from the complete truth table i.e., it generalises poorly. Two algorithms based on the Varying Block Mutation (VBM) operator are proposed and analysed to address the issue. We rigorously prove that under the uniform distribution the first one can efficiently evolve any Boolean function of constant size with respect to the number of available variables, while the second one can efficiently evolve general conjunctions or disjunctions of any size without requiring prior knowledge of the target function class. An experimental analysis confirms the theoretical insights for realistic problem sizes and indicates the superiority of the proposed operators also for small parity functions not explicitly covered by the theory.

Previous work has shown that in Artificial Immune Systems (AIS) the best static mutation rates to escape local optima with the ageing operator are far from the optimal ones to do so via large hyper-mutations and vice-versa. In this paper we propose an AIS that automatically adapts the mutation rate during the run to make good use of both operators. We perform rigorous time complexity analyses for standard multimodal benchmark functions with significant characteristics and prove that our proposed algorithm can learn to adapt the mutation rate appropriately such that both ageing and hypermutation are effective when they are most useful for escaping local optima. In particular, the algorithm provably adapts the mutation rate such that it is efficient for the problems where either operator has been proven to be effective in the literature.

Various studies have shown that immune system-inspired hypermutation operators can allow artificial immune systems (AIS) to be very efficient at escaping local optima of multimodal optimization problems. However, this efficiency comes at the expense of considerably slower runtimes during the exploitation phase compared to the standard evolutionary algorithms. We propose modifications to the traditional hypermutations with mutation potential (HMP) that allow them to be efficient at exploitation, as well as maintaining their effective explorative characteristics. Rather than deterministically evaluating fitness after each bit-flip of a hypermutation, we sample the fitness function stochastically with a “parabolic” distribution. This allows the stop at the first constructive mutation (FCM) variant of HMP to reduce the linear amount of wasted function evaluations when no improvement is found to a constant. The stochastic distribution also allows the removal of the FCM mechanism altogether as originally desired in the design of the HMP operators. We rigorously prove the effectiveness of the proposed operators for all the benchmark functions, where the performance of HMP is rigorously understood in the literature. We validate the gained insights to show linear speed-ups for the identification of high-quality approximate solutions to classical NP-Hard problems from combinatorial optimization. We then show the superiority of the HMP operators to the traditional ones in an analysis of the complete standard Opt-IA AIS, where the stochastic evaluation scheme allows HMP and aging operators to work in harmony. Through a comparative performance study of other “fast mutation” operators from the literature, we conclude that a power-law distribution for the parabolic evaluation scheme is the best compromise in black-box scenarios, where little problem knowledge is available.

We analyse the impact of the selective pressure for the global optimisation capabilities of steady-state evolutionary algorithms (EAs). For the standard bimodal benchmark function TwoMax , we rigorously prove that using uniform parent selection leads to exponential runtimes with high probability to locate both optima for the standard ( +1) EA and ( +1) RLS with any polynomial population sizes. However, we prove that selecting the worst individual as parent leads to efficient global optimisation with overwhelming probability for reasonable population sizes. Since always selecting the worst individual may have detrimental effects for escaping from local optima, we consider the performance of stochastic parent selection operators with low selective pressure for a function class called TruncatedTwoMax, where one slope is shorter than the other. An experimental analysis shows that the EAs equipped with inverse tournament selection, where the loser is selected for reproduction and small tournament sizes, globally optimise TwoMax efficiently and effectively escape from local optima of TruncatedTwoMax with high probability. Thus, they identify both optima efficiently while uniform (or stronger) selection fails in theory and in practice. We then show the power of inverse selection on function classes from the literature where populations are essential by providing rigorous proofs or experimental evidence that it outperforms uniform selection equipped with or without a restart strategy. We conclude the article by confirming our theoretical insights with an empirical analysis of the different selective pressures on standard benchmarks of the classical MaxSat and multidimensional knapsack problems.

Abstract It is generally accepted that populations are useful for the global exploration of multi-modal optimisation problems. Indeed, several theoretical results are available showing such advantages over single-trajectory search heuristics. In this paper we provide evidence that evolving populations via crossover and mutation may also benefit the optimisation time for hillclimbing unimodal functions. In particular, we prove bounds on the expected runtime of the standard ( $$\mu +1$$ μ + 1 ) GA for OneMax that are lower than its unary black box complexity and decrease in the leading constant with the population size up to $$\mu =o\left( \sqrt{\log n}\right) $$ μ = o log n . Our analysis suggests that the optimal mutation strategy is to flip two bits most of the time. To achieve the results we provide two interesting contributions to the theory of randomised search heuristics: (1) A novel application of drift analysis which compares absorption times of different Markov chains without defining an explicit potential function. (2) The inversion of fundamental matrices to calculate the absorption times of the Markov chains. The latter strategy was previously proposed in the literature but to the best of our knowledge this is the first time is has been used to show non-trivial bounds on expected runtimes.

Artificial Immune Systems (AIS) employing hypermutations with linear static mutation potential have recently been shown to be very effective at escaping local optima of combinatorial optimisation problems at the expense of being slower during the exploitation phase compared to standard evolutionary algorithms. In this paper, we prove that considerable speed-ups in the exploitation phase may be achieved with dynamic inversely proportional mutation potentials (IPM) and argue that the potential should decrease inversely to the distance to the optimum rather than to the difference in fitness. Afterwards, we define a simple (1+1) Opt-IA that uses IPM hypermutations and ageing for realistic applications where optimal solutions are unknown. The aim of this AIS is to approximate the ideal behaviour of the inversely proportional hypermutations better and better as the search space is explored. We prove that such desired behaviour and related speed-ups occur for a well-studied bimodal benchmark function called TwoMax. Furthermore, we prove that the (1+1) Opt-IA with IPM efficiently optimises a second multimodal function, Cliff, by escaping its local optima while Opt-IA with static mutation potential cannot, thus requires exponential expected runtime in the distance between the local and global optima.

Understanding how the time complexity of evolutionary algorithms (EAs) depend on their parameter settings and characteristics of fitness landscapes is a fundamental problem in evolutionary computation. Most rigorous results were derived using a handful of key analytic techniques, including drift analysis. However, since few of these techniques apply effortlessly to population-based EAs, most time complexity results concern simple EAs, such as the (1+1) EA. We present the level-based theorem, a new technique tailored to population-based processes. It applies to any nonelitist process where offspring are sampled independently from a distribution depending only on the current population. Given conditions on this distribution, our technique provides upper bounds on the expected time until the process reaches a target state. The technique is demonstrated on pseudo-Boolean functions, the sorting problem, and approximation of optimal solutions in combinatorial optimization. The conditions of the theorem are often straightforward to verify, even for genetic algorithms and estimation of distribution algorithms which were considered highly nontrivial to analyze. The proofs for the example applications are available in the supplementary materials. Finally, we prove that the theorem is nearly optimal for the processes considered. Given the information the theorem requires about the process, a much tighter bound cannot be proved.

Explaining to what extent the real power of genetic algorithms (GAs) lies in the ability of crossover to recombine individuals into higher quality solutions is an important problem in evolutionary computation. In this paper we show how the interplay between mutation and crossover can make GAs hillclimb faster than their mutation-only counterparts. We devise a Markov chain framework that allows to rigorously prove an upper bound on the runtime of standard steady state GAs to hillclimb the OneMax function. The bound establishes that the steady-state GAs are 25% faster than all standard bit mutation-only evolutionary algorithms with static mutation rate up to lower order terms for moderate population sizes. The analysis also suggests that larger populations may be faster than populations of size 2. We present a lower bound for a greedy (2 + 1) GA that matches the upper bound for populations larger than 2, rigorously proving that two individuals cannot outperform larger population sizes under greedy selection and greedy crossover up to lower order terms. In complementary experiments the best population size is greater than 2 and the greedy GAs are faster than standard ones, further suggesting that the derived lower bound also holds for the standard steady state (2 + 1) GA.

We present a time complexity analysis of the Opt-IA artificial immune system (AIS). We first highlight the power and limitations of its distinguishing operators (i.e., hypermutations with mutation potential and ageing) by analysing them in isolation. Recent work has shown that ageing combined with local mutations can help escape local optima on a dynamic optimisation benchmark function. We generalise this result by rigorously proving that ageing leads to considerable speed-ups (compared to evolutionary algorithms (EAs)) on the standard Cliff benchmark function both when using local and global mutations. Unless the stop at first constructive mutation (FCM) mechanism is applied, we show that hypermutations require exponential expected runtime to optimise any function with a polynomial number of optima. If instead FCM is used, the expected runtime is at most a linear factor larger than the upper bound achieved for any random local search algorithm using the artificial fitness levels method. Nevertheless, we prove that algorithms using hypermutations can be considerably faster than EAs at escaping local optima. An analysis of the complete Opt-IA reveals that it is efficient on the previously considered functions and highlights problems where the use of the full algorithm is crucial.

Understanding which function classes are easy and which are hard for a given algorithm is a fundamental question for the analysis and design of bio-inspired search heuristics. A natural starting point is to consider the easiest and hardest functions for an algorithm. For the (1+1) EA using standard bit mutation (SBM) it is well known that OneMax is an easiest function with unique optimum while Trap is a hardest. In this paper we extend the analysis of easiest function classes to the contiguous somatic hypermutation (CHM) operator used in artificial immune systems. We define a function MinBlocks and prove that it is an easiest function for the (1+1) EA using CHM, presenting both a runtime and a fixed budget analysis. Since MinBlocks is, up to a factor of 2, a hardest function for standard bit mutations, we consider the effects of combining both operators into a hybrid algorithm. We rigorously prove that by combining the advantages of k operators, several hybrid algorithmic schemes have optimal asymptotic performance on the easiest functions for each individual operator. In particular, the hybrid algorithms using CHM and SBM have optimal asymptotic performance on both OneMax and MinBlocks . We then investigate easiest functions for hybrid schemes and show that an easiest function for a hybrid algorithm is not just a trivial weighted combination of the respective easiest functions for each operator.

Bi-level optimisation problems have gained increasing interest in the field of combinatorial optimisation in recent years. In this paper, we analyse the runtime of some evolutionary algorithms for bi-level optimisation problems. We examine two NP-hard problems, the generalised minimum spanning tree problem and the generalised travelling salesperson problem in the context of parameterised complexity. For the generalised minimum spanning tree problem, we analyse the two approaches presented by Hu and Raidl ( 2012 ) with respect to the number of clusters that distinguish each other by the chosen representation of possible solutions. Our results show that a (1+1) evolutionary algorithm working with the spanning nodes representation is not a fixed-parameter evolutionary algorithm for the problem, whereas the problem can be solved in fixed-parameter time with the global structure representation. We present hard instances for each approach and show that the two approaches are highly complementary by proving that they solve each other's hard instances very efficiently. For the generalised travelling salesperson problem, we analyse the problem with respect to the number of clusters in the problem instance. Our results show that a (1+1) evolutionary algorithm working with the global structure representation is a fixed-parameter evolutionary algorithm for the problem.

Understanding which function classes are easy and which are hard for a given algorithm is a fundamental question for the analysis and design of bio-inspired search heuristics. A natural starting point is to consider the easiest and hardest functions for an algorithm. For the (1+1)EA using standard bit mutation it is well known that OneMax is an easiest function with unique optimum while Trap is a hardest.

Bi-level optimisation problems have gained increasing interest in the field of combinatorial optimisation in recent years. With this paper, we start the runtime analysis of evolutionary algorithms for bi-level optimisation problems. We examine the NP-hard generalised minimum spanning tree problem and analyse the two approaches presented by Hu and Raidl [7] (2012) in the context of parameterised complexity (with respect to the number of clusters) that distinguish each other by the chosen representation of possible solutions. Our results show that a (1+1) EA working with the spanning nodes representation is not a fixed-parameter evolutionary algorithm for the problem, whereas the global structure representation enables to solve the problem in fixed-parameter time. Furthermore, we present hard instances for each approach and show that the two approaches are highly complementary by proving that they solve each other's hard instances very efficiently.