La résolution efficace de problèmes d'optimisation à permutation de grande taille nécessite le développement de méthodes hybrides complexes combinant différentes classes d'algorithmes d'optimisation. L'hybridation des métaheuristiques avec les méthodes exactes arborescentes, tel que l'algorithme du branch-and-bound (B&B), engendre une nouvelle classe d'algorithmes plus efficace que ces deux classes de méthodes utilisées séparément. Le défi principal dans le développement de telles méthodes consiste à trouver des liens ou connections entre les stratégies de recherche divergentes utilisés dans les deux classes de méthodes. Les Algorithmes Génétiques (AGs) sont des métaheuristiques, à base de population, très populaires basés sur des opérateurs stochastiques inspirés de la théorie de l'évolution. Contrairement aux AGs et aux métaheuristiques généralement, les algorithmes de B&B sont basés sur l'énumération implicite de l'espace de recherche représenté par le moyen d'un arbre, dit arbre de recherche. Notre approche d'hybridation consiste à définir un codage commun des solutions et de l'espace de recherche ainsi que des opérateurs de recherche adéquats afin de permettre un couplage efficace de bas niveau entre les deux classes de méthodes AGs et B&B. La représentation de l'espace de recherche par le moyen d'arbres est traditionnellement utilisée dans les algorithmes de B&B. Dans cette thèse, cette représentation a été adaptée aux métaheuristiques. L'encodage des permutations au moyen de nombres naturels faisant référence à l'ordre d'énumération lexicographique des permutations dans l'arbre du B&B, est proposé comme une nouvelle manière de représenter l'espace de recherche des problèmes à permutations dans les métaheuristiques. Cette méthode de codage est basée sur les propriétés mathématiques des permutations, à savoir les codes de Lehmer et les tables d'inversions ainsi que les système d'énumération factoriels. Des fonctions de transformation permettant le passage entre les deux représentations (permutations et nombres) ainsi que des opérateurs de recherche adaptés au codage, sont définis pour les problèmes à permutations généralisés. Cette représentation, désormais commune aux métaheuristiques et aux algorithmes de B&B, nous a permis de concevoir des stratégies d'hybridation et de collaboration efficaces entre les AGs et le B&B. En effet, deux approches d'hybridation entre les AGs et les algorithmes de B&B (HGABB et COBBIGA) basés sur cette représentation commune ont été proposées dans cette thèse. Pour validation, une implémentation a été réalisée pour le problème d'affectation quadratique à trois dimension (Q3AP). Afin de résoudre de larges instances de ce problème, nous avons aussi proposé une parallélisation pour les deux algorithmes hybrides, basée sur des techniques de décomposition d'espace (décomposition par intervalle) utilisées auparavant pour la parallélisation des algorithmes de B&B. Du point de vue implémentation, afin de faciliter de futurs conceptions et implémentations de méthodes hybrides combinant métaheuristiques et méthodes exacte arborescentes, nous avons développé une plateforme d'hybridation intégrée au logiciel pour métaheuristiques, ParadisEO. La nouvelle plateforme a été utilisée pour réaliser des expérimentations intensives sur la grille de calcul Grid'5000. / Solving efficiently large benchmarks of NP-hard permutation-based problems requires the development of hybrid methods combining different classes of optimization methods. Indeed, it is now acknowledged that such methods perform better than traditional optimization methods when used separately. The key challenge is how to find connections between the divergent search strategies used in each class of methods in order to build efficient hybridization strategies. Genetic algorithms (GAs) are very popular population-based metaheuristics based on stochastic evolutionary operators. The hybridization of GAs with tree-based exact methods such as Branch-and-Bound is a promising research trend. B&B algorithms are based on an implicit enumeration of the solution space represented as a tree. Our hybridization approach consists in providing a common solution and search space coding and associated search operators enabling an efficient cooperation between the two methods. The tree-based representation of the solution space is traditionally used in B&B algorithms to enumerate the solutions of the problem at hand. In this thesis, this special representation is adapted to metaheuristics. The encoding of permutations as natural numbers, which refer to their lexicographic enumeration in the tree, is proposed as a new way to represent the solution space of permutation problems in metaheuristics. This encoding approach is based on the mathematical properties of permutations (Lehmer codes, inversion tables, etc.). Mapping functions between the two representations (permutations and numbers) and special search operators adapted to the encoding are defined for general permutation problems, with respect to the theory of representation. This common representation allows the design of efficient cooperation strategies between GAs and B\&B algorithms. In this thesis, two hybridization schemes combining GAs with B\&B based on this common representation are proposed. The two hybridization approaches HGABB/HAGABB (Hybrid Adaptive GA-B\&B) and COBBIGA (cooperative B&B interval-based GA), have been validated on standard benchmarks of one of the hardest permutation-based problems, the three dimensional quadratic assignment problem (Q3AP). In order to solve large benchmarks of permutation-based problems, a parallelization for computational grids is also proposed for the two hybrid schemes. This parallelization is based on space decomposition techniques (the decomposition by intervals) used in parallel B\&B algorithms. From the implementation point of view, in order to facilitate further design and implementation of hybrid methods combining metaheuristics with tree-based exact methods, a hybridization C++ framework integrated to the framework for metaheuristics ParadisEO is developed. The new framework is used to conduct extensive experiments over the computational grid Grid'5000.

