Complexité des problèmes et heuristiques
195
problème abordé : ce ne seront pas les mêmes pour un problème d'ordonnancement
d'atelier et pour un problème de voyageur de commerce.
Compte tenu de la nature de ces méthodes, il n'est pas très étonnant que peu de résultats
généraux existent sur leurs performances. Citons cependant la théorie des schémas, qui a
donné lieu à quelques résultats de ce type. Mais là encore, la mise en route de ces
heuristiques nécessite une solide expérience en la matière (fixation de nombreux
ingrédients : codage, taille de la population, probabilités et opérateurs de croisement et
de mutation, nombre d'itérations etc.).
Les algorithmes génétiques, comme les autres, se sont attaqués non sans succès à de très
difficiles problèmes combinatoires, comme ceux d'ordonnancement d'atelier. La
recherche est très active dans le domaine et consiste notamment, sur des problèmes de
taille importante, à comparer les performances des différentes méthodes que nous
venons d'exposer. Il y en a d'autres, d'ailleurs (citons la technique également connue des
« réseaux neuronaux », qui nous semble moins centrale pour les problèmes qui nous
occupent ici).
Un des avantages de ce type de méthode est le peu de savoir mathématique qu'elles
présupposent. Alors que les méthodes d'optimisation connues en mathématiques
reposent sur des connaissances étendues (lagrangiens, hessiens, conditions de Kuhn et
Tucker, etc.) demandant un certain effort de compréhension et des bases solides en
mathématiques (tout en étant en général peu adaptées aux problèmes particuliers
mobilisés par la recherche opérationnelle, sauf exception -on a évoqué un exemple
d'importation de ces méthodes classiques avec les algorithmes de point intérieur pour la
programmation linéaire), les algorithmes génétiques exigent très peu de « back ground »
de ce type. Mais c'est là une des caractéristiques générales des méthodes de la recherche
opérationnelle, comme on l'a souligné en introduction.
Après ce survol des problèmes combinatoires difficiles, nous allons revenir à des
problèmes moins « chevelus » car relevant d'algorithmes polynomiaux : les problèmes
de flots.
195
problème abordé : ce ne seront pas les mêmes pour un problème d'ordonnancement
d'atelier et pour un problème de voyageur de commerce.
Compte tenu de la nature de ces méthodes, il n'est pas très étonnant que peu de résultats
généraux existent sur leurs performances. Citons cependant la théorie des schémas, qui a
donné lieu à quelques résultats de ce type. Mais là encore, la mise en route de ces
heuristiques nécessite une solide expérience en la matière (fixation de nombreux
ingrédients : codage, taille de la population, probabilités et opérateurs de croisement et
de mutation, nombre d'itérations etc.).
Les algorithmes génétiques, comme les autres, se sont attaqués non sans succès à de très
difficiles problèmes combinatoires, comme ceux d'ordonnancement d'atelier. La
recherche est très active dans le domaine et consiste notamment, sur des problèmes de
taille importante, à comparer les performances des différentes méthodes que nous
venons d'exposer. Il y en a d'autres, d'ailleurs (citons la technique également connue des
« réseaux neuronaux », qui nous semble moins centrale pour les problèmes qui nous
occupent ici).
Un des avantages de ce type de méthode est le peu de savoir mathématique qu'elles
présupposent. Alors que les méthodes d'optimisation connues en mathématiques
reposent sur des connaissances étendues (lagrangiens, hessiens, conditions de Kuhn et
Tucker, etc.) demandant un certain effort de compréhension et des bases solides en
mathématiques (tout en étant en général peu adaptées aux problèmes particuliers
mobilisés par la recherche opérationnelle, sauf exception -on a évoqué un exemple
d'importation de ces méthodes classiques avec les algorithmes de point intérieur pour la
programmation linéaire), les algorithmes génétiques exigent très peu de « back ground »
de ce type. Mais c'est là une des caractéristiques générales des méthodes de la recherche
opérationnelle, comme on l'a souligné en introduction.
Après ce survol des problèmes combinatoires difficiles, nous allons revenir à des
problèmes moins « chevelus » car relevant d'algorithmes polynomiaux : les problèmes
de flots.