Made available in DSpace on 2014-12-17T15:47:52Z (GMT). No. of bitstreams: 1 ThatianaCNS_DISSERT.pdf: 1637234 bytes, checksum: 8b38ce4a7a358efe654d9bb1c23c15bc (MD5) Previous issue date: 2010-03-02 / The distribution of petroleum products through pipeline networks is an important problem that arises in production planning of refineries. It consists in determining what will be done in each production stage given a time horizon, concerning the distribution of products from source nodes to demand nodes, passing through intermediate nodes. Constraints concerning storage limits, delivering time, sources availability, limits on sending or receiving, among others, have to be satisfied. This problem can be viewed as a biobjective problem that aims at minimizing the time needed to for transporting the set of packages through the network and the successive transmission of different products in the same pipe is called fragmentation. This work are developed three algorithms that are applied to this problem: the first algorithm is discrete and is based on Particle Swarm Optimization (PSO), with local search procedures and path-relinking proposed as velocity operators, the second and the third algorithms deal of two versions based on the Non-dominated Sorting Genetic Algorithm II (NSGA-II). The proposed algorithms are compared to other approaches for the same problem, in terms of the solution quality and computational time spent, so that the efficiency of the developed methods can be evaluated / A distribui??o de produtos de petr?leo atrav?s de redes de polidutos ? um importante problema que se coloca no planejamento de produ??o das refinarias. Consiste em determinar o que ser? feito em cada est?gio de produ??o dado um determinado horizonte de tempo, no que respeita ? distribui??o de produtos de n?s fonte ? procura de n?s, passando por n?s intermedi?rios. Restri??es relativas a limites de armazenamento, tempo de entrega, disponibilidade de fontes, limites de envio ou recebimento, entre outros, t?m de ser satisfeitas. Este problema pode ser visto como um problema biobjetivo, que visa minimizar o tempo necess?rio para transportar o conjunto de pacotes atrav?s da rede e o envio sucessivo de produtos diferentes no mesmo duto que ? chamado de fragmenta??o. Neste trabalho, s?o desenvolvidos tr?s algoritmos que s?o aplicados a esse problema: o primeiro algoritmo ? discreto e baseia-se na Otimiza??o por Nuvem de Part?culas (PSO), com procedimentos de busca local e path-relinking propostos como operadores de velocidade, o segundo e o terceiro algoritmos tratam de duas vers?es baseadas no Non-dominated Sorting Genetic Algorithm II (NSGA-II). Os algoritmos propostos s?o comparados a outras abordagens para o mesmo problema, em termos de qualidade de solu??o e tempo computacional despendido, a fim de se avaliar a efici?ncia dos m?todos desenvolvidos

