Les algorithmes génétiques: théorie et applications

  • Romain HENDRICKX

    Student thesis: Master typesMaster in Mathematics

    Abstract

    Genetic algorithms (GAs) are metaheuristics for discrete optimization problems inspired by Darwin's theory of evolution. Roughly speaking, candidate solutions from the search space are seen as individuals from an abstract world, in which their adaptibility is described by some fitness function corresponding to the objective function, such that higher is the objective value, fitter is the individual. Then, considering some initial random-created individuals and simulating on this population an evolution process, based on both recombination operations, whose goal are to introduce perturbations in candidate solutions in order to explore the search space, and selection operation, whose goal is to determine, according to the indivual's fitness, which of them are chosen to the next generation, GAs provide individuals with fitness growing up over generations, and thus candidate solutions closer to the optimal value. The main goal of this master's thesis is to give an overview of how and why GAs works. The first part consists in introducing the basic structure of a genetic algorithm, and giving some well-known specifications for the recombination and selection operators, as well as a theoretical justification of their use (chapter 3). The second part is devoted to the illustration of the GAs on a few concrete and/or real problems. For example, we study the problem of designing an optimal strategy for a robot cleaning a given floor strewn with empty soda cans (known as rRobby, the Soda-Can-Collecting Robot", chapter 4). We also consider the robust optimization of event-related design in fMRI (achieved in the framework of the research stage of the Master 2, chapter 5).
    Date of Award24 Jun 2011
    Original languageFrench
    SupervisorTimoteo Carletti (Supervisor), Bertrand Hespel (Jury), Jean-Paul LECLERCQ (Jury) & Anne Lemaitre (Jury)

    Cite this

    '