Optimisation pour la resolution des problemes difficiles par les methodes classico-metaheuristiques

Les problèmes d‟optimisation occupent actuellement une place grandissante dans la communauté scientifique. Ces problèmes peuvent être combinatoires (discrets) ou à variables continues, avec un seul ou plusieurs objectifs (optimisation mono ou multi-objectifs), statiques ou dynamiques, avec ou sans contraintes. Cette liste n‟est pas exhaustive et un problème peut être, par exemple, à la fois continu et dynamique. L‟optimisation combinatoire est une branche de l’optimisation en mathématiques appliquées et en informatique, également située au carrefour des différentes sciences et technologies liées à la recherche opérationnelle, l’algorithmique et la théorie de la complexité. C‟est plutôt incontournable dans tous les domaines car dans la plupart des cas, on l‟appelle souvent : „‟aide à la décision‟‟.

Un problème d‟optimisation est défini par un ensemble de variables, une fonction objectif (ou fonction de coût) et un ensemble de contraintes. L‟espace de recherche est l‟ensemble des solutions possibles du problème. Il possède une dimension pour chaque variable. Pour des raisons pratiques et de temps de calcul, l‟espace de recherche des méthodes de résolution est en général fini. La fonction objectif définit le but à atteindre, on cherche à minimiser ou à maximiser celle-ci. L‟ensemble des contraintes est en général un ensemble d‟égalités et d‟inégalités que les variables doivent satisfaire. Ces contraintes limitent l‟espace de recherche. Malgré la simplicité apparente de leur définition, les graphes occupent une large part de la complexité algorithmique. Il est donc très important de bien comprendre la structure des graphes afin de l’utiliser dans des modélisations pertinentes (i.e. des modélisations sur lesquelles les algorithmes de résolution sont efficaces).

Historique

Au fil de l’histoire, la collaboration entre les scientifiques et les militaires est fréquent afin de prendre les meilleures décisions dans les batailles et d’essayer d‟obtenir la victoire. C‟est pour cela que beaucoup d’experts dans le domaine considèrent le début de la Recherche Opérationnelle dans le IIIe siècle av. J.-C, pendant les Guerres puniques, avec l’analyse et la solution qu’Archimède a proposé pour la défense de la ville de Syracuse, assiégée par les romains. Parmi ses inventions, on trouve la catapulte et un système de miroirs qui enflammait les embarcations ennemies en faisant usage des rayons de soleil.

En 1503, Léonard de Vinci avait participé comme ingénieur dans la guerre contre Pise puisqu’il connaissait les techniques pour bombarder, construire des bateaux, des véhicules cuirassés, des canons, des catapultes et d’autres machines de guerre. Un autre précédent est l’usage de la Recherche Opérationnelle pendant la Première Guerre mondiale en Angleterre, grâce à l’étude mathématique de Frederick William Lanchester sur la puissance balistique des forces opposantes. En plus, il a développé, à partir d’un système d’équations différentielles, la Loi quadratique de Lanchester, avec laquelle il était possible de déterminer le dénouement d’une bataille militaire en fonction de la force numérique relative et la capacité relative de feu des combattants. Comme tout progrès scientifique, la Recherche Opérationnelle a été utilisé premièrement dans de buts militaires. Cependant, grâce aux profits, elle a été adoptée dans d’autres domaines tel que l’industrie, le transport, l’urbanisme, le commerce, les finances, le service sanitaire, etc. pour optimiser les ressources disponibles et obtenir des bénéfices, essentiellement économiques. Néanmoins, la Recherche Opérationnelle n’était pas considérée comme une science que jusqu’à la Seconde Guerre mondiale, pendant la bataille d’Angleterre. La Luftwaffe, armée de l’air allemande, soumettait ce pays à de grands assauts dues à la capacité aérienne britannique réduite à cause de la politique de désarmement, bien qu’expérimentée dans le combat. Le gouvernement britannique, dans le dessein de trouver une méthode pour défendre son pays, a convoqué des scientifiques de diverses disciplines pour résoudre le problème et profiter ainsi des radars d’invention récents dont ils disposaient. Grâce à son travail de localisation optimale des antennes et à l’amélioration de la distribution des signaux, ils ont doublé l’effectivité du système de défense aérienne et ils ont évité que l’île tombe entre les mains de l’Allemagne nazie.

