Extending the black-box complexity framework, we consider multistage stochastic optimisation problems under recourse. Such problems ask for a solution to an optimisation problem under uncertainty, where once the uncertainty is (partially) observed, in one or more stages, a stage-by-stage set of 'recourse' actions may be applied to repair the solution. These problems have been studied in the optimisation literature for decades, and applications include multistage portfolio investment, routing under uncertainty, and (dynamic) rescheduling. To facilitate rigorous complexity analysis of these problems in a black-box setting, we develop a precise, broad framework enabling us to describe what information is exchanged between the black-box and the optimisation algorithm, and what solution concept is used. To illustrate the power of the technique, we develop runtime bounds for evolutionary algorithms applied to stochastic optimisation problems with recourse. The theoretical results are complemented by experiments.

International audience

Abstract A big challenge in the knowledge discovery process is to perform data pre-processing, specifically feature selection, on a large amount of data and high dimensional attribute set. A variety of techniques have been proposed in the literature to deal with this challenge with different degrees of success as most of these techniques need further information about the given input data for thresholding, need to specify noise levels or use some feature ranking procedures. To overcome these limitations, rough set theory (RST) can be used to discover the dependency within the data and reduce the number of attributes enclosed in an input data set while using the data alone and requiring no supplementary information. However, when it comes to massive data sets, RST reaches its limits as it is highly computationally expensive. In this paper, we propose a scalable and effective rough set theory-based approach for large-scale data pre-processing, specifically for feature selection, under the Spark framework. In our detailed experiments, data sets with up to 10,000 attributes have been considered, revealing that our proposed solution achieves a good speedup and performs its feature selection task well without sacrificing performance. Thus, making it relevant to big data.

Fitness sharing is a well-known diversity mechanism inspired by the idea that individuals in the population that are close to each other have to share their fitnesses in a similar way to how species in nature occupying the same ecological environment have to share resources. Thus, by derating the fitness of close individuals one hopes to encourage the population to spread out more. Previous runtime analyses of fitness sharing studied a variant where selection was based on populations instead of individuals. We study the conventional fitness sharing mechanism based on individuals and use runtime analysis to highlight its benefits and dangers on the well-known bimodal test problem TwoMax, where diversity is crucial for finding both optima. In contrast to population-based sharing, a (2+1) evolutionary algorithm (EA) with conventional fitness sharing does not guarantee to find both optima in polynomial time even when problem specific knowledge is used to estimate the distance between individuals; however, a (μ+1) EA with μ≥3 always succeeds in expected polynomial time. We further show theoretically and empirically that large offspring populations in (μ+λ) EA s can be detrimental as creating too many offspring in one particular area of the search space can make all individuals in this area go extinct. We conclude the paper with an empirical study indicating that similar conclusions may be drawn when using the genotypic distance that has to be relied upon when no problem specific knowledge is available.

A big challenge in the knowledge discovery process is to perform big data pre-processing; specifically feature selection. To handle this challenge, Rough Set Theory (RST) has been considered as one of the most powerful techniques as it has much to offer for feature selection. To extend its applicability to big data, a distributed version of RST was developed. However, one of its key challenges is the partitioning of the feature search space in the distributed environment while guaranteeing data dependency. In this paper, we propose a new distributed version of RST based on Locality Sensitive Hashing (LSH), named LSH-dRST, for big data pre-processing. LSH-dRST uses LSH to match similar features into the same bucket and maps the generated buckets into partitions to enable the splitting of the universe in a more appropriate way. We compare LSH-dRST to the standard distributed RST technique which is based on a random partitioning of the universe and demonstrate that our LSH-dRST is not only scalable but also more reliable for feature selection; making it more relevant to big data pre-processing. We also demonstrate that our LSH-dRST ensures the partitioning of the high dimensional feature search space in a more reliable way. Hence, guarantees data dependency in the distributed environment, and ensures a lower computational cost.