Cette thèse s'intéresse à la conception et le développement des techniques de bioinfor- matique qui peuvent faciliter l'utilisation de l'approche metabarcoding pour mesurer la diversité d'espèces. Le metabarcoding peut être utilisé avec le séquencage haut débit pour l'identification d'espèces multiples à partir d'un seul échantillon environnemental. La véritable force du metabarcoding réside dans l'utilisation de barcode marqueurs choisi pour une étude particulière et l'identification d'espèces ou des taxons peut être réalisé avec des marqueurs soigneusement conçu. Avec l'avancement des techniques haut débit de séquençage, une énorme quantité des données de séquences est produit qui contient un nombres substantiel des mutations. Ces mutations posent un grand problème pour les estimations correctes de la biodiversité et pour le d'assignation de taxon. Les trois problèmes majeurs dans le domaine de la bioinformatique que j'ai abordés dans cette thèse sont: i) évaluer la qualité d'une barcode marker , ii) concevoir des nouveaux région barcode et iii) d'analyser les données de séquençage pour traiter les erreurs et éliminer le bruit en séquences. Pour évaluer la qualité d'un barcode marker, on a développé deux mesures quantita- tive,formelle: la couverture (Bc) et la spécificité (Bs). La couverture donne une mesure de universalité d'une pairs de primer pour amplifier un large nombre de taxa, alors que la spécificité donne une mesure de capacité à discriminer entre les différents taxons. Ces mesures sont très utiles pour le classement des barcode marker et pour sélectionner les meilleurs markers. Pour trouver des nouveaux région barcode notamment pour les applications metabarcod- ing, j'ai développé un logiciel, ecoPrimers3. Basé sur ces deux mesures de qualité et de l'information taxinomique intégré, ecoPrimers nous permet de concevoir barcode markers pour n'importe quel niveau taxonomique . En plus, avec un grand nombre de paramètres réglables il nous permet de contrôler les propriétés des amorces. Enfin, grâce a des algorithmes efficaces et programmé en langage C, ecoPrimers est suffisamment efficace pour traiter des grosses bases de données, y compris génomes bactériens entièrement séquencés. Enfin pour traiter des erreurs présentes dans les données de séquencage , nous avons analysé un ensemble simple d'échantillons de PCR obtenus à partir de l'analyse du régime alimentaire de Snow Leopard. En mesurant les corrélations entre les différents paramètres des erreurs, nous avons observé que la plupart des erreurs sont produites pendant l'amplification par PCR. Pour détecter ces erreurs, nous avons développé un algorithme utilisant les graphes, qui peuvent différencier les vrai séquences des erreurs induites par PCR. Les résultats obtenus à partir de cet algorithme a montré que les données de-bruitée a donnent une estimation réaliste de la diversité des espèces étudiées dans les Alpes françaises. / This thesis is concerned with the design and development of bioinformatics techniques that can facilitate the use of metabarcoding approach for measuring species diversity. Metabarcoding coupled with next generation sequencing techniques have a strong po- tential for multiple species identification from a single environmental sample. The real strength of metabarcoding resides in the use of barcode markers chosen for a particular study. The identification at species or higher level taxa can be achieved with carefully designed barcode markers. Moreover with the advent of high throughput sequencing techniques huge amount of sequence data is being produced that contains a substantial level of mutations. These mutations pose a problem for the correct estimates of biodi- versity and for the taxon assignation process. Thus the three major challenges that we addressed in this thesis are: evaluating the quality of a barcode region, designing new barcodes and dealing with errors occurring during different steps of an experiment. To assess the quality of a barcode region we have developed two formal quantitative mea- sures called barcode coverage (Bc) and barcode specificity (Bs). Barcode coverage is concerned with the property of a barcode to amplify a broad range of taxa, whereas barcode specificity deals with its ability to discriminate between different taxa. These measures are extremely useful especially for ranking different barcodes and selecting the best markers. To deal with the challenge of designing new barcodes for metabarcoding applications we have developed an efficient software called ecoPrimers. Based on the above two quality measures and with integrated taxonomic information, ecoPrimers1 enables us to design primers and their corresponding barcode markers for any taxonomic level. Moreover with a large number of tunable parameters it allows us to control the properties of primers. Finally, based on efficient algorithms and implemented in C language, ecoPrimers is efficient enough to deal with large data bases including fully sequenced bacterial genomes. Finally to deal with errors present in DNA sequence data, we have analyzed a simple set of PCR samples obtained from the diet analysis of snow leopard. We grouped closely related sequences and by measuring the correlation between different parameters of mutations, we have shown that most of the errors were introduced during PCR amplification. In order to deal with such errors, we have further developed an algorithm using graphs approach, that can differentiate true sequences from PCR induced errors. The results obtained from this algorithm showed that de-noised data gave a realistic estimate of species diversity studied in French Alpes. This algorithm is implemented in program obiclean.

Made available in DSpace on 2015-03-03T15:48:41Z (GMT). No. of bitstreams: 1 MatheusSM_TESE.pdf: 3657538 bytes, checksum: 05bf71663b044728a1e70b6db57b834e (MD5) Previous issue date: 2014-03-21 / This paper introduces a new variant of the Traveling Car Renter Problem, named Prizecollecting Traveling Car Renter Problem. In this problem, a set of vertices, each associated with a bonus, and a set of vehicles are given. The objective is to determine a cycle that visits some vertices collecting, at least, a pre-defined bonus, and minimizing the cost of the tour that can be traveled with different vehicles. A mathematical formulation is presented and implemented in a solver to produce results for sixty-two instances. The proposed problem is also subject of an experimental study based on the algorithmic application of four metaheuristics representing the best adaptations of the state of the art of the heuristic programming.We also provide new local search operators which exploit the neighborhoods of the problem, construction procedures and adjustments, created specifically for the addressed problem. Comparative computational experiments and performance tests are performed on a sample of 80 instances, aiming to offer a competitive algorithm to the problem. We conclude that memetic algorithms, computational transgenetic and a hybrid evolutive algorithm are competitive in tests performed / Este trabalho apresenta uma nova variante do problema do Caixeiro Alugador ainda n?o descrita na literatura, denominada de Caixeiro Alugador com Coleta de Pr?mios. Neste problema s?o disponibilizados um conjunto de v?rtices, cada um com um b?nus associado e um conjunto de ve?culos. O objetivo do problema ? determinar um ciclo que visite alguns v?rtices coletando, pelo menos, um b?nus pr?-de nido e minimizando os custos de viagem atrav?s da rota, que pode ser feita com ve?culos de diferentes tipos. ? apresentada uma formula??o matem?tica e implementada em um solver produzindo resultados em sessenta e duas inst?ncias. O problema proposto tamb?m ? objeto de um estudo algor?tmico experimental baseado na aplica??o de quatro metaheur?sticas de solu??o, representando adapta??es do melhor do estado da arte em programa??o heur?stica. Nesse trabalho tamb?m apresentamos a constitui??o de novos operadores que exploram as vizinhan?as do problema, procedimentos construtivos e adapta??es, criados especifi camente para o problema abordado. Experimentos computacionais comparativos e testes de desempenho s?o realizados sobre uma amostra de 80 inst?ncias, visando oferecer um algoritmo de solu??o competitivo para o problema. Conclui-se que algoritmos com abordagem mem?tica, transgen ?tica e evolucion?ria h?brida obtiveram resultados competitivos nos testes efetuados. Palavras-chave: Caixeiro Alugador com Coleta de Pr?mios. Metaheur?sticas. GRASP/VNS. Algoritmo Mem?tico. Transgen?tica Computacional. Computa??o Evolucion?ria

