| Titre : | Contributions à la résolution de problèmes d’optimisation combinatoires NP-difficiles |
| Auteurs : | Abdelkamel Benali, Auteur ; kamal Eddine Melkemi, 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, 2018 |
| Format : | 1 vol. (216 p.) / 30 cm |
| Langues: | Français |
| Mots-clés: | Algorithmes génétiques multi-objectifs Pareto,Optimisation par essaims de particules,Hybridation,Problème du sac à dos multi-objectif,As-semblage de fragments d’ADN,Recherche locale spécifique. |
| Résumé : |
Cette thèse porte sur des algorithmes efficaces pour la résolution de problèmes d’optimisation combinatoires NP-difficiles, avec deux contributions. La première contribution consiste en la proposition d’un nouvel algorithme multi-objectif hybride combinant un algorithme génétique avec un opérateur de recherche basé sur l’optimisation par essaims de particules. L’objectif de cette hybridation est de surmonter les situations de convergence lente des algorithmes génétiques multi objectifs lors de la ré- solution de problèmes difficiles à plus de deux objectifs. Dans le schéma hybride proposé, un algorithme génétique multi-objectif Pareto applique périodiquement un algorithme d’optimisation par essaim de particules pour optimiser une fonction d’adaptation scalaire sur une population archive. Deux variantes de cet algorithme hybride sont proposées et adaptées pour la résolution du problème du sac à dos multi-objectif. Les résultats expérimentaux prouvent que les algorithmes hybrides sont plus performants que les algorithmes standards. La seconde contribution concerne l’amélioration d’un algorithme heuristique de recherche locale dit PALS (pour l’anglais Problème Aware Local Search) spécifique au problème d’assemblage de fragments d’ADN, un problème d’optimisation combinatoire NP-difficile enbio-informatique des séquences. Deux modifications à PALS sont proposées. La première modification permet d’éviter les phénomènes de convergence prématurée vers des optima locaux. La seconde modification conduit à une réduction significative des temps de calcul tout en conservant la précision des résultats. Après des expérimentations réalisées sur les jeux de données disponibles dans la littérature, nos nouvelles variantes de PALS se révèlent très compétitives par rapport aux variantes existantes et à d’autres algorithmes d’assemblage |
| Sommaire : |
Introduction générale : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 1 Optimisation combinatoire et algorithmes métaheuristiques : : : 6 1.1 Théorie de la complexité . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.1 Complexité des algorithmes . . . . . . . . . . . . . . . . . . . . 7 1.1.2 Complexité des problèmes . . . . . . . . . . . . . . . . . . . . . 9 1.2 Optimisation combinatoire . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.1 Problème d'optimisation combinatoire . . . . . . . . . . . . . . 11 1.2.2 Résolution des problèmes combinatoires dificiles . . . . . . . . . 15 1.3 Métaheuristiques à la solution unique . . . . . . . . . . . . . . . . . . . . 16 1.3.1 Recuit simulé . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3.2 Recherche locale itérée . . . . . . . . . . . . . . . . . . . . . . . 20 1.3.3 Recherche à voisinage variable . . . . . . . . . . . . . . . . . . . 22 1.3.4 Recherche tabou . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.3.5 Méthode GRASP . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.4 Métaheuristiques à population de solutions . . . . . . . . . . . . . . . . 27 1.4.1 Algorithmes génétiques (GAs) . . . . . . . . . . . . . . . . . . . 29 1.4.2 Optimisation par essaim de particules (PSO) . . . . . . . . . . . 41 1.4.3 Optimisation par colonies de fourmis (ACO) . . . . . . . . . . . 50 1.5 Métaheuristiques hybrides . . . . . . . . . . . . . . . . . . . . . . . . . 53 1.5.1 Hybridation métaheuristiques/(méta)heuristiques . . . . . . . . 54 1.5.2 Hybridation métaheuristiques/méthodes complétes . . . . . . . 59 1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 2 Optimisation multiobjectif par algorithmes génétiques : : : : : : : 67 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 2.2 Concepts de base et definitions . . . . . . . . . . . . . . . . . . . . . . 68 2.3 Approches de résolution . . . . . . . . . . . . . . . . . . . . . . . . . . 72 2.4 Principaux composants de recherche d'un logarithme génétique multiobjectif 2.4.1 Procédures de ranking . . . . . . . . . . . . . . . . . . . . . . . 77 2.4.2 Nichage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 2.4.3 Elitisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 2.4.4 Hybridation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 2.5 Deux algorithmes génétiques multiobjectifs performants . . . . . . . . . 83 2.5.1 Le NSGA-II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 2.5.2 Le SPEA2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 2.6 Evaluation d'un ensemble de solutions . . . . . . . . . . . . . . . . . . 91 2.6.1 Métrique d'hypervolume . . . . . . . . . . . . . . . . . . . . . . 92 2.6.2 Métrique de couverture . . . . . . . . . . . . . . . . . . . . . . . 93 2.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 3 Une métaheuristique hybride pour l'optimisation multiobjectif : 95 3.1 Constat et Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 3.2 MOGA-PSO : un algorithme métaheuristique multiobjectif hybride . . 97 3.3 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . 99 3.3.1 Variantes implémentées . . . . . . . . . . . . . . . . . . . . . . . 101 3.3.2 Problèmes de test . . . . . . . . . . . . . . . . . . . . . . . . . . 101 3.3.3 Paramètres de contr^ole . . . . . . . . . . . . . . . . . . . . . . . 104 3.3.4 Résultats et comparaison de performances . . . . . . . . . . . . 106 3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 4 Problème d'assemblage de fragments d'ADN : état de l'art : : : : 120 4.1 Bio-informatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 4.1.1 Structure de L'ADN . . . . . . . . . . . . . . . . . . . . . . . . 121 4.1.2 Probl?emes combinatoires en bio-informatique des séquences . . . 122 4.2 Assemblage de fragments d'ADN . . . . . . . . . . . . . . . . . . . . . 123 4.2.1 Definitions et notations . . . . . . . . . . . . . . . . . . . . . . . 123 4.2.2 Séquenécage shotgun . . . . . . . . . . . . . . . . . . . . . . . . . 124 4.2.3 L'approche OLC et dificultés d'assemblage . . . . . . . . . . . . 126 4.2.4 Modèles formels existants . . . . . . . . . . . . . . . . . . . . . 130 4.3 Assemblage de génomes . . . . . . . . . . . . . . . . . . . . . . . . . . 131 4.3.1 Graphe de chevauchements . . . . . . . . . . . . . . . . . . . . . 131 4.3.2 Graphe a chaînes . . . . . . . . . . . . . . . . . . . . . . . . . . 133 4.3.3 Graphe de de Bruijn . . . . . . . . . . . . . . . . . . . . . . . . 134 4.4 Etat de l'art en assemblage de fragments d'ADN par (méta)heuristiques 135 4.4.1 Evaluation d'un résultat d'assemblage de fragments d'ADN . . . 136 4.4.2 L'algorithme PALS et ses variantes . . . . . . . . . . . . . . . . 138 4.4.3 Approches basées sur les GAs . . . . . . . . . . . . . . . . . . . 140 4.4.4 Algorithmes basées sur l'intelligence en essaim . . . . . . . . . . 144 4.4.5 Autres techniques . . . . . . . . . . . . . . . . . . . . . . . . . . 149 4.5 Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15viii 5 Algorithmes performants pour l'assemblage de fragments d'ADN 155 5.1 Problèmatique et Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . 156 5.2 Présentation détaillée de l'algorithme PALS . . . . . . . . . . . . . . . 158 5.3 Deux modifications à l'algorithme PALS . . . . . . . . . . . . . . . . . 162 5.3.1 Première modification : PALS2 . . . . . . . . . . . . . . . . . . 162 5.3.2 Seconde modification : PALS2-many . . . . . . . . . . . . . . . 163 5.4 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . 165 5.4.1 Instances de test . . . . . . . . . . . . . . . . . . . . . . . . . . 166 5.4.2 Analyse des résultats expérimentaux . . . . . . . . . . . . . . . 167 5.4.3 Comparaison de PALS2-many avec la littérature . . . . . . . . . 180 5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 Conclusion générale et Perspectives : : : : : : : : : : : : : : : : : : : : : 186 Bibliographie : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 190 |
| En ligne : | http://thesis.univ-biskra.dz/id/eprint/3828 |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| TINF/122 | Théses de doctorat | bibliothèque sciences exactes | Consultable |
