Le problème de planification d'itinéraires dans un environnement dynamique est un problème complexe. Ce problème est d'autant plus difficile que les décisions doivent se prendre dans un temps limité, en se basant sur des informations incertaines et qui évoluent dans le temps. Nous nous sommes intéressés aux méthodes métaheuristiques, et plus particulièrement aux algorithmes génétiques pour résoudre ce problème. Plusieurs approches habituellement proposées pour ce problème sont purement prescriptives et ne garantissent que la convergence vers une solution réalisable au détriment de l'optimalité. De plus, les approches basées sur les algorithmes génétiques souffrent toutes du problème de calibrage des paramètres, une étape importante quand quelqu'un décide de les utiliser. Notre thèse s'inscrit dans le cadre de cette nouvelle direction de recherche et puise sa motivation plus particulièrement dans la volonté de répondre à quelques-unes des problématiques rencontrées dans des applications temps-réel. Nous proposons une approche générique utilisant un processus évolutionnaire à deux niveaux pour régler le problème de calibrage de combinaisons d'opérateurs dans les algorithmes génétiques. Nous avons développé une stratégie d'attente qui exploite des connaissances probabilistes sur les événements futurs afin de produire des solutions robustes et de meilleure qualité en temps réel. De plus, dans le cas des problèmes de transport utilisant des flottes de véhicules (pour la distribution des biens et services), l'approche proposée reflète la réalité de façon plus adéquate en considérant différentes situations observées en pratique comme des temps de voyage variables, et en intégrant des stratégies et mécanismes appropriés pour chacune des situations identifiées. Nous avons présenté une vision plus large du concept de diversion et nous avons introduit une condition d'acceptation d'une diversion dans la planification d'itinéraires en temps réel. Afin de faire face aux pressions temporelles inhérentes à un contexte dynamique, nous avons opté pour des implantations parallèles afin d'accélérer les temps de réponse. Enfin, des tests numériques ont été réalisés à l'aide de simulations utilisant une adaptation des instances de problèmes de Solomon pour le problème de tournées de véhicules avec fenêtres de temps (VRPTW). Dans ce problème, il s'agit d'affecter des requêtes de clients qui arrivent en temps réel à une flotte de véhicules en mouvement. Ce processus implique aussi la construction simultanée d'un ensemble d'itinéraires planifiés qui satisfont la demande, tout en respectant diverses contraintes. Afin de minimiser les biais, le même jeu de données utilisé dans la littérature pour le VRPTW dynamique a été employé pour réaliser notre étude. Les résultats numériques confirment la pertinence des différentes stratégies que nous avons développées et la supériorité de notre approche de planification d'itinéraires en temps réel comparativement à d'autres méthodes proposées dans la littérature.

Ce mémoire est consacré à la parallélisation d'un algorithme d'assemblage d'ADN de type de novo sur différentes plateformes matérielles, soit les processeurs multicoeurs et les accélérateurs de type FPGA. Plus précisément, le langage OpenCL est utilisé pour accélérer l'algorithme dont il est question, et de permettre un comparatif direct entre les les plateformes. Cet algorithme est d'abord introduit, puis son implémentation originale, développée pour une exécution sur une grappe de noeuds, est discutée. Les modifications apportées à l'algorithme dans le but de faciliter la parallélisation sont ensuite divulgées. Ensuite, le coeur du travail est présenté, soit la programmation utilisant OpenCL. Finalement, les résultats sont présentés et discutés.

