Les algorithmes génétiques et leur application aux problèmes d' ordonnancement

摘要

Les méthodes génétiques sont de plus en plus utilisées pour la résolution de problèmes d'optimisation. Cet article décrit tout d'abord les principes fondamentaux des algorithmes génétiques "classiques" basés sur des représentations binaires des solutions (évaluation, sélection, opérateurs génétiques). Des extensions de ces algorithmes, appelées algorithmes évolutionnistes et basées sur des représentations non binaires des solutions ou sur des évolutions de l'algorithme sont ensuite présentées. Les problèmes d'ordonnancement sont modélisés grâce à différentes méthodes de représentation des permutations qui sont présentées. Ces méthodes permettent la prise en compte de certaines contraintes mais nécessitent des opérateurs génétiques spécifiques. Une revue des opérateurs génétiques travaillant sur les permutations est alors effectuée. Pour terminer la présentation de cet état de l'art, nous appliquons des méthodes génétiques à un problème de voyageur de commerce.%Recently, genetic methods have been successfully applied to various optimization problems. In this paper, we first describe the genetic algorithms foundations (selection, evaluation, genetic operators). These algorithms are based on a binary string representation of solutions. Then, we present some extensions of the genetic algorithms named evolutionary algorithms. These extensions use a non-binary representation of solutions and a modified algorithm. We detail some representation methods of permutations in order to model scheduling problems. These methods allow to model constrained problems but they require specific genetic operators. So, a review of the main genetic operators is given. An example of the genetic algorithms applied to the traveling salesman problem concludes the presentation on the genetic methods state of the art.