Search

International audience; The Zoetrope Genetic Programming (ZGP) algorithm is based on an original representation for mathematical expressions, targeting evolutionary symbolic regression. The zoetropic representation uses repeated fusion operations between partial expressions, starting from the terminal set. Repeated fusions within an individual gradually generate more complex expressions, ending up in what can be viewed as new features. These features are then linearly combined to best fit the training data. ZGP individuals then undergo specific crossover and mutation operators, and selection takes place between parents and offspring. ZGP is validated using a large number of public domain regression datasets, and compared to other symbolic regression algorithms, as well as to traditional machine learning algorithms. ZGP reaches state-of-theart performance with respect to both types of algorithms, and demonstrates a low computational time compared to other symbolic regression approaches.

The study of semantics in Genetic Programming (GP) has increased dramatically over the last years due to the fact that researchers tend to report a performance increase in GP when semantic diversity is promoted. However, the adoption of semantics in Evolutionary Multi-objective Optimisation (EMO), at large, and in Multi-objective GP (MOGP), in particular, has been very limited and this paper intends to fill this challenging research area. We propose a mechanism wherein a semantic-based distance is used instead of the widely known crowding distance and is also used as an objective to be optimised. To this end, we use two well-known EMO algorithms: NSGA-II and SPEA2. Results on highly unbalanced binary classification tasks indicate that the proposed approach produces more and better results than the rest of the three other approaches used in this work, including the canonical aforementioned EMO algorithms.

In Genetic Programming (GP), the fitness of individuals is normally computed by using a set of fitness cases (FCs). Research on the use of FCs in GP has primarily focused on how to reduce the size of these sets to, for instance, reduce the fitness evaluation time. However, often, only a small set of FCs is available and there is no need to reduce it. In this work, we are interested in using the whole FCs set, but rather than adopting the commonly used GP approach of presenting the entire set of FCs to the system from the beginning of the search, referred as static FCs, we allow the GP system to build it over time, named as dynamic FCs, to make the search more amenable. Moreover, to the best of our knowledge, there is no study on the use/impact of FCs in Dynamic Optimisation Problems (DOPs). To this end, we also propose the Kendall Tau Distance (KTD) approach, which quantifies pairwise dissimilarities among two lists of fitness values. KTD aims to capture the degree of a change in DOPs and we use this to promote diversity, which has constantly reported to be beneficial in a dynamic setting. Results on eight symbolic regression functions indicate that both approaches are highly beneficial in GP.

In this paper, three extensions of the BI-population Covariance Matrix Adaptation Evolution Strategy with weighted active covariance matrix update (BIPOP-aCMA-ES) are investigated. First, to address expensive optimization, we benchmark a recently proposed extension of the self-adaptive surrogate-assisted CMA-ES which benefits from more intensive surrogate model exploitation (BIPOP-saACM-k). Second, to address separable optimization, we propose a hybrid of BIPOP-aCMA-ES and STEP algorithm with coordinate-wise line search (BIPOP-aCMA-STEP). Third, we propose HCMA, a hybrid of BIPOP-saACM-k, STEP and NEWUOA to benefit both from surrogate models and line searches. All algorithms were tested on the noiseless BBOB testbed using restarts till a total number of function evaluations of 106n was reached, where n is the dimension of the function search space. The comparison shows that BIPOP-saACM-k outperforms its predecessor BIPOP-saACM up to a factor of 2 on ill-conditioned problems, while BIPOP-aCMA-STEP outperforms the original BIPOP-based algorithms on separable functions. The hybrid HCMA algorithm demonstrates the best overall performance compared to the best algorithms of the BBOB-2009, BBOB-2010 and BBOB-2012 when running for more than 100n function evaluations.

Nowadays, with the increasing traffic density of the European airspace, air traffic management includes the planning and monitoring of the capacity of the network as a way to facilitate the work of the air traffic controllers. This article presents the use of an evolutionary multiobjective algorithm for optimizing a schedule on the time of overflight of the waypoints. The evaluation function is defined as a probabilistic model, which reports the expected delays and the expected congestion giving the schedule. We believe that the robustness of such decision-support tool can only arise from a precise modeling of the uncertainty at a trajectory level and to propagate it to the sector level, allowing us to compute the probability of congestion. This paper gives the outline of the probabilistic model and the way it is used with an evolutionary algorithm in order to optimize the schedule. The proposed approach is tested against two artificial instances where one consists of 300 aircraft and 16 sectors.

