The aim of this thesis is to study coherence and transitivity in coercive subtyping. Among other things, coherence and transitivity are key aspects for a coercive subtyping system to be consistent and for it to be implemented in a correct way. The thesis consists of three major parts. First, I prove that, for the subtyping rules of some parameterised inductive data types, coherence holds and the normal transitivity rule is admissible. Second, the notion of weak transitivity is introduced. The subtyping rules of a large class of parameterised inductive data types are suitable for weak transitivity, but not compatible with the normal transitivity rule. Third, I present a new formulation of coercive subtyping in order to combine incoherent coercions for the type of dependent pairs. There are two subtyping relations in the system and hence a further understanding of coherence and transitivity is needed. This thesis has the first case study of combining incoherent coercions in a single system. The thesis provides a clearer understanding of the subtyping rules for parameterised inductive data types and explains why the normal transitivity rule is not admissible for some natural subtyping rules. It also demonstrates that coherence and transitivity at type level can sometimes be very difficult issues in coercive subtyping. Besides providing theoretical understanding, the thesis also gives algorithms for implementing the subtyping rules for parameterised inductive data types.

Video comprises several modalities and as the richest of all type of media, it is a very important tool and powerful medium of communication. It is used extensively for presenting information and expressing and communicating ideas. Huge amount of video material is generated everyday covering a wide variety of subjects. Without efficient and flexible tools, the usability of this material is quite restricted. In recent years there has been much research addressing the problem of automatic video analysis and retrieval. In this thesis, the problem of automatic video annotation is considered. We develop a multistage decision making system tailored to the domain of sport videos. The first stage is concerned with reaching a compact yet efficient representation of raw video material. One popular approach to this problem is a representation in terms of low-level features. A major limitation is that the stored indexing features are too low-level; they relate directly to the properties of the data. In this stage we opted for a representation in terms of cues. Cues are the result of processing that associates the feature measurements with real-world objects or events. An additional advantage of this approach is that the cues from different types of features are presented in a homogeneous way. The second stage of the system is concerned with the classification of video shots. The set of classes considered relate to some characteristic views that occur frequently in sport videos. The decision making mechanism in this stage is a boosted decision tree which generates hypotheses concerning the semantics of the sports video content given the cues annotation. In contrast to many shot classifiers reported in the literature, the proposed one decomposes the global complex classification problem into a number of simpler tasks. It has the flexibility of choosing different subsets of features (cues in our case) to solve those tasks, thus eliminating unnecessary computations. The final stage of the system is designed to attack the misclassification committed in earlier stages by exploiting temporal context. Misclassification can be due to error in the cue extraction, in the shot classifier or the consequence of a genuine ambiguity as the same visual content may be attributed to different sport categories, depending on the context. The functionality of this stage is realised by a Hidden Markov Model system which bridges the gap between the semantic content categorisation defined by the user and the actual visual content categories. This stage also addresses the grouping of shots into scenes. Experimental results on a database comprising video material from six different events demonstrate that the proposed system is working well.

The development of new digital media (picture, video and audio technologies), cheap storage devices on personal computers, and the introduction of the Internet, have resulted in a significant rise in the amount of information which users can search in order to answer specific questions of interest. This large increase in the availability of information has not been matched by corresponding improvements in searching strategies for locating and identifying relevant information. Whilst users access the Internet to find new information they also frequently use it to locate information which has been useful to them in the past. This is also true on personal computers, where the majority of searches are concerned with re-finding existing information. Traditional Information Retrieval and Internet search technologies return a large number of results, many of which are not relevant. These query techniques utilize keywords (often in the form of Regular Expressions) and Boolean expressions to answer user requests. The queries are simply not expressive enough. This thesis proposes a new search strategy, which depends upon the use of contextual information when formulating queries.

