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

Dans cette thèse, nous montrons l'importance de la modélisation et de la coopération de métaheuristiques pour la résolution de problèmes réels en bioinformatique. Deux problèmes ont été étudiés: l'identification de protéines à partir de données spectrales en protéomique et le problème du docking moléculaire flexible en analyse structurale des molécules. Pour le premier problème, un nouveau modèle basé sur une comparaison directe des bases de données protéiques avec les données expérimentales brutes a été mise en place. L'approche associée a été intégrée au sein d'un moteur d'identification par empreinte de masse peptide appelé ASCQ_ME. Ce modèle d'identification a permis ensuite de proposer et de valider une modélisation pour le problème de de novo protein sequencing qui consiste à retrouver la séquence d'une protéine à partir des données expérimentales seules. Il s'agit d'un modèle en trois étapes appelé SSO pour Sequence, Shape et Order. SSO a été implémenté et testé à travers trois métaheuristiques collaborant de manière séquentielle. Pour le second problème, une étude des nouvelles modélisations multi-objectif a été menée et a conduit à la définition de huit modèles différents testés à l'aide d'algorithmes génétiques multi-objectif parallèles. Les tests réalisés ont mis en évidence l'efficacité de l'hybridation des algorithmes génétiques avec des recherches locales. Nos développement furent réalisé sur la plateforme ParadisEO et notamment sur la partie ParadisEO-MO pour laquelle nous avons grandement contribués. L'ensemble de ces travaux a été soutenu par le PPF Bio-Informatique de l'Université des Sciences et Technologies de Lille et le projet ANR Dock. / Ln this thesis, we show the importance of the modeling and the cooperation of metaheuristics for solving real problems in Bioinformatics. Two problems are studied: the first in the Proteomics domain for the protein identification from spectral data analysis and the second in the domain of the structural analysis of molecules for the flexible molecular docking problem. So, for the first problem, a new model has been designed based on a direct comparison of a raw experimental spectrum with protein from databases. This model has been included in an identification engine by peptide mass fingerprinting called ASCQ_ME. From this model, an approach for the de novo protein sequencing problem has been proposed and validated. ln this problem, a protein sequence has to be found with only spectral information. Our model is a three step approach called SSO for Sequence, Shape and Order. After a study of each step, SSO has been implemented and tested with three metaheuristics collaborating sequentially. For the second problem, a study of new multi-objective models has been made and has allowed to design eight different models tested with parallel multi-objective genetic algorithms. Twelve configurations of genetic operators has been tested in order to prove the efficiency of the hybridizing of genetic algorithms with local searches. For each part of this work, the ParadisEO platform has been used and more particularly the ParadisEO-MO part dedicated to single solution based metaheuristics for which we have substantially contributed. All this work has been funded by the "PPF Bio-Informatique" of the "Université des Sciences et Technologies de Lille" and by the ANR Dock project.

