introdc
145 pages
Français
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
145 pages
Français
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

UNIVERSITÉ MOHAMMED V – AGDAL FACULTÉ DES SCIENCES Rabat N° d’ordre: 2493 THÈSE DE DOCTORAT Présentée par : Lamia Benameur Discipline : Sciences de l’Ingénieur Spécialité : Informatique et Télécommunications Titre : Contribution à l’optimisation complexe par des techniques de swarm intelligence Soutenue le : 13 Mai 2010 Devant le jury Président : D. Aboutajdine, Professeur, Faculté des Sciences de Rabat. Examinateurs : A.A. El Imrani, Professeur, Faculté des Sciences de Rabat B. El Ouahidi, Professeur, Faculté des Sciences de Rabat A. Sekkaki, Professeur, Faculté des Sciences Ain Chock de Casablanca J. Benabdelouahab, Professeur, Faculté des Sciences de Tanger Y. El Amrani, Professeur Assistant, Faculté des Sciences de Rabat Faculté des Sciences, 4 Avenue Ibn Battouta B.P. 1014 RP, Rabat – Maroc Tel +212 (0) 37 77 18 34/35/38, Fax : +212 (0) 37 77 42 61, http://www.fsr.ac.ma Avant-Propos LestravauxprésentésdanscemémoireontétéeffectuésauLaboratoireConception et Systèmes (LCS) de la Faculté des Sciences de Rabat (Equipe de Soft Computing et aide à la décision) sous la direction du Professeur A. A. El Imrani. J’exprime, tout d’abord, ma vive reconnaissance à Monsieur A. Ettouhami, Di- recteur du LCS, pour la confiance qu’il m’a accordée en m’autorisant à mener mes travaux de recherche dans ce laboratoire.

Informations

Publié par
Publié le 19 juillet 2012
Nombre de lectures 33
Langue Français
Poids de l'ouvrage 4 Mo

Extrait

 UNIVERSITÉ MOHAMMED V – AGDAL  FACULTÉ DES SCIENCES  Rabat
 N° d’ordre: 2493 THÈSE DE DOCTORAT Présentée par : Lamia Benameur Discipline :Sciences de l’Ingénieur Spécialité :Informatique et Télécommunications Titre :Contribution à l’optimisation complexe par des techniques de swarm intelligence Soutenue le : 13 Mai 2010Devant le jury Président : D. Aboutajdine,Professeur, Faculté des Sciences de Rabat. Examinateurs :  A.A. El Imrani,Professeur, Faculté des Sciences de Rabat B.El Ouahidi,Professeur, Faculté des Sciences de Rabat  A. Sekkaki,Professeur, Faculté des Sciences Ain Chock de Casablanca J. Benabdelouahab,Professeur, Faculté des Sciences de Tanger Y. El Amrani,Professeur Assistant, Faculté des Sciences de Rabat Faculté des Sciences, 4 Avenue Ibn Battouta B.P. 1014 RP, Rabat – Maroc Tel +212 (0) 37 77 18 34/35/38, Fax : +212 (0) 37 77 42 61, http://www.fsr.ac.ma