L’industrie de la volaille est en pleine croissance au cours des dernières décennies. Au Québec, les producteurs de volailles sont organisés en association dans une complexe chaîne d’approvisionnement. Cette chaîne suit les principes de l’agriculture contractuelle sur un marché basé sur la gestion de l’offre. La gestion de l’offre, parmi d’autres règles, établit le prix de vente de la volaille aux épiceries. Cependant, il existe un marché spécialisé pour la volaille où le prix de vente n’est pas contrôlé par la gestion de l’offre. Ce marché spécialisé comprend le besoin de volaille fraîche de la restauration et des rôtisseries. Il est beaucoup plus profitable pour les producteurs d’approvisionner ce marché spécialisé. La coopérative partenaire de cette recherche est formée par des producteurs de volailles pour abattre et vendre leur production. La coopérative veut ajouter de la valeur à ses propriétaires en augmentant sa participation au marché spécialisé de la volaille. Cependant, ses produits ne sont pas toujours dans le standard de poids requis par ce marché. Ce mémoire présente l’étude du cas de cette coopérative, afin d’améliorer leurs processus opérationnels et d’obtenir des produits dans le poids standard établi par le marché spécialisé. On propose donc une solution à ce problème avec l’emploi de la programmation mathématique. L’algorithme de séparation et d’évaluation progressive (branch-and-bound) est appliqué pour l’obtention des résultats. On a trouvé une solution à la formulation mathématique proposée au problème opérationnel de la coopérative. Bien que la solution ait été obtenue avec un écart d’optimalité de 20%, la coopérative a vu qu’il était possible de gagner du temps dans son processus opérationnel si la solution était adoptée. La coopérative a donc décidé de transformer ce prototype en un vrai logiciel pour la planification de l’élevage. / The poultry industry faces a strong growth in the last decades. In Québec, poultry producers are organized in associations within a complex supply chain. This chain follows the principles of the contract farming in a market based on supply management. The supply management, among other rules, establishes the sales price of poultry to grocery stores. However, there is a specialized market for the poultry where the sale price is not controlled by the supply management. This specialized market gathers the need of fresh poultry for the restaurants and rotisseries. It is much more profitable for the producers to supply this specialized market. The cooperative partner of this research is composed of poultry producers to slaughter and sell their production. This cooperative wants to add value to their owners by increasing participation in the specialized poultry market. However, their products are not always within the required weight. This master thesis presents the case study of the cooperative so that they can enhance their operational processes and have the products within the standard weight established by the specialized market. We propose a solution to this problem by using mathematical programming. The branch-and-bound algorithm is used for obtaining the results. We found a solution for the mathematical formulation proposed for the operational problem. Even though the solution was obtained with an optimization gap of 20%, the cooperative noticed an opportunity to save time on the daily work in its operational process if the solution is adopted. So, the cooperative decided to transform this prototype in a real software for their production planning.

