4.3. L'optimisation combinatoire
L'optimisation combinatoire [4,16] occupe une place
très importante en recherche opérationnelle, en
mathématiques discrètes et en informatique. Son importance se
justifie d'une part par la grande difficulté des problèmes
d'optimisation et d'autre part par de nombreuses applications pratiques pouvant
être formulées sous la forme d'un problème d'optimisation
combinatoire. Bien que les problèmes d'optimisation combinatoire soient
souvent faciles à définir, ils sont généralement
difficiles à résoudre. En effet, la plupart de ces
problèmes appartiennent à la classe des problèmes
NP-difficiles et ne possèdent donc pas à ce jour de
solution algorithmique efficace valable pour toutes les données.
L'optimisation combinatoire est minimiser (ou maximiser) une
fonction souvent appelée fonction coût, d'une ou plusieurs
variables soumises à des contraintes. Le sujet de l'optimisation
combinatoire dans un domaine discret. Il faut trouver parmi toutes les
possibilités, souvent en nombre fini, la possibilité optimale.
Ceci parait facile mais devient infaisable dès que la taille du
problème est suffisamment grande. La taille pour laquelle la recherche
d'un optimum devient infaisable est petite, très souvent plus petite que
la taille des problèmes pratiques. En général, la
difficulté d'un problème grandit très vite avec le nombre
des variables. Il n'est pas alors faisable d'examiner toutes les
possibilités.
Les méthodes d'optimisation peuvent être
reparties en deux catégories :
1. Méthodes exactes.
2. Méthodes approchées.
Les méthodes exactes fournissent
systématiquement une solution (optimale) au problème
traité si une telle solution existe. Dans le cas contraire, ce type de
méthode permet d'affirmer qu'il n'existe pas de solution au
problème traité.
Les méthodes approchées fournissent une solution
approchée au problème traité. Elles sont en
général conçues de manière à ce que la
solution obtenue puisse être située par rapport à la valeur
optimale : de telle méthodes permettent d'obtenir des bornes
inférieures ou supérieures de la valeur optimale tel
que :
1- Méthodes Heuristiques ;
2- Méthodes Méta heuristiques.
4.4. La démarche heuristique
L'heuristique [5,17] est une méthode, une technique ou
un critère de guidage ou de décision, en général
empirique ou obtenu par approximation, permettant de choisir la voie la plus
prometteuse de recherche de la solution au problème posé, ou
d'éliminer les voies les moins intéressantes, sans garantie sur
la validité ou la précision de l'information ainsi fournie.
Entrer dans le domaine des heuristiques, c'est se
départir d'emblée les schémas classiques. En effet, alors
que la démarche classique mathématique est centrée sur
l'objet de l'étude, sur la compréhension de sa structure et de sa
logique, la démarche heuristique repousse le problème
lui-même au rang d'illustration pour dégager des schémas de
pensée plus généraux et donc originaux.
Les heuristiques disposent d'une simplicité et donc
d'une rapidité dans leur exécution plus élevée que
les algorithmes classiques. Ces règles s'appliquant à un ensemble
particulier la recherche des faits ce voit simplifiée et
accélérée (moins de possibilité). D'où une
analyse des situations améliorées. Mais une méthode
heuristique trop simplifiée ou au contraire trop générale
peut conduire à des biais cognitifs, générant des erreurs
de décision.
L'utilisation de plus de ces éléments simples
(les heuristiques) afin de créer des éléments plus
complexes (les méta- heuristiques) permet donc de réduire
considérablement l'ensemble de recherche global de l'algorithme.
L'une de leur caractéristique principale et à
première vue défaut, dont hérite également les
méta- heuristiques, est qu'ils peuvent dans certains cas ne pas proposer
de solution optimale au problème. Mais au résultat s'y approchant
d'assez près pour qu'il soit considéré comme correct, on
parle alors de garantie de performance.
| 
