Soutenance mémoire
Cette thèse en cotutelle s’inscrit dans le cadre de la collaboration entre le Laboratoire des Génies et Systèmes (LGS, École Nationale des Sciences Appliquées, Université Ibn Tofail, à Kenitra au Maroc) et le Laboratoire d’Informatique et Traitement de l’Information et des Systèmes (LITIS, Institut National des Sciences Appliquées, Université de Normandie à Rouen en France).
Les problèmes d’optimisation dans le monde réel sont généralement complexes. Ils contiennent non seulement les termes de contraintes, d’objectifs simples / multiples, mais leur modélisation évolue constamment. Leur résolution et l’évaluation itérative des fonctions objectives requièrent un temps CPU long. Le coût de calcul élevé pour la résolution de ces problèmes a poussé au développement d’algorithmes d’optimisation avec la parallélisation.
L’algorithme d’optimisation par essaims de particules (PSO) est l’un des algorithmes les plus populaires basés sur l’intelligence des essaims, qui s’enrichit de robustesse, de simplicité et de capacités de recherche globale. Cependant, l’un des principaux obstacles de la méthode PSO est sa susceptibilité à rester piégé dans les optima locaux et; à l’instar d’autres algorithmes évolutifs, les performances de PSO se détériorent dès que la dimension du problème augmente. Par conséquent, plusieurs efforts sont déployés pour améliorer ses performances. Différents scénarios sont développés, soit en ajoutant de nouveaux paramètres à l’algorithme de base [1], en l’hybridant avec d’autres méta-heuristiques [2], ou en proposant des scénarios de parallélisation .
Principes du parallélisme et méthodes métaheuristiques
La plupart des problèmes de recherche complexes peuvent être formulés comme des problèmes d’optimisation. L’émergence des grandes technologies de données a également commencé la génération de problèmes d’optimisation complexes de grande taille. Le coût de calcul élevé de ces problèmes a rendu nécessaire le développement d’algorithmes d’optimisation avec parallélisation.
Problème du parallélisme en informatique
En programmation, le parallélisme est l’exécution simultanée de calculs (éventuellement liés) dans le but d’accélerer le traitement des problèmes de calculs intensifs et d’effectuer un grand nombre d’opérations en un temps restreint. Il englobe tous les concepts liés aux systèmes multi-processeurs / multi-coeurs, le distribué à savoir les multi-ordinateurs (qui représentent des machines composées d’un ensemble de processeurs avec mémoire distribuée interconnectés par un réseau); et aux applications associées, en passant par la conception, la modélisation, la mise en œuvre et l’utilisation des systèmes et des applications.
Types du parallélisme
Il existe plusieurs classifications des différents types du parallélisme. Dans ce manuscrit nous allons présenter deux types de classifications : le classement de Mickeal J.Flynn nommé « la Taxonomie de Flynn » [7] et la classification par mémoire .
Taxonomie de Flynn
Elle représente le classement des machines selon deux dimensions indépendantes : le flux de données et le flux d’instructions. Un seul état (unique ou multiple) est attribué à chaque dimension .
1) Architecture SISD (Single Instruction Single Data): il s’agit des systèmes séquentiels qui font le traitement d’une donnée à la fois.
2) Architecture SIMD (Single Instruction Multiple Data): représente des systèmes parallèles qui traitent de grandes quantités de données d’une manière uniforme.
3) Architecture MIMD (Multiple Instruction Multiple Data): ce sont des systèmes parallèles, comme les SIMD traitant de grandes quantités de données mais d’une manière hétérogène.
4) Architecture MISD (Multiple Instruction Single Data): ce sont des systèmes parallèles qui traitent une seule donnée de manière hétérogène.
Classification par mémoire
Dans le parallélisme, nous distinguons généralement trois types de systèmes basés mémoire [8]: Les systèmes à mémoire distribuée, les systèmes à mémoire partagée et les systèmes à mémoire hybride partagée distribuée :
1. Concernant les systèmes à mémoire distribuée : Chaque processeur a sa propre portion de mémoire et ses propres données, l’espace mémoire est fragmenté. L’accès à la mémoire d’un autre processeur (dit voisin) s’effectue à travers un échange de messages sur le réseau entre les deux processeurs. Les algorithmes utilisés dans ce cas doivent minimiser ces communications en évitant les échanges inutiles afin d’optimiser le temps de traitement. Ce type de systèmes présente un ensemble d’avantages, notamment :
• Chaque processeur est indépendant et a un accès rapide à son espace mémoire.
• La mémoire est évolutive en fonction du nombre de processeurs.
• Son coût est réduit et facile à construire.
Ses inconvénients sont moins nombreux :
• La gestion des communications doit être effectuée par le programmeur, ce qui génère une complexité des algorithmes, un risque d’erreurs et une source de perte de performances.
• Puisque les communications passent via le réseau, les performances seront parfois au prix d’un réseau d’interconnexion coûteux.
2. Pour les systèmes à mémoire partagée : Chaque processeur a sa propre mémoire locale dans laquelle une partie de la mémoire globale sera copiée. Cette dernière est uniforme et visible par tous les processeurs. La gestion de l’ensemble de ces mémoires locales est effectuée soit par le matériel, le logiciel ou manuellement par l’utilisateur.
Ce système présente deux grands avantages : la simplicité de sa programmation et la rapidité du partage des données entre les tâches. Par contre c’est le programmeur qui est responsable de la validité des synchronisations puisque le dit système n’est pas évolutif et donc ne favorise pas le passage à l’échelle des accès en mémoire (tous les processeurs ne peuvent pas accéder à la mémoire globale en même temps).
3. Quant aux systèmes à mémoire hybride partagée distribuée : Ce sont des systèmes conçus pour bénéficier des avantages des deux précédents systèmes : la simplicité des architectures partagées et le coût réduit des architectures distribuées. Ceci peut être effectué par exemple en utilisant des systèmes à mémoire virtuellement partagée ou des langages à espace global adressable.
Efficacité du parallélisme
La principale raison pour laquelle nous utilisons le parallélisme est d’accélérer les calculs et de gagner du temps i.e. le temps mis pour effectuer un calcul. Souvent en informatique, pour un problème donné, il n’existe pas une seule solution, mais une multitude de façons pour implémenter la solution. Pour évaluer le gain lié à la parallélisation d’un programme, on utilise le facteur d’accélération (speedup) et l’efficacité.
|
Table des matières
INTRODUCTION GENERALE
CHAPITRE 1 PRINCIPES DU PARALLÉLISME ET MÉTHODES MÉTAHEURISTIQUES
1.1 INTRODUCTION
1.2 PROBLEME DU PARALLELISME EN INFORMATIQUE
1.2.1 Types du parallélisme
1.2.2 Efficacité du parallélisme
1.2.3 Lois du parallélisme
1.2.4 Niveaux du parallélisme
1.2.5 Stratégies du parallélisme
1.2.6 Modèles du parallélisme
1.2.7 Programmation concurrente et synchronisation
1.3 OPTIMISATION MATHEMATIQUE
1.3.1 Étapes du processus de l’optimisation
1.3.2 Classification des types d’optimisation
1.3.3 Méthodes méta-heuristiques
1.4 CONCLUSION
CHAPITRE 2 PROPOSITION DE DEUX MODÈLES PARALLÈLES BASÉS SUR LA MÉTHODE PSO
2.1 INTRODUCTION
2.2 MODELES PARALLELES BASES SUR LA METHODE PSO
2.3 APPROCHES PROPOSEES : DEUX PARALLELISATIONS BASEES SUR LA METHODE PSO
2.3.1 Proposition du premier modèle parallèle (PPSO1)
2.3.2 Proposition du deuxième modèle parallèle (PPSO2)
2.4 DESCRIPTION DES EXPERIMENTATIONS ET RESULTATS
2.4.1 Fonctions tests
2.4.2 Paramètres expérimentaux
2.4.3 Résultats
2.4.4 Analyse des résultats
2.5 CONCLUSION
CHAPITRE 3 APPLICATION D’UN MODÈLE PARALLÈLE AU PROBLÈME DE TRANSPORT D’ÉLECTRICITÉ
3.1 INTRODUCTION
3.2 DESCRIPTION DE LA PROBLEMATIQUE
3.3 DESCRIPTION DE L’ALGORITHME MPSO PROPOSE
3.3.1 Création des voisinages
3.3.2 Calcul parallèle
3.3.3 Étapes de l’algorithme
3.3.4 Critère d’arrêt 92
3.4 APPLICATION DE L’ALGORITHME MPSO AU PROBLEME DE TRANSPORT D’ELECTRICITE
3.4.1 Modélisation du problème
3.4.2 Formulation mathématique du problème
3.5 RESULTATS ET DISCUSSION
3.5.1 Étapes de l’application de MPSO du transport d’électricité 97
3.5.2 Résultats numériques
3.6 CONCLUSION
CHAPITRE 4 ÉLABORATION D’UN MODÈLE D’OPTIMISATION HYBRIDE APPLIQUÉ AU PROBLÈME DES RÉSEAUX DE COLLABORATION
4.1 INTRODUCTION
4.2 CONTEXTE GÉNÉRAL DES RÉSEAUX DE COLLABORATION DES SI
4.2.1 Concept de l’interopérabilité
4.2.2 Classification de l’interopérabilité
4.2.3 Métrique de l’interopérabilité
4.2.4 Ratio global de l’interopérabilité
4.2.5 Description de la problématique
4.3 ALGORITHME HYBRIDE PROPOSE
4.3.1 Description de l’algorithme H-MPSO-SA
4.3.2 Expérimentations et résultats de H-MPSO-SA sur les fonctions tests
4.4 PROPOSITION D’UN MODELE D’OPTIMISATION DANS LES RESEAUX DE COLLABORATION
4.4.1 Modélisation dans les réseaux de collaboration
4.4.2 Application de H-MPSO-SA au problème des réseaux de collaboration
4.5 CONCLUSION
CONCLUSION
