Dans le cadre de l'optimisation multiobjectif, les métaheuristiques sont reconnues pour être des méthodes performantes mais elles ne rencontrent qu'un succès modéré dans le monde de l'industrie. Dans un milieu où seule la performance compte, l'aspect stochastique des métaheuristiques semble encore être un obstacle difficile à franchir pour les décisionnaires. Il est donc important que les chercheurs de la communauté portent un effort tout particulier sur la facilité de prise en main des algorithmes. Plus les algorithmes seront faciles d'accès pour les utilisateurs novices, plus l'utilisation de ceux-ci pourra se répandre. Parmi les améliorations possibles, la réduction du nombre de paramètres des algorithmes apparaît comme un enjeu majeur. En effet, les métaheuristiques sont fortement dépendantes de leur jeu de paramètres. Dans ce cadre se situe l'apport majeur de TRIBES, un algorithme mono-objectif d'Optimisation par Essaim Particulaire (OEP) qui fonctionne automatiquement,sans paramètres. Il a été mis au point par Maurice Clerc. En fait, le fonctionnement de l'OEP nécessite la manipulation de plusieurs paramètres. De ce fait, TRIBES évite l'effort de les régler (taille de l'essaim, vitesse maximale, facteur d'inertie, etc.).Nous proposons dans cette thèse une adaptation de TRIBES à l'optimisation multiobjectif. L'objectif est d'obtenir un algorithme d'optimisation par essaim particulaire multiobjectif sans paramètres de contrôle. Nous reprenons les principaux mécanismes de TRIBES auxquels sont ajoutés de nouveaux mécanismes destinés à traiter des problèmes multiobjectif. Après les expérimentations, nous avons constaté, que TRIBES-Multiobjectif est moins compétitif par rapport aux algorithmes de référence dans la littérature. Ceci peut être expliqué par la stagnation prématurée de l'essaim. Pour remédier à ces problèmes, nous avons proposé l'hybridation entre TRIBES-Multiobjectif et un algorithme de recherche locale, à savoir le recuit simulé et la recherche tabou. L'idée était d'améliorer la capacité d'exploitation deTRIBES-Multiobjectif. Nos algorithmes ont été finalement appliqués sur des problèmes de dimensionnement des transistors dans les circuits analogiques

Le développement des techniques d'intégration permet de réaliser des circuits de 10**(5) a 10**(6) transistors et, dans un futur proche, des circuits encore plus complexes. Les problèmes de CAO deviennent donc de plus en plus ardus, comme la simulation logique ou le placement. Cette même évolution nous autorise a réaliser des machines parallèles très puissantes pour résoudre ces problèmes. Nous proposons l'architecture d'un réseau cellulaire asynchrone. Ce réseau, compose de nxn cellules dont chacune est physiquement connectée à ses quatre voisines, dispose d'un mécanisme de communication permettant l'acheminement de messages d'une cellule quelconque a n'importe quelle autre. Un circuit intégré, incluant un réseau de 2 x 2 cellules dédié à la simulation logique, a été réalisé. Utilisant cette architecture cellulaire nous avons développé un placeur, qui a partir d'une configuration initiale, minimise la longueur des connexions par échanges de paires. Nous avons aborde la manière dont le placement pourrait être amélioré par la méthode de recuit simule. Ces deux applications, différentes de l'architecture cellulaire, nous permettent de constater que beaucoup de parties sont communes aux deux circuits. Nous énonçons certaines règles de façon à rendre la conception plus rapide et plus sure

Nos travaux concernent la mise en œuvre de méthodologies pour la résolution de problèmes d'ordonnancement en industries agroalimentaires. Trois nouvelles approches basées sur les algorithmes génétiques, sont proposées pour la résolution de problèmes d'ordonnancement multi-objectifs : les algorithmes génétiques séquentiels (SGA), les algorithmes génétiques parallèles (PGA) et les algorithmes génétiques parallèles séquentiels (PSGA). Deux approches coopératives multi-objectifs en mode relais, SH_GA/TS et SH_GA/SA, hybridant toutes les deux des métaheuristiques de haut niveau, sont par la suite proposées. Un algorithme évolutionnaire et un algorithme de recherche locale sont, dans ce cas exécutés séquentiellement.