Les problèmes d'optimisation combinatoire sont généralement NP-difficiles et les méthodes exactes demeurent inefficaces pour les résoudre rapidement. Les métaheuristiques sont des méthodes génériques de résolution connues et utilisées pour leur efficacité. Elles possèdent souvent plusieurs paramètres qui s'avèrent fastidieux à régler pour obtenir de bonnes performances. Il est alors intéressant de chercher à rendre plus évident, voire à automatiser, ce réglage des paramètres. Le paysage d'un problème d'optimisation combinatoire est une structure, basée sur la notion de voisinage, permettant de caractériser le problème puis de suivre la dynamique d'une méthode d'optimisation pour comprendre son efficacité. Les travaux de cette thèse portent sur l'analyse de paysage de problèmes d'optimisation combinatoire et le lien étroit avec certaines classes de métaheuristiques, basées sur une exploration du voisinage des solutions. Ainsi, nous montrons l'influence de la structure de paysage sur la dynamique d'une métaheuristique, pour deux problèmes issus de la logistique. Ensuite, nous analysons les caractéristiques du paysage qui permettent de concevoir et/ou paramétrer des métaheuristiques, principalement des recherches locales, efficaces. La neutralité est, en particulier, une caractéristique structurelle importante des paysages. De tels paysages présentent de nombreux plateaux bloquant la progression d'une recherche locale. Après une analyse fine des plateaux, nous prouvons que cette structure neutre ne doit pas être ignorée. Puis, nous utilisons plusieurs informations liées à la neutralité, et plus particulièrement aux plateaux bloquants, pour concevoir une première recherche locale simple à mettre en œuvre et efficace. Enfin, pour approfondir nos travaux sur les structures neutres, nous avons choisi d'exploiter la neutralité à tous les niveaux du paysage pour concevoir une nouvelle recherche locale basée sur la capacité des solutions d'un même plateau à produire une amélioration. Une stratégie de guidage vers cette solution est alors proposée. La thèse se termine par l'analyse comparative des deux méthodes d'optimisation proposées pour les problèmes neutres afin d'en exploiter de nouvelles caractéristiques, et ainsi, renforcer le lien entre l'analyse de paysage et la conception de méthodes efficaces. / Many problems from combinatorial optimization are NP-hard, so that exact methods remain inefficient to solve them efficiently. However, metaheuristics are approximation methods known and used for their efficiency. But they often require a lot of parameters, which are very difficult to set in order to provide good performance. As a consequence, a challenging question is to perform such parameter tuning easier, or adaptive.The fitness landscape of given combinatorial optimization problem, based on a search space, a fitness function and a neighborhood relation, allow to characterize the problem structure and make the understanding of the dynamics of search approches possible.This thesis deals with fitness landscape analysis, together with the link with some neighborhood-based metaheuristic classes. We show the influence of the landscape structure on the dynamics of metaheuristics, for two challenging problems from the field of logistics. We analyze the landscape characteristics which help to design efficient local search metaheuristics and/or to set their parameters.Neutrality is one of the main structural characteristic of a landscape. Such landscapes have numerous plateaus, which often inhibits the progress of local search algorithms. After a deep analysis of these plateaus, we prove that this neutral structure cannot be ignored. Then, we use several information linked with neutrality, and particularly with blocking plateaus, in order to design a first local search approach, which appear to efficient and easy to implement. At last, in order to extend our work on the neutral structure, we chose to exploit the neutrality involved in the whole landscape. We propose a new local search algorithm, based on the ability of solutions of a plateau to produce improvement by means of a guiding strategy.The thesis ends with an experimental analysis of the two local search methods presented for neutral problems in order to exploit new characteristics, and then to strengthen the link between fitness landscape analysis and efficient algorithm design.

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

Cette thèse a été réalisée dans le cadre d'une collaboration entre l'université d'Angers et la société Perinfo. Elle porte sur le développement de nouveaux modèles et algorithmes dédiés à la détermination des horaires de lignes dans les réseaux de bus. Le coeur de ce manuscrit est la qualité de service perçue par l'usager. Nous réalisons dans un premier temps un état de l'art des étapes relatives à la planification du réseau. Nous proposons ensuite un modèle et des fonctions d'évaluation pour les objectifs de synchronisation des correspondances et de régularité du cadencement. Ces éléments sont utilisés au sein d'une méthode de recherche locale basée sur un ensemble de voisinages que nous définissons pour le problème. Notre troisième contribution est la modélisation d'un problème original et intégré qui résout simultanément le problème de fixation des horaires et de création des affectations de véhicules. Pour ce problème complexe, nous proposons une méthode de résolution hybride basée sur une recherche locale itérée et un algorithme exact par enchères, ainsi que deux voisinages spécifiques. Les tests réalisés sur données réelles valident la supériorité de l'approche simultanée par comparaison avec la situation existante et l'approche séquentielle, tant au niveau de la qualité de service que des coûts économiques. Enfin, nous étudions une problématique originale qui prend à contre-courant le processus traditionnel de planification. Ce problème de fixation des horaires, visant des objectifs liés aux correspondances, prend pour contraintes les séquences de courses affectées aux véhicules et aux conducteurs. Cette approche permet d'améliorer la qualité de service sans remettre en cause les plannings d'exploitation. Une méthode tabou basée sur deux voisinages adaptés est développée et testée sur un cas d'étude.

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

