Search

International audience; In this paper, we investigate the effect of a learning rate for the mean in Evolution Strategies with recombination. We study the effect of a half-line search after the mean shift direction is established, hence the learning rate value is conditioned to the direction. We prove convergence and study convergence rates in different dimensions and for different population sizes on the sphere function with the step-size proportional to the distance to the optimum. We empirically find that a perfect half-line search increases the maximal convergence rate on the sphere function by up to about 70%, assuming the line search imposes no additional costs. The speedup becomes less pronounced with increasing dimension. The line search reduces-however does not eliminate-the dependency of the convergence rate on the step-size. The optimal step-size assumes considerably smaller values with line search, which is consistent with previous results for different learning rate settings. The step-size difference is more pronounced in larger dimension and with larger population size, thereby diminishing an important advantage of a large population. CCS CONCEPTS • Theory of computation → Bio-inspired optimization; Nonconvex optimization.

International audience; In this paper, we investigate a non-elitist Evolution Strategy designed to handle black-box constraints by an adaptive Augmented Lagrangian penalty approach, AL-(µ/µw, λ)-CMA-ES, on problems with up to 28 constraints. Based on stability and performance observations, we propose an improved default parameter setting. We exhibit failure cases of the Augmented Lagrangian technique and show how surrogate modeling of the constraints can overcome some difficulties. Several variants of AL-CMA-ES are compared on a set of nonlinear constrained problems from the literature. Simple adaptive penalty techniques serve as a baseline for comparison.

International audience; An automatic procedure to identify the bed friction coefficient is tested on a 2D hydrodynamic model of the Gironde estuary (France). The proposed procedure involves an optimization algorithm based on evolution strategy, namely Covariance Matrix Adaptation Evolution Strategy. Without optimization, application of the same friction distribution to different hydrological conditions leads to significant relative error in water level prediction up to 20%–30%. For the tested configuration, 300 runs seemed to be sufficient to reach an optimal value whereas an additional 200 runs would help to gain an accuracy of a few millimeters (or 0.3%). In order to reach the same level of accuracy for the different hydrological configurations, it is necessary to adapt for each configuration of the bed friction coefficient. Such behavior tends to confirm a seasonal variation of the friction coefficient and this is particularly the case in the central part of the estuary. Different relationships of the friction coefficient according to the flowrate have been incorporated inside the 2D hydrodynamic model. These relationships effectively maintain an accurate prediction of the water levels close to 10% for a wide range of hydrological configurations.

Local search algorithms consist in evolving a solution guided by a fitness function, which is usually directly derived from the objective function of the problem. Solving difficulties appear when the fitness landscape, naturally induced by the problem instance, is not perfectly exploitable, has a certain level of ruggedness and therefore has many local optima. We propose here to shift the problem from searching for a solution, to searching for a fitness function, which maximizes the efficiency of a deterministic and basic hill-climber. Considering that a LS algorithm is defined by a starting point, a neighborhood structure, a fitness function and a move strategy, we propose here to fix all components but the fitness function, so that each fitness function induces an algorithm generating a unique search trajectory. Through a simple evolution strategy applied to NK fitness functions, we propose to search for a basic hill-climbing algorithm specifically dedicated to attain the best possible solution of the original problem.

International audience; This paper proposes a new approach for online control law gains adaptation, through the use of neural networks and the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) algorithm, in order to optimize the behavior of the robot with respect to an objective function. The neural network considered takes as input the current observed state as well as its uncertainty, and provides as output the control law gains. It is trained, using the CMA-ES evolution strategy, on a simulator reproducing the vehicle dynamics. Then, it is tested in real conditions on an agricultural mobile robot at different speeds. The transferability of this method from simulation to a real system is demonstrated, as well as its robustness to environmental changes, such as GPS signal degradation or ground variation. As a result, path following errors are reduced, while ensuring tracking stability.

International audience; Modern genomic sequencing machines can measure thousands of probes from different specimens. Nevertheless, theoretically comparable datasets can show considerably distinguishable properties, depending on both platform and specimen, a phenomenon known as batch effect. Batch correction is the technique aiming at removing this effect from the data. A possible approach to batch correction is to find a transformation function between different datasets, but optimizing the weights of such a function is not trivial: As there is no explicit gradient to follow, traditional optimization techniques would fail. In this work, we propose to use a state-of-the-art evolutionary algorithm, Covariance Matrix Adaptation Evolution Strategy, to optimize the weights of a transformation function for batch correction. The fitness function is driven by the classification accuracy of an ensemble of algorithms on the transformed data. The case study selected to test the proposed approach is mRNA gene expression data of Chronic Fatigue Syndrome, a disease for which there is currently no established diagnostic test. The transformation function obtained from three datasets, produced from different specimens, remarkably improves the performance of classifiers on the task of diagnosing Chronic Fatigue. The presented results are an important steppingstone towards a reliable diagnostic test for this syndrome.

International audience; When faced with a specific optimization problem, deciding which algorithm to apply is always a difficult task. Not only is there a vastvariety of algorithms to select from, but these algorithms are often controlled by many hyperparameters, which need to be suitablytuned in order to achieve peak performance. Usually, the problem of selecting and configuring the optimization algorithm is addressedsequentially, by first selecting a suitable algorithm and then tuning it for the application at hand. Integrated approaches, commonlyknown as Combined Algorithm Selection and Hyperparameter (CASH) solvers, have shown promise in several applications.In this work we compare sequential and integrated approaches for selecting and tuning the best out of the 4,608 variants of themodular Covariance Matrix Adaptation Evolution Strategy (CMAES). We show that the ranking of these variants depends to a largeextent on the quality of the hyperparameters. Sequential approaches are therefore likely to recommend sub-optimal choices. Integratedapproaches, in contrast, manage to provide competitive results at much smaller computational cost. We also highlight importantdifferences in the search behavior of two CASH approaches, which build on racing (irace) and on model-based optimization (MIP-EGO),respectively.

