Français Anglais
Accueil Annuaire Plan du site
Home > Research results > Dissertations & habilitations
Research results
Ph.D de

Ph.D
Group : Learning and Optimization

Adaptive operator selection in evolutionary algorithms

Starts on 10/10/2007
Advisor : SCHOENAUER, Marc

Funding : CDD sur contrat INRIA
Affiliation : Université Paris-Sud
Laboratory : LRI AO

Defended on 22/12/2010, committee :
- Agoston E. Eiben (rapporteur), Vrije Universiteit Amsterdam, Pays-Bas
- Youssef Hamadi, Microsoft Research Cambridge, Royaume-Uni
- Yannis Manoussakis, Université Paris-Sud XI
- Marc Schoenauer (directeur de thèse), INRIA Saclay
- Michele Sebag (directrice de thèse), CNRS/LRI
- Thomas Stuetzle (rapporteur), FNRS/IRIDIA, Bruxelles, Belgique
- Dirk Thierens, Universiteit Utrecht, Pays-Bas

Research activities :

Abstract :
Evolutionary Algorithms (EAs) are stochastic optimization algorithms which
have already shown their efficiency on many application domains. This is
achieved mainly due to the many parameters that can be defined by the user
according to the problem at hand. However, the performance of EAs is very
sensitive to the setting of these parameters, and there are no general
guidelines for an efficient setting; as a consequence, EAs are rarely used
by researchers from domains other than computer science. The
methodsproposed in this thesis contribute towards alleviating the user
from theneed of defining two very sensitive and problem-dependent choices:
whichvariation operators should be used for the generation of new
solutions, and at which rate each operator should be applied. The
paradigm, referredto as Adaptive Operator Selection (AOS), provides the
on-line autonomouscontrol of the operator that should be applied at each
instant of the search, i.e., while solving the problem. In order to do so,
one needs to define a Credit Assignment scheme, which rewards the
operators based on theimpact of their recent applications on the current
search process, and an Operator Selection mechanism, that decides which
should be the next operator to be applied, based on the empirical quality
estimates built by the rewards received. In this work, we have tackled the
Operator Selection problem as an instance of the Exploration versus
Exploitation dilemma: the best operator needs to be exploited as much as
possible, while the others should also be minimally explored from time to
time, as one of them might become the best in a further moment of the
search. We have proposed different Operator Selection techniques to extend
the Multi-Armed Bandit paradigm to the dynamic context of AOS. On the
Credit Assignment side, we have proposed rewarding schemes based on
extreme values and on ranks, in order to promote the use of outlier
operators, while providing more robust operator assessments. The different
AOS methods formed by the combinations of the proposed Operator Selection
and Credit Assignment mechanisms have been validated on a very diverse set
of benchmark problems. Based on empirical evidence gathered from this
empirical analysis, the final recommended method, which uses the
Rank-based Multi-Armed Bandit Operator Selection and the Area-Under-Curve
Credit Assignment schemes, has been shown to achieve state-of-the-art
performance while also being very robust withrespect to different

Ph.D. dissertations & Faculty habilitations
APPRENTISSAGE ET OPTIMISATION SUR LES GRAPHES


ANALYSE DE DONNéES MULTI-MODALES POUR LES PATHOLOGIES COMPLEXES PAR LA CONCEPTION ET L’IMPLéMENTATION DE PROTOCOLES REPRODUCTIBLES ET RéUTILISABLES


DESIGNING INTERACTIVE TOOLS FOR CREATORS AND CREATIVE WORK
Creative work has been at the core of research in Human-Computer Interaction (HCI). I describe the results of a series of studies that look at how creators work, where creators include artists with years of professional practice, as well as learners, or novices and casual makers. My research focuses on three creation activities: drawing, physical modeling, and music composition. For these activities, I examine how artists switch between representations and how these representations evolve throughout their creative process, from early sketches to fine-grained forms or structured vocabularies. I present interactive systems that enrich their workflow (i) by extending their computer tools with physical user interfaces, or (ii) by making physical materials interactive. I also argue that sketch-based representations can allow for user interfaces that are more personal and less rigid. My presentation will reflect on lessons and limitations of this work and discuss challenges for future design-support tools.