Proefschrift--Nederlandsche Economische Hoogeschool, Rotterdam. / "Stellingen": [4] p. inserted.

Proefschrift--Nederlandsche Economische Hoogeschool, Rotterdam. / "Stellingen": [4] p. inserted.

Cette thèse est divisée en trois chapitres distincts, ayant comme dénominateur commun l'analyse stochastique de certains champs gaussiens. Les processus stochastiques multiparamétriques qui apparaissent dans ce manuscrit sont généralement auto-similaires. L'auto-similarité est la propriété qu’un processus stochastique préserve sa loi après un changement d'échelle du temps. Dans une première partie, nous avons mis en évidence des nouveaux aspects du drap brownien fractionnaire en utilisant essentiellement la notion de la transformation de Lamperti. Un focus sur l'équation différentielle stochastique vérifiée par cette transformée, a été aussi évoqué. Dans une deuxième partie, nous avons analysé le comportement asymptotique en loi des variations quadratiques spatiales des processus qui sont des solutions de deux types d'équations différentielles stochastiques partielles des ondes perturbées par deux sortes des bruits gaussiens auto-similaires. L'outil principal de notre raisonnement était des nouveaux critères basés sur le calcul stochastique de Malliavin et combinés avec la méthode classique de Stein. En guise d'application, nous avons construit un estimateur de l'indice de Hurst H du bruit fractionnaire en se basant sur les variations quadratiques étudiées. / This thesis is divided into three distinct chapters with a common denominator which is the stochastic analysis of some Gaussian fields. The multi-parameter stochastic processes that appeared in this manuscript are generally self-similar. Self-similarity is the property that a stochastic process preserves its law after a scaling of time. Firstly, we deduced new aspects of the fractional Brownian sheet, using essentially the notion of the Lamperti transform. A Focus on the stochastic differential equation verified by this transform sheet was also mentioned. Secondly, we analyzed the asymptoticbehavior of the spatial quadratic variations of processes that are solutions of two types of stochastic wave equations perturbed by two kinds of self-similar Gaussian noises. The main tool in our reasoning was new criteria based on the Malliavin calculus and combined with the classical method of Stein. As an application, we constructed, by the aid of the quadratic variations, an estimator of the Hurst index H of the fractional noise.