This paper proposes a self-adaptation mechanism to manage the resources allocated to the different species comprising a cooperative coevolutionary algorithm. The proposed approach relies on a dynamic extension to the well-known multi-armed bandit framework. At each iteration, the dynamic multi-armed bandit makes a decision on which species to evolve for a generation, using the history of progress made by the different species to guide the decisions. We show experimentally, on a benchmark and a real-world problem, that evolving the different populations at different paces allows not only to identify solutions more rapidly, but also improves the capacity of cooperative coevolution to solve more complex problems., Accepted at GECCO 2013

Learn-and-Optimize (LaO) is a generic surrogate based method for parameter tuning combining learning and optimization. In this paper LaO is used to tune Divide-and-Evolve (DaE), an Evolutionary Algorithm for AI Planning. The LaO framework makes it possible to learn the relation between some features describing a given instance and the optimal parameters for this instance, thus it enables to extrapolate this knowledge to unknown instances in the same domain. Moreover, the learned relation is used as a surrogate-model to accelerate the search for the optimal parameters. It hence becomes possible to solve intra-domain and extra-domain generalization in a single framework. The proposed implementation of LaO uses an Artificial Neural Network for learning the mapping between features and optimal parameters, and the Covariance Matrix Adaptation Evolution Strategy for optimization. Results demonstrate that LaO is capable of improving the quality of the DaE results even with only a few iterations. The main limitation of the DaE case-study is the limited amount of meaningful features that are available to describe the instances. However, the learned model reaches almost the same performance on the test instances, which means that it is capable of generalization.

International audience; Adaptive Operator Selection (AOS) turns the impacts of the applications of variation operators into Operator Selection through a Credit Assignment mechanism. However, most Credit Assignment schemes make direct use of the fitness gain between parent and offspring. A first issue is that the Operator Selection technique that uses such kind of Credit Assignment is likely to be highly dependent on the a priori unknown bounds of the fitness function. Additionally, these bounds are likely to change along evolution, as fitness gains tend to get smaller as convergence occurs. Furthermore, and maybe more importantly, a fitness-based credit assignment forbid any invariance by monotonous transformation of the fitness, what is a usual source of robustness for comparison-based Evolutionary Algorithms. In this context, this paper proposes two new Credit Assignment mechanisms, one inspired by the Area Under the Curve paradigm, and the other close to the Sum of Ranks. Using fitness improvement as raw reward, and directly coupled to a Multi-Armed Bandit Operator Selection Rule, the resulting AOS obtain very good performances on both the OneMax problem and some artificial scenarios, while demonstrating their robustness with respect to hyper-parameter and fitness transformations. Furthermore, using fitness ranks as raw reward results in a fully comparison-based AOS with reasonable performances.

International audience; The choice of which of the available strategies should be used within the Differential Evolution algorithm for a given problem is not trivial, besides being problem-dependent and very sensitive with relation to the algorithm performance. This decision can be made in an autonomous way, by the use of the Adaptive Strategy Selection paradigm, that continuously selects which strategy should be used for the next offspring generation, based on the performance achieved by each of the available ones on the current optimization process, i.e., while solving the problem. In this paper, we use the BBOB-2010 noiseless benchmarking suite to better empirically validate a comparison-based technique recently proposed to do so, the Fitness-based Area-Under-Curve Bandit, referred to as F-AUC-Bandit. It is compared with another recently proposed approach that uses Probability Matching technique based on the relative fitness improvements, referred to as PM-AdapSS-DE.

International audience; One of the choices that most affect the performance of Evolutionary Algorithms is the selection of the variation operators that are efficient to solve the problem at hand. This work presents an empirical analysis of different Adaptive Operator Selection (AOS) methods, i.e., techniques that automatically select the operator to be applied among the available ones, while searching for the solution. Four previously published operator selection rules are combined to four different credit assignment mechanisms. These 16 AOS combinations are analyzed and compared in the light of two well-known benchmark problems in Evolutionary Computation, the Royal Road and the Long K-Path.

International audience; Evolutionary Computation is an exciting research field with the power to assist researchers in the task of solving hard optimization problems (i.e., problems where the exploitable knowledge about the solution space is very hard and/or expensive to obtain). However, Evolutionary Algorithms are rarely used outside the circle of knowledgeable practitioners, and in that way have not achieved a status of useful enough tool to assist "general" researchers. We think that part of the blame is the lack of practical implementations of research efforts reflecting a unifying common ground in the field. In this communication we present GUIDE, a software framework incorporating some of the latest results from the EC research community and offering a Graphical User Interface that allows the straightforward manipulation of evolutionary algorithms. From a high-level description provided by the user it generates the code that is needed to run an evolutionary algorithm in a specified existing library (as of March 2009, EO and ECJ are the possible targeted libraries). GUIDE's GUI allows users to acquire a straightforward understanding of EC ideas, while at the same time providing them with a sophisticated research tool. In this communication we present 3 industrial case studies using GUIDE as one of the main tools in order to perform software testing on large, complex systems.

The performance of evolutionary algorithms is highly affected by the selection of the variation operators to solve the problem at hand. This abstract presents a survey of results that have been obtained using the "Extreme - Dynamic Multi-Armed Bandit" (Ex-DMAB), a technique used to automatically select the operator to be applied between the available ones, while searching for the solution. Experiments on three well-known artificial problems of the EC community are presented, namely the OneMax, the long k-path and the Royal Road, demonstrating some improvements over both any choice of a single-operator alone, and the naive uniform choice of one operator at each application. The Ex-DMAB approach is also compared to the optimal choice of operators, whenever available. The results are discussed in the light of the new parameters that are introduced to tune the selection technique...

10-years Impact Award at GECCO 2018; International audience; An important step toward self-tuning Evolutionary Algorithms is to design efficient Adaptive Operator Selection procedures. Such a procedure is made of two main components: a credit assignment mechanism, that computes a reward for each operator at hand based on some characteristics of the past offspring; and an adaptation rule, that modifies the selection mechanism based on the rewards of the different operators. This paper is concerned with the latter, and proposes a new approach for it based on the well-known Multi-Armed Bandit paradigm. However, because the basic Multi-Armed Bandit methods have been developed for static frameworks, a specific Dynamic Multi-Armed Bandit algorithm is proposed, that hybridizes an optimal Multi-Armed Bandit algorithm with the statistical Page-Hinkley test, which enforces the efficient detection of changes in time series. This original Operator Selection procedure is then compared to the state-of-the-art rules known as Probability Matching and Adaptive Pursuit on several artificial scenarios, after a careful sensitivity analysis of all methods. The Dynamic Multi-Armed Bandit method is found to outperform the other methods on a scenario from the literature, while on another scenario, the basic Multi-Armed Bandit performs best.

In this paper we propose an agent-based model of evolutionary algorithms (EAs) which extends seamlessly from concurrent single-host to distributed multi-host installations. Since the model is based on locally executable selection, we focus on the comparison of two selection mechanisms which accomplish with such a restriction: the classical tournament method and a new one called autonomous selection. Using the latter method the population size changes during runtime, hence it is not only interesting as a new selection mechanism, but also from the perspective of scalable networks.

A fuzzy controller is usually designed by formulating the knowledge of a human expert into a set of linguistic variables and fuzzy rules. Among the most successful methods to automate the fuzzy controllers development process are evolutionary algorithms. In this work, we propose the Recurrent Fuzzy Voronoi (RFV) model, a representation for recurrent fuzzy systems. It is an extension of the FV model proposed by Kavka and Schoenauer that extends the application domain to include temporal problems. The FV model is a representation for fuzzy controllers based on Voronoi diagrams that can represent fuzzy systems with synergistic rules, fulfilling the $\epsilon$-completeness property and providing a simple way to introduce a priory knowledge. In the proposed representation, the temporal relations are embedded by including internal units that provide feedback by connecting outputs to inputs. These internal units act as memory elements. In the RFV model, the semantic of the internal units can be specified together with the a priori rules. The geometric interpretation of the rules allows the use of geometric variational operators during the evolution. The representation and the algorithms are validated in two problems in the area of system identification and evolutionary robotics.

A Quasi-Monte-Carlo method based on the computation of a surrogate model of the fitness function is proposed, and its convergence at super-linear rate 3/2 is proved under rather mild assumptions on the fitness function -- but assuming that the starting point lies within a small neighborhood of a global maximum. A memetic algorithm is then constructed, that performs both a random exploration of the search space and the exploitation of the best-so-far points using the previous surrogate local algorithm, coupled through selection. Under the same mild hypotheses, the global convergence of the memetic algorithm, at the same 3/2 rate, is proved.