International audience; The MAP-Elites quality-diversity algorithm has been successful in robotics because it can create a behaviorally diverse set of solutions that later can be used for adaptation, for instance to unanticipated damages. In MAP-Elites, the choice of the behaviour space is essential for adaptation, the recovery of performance in unseen environments , since it defines the diversity of the solutions. Current practice is to hand-code a set of behavioural features, however, given the large space of possible behaviour-performance maps, the designer does not know a priori which behavioural features maximise a map's adaptation potential. We introduce a new meta-evolution algorithm that discovers those behavioural features that maximise future adaptations. The proposed method applies Covari-ance Matrix Adaptation Evolution Strategy to evolve a population of behaviour-performance maps to maximise a meta-fitness function that rewards adaptation. The method stores solutions found by MAP-Elites in a database which allows to rapidly construct new behaviour-performance maps on-the-fly. To evaluate this system , we study the gait of the RHex robot as it adapts to a range of damages sustained on its legs. When compared to MAP-Elites with user-defined behaviour spaces, we demonstrate that the meta-evolution system learns high-performing gaits with or without damages injected to the robot.

International audience; This paper proposes a new approach for feature importance of neural networks and subsequently a methodology to determine useful sensor information in high performance controllers, using a trained neural network that predicts the quasi-optimal gain in real time. The neural network is trained using the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) algorithm, in order to lower a given objective function. The important sensor information for robotic control are determined using the described methodology. Then a proposed improvement to the tested control law is given, and compared with the neural network's gain prediction method for real time gain tuning. As a results, crucial information about the importance of a given sensory information for robotic control is determined, and shown to improve the performance of existing controllers.

International audience; Knowledge discovery from data typically includes solving some type of an optimization problem that can be efficiently addressed using algorithms belonging to the class of evolutionary and bio-inspired computation. In this chapter, we give an overview of the various kinds of evolutionary algorithms, such as genetic algorithms, evolutionary strategy, evolutionary and genetic programming, differential evolution, and coevolutionary algorithms, as well as several other bio-inspired approaches, like swarm intelligence and artificial immune systems. After elaborating on the methodology, we provide numerous examples of applications in astronomy and geoscience and show how these algorithms can be applied within a distributed environment, by making use of parallel computing, which is essential when dealing with Big Data.

International audience; Subspace clustering is a data-mining task that groups similar data objects and at the same time searches the subspaces where similarities appear. For this reason, subspace clustering is recognized as more general and complicated than standard clustering. In this article, we present ChameleoClust+, a bioinspired evolutionary subspace clustering algorithm that takes advantage of an evolvable genome structure to detect various numbers of clusters located in different subspaces. ChameleoClust+ incorporates several biolike features such as a variable genome length, both functional and nonfunctional elements, and mutation operators including large rearrangements. It was assessed and compared with the state-of-the-art methods on a reference benchmark using both real-world and synthetic data sets. Although other algorithms may need complex parameter settings, ChameleoClust+ needs to set only one subspace clustering ad hoc and intuitive parameter: the maximal number of clusters. The remaining parameters of ChameleoClust+ are related to the evolution strategy (eg, population size, mutation rate), and a single setting for all of them turned out to be effective for all the benchmark data sets. A sensitivity analysis has also been carried out to study the impact of each parameter on the subspace clustering quality.

International audience; In the context of numerical constrained optimization, we investigate stochastic algorithms, in particular evolution strategies, handling constraints via augmented Lagrangian approaches. In those approaches, the original constrained problem is turned into an unconstrained one and the function optimized is an augmented Lagrangian whose parameters are adapted during the optimization. The use of an augmented Lagrangian however breaks a central invariance property of evolution strategies, namely invariance to strictly increasing transformations of the objective function. We formalize nevertheless that an evolution strategy with augmented Lagrangian constraint handling should preserve invariance to strictly increasing affine transformations of the objective function and the scaling of the constraints—a subclass of strictly increasing transformations. We show that this invariance property is important for the linear convergence of these algorithms and show how both properties are connected.

International audience; In this paper we benchmark five variants of CMA-ES for optimization in large dimension on the novel large scale testbed of COCO under default or modified parameter settings. In particular, we compare the performance of the separable CMA-ES, of VD-CMA-ES and VkD-CMA-ES, of two implementations of the Limited Memory CMA-ES and of the Rank m Evolution Strategy, RmES. For VkD-CMA-ES we perform experiments with different complexity models of the search distribution and for RmES we study the impact of the number of evolution paths employed by the algorithm. The quasi-Newton L-BFGS-B algorithm is also benchmarked and we investigate the effect of choosing the maximum number of variable metric corrections for the Hessian approximation. As baseline comparison, we provide results of CMA-ES up to dimension 320.

International audience; Multi-Modal Optimization problems are widespread and can be solved using numerous methods, such as niching, sharing or clearing. In this paper, we are interested in algorithms based on restart strategies, where the searching point is restarted at another initial position when an optimum is found. Previous works show that the choice of these initial positions greatly impacts the performance of the algorithm but is not easy to make. In this paper, we propose a new restart strategy, based on reinforcement learning. Our algorithm subdivides the search space and uses a Multi-Armed Bandit technique to choose the successive restart positions. We experiment this algorithm on various functions and on a modified Hump function with more complex local areas. Our results show significant improvements over previous algorithms, such as the Quasi-Random restart with Decreasing Step-size algorithm.

