| Titre : | Adaptation des métaheuristiques aux problèmes d'optimisation à variables continues |
| Auteurs : | ABDELHAK FAREH, Auteur ; Okba Kazar, 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, 2009 |
| ISBN/ISSN/EAN : | TINF/18 |
| Format : | 1 vol. (116 p.) / ill. / 29 cm |
| Langues: | Français |
| Résumé : |
Les métaheuristiques ont été conçues, à l’origine, pour résoudre les problèmes d’optimisation discrète. Le travail présenté dans le cadre de ce mémoire consiste à adapter spécialement la méthode d’optimisation par essaim de particules aux problèmes à variables continues. Cette métaheuristique est l’une des méthodes de la large catégorie des méthodes d’intelligence en essaim. Elle simule le comportement social des essaims d’oiseaux et des bancs de poissons et repose sur la notion d’essaim de particules.L’algorithme d’essaim de particules se base sur la collaboration des particules entre elles. Il est initialisé par une population de solutions potentielles aléatoires, interprétées comme des particules se déplaçant dans l’espace de recherche. Chaque particule est attirée vers sa meilleure position découverte par le passé ainsi que vers la meilleure position découverte par les particules de son voisinage.L’algorithme est enfin appliqué dans le cadre d’un problème de télécommunication concernant la planification des réseaux locaux sans-fil. Ce problème est similaire à celui posé depuis quelques années dans les réseaux cellulaires et largement traité dans la littérature.La planification d’un réseau local sans-fil est un problème d’optimisation dont les variables sont données par l’ensemble des configurations possibles des points d’accès et les objectifs par la description mathématique des services que le réseau doit offrir. |
| Sommaire : |
Intro duction générale Introduction générale 1 Chapitre 1 Chapitre 1 : G énér a li t é s ur l es m ét ah e u ri s ti q u es G énér a li t é s ur l es m ét ah e u ri s ti q u es 4 I. Introduction 4 II. Vue générale 4 III. Notions fondamentales 6 III.1. Définition 6 III.2. Présentation des heuristiques 6 III.3. Présentation des métaheuristiques 7 III.4. Fonctionnement général des métaheuristiques 7 III.4.1. Fonctionnement des métaheuristiques à parcours 8 III.4.2. Fonctionnement des métaheuristiques à populations 8 III.4.3. Fonctionnement des métaheuristiques à méthodes implicites 9 III.4.4. Fonctionnement des métaheuristiques à méthodes explicites 9 IV. Métaheuristiques modernes 9 IV.1. Méthode du recuit simulé 9 IV.2. Méthode de recherche tabou 12 IV.2.1. Principe de base 12 IV.2.2. Critère d’aspiration 13 IV.2.3. Intensification 14 IV.2.4. Diversification 14 IV.3. Algorithmes génétiques 15 IV.3.1. Principe de base 15 IV.3.2. Codage 16 IV.3.3. Calcul de la qualité 17 IV.3.4. Opérateurs de reproduction 17 IV.3.5. Quelques résultats théoriques 18 IV.4. Optimisation par colonie de fourmis 19 IV.5. Optimisation par essaim de particules 21 IV.5.1. Méthode de base 22 IV.5.2. Formulation générale 23 IV.5.3. Algorithme de base 24 IV.5.4. Paramètres de l’algorithme 24 IV.5.5. Domaines d’application 25 V. Conclusion 26 Chapitre 2 Chapitre 2 : Mé t ah e u ri s ti q u es po ur l’o p ti mi s ati on di f fi ci l e Mé t ah e u ri s ti q u es po ur l’o p ti mi s ati on di f fi ci l e 27 I. Introduction 27 II. Vue générale 27 III. Problème d’optimisation 28 IV. Processus d’optimisation 29 IV.1. Variables du problème 29 IV.2. Espace de recherche 29 IV.3. Fonctions objectif 30 Table des matières V. Optimisation difficile 30 VI. Métaheuristiques en optimisation 31 VI.1. Problème du voyageur de commerce 31 VI.2. Méthode du recuit simulé 31 VI.2.1. Avantages et inconvénients 32 VI.3. Algorithmes génétiques 32 VI.3.1. Instance du problème 32 VI.3.2. Espace de recherche 33 VI.3.3. Codage des points de l’espace de recherche 33 VI.3.4. Fonction d’évaluation 33 VI.3.5. Opérateurs génétiques classiques 33 VI.3.6. Diversification 34 VI.3.7. Avantages et inconvénients 34 VI.4. Optimisation par colonie de fourmis 35 VI.4.1. Algorithme 35 VI.4.2. Choix de la ville 36 VI.4.3. Trace locale 36 VI.4.4. Trace globale 36 VI.4.5. Efficacité de l’algorithme 36 VI.4.6. Avantages et inconvénients 37 VI.5. Optimisation par essaim de particules 37 VI.5.1. Espace de recherche 37 VI.5.2. Fonction objectif 37 VI.5.3. Formulations 38 VI.5.4. Vitesse 38 VI.5.5. Voisinage 38 VI.5.6. Processus NoHope / ReHope 39 VI.5.7. Extra-meilleure particule 40 VI.5.8. Version parallèle et séquentielle 41 VII. Conclusion 41 Chapitre 3 Chapitre 3 : Ad ap t a ti on d es mé t ahe u ri s ti q ue s a ux pr o bl èm es d’ o pti mi s a ti on cont i nu e d’ o pti mi s a ti on cont i nu e 42 I. Introduction 42 II. Adaptation de la méthode tabou 42 II.1. Principe 43 II.2. Notions de "voisinage" et de "pas" de mouvement 44 II.2.1. Subdivision de l’espace des solutions 44 II.2.2. Partitionnement par arbre binaire 45 II.2.3. Mouvement par modification d’une seule composante 46 II.2.4. Notion de voisinage par topologie de boules 46 II.3. Taille de la liste tabou 47 II.4. Présentation détaillée de l’algorithme tabou continu (CPTS) 48 II.4.1. Diversification 48 II.4.2. Sélection de la meilleure zone prometteuse 50 II.4.3. Intensification 51 II.5. Présentation de l’algorithme hybride tabou-polytope (CHTS) 52 II.5.1. Principe 52 II.5.2. Description de l’algorithme 52 II.5.3. Diversification 54 II.5.4. Intensification à l’intérieur d’une zone prometteuse 54 II.5.5. Critères d’arrêt 54 III. Adaptation de l’algorithme génétique 55 III.1. Principe de base de l’algorithme génétique pur continu (CPGA) 56 III.1.1. Diversification 56 III.1.2. Intensification 56 III.2. Génération de la population initiale 57 III.2.1. Théorie de l’entropie d’information 57 III.2.2. Méthode du voisinage 57 III.3. Fonction d’adaptation 58 III.3.1. Rangement linéaire 58 III.3.2. Rangement non linéaire 59 III.3.3. Simple fonction "fitness" 59 III.4. Sélection 59 III.4.1. Sélection proportionnelle 60 III.4.2. Sélection par tournois 61 III.5. Recombinaison 62 III.5.1. Recombinaison discrète 62 III.5.2. Recombinaison intermédiaire 63 III.5.3. Recombinaison "ligne" 63 III.5.4. Recombinaison hybride 64 III.6. Mutation 64 III.7. Remplacement et réinsertion (stratégies élitistes) 65 III.8. Présentation de l’algorithme hybride génétique-polytope (CHGA) 65 III.8.1. Principe 65 III.8.2. Description de l’algorithme 67 III.8.3. Diversification 67 III.8.4. Intensification à l’intérieur d’une zone prometteuse 68 III.8.5. Critères d’arrêt 68 IV. Adaptation de la méthode d’optimisation par colonie de fourmis 68 IV.1. Problèmes d’adaptation 68 IV.2. Algorithme CACO 69 IV.3. Méthode hybride 70 IV.4. Algorithme API 71 IV.5. ACO pour l’optimisation continue 72 IV.6. Algorithme CACS 73 V. Conclusion 74 Chapitre 4 Chapitre 4 : C once p ti on & I mpl é men t ati on C once p ti on & I mpl é men t ati on 76 I. Introduction 76 II. Planification de réseaux wLAN 76 II.1. Déploiement de réseaux sans-fil 76 II.2. Variables et paramètres du problème wLAN 77 II.2.1. Nombre de points d’accès 77 II.2.2. Position des points d’accès 77 II.2.3. Paramètres antennaires 77 II.3. Scénarios de planification 78 II.4. Objectifs de la planification 79 II.4.1. Objectifs de couverture radio 79 II.4.2. Objectifs de recouvrement et d’interférences 79 II.4.3. Objectifs de trafic et de qualité de service 80 II.5. Formulations du problème wLAN 81 II.5.1. Approche continue 81 II.5.2. Approche combinatoire 82 II.6. Métaheuristiques pour le problème wLAN 82 II.6.1. Recuit simulé 82 II.6.2. Recherche Tabou 83 II.6.3. Algorithmes génétiques 84 III. Environnement de développement 84 IV. Choix techniques 85 V. Description du modèle 85 VI. Présentation du logiciel 89 VII. Étude de cas 93 VIII. Résultats d’application 96 IX. Étude comparative 99 X. Conclusion 107 Conclusion générale 109 Annexe Annexe : Ré su lt a ts o b te nu s Ré su lt a ts o b te nu s 111 R éférences bibliographiques 115 |
| Type de document : | Thése magister |
| En ligne : | http://thesis.univ-biskra.dz/id/eprint/3656 |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| TINF/18 | Mémoire de magister | bibliothèque sciences exactes | Consultable |
