| Titre : | Contribution au développement de concepts et outils d’aide à la décision pour l’optimisation via le plongement dans un réseau d’interconnexion parallèle |
| Auteurs : | Aymen Takie Eddine Selmi, Auteur ; Mohamed Faouzi Zerarka, Directeur de thèse |
| Type de document : | Thése doctorat |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2024 |
| Format : | 1 vol. (156 p.) / ill., couv. ill. en coul / 30 cm |
| Langues: | Français |
| Mots-clés: | Problèmes complexes, modélisation, plongement, réseau d’interconnexion parallèle, systèmes d’évènements discrets, clustering, optimisation |
| Résumé : |
Dans un monde caractérisé par des défis complexes et interconnectés, la prise de décision efficace est primordiale pour aborder des problèmes touchant à la durabilité environnementale, à l'amélioration des infrastructures de transport et à l'innovation médicale. Cependant, la complexité croissante de ces problèmes dépasse souvent les capacités de raisonnement traditionnelles. Les systèmes d'aide à la décision, exploitant les techniques d'intelligence artificielle, offrent des perspectives prometteuses pour naviguer dans ces défis. Cette thèse se concentre sur l'adresse d'un tel problème complexe, le Problème du Voyageur de Commerce (TSP), qui trouve des applications dans la logistique, la planification de réseau et la bio-informatique. Malgré les avancées dans les méthodes de résolution du TSP, la scalabilité et l'adaptabilité aux scénarios dynamiques demeurent des défis persistants. Cette recherche propose une simulation parallèle via un outil d'optimisation basé sur une topologie de réseau d'interconnexion intégrant des techniques avancées d'intelligence artificielle pour aborder ces problèmes. La méthodologie inclut des représentations de regroupement hiérarchique, des plongements de graphes et des stratégies hybrides de résolution parallèle. Les contributions clés comprennent de nouveaux algorithmes de regroupement adaptés à l'optimisation du TSP, une intégration avec les architectures informatiques parallèles et une validation expérimentale démontrant des performances supérieures par rapport aux méthodes traditionnelles. La thèse décrit les fondements théoriques, explore les architectures informatiques parallèles et les techniques de plongement de graphes de la meilleure qualité, et présente une évaluation complète de la méthodologie proposée. Les résultats contribuent à améliorer les processus de prise de décision et offrent un cadre robuste pour aborder les défis d'optimisation complexes dans des environnements réels dynamiques. . |
| Sommaire : |
Contents Contents . . . . . . . . . . . i List of Figures . . . . . . . . . . . . . . . . . . . . . . vi List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii 1 General Introduction 1 1.1 Context and Motivation . . . . . . . . . . . . . . . . .. . 1 1.2 Objectives . . . . . . . . . . . . . . . . . . . 2 1.3 Thesis Contributions . . . . . . . . . . . . . . 2 1.4 Thesis Outline . . . .. . . . 3 2 General concepts 5 2.1 Introduction . . . . . . . . . . . . . . . . . .. . . . . 5 2.2 Complex System . . . . . . . . . 5 2.2.1 Characteristics of complex syst 2.2.2 Specification [8] . . . . . . . . . . . . . . . . . . . . 6 2.2.3 Modeling [21] . . . . . . . . . . . . . . . . . . . . 6 2.2.4 Simulation [21] . . . . . . . . . . . . . .. 7 2.3 Discrete event system . . . . . . . . . . . . . . . . . . . . . . 8 2.3.1 Petri nets approach . . . . . . . . . . . . . . . . . 8 2.3.2 State-space models . . . . . . . . . . . . . . . 8 2.3.3 Agent-based modeling . . . . . . . . . . . . . .. 8 2.3.4 Discrete Event System Specification (DEVS) . . . . . . 8 2.4 The problem concept . . . . . . . . . . . . . . . . 10 2.5 Classification of problems . . . . . . . . . . . . . 10 2.5.1 Discrete problems . . . . . . . . . . . . . . . . . . 11 2.6 The optimization concept . . . . . . . . . . . .. . 12 2.7 Combinatorial optimization [119, 124] . . . . . . . . . . . 12 2.7.1 Graph theory notations . . . . . . . . . . . . . . . . . 13 2.7.2 Landscape definition . . . . . . . . . . . . . . 14 2.7.3 Search space . . . . . . . . . . . . . . . . . . . . . . 14 2.7.4 Neighborhood relation . . . . . . . . 15 2.7.5 Objective space . . . . . . . . . . . . . . . . . . 15 2.7.6 Landscape analysis . . . . . . . . . . . . 16 2.8 Classification of combinatorial optimization methods . . . .. . 16 iii CONTENTS 2.9 Metha-heuristic for combinatorial optimization [153] . . . 17 2.9.1 Solution Representation . . . . . . . . . . . . 17 2.9.2 S-solution methods . . . . . . . . . . . . . . . . . . . 18 Simulated annealing (SA) . . . . . . .18 2.9.3 Population solution methods . . . 19 2.10 Choice of Metha-heuristic . . . . . . . . . . . .. . . . 20 2.11 Parallel Metha-heuristic [4] . . . . . . . . .. . . . . . 22 2.11.1 Decomposition for Parallel Metha-heuristic . . . . . . . 23 2.11.2 Decomposition methods . . . . . . 23 K-means [67] . . . . . . . . . . . . . . . . . . . . . 24 Affinity Propagation [52] . . . . . . . . . . . . . . 24 Density peaks clustering [125] . . . . . . . . . . . . . 25 2.11.3 Evaluating decomposition methods . . . . . . .. . 25 2.11.4 Index measures . . . . . . . . . . . . . . . . . . 26 2.12 Hybrid Methaheuristic [4] . . . . . . . . . . . . .. . . . 27 2.12.1 Reasons for Hybridization . . . . . . . . . . . . 27 2.12.2 Relation between Parallel models and Hybrid Metha-heuristic . . . . 27 2.12.3 Integration of machine learning techniques with Metha-heuristic . . . 28 2.13 Modeling, Simulation, and Optimisation . . . . . 29 2.14 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 30 3 Parallel architecture and embedding 31 3.1 Introduction . . . . . . . . . . . . . . . . .. . 31 3.2 Flynn classification . . . . . . . . . . . . . . . . . . . 31 3.3 Topological classification . . . . . . . . . 32 3.3.1 Simple connection networks . . . . . . . 32 Vector architecture . . . . . . . . . . 33 Mesh (Vector Composition) . . . . . .. . . . 33 Trees . . . . . . . . . . . . . . . . . . . . .. . . 36 3.3.2 Hybrid connection networks . . . . . . . . . . . . . . 38 3.3.3 Hypercube connection networks . . . . . . . . 38 Properties of the Hypercube . . . . . . . . . . 40 The Networks Within a Hypercube . . . . . . . . . . 41 Advantages and disadvantages . . . . . . . . . . . 41 Importance of the hypercube . . . . Variations of the hypercube . . . . 42 3.4 Crossed Cubes . . . . . . . . . . . . . . .. . . . . . 43 3.5 Embedding . . . . . . . . . . . . . . . .. . . . 46 3.5.1 Embedding problems . . . . . . . . . . . . . . . . . 46 3.5.2 Definitions . . . . . . . . . . . . . . . . .. . . . 47 3.5.3 Embedding types . . . . . . . . . . . . . . . . . .. . 47 3.5.4 Quality of graph embedding . . . . . . . . . . . . . 47 3.5.5 Process of embedding . . . . . . . . . . .. . . 49 3.5.6 The need for embedding . . . . . . . . . . .. . 51 3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 51 4 Case of study: The Traveling Salesman Problem (TSP) 52 4.1 Introduction . . . . . . . . . . . . 52 4.2 The problem . . . . . . . . . . . . . . . . . . 53 4.2.1 Introduction . . . . . . . . . . . . . . . . . . . . 53 4.2.2 Definition . . . . . . . . . . . . . .. . . . 53 4.2.3 Formal Model . . . . . . . . . . . . . . . . . . . . . 53 4.2.4 The euclidean TSP . . . . . . . . . 54 4.2.5 Datasets . . . . . . . . . . . . . . . . . . . . .. . . . 54 4.2.6 The Classic Modeling of the problem . . . . . . . . . . . . 54 Representation . . . . . . . . .. 54 Evaluation . . . . . . . . . . . . . . . . . . . . . Neighborhood . . . . . . . . . . . . . . . . . 54 Initialization . . . . . . . . . . . . . . . . . . . . 54 4.3 The Classic TSP solving methods . . . . . . . . . . . . 55 4.3.1 Exact solving . . . . . . . . . . . . .. . 55 4.3.2 Heuristic solving . . . . . . . 55 Tour Construction Algorithms . . . . . . . . . . .. 56 Tour improvement algorithms . . . . . . . . . . . . 56 Lin-Kernighan . . . . . . . . . . . . . . . . . . . . 58 4.3.3 Metha-heuristic solving . . . . . . . . . . . . 58 4.4 Hybrid TSP solving methods . . . . . . . . . . . . 59 4.4.1 Hybridization between Optimization methods . . . . .. 60 Combining Metaheuristics . . . . . . . . . . . . . . 60 Integrating exact methods with heuristics . . . . . . . .. 60 4.4.2 Machine learning methods with Meta-heuristics for solving TSP . . . 61 4.5 Parallel TSP solving . . . . . .. . . . 61 4.5.1 Formalization of TSP for Parallelization . . . . . . 62 4.5.2 TSP problem decomposition . . . . . . . . . . . . . . . . . . 63 4.5.3 The need for alternative problem representations . . . . . . . 64 4.6 Proposed model methodology . . . . . . . . . . . . . 66 4.6.1 Feature selection module . . . . . . . . . 68 Transformation of Euclidean TSP to a Hierarchical Representation . 68 Embedding the Hierarchical Representation into Crossed cubes interconnection network . . . 68 4.6.2 Processing module . . . .. . 69 Initial solutions construction . . .. . . 69 Optimization . . . . .. . 69 4.6.3 Visualisation and interpretation module . . . 70 4.7 Conclusion . . . . 70 5 Proposed Modeling Paradigm for Solving TSP 71 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.2 Feature Selection: TSP-Compressed Quadtree/Octree-based recursive hybrid clustering representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.2.1 Enhancing k-means with post-redistribution [129] . . . . . . . . . . . 72iv CONTENTS Rationale for SSE and diameter criteria in redistribution . . . . . . . 73 The complexity of enhanced K-means algorithm . . . . . . . . . . . . 73 5.2.2 K-Affinity Propagation and K-Density Peaks Clustering . . . . . . . . 74 K-Affinity Propagation (AP) . . . . . . . . . . . . . . . . . . . . . . . 75 K-Density Peaks Clustering (K-DPC) . . . . . . . . . . . . . . . . . . 75 5.2.3 Evaluation clustering methods . . . . . . . . . . . . . . . . . . . . . . 75 5.2.4 TSP-Compressed Quadtree/Octree-based recursive hybrid clustering representation process . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.3 Feature Selection: Enhancing optimization via the embedding TSP-Compressed Quadtree/Octree into Crossed Cubes Interconnection Network . . . . . . . . 77 5.3.1 Definition . . . . . . . . . . 78 5.3.2 Notations . . . . . . . . . . . . . . . . . . . 78 5.3.3 Dimension of CQm . . . . . . . . . . . . . . 80 5.3.4 One-by-one vertex embedding [130, 128] . . . . . . . . 80 One-by-one vertex embedding of TSP-CQTn . . . .. 80 One-by-one vertex embedding of TSP-COTn . . . . . . . . . . . . 83 5.3.5 Dilation two one-by-one edges embedding [130, 128] . .. . . . . 85 Dilation two one-by-one edges embedding of TSP-CQTn . . . .. 85 Dilation two one-by-one edges embedding of TSP-COTn . . . . 88 5.3.6 Theoretical Validation of Embeddings [131] . . . . . . . . 93 5.4 Processing: Hybrid Parallel solving [133] . . . . . . . .. . . 101 5.5 Processing: Optimization for refinement initial solutions [133] . . . . . . . . 104 5.6 Visualisation and Interpritation . . . . . . . . .. . . . 104 5.6.1 Illustrating the structures of clusters through visualization . . .. 104 5.6.2 Illustrating the graph embedding . . . . . . . . 105 5.6.3 Illustrating the solution paths . . . . . . . . .. . . 105 5.6.4 Interpreting the boundary interactions . . . . . . . . 105 5.6.5 Evaluating of solutions, and runtime: Statistical examination . . . . . 105 5.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 6 Experimental Results of Implementation of Proposed Paradigm and Evaluation 107 6.1 Introduction . . . . . . . . . . . . . . . 107 6.2 Environment . . . . . . . . . . . . . . . . 107 6.3 Datasets . . . . . . . . . . . . . . . . .. . 108 6.4 Analyzing the performance of enhanced K-means . . . . .. 108 6.4.1 Comparative performance analysis (standard K-means Vs Enhancedvariants) . . . . . . 108 6.4.2 Influence of Parameter r to enhanced K-means . . . .. 109 6.5 Constructing the Compressed Quadtree/Octree . . . . . . . . . . . . . 112 6.6 Construct the graph one-by-one embedding of TSP-Compressed Quadtree/Octree representations into Crossed Cubes interconnection network . . . . . . . . . 116 6.6.1 Simulation rules of embedding 2D/3D representation into Crossed Cubes116 Embedding 2D representations into Crossed Cubes: Simulation rules 116 Embedding 3D representations into Crossed Cubes: Simulation rules 120CONTENTS v 6.6.2 Graph embedding of 2D Euclidean TSP(instance)-CQTn into CQm . 123 6.7 Processing: Construct intra-cluster solutions and inter-connection between clusters 126 6.7.1 Scale of each cluster and the selection of methods for local optimization 126 6.7.2 Determining the boundaries’ citie. 127 6.7.3 Parameters settings . . . . . . . . . . . . . . . . . 129 6.8 Initial solutions refinement . . . . . . . . . . . 129 6.9 Results and Discussion . . . . . . . . . . . . . . . . .. . . . 130 6.9.1 Effectiveness of clustering methods for hierarchical TSP representation 130 6.9.2 Evaluation performance of processing algorithm . . . 133 6.9.3 Runtime Evaluation [134] . . . . . . . . . . . . . . 138 6.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . .139 7 General Conclusion and Perspectives 141 7.1 Perspectives . . . . . . . . . . . . . . . . . . 143 Bibliography 145 |
| En ligne : | http://thesis.univ-biskra.dz/id/eprint/6569 |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| TINF/196 | Théses de doctorat | bibliothèque sciences exactes | Consultable |
