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.

Robust optimization over time (ROOT) is the combination of robust optimization and dynamic optimization. In ROOT, frequent changes to deployed solutions are undesirable, which can be due to the high cost of switching between deployed solutions, limitations on the resources required to deploy new solutions, and/or the system’s inability to tolerate frequent changes in the deployed solutions. ROOT is dedicated to the study and development of algorithms capable of dealing with the implications of deploying or maintaining solutions over longer time horizons involving multiple environmental changes. This paper presents an in-depth review of the research on ROOT. The overarching aim of this survey is to help researchers gain a broad perspective on the current state of the field, what has been achieved so far, and the existing challenges and pitfalls. This survey also aims to improve accessibility and clarity by standardizing terminology and unifying mathematical notions used across the field, providing explicit mathematical formulations of definitions, and improving many existing mathematical descriptions. Moreover, we classify ROOT problems based on two ROOT-specific criteria: the requirements for changing or keeping deployed solutions and the number of deployed solutions. This classification helps researchers gain a better understanding of the characteristics and requirements of ROOT problems, which is crucial to systematic algorithm design and benchmarking. Additionally, we classify ROOT methods based on the approach they use for finding robust solutions and provide a comprehensive review of them. This survey also reviews ROOT benchmarks and performance indicators. Finally, we identify several future research directions.

Many real-world optimization problems are dynamic. The field of robust optimization over time (ROOT) deals with dynamic optimization problems in which frequent changes of the deployed solution are undesirable. This can be due to the high cost of switching the deployed solutions, the limitation of the needed resources to deploy such new solutions, and/or the system being intolerant towards frequent changes of the deployed solution. In the considered ROOT problems in this article, the main goal is to find solutions that maximize the average number of environments where they remain acceptable. In the state-of-the-art methods developed to tackle these problems, the decision makers/metrics used to select solutions for deployment mostly make simplifying assumptions about the problem instances. Besides, the current methods all use the population control components which have been originally designed for tracking the global optimum over time without taking any robustness considerations into account. In this paper, a multi-population ROOT method is proposed with two novel components: a robustness estimation component that estimates robustness of the promising regions, and a dual-mode computational resource allocation component to manage sub-populations by taking several factors, including robustness, into account. Our experimental results demonstrate the superiority of the proposed method over other state-of-the-art approaches.

Population clustering methods, which consider the position and fitness of individuals to form sub-populations in multi-population algorithms, have shown high efficiency in tracking the moving global optimum in dynamic optimization problems. However, most of these methods use a fixed population size, making them inflexible and inefficient when the number of promising regions is unknown. The lack of a functional relationship between the population size and the number of promising regions significantly degrades performance and limits an algorithm’s agility to respond to dynamic changes. To address this issue, we propose a new species-based particle swarm optimization with adaptive population size and number of sub-populations for solving dynamic optimization problems. The proposed algorithm also benefits from a novel systematic adaptive deactivation component that, unlike the previous deactivation components, adapts the computational resource allocation to the sub-populations by considering various characteristics of both the problem and the sub-populations. We evaluate the performance of our proposed algorithm for the Generalized Moving Peaks Benchmark and compare the results with several peer approaches. The results indicate the superiority of the proposed method.

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.

Many real-world optimization problems are dynamic. The field of dynamic optimization deals with such problems where the search space changes over time. In this two-part article, we present a comprehensive survey of the research in evolutionary dynamic optimization for single-objective unconstrained continuous problems over the last two decades. In Part A of this survey, we propose a new taxonomy for the components of dynamic optimization algorithms (DOAs), namely, convergence detection, change detection, explicit archiving, diversity control, and population division and management. In comparison to the existing taxonomies, the proposed taxonomy covers some additional important components, such as convergence detection and computational resource allocation. Moreover, we significantly expand and improve the classifications of diversity control and multipopulation methods, which are underrepresented in the existing taxonomies. We then provide detailed technical descriptions and analysis of different components according to the suggested taxonomy. Part B of this survey provides an in-depth analysis of the most commonly used benchmark problems, performance analysis methods, static optimization algorithms used as the optimization components in the DOAs, and dynamic real-world applications. Finally, several opportunities for future work are pointed out.

This article presents the second Part of a two-Part survey that reviews evolutionary dynamic optimization (EDO) for single-objective unconstrained continuous problems over the last two decades. While in the first part, we reviewed the components of dynamic optimization algorithms (DOAs); in this part, we present an in-depth review of the most commonly used benchmark problems, performance analysis methods, static optimization methods used in the framework of DOAs, and real-world applications. Compared to the previous works, this article provides a new taxonomy for the benchmark problems used in the field based on their baseline functions and dynamics. In addition, this survey classifies the commonly used performance indicators into fitness/error-based and efficiency-based ones. Different types of plots used in the literature for analyzing the performance and behavior of algorithms are also reviewed. Furthermore, the static optimization algorithms that are modified and utilized in the framework of DOAs as the optimization components are covered. We then comprehensively review some real-world dynamic problems that are optimized by EDO methods. Finally, some challenges and opportunities are pointed out for future directions.

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.

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.