Ce travail présente nos principales contributions à la résolution de problèmes d'optimisation combinatoire en environnements déterministe et stochastique. Au niveau des métaheuristiques, une vue unifiée de la conception de métaheuristiques à solution unique et de métaheuristiques multi-objective est proposée. Cette unification a permis notamment de retravailler la plateforme ParadisEO afin d'offrir plus de flexibilité et de polyvalence. La synthèse des travaux présente également une vue unifiée des métaheuristiques coopératives. Nous montrons que cette vue convient aussi bien pour des coopérations entre métaheuristiques que des coopération entre des métaheuristiques et des méthodes exactes mais également des coopérations entre des métaheuristiques et des algorithmes d'extraction de connaissances. Différents exemples de coopérations réalisées dans mes travaux de recherche illustent ces coopérations et leur application à des problèmes d'optimisation combinatoire mono- et multi-objectif. Cette habilitation se termine par la présentation de travaux réalisés en optimisation stochastique notamment dans le cadre de l'optimisation sous incertitude et de l'optimisation dynamique. L'importance des critères de robustesse est discutée ainsi que l'intérêt et la mise en œuvre de méthodes coopératives dans un contexte dynamique. Les principales applications présentées on été réalisées sur des problèmes en transport et logistique ainsi qu'en biologie dans le cadre de l'ANR Dock.

L'utilisation d'un framework pose des problèmes liés au respect de la structure et du comportement de celui-ci. Ces problèmes sont la conséquence de la perte des informations de conception lors de l'implémentation, ce qui se traduit par l'absence d'une documentation pertinente lors de l'utilisation. Ainsi le but de cette thèse est de fournir un modèle d'expression des dépendances structurelles et comportementales. Ces modèles sont intégrés au cycle de vie du framework, de la spécification jusqu'à la finalisation. Le modèle de dépendances structurelles propose une expression explicite des dépendances grâce à une réification partielle du framework. Ce modèle, indépendant de tout langage permet au développeur du framework aussi bien qu'à un utilisateur, de consulter les dépendances entre les éléments du framework, et de bénéficier d'une aide dynamique ainsi que d'un système de vérification. Le modèle de dépendances comportementales étend l'interface statique des classespar une spécification dynamique (protocole) de celles-ci. Cette spécification définit les séquences valides d'enchaînement de messages entrant et sortant de la classe. Cette spécification, basée sur le modèle formel d'Esterel, permet des vérifications statiques et dynamiques.

Ce travail concerne la modélisation du processus de synthèse (construction) de supports de catalyseurs obtenus par réaction silice-alumine. La synthèse est caractérisée par 5 variables d'entrée et 2 variables de sortie (la surface spécifique et le volume mesoporeux du support de catalyseur). Chaque combinaison des valeurs de sortie ayant une application potentielle, on voudrait savoir en synthétiser le plus grand nombre, c'est-a-dire connaitre les variables d'entrée permettant de construire un catalyseur ayant une surface et un volume donnes quelconques. Les limites atteignables des deux sorties du système sont inconnues. Ne disposant pas de suffisamment d'essais pour pouvoir espérer construire un modèle fiable sur l'ensemble du domaine de variation des variables d'entrée, nous choisissons une approche par plans d'expérience séquentiels avec modélisation par krigeage, permettant d'éviter une trop grande dispersion des variables d'entrée tout en assurant une exploration du domaine accessible pour les variables de sortie. Les essais sont choisis séquentiellement en se servant de l'information apportée par les essais précédents et traitée par le modèle de krigeage. Cette façon de procéder est a priori plus efficace que celle consistant a utiliser un plan d'expériences fixe au départ et comprenant la totalité des essais disponibles. Des critères d'ajout séquentiel de points d'expérimentation (définissant les valeurs des variables d'entrée) sont proposes, qui favorisent une forte dispersion des sorties correspondantes et prennent en compte les incertitudes associées aux prédictions par krigeage. Enfin, les critères retenus, l'un à base de distance et l'autre à base d'entropie, sont testes sur des données simulées afin de vérifier la bonne répartition finale des valeurs des réponses. Des rappels sur la modélisation par processus gaussien, la régression/interpolation par krigeage et ses liens avec les méthodes de type splines et SVM, ainsi que la planification d'expériences sont présentes en essayant de concilier rigueur et clarté.

La recherche de la solution optimale d'un problème combinatoire est souvent très longue puisque, d'une manière générale, le temps de résolution est une fonction exponentielle de la taille de ce problème. Dès l'instant où on se place dans un contexte temps réel, c'est-à-dire chaque fois qu'on impose une limite au temps de calcul alloué, les algorithmes d'optimisation classique s'avèrent, à quelques rares exceptions près , impuissants, et on doit se contenter d'utiliser des méthodes heuristiques. La présente étude porte sur l'évaluation de celles qui sont susceptibles d'apporter une réponse satisfaisante à certains problèmes d'ordonnancement. Trois types d'approches sont étudiées : - les heuristiques non convergentes, - les heuristiques convergentes, - les méthodes d'apprentissage. L'évaluation de leurs performances est réalisée sur le double critère de la qualité de la solution et du temps de calcul nécessaire à leur mise en œuvre.

.

.