Les recherches menées dans le cadre de mon doctorat concernent le domaine de la Traduction Automatique (TA), ou comment traduire d'une langue source vers une langue cible sans aucune intervention humaine. Mes travaux se sont plus particulièrement concentrés sur l'approche statistique de la TA qui consiste à utiliser différents modèles probabilistes appris sur des quantités importantes de corpus parallèles alignés afin de trouver la traduction la plus vraisemblable d'une phrase source. Deux problèmes étroitement liés à l'approche statistique de la TA sont abordés dans ce manuscrit : la collecte de corpus parallèles et l'estimation de modèles de traduction à partir de ces corpus. Un système de TA statistique extrait la connaissance dont il a besoin pour produire des traductions à partir de corpus parallèles dans lesquels chaque phrase source est associée à sa traduction dans la langue cible. De nombreux travaux utilisent comme corpus parallèle les actes du Parlement Européen disponibles gratuitement en différentes langues. De tels corpus ne sont pas adéquats pour la traduction de parole spontanée, c'est pourquoi j'ai décidé de construire des corpus parallèles à partir de sous-titres de films afin de construire un système de traduction plus réaliste. Les sous-titres sont des données complexes, ils ne peuvent constituer un corpus parallèle aligné dans leur état brut. Ils nécessitent une phase de pré-traitement et d'alignement. J'ai pour cela proposé une méthode originale basée sur la Programmation Dynamique qui aligne automatiquement les sous-titres. J'ai ainsi constitué une ressource importante et riche pour l'apprentissage des systèmes de TA statistique. La TA statistique repose sur l'utilisation de plusieurs modèles statistiques comme le modèle d'alignement, la table de traduction ou encore le modèle de distortion. La table de traduction est le modèle le plus indispensable à un système de TA statisque pour calculer la traduction la plus vraisemblable d'une phrase source. En effet, celle-ci donne les probabilités de traduction entre les couples de mots sources et cibles. Il existe différentes méthodes permettant l'estimation de ces tables de traduction. Elles ont habituellement recours à un alignement des mots obtenu automatiquement sur les corpus parallèles. Cette tâche d'alignement est une étape longue et fastidieuse qui fait appel à des algorithmes complexes. Le coeur de mon travail a été de repenser le problème et d'explorer de nouvelles pistes pour estimer les tables de traduction de mots et de séquences de mots, totalement différentes des méthodes état-de-l'art. J'ai proposé une approche originale basée sur le concept de triggers inter-langues qui ne nécessite aucun alignement des mots au sein des corpus parallèles. Les triggers inter-langues permettent de mettre en évidence des unités fortement corrélés en se basant sur l'Information Mutuelle. Dans notre cas les unités sont des séquences de mots sources et cibles. L'idée derrière ce concept est que si une séquence de mots sources est fortement corrélée à une séquence de mots cibles en termes d'IM, alors nous pouvons supposer que la présence de la première dans une phrase source déclenchera la présence de la seconde dans sa traduction et vice versa. J'ai proposé d'utiliser les triggers inter-langues sur les corpus parallèles dans le but de trouver les traductions possibles de séquences de mots et ainsi constituer une table de traduction. L'Information Mutuelle est une mesure de co-occurence qui se calcule simplement en un seul passage sur le corpus parallèle. Pour sélectionner les triggers interlangues, nous supposons que deux séquences sources et cibles co-occurent si elles apparaissent dans une même paire de phrases du corpus parallèle. De ce fait, ma méthode ne requiert qu'un alignement au niveau des phrases et non au niveau des mots au sein du corpus parallèle. L'utilisation des triggers inter-langues pour estimer une table de traduction rend mon approche moins complexe mais tout aussi efficace que les approches existantes. Dans un contexte de traduction mot-à-mot, la table de traduction obtenue grâce aux triggers inter-langues conduit à des traductions automatiques de meilleur qualité, en termes de score BLEU, que celles produites avec une table de traduction de mots estimée selon le modèle 3 d'IBM. Dans un contexte de traduction par groupe de mots, la table de traduction basée sur les triggers inter-langues amènent à des traductions automatiques dont le score BLEU est supérieur à 34 et proche de celui des traductions automatiques produites par une table de traduction de séquences estimées à partir de l'alignement des mots suivant les approches état-de-l'art. Mots-clés: Traduction Automatique Statistique, Triggers Inter-langues, Traduction Automatique à base de séquences

