Les problèmes de placement sont généralement NP-difficiles, ou NP-complets suivant l'objectif à atteindre. Il s'agit ici de positionner un ensemble d'objets dans un ou plusieurs “container(s)”, de dimensions données ou de hauteur infinie, en respectant des contraintes liées à certaines caractéristiques (poids, quantité, rotation, équilibre, découpe guillotine...). Ces problèmes ont de nombreuses applications pratiques. Les stratégies de résolution les plus efficaces sont généralement les méthodes approchées, en particulier la recherche locale. Dans cette thèse, nous nous intéressons à un problème de placement particulier en deux dimensions (sans rotation possible des objets (rectangulaires) ni prise en compte de la contrainte guillotine) connu sous le nom de “strip packing” (SPP). L'objectif de ce problème est de minimiser la hauteur atteinte après placement (sans chevauchement) des objets. Nous avons développé deux approches “méta-heuristiques” incluant des composants novateurs reposant sur une connaissance approfondie du problème. La première est un algorithme génétique avec un nouveau croisement (très “visuel”) et une fonction d'évaluation hiérarchique. La seconde est une recherche tabou avec représentation “directe” (i.e. n'utilisant pas les habituelles permutations) dont les caractéristiques principales sont un voisinage consistant, une diversification reposant sur l'historique de la recherche et une fonction d'évaluation qui mesure la qualité de solutions éventuellement partielles. Les deux approches proposées, évaluées sur un jeux de test bien connu et très difficile, se sont révélées performantes comparées à d'autres stratégies.

La plupart des méthodes d'ordonnancement considèrent un environnement déterministe où les données du problème sont connues. Néanmoins, en réalité, plusieurs sortes d'aléas peuvent être rencontrées et l'ordonnancement robuste permet en tenir compte. Dans cette thèse, notre intuition initiale est que, d'une part, un ordonnancement non robuste deviendra rapidement inefficace avec les incertitudes qu'un ordonnancement robuste, et d'autre part, un ordonnancement robuste sera moins efficace qu'un ordonnancement non robuste en l'absence d'incertitudes. Dans ce cadre, nous avons proposé un algorithme génétique pour l'ordonnancement robuste. Un nouveau mécanisme de résolution et un nouveau critère de robustesse permettant de trouver une solution de bonne performance et peu sensible aux incertitudes ont été développés. Une phase expérimentale a été menée, d'une part, pour vérifier l'efficacité de l'algorithme génétique pour l'ordonnancement déterministe, sans tenir compte des incertitudes, et d'autre part, pour valider l'algorithme génétique pour l'ordonnancement robuste par la simulation afin de juger la qualité de la robustesse face aux incertitudes. Nous avons intégré cette approche de robustesse dans une démarche méthodologique générique intégrant des techniques d'optimisation et de simulation pour l'aide au dimensionnement des systèmes de production basé sur des ordonnancements robustes. Les différents modules de la démarche ont été développés sous forme d'un outil d'aide au dimensionnement, dans le cadre d'un cas applicatif réel, celui du bloc opératoire dans le secteur hospitalier.

Le développement de créatures artificielles est un domaine de recherche en plein essor. Depuis plus de vingt ans maintenant, de nombreuses techniques sont apparues afin de simuler à plusieurs niveaux des êtres artificiels : en commençant par la simulation de leur comportement au début des années 90, on a ensuite continué en modifiant leur morphologie pour qu'elle soit adaptée à leur environnement. Plus récemment, l'embryogenèse artificielle s'inspire des mécanismes de développement du vivant afin de générer de petites créatures de quelques dizaines à plusieurs centaines de cellules. Le but de ces systèmes est d'une part de mieux comprendre le vivant mais aussi de produire des modèles comportementaux pour les futurs robots modulaires. Après avoir étudié ces différents niveaux de simulation, nous nous sommes aperçus qu'il n'existait pas de modèle transversal permettant une simulation à plusieurs échelles des créatures. Le but de ces travaux est de développer une créature complète en partant d'une cellule unique, possédant différents organes et des fonctionnalités haut niveau. Le but de cette thèse est de construire le modèle chimique de cet ensemble de simulateurs. Nous avons ainsi proposé un modèle basé sur une forte simplification du modèle de développement naturel. Les créatures devront de plus intégrer un métabolisme afin de pouvoir extraire de l'énergie des différents constituants de son environnement. Ce métabolisme est trop souvent oublié dans les modèles de développement de la littérature bien qu'il soit à la base de la vie de tous les êtres vivants. A travers différentes expérimentations que nous avons effectuées, nous avons prouvé que ce modèle est capable de produire différents organes et de les assembler afin de créer un organisme plus complexe. Nous avons aussi montré la possibilité à produire une forme particulière. Enfin, nous avons observé d'importantes capacités d'auto-réparation inhérentes au modèle. Ce modèle de développement est un premier simulateur qui sera inclu dans un ensemble de simulateurs agissants à différentes échelles de la créature. Comme nous le verrons dans les perspectives de ces travaux, nous avons commencé à imaginer un simulateur physique et un simulateur hydrodynamique permettant de plonger une créature en train de se développer dans un monde physique aux lois newtoniennes et un monde hydrodynamique répondant aux équations de Navier et Stokes.

.

.

.

Dans ce mémoire, nous presentons les meta-heuristiques inspirées du comportement des fourmis lors de la recherche de nourriture, les OCF. Nous confrontons ces méthodes face aux principales méta-heuristiques connues. Pour cela, nous proposons de nous placer sous le point de vue de l'utilisation de la mémoire et nous présentons taxinomie qui étend celle des AMP. Nous proposons deux nouvelles adaptations du modéle des fourmis. La premiere est l'algorithme ANTabu, il s'agit d'une méthode hybride pour la résolution du PAQ. Il associe l'utilisation des fourmis artificielles et d'une méthode de recherche locale robuste : la recherche tabou. Le parallélisme intrinseque des systèmes de fourmis nous a amene a developper un modele paralléle pour ANTabu.<br />Cette méthode intègre également une puissante fonction de diversification et l'utilisation de bornes qui lui permettent d'eviter d'être piege au niveau d'optima locaux.<br />La seconde application développee est AP, cet algorithme est l'adaptation du modèle de coopération des fourmis a la programmation automatique. Son mécanisme de fonctionnement<br />est simple, puisque à chaque itération on crée une nouvelle population en utilisant l'information emmagasinée par la phéromone. L'intérêt de cette gestion de l'information est qu'elle n'utilise pas de mécanismes complexes. Nous présentons cette méthode face a l'algorithme de base tel que Koza l'a défini.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.