Résoudre des problèmes d'optimisation est un point clé dans l'amélioration constante de la productivité des entreprises. Quand les méthodes traditionnelles échouent, il devient alors naturel de se tourner vers des techniques de résolution approchée. Les métaheuristiques jouent, aujourd'hui, un rôle primordial dans la résolution des problèmes d'optimisation. Ces techniques sont devenues, en quelques années, des outils incoutournables et performants. Dans cette synthèse, nous présentons un panorama des métaheuristiques classiques (méthodes de descente, recuit simulé, recherche tabou, algorithmes génétiques), de certaines moins connues (recherche à voisinages variables, GRASP, iterated local search, guided local search, colonies de fourmis) et de techniques avancées (algorithmes mémétiques, scatter search, GA|PM). Pour toutes ces méthodes, nous analysons les facteurs d'intensification et de diversification présents, les particularités de chacune d'elle et notre retour d'expérience sur les applications que nous avons traités. De cette analyse, nous pouvons proposer ce que sont, selon nous, les caractéristiques indispensables à une bonne métaheuristique.

Le problème de planification de trajectoire des bras manipulateurs redondants est largement étudié dans la littérature. Sa résolution nécessite la prise en compte d'un certain nombre de contraintes, qui sont : • le calcul des différentes configurations par lesquelles le robot doit passer ; • l'obtention de courbes lisses (vitesses, accélérations, jerks).La prise en compte de ces deux contraintes dans la démarche de résolution peut se faire de deux manières différentes. La première consiste à supposer au préalable que les différentes courbes suivent des trajectoires lisses (utilisation de fonctions polynomiales ou trigonométriques). La résolution aura pour objectif de calculer les paramètres de chacune des courbes. La deuxième technique consiste à traiter les deux contraintes séparément. Ainsi, on calcule les différentes configurations, puis on procède à une interpolation. Outre ces deux contraintes, on doit aussi résoudre le problème de redondance du robot et la manière de l'exploiter. La première partie de cette thèse est ainsi consacrée à l'étude de cette problématique. La démarche de résolution proposée repose entièrement sur des algorithmes d'optimisation. Les deux contraintes citées précédemment étant traitées séparément, il devient aisé de prendre en compte davantage de critères dans le problème d'optimisation. Ainsi, de nouvelles formulations sont proposées. Ces dernières font appel aux techniques d'optimisation hiérarchique, afin de faciliter le traitement de la redondance, qui est exploitée pour l'évitement d'obstacles et les singularités du robot. Vu la complexité de ces formulations, nous avons préconisé une démarche de résolution approchée, qui fait appel aux métaheuristiques d'optimisation, en particulier les algorithmes génétiques. La validation de la démarche proposée est faite sur le modèle du robot Neuromate. La deuxième partie de cette thèse est consacrée à une application avec le robot Neuromate. Plus particulièrement, nous nous sommes intéressés à l'opération de craniotomie avec le robot Neuromate. L'objectif est de réaliser une petite ouverture au niveau du crâne humain afin que le chirurgien puisse glisser des instruments pour traiter des maladies affectant le cerveau. Réalisée par le chirurgien lui-même, sans assistance robotique, cette opération est très délicate, du fait du manque de précision et de l'allongement du temps d'intervention. Les risques d'aggravation sont particulièrement élevés si la zone d'intervention est proche des veines ou située dans des régions qui ont une fonction importante (région motrice ou région de langage, par exemple). La démarche classique de la craniotomie assistée fait appel à la co-manipulation, qui contraint le chirurgien à participer à l'action, et donc à fournir des efforts. Dans ce travail, une autre démarche est proposée, basée sur l'intégration au robot Neuromate d'un système d'usinage à grande vitesse. Des tests ont été réalisés sur des plaques en polyamide dont les caractéristiques mécaniques sont proches de celles du crâne / The problem of trajectory planning is largely studied in the literature. In order to solve this problem, we need to take into account two important constraints, which are : • the computation of the different configurations in which the robot must pass ; • the smoothness of the resulting curves (velocities, accelerations, jerks).Taking both constraints into consideration can be done in two different ways. The first one is to suppose that all the curves are smooth (using polynomial or trigonometric functions) and then, the aim of the resolution is to find the coefficient of each of them. The second way is to deal the constraints separately. Thus, we compute in first the different configurations in which the robot must pass. After that, we compute the whole curve by interpolation. Adding to the constraints mentioned before, we have to solve the problem of the redundancy of the robot. The first part of this thesis is then devoted to the study of this problem. The proposed solving technique is entirely based on optimization algorithms. The two constraints cited above are treated separately, which allows to take more criteria into account. Thus, new formulations are proposed. They are based on the hierarchical optimization problem, which facilitates handling of the redundancy which is used for the obstacle and the singularities avoidance. Because of the high complexity of the proposed formulations, we chose to use metaheuristics to resolve them, especially the genetic algorithms. We validated the proposed technique on the model of the Neuromate robot. The second part of this thesis is devoted to an application achieved with the Neuromate robot. The procedure of craniotomy is used to perform a very small hole in the human skull in order to allow the surgeon to introduce medical instruments, to take care of some illness that affects brain. Achieved by the surgeon himself, without any robotics aid, this operation is very delicate, because of its lack of precision and increase of processing time. The risks are particularly high if the area of intervention is near the veins. The classical solving technique is based on the co-manipulation principle, which means that the surgeon participates in the action and then, provides an effort. In this work, another solving technique is proposed. It is based on the integration of a machining system with the Neuromate robot. The tests are achieved on plates made of polyamide of which the mechanical characteristics are near to those of the human skull