La prise de décision est une partie intégrante de notre vie quotidienne où le décideur est confronté à des problèmes composés de plusieurs objectifs habituellement contradictoires. Dans ce travail, nous traitons des problèmes d'optimisation multiobjectif dans des espaces de recherche continus ou discrets. Nous avons développé plusieurs nouveaux algorithmes basés sur les métaheuristiques hybrides évolutionnaires, en particulier sur l'algorithme MOEA/D. Nous avons proposé l'algorithme HEMH qui utilise l'algorithme DM-GRASP pour construire une population initiale de solutions de bonne qualité dispersées le long de l'ensemble des solutions Pareto optimales. Les résultats expérimentaux montrent la supériorité de toutes les variantes hybrides proposées sur les algorithmes originaux MOEA/D et SPEA2. Malgré ces bons résultats, notre approche possède quelques limitations, levées dans une version améliorée de HEMH : HEMH2 et deux autres variantes HEMHde et HEMHpr. Le Adaptive Binary DE inclus dans les HEMH2 et HEMHde a de meilleures capacités d'exploration qui pallient aux capacités de recherche locale contenues dans la HEMH, HEMH2 et HEMHde. Motivés par ces résultats, nous avons proposé un nouvel algorithme baptisé HESSA pour explorer un espace continu de recherche où le processus de recherche est réalisé par différentes stratégies de recherche. Les résultats expérimentaux montrent la supériorité de HESSA à la fois sur MOEA/D et dMOPSO. Tous les algorithmes proposés ont été vérifiés, testé et comparés à certaines méthodes MOEAs. Les résultats expérimentaux montrent que toutes les propositions sont très compétitives et peuvent être considérés comme une alternative fiable / Many real-world decision making problems consist of several conflicting objectives, the solutions of which is called the Pareto-optimal set. Hybrid metaheuristics proved their efficiency in solving these problems. They tend to enhance search capabilities by incorporating different metaheuristics. Thus, we are concerned with developing new hybrid schemes by incorporating different strategies with exploiting the pros and avoiding the drawback of the original ones. First, HEMH is proposed in which the search process includes two phases DMGRASP obtains an initial set of efficient solutions in the 1st phase. Then, greedy randomized path-relinking with local search or reproduction operators explore the non-visited regions. The efficient solutions explored over the search are collected. Second, a comparative study is developed to study the hybridization of different metaheuristics with MOEA/D. The 1st proposal combines adaptive discrete differential Evolution with MOEA/D. The 2nd combines greedy path-relinking with MOEA/D. The 3rd and the 4th proposals combine both of them in MOEA/D. Third, an improved version of HEMH is presented. HEMH2 uses inverse greedy to build its initial population. Then, differential evolution and path-relink improves these solutions by investigating the non-visited regions in the search space. Also, Pareto adaptive epsilon concept controls the archiving process. Motivated by the obtained results, HESSA is proposed to solve continuous problems. It adopts a pool of search strategies, each of which has a specified success ratio. A new offspring is generated using a randomly selected one. Then, the success ratios are adapted according to the success of the generated offspring. The efficient solutions are collected to act as global guides. The proposed algorithms are verified against the state of the art MOEAs using a set of instances from literature. Results indicate that all proposals are competitive and represent viable alternatives