Cette thèse présente principalement des résultats sur la combinatoire des droites et segments qui apparaissent naturellement dans l'étude des problèmes de visibilité en trois dimensions. Nous exposons en premier lieu des résultats sur la taille de la silhouette d'un objet vu d'un point, c'est à dire sur la complexite de l'ensemble des droites ou segments tangents à l'objet et passant par le point. Nous présentons en particulier les premières bornes théoriques non triviales pour des polyèdres non-convexes, à savoir que, sous des hypothèses raisonnables, la complexité moyenne de la silhouette est au plus la racine carrée de la complexité du polyèdre, phénomène largement observé en infographie. Nous présentons aussi des bornes, en moyenne et dans le cas le pire, sur le nombre de droites et segments tangents à quatre objets dans une scène composée d'objets polyédriques ou sphériques. Ces bornes donnent en particulier l'espoir que la complexité des structures de données globales comme le complexe de visibilité ne soit pas nécessairement prohibitive. Les bornes sur les polytopes sont également les premières à tirer parti des propriétés structurelles des scènes composées de triangles organisés en polytopes de facon réaliste, c'est à dire non nécessairement disjoints. Ces bornes induisent enfin les premières bornes non triviales sur la complexité des ombres induites par des sources lumineuses non ponctuelles. Les résultats presentés dans cette thèse améliorent significativement l'état de l'art sur les propriétés combinatoires des structures de visibilité en trois dimensions et devraient favoriser les développements algorithmiques futurs pour ces problèmes.

Cette th`ese se concentre sur des bases th´eoriques utiles pour l'analyse d'algorithmes et de protocoles<br />pour des syst`emes r´epartis modernes. Deux caract´eristiques importantes des mod`eles pour<br />ces syst`emes sont les probabilit´es et la mobilit´e typ´ee : des probabilit´es peuvent ˆetre utilis´ees pour<br />quantifier des comportements incertains ou impr´evisibles, et des types peuvent ˆetre utilis´es pour<br />garantir des comportements sˆurs dans des syst`emes mobiles. Dans cette th`ese nous d´eveloppons<br />des techniques alg´ebriques et des techniques bas´ees sur les types pour l'´etude comportementale des<br />processus probabilistes et mobiles.<br /><br />Dans la premi`ere partie de la th`ese nous ´etudions la th´eorie alg´ebrique d'un calcul de processus<br />qui combine les comportements non-d´eterministe et probabiliste dans le mod`ele des automates probabilistes<br />propos´es par Segala et Lynch. Nous consid´erons diverses ´equivalences comportementales<br />fortes et faibles, et nous fournissons des axiomatisations compl`etes pour des processus `a ´etats finis,<br />limit´ees `a la r´ecursion gard´ee dans le cas des ´equivalences faibles.<br /><br />Dans la deuxi`eme partie de la th`ese nous ´etudions la th´eorie alg´ebrique du -calcul en pr´esence<br />des types de capacit´es, qui sont tr`es utiles dans les calculs de processus mobiles. Les types de<br />capacit´es distinguent la capacit´e de lire sur un canal, la capacit´e d'´ecrire sur un canal, et la capacit´e<br />de lire et d'´ecrire `a la fois. Ils introduisent ´egalement une relation de sous-typage naturelle et<br />puissante. Nous consid´erons deux variantes de la bisimilarit´e typ´ee, dans leurs versions retard´ees<br />et anticip´ees. Pour les deux variantes, nous donnons des axiomatisations compl`etes pour les termes<br />ferm´es. Pour une des deux variantes, nous fournissons une axiomatisation compl`ete pour tous les<br />termes finis.<br /><br />Dans la derni`ere partie de la th`ese nous d´eveloppons des techniques bas´ees sur les types pour<br />v´erifier la propri´et´e de terminaison de certains processus mobiles. Nous fournissons quatre syst`emes<br />de types pour garantir cette propri´et´e. Les syst`emes de types sont obtenus par des am´eliorations<br />successives des types du -calcul simplement typ´e. Les preuves de terminaison utilisent des techniques<br />employ´ees dans les syst`emes de r´e´ecriture. Ces syst`emes de types peuvent ˆetre utilis´es pour<br />raisonner sur le comportement de terminaison de quelques exemples non triviaux : les codages des<br />fonctions r´ecursives primitives, le protocole pour coder le choix s´epar´e en terme de composition<br />parall`ele, une table de symboles implement´ee comme une chaˆıne dynamique de cellules.<br /><br />Ces r´esultats ´etablissent des bases pour une future ´etude de mod`eles plus avanc´es qui peuvent<br />combiner des probabilit´es avec des types. Ils soulignent ´egalement la robustesse des techniques<br />alg´ebriques et de celles bas´ees sur les types pour le raisonnement comportemental.

Cette thèse s'articule autour du problème de la synchronisation d'une ligne d'automates. Elle propose une solution économe en nombre d'états en utilisant le schéma de Minsky: temps de synchronisation 3n et nombre d'états 7. Elle s'attache aussi à décrire le comportement de certains automates particuliers découverts lors de la quête automatisée de solutions minimales.

The source system is the real or virtual environment that we are interested in modeling. It is viewed as a source of observable data, in the form of time-indexed trajectories of variables. The data that has been gathered from observing or experimenting with a system is called the system behavior data base. The time indexed trajectories of variables provide an important clue to compose the DEVS (discrete event specification) model. Once event set is derived from the time indexed trajectories of variable, the DEVS model formalism can be extracted from the given event set. The process must not be a simple model generation but a meaningful model structuring of a request. The source data and query designed with SES are converted to XML Meta data by XML converting process. The SES serves as a compact representation for organizing all possible hierarchical composition of system so that it performs an important role to design the structural representation of query and source data to be saved. For the real data application, the model structuring with the US Climate Normals is introduced. Moreover, complex systems are able to be developed at different levels of resolution. When the huge size of source data in US Climate Normals are implemented for the DEVS model, the model complexity is unavoidable. This issue is dealt with the creation of the equivalent lumped model based on the concept of morphism. Two methods to define the resolution level are discussed, fixed and dynamic definition. Aggregation is also discussed as the one of approaches for the model abstraction. Finally, this paper will introduce the process to integrate the DEVSML(DEVS Modeling Language) engine with the DEVS model creation engine for the Web Service Oriented Architecture.