Part 2: Evolutionary Computation; International audience; Nature-inspired algorithms attract many researchers worldwide for solving the hardest optimization problems. One of the well-known members of this extensive family is the evolutionary strategy ES algorithm. To date, many variants of this algorithm have emerged for solving continuous as well as combinatorial problems. One of the more promising variants, a self-adaptive evolutionary algorithm, has recently been proposed that enables a self-adaptation of its control parameters. In this paper, we discuss and evaluate popular common and self-adaptive evolutionary strategy (ES) algorithms. In particular, we present an empirical comparison between three self-adaptive ES variants and common ES methods. In order to assure a fair comparison, we test the methods by using a number of well-known unimodal and multimodal, separable and non-separable, benchmark optimization problems for different dimensions and population size. The results of this experiments study were promising and have encouraged us to invest more efforts into developing in this direction.

PMC5785979; Cold adaptation is an evolutionary process that has dramatic impact on enzymatic activity. Increased flexibility of the protein structure represents the main evolutionary strategy for efficient catalysis and reaction rates in the cold, but is achieved at the expense of structural stability. This results in a significant activity-stability tradeoff, as it was observed for several metabolic enzymes. In polymerases, however, not only reaction rates, but also fidelity plays an important role, as these enzymes have to synthesize copies of DNA and RNA as exact as possible. Here, we investigate the effects of cold adaptation on the highly accurate CCA-adding enzyme, an RNA polymerase that uses an internal amino acid motif within the flexible catalytic core as a template to synthesize the CCA triplet at tRNA 3'-ends. As the relative orientation of these residues determines nucleotide selection, we characterized how cold adaptation impacts template reading and fidelity. In a comparative analysis of closely related psychro-, meso-, and thermophilic enzymes, the cold-adapted polymerase shows a remarkable error rate during CCA synthesis in vitro as well as in vivo. Accordingly, CCA-adding activity at low temperatures is not only achieved at the expense of structural stability, but also results in a reduced polymerization fidelity.

International audience

Quality gain is the expected relative improvement of the function value in a single step of a search algorithm. Quality gain analysis reveals the dependencies of the quality gain on the parameters of a search algorithm, based on which one can derive the optimal values for the parameters. In this paper, we investigate evolution strategies with weighted recombination on general convex quadratic functions. We derive a bound for the quality gain and two limit expressions of the quality gain. From the limit expressions, we derive the optimal recombination weights and the optimal step-size, and find that the optimal recombination weights are independent of the Hessian of the objective function. Moreover, the dependencies of the optimal parameters on the dimension and the population size are revealed. Differently from previous works where the population size is implicitly assumed to be smaller than the dimension, our results cover the population size proportional to or greater than the dimension. Numerical simulation shows that the asymptotically optimal step-size well approximates the empirically optimal step-size for a finite dimensional convex quadratic function., Comment: Extended version of the work presented in FOGA 2017, accepted in TCS-D

International audience; We analyze linear convergence of an evolution strategy for constrained optimization with an augmented Lagrangian constraint handling approach. We study the case of multiple active linear constraints and use a Markov chain approach—used to analyze ran-domized optimization algorithms in the unconstrained case—to establish linear convergence under sufficient conditions. More specifically , we exhibit a class of functions on which a homogeneous Markov chain (defined from the state variables of the algorithm) exists and whose stability implies linear convergence. This class of functions is defined such that the augmented Lagrangian, centered in its value at the optimum and the associated Lagrange multipliers, is positive homogeneous of degree 2, and includes convex quadratic functions. Simulations of the Markov chain are conducted on linearly constrained sphere and ellipsoid functions to validate numerically the stability of the constructed Markov chain.

Legacy systems modernization is one of the most common issues for enterprise organizations. As technology is changing rapidly, enterprises need to upgrade legacy systems and provide suitable modernization. To make valid decisions on the choice of modernization strategy and achieve a successful evolutionary system, it requires addressing the full modernization project life cycle. In this paper, we propose a Legacy System Assessment Conceptual Framework (LSACF) based on quality metrics. LSACF presents a strategy including a methodological approach and supporting functional toolkit to help maintainers in the evolution process. Further, it provides an analysis composed of four phases. Firstly, qualification phase of LSACF defines the starting moment of legacy system transformation, the legacy system program and its roadmap, and identifies the appropriate modernization approaches. Secondly, selection phase selects the most suitable evolution strategy based on multi criteria optimization algorithm. Then, transition phase verifies the correctness of the evolution process. Finally, validation phase verifies that the claimed benefits have been achieved or not. Our methodology is applied in the context of a legacy ERP system.

In order to reduce the cost of solving expensive optimization problems, this thesis devoted to Kriging-Assisted Covariance Matrix Adaptation Evolution Strategy (KA-CMA-ES). Several algorithms of KA-CMA-ES were developed and a comprehensive investigation on KA-CMA-ES was performed. Then applications of the developed KA-CMA-ES algorithm were carried out in material parameter identification of an elastic-plastic damage constitutive model. The results of experimental studies demonstrated that the developed KA-CMA-ES algorithms generally are more efficient than the standard CMA-ES and that the KA-CMA-ES using ARP-EI has the best performance among all the investigated KA-CMA-ES algorithms in this work. The results of engineering applications of the algorithm ARP-EI in material parameter identification show that the presented elastic-plastic damage model is adequate to describe the plastic and ductile damage behavior and also prove that the proposed KA-CMA-ES algorithm apparently improve the efficiency of the standard CMA-ES. Therefore, the KA-CMA-ES is more powerful and efficient than CMA-ES for expensive optimization problems., Afin de réduire le coût de calcul pour des problèmes d'optimisation coûteuse, cette thèse a été consacrée à la Stratégie d'Evolution avec Adaptation de Matrice de Covariance assistée par modèle de Krigeage (KA-CMA-ES). Plusieurs algorithmes de KA-CMA-ES ont été développés et étudiés. Une application de ces algorithmes KA-CMA-ES développés est réalisée par l'identification des paramètres matériels avec un modèle constitutif d'endommagement élastoplastique. Les résultats expérimentaux démontrent que les algorithmes KA-CMA-ES développés sont plus efficaces que le CMA-ES standard. Ils justifient autant que le KA-CMA-ES couplé avec ARP-EI est le plus performant par rapport aux autres algorithmes étudiés dans ce travail. Les résultats obtenus par l'algorithme ARP-EI dans l'identification des paramètres matériels montrent que le modèle d'endommagement élastoplastique utilisé est suffisant pour décrire le comportement d'endommage plastique et ductile. Ils prouvent également que la KA-CMA-ES proposée améliore l'efficace de la CMA-ES. Par conséquent, le KA-CMA-ES est plus puissant et efficace que CMA-ES pour des problèmes d'optimisation coûteuse.

International audience; We focus on a variant of covariance matrix adaptation evolution strategy (CMA-ES) with a restricted covariance matrix model, namely VkD-CMA, which is aimed at reducing the internal time complexity and the adaptation time in terms of function evaluations. We tackle the shortage of the VkD-CMA—the model of the restricted covariance matrices needs to be selected beforehand. We propose a novel mechanism to adapt the model online in the VkD-CMA. It eliminates the need for advance model selection and leads to a performance competitive with or even better than the algorithm with a nearly optimal but fixed model.

International audience; Previous studies have shown the efficiency of using quasi-random mutations on the well-know CMA evolution strategy [13]. Quasi-random mutations have many advantages, in particular their application is stable, efficient and easy to use. In this article, we extend this principle by applying quasi-random mutations on several well known continuous evolutionary algorithms (SA, CMSA, CMA) and do it on several old and new test functions, and with several criteria. The results point out a clear improvement compared to the baseline, in all cases, and in particular for moderate computational budget.

This thesis deals with the generation of ultrashort pulses within a fiber laser cavity through the automatic optimization of its parameters by an evolutionary algorithm. The interest of this subject comes from the difficulty to systematically explore dynamics in a large domain of experimental parameters. We have shown that it is possible to implement an evolutionary algorithm on fiber laser cavity with appropriate precautions. We have experimentally demonstrated for the first time the mode locking of a laser cavity only using the optimization of polarization controllers through an automatic and self-learning procedure. We also have demonstrated that selecting the mode locking from it radio-frequency spectrum allow to select the pulses repetition rate within the cavity. These preliminary results show the promising aspect of our method used in situations of non linear ultrafast dynamics with high complexity which are particularly sensitive to parameters., Le sujet de cette thèse se rapporte à la génération d’impulsions ultracourtes dans une cavité laser fibrée à travers l’optimisation automatique de ses paramètres par un algorithme d’évolution. L’intérêt pour cette problématique provient de la difficulté à explorer les dynamiques impulsionnelles de manière systématique dans un large domaine de paramètres expérimentaux. Nous avons montré que l’implémentation d’un algorithme d’évolution sur une cavité laser fibrée de ce type peut être réalisée, en prenant les précautions adéquates pour que cette association soit la plus efficace possible. Nous avons démontré expérimentalement pour la première fois le verrouillage de modes depuis la seule optimisation des contrôleurs de polarisation utilisant une procédure automatique d’auto-apprentissage. Nous avons démontré que la sélection du blocage de modes depuis son spectre radio-fréquence permet de sélectionner le taux de répétition desimpulsions à l’intérieur de la cavité. Ces résultats préliminaires démontrent les potentialités de notre méthode employée dans des situations de dynamique non linéaire ultrarapide de grande complexité, particulièrement sensibles aux paramètres.

International audience; Real-time embedded systems may be composed of a large number of time constrained functions. When such systems are implemented on top of multitasks real-time operating systems (RTOS), the functions have to be assigned to tasks of the target RTOS. This is a challenging work due to the large number of valid candidate functions to tasks assignment solutions. Moreover, the impact of the assignment on the system performance criteria (often conflicting) should be taken intoaccount in the architecture exploration. The automation of the software design exploration by the use of metaheuristics such as multi-objective evolutionary algorithm (MOEA) is a suitable way to help the designers. Indeed, MOEAs approximate near optimal alternatives at a reasonable time when compared to an exhaustive and exact search method. However, for large scale systems (i.e having a huge number of functions) even a MOEA method is impractical due to the increased time required to solve a problem instance. This may raise a threat to the scalability of the software design exploration method. To tackle this problem, we present in this article a parallel implementation of the Pareto Archived Evolution Strategy (PAES) algorithm used as a MOEA for the software design exploration. The proposed parallelization method is based on the well-known master-slave paradigm. Additionally, it involves a new selection scheme in the PAES algorithm. Results of experimentations provide evidence that, on one hand, the parallel approach can considerably speed up the design exploration and the optimization processes. On the other hand, the proposed selection strategy improves the quality of obtained solutions as compared to the original PAES selection schema.

