Hybridations d’algorithmes métaheuristiques en optimisation globale et leurs applications

« Un bon croquis vaut mieux qu’un long discours » Napoléon 1er. 

Cette thèse s’intéresse à la résolution des problèmes mono-objectifs et multiobjectifs des structures mécaniques et mécatroniques. Elle a été menée au sein de l’équipe optimisation et analyse numérique du Laboratoire d’Étude et Recherche en Mathématiques Appliquées (LERMA, École Mohammadia d’Ingénieurs, Université Mohammed V) en collaboration avec l’équipe d’accueil optimisation fiabiliste des structures du Laboratoire d’Optimisation et FIabilité en Mécanique des Structures (LOFIMS, Institut National des Sciences Appliquées de Rouen).

La conception optimale, appelée aussi optimisation de formes devient un outil indispensable pour presque tous les domaines industriels, notamment en mécanique de structures ; c’est une préoccupation essentielle des chercheurs qui conçoivent des objets industriels innovants (structures mécaniques, profils aérodynamiques, antennes, composants électroniques, etc.) afin d’en augmenter des propriétés physiques essentielles (solidité, efficacité, durabilité et fiabilité). Cette conception doit aussi satisfaire des contraintes strictes telles que le coût, la faisabilité industrielle, mais aussi le poids ou le volume des structures, ou bien toute autre propriété physique importante. Il s’agit donc d’un problème classique en mathématiques : l’optimisation sous contraintes d’une fonction, dite objectif. Grâce au développement de la puissance de calcul des ordinateurs, les mathématiques sont devenues essentielles dans l’automatisation de ce processus d’optimisation. En effet, la méthode traditionnelle d’optimisation est de procéder par essais et erreurs, suivant le savoir-faire et l’intuition du chercheur : on essaye une forme dont on calcule la performance puis, en fonction de cette dernière, on la modifie pour essayer de l’améliorer et on recommence jusqu’à obtention d’une forme satisfaisante (à défaut d’être optimale). Cette façon analytique de faire est très lente, coûteuse et imprécise. De plus en plus, elle est remplacée par des logiciels d’optimisation numérique qui représentent la forme par un nombre limité de paramètres descriptifs (généralement des points de contrôle sur les bords), et l’améliorent itérativement en faisant varier ces paramètres de manière automatique.

L’Optimisation :Etat de l’art 

La résolution de problèmes d’optimisation est devenue un sujet central en recherche opérationnelle, le nombre de problèmes d’aide à la décision pouvant être formalisés sous la forme d’un problème d’optimisation étant en forte croissance[53]. Les problèmes d’apprentissage de réseaux de neurones, de planification des tâches ou encore d’identification sont, par exemple, des problèmes communs d’optimisation. En outre, l’Homme cherche à améliorer sa vie quotidienne, l’Homme aime la perfection ! Et sans qu’il se rend compte, il essaye à minimiser ses charges, son loyer ou la consommation de sa voiture….Il tente toujours à vrai dire à optimiser que se soit minimiser ses dépenses et maximiser ses biens. Le mathématicien vient pour concrétiser le voeux de l’Homme en modélisant les problèmes de la vie sous des fonctions coûts en utilisant les différents types d’optimisation. De nos jours l’optimisation est devenue un domaine indispensable pour résoudre plusieurs problèmes que se soit dans l’industrie ou d’autres secteurs [51]. En effet nous avons assisté ces dernières années à une croissance très rapide des travaux utilisant les méthodes d’optimisation. Cette tendance peut être observée dans tous les domaines de la science.

Problèmes d’optimisation

La formulation des problèmes d’optimisation reste très ambigüe à cause de la diversité des vocabulaires et des confusions éventuelles que cela pourrait engendrer. Nous avons convenu d’adopter le vocabulaire qui suit : Un problème d’optimisation mono-objectif est défini par un ensemble de variables, une fonction objectif et un ensemble de contraintes. Un problème d’optimisation multiobjectif est défini par un ensemble de variables, un ensemble de fonctions objectif et un ensemble de contraintes. L’espace d’état, appelé aussi domaine de recherche, est l’ensemble des domaines de définition des différentes variables du problème. Les variables du problème dite aussi variable de conception ou de décision peuvent être de nature diverse (réelle, entière, booléenne. etc.) et exprimer des données qualitatives ou quantitatives, dans la présente thèse on s’intéresse au cas réel. La fonction objectif ou encore (fonction de coût) définit le but à atteindre, on cherche à minimiser ou à maximiser celle-ci. Une fonction multimodale présente plusieurs minima (locaux et globaux).  Tandis qu’une fonction unimodale n’a qu’un minimum, le minimum global. L’ensemble des contraintes est en général un ensemble d’égalités ou d’inégalités que les variables de l’espace d’état doivent satisfaire. Ces contraintes limitent l’espace de recherche. Les méthodes d’optimisation recherchent un point ou un ensemble de points dans l’espace de recherche qui satisfont l’ensemble des contraintes, et qui maximisent ou minimisent la fonction objectif.

La Programmation Non Linéaire
La fonction objectif et les limitations sont non linéaires. Pratiquement ils recouvrent toutes les catégories, ce qui fait apparaître les autres comme des cas particuliers. Derrière toutes ces catégories, il y a bien entendu des méthodes mathématiques de résolution qui en général portent le même nom. Dans ce qui suit, nous nous limiterons aux méthodes de programmation non linéaire qui sont directement en relation avec l’optimisation des structures. Optimum global, optimum local .

Optimisation continue sans contraintes

Les méthodes d’optimisation locale

la recherche locale est une méthode utilisée pour résoudre des problèmes d’optimisation difficiles. La recherche locale peut être utilisée sur des problèmes de recherche d’une solution maximisant un critère parmi un ensemble de solutions candidates. Les algorithmes de recherche locale passent d’une solution à une autre dans l’espace des solutions candidates (l’espace de recherche) jusqu’à ce qu’une solution considérée comme optimale soit trouvée ou que le temps imparti soit dépassé. En revanche optimiser localement, c’est chercher une solution à un problème qui soit proche d’une solution de départ (optimisation locale), mais qui soit meilleure en terme de coût (fonction objectif). Pour cela, nous recherchons une meilleure solution par itérations successives, cette classe de méthodes peut être déterministe ou non-déterministe.

Optimisation déterministe 

Lorsque l’évolution de la méthode de résolution est prévisible et ne laisse aucune place au hasard, celle-ci est qualifiée de déterministe. Bien que l’optimisation locale ne soit pas le thème essentiel de notre travail. Nous en présentons les grandes lignes. En effet, comme nous le verrons plus loin beaucoup d’algorithmes d’optimisation globale utilisent des codes d’optimisation locale comme sous-programmes. Donc l’efficacité de ces derniers affecte celle des premiers.

La condition (i) a donné naissance à deux familles de méthodes dites d’interpolation et de recherche directe : Les méthodes d’interpolation : elles sont utiles lorsque la fonction objectif est non définie en certains points de l’espace. Cette famille est composée de méthodes tentant de construire un modèle de la fonction à optimiser. Ce modèle est souvent un polynôme interpolant f, construit à partir d’un échantillonnage de points où f a déjà été évaluée. Le modèle est ensuite lui même optimisé. Les méthodes sans dérivées, ou sampling methods, elles sont décrites dans [[53],[54],[179],[180]]. Dans cette famille. Il existe des méthodes qui tentent d’approcher les gradients de f, et d’utiliser cette information afin de déterminer quels sont les points prometteurs où f est évaluée[57].

Les méthodes de recherche directe (direct search) : Le terme de recherche directe est utilisé pour décrire une méthode de recherche utilisant différents essais de solution possible en comparant chaque essai au meilleur résultat obtenu jusqu’à présent, combiné à une stratégie permettant de déterminer quelle est la prochaine solution à tester.

Cette famille de méthodes ne tente pas d’approcher le gradients ni de construire un modèle de f, des approximations de gradients sont utilisées pour ordonner les directions de recherche, elle se base principalement sur le calcul de la fonction objectif. Parmi ces méthodes se trouvent la méthode simplexe proposée par[60]. Des extensios de cet algorithme ont été proposées par Nelder et Mead[172], plusieurs variantes existent [[179],[180],[184],[183]] en ajoutant d’autres mouvements : en plus de la réflexion, ils proposent la contraction, la réduction et l’étirement. Ily a aussi l’algorithme de Hooke et Jeeves , l’algorithme DIRECT la recherche par coordonnées[64], GPS [[15], [31], [228]], [16],etc.

Table des matières

Introduction Générale
1 L’Optimisation :Etat de l’art
1.1 Introduction
1.2 Problèmes d’optimisation
1.3 Optimisation continue sans contraintes
1.3.1 Les méthodes d’optimisation locale
1.3.2 Les méthodes d’optimisation globale
1.3.3 Les méthodes d’optimisation hybride
1.3.4 Choix d’une méthode d’optimisation
1.3.5 Exploration et exploitation des algorithmes d’optimisation
1.4 Optimisation continue avec contraintes
1.4.1 Méthodes d’optimisation par transformation
1.4.2 Optimisation séquentielle des contraintes
1.5 Optimisation multiobjectif
1.5.1 Formulation d’un problème multiobjectif
1.5.2 Classification des méthodes d’optimisation multiobjectif
1.6 Conclusion
2 Les Métaheuristiques
2.1 Introduction
2.2 Les métaheuristiques les plus utilisées
2.2.1 Méthode de colonies de fourmis
2.2.2 Méthode de recuit simulé
2.2.3 Recherche Tabou
2.3 Algorithmes génétiques
2.3.1 Principes : Définition et vocabulaire
2.3.2 Codage et population initiale
2.3.3 Evaluation de la population
2.3.4 Opérateur de sélection
2.3.5 Opérateur de croisement
2.3.6 Opérateur de mutation
2.4 L’évolution différentielle
2.5 Optimisation par essaim particulaire
2.6 Conclusion
3 Hybridation et Méthodes proposées
3.1 Introduction
3.2 Hybridation métaheuristiques/métaheuristiques
3.2.1 Classification hiérarchique des métaheuristiques
3.2.2 L’hybridation relais de bas niveau
3.2.3 L’hybridation co-évolutionnaire de bas niveau
3.2.4 L’hybridation relais de haut niveau
3.2.5 Classification à plat des métaheuristiques
3.3 Hybridation métaheuristiques/méthodes exactes
3.4 Méthodes proposées
3.4.1 Hybridation de GA _ PSO
3.4.2 Hybridation de DE _ PSO
3.4.3 Hybridation de GA _ PSO_NBI
3.4.4 Hybridation de DE _ PSO_NNCM
3.5 Conclusion
4 Applications en optimisation mono-objectif
4.1 Introduction
4.2 Optimisation des cartes électroniques
4.2.1 Optimisation de la position de la vis d’une carte électronique
4.2.2 Optimisation du joint de brasure
5 Applications en optimisation multiobjectif
5.1 Introduction
5.2 Optimisation méchano-électronique
5.3 Conclusion
5.4 Optimisation mécanique
5.4.1 Pendule double
5.4.2 Pendule triple
5.5 Conclusion
Conclusion générale

Lire le rapport complet