Cette thèse porte sur la modélisation et la résolution de différents problèmes de tournées de véhicules et plus particulièrement sur des problèmes de transport de personnes. Ces problèmes, demandent, entre autre, de respecter une qualité de service minimale pour les solutions proposées. Pour résoudre ces problèmes, plusieurs méthodes d'optimisation de type métaheuristique sont proposées pour obtenir des solutions de bonne qualité dans des temps raisonnables. Trois problèmes sont traités successivement : le DARP, le TDVRP, le SDARP. Le premier est un problème de transport à la demande (DARP - Dial-A-Ride Problem) qui est le problème de transport de personnes le plus connu de la littérature. Il est proposé dans ce chapitre une méthode de type ELS qui a été comparée aux meilleures méthodes publiées. Les tests montrent que la méthode ELS est compétitive en termes de temps de calcul et de qualité des résultats. Le deuxième problème est une extension du problème de tournées de véhicules (VRP - Vehicle Routing Problem) dans lequel les temps de trajet entre les sommets varient au cours de la journée (TDVRP - Time Dependent Vehicle Routing Problem). Dans ce problème, une distinction existe entre les temps de conduite et les temps de travail des chauffeurs. La différence entre les deux correspond aux temps de pause. Ils sont utilisés ici durant les tournées pour éviter aux chauffeurs de conduire durant les périodes à fort ralentissement du trafic. La méthode proposée permet entre autre de positionner stratégiquement ces pauses afin de réduire le temps de conduite et de proposer de nouvelles solutions. Le dernier problème traité concerne la résolution d'un DARP stochastique. Dans ce problème, les temps de trajet entre les clients ne sont plus déterministes, et ils sont modélisés par une loi de probabilité. L'objectif est de déterminer des solutions robustes aux fluctuations des temps de trajets sur les arcs. Une première approche a permis de calculer des solutions robustes qui ont une probabilité importante d'être réalisables, une seconde approche a permis de générer un ensemble de solutions offrant un équilibre entre la robustesse et le coût. / In this thesis, we are interested in modeling and solving various vehicle routing problems (VRP), especially passenger transportation problems. These problems aim at finding solutions which guarantee a required quality of service. Several metaheuristics are proposed to obtain high quality solutions within reasonable time. Three problems are addressed: the Dial-A-Ride Problem (DARP), the Time-Dependent Vehicle Routing Problem (TDVRP) and the Stochastic DARP (SDARP). The DARP is a well-known on-demand transportation problem. We propose an Evolutionary Local Search (ELS) method. It relies on a new randomized constructive heuristic and on adaptive probabilities for selecting neighborhood structures. This approach is compared with existing methods on classical instances. Results show the interest of the proposed method. The TDVRP is an extension of VRP in which the transportation time varies throughout the day. The driving time is separated from the drivers working time and the difference corresponds to the resting time. The resting time is used to avoid driving during highly congested periods. The proposed method set these resting times in order to reduce the driving time. Hence new solutions avoiding congestion as much as possible are proposed. In the SDARP, the travel time between clients is stochastic and thus follows a probability distribution. The objective is to compute robust solutions, i.e. solutions which handle variations of the transportation time. Two approaches are proposed for this problem. The first one produces robust solutions that have a significant probability of staying feasible. The second one generates a set of compromise solutions, balancing the robustness and the cost.

