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.
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
AvantPropos
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
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 "NPdifficiles".
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é FCMOPSO (Fuzzy Clustering Multiobjective 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.