L’objectif général de cette thèse est d’utiliser les connaissances en physique de la radiation, en programmation informatique et en équipement informatique à la haute pointe de la technologie pour améliorer les traitements du cancer. En particulier, l’élaboration d’un plan de traitement en radiothérapie peut être complexe et dépendant de l’utilisateur. Cette thèse a pour objectif de simplifier la planification de traitement actuelle en curiethérapie de la prostate à haut débit de dose (HDR). Ce projet a débuté à partir d’un algorithme de planification inverse largement utilisé, la planification de traitement inverse par recuit simulé (IPSA). Pour aboutir à un algorithme de planification inverse ultra-rapide et automatisé, trois algorithmes d’optimisation multicritères (MCO) ont été mis en oeuvre. Suite à la génération d’une banque de plans de traitement ayant divers compromis avec les algorithmes MCO, un plan de qualité a été automatiquement sélectionné. Dans la première étude, un algorithme MCO a été introduit pour explorer les frontières de Pareto en curiethérapie HDR. L’algorithme s’inspire de la fonctionnalité MCO intégrée au système Raystation (RaySearch Laboratories, Stockholm, Suède). Pour chaque cas, 300 plans de traitement ont été générés en série pour obtenir une approximation uniforme de la frontière de Pareto. Chaque plan optimal de Pareto a été calculé avec IPSA et chaque nouveau plan a été ajouté à la portion de la frontière de Pareto où la distance entre sa limite supérieure et sa limite inférieure était la plus grande. Dans une étude complémentaire, ou dans la seconde étude, un algorithme MCO basé sur la connaissance (kMCO) a été mis en oeuvre pour réduire le temps de calcul de l’algorithme MCO. Pour ce faire, deux stratégies ont été mises en oeuvre : une prédiction de l’espace des solutions cliniquement acceptables à partir de modèles de régression et d’un calcul parallèle des plans de traitement avec deux processeurs à six coeurs. En conséquence, une banque de plans de traitement de petite taille (14) a été générée et un plan a été sélectionné en tant que plan kMCO. L’efficacité de la planification et de la performance dosimétrique ont été comparées entre les plans approuvés par le médecin et les plans kMCO pour 236 cas. La troisième et dernière étude de cette thèse a été réalisée en coopération avec Cédric Bélanger. Un algorithme MCO (gMCO) basé sur l’utilisation d’un environnement de développement compatible avec les cartes graphiques a été mis en oeuvre pour accélérer davantage le calcul. De plus, un algorithme d’optimisation quasi-Newton a été implémenté pour remplacer le recuit simulé dans la première et la deuxième étude. De cette manière, un millier de plans de traitement avec divers compromis et équivalents à ceux générés par IPSA ont été calculés en parallèle. Parmi la banque de plans de traitement généré par l’agorithme gMCO, un plan a été sélectionné (plan gMCO). Le temps de planification et les résultats dosimétriques ont été comparés entre les plans approuvés par le médecin et les plans gMCO pour 457 cas. Une comparaison à grande échelle avec les plans approuvés par les radio-oncologues montre que notre dernier algorithme MCO (gMCO) peut améliorer l’efficacité de la planification du traitement (de quelques minutes à 9:4 s) ainsi que la qualité dosimétrique des plans de traitements (des plans passant de 92:6% à 99:8% selon les critères dosimétriques du groupe de traitement oncologique par radiation (RTOG)). Avec trois algorithmes MCO mis en oeuvre, cette thèse représente un effort soutenu pour développer un algorithme de planification inverse ultra-rapide, automatique et robuste en curiethérapie HDR. / The overall purpose of this thesis is to use the knowledge of radiation physics, computer programming and computing hardware to improve cancer treatments. In particular, designing a treatment plan in radiation therapy can be complex and user-dependent, and this thesis aims to simplify current treatment planning in high dose rate (HDR) prostate brachytherapy. This project was started from a widely used inverse planning algorithm, Inverse Planning Simulated Annealing (IPSA). In order to eventually lead to an ultra-fast and automatic inverse planning algorithm, three multi-criteria optimization (MCO) algorithms were implemented. With MCO algorithms, a desirable plan was selected after computing a set of treatment plans with various trade-offs. In the first study, an MCO algorithm was introduced to explore the Pareto surfaces in HDR brachytherapy. The algorithm was inspired by the MCO feature integrated in the Raystation system (RaySearch Laboratories, Stockholm, Sweden). For each case, 300 treatment plans were serially generated to obtain a uniform approximation of the Pareto surface. Each Pareto optimal plan was computed with IPSA, and each new plan was added to the Pareto surface portion where the distance between its upper boundary and its lower boundary was the largest. In a companion study, or the second study, a knowledge-based MCO (kMCO) algorithm was implemented to shorten the computation time of the MCO algorithm. To achieve this, two strategies were implemented: a prediction of clinical relevant solution space with previous knowledge, and a parallel computation of treatment plans with two six-core CPUs. As a result, a small size (14) plan dataset was created, and one plan was selected as the kMCO plan. The planning efficiency and the dosimetric performance were compared between the physician-approved plans and the kMCO plans for 236 cases. The third and final study of this thesis was conducted in cooperation with Cédric Bélanger. A graphics processing units (GPU) based MCO (gMCO) algorithm was implemented to further speed up the computation. Furthermore, a quasi-Newton optimization engine was implemented to replace simulated annealing in the first and the second study. In this way, one thousand IPSA equivalent treatment plans with various trade-offs were computed in parallel. One plan was selected as the gMCO plan from the calculated plan dataset. The planning time and the dosimetric results were compared between the physician-approved plans and the gMCO plans for 457 cases. A large-scale comparison against the physician-approved plans shows that our latest MCO algorithm (gMCO) can result in an improved treatment planning efficiency (from minutes to 9:4 s) as well as an improved treatment plan dosimetric quality (Radiation Therapy Oncology Group (RTOG) acceptance rate from 92.6% to 99.8%). With three implemented MCO algorithms, this thesis represents a sustained effort to develop an ultra-fast, automatic and robust inverse planning algorithm in HDR brachytherapy.

