WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Contribution à  l'optimisation complexe par des techniques de swarm intelligence

( Télécharger le fichier original )
par Lamia Benameur
Université Mohamed V Agdal Rabat Maroc - Ingénieur spécialité : informatique et télécommunications 0000
  

précédent sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

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 difficile. En effet, deux sortes de problèmes reçoivent, dans la littérature, cette appellation :

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".

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 particuliè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 neurones 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'impré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 actions 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, programmation génétique, algorithmes génétiques), d'évolution culturelle des populations

(algorithmes culturels), ou du comportement collectif des insectes (colonies de fourmis, 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 évolutif 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 performances, 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], oil il s'agit d'optimiser simultanément plusieurs objectifs contradictoires;

- L'optimisation multimodale, oil 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 premier temps l'adaptation de l'une des techniques de calcul évolutif, qui s'inspire du comportement collectif des insectes : l'optimisation par essaims particulaires (Particle 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'optimisation 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 multiobjectif par essaims particulaires standard. Cette limitation est liée à l'utilisation des archives qui fournit des complexités temporelles et spatiales additionnelles.

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 techniques 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 adopté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 domaine 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 techniques 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.

précédent sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy