|
| Titre : |
Contributions à la Résolution de l'Emergence Inversée en Utilisant les Métaheuristiques Quantiques |
| Type de document : |
texte imprimé |
| Auteurs : |
Djemame,Sefia, Auteur ; Batouche, Mohamed, Auteur |
| Editeur : |
Setif:UFA |
| Année de publication : |
2018 |
| Importance : |
1 vol (135 f .) |
| Format : |
29 cm |
| Langues : |
Français (fre) |
| Catégories : |
Thèses & Mémoires:Informatique
|
| Mots-clés : |
Système complexe
Automate cellulaire
Emergence inversée
Métaheuristiques
Informatique quantique
Particle swarm optimization
Genetic algorithm
Quantum
Quantum GA
Traitement d'images |
| Index. décimale : |
004 Informatique |
| Résumé : |
Résumé
Les systèmes complexes présentent une propriété intéressante : l'émergence.
Cette propriété est présente dans beaucoup de modèles inspirés de la nature.
Parmi ces modèles : les automates cellulaires, les colonies de fourmis, les syst
èmes multi-agents, les essaims de particules, les réseaux de neurones arti ciels.
La résolution de l'émergence inversée dans ces systèmes consiste à déterminer les
règles de base qui permettent à un collectif d'individus simples de coopérer et de
produire à un niveau global, une fonction émergente. Dans la littérature, ce probl
ème est quali é de "di cile" et induit d'intenses recherches. Dans cette optique,
nous proposons dans cette thèse trois méthodes de résolution. La première mé-
thode s'appuie sur la métaheuristique PSO, qui guide un processus évolutionnaire
d'automate cellulaire. La validation a été faite à travers l'extraction de contours
sur images. La deuxième méthode utilise les principes de l'informatique quantique
hybridée avec le PSO, à travers la métaheuristique Quantum PSO, pour
tirer pro t de la diversi cation de la population, le parallélisme, et la richesse des
opérateurs quantiques. Ce modèle a été utilisé pour résoudre deux problèmes : la
détection de contours et le ltrage d'images. La troisième méthode est une hybridation
entre l'algorithme génétique et l'informatique quantique. L'algorithme
obtenu a montré une bonne capacité de recherche globale. Un nombre réduit de
chromosomes quantiques a su pour étudier le problème.
Les résultats expérimentaux obtenus par les trois méthodes ont démontré la
grande capacité des métaheuristiques utilisées pour apporter une solution satisfaisante
au problème de l'émergence inversée et assurer une excellente convergence
du système et un bon équilibre entre exploitation et exploration |
| Note de contenu : |
Sommaire
Table des matières
Liste des gures iv
Liste des tableaux vi
Introduction Générale 1
1 Introduction aux Systèmes Complexes 8
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Systèmes Complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Niveaux de Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Historique et Dé nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.2 Dé nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Classi cation des Systèmes Complexes : types de complexité . . . . . . . . . . 11
1.4.1 Type 1. Complexité statique . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4.2 Type 2. Complexité dynamique . . . . . . . . . . . . . . . . . . . . . . 12
1.4.3 Type 3. Complexité évolutive . . . . . . . . . . . . . . . . . . . . . . . 12
1.4.4 Type 4. Complexité auto-organisatrice . . . . . . . . . . . . . . . . . . 12
1.5 Caractéristiques des Systèmes Complexes . . . . . . . . . . . . . . . . . . . . . 13
1.5.1 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5.2 Changement du niveau d'intégration . . . . . . . . . . . . . . . . . . . 14
1.5.3 Boucles de rétroaction et non-linéarité . . . . . . . . . . . . . . . . . . 14
1.5.4 Indéterminisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5.5 Irréversibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.6 Emergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.7 Auto-organisation et systèmes auto-organisés . . . . . . . . . . . . . . . 19
1.5.8 Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.8.1 Système adaptatif . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5.9 Apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.5.9.1 Types d'apprentissage . . . . . . . . . . . . . . . . . . . . . . 21
1.5.9.2 Diérence entre apprentissage et adaptation . . . . . . . . . . 21
1.6 Domaines d'application des systèmes complexes . . . . . . . . . . . . . . . . . 22
1.6.1 Biologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.6.2 Sciences sociales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.6.3 Psychologie et neuroscience . . . . . . . . . . . . . . . . . . . . . . . . 23
1.6.4 Economie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.6.5 Chimie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.6.6 Géologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.6.7 Logistique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.7 Exemples de systèmes complexes naturels et arti ciels . . . . . . . . . . . . . . 25
1.7.1 Systèmes complexes naturels . . . . . . . . . . . . . . . . . . . . . . . . 26
1.7.1.1 Le tas de sable . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.7.1.2 Les colonies d'insectes sociaux . . . . . . . . . . . . . . . . . . 27
1.7.1.3 Autres exemples naturels . . . . . . . . . . . . . . . . . . . . 28
1.7.2 Systèmes complexes arti ciels . . . . . . . . . . . . . . . . . . . . . . . 28
1.7.2.1 Systèmes multi-agents . . . . . . . . . . . . . . . . . . . . . . 29
1.7.2.2 Boids de Reynolds . . . . . . . . . . . . . . . . . . . . . . . . 31
1.7.2.3 L'intelligence en essaim . . . . . . . . . . . . . . . . . . . . . 33
1.7.2.4 Les réseaux de neurones . . . . . . . . . . . . . . . . . . . . . 33
1.7.2.5 Les algorithmes évolutionnaires . . . . . . . . . . . . . . . . . 35
1.7.2.6 Les automates cellulaires . . . . . . . . . . . . . . . . . . . . . 36
1.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2 Les Automates Cellulaires 39
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2 Dé nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.1 Dé nition générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.2 Dé nition formelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.2.2.1 Naissance des Automates Cellulaires . . . . . . . . . . . . . . 41
2.2.3 Exemples d'Automates Cellulaires . . . . . . . . . . . . . . . . . . . . . 42
2.2.3.1 Automate Cellulaire Elémentaire . . . . . . . . . . . . . . . . 42
2.2.3.2 L'automate cellulaire "Jeu de la Vie" . . . . . . . . . . . . . . 43
2.2.3.3 Exploration des possibilités des AC . . . . . . . . . . . . . . . 44
2.2.4 La classi cation de Wolfram . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3 Domaines d'Application des Automates Cellulaires . . . . . . . . . . . . . . . 45
2.3.1 Modélisation en Physique . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.2 Codage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.3 Mathématiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.4 Électronique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.5 Phénomènes Biologiques . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.3.6 Autres applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.4 les Automates Cellulaires en Traitement d'images . . . . . . . . . . . . . . . . 48
2.4.1 Intérêt des AC en traitement d'images . . . . . . . . . . . . . . . . . . 48
2.4.2 Etat de l'art des AC en traitement d'images . . . . . . . . . . . . . . . 48
2.5 Problématique et motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.5.1 Formulation du problème . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.5.2 Problèmes Inverses d'Automates Cellulaires . . . . . . . . . . . . . . . 50
2.5.2.1 Dé nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.5.2.2 Quelques Problèmes Inverses d'Automates Cellulaires . . . . . 52
2.5.3 Approches utilisées dans la littérature . . . . . . . . . . . . . . . . . . . 55
2.5.4 Les Algorithmes Evolutionnaires pour Résoudre l'Emergence Inversée . 55
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3 Métaheuristiques d'Optimisation : Etat de l'Art 57
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2 Les Algorithmes d'Optimisation Approchée . . . . . . . . . . . . . . . . . . . . 58
3.2.1 Heuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2.2 Métaheuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2.3 Les métaheuristiques à solution unique . . . . . . . . . . . . . . . . . . 59
3.2.3.1 Le Recuit Simulé . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.2.3.2 L'Algorithme de Recherche Tabou . . . . . . . . . . . . . . . 61
3.2.4 Les métaheuristiques à population de solutions . . . . . . . . . . . . . . 62
3.2.4.1 Les algorithmes évolutionnaires . . . . . . . . . . . . . . . . . 62
3.2.4.2 Les Algorithmes des Colonies de Fourmis . . . . . . . . . . . . 64
3.2.4.3 L'algorithme des colonies d'abeilles arti cielles (ABC) . . . . 66
3.2.4.4 Les systèmes immunitaires arti ciels (AIS) . . . . . . . . . . . 66
3.2.4.5 Algorithme à évolution diérentielle . . . . . . . . . . . . . . 68
3.2.4.6 Les algorithmes à estimation de distribution . . . . . . . . . . 68
3.3 L'Optimisation par Essaim de Particules . . . . . . . . . . . . . . . . . . . . . 69
3.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.3.2 Comparaison entre l'algorithme génétique et le PSO . . . . . . . . . . . 70
3.3.3 Domaines d'utilisation du PSO . . . . . . . . . . . . . . . . . . . . . . 71
3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4 L'Informatique Quantique 73
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.2 L'Informatique Quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.2.1 Bit Quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.2.2 Registre quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.2.3 Les cinq principes de l'informatique quantique . . . . . . . . . . . . . . 75
4.2.4 Calcul quantique et algorithmes quantiques . . . . . . . . . . . . . . . . 77
4.2.5 Avantages et limites de l'informatique quantique . . . . . . . . . . . . . 78
4.3 Algorithmes Evolutionnaires Quantiques . . . . . . . . . . . . . . . . . . . . . 79
4.3.1 Individu quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.3.2 Mesure quantique d'individus . . . . . . . . . . . . . . . . . . . . . . . 80
4.3.3 La porte D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.3.4 Discussion de l'algorithme évolutionnaire quantique . . . . . . . . . . . 82
4.4 Autres Algorithmes Inspirés du Quantique . . . . . . . . . . . . . . . . . . . . 82
4.4.1 Algorithmes génétiques quantiques . . . . . . . . . . . . . . . . . . . . 83
4.4.2 Boids de Reynolds quantiques . . . . . . . . . . . . . . . . . . . . . . . 84
4.4.3 Réseaux de neurones quantiques . . . . . . . . . . . . . . . . . . . . . . 85
4.5 Avantages des Algorithmes Inspirés du Quantique . . . . . . . . . . . . . . . . 85
4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5 Utilisation du PSO puis QPSO pour résoudre le problème d'émergence inversée .......87
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.2 Contribution 1 : Application de la Métaheuristique PSO pour la Résolution de l'Emergence Inversée . . . . . . 87
5.2.1 Format des règles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.2.2 Evolution de l'automate Cellulaire par la métaheuristique PSO . . . . . 89
5.2.3 La fonction Fitness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.2.4 L'algorithme CA-PSO pour la détection de contours . . . . . . . . . . . 90
5.2.5 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.2.5.1 Les meilleures règles obtenues . . . . . . . . . . . . . . . . . . 92
5.2.5.2 Résultats sur images de synthèse . . . . . . . . . . . . . . . . 92
5.2.5.3 Résultats sur image à niveaux de gris . . . . . . . . . . . . . . 93
5.2.5.4 Résultats sur image réelle . . . . . . . . . . . . . . . . . . . . 93
5.2.5.5 Résultats sur image médicale . . . . . . . . . . . . . . . . . . 94
5.2.5.6 Temps d'exécution . . . . . . . . . . . . . . . . . . . . . . . . 94
5.2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.3 Contribution 2 : Utilisation du PSO Quantique pour la résolution de problème inverse . . . . . .. . 95
5.3.1 L'Algorithme Quantum-behaved PSO . . . . . . . . . . . . . . . . . . . 96
5.3.2 L'approche proposée . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.3.3 Les règles de transition . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.4 Réglage de paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.5 Les fonctions tness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.6 L'algorithme QPSO pour la détection de contours . . . . . . . . . . . . 99
5.3.7 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.3.7.1 Meilleur paquet de règles . . . . . . . . . . . . . . . . . . . . 100
5.3.7.2 Résultats visuels . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.3.7.3 Comparaison avec des travaux similaires . . . . . . . . . . . . 101
5.3.8 L'algorithme QPSO pour le ltrage d'images . . . . . . . . . . . . . . . 104
5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6 L'Algorithme Génétique Quantique pour la Résolution de l'Emergence Inversée .....107
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.2 Etat de l'art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.3 Généralités sur le Quantum Genetic Computing . . . . . . . . . . . . . . . . . 109
6.3.1 Principes de l'Algorithme Génétique Quantique . . . . . . . . . . . . . 110
6.3.2 Codage des Chromosomes Quantiques . . . . . . . . . . . . . . . . . . 110
6.3.3 La Mesure des Chromosomes . . . . . . . . . . . . . . . . . . . . . . . 111
6.4 L'Approche Proposée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.5 Résultats Expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.6 Comparaison entre Algorithme Génétique Quantique et Algorithme Génétique Classique . . . . . . . 115
6.6.1 Résultats Numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.6.2 Complexité Algorithmique . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Conclusion et Perspectives 119
Travaux de l'auteur 121
Bibliographie |
| Côte titre : |
DI/0036 |
| En ligne : |
https://drive.google.com/file/d/1v48n0zBwSM8vrMsZyUqThjE9MEXQlGn2/view?usp=shari [...] |
| Format de la ressource électronique : |
pdf |
Contributions à la Résolution de l'Emergence Inversée en Utilisant les Métaheuristiques Quantiques [texte imprimé] / Djemame,Sefia, Auteur ; Batouche, Mohamed, Auteur . - [S.l.] : Setif:UFA, 2018 . - 1 vol (135 f .) ; 29 cm. Langues : Français ( fre)
| Catégories : |
Thèses & Mémoires:Informatique
|
| Mots-clés : |
Système complexe
Automate cellulaire
Emergence inversée
Métaheuristiques
Informatique quantique
Particle swarm optimization
Genetic algorithm
Quantum
Quantum GA
Traitement d'images |
| Index. décimale : |
004 Informatique |
| Résumé : |
Résumé
Les systèmes complexes présentent une propriété intéressante : l'émergence.
Cette propriété est présente dans beaucoup de modèles inspirés de la nature.
Parmi ces modèles : les automates cellulaires, les colonies de fourmis, les syst
èmes multi-agents, les essaims de particules, les réseaux de neurones arti ciels.
La résolution de l'émergence inversée dans ces systèmes consiste à déterminer les
règles de base qui permettent à un collectif d'individus simples de coopérer et de
produire à un niveau global, une fonction émergente. Dans la littérature, ce probl
ème est quali é de "di cile" et induit d'intenses recherches. Dans cette optique,
nous proposons dans cette thèse trois méthodes de résolution. La première mé-
thode s'appuie sur la métaheuristique PSO, qui guide un processus évolutionnaire
d'automate cellulaire. La validation a été faite à travers l'extraction de contours
sur images. La deuxième méthode utilise les principes de l'informatique quantique
hybridée avec le PSO, à travers la métaheuristique Quantum PSO, pour
tirer pro t de la diversi cation de la population, le parallélisme, et la richesse des
opérateurs quantiques. Ce modèle a été utilisé pour résoudre deux problèmes : la
détection de contours et le ltrage d'images. La troisième méthode est une hybridation
entre l'algorithme génétique et l'informatique quantique. L'algorithme
obtenu a montré une bonne capacité de recherche globale. Un nombre réduit de
chromosomes quantiques a su pour étudier le problème.
Les résultats expérimentaux obtenus par les trois méthodes ont démontré la
grande capacité des métaheuristiques utilisées pour apporter une solution satisfaisante
au problème de l'émergence inversée et assurer une excellente convergence
du système et un bon équilibre entre exploitation et exploration |
| Note de contenu : |
Sommaire
Table des matières
Liste des gures iv
Liste des tableaux vi
Introduction Générale 1
1 Introduction aux Systèmes Complexes 8
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Systèmes Complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Niveaux de Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Historique et Dé nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.2 Dé nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Classi cation des Systèmes Complexes : types de complexité . . . . . . . . . . 11
1.4.1 Type 1. Complexité statique . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4.2 Type 2. Complexité dynamique . . . . . . . . . . . . . . . . . . . . . . 12
1.4.3 Type 3. Complexité évolutive . . . . . . . . . . . . . . . . . . . . . . . 12
1.4.4 Type 4. Complexité auto-organisatrice . . . . . . . . . . . . . . . . . . 12
1.5 Caractéristiques des Systèmes Complexes . . . . . . . . . . . . . . . . . . . . . 13
1.5.1 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5.2 Changement du niveau d'intégration . . . . . . . . . . . . . . . . . . . 14
1.5.3 Boucles de rétroaction et non-linéarité . . . . . . . . . . . . . . . . . . 14
1.5.4 Indéterminisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5.5 Irréversibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.6 Emergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.7 Auto-organisation et systèmes auto-organisés . . . . . . . . . . . . . . . 19
1.5.8 Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.8.1 Système adaptatif . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5.9 Apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.5.9.1 Types d'apprentissage . . . . . . . . . . . . . . . . . . . . . . 21
1.5.9.2 Diérence entre apprentissage et adaptation . . . . . . . . . . 21
1.6 Domaines d'application des systèmes complexes . . . . . . . . . . . . . . . . . 22
1.6.1 Biologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.6.2 Sciences sociales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.6.3 Psychologie et neuroscience . . . . . . . . . . . . . . . . . . . . . . . . 23
1.6.4 Economie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.6.5 Chimie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.6.6 Géologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.6.7 Logistique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.7 Exemples de systèmes complexes naturels et arti ciels . . . . . . . . . . . . . . 25
1.7.1 Systèmes complexes naturels . . . . . . . . . . . . . . . . . . . . . . . . 26
1.7.1.1 Le tas de sable . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.7.1.2 Les colonies d'insectes sociaux . . . . . . . . . . . . . . . . . . 27
1.7.1.3 Autres exemples naturels . . . . . . . . . . . . . . . . . . . . 28
1.7.2 Systèmes complexes arti ciels . . . . . . . . . . . . . . . . . . . . . . . 28
1.7.2.1 Systèmes multi-agents . . . . . . . . . . . . . . . . . . . . . . 29
1.7.2.2 Boids de Reynolds . . . . . . . . . . . . . . . . . . . . . . . . 31
1.7.2.3 L'intelligence en essaim . . . . . . . . . . . . . . . . . . . . . 33
1.7.2.4 Les réseaux de neurones . . . . . . . . . . . . . . . . . . . . . 33
1.7.2.5 Les algorithmes évolutionnaires . . . . . . . . . . . . . . . . . 35
1.7.2.6 Les automates cellulaires . . . . . . . . . . . . . . . . . . . . . 36
1.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2 Les Automates Cellulaires 39
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2 Dé nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.1 Dé nition générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.2 Dé nition formelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.2.2.1 Naissance des Automates Cellulaires . . . . . . . . . . . . . . 41
2.2.3 Exemples d'Automates Cellulaires . . . . . . . . . . . . . . . . . . . . . 42
2.2.3.1 Automate Cellulaire Elémentaire . . . . . . . . . . . . . . . . 42
2.2.3.2 L'automate cellulaire "Jeu de la Vie" . . . . . . . . . . . . . . 43
2.2.3.3 Exploration des possibilités des AC . . . . . . . . . . . . . . . 44
2.2.4 La classi cation de Wolfram . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3 Domaines d'Application des Automates Cellulaires . . . . . . . . . . . . . . . 45
2.3.1 Modélisation en Physique . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.2 Codage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.3 Mathématiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.4 Électronique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.5 Phénomènes Biologiques . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.3.6 Autres applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.4 les Automates Cellulaires en Traitement d'images . . . . . . . . . . . . . . . . 48
2.4.1 Intérêt des AC en traitement d'images . . . . . . . . . . . . . . . . . . 48
2.4.2 Etat de l'art des AC en traitement d'images . . . . . . . . . . . . . . . 48
2.5 Problématique et motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.5.1 Formulation du problème . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.5.2 Problèmes Inverses d'Automates Cellulaires . . . . . . . . . . . . . . . 50
2.5.2.1 Dé nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.5.2.2 Quelques Problèmes Inverses d'Automates Cellulaires . . . . . 52
2.5.3 Approches utilisées dans la littérature . . . . . . . . . . . . . . . . . . . 55
2.5.4 Les Algorithmes Evolutionnaires pour Résoudre l'Emergence Inversée . 55
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3 Métaheuristiques d'Optimisation : Etat de l'Art 57
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2 Les Algorithmes d'Optimisation Approchée . . . . . . . . . . . . . . . . . . . . 58
3.2.1 Heuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2.2 Métaheuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2.3 Les métaheuristiques à solution unique . . . . . . . . . . . . . . . . . . 59
3.2.3.1 Le Recuit Simulé . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.2.3.2 L'Algorithme de Recherche Tabou . . . . . . . . . . . . . . . 61
3.2.4 Les métaheuristiques à population de solutions . . . . . . . . . . . . . . 62
3.2.4.1 Les algorithmes évolutionnaires . . . . . . . . . . . . . . . . . 62
3.2.4.2 Les Algorithmes des Colonies de Fourmis . . . . . . . . . . . . 64
3.2.4.3 L'algorithme des colonies d'abeilles arti cielles (ABC) . . . . 66
3.2.4.4 Les systèmes immunitaires arti ciels (AIS) . . . . . . . . . . . 66
3.2.4.5 Algorithme à évolution diérentielle . . . . . . . . . . . . . . 68
3.2.4.6 Les algorithmes à estimation de distribution . . . . . . . . . . 68
3.3 L'Optimisation par Essaim de Particules . . . . . . . . . . . . . . . . . . . . . 69
3.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.3.2 Comparaison entre l'algorithme génétique et le PSO . . . . . . . . . . . 70
3.3.3 Domaines d'utilisation du PSO . . . . . . . . . . . . . . . . . . . . . . 71
3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4 L'Informatique Quantique 73
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.2 L'Informatique Quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.2.1 Bit Quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.2.2 Registre quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.2.3 Les cinq principes de l'informatique quantique . . . . . . . . . . . . . . 75
4.2.4 Calcul quantique et algorithmes quantiques . . . . . . . . . . . . . . . . 77
4.2.5 Avantages et limites de l'informatique quantique . . . . . . . . . . . . . 78
4.3 Algorithmes Evolutionnaires Quantiques . . . . . . . . . . . . . . . . . . . . . 79
4.3.1 Individu quantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.3.2 Mesure quantique d'individus . . . . . . . . . . . . . . . . . . . . . . . 80
4.3.3 La porte D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.3.4 Discussion de l'algorithme évolutionnaire quantique . . . . . . . . . . . 82
4.4 Autres Algorithmes Inspirés du Quantique . . . . . . . . . . . . . . . . . . . . 82
4.4.1 Algorithmes génétiques quantiques . . . . . . . . . . . . . . . . . . . . 83
4.4.2 Boids de Reynolds quantiques . . . . . . . . . . . . . . . . . . . . . . . 84
4.4.3 Réseaux de neurones quantiques . . . . . . . . . . . . . . . . . . . . . . 85
4.5 Avantages des Algorithmes Inspirés du Quantique . . . . . . . . . . . . . . . . 85
4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5 Utilisation du PSO puis QPSO pour résoudre le problème d'émergence inversée .......87
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.2 Contribution 1 : Application de la Métaheuristique PSO pour la Résolution de l'Emergence Inversée . . . . . . 87
5.2.1 Format des règles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.2.2 Evolution de l'automate Cellulaire par la métaheuristique PSO . . . . . 89
5.2.3 La fonction Fitness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.2.4 L'algorithme CA-PSO pour la détection de contours . . . . . . . . . . . 90
5.2.5 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.2.5.1 Les meilleures règles obtenues . . . . . . . . . . . . . . . . . . 92
5.2.5.2 Résultats sur images de synthèse . . . . . . . . . . . . . . . . 92
5.2.5.3 Résultats sur image à niveaux de gris . . . . . . . . . . . . . . 93
5.2.5.4 Résultats sur image réelle . . . . . . . . . . . . . . . . . . . . 93
5.2.5.5 Résultats sur image médicale . . . . . . . . . . . . . . . . . . 94
5.2.5.6 Temps d'exécution . . . . . . . . . . . . . . . . . . . . . . . . 94
5.2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.3 Contribution 2 : Utilisation du PSO Quantique pour la résolution de problème inverse . . . . . .. . 95
5.3.1 L'Algorithme Quantum-behaved PSO . . . . . . . . . . . . . . . . . . . 96
5.3.2 L'approche proposée . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.3.3 Les règles de transition . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.4 Réglage de paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.5 Les fonctions tness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.6 L'algorithme QPSO pour la détection de contours . . . . . . . . . . . . 99
5.3.7 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.3.7.1 Meilleur paquet de règles . . . . . . . . . . . . . . . . . . . . 100
5.3.7.2 Résultats visuels . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.3.7.3 Comparaison avec des travaux similaires . . . . . . . . . . . . 101
5.3.8 L'algorithme QPSO pour le ltrage d'images . . . . . . . . . . . . . . . 104
5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6 L'Algorithme Génétique Quantique pour la Résolution de l'Emergence Inversée .....107
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.2 Etat de l'art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.3 Généralités sur le Quantum Genetic Computing . . . . . . . . . . . . . . . . . 109
6.3.1 Principes de l'Algorithme Génétique Quantique . . . . . . . . . . . . . 110
6.3.2 Codage des Chromosomes Quantiques . . . . . . . . . . . . . . . . . . 110
6.3.3 La Mesure des Chromosomes . . . . . . . . . . . . . . . . . . . . . . . 111
6.4 L'Approche Proposée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.5 Résultats Expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.6 Comparaison entre Algorithme Génétique Quantique et Algorithme Génétique Classique . . . . . . . 115
6.6.1 Résultats Numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.6.2 Complexité Algorithmique . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Conclusion et Perspectives 119
Travaux de l'auteur 121
Bibliographie |
| Côte titre : |
DI/0036 |
| En ligne : |
https://drive.google.com/file/d/1v48n0zBwSM8vrMsZyUqThjE9MEXQlGn2/view?usp=shari [...] |
| Format de la ressource électronique : |
pdf |
|
Contributions à la Résolution de l'Emergence Inversée en Utilisant les Métaheuristiques Quantiques