Beaucoup de problèmes dans le monde réel ont une nature dynamique et peuvent être modélisés comme des problèmes dynamiques d'optimisation combinatoire. Cependant, les travaux de recherches sur l'optimisation dynamique se concentrent essentiellement sur les problèmes d'optimisation continue et ils ciblent rarement les problèmes combinatoires. Une des applications dans le domaine des problèmes dynamiques combinatoires ayant reçu un intérêt croissant au cours de ces dernières décennies est le système de transport en ligne où dynamique. Un problème typique de ce domaine est le Problème Dynamique de Tournées de Véhicules (PDTV). Dans ce dernier, le dynamisme peut être attribué à plusieurs facteurs (conditions météorologiques, nouvelle commande client, annulation d'une commande précédente, véhicule tombant en panne, etc.). Dans un tel problème, les informations ne sont pas complètement connues a priori, mais plutôt révélées au décideur progressivement avec le temps. Par conséquent, les solutions des différentes instances doivent être trouvées au fur et à mesure du temps, simultanément avec les informations entrantes. Ces problèmes font appel à une méthodologie capable de suivre les solutions optimales au cours du temps. Dans cette thèse, le problème dynamique de tournées de véhicules est étudié et le développement de méthodologies générales appelées métaheuristiques pour sa résolution est traité. Leur capacité à s'adapter à l'évolution de l'environnement et leur robustesse sont discutées. Les résultats des expérimentations montrent grâce à des mesures de performance dynamique que nos méthodes sont efficaces sur ce problème et ont donc un grand potentiel pour d'autres problèmes combinatoires dynamiques. / Many problems in the real world have dynamic nature and can be modeled as dynamic combinatorial optimization problems. However, research on dynamic optimization focuses on continuous optimization problems, and rarely targets combinatorial problems. One of the applications in dynamic combinatorial problems that has received a growing interest during the last decades is the on-line or dynamic transportation systems. A typical problem of this domain is the Dynamic Vehicle Routing Problems (DVRPs). In this latter, the dynamism can be attributed to several factors (weather condition, new customer order, cancellation of old demand, vehicle broken down, etc.). In such application, information on the problem is not completely known a priori, but instead is revealed to the decision maker progressively with time. Consequently, solutions for different instances have to be found as time proceeds, concurrently with managing the incoming information. Such problems call for a methodology to track their optimal solutions through time. In this thesis, dynamic vehicle routing problem is addressed and developing general methodologies called metaheuristics to tackle this problem is investigated. Their ability to adapt to the changing environment and their robustness are discussed. Results of experiments demonstrate thanks to dynamic performance measures that our methods are effective on this problem and hence have a great potential for other dynamic combinatorial problems.

Les puces à ADN sont des matrices qui indiquent les niveaux d’expression de milliers de gènes sous plusieurs conditions. L’analyse de ces données consiste à extraire des gènes qui ont un comportement similaire sous certaines conditions. En fait, les informations extraites sont des sous-matrices (biclusters) qui réspectent certaines contraints de cohérence. Le processus d'extraction est appelé biclustering. Dans cette thèse, nous traitons ce problème dans le contexte multiobjectif appliqué à l’analyse des données biologiques. Par conséquent, plusieurs questions liées à la modélisation des problèmes et la conception d’algorithmes ont été abordées. Tout d’abord, une description du problème est revue. En outre, une nouvelle mesure de la cohérence est proposée. En outre, deux modèles multiobjectif sont proposées afin d’extraire des biclusters de différents types. Par ailleurs, ce travail explore différentes métaheuristiques pour résoudre ces modèles . De plus, différentes hybridations entre les différentes métaheuristiques sont pris en compte. De plus, nous avons proposé une nouvelle application de biclustering, à savoir, l’analyse des données GWA. En fait, les données GWA consiste au génotype et le phénotype d’un ensemble d’individus. L’analyse de ces données consiste à trouver des associations entre des variants génétiques et les traits considérés. De ce fait, un modèle multiobjectifs pour le biclustering est proposé. En outre, un métaheuristique hybride est appliqué pour résoudre le modèle proposé. Les résultats expérimentaux, pour les deux applications, démontrent que les méthodes sont efficaces sur et permettent d'extraire des informations importantes. / Microarray data represents the expression levels of thousands of genes under several conditions. its analysis consists on discovering genes that have similar behavior across a subset of conditions. In fact, the extracted informations are submatrices (biclusters) that satisfy a coherence constraint. The process of extracting them is called biclustering. In this thesis, we deal with biclustering task applied to the analysis of biological data. Accordingly, several issues related to problem modeling and algorithms design have been addressed. First, a description of the problem and the different measures of biclusters coherence are reviewed. Furthermore, a new coherence measure allowing identification of all biclusters types with a low complexity is proposed. Additionally, two multiobjective models for biclustering problem are proposed in order to mine biclusters of different types. Besides problems modeling, this work investigates different metaheuristics to solve biclustering problem. Moreover, different hybridizations between different metaheuristics presenting different behaviors are considered. Additionally, we propose a new application of biclustering task, namely, analysis of GWA data. In fact, GWA data consists in genotype and phenotype informations of a set of individuals. Its analysis consists in finding associations between markers and the considered traits. Thus, a multiobjective model for biclustering method is proposed. Moreover, a hybrid metaheuristic is applied to solve the proposed model. Experimental results, for both applications, demonstrate that the proposed approaches are effective and are able to extract relevant informations from the considered data.