The monitoring data collected during tunnel excavation can be used in inverse analysis procedures in order to identify more realistic geomechanical parameters that can increase the knowledge about the interested formations. These more realistic parameters can be used in real time to adapt the project to the real structure in situ behaviour. However, monitoring plans are normally designed for safety assessment and not especially for the purpose of inverse analysis. In fact, there is a lack of knowledge about what types and quantity of measurements are needed to succeed in identifying the parameters of interest. Also, the optimisation algorithm chosen for the identification procedure may be important for this matter. In this work, this problem is addressed using a theoretical case with which a thorough parametric study was carried out using two optimisation algorithms based on different calculation paradigms, namely a conventional gradient-based algorithm and an evolution strategy algorithm. Calculations were carried for different sets of parameters to identify several combinations of types and amount of monitoring data. The results clearly show the high importance of the available monitoring data and the chosen algorithm for the success rate of the inverse analysis process., The work was supported by CETu.

11 pp; International audience; This article deals with real-time embedded system design and verification. Real-time embedded systems are frequentlydesigned according to multi-tasking architectures that have timing constraints to meet. The design of real-time embeddedsystems expressed as a set of tasks raises a major challenge since designers have to decide how functions of the system mustbe assigned to tasks. Assigning each function to a different task will result in a high number of tasks, and then in higherpreemption overhead. In contrast, mapping many functions on a limited number of tasks leads to a less flexible design whichis more expensive to change when the functions of the system evolve. This article presents a method based on an optimizationtechnique to investigate the assignment of functions to tasks. We propose a multi-objective evolution strategy formulation whichboth minimizes the number of preemptions and maximizes task laxities. Our method allows designers to explore the search spaceof all possible function to task assignments and to find good tradeoffs between the two optimization objectives among schedulablesolutions. After explaining our mapping approach, we present a set of experiments which demonstrates its effectiveness fordifferent system sizes.

International audience; In this paper we propose a new way to compute a rough approximation solution, to be later used as a warm starting point in a more refined optimization process, for a challenging global optimization problem related to Earth imaging in geophysics. The warm start con- sists of a velocity model that approximately solves a full-waveform inverse problem at low frequency. Our motivation arises from the availability of massively parallel computing plat- forms and the natural parallelization of evolution strategies as global optimization methods for continuous variables.Our first contribution consists of developing a new and efficient parametrization of the velocity models to significantly reduce the dimension of the original optimization space. Our second contribution is to adapt a class of evolution strategies to the specificity of the physical problem at hands where the objective function evaluation is known to be the most expen- sive computational part. A third contribution is the development of a parallel evolution strategy solver, taking advantage of a recently proposed modification of these class of evolu- tionary methods that ensures convergence and promotes better performance under moderate budgets.The numerical results presented demonstrate the effectiveness of the algorithm on a realistic 3D full-waveform inverse problem in geophysics. The developed numerical approach allows us to successfully solve an acoustic full-waveform inversion problem at low frequencies on a reasonable number of cores of a distributed memory computer.

International audience; The global optimization of expensive-to-calculate continuous functions is of great practical importance in engineering. Among the proposed algorithms for solving such problems, Efficient Global Optimization (EGO) and Covariance Matrix Adaptation Evolution Strategy (CMA-ES) are regarded as two state-of-the-art unconstrained continuous optimization algorithms. Their underlying principles and performances are different, yet complementary: EGO fills the design space in an order controlled by a Gaussian process (GP) conditioned by the objective function while CMA-ES learns and samples multi-normal laws in the space of design variables. This paper proposes a new algorithm, called EGO-CMA, which combines EGO and CMA-ES. In EGO-CMA, the EGO search is interrupted early and followed by a CMA-ES search whose starting point, initial step size and covariance matrix are calculated from the already sampled points and the associated conditional GP. EGO-CMA improves the performance of both EGO and CMA-ES in our 2 to 10 dimensional experiments.

International audience; This paper proposes the application of the Covariance Matrix Adaptation (CMA) evolution strategy for the identification of building envelope materials hygrothermal properties. All material properties are estimated on the basis of local temperature and relative humidity measurements, by solving the inverse heat and moisture transfer problem. The applicability of the identification procedure is demonstrated in two stages: first, a numerical benchmark is developed and used as to show the potential identification accuracy, justify the choice for a Tikhonov reg-ularisation term in the fitness evaluation, and propose a method for its appropriate tuning. Then, the procedure is applied on the basis of experimental measurements from an instrumented test cell, and compared to the experimental characterisation of the observed material. Results show that an accurate estimation of all hygrothermal properties of a building material is feasible, if the objective function of the inverse problem is carefully defined.

The complexity of continuous optimisation by comparison-based algorithms has been developed in several recent papers. Roughly speaking, these papers conclude that a precision $$\epsilon $$ can be reached with cost $$\varTheta n\log 1/\epsilon $$ in dimension n within polylogarithmic factors for the sphere function. Compared to other non comparison-based algorithms, this rate is not excellent; on the other hand, it is classically considered that comparison-based algorithms have some robustness advantages, as well as scalability on parallel machines and simplicity. In the present paper we show another advantage, namely resilience to useless variables, thanks to a complexity bound $$\varTheta m\log 1/\epsilon $$ where m is the codimension of the set of optima, possibly $$m << n$$. In addition, experiments show that some evolutionary algorithms have a negligible computational complexity even in high dimension, making them practical for huge problems with many useless variables.

