On distingue en réalité deux types de problèmes d’optimisation : les problèmes combinatoires (ou problèmes “discrets”) et les problèmes à variables continues. Pour clarifier, citons
quelques exemples : parmi les problèmes combinatoires, on trouve le problème du voyageur
de commerce mentionné plus haut, ou encore celui de l’ordonnancement de tâches concourant
à un même projet. Deux exemples de problèmes continus sont les suivants : l’identification
des paramètres d’un modèle associé à un composant électronique, à partir de données expé-rimentales caractérisant celui-ci ; la restauration optimale d’une image, à partir d’une image brouillée.
Cette différenciation est nécessaire pour cerner le domaine de l’optimisation difficile. En
effet, deux sortes de problèmes reçoivent, dans la littérature, cette appellation, non définie
strictement (et liée, en fait, à l’état de l’art en matière d’optimisation) :
– certains problèmes d’optimisation combinatoire, pour lesquels on ne connaît pas d’al-gorithme exact rapide. C’est le cas, en particulier, des problèmes dits “NP-difficiles”,
c’est-à-dire - schématiquement - dont la résolution exacte n’est pas possible en un
temps de calcul proportionnel à N n , où N désigne le nombre de paramètres inconnus
du problème, et n est un entier.
– certains problèmes d’optimisation à variables continues, pour lesquels on ne connaît
pas d’algorithme permettant de repérer un optimum global à coup sûr et en un nombre
fini de calculs.
Des efforts ont longtemps été menés, séparément, pour résoudre ces deux types de problèmes
“difficiles”. Dans le domaine de l’optimisation continue, il existe ainsi un arsenal important
de méthodes classiques dites d’optimisation globale, mais ces techniques sont souvent ineffi-caces si la fonction objectif ne possède pas une propriété structurelle particulière, telle que la
convexité. Dans le domaine de l’optimisation combinatoire, un grand nombre d’heuristiques,
qui produisent des solutions proches de l’optimum, ont été développées ; mais la plupart
d’entre elles ont été conçues spécifiquement pour un problème donné.
télécharger