Thèse en cotutelle : Université Laval, Québec, Canada et Université Paris-Sud, Orsay, France. / La publicité et le marketing, autrefois connus comme étant des moyens pour les entreprises de faire connaître leurs produits aux consommateurs, sont sournoisement devenus des armes de consommation massives ciblant le consommateur au meilleur moment pour modifier son comportement d’achat. Grâce aux technologies émergentes, comme l’intelligence artificielle, et à la multiplication des moyens pour recueillir massivement des informations sur le consommateur, les entreprises ont su créer une nouvelle forme de marketing : le marketing intelligent. Cette nouvelle méthode qui couple les données massives aux nouvelles techniques d’apprentissage machine permet aux commerçants d’en connaître plus sur le consommateur qu’il n’en connaît sur lui-même. Armées de nouvelles techniques issues de l’intelligence artificielle, les entreprises sont en mesure de cibler de manière précise les consommateurs afin de personnaliser l’offre de manière unique. Grâce aux nouvelles technologies, le marketing opère un changement de paradigme vers une pratique individualisée. Le consommateur ne devient-il pas alors plus vulnérable à ces pratiques ciblées et à leur omniprésence dans le marché ? / Advertising and marketing, known as methods for companies to promote their products to consumers, have steadily become massive targeting weapons to influence the consumers behavior. Emerging technologies such as artificial intelligence and big data analytics have allowed companies to create a new form of marketing: intelligent marketing. These new methods allow merchants to know more about the consumer than he knows about himself. Armed with new techniques derived from artificial intelligence, companies are able to precisely target consumers and uniquely personalize their offerings. This begs the question: Does the consumer become more vulnerable to these growing practices and their omnipresence in the market?

Un besoin ayant toujours existé dans le domaine de la vision numérique est celui d'avoir accès à des ensembles d'images annotées. Les avancements scientifiques et technologiques ont exacerbé les besoins en données étiquetées; un modèle d'apprentissage profond peut nécessiter des milliers, voire des centaines de milliers (dépendamment de la complexité du problème), d'images étiquetées. Cela peut causer un problème puisque générer de grands ensembles de données étiquetées est une tâche longue et ardue. Est-il possible de travailler en vision numérique sans avoir à collecter et étiqueter des ensembles de données de plus en plus grands ? Dans le cadre de cette thèse, nous tentons de répondre à cette question sur deux fronts différents. Premièrement, nous avons développé une approche de détection et segmentation d'objets nécessitant peu de données d'entraînement. Cette approche, inspirée des modèles par les bag-of-words, modélise l'apparence et la forme des objets de façon éparse; la modélisation de la forme se fait par l'entremise d'un nouveau descripteur de forme. Deuxièmement, nous nous sommes penchés sur le fait que certains ensembles de données sont difficilement capturables et étiquetables. Nous nous sommes concentrés sur un exemple particulier, c'est-à-dire générer un ensemble d'images de scènes extérieures avec de la pluie dont les annotations consistent au taux de précipitation (mm/h). Notre solution consiste à augmenter des images réelles avec de la pluie synthétique. Si ces images augmentées sont suffisamment réalistes, il est possible d'expérimenter sur celles-ci comme si elles étaient des images de pluie réelle. Dans nos expérimentations, nous avons évalué l'effet de la pluie sur différents algorithmes de vision numérique et nous avons augmenté la robustesse de ceux-ci sur des images contenant de la vraie pluie.