International audience; In Noisy Optimization, one of the most common way to deal with noise is through resampling. In this paper, we compare various resampling rules applied to Evolution Strategy (ES). The goal is to provide a conclusive answer for resampling rules in simple settings. We use a variant of ES as our main algorithm: Self-Adaptive (μ/μ,λ)-Evolution Strategy. We focus our attention on local noisy optimization. In other words, we are interested in situation where reducing the noise is more important than avoiding local minima. We study different sampling rules on the noisy sphere function and compare them experimentally. We conclude that there exists parameter-free formulas that provide adequate resampling rules.

This paper analyses a $(1,\lambda)$-Evolution Strategy, a randomised comparison-based adaptive search algorithm, on a simple constraint optimisation problem. The algorithm uses resampling to handle the constraint and optimizes a linear function with a linear constraint. Two cases are investigated: first the case where the step-size is constant, and second the case where the step-size is adapted using path length control. We exhibit for each case a Markov chain whose stability analysis would allow us to deduce the divergence of the algorithm depending on its internal parameters. We show divergence at a constant rate when the step-size is constant. We sketch that with step-size adaptation geometric divergence takes place. Our results complement previous studies where stability was assumed., Comment: Amir Hussain; Zhigang Zeng; Nian Zhang. IEEE Congress on Evolutionary Computation, Jul 2014, Beijing, China

International audience; When the regenerative braking energy cannot be stored by the metro producing it, it has to be used instantaneously on the network, otherwise it is lost. In this case, the accelerating and braking trains need be synchronized to fully benefit from the regenerative energy, and a metro timetable is energetically optimized when all the re-generative braking is utilized to power other trains. This synchronization consists in lining up each braking train with an accelerating one in its neighbourhood. Doing so, the latter will benefit from the regenerative energy of the former. We propose a fast greedy heuristic to tackle the problem of minimizing the energy consumption of a metro timetable by modifying solely the dwell times in stations. This heuristic is compared to a state-of-the-art meta heuristic called the covariance matrix adaptation evolution strategy (CMA-ES) and shows similar results with much faster computation time. Finally, we show that a run of the algorithm on a full timetable may reduce its energy consumption by 5.1%.

Irrigation scheduling is an important task that significantly influences water conservation and crop production. For most gravity irrigation networks located in semi-arid areas, irrigation scheduling is based on available water regardless of crops water needs. The objective of this study is to propose a new approach for optimizing irrigation scheduling taking into account crops water demand, based on the Covariance Matrix Adaptation - Evolution Strategy (CMA-ES) evolutionary strategy algorithm. The objective function, that must be minimized, of this optimization problem is defined as the sum of two terms. The first term is the Irrigation Priority Index (IPI) which characterizes the degree of imbalance between water stress and irrigation timing of the plot. The second one takes into account the various constraints that relate to canals capacity, tasks timing, geographical distances and canal flow rate variations. The approach was applied to an agricultural sector located at 40 km from the city of Marrakech (Morocco). Optimal schedule for the third irrigation, of the 2011-2012 agricultural season, is provided and the comparisons between schedules before and after optimization are made. The obtained results demonstrate that such approach allows reducing the proportion of late irrigated plots (from 22% to 8%) and increasing the proportion of plots irrigated at an appropriate time (from 28% to 40%). We conclude that this approach can be considered as an efficient tool for planning irrigation schedules by considering crops water needs.

In this paper, we develop a novel stochastic multi-objective multi-mode transportation model for hub covering location problem under uncertainty. The transportation time between each pair of nodes is an uncertain parameter and also is influenced by a risk factor in the network. We extend the traditional comprehensive hub location problem by considering two new objective functions. So, our multi-objective model includes (i) minimization of total current investment costs and (ii) minimization of maximum transportation time between each origin–destination pair in the network. Besides, a novel multi-objective imperialist competitive algorithm (MOICA) is proposed to obtain the Pareto-optimal solutions of the problem. The performance of the proposed solution algorithm is compared with two well-known meta-heuristics, namely, non-dominated sorting genetic algorithm (NSGA-II) and Pareto archive evolution strategy (PAES). Computational results show that MOICA outperforms the other meta-heuristics.

In the context of unconstraint numerical optimization, this paper investigates the global linear convergence of a simple probabilistic derivative-free optimization algorithm (DFO). The algorithm samples a candidate solution from a standard multivariate normal distribution scaled by a step-size and centered in the current solution. This solution is accepted if it has a better objective function value than the current one. Crucial to the algorithm is the adaptation of the step-size that is done in order to maintain a certain probability of success. The algorithm, already proposed in the 60's, is a generalization of the well-known Rechenberg's $(1+1)$ Evolution Strategy (ES) with one-fifth success rule which was also proposed by Devroye under the name compound random search or by Schumer and Steiglitz under the name step-size adaptive random search. In addition to be derivative-free, the algorithm is function-value-free: it exploits the objective function only through comparisons. It belongs to the class of comparison-based step-size adaptive randomized search (CB-SARS). For the convergence analysis, we follow the methodology developed in a companion paper for investigating linear convergence of CB-SARS: by exploiting invariance properties of the algorithm, we turn the study of global linear convergence on scaling-invariant functions into the study of the stability of an underlying normalized Markov chain (MC). We hence prove global linear convergence by studying the stability (irreducibility, recurrence, positivity, geometric ergodicity) of the normalized MC associated to the $(1+1)$-ES. More precisely, we prove that starting from any initial solution and any step-size, linear convergence with probability one and in expectation occurs. Our proof holds on unimodal functions that are the composite of strictly increasing functions by positively homogeneous functions with degree $\alpha$ (assumed also to be continuously differentiable). This function class includes composite of norm functions but also non-quasi convex functions. Because of the composition by a strictly increasing function, it includes non continuous functions. We find that a sufficient condition for global linear convergence is the step-size increase on linear functions, a condition typically satisfied for standard parameter choices. While introduced more than 40 years ago, we provide here the first proof of global linear convergence for the $(1+1)$-ES with generalized one-fifth success rule and the first proof of linear convergence for a CB-SARS on such a class of functions that includes non-quasi convex and non-continuous functions. Our proof also holds on functions where linear convergence of some CB-SARS was previously proven, namely convex-quadratic functions (including the well-know sphere function).

