| Titre : | Métatheuristique hybride pour l'optimisation multi-objectif |
| Auteurs : | Abdelhakim Cheriet, Auteur ; Foudil Cherif, 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, 2016 |
| ISBN/ISSN/EAN : | TINF/100 |
| Format : | 1 vol. (156 p.) / ill. / 29 cm |
| Langues: | Français |
| Résumé : |
Dans la plupart des problèmes réels que ce soit technologiques, économiques ou autres, une compétence du point de vue choix de décisions à faire est indispensable.Un décideur doit avoir une très bonne connaissance autour du problème traité pour que les choix puissent être optimaux des points de vue objectifs à atteindre. Néanmoins, les problèmes du monde réel comportent plusieurs objectifs à atteindre, la recherche des solutions qui optimisent les objectifs simultanément rentre dans le domaine d’optimisation multiobjectif. La résolution des problèmes d’optimisation multiobjectif vise à trouver un ensemble de solutions appelé Solution Pareto. Les solutions Pareto sont celles qui ne sont dominées par aucune autre solution. Plusieurs méthodes ont été utilisées pour résoudre ce problème, dont les algorithmes évolutionnaires sont les mieux adaptés. Ceci est du à leurs capacités de trouver les bonnes approximations des solutions Pareto. La plupart des algorithmes évolutionnaires sont classés selon la manière d’intervention du décideur en trois catégories : a priori, a posteriori et interactif. L’algorithme fournit des solutions optimales au décideur qui va choisir celles qu’il le convient. Dans toutes les catégories, si le décideur n’est pas satisfait par les solutions fournies, l’algorithme doit être ré-exécuté, ce qui est vu comme un inconvénient. An de faire face à ce problème,l’algorithme utilisé doit être capable de modéliser les solutions obtenues lors de la phase d’optimisation. Un tel modèle sera exploité dans le cas où de nouvelles solutions sont requises. Pour cela, un algorithme à estimation de distribution est utilisé. Il vise à estimer la distribution de meilleures solutions qui sera utilisée pour générer des nouvelles solutions avec les mêmes caractéristiques d’optimalité. Dans cette thèse, un algorithme,nommé CEDA, utilisant les copules pour modéliser les dépendances entre les variables du problème est proposé. Pour bien exploiter les capacités de cet algorithme, une hybridation avec une méthode d’apprentissage SVM est proposée. L’objectif est de minimiser le temps d’exécution dans la phase de mise à jour des solutions surtout dans les problèmes Many-objective. L’utilisation de CEDA sur plusieurs problèmes benchmarks de la littérature montre que notre proposition donne des meilleures qualités. |
| Sommaire : |
Introduction 1 1 Optimisation Multiobjectif 6 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1 Dénitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.1 Problème d’optimisation multiobjectif . . . . . . . . . . . . . . . 7 1.1.2 Relation de dominance de Pareto et optimalité . . . . . . . . . . . 8 1.2 Une vue de méthodes de résolutions . . . . . . . . . . . . . . . . . . . . . 9 1.3 Programmation mathématique . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3.1 Méthodes a priori . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.2 Méthodes a posteriori . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.3 Méthodes interactives . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Algorithmes évolutionnaires multiobjectifs . . . . . . . . . . . . . . . . . 14 1.4.1 Les éléments clés d’un MOEA . . . . . . . . . . . . . . . . . . . . 17 1.4.2 MOEAs basés sur l’optimalité de Pareto . . . . . . . . . . . . . . 20 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2 Algorithmes évolutionnaires pour l’optimisation multiobjectif 22 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.1 Algorithmes évolutionnaires multiobjectif . . . . . . . . . . . . . . . . . 23 2.1.1 Framework basé préférence . . . . . . . . . . . . . . . . . . . . . 23 2.1.2 Framework basé dominance . . . . . . . . . . . . . . . . . . . . . 24 2.1.3 Framework basé sur la décomposition . . . . . . . . . . . . . . . 27 2.2 Algorithme à estimation de distribution multiobjectif (MOEDA) . . . . . 29 2.3 Algorithmes associés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.3.1 Algorithme génétique de tri par non-dominance II . . . . . . . . 30 2.3.2 Algorithme évolutionnaire de force Pareto SPEA2 . . . . . . . . . 32 2.3.3 Algorithme évolutionnaire multobjectif basé sur la décomposition MOEA/D . . . . . . . 36 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3 Algorithmes à Estimation de Distribution 41 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.1 Procédure principale d’un EDA . . . . . . . . . . . . . . . . . . . . . . . . 42 3.1.1 Dénition de problème . . . . . . . . . . . . . . . . . . . . . . . . 42 3.1.2 Procédure EDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.1.3 Simulation d’un exemple de EDA . . . . . . . . . . . . . . . . . . 46 3.2 Classication des modèles EDA . . . . . . . . . . . . . . . . . . . . . . . 48 3.2.1 Classication basée sur la décomposition du problème . . . . . . 49 3.2.2 Classication basée sur les distributions locales dans les modèles graphiques . . . 52 3.3 Aperçu sur les EDAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.3.1 EDAs pour des chaines de taille xe sur alphabets nis . . . . . . 54 3.3.2 EDAs avec vecteurs de valeur réelle . . . . . . . . . . . . . . . . . 59 3.3.3 EDAs pour les problèmes de permutation . . . . . . . . . . . . . 61 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4 Algorithme à estimation de distribution basé Copule (CEDA) 64 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.1 Les Mesures de dépendances . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.1.1 Les propriétés souhaitables des mesures de dépendance . . . . . 66 4.1.2 Corrélation linéaire de Pearson . . . . . . . . . . . . . . . . . . . 66 4.1.3 Corrélation des rangs . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.2 Fonctions de distributions et variables aléatoires . . . . . . . . . . . . . . 68 4.2.1 Densité de probabilité PDF . . . . . . . . . . . . . . . . . . . . . . 68 4.2.2 Fonction de répartition CDF . . . . . . . . . . . . . . . . . . . . . 69 4.2.3 Loi de probabilité marginale . . . . . . . . . . . . . . . . . . . . . 69 4.3 Théorie de Copule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.3.1 Le théorème de Sklar . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.3.2 Caractéristique de Copules . . . . . . . . . . . . . . . . . . . . . . 70 4.3.3 Copule Archimedean . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.3.4 Simulation de Copules . . . . . . . . . . . . . . . . . . . . . . . . 73 4.4 Algorithme à estimation de distribution basé copule . . . . . . . . . . . . 74 4.4.1 Idée de la proposition . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.4.2 Framework général . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.4.3 Initialisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.4.4 Sélection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.4.5 Reproduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.5 Diversication a posteriori des Solutions . . . . . . . . . . . . . . . . . . 79 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5 Algorithme Hybride pour la résolution des problèmes many-objectives 81 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.1 Problème Many-objective . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 5.1.1 Dénition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 5.1.2 Les enjeux d’un problème Many-objective . . . . . . . . . . . . . 82 5.1.3 Méthodes d’optimisation Many-objective . . . . . . . . . . . . . 84 5.2 Machine à vecteur de support (SVM) . . . . . . . . . . . . . . . . . . . . 85 5.2.1 Le SVM Binaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.2.2 Le SVM multi-classes . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.2.3 Le SVM mono-classe . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.3 Algorithme hybrides CEDA-SVM . . . . . . . . . . . . . . . . . . . . . . 88 5.3.1 Phase d’Optimisation . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.3.2 La mise à jour en utilisant un SVM mono-classe . . . . . . . . . . 89 5.4 Expérimentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 5.4.1 Les problèmes benchmarks et les métriques . . . . . . . . . . . . 91 5.4.2 Résultats de simulation . . . . . . . . . . . . . . . . . . . . . . . . 91 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 6 Expérimentation 96 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.1 Métriques de performance . . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.1.1 La métrique ? (Spread) . . . . . . . . . . . . . . . . . . . . . . . 97 6.1.2 Distance générational GD . . . . . . . . . . . . . . . . . . . . . . 97 6.1.3 Distance générational inversée IGD . . . . . . . . . . . . . . . . . 98 6.1.4 Hypervolume H . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 6.2 Les problèmes test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 6.2.1 Les problèmes test ZDT . . . . . . . . . . . . . . . . . . . . . . . 99 6.2.2 Les problèmes test DTLZ . . . . . . . . . . . . . . . . . . . . . . . 102 6.2.3 Métriques de qualité proposée . . . . . . . . . . . . . . . . . . . . 105 6.3 Les résultats de Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . 106 6.3.1 Qualités de Solutions (Stage d’optimisation) . . . . . . . . . . . . 106 6.3.2 Convergence des Solutions (Stage d’optimisation) . . . . . . . . . 108 6.3.3 La vitesse de mise à jour des solutions . . . . . . . . . . . . . . . 110 6.3.4 Nombres de nouvelles solutions . . . . . . . . . . . . . . . . . . . 110 6.3.5 Diversité des solutions . . . . . . . . . . . . . . . . . . . . . . . . 112 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 Conclusions et perspectives 114 6.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.5 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 Bibliographie 132 A Les Fronts Pareto des problèmes Many-objective 133 A.1 Les résultats pour les problèmes Many-objective utilisés . . . . . . . . . 134 B Métriques des résultats pour les problèmes de CEC2009 139 B.1 Les résultats pour les problèmes CEC2009 . . . . . . . . . . . . . . . . . . 140 |
| En ligne : | http://thesis.univ-biskra.dz/2620/1/Th%C3%A8se_103_2016.pdf |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| TINF/100 | Théses de doctorat | bibliothèque sciences exactes | Consultable |