Cette thèse concerne l’étude des ailes oscillantes flexibles et des méthodes numériques qui s’y rattachent. De ce fait, la thèse est divisée en deux parties. La première contribution concerne le développement d’un algorithme de couplage fluide-structure qui prend en charge les interactions entre un solide élastique en grands déplacements et un fluide incompressible. L’algorithme est basé sur une approche partitionnée et permet d’utiliser des codes numériques de mécanique des fluides et de mécanique des solides existants. L’utilisation d’un terme de compressibilité artificiel dans l’équation de continuité du fluide combinée à des choix algorithmiques judicieux permet d’utiliser cette méthode de couplage efficacement avec un code de mécanique des fluides utilisant une méthode de projection de type SIMPLE ou PISO. La seconde contribution est l’étude de l’effet de flexibilité des ailes sur le vol à ailes battantes. Deux principaux régimes de vol sont mis en évidence concernant la déformation de l’aile : déformation causée par la pression et déformation causée par l’inertie. Les effets de ces régimes sur la topologie de l’écoulement et sur les performance de l’aile en propulsion sont discutés. Il est montré que les cas avec des déformations causées par la pression présentent généralement des efficacités plus élevées avec une flexibilité modérée. Il en est de même pour la force de poussée lorsque l’amplitude de tangage est faible. D’autre part, lorsque les déformations sont causées par l’inertie, les performances de l’aile sont généralement réduites. Certains cas montrent une augmentation marginale des performances lorsque le synchronisme des déformations est optimal, mais ces cas représentent davantage une exception que la norme. Il est également démontré que la flexibilité peut être utilisée comme mécanisme de tangage passif tout en conservant des performances intéressantes. Enfin, un modèle d’aile oscillante flexible non contraint est présenté. Il est démontré que le mouvement de déviation observé dans la nature est une conséquence d’un phénomène aérodynamique de mise en drapeau. / This thesis concerns the study of flexible flapping wings and the related numerical methods. It thus contains two distinct themes. The first contribution is the implementation of an efficient fluid-structure interaction algorithm that handles the interaction of an elastic solid undergoing large displacement with an incompressible fluid. The algorithm is based on the partitioned approach and allows state-of-the-art fluid and structural solvers to be used. Stabilization with artificial compressibility in the fluid continuity equation along with judicious algorithmic choices make the method suitable to be used with SIMPLE or PISO projection fluid solvers. The second contribution is the study of the effects of wing flexibility in flapping flight. The different regimes, namely inertia-driven and pressure-driven wing deformations are presented along with their effects on the topology of the flow and, eventually, on the performance of the flapping wing in propulsion regime. It is found that pressure-driven deformations can increase the thrust efficiency if a suitable amount of flexibility is used. Thrust increases are also observed when small pitching amplitude cases are considered. On the other hand, inertia-driven deformations generally deteriorate aerodynamic performances of flapping wings unless meticulous timing is respected, making them less practical. It is also shown that wing flexibility can act as a passive pitching mechanism while keeping decent thrust and efficiency. Lastly, a freely-moving flexible flapping wing model is presented. It is shown that the deviation motion found in natural flyers is a consequence of a feathering mechanism.

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2010-2011 / Comment utiliser la théorie de la recherche et la planification de chemins pour formuler et résoudre un problème de détection dans le contexte de la recherche et sauvetage en milieu terrestre considérant des aspects pratiques tels que les contraintes de visibilité découlant du terrain? Pour répondre à cette question, nous présentons une nouvelle formulation introduisant les contraintes de visibilité du chercheur (le problème de planification du chemin optimal du chercheur avec visibilité ou OSPV). De plus, nous présentons une extension multicritère du problème. Dans un premier temps, l'efficacité du plan de recherche est quantifiée par la probabilité de retrouver l'objet recherché; un programme en nombres entiers mixte est comparé à Ant Search, notre adaptation de l'optimisation par colonies de fourmis. Ensuite, l'extension multicritère intègre les aspects de sécurité du chercheur et de complexité du plan; Ant Search est alors étendu pour introduire Pareto Ant Search et Lexicographie Ant Search.

L’optimisation combinatoire concerne la résolution de problèmes pour lesquels les variables prennent des valeurs discrètes et sur lesquelles s’appliquent des contraintes. L’ensemble des variables et des contraintes définissent un modèle représentant le problème. Un très grand nombre de problèmes industriels peuvent être représentés sous cette forme. Un logiciel qui prend un modèle en entrée et produit une solution est appelé solveur. La programmation par contraintes (PPC) est l’une des techniques algorithmiques pouvant être utilisée par ces solveurs. Dans ce mémoire, nous développons un nouveau solveur. L’objectif premier est de compter sur un solveur facilement modifiable dans le but d’y ajouter de nouvelles approches de résolution développées par les chercheurs. De plus, dans le but de démontrer l’utilité du solveur, nous développons une approche exploitant ce solveur dans le but de générer des patrons de chargement alternatifs pour un séchoir à bois utilisé par l’industrie des produits forestiers. Finalement, nous présentons dans ce mémoire une nouvelle technique pour résoudre avec plus d’efficience certains problèmes de PPC. Les algorithmes de filtrage associés aux contraintes sont typiquement déclenchés en fonction d’événements qui se produisent lors de la résolution du problème. Nous proposons un nouvel événement qui permet d’effectuer du filtrage tardif des variables. Nous montrons que, pour un problème classique d’optimisation combinatoire (Balanced Incomplete Block Design), il donne une meilleure performance tout en maintenant le même niveau de filtrage par rapport à l’utilisation des événements classiques. / Combinatorial optimization concerns the solving of problems for which the variables take discrete values and on which constraints apply. The set of variables and constraints form the model of the problem. A lot of industrial problems can be represented in this form. A solver is a software that takes as input a model and produces a solution. Constraint programming (CP) is one of the algorithmic techniques that can be used within a solver. In this master’s thesis, we develop a new solver. The primary objective is to rely on an easily modifiable solver in order to add new resolution approaches developed by researchers. Moreover, in order to demonstrate the utility of the solver, we develop an approach using that solver in order to generate alternative loading patterns for a kiln in the forest industry. Finally, in this master’s thesis, we present a new technique for solving some CP problems. The filtering algorithms are triggered according to events that occur when solving the problem. We propose a new event that allows to perform a lazy filtering of the variables. We demonstrate, on a classical combinatorial optimization problem (Balanced Incomplete Block Design), that it gives a better performance while maintaining the same level of filtering when compared with classical events.

Le biais de confusion peut affecter tous les types d’études d’observation. Il apparaît lorsque la caractéristique étudiée est associée à un facteur de perturbation complémentaire et que ce dernier fait croire à l’existence d’une relation de cause à effet entre la caractéristique étudiée et l’issue. Des méthodes d’ajustement pour le biais de confusion, notamment les modèles structurels marginaux, peuvent être utilisées pour corriger ce type de biais. Ces modèles n’ont toutefois été utilisés qu’une seule fois pour l'étude de l’effet d’une exposition cumulative aux stresseurs psychosociaux au travail sur la pression artérielle. L’objectif principal de ce mémoire était de comparer différents estimateurs des paramètres d’un modèle structurel marginal à des approches classiques. Nous avons considéré les estimateurs par pondération inverse de la probabilité de traitement, le calcul-g, le maximum de vraisemblance ciblé avec et sans SuperLearner. Ces estimateurs ont d’abord été utilisés pour estimer l’effet d’une exposition cumulée aux stresseurs psychosociaux au travail sur la pression artérielle systolique dans le cadre d’une étude de cohorte prospective de 5 ans. Cette analyse a révélé des différences significatives entre les estimateurs. Puisqu’il s’agit de données réelles, il est toutefois impossible de déterminer quelle méthode produit les résultats les plus valides. Pour répondre à cette question, nous avons développé deux algorithmes de simulation de données longitudinales de type Plasmode, l’un utilisant des modèles paramétriques et l’autre utilisant des approches non paramétriques. Les simulations Plasmode combinent des données réelles et des données synthétiques pour étudier les propriétés dans un contexte connu, mais similaire au contexte réel. Au vue des résultats, nous avons conclu que les modèles structurels marginaux représentent des approches pertinentes pour estimer l’effet des stresseurs psychosociaux au travail. Nous recommandons particulièrement d’utiliser la méthode de maximum de vraisemblance ciblé avec et sans SuperLearner. Cependant, cela nécessite un effort supplémentaire en termes d’implantation de code et de temps d’exécution.