International audience; Many theories and solutions have been proposed for the improvement of the learning efficiency of secondary language(L2) learning. However neither an unified view on the functionality of semantics in aiding learning nor an objective measure of the efficiency improvement at theoretical level has been presented in ex- isting literature. This situation hinders the efficient adoption of the semantics aided learning and the explicit planning of a semantics aided learning process. We aim to fill these gaps by adopting an evolutionary strategy towards approaching a holistic solution. Firstly we model the general learning process from cognitive linguistic per- spective at the memory level. Then we justify the functionality of semantics aided approach according to specific conditions. Thereafter we propose the quantity mea- sure for the improvement of learning efficiency in terms of reuse level for semantics aided secondary language learning from the perspective of value based analysis.

International audience; Cooperative co-evolution algorithms (CCEA) are a thriving sub-field of evolutionary computation. This class of algorithms makes it possible to exploit more efficiently the artificial Darwinist scheme, as soon as an optimisation problem can be turned into a co-evolution of interdependent sub-parts of the searched solution. Testing the efficiency of new CCEA concepts, however, it is not straightforward: while there is a rich literature of benchmarks for more traditional evolutionary techniques, the same does not hold true for this relatively new paradigm. We present a benchmark problem designed to study the behavior and performance of CCEAs, modeling a search for the optimal placement of a set of lamps inside a room. The relative complexity of the problem can be adjusted by operating on a single parameter. The fitness function is a trade-off between conflicting objectives, so the performance of an algorithm can be examined by making use of different metrics. We show how three different cooperative strategies, Parisian Evolution, Group Evolution and AllopatricGroup Evolution, can be applied to the problem. Using a Classical Evolution approach as comparison, we analyse the behavior of each algorithm in detail, with respect to the size of the problem.

International audience; This paper investigates two variants of the well-known Covariance Matrix Adaptation Evolution Strategy (CMA-ES). Active covariance matrix adaptation allows for negative weights in the covariance matrix update rule such that "bad" steps are (actively) taken into account when updating the covariance matrix of the sample distribution. On the other hand, mirrored mutations via selective mirroring also take the "bad" steps into account. In this case, they are first evaluated when taken in the opposite direction (mirrored) and then considered for regular selection. In this study, we investigate the difference between the performance of the two variants empirically on the noiseless BBOB testbed. The CMA-ES with selectively mirrored mutations only outperforms the active CMA-ES on the sphere function while the active variant statistically significantly outperforms mirrored mutations on 10 of 24 functions in several dimensions.

In this paper, we study the performance of IPOP-saACM-ES and BIPOP-saACM-ES, recently proposed self-adaptive surrogate-assisted Covariance Matrix Adaptation Evolution Strategies. Both algorithms were tested using restarts till a total number of function evaluations of $10^6D$ was reached, where $D$ is the dimension of the function search space. We compared surrogate-assisted algorithms with their surrogate-less versions IPOP-saACM-ES and BIPOP-saACM-ES, two algorithms with one of the best overall performance observed during the BBOB-2009 and BBOB-2010. The comparison shows that the surrogate-assisted versions outperform the original CMA-ES algorithms by a factor from 2 to 4 on 8 out of 24 noiseless benchmark problems, showing the best results among all algorithms of the BBOB-2009 and BBOB-2010 on Ellipsoid, Discus, Bent Cigar, Sharp Ridge and Sum of different powers functions., Comment: arXiv admin note: substantial text overlap with arXiv:1206.0974

International audience; In this paper, we study the performance of NIPOP-aCMA-ES and NBIPOP-aCMA-ES, recently proposed alternative restart strategies for CMA-ES. Both algorithms were tested using restarts till a total number of function evaluations of $10^6D$ was reached, where $D$ is the dimension of the function search space. We compared new strategies to CMA-ES with IPOP and BIPOP restart schemes, two algorithms with one of the best overall performance observed during the BBOB-2009 and BBOB-2010. We also present the first benchmarking of BIPOP-CMA-ES with the weighted active covariance matrix update (BIPOP-aCMA-ES). The comparison shows that NIPOP-aCMA-ES usually outperforms IPOP-aCMA-ES and has similar performance with BIPOP-aCMA-ES, using only the regime of increasing the population size. The second strategy, NBIPOP-aCMA-ES, outperforms BIPOP-aCMA-ES in dimension 40 on weakly structured multi-modal functions thanks to the adaptive allocation of computation budgets between the regimes of restarts.

This paper presents a novel mechanism to adapt surrogate-assisted population-based algorithms. This mechanism is applied to ACM-ES, a recently proposed surrogate-assisted variant of CMA-ES. The resulting algorithm, saACM-ES, adjusts online the lifelength of the current surrogate model (the number of CMA-ES generations before learning a new surrogate) and the surrogate hyper-parameters. Both heuristics significantly improve the quality of the surrogate model, yielding a significant speed-up of saACM-ES compared to the ACM-ES and CMA-ES baselines. The empirical validation of saACM-ES on the BBOB-2012 noiseless testbed demonstrates the efficiency and the scalability w.r.t the problem dimension and the population size of the proposed approach, that reaches new best results on some of the benchmark problems., Genetic and Evolutionary Computation Conference (GECCO 2012) (2012)