Dans ce mémoire de thèse, nous nous intéressons à l'affectation des vols aux avions dans une compagnie aérienne. Notre objectif est de proposer des plannings de vols qui prennent en compte des contraintes de maintenance, en utilisant des algorithmes efficaces. Au cours de nos recherches, nous avons ramené le problème de rotation des avions à des cas particuliers du problème de partitionnement d'un graphe orienté acyclique par des chemins disjoints. Nous avons fait des études de complexité pour différents cas et nous avons proposé des algorithmes de liste, un recuit simulé et une approche heuristique basée sur la génération de colonnes. Nous avons finalement comparé la performance de ces méthodes sur différentes instances.

La technique de paramétrisation est très prometteuse pour la conception radio logicielle. La radio logicielle consiste à concevoir des systèmes multi-standards qui tirent bénéfice des possibilités de programmation ou de reconfiguration offertes par les composants de traitement la constituant. Cette thèse étudie la technique de paramétrisation par opérateurs communs. Les opérateurs communs sont des unités de traitements communes à plusieurs opérations qu'effectue un équipement, quelle que soit la couche du modèle OSI à laquelle elles appartiennent. La méthode proposée repose sur une approche théorique afin de résoudre le problème de conception d'un équipement multi-standards. Elle consiste en une optimisation d'un hypergraphe. La conception de l'équipement est représentée par des opérateurs à différents niveaux de granularité dans un graphe acyclique orienté. Le niveau le plus élevé représente une approche de conception d'équipements multi-standards de type Velcro. Plus les opérateurs sont bas dans le graphe, plus leur coût est faible en termes de complexité, mais plus il faut faire appel de fois à eux pour effectuer des opérations de différentes sortes. Nous décrivons ensuite en tant qu'exemples des conception basées sur les opérateurs DMFFT (dual mode FFT), LFSR (linear feedback shift register) et le cas du FRMFB (frequency response masking filter bank). Les solutions basées sur les opérateurs communs proposées dans cette thèse peuvent contribuer à optimiser la conception des futurs équipements multi-standards de radio logicielle qui devront supporter de nombreux standards de communication sans fil.

Cette thèse s'articule autour des fonctions booléennes liées à la cryptographie et la cryptanalyse de certains schémas d'identification. Les fonctions booléennes possèdent des propriétés algébriques fréquemment utilisées en cryptographie pour constituer des S-Boxes (tables de substitution).Nous nous intéressons, en particulier, à la construction de deux types de fonctions : les fonctions courbes et les fonctions équilibrées de haut degré de non-linéarité.Concernant la cryptanalyse, nous nous focalisons sur les techniques d'identification basées sur les problèmes de perceptron et de perceptron permuté. Nous réalisons une nouvelle attaque sur le schéma afin de décider de sa faisabilité.Nous développons ici des nouvelles méthodes combinant l'approche déterministe DCA (Difference of Convex functions Algorithm) et heuristique (recuit simulé, entropie croisée, algorithmes génétiques...). Cette approche hybride, utilisée dans toute cette thèse, est motivée par les résultats intéressants de la programmation DC. / In cryptography especially in block cipher design, boolean functions are the basic elements.A cryptographic function should have high non-linearity as it can be attacked by linear method. There are three goals for the research presented in this thesis :_ Finding a new construction algorithm for the highest possible nonlinear boolean functions in the even dimension, that is bent functions, based on a detreministic model._ Finding highly non linear boolean functions._ Cryptanalysing an identification scheme based on the perceptron problem.Optimisation heuristic algorithms (Genetic algorithm and simulated annealing) and a deterministicone based on DC programming (DCA) were used together.

