Best Paper Awards à GECCO 2015
GECCO (Genetic and Evolutionary Computation Conference) est l’une des meilleures conférences en modèles de calcul bioinspirés. Quatre laboratoires de l’INS2I se sont distingués lors de la session de 2015 en obtenant des Best Paper Awards dans différentes catégories.
- Dans la catégorie Estimation of Distribution Algorithms (EDA)+ THEORY
Improved Runtime Bounds for the (1+1) EA on Random 3-CNF Formulas Based on Fitness-Distance Correlation de Benjamin Doerr du Laboratoire d’Informatique de l’École Polytechnique (LIX - CNRS/École polytechnique), Frank Neumann de l’University of Adelaide et Andrew M. Sutton de Hasso-Plattner-Institut
Abstract : With this paper, we contribute to the theoretical understanding of randomized search heuristics by investigating their behavior on random 3-SAT instances. We improve the results for the (1+1) EA obtained by Sutton and Neumann [PPSN 2014, 942—951] in three ways. First, we reduce the upper bound by a linear factor and prove that the (1+1) EA obtains optimal solutions in time $O(n \log n)$ with high probability on asymptotically almost all high-density satisfiable 3-CNF formulas. Second, we extend the range of densities for which this bound holds to satisfiable formulas of at least logarithmic density. Finally, we complement these mathematical results with numerical experiments that summarize the behavior of the (1+1) EA on formulas along the density spectrum, and suggest that the implicit constants hidden in our bounds are low. Our proofs are based on analyzing the run of the algorithm by establishing a fitness-distance correlation. This approach might be of independent interest and we are optimistic that it is useful for the analysis of randomized search heuristics in various other settings. To our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.
- Dans la catégorie Evolutionary Combinatorial Optimization and Metaheuristics (ECOM)
Global vs Local Search on Multi-objective NK-landscapes : Contrasting the Impact of Problem Features de Fabio Daolio de Shinshu University, Arnaud Liefooghe du Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL - CNRS/Université Lille 1/École Centrale de Lille), Sébastien Verel de l’Université du Littoral Côte d’Opale, Hernán Aguirre de Shinshu University et Kiyoshi Tanaka de Shinshu University
Abstract : Computationally hard multi-objective combinatorial optimization problems are common in practice, and numerous evolutionary multi-objective optimization (EMO) algorithms have been proposed to tackle them. Our aim is to understand which (and how) problem features impact the search performance of such approaches. In this paper, we consider two prototypical dominance-based algorithms : a global EMO strategy using an ergodic variation operator (GSEMO) and a neighborhood-based local search heuristic (PLS). Their respective runtime is estimated on a benchmark of combinatorial problems with tunable ruggedness, objective space dimension, and objective correlation ($\rho$MNK-landscapes). In other words, benchmark parameters define classes of instances with increasing empirical problem hardness ; we enumerate and characterize the search space of small instances. Our study departs from simple performance comparison to systematically analyze the correlations between runtime and problem features, contrasting their association with search performance within and across instance classes, for both chosen algorithms. A mixed-model approach then allows us to further generalize from the experimental design, supporting a sound assessment of the joint impact of instance features on EMO search performance.
- Dans la catégorie Evolutionary Machine Learning -EML
Subspace clustering using evolvable genome structure de Sergio Peignier, Christophe Rigotti et Guillaume Beslon du Laboratoire d’Informatique en Images et Systèmes d’Information (LIRIS - CNRS/INSA de Lyon/Université Claude Bernard Lyon 1/Université Lumière Lyon 2/École Centrale de Lyon)
Abstract : In this paper we present an evolutionary algorithm to tackle the subspace clustering problem. Subspace clustering is recognized as more difficult than standard clustering since it requires to identify not only the clusters but also the various subspaces where the clusters hold. We propose to tackle this problem with a bio-inspired algorithm that includes many bio-like features like variable genome length and organization, functional and non-functional elements, and variation operators including chromosomal rearrangements. These features give the algorithm a large degree of freedom to achieve subspace clustering with satisfying results on a reference benchmark with respect to state of the art methods. One of the main advantages of the approach is that it needs only one subspace clustering ad-hoc parameter : the maximal number of clusters. This is a single and intuitive parameter that sets the maximal level of details of the clustering, while other algorithms require more complicated parameter space exploration. The other parameters of the algorithm are related to the evolution strategy (population size, mutation rate, …) and for them we use a single setting that turns out to be effective on all the datasets of the benchmark.
- Dans la catégorie Genetic Programming - GP
Memetic Semantic Genetic Programming de Robyn Ffrancon et Marc Schoenauer du Laboratoire de Recherche en Informatique (LRI - CNRS/Université Paris-Sud)
Abstract : Semantic Backpropagation (SB) was introduced in GP so as to take into account the semantics of a GP tree at all intermediate states of the program execution, i.e., at each node of the tree. The idea is to compute the optimal "should-be" values each subtree should return, whilst assuming that the rest of the tree is unchanged, so as to minimize the fitness of the tree. To this end, the Random Desired Output (RDO) mutation operator, proposed in [17], uses SB in choosing, from a given library, a tree whose semantics are preferred to the semantics of a randomly selected subtree from the parent tree. Pushing this idea one step further, this paper introduces the Brando (BRANDO) operator, which selects from the parent tree the overall best subtree for applying RDO, using a small randomly drawn static library. Used within a simple Iterated Local Search framework, BRANDO can find the exact solution of many popular Boolean benchmarks in reasonable time whilst keeping solution trees small, thus paving the road for truly memetic GP algorithms.