International audience; Active Covariance Matrix Adaptation and Mirrored Mutations have been independently proposed as improved variants of the well-known optimization algorithm Covariance Matrix Adaptation Evolution Strategy (CMA-ES) for numerical optimization. This paper investigates the impact of the algorithm's population size when both active covariance matrix adaptation and mirrored mutation are used in the CMA-ES. To this end, we compare the CMA-ES with standard population size $\lambda$, i.e., $\lambda = 4 + \lfloor 3\log(D) \rfloor$ with a version with half this population size where $D$ is the problem dimension.

International audience; This paper deals with a statistical model fitting procedure for non-stationary time series. This procedure selects the parameters of a piecewise autoregressive model using the Minimum Description Length principle. The existing chromosome representation of the piecewise autoregressive model and its corresponding optimisation algorithm are improved. First, we show that our proposed chromosome representation better captures the intrinsic properties of the piecewise autoregressive model. Second, we apply an optimisation algorithm, the Covariance Matrix Adaptation - Evolution Strategy, with which our setup converges faster to the optimal fit. Our proposed method achieves at least one order of magnitude performance improvement compared to the existing solution.

International audience; In this paper, we propose a framework to automate the assessment of the movements of a third cerebral ventricle in a cine MR sequence. Indeed, the goal of this assessment is to build an atlas of the movements of the healthy ventricles in the context of the hydrocephalus pathology. This approach is composed of two phases: a contour extraction, using fractional integration and a registration method, based on dynamic evolutionary optimization. The first phase of the framework is based on the fractional integration thresholding, that allows delineating the contours of the area of interest. In order to track over time each point of the primitive and achieve the assessment of the deformation, a matching method, based on a new dynamic optimization algorithm, called Dynamic Covariance Matrix Adaptation Evolution Strategy (D-CMAES), is used. The obtained results for quantification have been clinically validated by an expert and compared to those presented in the literature.

In the present study, a modified variant of Differential Evolution (DE) algorithm for solving multi-objective optimization problems is presented. The proposed algorithm, named Multi-Objective Differential Evolution Algorithm (MODEA) utilizes the advantages of Opposition-Based Learning for generating an initial population of potential candidates and the concept of random localization in mutation step. Finally, it introduces a new selection mechanism for generating a well distributed Pareto optimal front. The performance of proposed algorithm is investigated on a set of nine bi-objective and five tri-objective benchmark test functions and the results are compared with some recently modified versions of DE for MOPs and some other Multi Objective Evolutionary Algorithms (MOEAs). The empirical analysis of the numerical results shows the efficiency of the proposed algorithm.

The “Policy Improvement with Path Integrals” (PI2) [25] and “Covariance Matrix Adaptation - Evolutionary Strategy” [8] are considered to be state-of-the-art in direct reinforcement learning and stochastic optimization respectively. We have recently shown that incorporating covariance matrix adaptation into PI2 – which yields the PICMA 2 algorithm – enables adaptive exploration by continually and autonomously reconsidering the exploration/exploitation trade-off. In this article, we provide an overview of our recent work on covariance matrix adaptation for direct reinforcement learning [22–24], highlight its relevance to developmental robotics, and conduct further experiments to analyze the results. We investigate two complementary phenomena from developmental robotics. First, we demonstrate PICMA 2’s ability to adapt to slowly or abruptly changing tasks due to its continual and adaptive exploration. This is an important component of life-long skill learning in dynamic environments. Second, we show on a reaching task PICMA 2 how subsequently releases degrees of freedom from proximal to more distal limbs as learning progresses. A similar effect is observed in human development, where it is known as ‘proximodistal maturation’.

International audience; Artificial olfaction systems; which mimic human olfaction by using arrays of gas chemical sensors combined with pattern recognition methods, represent a potentially low-cost tool in many areas of industry such as perfumery, food and drink production, clinical diagnosis, health and safety, environmental monitoring and process control. However, successful applications of these systems are still largely limited to specialized laboratories. Sensor drift, i.e., the lack of a sensor's stability over time, still limits real industrial setups. This paper presents and discusses an evolutionary based adaptive drift-correction method designed to work with state-of-the-art classification systems. The proposed approach exploits a cutting-edge evolutionary strategy to iteratively tweak the coefficients of a linear transformation which can transparently correct raw sensors' measures thus mitigating the negative effects of the drift. The method learns the optimal correction strategy without the use of models or other hypotheses on the behavior of the physical chemical sensors.

International audience; We present two new approaches to address the optimization problem associated with engine calibration. In this area, the tuning parameters are traditionally determined in a local way, i.e., at each engine operating point, via a single-objective minimization problem. To overcome these restrictions, the first method we propose is able to cope with several objective functions simultaneously in the local formulation. The second method we put forward relies on a global formulation, which allows the whole driving cycle to be taken into account while remaining single-objective. At the practical level, the two methods are implemented by combining various existing techniques such as the LoLiMoT (Local Linear Model Tree) parameterization and the MO-CMA-ES (Multi-Objective Covariance Matrix Adaptation Evolution Strategy) algorithm. A better compromise appears to be achieved on real case applications. Keywords Engine calibration · Response surface · LoLiMoT · Multi-objective optimization · Evolutionary algorithm Nomenclature Abbreviations (by alphabetical order)