Les tournées de service concernent l’organisation de déplacement de personnels vers des clients. Lors de la planification et de l’exécution de tournées de service mono-période, les entreprises sont confrontées aux aléas des temps de service et de parcours. C’est pourquoi, dans cette thèse, nous nous intéressons à une variante du problème de tournées de service, dans laquelle les temps de parcours et de service sont stochastiques. Il s’agit du problème de tournées de service multi-dépôt, incluant fenêtres de temps, temps de service et de parcours stochastiques avec priorité entre les clients (distinction clients obligatoires / clients optionnels). Pour résoudre cette problématique, nous proposons trois méthodes différentes. Dans la première méthode, nous construisons des routes contenant uniquement des clients obligatoires puis nous procédons à l’insertion des clients optionnels. La deuxième méthode est une méthode approchée basée sur la génération de colonnes consistant à générer un ensemble de routes de bonne qualité pour chaque véhicule puis à en sélectionner une par véhicule. La dernière méthode est un algorithme de branch and price dans lequel le sous-problème consiste à générer des routes réalisables pour un véhicule donné, tandis que le problème maître permet de sélectionner des routes en s’assurant que la priorité des clients est respectée. Après chacune de ces méthodes, afin d’évaluer la qualité de ces solutions face aux aléas, nous utilisons un algorithme de programmation dynamique et procédons à un ensemble de simulations du déroulement des tournées en temps réel. Nous avons testé ces méthodes sur des problèmes dont les données sont issues du milieu industriel. / The field service routing problem consists in assigning the visits of technicians to clients in order to satisfy their requests for service activities such as maintenance. When planning service routes, companies have to face hazardous travel and service times. Therefore, in this thesis, we deal with a variant of the single-period field service routing problem in which travel and service times are stochastic. It is the field service routing problem with multiple depots, time windows, stochastic travel and service times and priority within customers (distinguishing mandatory and optional customers). To solve this problem, we propose three different methods. In the first one, we first build routes containing only mandatory customers and then, we insert optional customers in these routes. The second one is a heuristic method based on column generation consisting in generating a set of valuable routes for each vehicle and then in selecting one route per vehicle. The last method is a branch and price algorithm, based on the second method, in which the subproblem consists in finding feasible routes for a given vehicle, whereas the master problem consists in selecting routes while ensuring that customer’s priority is respected. After each of these methods, in order to evaluate the quality of these solutions regarding stochasticity, we use a dynamic programming algorithm and we proceed to a set of simulations of the real-time execution of the service activities over the period. All our experimentations have been made on problems coming from realistic data.

Cette thèse porte sur l'optimisation de la conception et des décisions opérationnelles des laboratoires d'analyses médicales. Dans cette thèse, un outil d'aide à la décision comprenant des modèles mathématiques, un algorithme heuristique et un modèle de simulation personnalisé est développé pour aider les décideurs à résoudre les principaux problèmes stratégiques, tactiques et opérationnels en conception et gestion des opérations des laboratoires d'analyses médicales. Dans cette thèse, la sélection des machines et la disposition des instruments sont étudiées en tant que principaux problèmes stratégiques, le problème de configuration des analyseurs en tant que problème tactique et l’affectation, l’aliquotage et l'ordonnancement en tant que principaux problèmes opérationnels. Un modèle de simulation personnalisé et flexible est développé dans FlexSim pour étudier le laboratoire d'analyse médicale conçu à l'aide des résultats de modèles mathématiques et d'un algorithme de layout développés. Le modèle de simulation aide le concepteur à construire et à analyser un laboratoire complet en tenant compte de toutes les principales caractéristiques du système. Cet attribut de simulation permet d'analyser le comportement du système et de déterminer si le système conçu est efficace. Pour vérifier la validité du cadre proposé, les données extraites d’un cas réel sont utilisées. Les résultats de sortie scellent l'applicabilité et l'efficacité du cadre proposé ainsi que la compétence des techniques proposées pour traiter chaque problème d'optimisation. À notre connaissance, cette thèse est l’une des principales études sur l’optimisation des laboratoires d'analyses médicales. / This thesis focuses on the optimization of clinical laboratory design and operating decisions. In this thesis, a decision support tool including mathematical models, a heuristic algorithm and a customized simulation model is developed to aid decision makers for the main strategic, tactical and operational problems in clinical laboratory design and operations management. In this thesis, machine selection and facility layout are studied as the main strategic problems, analyzer configuration problem as the tactical problem, and assignment, aliquoting, and scheduling as the principal operational problems. A customized and flexible simulation model is developed in FlexSim to study the clinical laboratory designed through the outputs of developed mathematical models and layout algorithm. The simulation model helps the designer to construct and analyze a complete clinical laboratory taking into account all major features of the system. This simulation attribute provides the ability to scrutinize the system behaviour and to find out whether the designed system is efficient. Furthermore, simulation model can be fruitful to decide on scheduling, aliquoting and staffing problems through the evaluation of various scenarios proposed by decision maker for each of these problems. To verify the validity of the proposed framework, data extracted from a real case is used. The output results seal on the applicability and the efficiency of the proposed framework as well as competency of proposed techniques to deal with each optimization problem. To the best of our knowledge, this thesis is one of the leading studies on the optimization of clinical laboratories.

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.

