Approches d’optimisation pour le partitionnement de graphe de conductance minimale
| Autor: | Zhi Lu |
|---|---|
| Přispěvatelé: | Laboratoire d'Etudes et de Recherche en Informatique d'Angers (LERIA), Université d'Angers (UA), Université d'Angers, Jin-Kao Hao, STAR, ABES |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Combinatorial optimization
Multiniveaux Graph partitioning [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC] Metaheuristics Multilevel Recherche de voisinage Minimisation de la conductance Hybrid algorithm Optimisation de grands graphes Algorithme hybride [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC] Large graph optimization Conductance minimization Neighborhood search |
| Zdroj: | Optimization and Control [math.OC]. Université d'Angers, 2020. English. ⟨NNT : 2020ANGE0013⟩ Zhi Lu |
| Popis: | The minimum conductance graph partitioning problem (MC-GPP) is an important NP-hard combinatorial optimization problem with numerous practical applications in various areas such as community detection, bioinformatics, and computer vision. Due to its high computational complexity, heuristic and metaheuristic approaches constitute a highly useful tool for approximating this challenging problem. This thesis is devoted to developing effective metaheuristic algorithms for the MC-GPP. Specifically, we propose a stagnation-aware breakout tabu search algorithm (SaBTS), a hybrid evolutionary algorithm (MAMC), and an iterated multilevel simulated annealing algorithm (IMSA). Extensive computational experiments and comparisons on large and massive benchmark instances (with more than 23 million vertices) demonstrate that the proposed algorithms compete very favorably with stateof- the-art algorithms in the literature. Furthermore, the key issues of these algorithms are analyzed to shed light on their influences over the performance of the proposed algorithms. Le problème de partitionnement de graphe de conductance minimale (MCGPP) est un problème d’optimisation combinatoire NP-difficile avec de nombreuses applications pratiques dans divers domaines tels que la détection communautaire, la bioinformatique et la vision par ordinateur. Etant donnée sa complexité intrinsèque, des approches heuristiques et métaheuristiques constituent un moyen convenable pour résoudre des instances de grande taille. Cette thèse est consacrée au développement d’algorithmes métaheuristiques performants pour le MC-GPP. Plus précisément, nous proposons un algorithme «Stagnation aware Breakout Tabu Search», un algorithme évolutif hybride (MAMC) et un algorithme multiniveaubasé sur le recuit simulé (IMSA). Nous présentons des résultats expérimentaux sur de nombreux graphes de grande dimension de la littérature ayant jusqu’à 23 millions de sommets. Nous montrons la haute performance de nos algorithmes par rapport à l’état de l’art. Nous analysons les éléments algorithmiques et stratégies de recherche pour mettre en lumière leur influence sur la performance des algorithmes proposés. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|