Problème d’optimisation 

Lorsque l‟on veut résoudre un problème d‟optimisation, on recherche la meilleure solution possible à ce problème, c‟est-à-dire l‟optimum global. Cependant, il peut exister des solutions intermédiaires, qui sont également des optimums, mais uniquement pour un sous-espace restreint de l‟espace de recherche : on parle alors d’optimums locaux. Un problème d‟optimisation se définit comme la recherche, parmi un ensemble de solutions possibles S (appelé aussi espace de décision ou espace de recherche), de la (ou des) solution(s) X* qui rend minimale (ou maximale) une fonction mesurant la qualité de cette solution. Cette fonction est appelée fonction objectif ou fonction coût. Si l‟on pose :
f : S ➙ R la fonction objectif à minimiser (respectivement à maximiser) à valeurs dans R, le problème revient alors à trouver l‟optimum x* S tel que f(x*) soit minimal (resp maximal).

Classification des méthodes d’optimisation

La résolution d‟un problème d‟optimisation est réalisée à l‟aide de diverses méthodes dont la classification est illustrée comme dans la Figure 3 ci-dessous. On distingue en premier lieu l‟optimisation continue de l‟optimisation discrète (ou combinatoire). Cette première distinction concerne la nature des « espaces » dans lesquels les variables de décision prennent leurs valeurs : c‟est la dichotomie « discret-continu » bien marquée en Mathématiques et qui conditionne évidemment beaucoup les possibilités de recourir à certaines méthodes. Pour l‟optimisation continue, on sépare sommairement le cas linéaire (qui relève notamment de la programmation linéaire) du cas non linéaire, où l‟on retrouve le cadre de l‟optimisation difficile.

i- Pour les problèmes d‟optimisation classés comme facile et de taille raisonnable, les méthodes exactes peuvent trouver des solutions optimales. Ces méthodes explorent de façon systématique l‟espace des combinaisons jusqu‟à trouver une solution optimale.

ii- Lorsque l‟on dispose d‟un temps de calcul limité ou lorsqu‟on est confronté à des problèmes difficiles ou de taille importante, on peut avoir recours aux méthodes approchées, en se contentant de rechercher une solution de « bonne qualité ». On l‟appelle souvent « métaheuristique ».

L’optimisation combinatoire

En suivant la définition mathématique, l’optimisation recouvre toutes les méthodes qui permettent de déterminer l’optimum d’une fonction, avec ou sans contraintes.

Dans une autre vision, c‟est le domaine qui étudie les problèmes de la forme :

Max x ∈ X. f(x). (1.01)

Où X est un ensemble fini, mais de très grande taille A chaque instance du problème est associé un ensemble discret de solutions S, un sous ensemble X de S représentant les solutions admissibles (réalisables), ainsi qu‟une fonction de coût f (appelée aussi fonction objectif). f assigne à chaque solution s ∈ X le nombre f(s).

Résoudre un problème d‟optimisation combinatoire consiste alors à trouver une solution s ∈ X optimisant la valeur de la fonction de coût f. Mathématiquement, on cherche donc s* ∈ X tel que f(s*) ≤ f(s) pour tout s ∈ X. Une telle solution s* s’appelle une solution optimale, ou un optimum global.

Il existe une seconde formalisation du problème d‟optimisation combinatoire, plus générale, qui inclue la notion de contraintes et d‟affectation de valeurs à des variables.

Optimisation sous contraintes

La plupart des problèmes posés dans le monde réel sont souvent soumis à des contraintes. Plusieurs méthodes, classiques et évolutionnistes, ont été développées pour prendre en compte la confrontation face à ces contraintes. Un problème d‟optimisation sous contraintes contient deux aspects. L‟aspect « contraintes » et l‟aspect « optimisation ».

a. L‟aspect « contraintes » sert à spécifier la forme que devrait avoir un objet solution du problème.
b. L‟aspect « optimisation » sert à classifier les objets vérifiant cette forme et à sélectionner le(s) meilleure(s).

Table des matières