Un hypercube latin (LHD) maximin est un ensemble de points contenus dans un hypercube tel que les points ne partagent de coordonnées sur aucune dimension et tel que la distance minimale entre deux points est maximale. Les LHDs maximin sont particulièrement utilisés pour la construction de métamodèles en raison de leurs bonnes propriétés pour l’échantillonnage. Comme la plus grande partie des travaux concernant les LHD se sont concentrés sur leur construction par des algorithmes heuristiques, nous avons décidé de produire une étude détaillée du problème, et en particulier de sa complexité et de son approximabilité en plus des algorithmes heuristiques permettant de le résoudre en pratique.Nous avons généralisé le problème de construction d’un LHD maximin en définissant le problème de compléter un LHD entamé en respectant la contrainte maximin. Le sous-problème dans lequel le LHD partiel est vide correspond au problème de construction de LHD classique. Nous avons étudié la complexité du problème de complétion et avons prouvé qu’il est NP-complet dans de nombreux cas. N’ayant pas déterminé la complexité du sous-problème, nous avons cherché des garanties de performances pour les algorithmes résolvant les deux problèmes.D’un côté, nous avons prouvé que le problème de complétion n’est approximable pour aucune norme en dimensions k ≥ 3. Nous avons également prouvé un résultat d’inapproximabilité plus faible pour la norme L1 en dimension k = 2. D’un autre côté, nous avons proposé un algorithme d’approximation pour le problème de construction, et avons calculé le rapport d’approximation grâce à deux bornes supérieures que nous avons établies. En plus de l’aspect théorique de cette étude, nous avons travaillé sur les algorithmes heuristiques, et en particulier sur la méta-heuristique du recuit simulé. Nous avons proposé une nouvelle fonction d’évaluation pour le problème de construction et de nouvelles mutations pour les deux problèmes, permettant d’améliorer les résultats rapportés dans la littérature. / A maximin Latin Hypercube Design (LHD) is a set of point in a hypercube which do not share a coordinate on any dimension and such that the minimal distance between two points, is maximal. Maximin LHDs are widely used in metamodeling thanks to their good properties for sampling. As most work concerning LHDs focused on heuristic algorithms to produce them, we decided to make a detailed study of this problem, including its complexity, approximability, and the design of practical heuristic algorithms.We generalized the maximin LHD construction problem by defining the problem of completing a partial LHD while respecting the maximin constraint. The subproblem where the partial LHD is initially empty corresponds to the classical LHD construction problem. We studied the complexity of the completion problem and proved its NP-completeness for many cases. As we did not determine the complexity of the subproblem, we searched for performance guarantees of algorithms which may be designed for both problems. On the one hand, we found that the completion problem is inapproximable for all norms in dimensions k ≥ 3. We also gave a weaker inapproximation result for norm L1 in dimension k = 2. On the other hand, we designed an approximation algorithm for the construction problem which we proved using two new upper bounds we introduced.Besides the theoretical aspect of this study, we worked on heuristic algorithms adapted for these problems, focusing on the Simulated Annealing metaheuristic. We proposed a new evaluation function for the construction problem and new mutations for both the construction and completion problems, improving the results found in the literature.

Cette thèse aborde le problème de la reconstruction tridimensionnelle de zones urbaines à partir d'images satellitaires très haute résolution. Le contenu informatif de ce type de données est insuffisant pour permettre une utilisation efficace des nombreux algorithmes développés pour des données aériennes. Dans ce contexte, l'introduction de connaissances a priori fortes sur les zones urbaines est nécessaire. Les outils stochastiques sont particulièrement bien adaptés pour traiter cette problématique.<br /><br />Nous proposons une approche structurelle pour aborder ce sujet. Cela consiste à modéliser un bâtiment comme un assemblage de modules urbains élémentaires extraits d'une bibliothèque de modèles 3D paramétriques. Dans un premier temps, nous extrayons les supports 2D de ces modules à partir d'un Modèle Numérique d' Elévation (MNE). Le résultat est un agencement de quadrilatères dont les éléments voisins sont connectés entre eux. Ensuite, nous reconstruisons les bâtiments en recherchant la configuration optimale de modèles 3D se fixant sur les supports précédemment extraits. Cette configuration correspond à la réalisation qui maximise une densité mesurant la cohérence entre la réalisation et le MNE, mais également prenant en compte des connaissances a priori telles que des lois d'assemblage des modules. Nous discutons enfin de la pertinence de cette approche en analysant les résultats obtenus à partir de données satellitaires (simulations PLEIADES). Des expérimentations sont également réalisées à partir d'images aériennes mieux résolues.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.