In this thesis we show that CBR systems can be constructed from numerical models, so as to improve their usability. It is shown that CBR models may be queried in a flexible manner, and that the user may formulate queries consisting of constraints over both “input” and “output” variables of the numerical model. It is also shown that the constraints may be formulated using either nominal or continuous variables. A generalization of the CBR retrieval process to include constraints over unified “input-output” space is formulated as a framework for the method. The method is illustrated with practical engineering models: the pneumatic conveyor problem and the projectile problem. Comparisons are made on usability of CBR and numerical models for specific problems. It is shown that CBR models can answer questions difficult or impossible to formulate using numerical models, and that CBR models can be faster. The thesis also addresses a latent problem with the general method, which is of importance generally. This is to do with interpolation over nominal values in unified space. A novel method is proposed for interpolation over nominal values, termed Generalised Shepard Nearest Neighbour method (GSNN). GSNN can utilise distance metrics defined on the solution space of a CBR system. The properties and advantages of GSNN are examined in the thesis. A comparison is made with other CBR retrieval methods, using several examples, including the travel domain case base. It is shown that GSNN can out-perform conventional nearest neighbour methods. It is shown that GSNN has advantages in that it can find solutions not in the case base and it can find solutions not in the retrieval set. It is also shown that the performance of GSNN can be improved further by using it in conjunction with a diversity algorithm. The merit of using GSNN as a case selection component is examined, and it is shown that it can give good results in sparse case bases. Finally the thesis concludes with a survey of numerical models where CBR construction can be useful, and where benefits can be expected.

Le développement des technologies de séquençage et de génotypage haut-débit permet de mesurer, pour un individu, une grande quantité d’information génomique.L’objectif de ce travail est, dans le cadre de la sélection génomique animale,de sélectionner un sous-ensemble de marqueurs génétiques pertinents permettant de prédire un caractère quantitatif, dans un contexte où le nombre d’animaux génotypés est largement inférieur au nombre de marqueurs étudiées.Ce manuscrit présente un état de l’art des méthodes actuelles permettant de répondre à la problématique. Nous proposons ensuite de répondre à notre problématique de sélection de variables en régression en grande dimension en combinant approches d’optimisation combinatoire et modèles statistiques. Nous commençons par paramétrer expérimentalement deux méthodes d’optimisation combinatoire, la recherche locale itérée et l’algorithme génétique, combinées avec une régression linéaire multiple et nous évaluons leur pertinence. Dans le contexte de la génomique animale les relations familiales entre animaux sont connues et peuvent constituer une information importante. Notre approche étant flexible, nous proposons une adaptation permettant de prendre en considération ces relations familiales via l’utilisation d’un modèle mixte. Le problème du sur-apprentissage étant particulièrement présent sur nos données dû au déséquilibre important entre le nombre de variables étudiées et le nombre d’animaux disponibles, nous proposons également une amélioration de notre approche permettant de diminuer ce sur-apprentissage.Les différentes approches proposées sont validées sur des données de la littérature ainsi que sur des données réelles de Gènes Diffusion. / Advances in high-throughput sequencing and genotyping technologies allow tomeasure large amounts of genomic information.The aim of this work is dedicated to the animal genomic selection is to select asubset of relevant genetic markers to predict a quantitative trait, in a context wherethe number of genotyped animals is widely lower than the number of markersstudied. This thesis introduces a state-of-the-art of existing methods to address the problem.We then suggest to deal with the variable selection in high dimensional regressionproblem combining combinatorial optimization methods and statistical models.We start by experimentally set two combinatorial optimization methods, theiterated local search and the genetic algorithm, combined with a linear multipleregression and we evaluate their relevance. In the context of animal genomic, familyrelationships between animals are known and can be an important information.As our approach is flexible we suggest an adaptation to consider these familialrelationships through the use of a mixed model. Moreover, the problem of overfittingis particularly present in such data due to the large imbalance between thenumber of variables studied and the number of animals available, so we suggest animprovement of our approach in order to reduce this over-fitting.The different suggested approaches are validated on data from the literature as wellas on real data of Gènes Diffusion.