INTRODUCTION GENERALE
Présentation du problème et les principales disciplines
CHAPITRE 1 LE PROBLEME D‟OPTIMISATION
1.1 Introduction à la première partie
1.2 Historique
1.3 Problème d‟optimisation
1.3.1 Classification des méthodes d‟optimisation
1.3.2 L‟optimisation combinatoire
1.3.3 Optimisation sous contraintes
1.3.4 Problème de satisfaction de contraintes
1.3.5 Problème d‟optimisation combinatoire sous contraintes
1.4 Complexité d’un problème d’optimisation
1.4.1 Définitions
1.4.2 La classe P
1.4.3 La classe NP
1.5 Les méthodes de résolution exacte et méthode approchée
1.5.1 Heuristique et métaheuristique
1.5.2 Historique
1.5.3 Heuristique
1.5.4 Métaheuristique (ou méta-heuristique)
1.5.5 Processus stochastiques
1.6 Conclusion
CHAPITRE 2 LES METHODES DE RESOLUTION ET LES CONCEPTS
2.1 Introduction à la deuxième partie
2.2 État de l‟art
2.3 La théorie des graphes
2.3.1 Définition
2.3.2 Notions de base sur les graphes
2.3.2.1 Graphes non orientés
2.3.2.2 Graphes orientés
2.3.2.3 Graphes valués
2.3.2.4 Graphes aléatoires
2.3.2.5 Représentation matricielle
2.4 Algorithme
2.4.1 Définition
2.4.2 Relations Mathématique (théories des graphes) et informatique (Algorithme)
2.4.2.1 Problème algorithmique
2.4.2.2 Algorithmes polynomiaux
2.4.3 Problèmes classiques d‟optimisation combinatoire
2.4.3.1 Problème du voyageur de commerce
2.4.3.2 Problème d’affectation
2.4.3.3 Problème du sac-à-dos
2.4.3.4 Problème d’ordonnancement
2.4.4 Plus courts chemins
2.4.4.1 Algorithme de Dijkstra
Algorithme
2.4.4.2 Algorithme de Bellman-Ford
Algorithme
2.4.4.3 Algorithme de Ford et Fulkerson
Algorithme
2.4.4.4 Plan d’ordonnancement
Algorithme
2.5 Intelligence Artificielle (I.A)
2.6 Simulation informatique
2.7 Les métaheuristiques à la résolution des problèmes d‟optimisations difficiles
2.7.1 Classification des métaheuristiques
2.7.1.1 Les approches « trajectoire »
2.7.1.2 Les approches « population » (ou évolutionnaires)
2.7.2 Analyse des principales métaheuristiques
2.7.2.1 La méthode de descente
Avantages et inconvénients
2.7.2.2 La méthode du recuit simulé
Avantages et inconvénients
2.7.2.3 La méthode Tabou
Avantages et inconvénients
2.7.2.4 La méthode GRASP
Avantages et inconvénients
2.7.2.5 Les algorithmes génétiques
Avantages et inconvénients
2.7.2.6 Les algorithmes de colonies de fourmi
Principe de l’algorithme
Avantages et Inconvénients
2.8 Stratégies de recherche
2.8.1 Intensification et diversification
2.8.1.1 La méthode de descente
2.8.1.2 Algorithme du recuit simulé
2.8.1.3 La méthode Tabou
2.8.1.4 La méthode GRASP
2.8.1.5 Les algorithmes génétiques
2.8.1.6 Les algorithmes à colonies de fourmi
2.8.2 Quelle métaheuristique utiliser ?
2.9 Bilan et perspectives
2.10 Conclusion
CHAPITRE 3 CONCEPTION, REALISATION ET SIMULATION
3.1 Introduction
3.2 Architecture et représentation
3.2.1 Le graphe d’un point de vue « model »
3.2.2 Le graphe d’un point de vue « view »
3.2.2.1 Mise en place des noeuds
3.2.2.2 La gestion des points et la résolution
3.3 Manuel utilisateur et mise en marche
3.4 Implémentation et jeux de tests
3.4.1 Paramètres systèmes
3.4.2 Résultats numériques et expérimentaux
3.5 Critères de comparaison des algorithmes
3.6 Outillage mathématique
3.6.1 La méthode des moindres carrés
3.6.2 Calculs de corrélation et coefficient de régression
3.6.3 Calcul du coefficient de détermination
3.6.4 Déduction des fonctions Y et les coefficients de déterminations pour chaque algorithmes
3.6.5 Comparaison mathématique
3.7 Objectifs atteints
3.8 Conclusion
CONCLUSION GENERALE
ANNEXES

Lire le rapport complet