AvantPropos
Les travaux présentés dans ce mémoire ont été effectués au Laboratoire Conception et Systèmes (LCS) de la Faculté des Sciences de Rabat (Equipe de Soft Computing et aide à la décision) sous la direction du Professeur A. A. El Imrani.
J’exprime, tout d’abord, ma vive reconnaissance à Monsieur A. Ettouhami, Di recteur du LCS, pour la confiance qu’il m’a accordée en m’autorisant à mener mes travaux de recherche dans ce laboratoire.
Je ne saurai témoigner toute ma gratitude à Monsieur A. A. El Imrani, Professeur à la Faculté des Sciences de Rabat, pour ses qualités humaines et scientifiques. Je suis heureuse de lui adresser mes vifs remerciements pour l’intérêt qu’il a manifesté à ce travail en acceptant la charge de suivre de près ces travaux. Je voudrais lui exprimer ma profonde reconnaissance pour l’aide qu’il m’a constamment octroyée tout au long de ce travail, qu’il trouve, en ce mémoire, le témoignage de mes sincères remerciements.
Je présente à Monsieur D. Aboutajdine, Professeur à la Faculté des sciences de Rabat, l’expression de ma profonde reconnaissance, pour l’honneur qu’il me fait en acceptant de présider ce jury de thèse.
Je tiens à remercier Monsieur B. El Ouahidi, Professeur à la Faculté des Sciences de Rabat, de l’intérêt qu’il a porté à ce travail en acceptant d’en être rapporteur et de sa participation au jury de cette thèse.
Je suis particulièrement reconnaissante à Monsieur J. Benabdelouahab, Professeur à la Faculté des Sciences et Techniques de Tanger, qui a bien voulu consacrer une part de son temps pour s’intéresser à ce travail, d’en être le rapporteur et qui me fait l’honneur de siéger dans le jury de cette thèse.
Que Monsieur A. Sekkaki, Professeur à la Faculté des Sciences Ain Chock de Casablanca, accepte mes vifs remerciements pour avoir bien voulu juger ce travail et pour sa participation au jury de cette thèse.
Mes remerciements et ma haute considération vont également à Monsieur Y. El Amrani, Professeur assistant à la Faculté des Sciences de Rabat, pour ses remarques, ses nombreux conseils et pour l’intérêt qu’il a porté à ce travail.
Je n’oublierai pas d’exprimer mon amitié et ma reconnaissance à Mademoiselle J. Alami Chentoufi, docteur chercheur et membre de l’équipe Soft computing et aide à la décision du laboratoire LCS, qui m’a initié au sujet de thèse. Elle m’a fait bénéficier de ses encouragements, de son soutien amical et moral et de son aide scientifique de tous les instants qu’elle n’a cessés de me témoigner.
i
Je tiens à remercier tous les membres du Laboratoire Conception et Systèmes, Professeurs et Doctorants, pour leur esprit de groupe. Qu’ils trouvent ici le témoi gnage de toute mon estime et ma sincère sympathie.
Je tiens finalement à souligner que la partie de ce travail, portant sur le problème d’affectation de fréquences mobiles, entre dans le cadre du projet "Résolution du problème d’affectation de fréquences par des méthodes de Soft Computing" soutenu par la Direction de la technologie du Ministère de l’Enseignement Supérieur.
"Durant les trois dernières années de mes études doctorales, j’ai bénéficié d’une bourse d’excellence octroyée par le Centre National de Recherche Scientifique et Technique (CNRST) et ce dans le cadre du programme des bourses de recherche initié par le ministère de l’Education Nationale de l’Enseignement Supérieur, de la Formation des Cadres et de la Recherche Scientifique".
ii
Table
des
matières
Introduction générale
1
I Application de l’algorithme d’optimisation par essaims particulaires à des problèmes réels 5
1 Techniques de calcul "intelligent" 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Techniques de Calcul "Intelligent" . . . . . . . . . . . . . . . . . . . . 1.2.1 Les réseaux de neurones (Neural Networks) . . . . . . . . . . . 1.2.2 La logique floue (Fuzzy Logic) . . . . . . . . . . . . . . . . . . 1.2.3 Les techniques de calcul évolutif (Evolutionary Computation) 1.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 8 10 10 12 13 24
2 Application de l’algorithme d’optimisation par essaims particu laires aux problèmes MSAP et PAF 25 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.2 Commande en vitesse des machines synchrones à aimant permanent (MSAP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.2.1 Modélisation d’une machine synchrone à aimant permanent . 27 2.2.2 Conception d’un contrôleur PI basé sur les essaims particulaires 29 2.2.3 Résultats de simulation . . . . . . . . . . . . . . . . . . . . . . 31 2.3 Problème d’affectation de fréquences (PAF) . . . . . . . . . . . . . . 38 2.3.1 Problématique . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.3.2 Formulation du FSFAP . . . . . . . . . . . . . . . . . . . . . 39 2.3.3 Implémentation de l’algorithme d’optimisation par essaims particulaires à la résolution de FSFAP . . . . . . . . . . . . . 40 2.3.4 Etude expérimentale . . . . . . . . . . . . . . . . . . . . . . . 42 2.3.5 Comparaison avec d’autres techniques . . . . . . . . . . . . . . 47 2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
II Conception de nouveaux modèles pour l’optimisation multimodale et l’optimisation multiobjectif 50
3 Conception d’un nouveau modèle d’optimisation multimodale (Mul tipopulation Particle Swarms Optimization MPSO) 52
iii
4
3.1 3.2 3.3
3.4 3.5
3.6
3.7
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Problématique de l’optimisation multimodale . . . . . . . . . . . . . . Techniques de l’optimisation multimodale . . . . . . . . . . . . . . . . 3.3.1 Les méthodes de niche . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Les systèmes basés sur l’intelligence des essaims particulaires (PSO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.3 Les systèmes immunitaires artificiels . . . . . . . . . . . . . . Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Conception d’un nouveau modèle d’optimisation multimodale (MPSO)
3.5.1 Le principe du modèle . . . . . . . . . . . . . . . . . . . . . . 3.5.2 La couche de classification automatique floue . . . . . . . . . . 3.5.3 La couche de séparation spatiale . . . . . . . . . . . . . . . . . 3.5.4 Le concept de migration . . . . . . . . . . . . . . . . . . . . . 3.5.5 Fonctionnement du modèle . . . . . . . . . . . . . . . . . . . . 3.5.6 Complexité temporelle de l’algorithme . . . . . . . . . . . . . Etude expérimentale . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6.1 Fonctions tests . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6.2 Résultats numériques . . . . . . . . . . . . . . . . . . . . . . . 3.6.3 Comparaisons avec d’autres techniques . . . . . . . . . . . . . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53 54 55 55
61 62 63 64 64 64 67 68 68 69 69 70 71 79 82
Conception d’un nouveau modèle pour l’optimisation multiobjectif 83 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 Principe de l’optimisation multiobjectif . . . . . . . . . . . . . . . . . 85 4.2.1 Formulation d’un problème multiobjectif . . . . . . . . . . . . 85 4.2.2 Exemple de problème multiobjectif . . . . . . . . . . . . . . . 86 L’optimisation multiobjectif . . . . . . . . . . . . . . . . . . . . . . . 86 4.3.1 Choix utilisateur . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.3.2 Choix concepteur . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.3.3 Les méthodes agrégées . . . . . . . . . . . . . . . . . . . . . . 88 4.3.4 Les méthodes non agrégées, non Pareto . . . . . . . . . . . . . 90 4.3.5 Les méthodes Pareto . . . . . . . . . . . . . . . . . . . . . . . 92 4.3.6 Les techniques non élitistes . . . . . . . . . . . . . . . . . . . 94 4.3.7 Les techniques élitistes . . . . . . . . . . . . . . . . . . . . . . 96 4.3.8 Difficultés des méthodes d’optimisation multiobjectif . . . . . 99 Optimisation multiobjectif par essaims particulaires . . . . . . . . . 100 4.4.1 Leaders dans l’optimisation multiobjectif . . . . . . . . . . . 102 4.4.2 Conservation et propagation des solutions nondominées . . . 104 4.4.3 Maintien de la diversité par création de nouvelles solutions . . 105 4.4.4 Classification des différentes approches . . . . . . . . . . . . . 107 Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Optimisation multiobjectif par essaims particulaires basée sur la Clas sification Floue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 4.6.1 Implémentation de la couche PSOMO . . . . . . . . . . . . . . 110 4.6.2 Fonctionnement du modèle . . . . . . . . . . . . . . . . . . . . 111 Etude expérimentale . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.1 4.2 4.3 4.4 4.5 4.6 4.7
iv
4.8
4.7.1 Problèmes tests . . . . . . . . . . . . . . . . . . . . . . . . . . 113 4.7.2 Résultats numériques . . . . . . . . . . . . . . . . . . . . . . . 115 4.7.3 Comparaisons avec d’autres techniques . . . . . . . . . . . . . 115 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Conclusion générale
Références Bibliographiques
v
119
122
Introduction
générale
Les ingénieurs et les décideurs sont confrontés quotidiennement à des problèmes de complexité grandissante, relatifs à des secteurs techniques très divers, comme dans la conception de systèmes mécaniques, le traitement des images, l’électronique, les télécommunications, les transports urbains, etc. Généralement, les problèmes à résoudre peuvent souvent s’exprimer sous forme de problèmes d’optimisation. Ces problèmes sont le plus souvent caractérisés en plus de leur complexité, d’exigences qui doivent tenir compte de plusieurs contraintes spécifiques au problème à traiter.
L’optimisation est actuellement un des sujets les plus en vue en " soft computing ". En effet, un grand nombre de problèmes d’aide à la décision peuvent être décrits sous forme de problèmes d’optimisation. Les problèmes d’identification, d’apprentissage supervisé de réseaux de neurones ou encore la recherche du plus court chemin sont, par exemple, des problèmes d’optimisation.
Pour modéliser un problème, on définit une fonction objectif, ou fonction de coût (voire plusieurs), que l’on cherche à minimiser ou à maximiser par rapport à tous les paramètres concernés. La définition d’un problème d’optimisation est souvent complétée par la donnée de contraintes : tous les paramètres des solutions retenues doivent respecter ces contraintes, faute de quoi ces solutions ne sont pas réalisables.
On distingue en réalité deux types de problèmes d’optimisation : les problèmes "discrets" et les problèmes à variables continues. Parmi les problèmes discrets, on trouve le problème d’affectation de fréquences à spectre fixe : il s’agit de trouver des solutions acceptables en minimisant le niveau global d’interférence de fréquences affectées. Un exemple classique de problème continu est celui de la recherche des valeurs à affecter aux paramètres d’un modèle numérique de processus, pour que ce modèle reproduise au mieux le comportement réel observé. En pratique, on rencontre aussi des "problèmes mixtes", qui comportent à la fois des variables discrètes et des variables continues.
Cette différenciation est nécessaire pour cerner le domaine de l’optimisation diffi cile. En effet, deux sortes de problèmes reçoivent, dans la littérature, cette appella tion : – Certains problèmes d’optimisation discrète, pour lesquels on ne connaît pas d’algorithme exact polynomial. C’est le cas, en particulier, des problèmes dits "NPdifficiles".
1
– Certains problèmes d’optimisation à variables continues, pour lesquels on ne connaît pas d’algorithme permettant de repérer un optimum global (c’està dire la meilleure solution possible) à coup sûr et en un nombre fini de calculs.
Des efforts ont longtemps été menés pour résoudre ces deux types de problèmes, dans le domaine de l’optimisation continue, il existe ainsi un arsenal important de méthodes classiques dites d’optimisation globales, mais ces techniques sont souvent inefficaces si la fonction objectif ne possède pas une propriété structurelle particu lière, telle que la convexité. Dans le domaine de l’optimisation discrète, un grand nombre d’heuristiques, qui produisent des solutions proches de l’optimum, ont été développées ; mais la plupart d’entre elles ont été conçues spécifiquement pour un problème donné.
Face à cette difficulté, il en a résulté un besoin d’outils informatiques nouveaux, dont la conception ne pouvait manquer de tirer parti de l’essor des technologies de l’information et du développement des mathématiques de la cognition.
Dans ce contexte, un nouveau thème de recherche dans le domaine des sciences de l’information a été récemment suggéré. Cette voie regroupe des approches possédant des caractéristiques ou des comportements "intelligents". Bien que ces techniques aient été développées indépendamment, elles sont regroupées sous un nouveau thème de recherche baptisé "Techniques de calcul intelligent" (Computational Intelligence). Ce thème, introduit par Bezdek (1994), inclut la logique floue, les réseaux de neu rones artificiels et les méthodes de calcul évolutif. Ces différents champs ont prouvé, durant ces dernières années, leur performance en résistant à l’imperfection et à l’im précision, en offrant une grande rapidité de traitement et en donnant des solutions satisfaisantes, non nécessairement optimales, pour de nombreux processus industriels complexes.
Par ailleurs, les techniques de calcul "intelligent" peuvent être vues comme un ensemble de concepts, de paradigmes et d’algorithmes, permettant d’avoir des ac tions appropriées (comportements "intelligents") pour des environnements variables et complexes.
Selon Fogel, ces nouvelles techniques représentent, de façon générale, des mé thodes, de calculs "intelligents", qui peuvent être utilisées pour adapter les solutions aux nouveaux problèmes et qui ne requièrent pas d’informations explicites. Par la suite, Zadeh a introduit le terme Soft Computing qui désigne également les mêmes techniques [Zadeh, 1994].
Les méthodes de calcul évolutif "Evolutionary Computation" constituent l’un des thèmes majeurs des techniques de calcul "intelligent". Ces méthodes qui s’inspirent de métaphores biologiques (programmation évolutive, stratégie évolutive, program mation génétique, algorithmes génétiques), d’évolution culturelle des populations
2
(algorithmes culturels), ou du comportement collectif des insectes (colonies de four mis, oiseaux migrateurs), etc., sont très utilisées dans le domaine de l’optimisation difficile.
A la différence des méthodes traditionnelles (Hard Computing), qui cherchent des solutions exactes au détriment du temps de calcul nécessaire et qui nécessitent une formulation analytique de la fonction à optimiser, les méthodes de calcul évo lutif permettent l’étude, la modélisation et l’analyse des phénomènes plus ou moins complexes pour lesquels les méthodes classiques ne fournissent pas de bonnes per formances, en termes de coût de calcul et de leur aptitude à fournir des solutions au problème étudié.
Une autre richesse de ces métaheuristiques est qu’elles se prêtent à toutes sortes d’extensions. Citons, en particulier : – L’optimisation multiobjectif [Collette et Siarry, 2002], où il s’agit d’optimiser simultanément plusieurs objectifs contradictoires ; – L’optimisation multimodale, où l’on s’efforce de repérer tout un jeu d’optima globaux ou locaux ; – L’optimisation dynamique, qui fait face à des variations temporelles de la fonction objectif.
Dans ce contexte, les travaux présentés dans ce mémoire présentent dans un pre mier temps l’adaptation de l’une des techniques de calcul évolutif, qui s’inspire du comportement collectif des insectes : l’optimisation par essaims particulaires (Par ticle Swarm Optimization PSO), à l’optimisation de problèmes réels tels que machine synchrone à aimant permanent et le problème d’affectation de fréquences à spectre fixe.
La seconde partie de ce travail sera consacrée à une investigation de l’optimisation multimodale et l’optimisation multiobjectif par essaims particulaires.
Dans cet ordre d’idée, le présent travail propose une nouvelle méthode d’opti misation multimodale par essaims particulaires, le modèle MPSO (Multipopulation Particle Swarms Optimization).
Dans le cadre de l’optimisation multiobjectif, une nouvelle approche, basée sur PSO, la dominance de Pareto et la classification floue, est proposée. Le but principal de cette approche est de surmonter la limitation associée à l’optimisation multiob jectif par essaims particulaires standard. Cette limitation est liée à l’utilisation des archives qui fournit des complexités temporelles et spatiales additionnelles.
3
Les travaux présentés dans ce mémoire sont structurés selon quatre chapitres :
Nous évoquerons dans le premier chapitre un concis rappel sur les différentes tech niques de calcul "intelligent". Un intérêt tout particulier est destiné aux techniques de calcul évolutif qui s’inscrivent dans le cadre de l’optimisation globale.
Le deuxième chapitre illustre la performance de l’algorithme d’optimisation par essaims particulaires dans l’optimisation globale de problèmes réels. Les différentes implémentations effectuées nécessitent une phase d’adaptation de la méthode adop tée ainsi qu’un bon réglage des paramètres. Les problèmes traités dans ce chapitre sont de nature combinatoire, e.g., le problème d’affectation de fréquences dans les réseaux cellulaires, ou des problèmes de prise de décision, e.g., la commande en vitesse des machines synchrones à aimant permanent.
Le troisième chapitre présente, dans un premier temps, l’état de l’art dans le do maine d’optimisation multimodale, et s’intéresse particulièrement aux techniques de niche, basées sur les algorithmes génétiques, les algorithmes culturels et sur les essaims particulaires. Les différentes couches du modèle présenté (MPSO) seront en suite décrites plus en détail. Enfin, les performances du modèle MPSO sont validées sur plusieurs fonctions tests et comparées à d’autres modèles.
Dans le quatrième chapitre nous commencerons par présenter les différentes tech niques d’optimisation multiobjectif proposées dans la littérature. Le modèle proposé FCMOPSO (Fuzzy Clustering Multiobjective Particle Swarm Optimizer) est en suite présenté et décrit en détail. Les performances du modèle seront enfin évaluées sur plusieurs fonctions tests et comparées à d’autres modèles.
4
Première partie
Application de d’optimisation particulaires à des
5
l’algorithme par essaims problèmes réels
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents