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