La L-théorie classique d'un anneau commutatif est construite à partir des formes quadratiques sur cet anneau modulo une relation d'équivalence lagrangienne. Nous construisons la L-théorie dérivée, à partir des formes quadratiques $n$-décalées sur un anneau commutatif dérivé. Nous montrons que les formes $n$-décalées qui admettent un lagrangien possèdent une forme standard. Nous montrons des résultats de chirurgie pour la L-théorie dérivée, qui permettent de réduire une forme quadratique décalée en une forme plus simple équivalente. On compare la L-théorie dérivée avec la L-théorie classique.On définit un champ dérivé des formes quadratiques dérivées, et un champ dérivé des lagrangiens dans une forme, qui sont localement algébriques de présentation finie. On calcule les complexes tangents, et on trouve des points lisses. On montre un résultat de rigidité pour la L-théorie : la L-théorie d'un anneau commutatif est isomorphe à celle d'un voisinage hensélien de cet anneau. Enfin, on définit l'algèbre de Clifford d'une forme quadratique n-décalée, qui est une déformation d'une algèbre symétrique en tant qu'E_k-algèbre. On montre un affaiblissement de la propriété d'Azumaya pour ces algèbres, dans le cas d'un décalage nul n=0, qu'on appelle semi-Azumaya. Cette propriété exprime la trivialité de l'homologie de Hochschild du bimodule de Serre. / The classical L-theory of a commutative ring is built from the quadratic forms over this ring modulo a lagrangian equivalence relation.We build the derived L-theory from the n-shifted quadratic forms on a derived commutative ring. We show that forms which admit a lagrangian have a standard form. We prove surgery results for this derived L-theory, which allows to reduce shifted quadratic forms to equivalent simpler forms. We compare classical and derived L-theory.We define a derived stack of shifted quadratic forms and a derived stack of lagrangians in a form, which are locally algebraic of finite presentation. We compute tangent complexes and find smooth points. We prove a rigidity result for L-theory : the L-theory of a commutative ring is isomorphic to that of any henselian neighbourhood of this ring.Finally, we define the Clifford algebra of a n-shifted quadratic form, which is a deformation as E_k-algebra of a symmetric algebra. We prove a weakening of the Azumaya property for these algebras, in the case n=0, which we call semi-Azumaya. This property expresses the triviality of the Hochschild homology of the Serre bimodule.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Cette thèse concerne l'analyse de la stabilité et la synthèse de lois de commande pour les multimodèles. La démarche proposée est exclusivement basée sur la deuxième méthode de Lyapunov et sa formulation en termes d'Inégalités Matricielles Linéaires (LMI). L'étude que nous avons menée est organisée autour de deux axes : le premier traite l'analyse de la stabilité par des fonctions de Lyapunov quadratiques, le deuxième fait appel aux fonctions de Lyapunov non quadratiques. Dans le volet consacré à la méthode quadratique, nous avons développé des conditions suffisantes de stabilité en nous appuyant sur les propriétés des M-matrices. La conception de multiobservateurs dans le cas de variables de décision non mesurables est abordée ainsi que celle de multiobservateurs à entrées inconnues. Une loi de commande statique non linéaire basée sur le retour de sortie est également proposée. Deux techniques de synthèse de cette loi de commande sont exposées. La première est basée sur une formulation convexe sous forme de LMI. La deuxième technique, quant à elle, est basée sur la transformation du problème (non convexe) de synthèse en un problème de complémentarité sur le cône. Pour réduire le pessimisme de la méthode quadratique, deux types de fonction de Lyapunov non quadratiques sont considérées : les fonctions dites polyquadratiques et les fonctions quadratiques par morceaux. En utilisant la procédure S, les conditions de stabilité obtenues sont formulées sous forme de LMI. Ces résultats ont abouti à réduire considérablement le conservatisme de la méthode quadratique et permettent d'envisager des extensions intéressantes concernant la commande par retour d'état ou de sortie ainsi que l'estimation d'état des multimodèles. Les conditions obtenues étant bilinéaires par rapport aux variables de synthèse, elles sont résolues en utilisant des algorithmes de linéarisation ou à l'aide de formulation LMI sous contrainte de rang.

