Complexité des problèmes et heuristiques
191
La taille de la liste Tabou est en général de l'ordre de la dizaine, mais là aussi d'autres
choix sont possibles.
La méthode Tabou a été appliquée à de nombreux problèmes combinatoires difficiles.
Citons par exemple le planning de cours ou le planning d'examens dans les universités,
problème hautement combinatoire (affectation de cours ou d'examens à la fois à des
salles et à des horaires) qui représente classiquement des '' casse-tête '' terrifiants pour les
directions des études.
Un autre type d'heuristique actuellement en vogue se fonde sur des principes assez
différents que ceux qui sont à la base des méthodes d'itération d'une solution à une autre
par voisinage : il s'agit des algorithmes génétiques.
8.2.4. Les algorithmes génétiques
Les algorithmes génétiques portent leur nom à cause d'une analogie (les heuristiques
sont friandes en métaphores) avec les phénomènes d'évolution des espèces, et plus
précisément des processus de mutation et de reproduction des individus. Comme on le
sait, ces processus vont mettre en cause les gènes et les chromosomes de ces individus,
agissant soit par mutation (changement d'un gène dans un chromosome) soit par
substitution de séquences de gènes à d'autres (croisement) lors de la reproduction. Les
algorithmes génétiques sont alors fondés sur l'idée suivante : dans la mesure où les
processus biologiques conduisent à une certaine adaptation des espèces à leur milieu, la
descendance d'individus adaptés va probablement être également adaptée, et peut-être en
mieux. Si on fait l'analogie avec les solutions d'un problème combinatoire et si l'on peut
engendrer des solutions nouvelles à partir de solutions existantes, conservant les
« bonnes » caractéristiques des premières, alors on disposera de solutions
progressivement meilleures.
Par différence avec les méthodes que nous venons de voir, les algorithmes génétiques
vont examiner non pas une solution l'une après l'autre mais un ensemble de
solutions
, appelée population, de taille en général fixée à l'avance. Chaque
solution est codée dans un alphabet donné de caractères, qui sont souvent les caractères
(programme linéaire en nombres entiers par exemple) mais qui peuvent être d'une
autre nature (liste des arcs par exemple dans le problème du voyageur de commerce ou
encore numéros des machines sur lesquelles doivent passer des pièces dans un problème
d'ordonnancement). La séquence des caractères d'une solution, par analogie avec les
processus biologiques, sera appelée chromosome de la solution et un caractère donné
gène.
Puisque l'on veut sélectionner des individus '' forts '' afin qu'ils aient une descendance
également ou encore plus forte, il faut un indicateur de cette force : on prend tout
simplement la valeur de la fonction économique pour l'individu - la solution - considéré.
Plus cette valeur est faible (on a choisi de minimiser ), plus la solution mérite d'être
sélectionnée dans le processus de reproduction.
On peut énoncer alors la forme générale d'un algorithme génétique (il existe cela dit de
nombreuses variantes et on peut toujours en inventer de nouvelles) :
191
La taille de la liste Tabou est en général de l'ordre de la dizaine, mais là aussi d'autres
choix sont possibles.
La méthode Tabou a été appliquée à de nombreux problèmes combinatoires difficiles.
Citons par exemple le planning de cours ou le planning d'examens dans les universités,
problème hautement combinatoire (affectation de cours ou d'examens à la fois à des
salles et à des horaires) qui représente classiquement des '' casse-tête '' terrifiants pour les
directions des études.
Un autre type d'heuristique actuellement en vogue se fonde sur des principes assez
différents que ceux qui sont à la base des méthodes d'itération d'une solution à une autre
par voisinage : il s'agit des algorithmes génétiques.
8.2.4. Les algorithmes génétiques
Les algorithmes génétiques portent leur nom à cause d'une analogie (les heuristiques
sont friandes en métaphores) avec les phénomènes d'évolution des espèces, et plus
précisément des processus de mutation et de reproduction des individus. Comme on le
sait, ces processus vont mettre en cause les gènes et les chromosomes de ces individus,
agissant soit par mutation (changement d'un gène dans un chromosome) soit par
substitution de séquences de gènes à d'autres (croisement) lors de la reproduction. Les
algorithmes génétiques sont alors fondés sur l'idée suivante : dans la mesure où les
processus biologiques conduisent à une certaine adaptation des espèces à leur milieu, la
descendance d'individus adaptés va probablement être également adaptée, et peut-être en
mieux. Si on fait l'analogie avec les solutions d'un problème combinatoire et si l'on peut
engendrer des solutions nouvelles à partir de solutions existantes, conservant les
« bonnes » caractéristiques des premières, alors on disposera de solutions
progressivement meilleures.
Par différence avec les méthodes que nous venons de voir, les algorithmes génétiques
vont examiner non pas une solution l'une après l'autre mais un ensemble de
solutions
, appelée population, de taille en général fixée à l'avance. Chaque
solution est codée dans un alphabet donné de caractères, qui sont souvent les caractères
(programme linéaire en nombres entiers par exemple) mais qui peuvent être d'une
autre nature (liste des arcs par exemple dans le problème du voyageur de commerce ou
encore numéros des machines sur lesquelles doivent passer des pièces dans un problème
d'ordonnancement). La séquence des caractères d'une solution, par analogie avec les
processus biologiques, sera appelée chromosome de la solution et un caractère donné
gène.
Puisque l'on veut sélectionner des individus '' forts '' afin qu'ils aient une descendance
également ou encore plus forte, il faut un indicateur de cette force : on prend tout
simplement la valeur de la fonction économique pour l'individu - la solution - considéré.
Plus cette valeur est faible (on a choisi de minimiser ), plus la solution mérite d'être
sélectionnée dans le processus de reproduction.
On peut énoncer alors la forme générale d'un algorithme génétique (il existe cela dit de
nombreuses variantes et on peut toujours en inventer de nouvelles) :