Big Data reduction is a main point of interest across a wide variety of fields. This domain was further investigated when the difficulty in quickly acquiring the most useful information from the huge amount of data at hand was encountered. To achieve the task of data reduction, specifically feature selection, several state-of-the-art methods were proposed. However, most of them require additional information about the given data for thresholding, noise levels to be specified or they even need a feature ranking procedure. Thus, it seems necessary to think about a more adequate feature selection technique which can extract features using information contained within the dataset alone. Rough Set Theory (RST) can be used as such a technique to discover data dependencies and to reduce the number of features contained in a dataset using the data alone, requiring no additional information. However, despite being a powerful feature selection technique, RST is computationally expensive and only practical for small datasets. Therefore, in this paper, we present a novel efficient distributed Rough Set Theory based algorithm for large-scale data pre-processing under the Spark framework. Our experimental results show the efficient applicability of our RST solution to Big Data without any significant information loss.

Bet-and-run initialisation strategies have been experimentally shown to be beneficial on classical NP-complete problems such as the travelling salesperson problem and minimum vertex cover. We analyse the performance of a bet-and-run restart strategy, where k independent islands run in parallel for t1 iterations, after which the optimisation process continues on only the best-performing island. We define a family of pseudo-Boolean functions, consisting of a plateau and a slope, as an abstraction of real fitness landscapes with promising and deceptive regions. The plateau shows a high fitness, but does not allow for further progression, whereas the slope has a low fitness initially, but does lead to the global optimum. We show that bet-and-run strategies with non-trivial k and t1 are necessary to find the global optimum efficiently. We show that the choice of t1 is linked to properties of the function. Finally, we provide a fixed budget analysis to guide selection of the bet-and-run parameters to maximise expected fitness after t = k · t1 + t2 fitness evaluations.

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.

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.

Dynamic optimisation is an area of application where randomised search heuristics like evolutionary algorithms and artificial immune systems are often successful. The theoretical foundation of this important topic suffers from a lack of a generally accepted analytical framework as well as a lack of widely accepted example problems. This article tackles both problems by discussing necessary conditions for useful and practically relevant theoretical analysis as well as introducing a concrete family of dynamic example problems that draws inspiration from a well-known static example problem and exhibits a bi-stable dynamic. After the stage has been set this way, the framework is made concrete by presenting the results of thorough theoretical and statistical analysis for mutation-based evolutionary algorithms and artificial immune systems.