La planification tactique consiste à élaborer des plans de production afin de répondre au mieux à la demande, à un moindre coût. Traditionnellement, cette planification est divisée en trois plans principaux : le Plan Industriel et Commercial (PIC), le Plan Directeur de Production (PDP) et le Calcul des Besoins Net (CBN). Pour élaborer ces différents plans, des modèles mathématiques dits de " lot-sizing " ont été développés. Cependant, les mécanismes de fusion/acquisition entre entreprises ont considérablement complexifié cette planification en y intégrant les aspects multi-site inhérents au concept de chaîne logistique et il n'existe pas, à notre connaissance, de modèle du domaine et de modèle mathématique de référence pour cette problématique. Dans cette thèse, nous proposons un modèle générique de connaissance pour la planification multi-site à partir duquel un modèle mathématique générique peut être obtenu. Ce dernier permet, par instanciation, de retrouver les principaux modèles de la littérature. Nous proposons également des méthodes d'optimisation efficaces pour l'élaboration des plans de production (PIC, PDP et CBN) dans un contexte mono et multi-site : - Nous nous intéressons à l'obtention du PIC et du PDP dans un contexte mono-site au travers de la résolution du Capacitated Lot Sizing Problem (CLSP) grâce à des métaheuristiques et des bornes inférieures. Par cette technique, nous améliorons des résultats de la littérature. - Nous proposons un modèle mathématique pour la planification d'une chaîne logistique de type " flowshop hybride " obtenu par instanciation du modèle mathématique générique ainsi qu'une méthode d'optimisation efficace pour déterminer les PDPs et CBNs pour cette chaîne logistique. Nous abordons ensuite les problèmes de faisabilité des plans de production ainsi déterminés au niveau opérationnel en utilisant différents couplages entre modèles mathématiques ou modèles de simulation, ce qui permet d'assurer la synchronisation verticale des plans. Enfin, dans le cadre d'un contrat industriel, nous nous intéressons à la mise en place d'une politique de gestion de stock à demande différenciée. Après avoir étudié la faisabilité d'une telle mise en oeuvre dans un contexte industriel, nous avons conçu les algorithmes et développé l'application permettant de calculer les seuils de rationnement de chaque client afin de mener un test grandeur nature de cette politique.