Cette thèse aborde le problème de l'analyse de la stabilité et de la conception des lois de commande pour les systèmes non linéaires mis sous la forme de modèles flous continus de type Takagi-Sugeno. L'analyse de stabilité est généralement basée sur la méthode directe de Lyapunov. Plusieurs approches existent dans la littérature, basées sur des fonctions de Lyapunov quadratiques sont proposées pour résoudre ce problème, les résultats obtenus à l'aide des telles fonctions introduisent un conservatisme qui peut être très préjudiciable. Pour surmonter ce problème, différentes approches basées sur des fonctions de Lyapunov non quadratiques ont été proposées, néanmoins ces approches sont basées sur desconditions très restrictives. L'idée développée dans ce travail est d'utiliser des fonctions de Lyapunov non quadratiques et des contrôleurs non-PDC afin d'en tirer des conditions de stabilité et de stabilisation moins conservatives. Les propositions principales sont : l'utilisation des bornes locales des dérivées partielles au lieu des dérivés des fonctions d'appartenances, le découplage du gain du régulateur des variables de décision de la fonction Lyapunov, l'utilisation des fonctions de Lyapunov floues polynomiales dans l'environnement des polynômes et la proposition de la synthèse de contrôleur vérifiant certaines limites de dérivés respectées dans une région de la modélisation à la place de les vérifier a posteriori. Ces nouvelles approches permettent de proposer des conditions locales afin de stabiliser les modèles flous continus de type T-S, y compris ceux qui n'admettent pas une stabilisation quadratique et obtenir des domaines de stabilité plus grand. Plusieurs exemples de simulation sont choisis afin de vérifier les résultats présentésdans cette thèse.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Ce travail est essentiellement centré sur l'estimation, du point de vue de la théorie de la décision, de la moyenne d'une distribution multidimensionnelle à symétrie sphérique. Sous coût quadratique, nous nous sommes concentrés à développer des classes d'estimateurs au moins aussi bons que les estimateurs usuels, puisque ces derniers tendent à perdre leur performance en dimension élevée et en présence de contraintes sur les paramètres. Dans un premier temps, nous avons considéré les distributions de mélange (par rapport à [sigma][indice supérieur 2]) de lois normales multidimensionnelles N ([théta], [sigma][indice supérieur 2]I[indice inférieur p]), en dimension p supérieure ou égale à 3. Nous avons trouvé une grande classe de lois a priori (généralisées), aussi dans la classe des distributions de mélange de lois normales, qui génèrent des estimateurs de Bayes minimax. Ensuite, pour étendre nos résultats, nous avons considéré les distributions à symétrie sphérique (pas nécessairement mélange de lois normales) avec paramètre d'échelle connu, en dimension supérieure ou égale à 3 et en présence d'un vecteur résiduel. Nous avons obtenu une classe d'estimateurs de Bayes généralisés minimax pour une grande classe de distributions sphériques incluant certaines distributions mélange de lois normales. Dans l'estimation de la moyenne [théta] d'une loi N[indice inférieur p]([théta], I[indice inférieur p]) sous la contrainte [double barre verticale][théta][double barre verticale] [inférieur ou égal] m avec m > 0, une analyse en dimension finie pour comparer les estimateurs linéaires tronqués [delta][indice inférieur a] (0 [plus petit ou égal] a < 1) avec l'estimateur du maximum de vraisemblance [delta][indice inférieur emv] est donnée. Un cadre asymptotique est développé, ceci nous permet de déduire la sous-classe des estimateurs [delta][indice inférieur a] qui dominent [delta][indice inférieur emv] et de mesurer avec précision le degré d'amélioration relative en risque. Enfin, dans l'estimation de la moyenne [théta] d'une loi N[indice inférieur p]([théta], [sigma][indice supérieur 2]I[indice inférieur p]) où [sigma] est inconnu et sous la contrainte [Special characters omitted.] [plus petit ou égal] m avec m > 0, des résultats de dominance de l'estimateur X et de l'estimateur du maximum de vraisemblance [delta][indice inférieur emv] sont développés. En particulier, nous avons montré que le meilleur estimateur équivariant [delta][indice inférieur m] (x , s) = h[indice inférieur m] ([Special characters omitted.]) x pour = [Special characters omitted.] = m domine [delta][indice inférieur emv] lorsque m [plus petit ou égal] [racine carrée]p et que sa troncature [delta][Special characters omitted.] domine [delta][indice inférieur emv] pour tout (m , p).