Submitted by Franciele Moreira (francielemoreyra@gmail.com) on 2018-10-30T13:30:59Z No. of bitstreams: 2 Dissertação - Diogo Machado de Freitas - 2018.pdf: 1477764 bytes, checksum: 73759c5ece96bf48ffd4d698f14026b9 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-10-30T13:41:38Z (GMT) No. of bitstreams: 2 Dissertação - Diogo Machado de Freitas - 2018.pdf: 1477764 bytes, checksum: 73759c5ece96bf48ffd4d698f14026b9 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-10-30T13:41:38Z (GMT). No. of bitstreams: 2 Dissertação - Diogo Machado de Freitas - 2018.pdf: 1477764 bytes, checksum: 73759c5ece96bf48ffd4d698f14026b9 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-09-24 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Fault Localization is one stage of the software life cycle, which demands important resources such as time and effort spent on a project. There are several initiatives towards the automation of the fault localization process and the reduction of the associated resources. Many techniques are based on heuristics that use information obtained (spectrum) from the execution of test cases, in order to measure the suspiciousness of each program element to be defective. Spectrum data generally refers to code coverage and test results (positive or negative). The present work presents two approaches based on the Genetic Programming algorithm for the problem of Fault Localization: a method to compose a new heuristic from a set of existing ones; and a method for constructing heuristics based on data from program mutation analysis. The innovative aspects of both methods refer to the joint investigation of: (i) specialization of heuristics for certain programs; (ii) application of an evolutionary approach to the generation of heuristics with non-linear equations; (iii) creation of heuristics based on the combination of traditional heuristics; (iv) use of coverage and mutation spectra extracted from the test activity; (v) analyzing and comparing the efficacy of methods that use coverage and mutation spectra for fault localization; and (vi) quality analysis of the mutation spectra as a data source for fault localization. The results have pointed to the competitiveness of both approaches in their contexts. / Localização de Defeitos é uma etapa do ciclo de vida de software, que demanda recursos importantes tais como o tempo e o esforço gastos em um projeto. Existem diversas iniciativas na direção da automação do processo de localização de defeitos e da redução dos recursos associados. Muitas técnicas são baseadas heurísticas que utilizam informação obtida (espectro) a partir da execução de casos de teste, visando a medir a suspeita de cada elemento de programa para ser defeituoso. Os dados de espectro referem-se, em geral, à cobertura de código e aos resultados dos teste (positivo ou negativo). O presente trabalho apresenta duas abordagens baseadas no algoritmo Programação Genética para o problema de Localização de Defeitos: um método para compor automaticamente novas heurísticas a partir de um conjunto de heurísticas existentes; e um método para a construção de heurísticas baseadas em dados oriundos da análise de mutação de programas. Os aspectos inovadores de ambos os métodos referem-se à investigação conjunta de: (i) especialização de heurísticas para determinados programas; (ii) aplicação de abordagem evolutiva para a geração de heurísticas com equações não lineares; (iii) criação de heurísticas a partir da combinação de heurísticas tradicionais; (iv) uso de espectro de cobertura e de mutação extraídos da atividade de teste; (v) análise e comparação da eficácia de métodos que usam os espectros de cobertura e de mutação para a localização de defeitos; e (vi) análise da qualidade dos espectros de mutação como fonte de dados para a localização de defeitos. Os resultados apontaram competitividade de ambas as abordagens em seus contextos.

In this thesis, our focus is on low-complexity, high-performance detection algorithms for multi-antenna communication receivers. A key contribution in this thesis is the demonstration that efficient algorithms from metaheuristics and machine learning can be gainfully adapted for signal detection in multi- antenna communication receivers. We first investigate a popular metaheuristic known as the reactive tabu search (RTS), a combinatorial optimization technique, to decode the transmitted signals in large-dimensional communication systems. A basic version of the RTS algorithm is shown to achieve near-optimal performance for 4-QAM in large dimensions. We then propose a method to obtain a lower bound on the BER performance of the optimal detector. This lower bound is tight at moderate to high SNRs and is useful in situations where the performance of optimal detector is needed for comparison, but cannot be obtained due to very high computational complexity. To improve the performance of the basic RTS algorithm for higher-order modulations, we propose variants of the basic RTS algorithm using layering and multiple explorations. These variants are shown to achieve near-optimal performance in higher-order QAM as well. Next, we propose a new receiver called linear regression of minimum mean square error (MMSE) residual receiver (referred to as LRR receiver). The proposed LRR receiver improves the MMSE receiver by learning a linear regression model for the error of the MMSE receiver. The LRR receiver uses pilot data to estimate the channel, and then uses locally generated training data (not transmitted over the channel) to find the linear regression parameters. The LRR receiver is suitable for applications where the channel remains constant for a long period (slow-fading channels) and performs well. Finally, we propose a receiver that uses a committee of linear receivers, whose parameters are estimated from training data using a variant of the AdaBoost algorithm, a celebrated supervised classification algorithm in ma- chine learning. We call our receiver boosted MMSE (B-MMSE) receiver. We demonstrate that the performance and complexity of the proposed B-MMSE receiver are quite attractive for multi-antenna communication receivers.

In ant societies, and, more in general, in insect societies, the activities of the individuals, as well as of the society as a whole, are not regulated by any explicit form of centralized control. On the other hand, adaptive and robust behaviors transcending the behavioral repertoire of the single individual can be easily observed at society level. These complex global behaviors are the result of self-organizing dynamics driven by local interactions and communications among a number of relatively simple individuals.<p><p>The simultaneous presence of these and other fascinating and unique characteristics have made ant societies an attractive and inspiring model for building new algorithms and new multi-agent systems. In the last decade, ant societies have been taken as a reference for an ever growing body of scientific work, mostly in the fields of robotics, operations research, and telecommunications.<p><p>Among the different works inspired by ant colonies, the Ant Colony Optimization metaheuristic (ACO) is probably the most successful and popular one. The ACO metaheuristic is a multi-agent framework for combinatorial optimization whose main components are: a set of ant-like agents, the use of memory and of stochastic decisions, and strategies of collective and distributed learning.<p><p>It finds its roots in the experimental observation of a specific foraging behavior of some ant colonies that, under appropriate conditions, are able to select the shortest path among few possible paths connecting their nest to a food site. The pheromone, a volatile chemical substance laid on the ground by the ants while walking and affecting in turn their moving decisions according to its local intensity, is the mediator of this behavior.<p><p>All the elements playing an essential role in the ant colony foraging behavior were understood, thoroughly reverse-engineered and put to work to solve problems of combinatorial optimization by Marco Dorigo and his co-workers at the beginning of the 1990's.<p><p>From that moment on it has been a flourishing of new combinatorial optimization algorithms designed after the first algorithms of Dorigo's et al. and of related scientific events.<p><p>In 1999 the ACO metaheuristic was defined by Dorigo, Di Caro and Gambardella with the purpose of providing a common framework for describing and analyzing all these algorithms inspired by the same ant colony behavior and by the same common process of reverse-engineering of this behavior. Therefore, the ACO metaheuristic was defined a posteriori, as the result of a synthesis effort effectuated on the study of the characteristics of all these ant-inspired algorithms and on the abstraction of their common traits.<p><p>The ACO's synthesis was also motivated by the usually good performance shown by the algorithms (e.g. for several important combinatorial problems like the quadratic assignment, vehicle routing and job shop scheduling, ACO implementations have outperformed state-of-the-art algorithms).<p><p>The definition and study of the ACO metaheuristic is one of the two fundamental goals of the thesis. The other one, strictly related to this former one, consists in the design, implementation, and testing of ACO instances for problems of adaptive routing in telecommunication networks.<p><p>This thesis is an in-depth journey through the ACO metaheuristic, during which we have (re)defined ACO and tried to get a clear understanding of its potentialities, limits, and relationships with other frameworks and with its biological background. The thesis takes into account all the developments that have followed the original 1999's definition, and provides a formal and comprehensive systematization of the subject, as well as an up-to-date and quite comprehensive review of current applications. We have also identified in dynamic problems in telecommunication networks the most appropriate domain of application for the ACO ideas. According to this understanding, in the most applicative part of the thesis we have focused on problems of adaptive routing in networks and we have developed and tested four new algorithms.<p><p>Adopting an original point of view with respect to the way ACO was firstly defined (but maintaining full conceptual and terminological consistency), ACO is here defined and mainly discussed in the terms of sequential decision processes and Monte Carlo sampling and learning.<p><p>More precisely, ACO is characterized as a policy search strategy aimed at learning the distributed parameters (called pheromone variables in accordance with the biological metaphor) of the stochastic decision policy which is used by so-called ant agents to generate solutions. Each ant represents in practice an independent sequential decision process aimed at constructing a possibly feasible solution for the optimization problem at hand by using only information local to the decision step.<p>Ants are repeatedly and concurrently generated in order to sample the solution set according to the current policy. The outcomes of the generated solutions are used to partially evaluate the current policy, spot the most promising search areas, and update the policy parameters in order to possibly focus the search in those promising areas while keeping a satisfactory level of overall exploration.<p><p>This way of looking at ACO has facilitated to disclose the strict relationships between ACO and other well-known frameworks, like dynamic programming, Markov and non-Markov decision processes, and reinforcement learning. In turn, this has favored reasoning on the general properties of ACO in terms of amount of complete state information which is used by the ACO's ants to take optimized decisions and to encode in pheromone variables memory of both the decisions that belonged to the sampled solutions and their quality.<p><p>The ACO's biological context of inspiration is fully acknowledged in the thesis. We report with extensive discussions on the shortest path behaviors of ant colonies and on the identification and analysis of the few nonlinear dynamics that are at the very core of self-organized behaviors in both the ants and other societal organizations. We discuss these dynamics in the general framework of stigmergic modeling, based on asynchronous environment-mediated communication protocols, and (pheromone) variables priming coordinated responses of a number of ``cheap' and concurrent agents.<p><p>The second half of the thesis is devoted to the study of the application of ACO to problems of online routing in telecommunication networks. This class of problems has been identified in the thesis as the most appropriate for the application of the multi-agent, distributed, and adaptive nature of the ACO architecture.<p><p>Four novel ACO algorithms for problems of adaptive routing in telecommunication networks are throughly described. The four algorithms cover a wide spectrum of possible types of network: two of them deliver best-effort traffic in wired IP networks, one is intended for quality-of-service (QoS) traffic in ATM networks, and the fourth is for best-effort traffic in mobile ad hoc networks.<p><p>The two algorithms for wired IP networks have been extensively tested by simulation studies and compared to state-of-the-art algorithms for a wide set of reference scenarios. The algorithm for mobile ad hoc networks is still under development, but quite extensive results and comparisons with a popular state-of-the-art algorithm are reported. No results are reported for the algorithm for QoS, which has not been fully tested. The observed experimental performance is excellent, especially for the case of wired IP networks: our algorithms always perform comparably or much better than the state-of-the-art competitors.<p><p>In the thesis we try to understand the rationale behind the brilliant performance obtained and the good level of popularity reached by our algorithms. More in general, we discuss the reasons of the general efficacy of the ACO approach for network routing problems compared to the characteristics of more classical approaches. Moving further, we also informally define Ant Colony Routing (ACR), a multi-agent framework explicitly integrating learning components into the ACO's design in order to define a general and in a sense futuristic architecture for autonomic network control.<p><p>Most of the material of the thesis comes from a re-elaboration of material co-authored and published in a number of books, journal papers, conference proceedings, and technical reports. The detailed list of references is provided in the Introduction.<p><p><p> / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

Dans cette thèse nous nous sommes intéressés à l’extension du problème job-shop en ajoutant la contrainte du transport des jobs entre les différentes machines. Dans cette étude nous avons retenu l’existence de deux types de robots, les robots de capacité de chargement unitaire (capacité=1 veut dire qu’un robot ne peut transporter qu’un seul job à la fois) et les robots de capacité de chargement non unitaire (capacité>1 veut dire qu’un robot peut transporter plusieurs job à la fois). Nous avons traité cette extension en deux étapes. Ainsi, la première étape est consacrée au problème du job-shop avec plusieurs robots de capacité de chargement unitaire et en seconde étape en ajoutant la capacité de chargement non unitaire aux robots. Pour les deux problèmes étudiés nous avons proposé :• Une modélisation linéaire ;• Une modélisation sous forme de graphe disjonctif ;• Plusieurs heuristiques de construction de solutions ;• Plusieurs recherches locales qui améliorent les solutions obtenues ;• Utilisation des algorithmes génétiques / mémétiques comme schéma global d’optimisation ;• De nouveaux benchmarks, des résultats de test de nos approches sur nos benchmarks et ceux de la littérature et ces résultats sont commentés et comparés à ceux de la littérature. Les résultats obtenus montrent la pertinence de notre modélisation ainsi que sa qualité. / In this thesis we are interested in the extension of the job-shop problem by adding the constraint of transport of jobs between different machines. In this study we used two types of robots, robots with unary loading capacity (capacity =1 means that each robot can carry only one job at a time,) and robots with non unary loading capacities (robot with capacity >1 can carry more than one job at time). Thus, the first step is devoted to the problem of job-shop with several robots with unary loading capacity. In the second step we extend the problem by adding the non-unary loading capacities to the robots. For both problems studied we have proposed :• A linear modeling ;• A Disjunctive graph Model ;• Several constructive heuristics ;• Several local searches methods that improve the obtained solutions ;• Use of genetic / memetic algorithms as a global optimization schema ;• New benchmarks, test results of our approaches on our benchmarks and those present in the literature and these results are commented and compared with those of literature. The results show the relevance of our model and its quality.

[EN] In this Thesis, we analyze an industry type that has two basic features: Its products are distributed in a geographic level and it reuses material after that is consumed to made new products. Because of these features, it represents a logistics challenge. This kind of supply chains is characterized also by having various stages that permit to carry the products from facility plants to the final customer. First, it is analyzed the supply chain structure, from production, in facility plants to the final customer by retailers, downstream; and from the customer, when returnable materials are liberated, classification and transport upstream to facility plants , where are prepared and used many times, until the end of their usable life. The attention focus is the integration of two fundamental functions of the supply chain management, in this case, production planning and distribution planning including the collection of reusable materials. It is precise to plan the production to satisfy retailers demand and to the procurement of returnable materials which after being consumed return to the process. It is made a bibliographical review about production planning, reverse logistics and vehicle routing and, it is built mathematical programming models to make decisions in production planning (in facility plants), inventories planning (in all the supply chain), and the deliveries that should be done in both senses in their respective routes. As a result of this research, there are three models of Mixed Integer Linear Programming: -Production planning model: Mathematical model which represents all the facilities in each one of the levels of the supply chain and their geographical localization. It lets to determine production and stock levels and delivery quantities in order to satisfy the demands in a planning horizon of several periods. This model has capacity constraints for both production and storage, constraints of demand, compatibility between products and facilities because not all the products can be in all facilities, and constraints of direct deliveries among determinate nodes in the supply chain (particularly between plants and retailers), especially. -Vehicle routing model: mathematical model that represents products distribution from different source nodes to destine nodes, it use a heterogeneous fleet, in a time period. One of the model assumptions is that a node acts as product emitting or recipient (facility plants or retailers). However, an intermediate node can take one of these roles depending if is the origin or destine of goods. This model has fleet use constraints, volume, and mass capacity vehicle constraints, fluxes in the supply chain. A vehicle can visit several destine nodes after leave from a source node, and a node can be visited by one or more vehicles (because of compatibility conditions between products and nodes or by economical aspects) and there are soft and strong time windows. -Integrated logistics and production management model: It is a model that join the two previous models, because of it, it is possible to plan production, inventories, and vehicle routing for a horizon time of several periods. Three proposed models have the objective of minimizing the total cost and are evaluated with testing instances. The Models were built using Gurobi 6.5.1 optimization model and Python2.7 pro- gramming language. Moreover, it was built a constructive heuristics and a genetic algorithm using Python programming language and Pyevolve software, as an alternative to solving routing vehicles, to reduce execution time. / [ES] En esta tesis se analiza un tipo de industria en el que: sus productos son distribuidos ampliamente a nivel geográfico y emplean elementos que una vez usados regresan al proceso de fabricación para hacer parte de nuevos productos. Este tipo de cadena se caracteriza por la presencia de varios eslabones que permiten acercar el producto al consumidor final. Se hace un análisis de la estructura de la cadena de suministros, desde la producción, en las plantas hasta su llegada al cliente final por intermedio de los detallistas, en el sentido "aguas abajo", y desde el consumo del producto y la consecuente liberación de los materiales reutilizables que deben conducirse "aguas arriba" hasta las plantas de producción, donde son preparados y utilizados una y otra vez hasta el final de su vida útil. El foco de atención consiste en la integración de dos funciones fundamentales de la cadena de suministros: la planeación de la producción y la distribución del producto con la consecuente recolección de los materiales de retorno. Se precisa realizar la planeación de la producción de manera que dé satisfacción a la demanda que tiene lugar en los detallistas, y que se abastezca de los materiales de retorno que una vez consumido el producto se reincorporan al proceso. Se hace una revisión bibliográfica sobre planeación de la producción, logística inversa y ruteo de vehículos y; se construyen modelos de programación matemática que soportan la toma de decisiones en la planeación de la producción, de los inventarios (en toda la cadena de suministros), y de los envíos que deben realizarse en uno y otro sentido en las correspondientes rutas. Como resultado de la investigación se presentan tres modelos de programación lineal entera mixta (MILP), así: -Modelo de planeación de la producción: representa la cadena de suministros a partir de las instalaciones de cada uno de los niveles y su ubicación geográfica, y determina los volúmenes a producir, a almacenar y las cantidades que se deben enviar desde cada nodo de la cadena de suministros a los demás, de modo que se satisfaga la demanda en un horizonte de planeación compuesto por varios periodos. Este modelo presenta restricciones de capacidad tanto de producción como de almacenamiento, de demanda, de compatibilidad de productos con las instalaciones, y de envíos directos entre determinados nodos de la cadena de suministros. -Modelo de ruteo de vehículos: representa la forma en que se deben distribuir los productos desde los diferentes nodos fuente a los diferentes nodos destino, haciendo uso de una flota heterogénea de vehículos, en un periodo de tiempo. El modelo se hace bajo el supuesto de que los nodos son o emisores o receptores del producto, un nodo intermedio asume uno de estos roles según si es origen o destino de las mercancías. Presenta restricciones asociadas al uso de la flota, a su capacidad tanto en masa como en volumen, los flujos a lo largo de la cadena bajo la premisa de que un vehículo parte de un nodo fuente y puede visitar varios nodos destino antes de regresar, y de que un nodo puede ser visitado por varios vehículos (por condiciones de compatibilidad entre nodos y productos o porque resulta más económico), ante la presencia de ventanas de tiempo tanto rígidas como suaves. -Modelo integrado de gestión de producción y logística: reúne los dos modelos anteriores, es decir, permite la planeación de la producción, la gestión de los inventarios y el ruteo de vehículos para un horizonte de planeación determinado. Los tres modelos se proponen con el objetivo de minimizar los costes totales y son evaluados con instancias de prueba. Los modelos fueron implementados haciendo uso del software de optimización Gurobi y del lenguaje de programación Python. Además, se implementó una heurística constructiva y un algortimo genético utilizando Python y el software Pyevolve, como alternativa a la solución del VRP, para reducir el tiem / [CAT] Aquesta tesi s'analitza un tipus d'indústria que: els seus productes són distribuïts àmpliament a nivell geogràfic i fan ús d'elements que una vegada usats tornen al procés de fabricació per a fer part dels nous productes. Aquest tipus de cadenes es caracteritza per la presència de diversos eslavons que permeten acostar el producte des de les plantes de producció fins a arribar al consumidor final. Es fa una anàlisi de l'estructura de la cadena de subministraments, des de la producció, en les plantes fins a la seua arribada al client final per mitjà dels detallistes, en el sentit "aigües a baix", i des del consum del producte i el conseqüent alliberament dels materials reutilitzables que han de conduir-se "aigües a dalt" fins a les plantes de producció, on són preparats i utilitzats una vegada i una altra, fins al final de la seua vida útil. El focus d'atenció consisteix en la integració de dues funcions fonamentals de la cadena de subministraments: la planificació de la producció i la distribució del producte amb la conseqüent recol·lecció dels materials de tornada. Sobre aquest tema, es precisa realitzar la planificació de la producció de manera que done satisfacció a la demanda que té lloc en els detallistes, i que es proveïsca dels materials de tornada que, una vegada consumit el producte, es reincorporen al procés. Es fa una revisió bibliogràfica del relacionat amb planificació de la producció, logística inversa i enrutament de vehicles i es construeixen models de programació matemàtica que suporten la presa de decisions en la planificació de la producció, dels inventaris (tota la cadena de subministraments), i dels enviaments que han de realitzar-se en un i un altre sentit en les corresponents rutes. Com a resultat de la recerca es presenten tres models de Programació Lineal Sencera Mixta (MILP), així: -Model de planificació de la producció: representa la cadena de subministraments a partir de les instal·lacions de cadascun dels nivells i la seua ubicació geogràfica, i es determinen els volums a produir, a emmagatzemar i les quantitats que s'han d'enviar des de cada node de la cadena de subministraments als altres, de manera que se satisfaça la demanda en un horitzó de planificació compost per diversos períodes. Aquest model presenta restriccions de capacitat tant de producció com d'emmagatzematge, de demanda, de compatibilitat de productes amb les instal·lacions, i d'enviaments directes entre determinats nodes de la cadena de subministraments, entre altres aspectes. -Model de enrutament de vehicles: representa la forma en què s'han de distribuir els productes des dels diferents nodes font als diferents nodes destine, fent ús d'una flota heterogènia de vehicles, en un període de temps. Els nodes són o emissors o receptors del producte, encara que en la seua utilització un node intermedi pot assumir un d'aquests rols segons si és origen o destinació de les mercaderies. Per a aquest model es tenen en compte les restriccions associades a l'ús de la flota, a la seua capacitat tant en massa com en volum, els fluxos al llarg de la cadena sota la premissa que un vehicle parteix d'un node font i pot visitar diversos nodes destine abans de tornar, i que un node pot ser visitat per diversos vehicles, davant la presència de finestres de temps tant rígides com suaus. -Model integrat de gestió de producció i logística: reuneix els dos models anteriors, és a dir, permet la planificació de la producció, la gestió dels inventaris i el enrutament de vehicles per a un horitzó de planificació determinat. Els tres models es proposen amb l'objectiu de minimitzar els costos totals i són avaluats amb instàncies de prova, apropiades. Els models van ser implementats fent ús del programari d'optimització Gurobi i del llenguatge de programació Python. A més, es va implementar una heurística constructiva i un algortime genètic utilitzant Python i el programari Pye / Parra Peña, J. (2016). Modelizado para la planeación de la producción y la logística directa e inversa de una cadena de suministro cuyo abastecimiento depende parcialmente de los materiales de retorno [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/73726 / TESIS

This master´s thesis deals with the registration of ultrasound sequences using evolutionary algorithms. The theoretical part of the thesis describes the process of image registration and its optimalization using genetic and metaheuristic algorithms. The thesis also presents problems that may occur during the registration of ultrasonographic images and various approaches to their registration. In the practical part of the work, several optimization methods for the registration of a number of sequences were implemented and compared.