Dynamic optimisation is an important area of application for evolutionary algorithms and other randomised search heuristics. Theoretical investigations are currently far behind practical successes. Addressing this deficiency a bi-stable dynamic optimisation problem is introduced and the performance of standard evolutionary algorithms and artificial immune systems is assessed. Deviating from the common theoretical perspective that concentrates on the expected time to find a global optimum (again) here the `any time performance' of the algorithms is analysed, i.e., the expected function value at each step. Basis for the analysis is the recently introduced perspective of fixed budget computations. Different dynamic scenarios are considered which are characterised by the length of the stable phases. For each scenario different population sizes are examined. It is shown that the evolutionary algorithms tend to have superior performance in almost all cases.

Different studies have theoretically analyzed the performance of artificial immune systems in the context of optimization. It has been noted that, in comparison with evolutionary algorithms and local search, hypermutations tend to be inferior on typical example functions. These studies have used the expected optimization time as performance criterion and cannot explain why artificial immune systems are popular in spite of these proven drawbacks. Recently, a different perspective for theoretical analysis has been introduced, concentrating on the expected performance within a fixed time frame instead of the expected time needed for optimization. Using this perspective we reevaluate the performance of somatic contiguous hypermutations and inverse fitness-proportional hypermutations in comparison with random local search on one well-known example function in which a random local search is known to be efficient and much more efficient than these hypermutations with respect to the expected optimization time. We prove that, depending on the choice of the initial search point, hypermutations can by far outperform random local search in a given time frame. This insight helps to explain the success of seemingly inefficient mutation operators in practice. Moreover, we demonstrate how one can benefit from these theoretically obtained insights by designing more efficient hybrid search heuristics.

In the literature only lower bounds are available on the approximation ratio of randomised search heuristics for vertex cover in the single-objective problem setting. These analyses are based on the natural vertex-based representation. Inspired by a well-known problem-specific approximation algorithm, we present an analysis of randomised search heuristics using edge-based representations. For the canonical objective function we prove that the performance can still be arbitrarily bad for the (1+1) EA and also RLS, even when using large search neighbourhoods. Adding slightly more information to the objective function turns RLS and the (1+1) EA into efficient 2-approximation algorithms requiring O(m log m) steps where m is the number of edges. Although equivalent in the worst case, such an upper bound on the runtime is at least a linear factor better than that of the multi-objective case for sparse graphs and for graphs with large optimal vertex covers. Furthermore RLS algorithms, that after an improvement do not flip tested bits before trying previously untested ones, guarantee 2-approximations in O(m) steps.

At last year's GECCO a novel perspective for theoretical performance analysis of evolutionary algorithms and other randomised search heuristics was introduced that concentrates on the expected function value after a pre-defined number of steps, called budget. This is significantly different from the common perspective where the expected optimisation time is analysed. While there is a huge body of work and a large collection of tools for the analysis of the expected optimisation time the new fixed budget perspective introduces new analytical challenges. Here it is shown how results on the expected optimisation time that are strengthened by deviation bounds can be systematically turned into fixed budget results. We demonstrate our approach by considering the (1+1) EA on LeadingOnes and significantly improving previous results. We prove that deviating from the expected time by an additive term of ω(n3/2 happens only with probability o(1). This is turned into tight bounds on the function value using the inverse function. We use three, increasingly strong or general approaches to proving the deviation bounds, namely via Chebyshev's inequality, via Chernoff bounds for geometric random variables, and via variable drift analysis.

Evolutionary dynamic optimisation has become one of the most active research areas in evolutionary computation. We consider the BALANCE function for which the poor performance of the (1+1) EA at low frequencies of change has been shown in the literature. We analyse the impact of populations and diversity mechanisms towards the robustness of evolutionary algorithms with respect to frequencies of change. We rigorously prove that for each population size mu, there exists a sufficiently low frequency of change such that the (μ+1) EA without diversity requires expected exponential time. Furthermore we prove that a crowding as well as a genotype diversity mechanism do not help the (μ+1) EA. On the positive side we prove that, independent of the frequency of change, a fitness-diversity mechanism turns the runtime from exponential to polynomial. Finally, we show how a careful use of fitness-sharing together with a crowding mechanism is effective already with a population of size 2.

Extending previous analyses on function classes like linear functions, we analyze how the simple (1+1) evolutionary algorithm optimizes pseudo-Boolean functions that are strictly monotonic. These functions have the property that whenever only 0-bits are changed to 1, then the objective value strictly increases. Contrary to what one would expect, not all of these functions are easy to optimize. The choice of the constant c in the mutation probability p(n) = c/n can make a decisive difference. We show that if c < 1, then the (1+1) EA finds the optimum of every such function in Θ(n log n) iterations. For c = 1, we can still prove an upper bound of O(n(3/2)). However, for c ≥ 16, we present a strictly monotonic function such that the (1+1) EA with overwhelming probability needs 2(Ω(n)) iterations to find the optimum. This is the first time that we observe that a constant factor change of the mutation probability changes the runtime by more than a constant factor.

Randomised search heuristics are used in practice to solve difficult problems where no good problem-specific algorithm is known. They deliver a solution of acceptable quality in reasonable time in many cases. When theoretically analysing the performance of randomised search heuristics one usually considers the average time needed to find an optimal solution or one of a pre-specified approximation quality. This is very different from practice where usually the algorithm is stopped after some time. For a theoretical analysis this corresponds to investigating the quality of the solution obtained after a pre-specified number of function evaluations called budget. Such a perspective is taken here and two simple randomised search heuristics, random local search and the (1+1) evolutionary algorithm, are analysed on simple and well-known example functions. If the budget is significantly smaller than the expected time needed for optimisation the behaviour of the algorithms can be very different depending on the problem at hand. Precise analytical results are proven. They demonstrate novel and interesting challenges in the analysis of randomised search heuristics. The potential of this different perspective to provide a more practically useful theory is shown.

Aging is a general mechanism that is used to increase the diversity of the collection of search points a randomized search heuristic works on. This aims at improving the search heuristic's performance for difficult problems. Examples of randomized search heuristics where aging has been employed include evolutionary algorithms and artificial immune systems. While it is known that randomized search heuristics with aging can be very much superior to randomized search heuristics without aging, recently the point has been made that aging can often be replaced by appropriate restart strategies that are conceptionally simpler and computationally faster. Here, it is demonstrated that aging can achieve performance improvements that restarts cannot. This is done by means of an illustrative example that also involves crossover as an important component. In addition to the theoretical results an empirical study demonstrates the importance of appropriately sized populations

The concept of aging has been introduced and applied in many different variants in many different randomized search heuristics. The most important parameter is the maximal age of search points. Considering static pure aging known from artificial immune systems in the context of simple evolutionary algorithms, it is demonstrated that the choice of this parameter is both, crucial for the performance and difficult to set appropriately. The results are derived in a rigorous fashion and given as theorems with formal proofs. An additional contribution is the presentation of a general method to combine fitness functions into a function with stronger properties than its components. By application of this method we combine a function where the maximal age needs to be sufficiently large with a function where the maximal age needs to be sufficiently small. This yields a function where an appropriate age lies within a very narrow range.

March 01 2009 Ingo Wegener In Special Collection: CogNet Thomas Jansen, Thomas Jansen Ingo Wegener's group, Technische Universität Dortmund Search for other works by this author on: This Site Google Scholar Melanie Schmidt, Melanie Schmidt Ingo Wegener's group, Technische Universität Dortmund Search for other works by this author on: This Site Google Scholar Dirk Sudholt, Dirk Sudholt Ingo Wegener's group, Technische Universität Dortmund Search for other works by this author on: This Site Google Scholar Carsten Witt, Carsten Witt Ingo Wegener's group, Technische Universität Dortmund Search for other works by this author on: This Site Google Scholar Christine Zarges Christine Zarges Ingo Wegener's group, Technische Universität Dortmund Search for other works by this author on: This Site Google Scholar Author and Article Information Thomas Jansen Ingo Wegener's group, Technische Universität Dortmund Melanie Schmidt Ingo Wegener's group, Technische Universität Dortmund Dirk Sudholt Ingo Wegener's group, Technische Universität Dortmund Carsten Witt Ingo Wegener's group, Technische Universität Dortmund Christine Zarges Ingo Wegener's group, Technische Universität Dortmund Online Issn: 1530-9304 Print Issn: 1063-6560 © 2009 by the Massachusetts Institute of Technology2009 Evolutionary Computation (2009) 17 (1): 1–2. https://doi.org/10.1162/evco.2009.17.1.1 Cite Icon Cite Permissions Share Icon Share Facebook Twitter LinkedIn MailTo Views Icon Views Article contents Figures & tables Video Audio Supplementary Data Peer Review Search Site Citation Thomas Jansen, Melanie Schmidt, Dirk Sudholt, Carsten Witt, Christine Zarges; Ingo Wegener. Evol Comput 2009; 17 (1): 1–2. doi: https://doi.org/10.1162/evco.2009.17.1.1 Download citation file: Ris (Zotero) Reference Manager EasyBib Bookends Mendeley Papers EndNote RefWorks BibTex toolbar search Search Dropdown Menu toolbar search search input Search input auto suggest filter your search All ContentAll JournalsEvolutionary Computation Search Advanced Search This content is only available as a PDF. © 2009 by the Massachusetts Institute of Technology2009 Article PDF first page preview Close Modal You do not currently have access to this content.