Dans cette thèse, nous cherchons à répondre à une problématique formulée par la DGA Techniques navales pour surveiller une zone stratégique : planifier le déploiement spatial et temporel optimal d’un ensemble de capteurs de façon à maximiser les chances de détecter une cible mobile et intelligente. La cible est dite intelligente car elle est capable de détecter sous certaines conditions les menaces que représentent les capteurs et ainsi de réagir en adaptant son comportement. Les déploiements générés pouvant aussi avoir un coût élevé nous devons tenir compte de ce critère lorsque nous résolvons notre problématique. Il est important de noter que la résolution d’un problème de ce type requiert, selon les besoins, l’application d’une méthode d’optimisation mono-objectif voire multiobjectif. Jusqu’à présent, les travaux existants n’abordent pas la question du coût des déploiements proposés. De plus la plupart d’entre eux ne se concentrent que sur un seul aspect à la fois. Enfin, pour des raisons algorithmiques, les contraintes sont généralement discrétisées.Dans une première partie, nous présentons un algorithme qui permet de déterminer le déploiement spatio-temporel de capteurs le plus efficace sans tenir compte de son coût. Cette méthode est une application à l’optimisation de la méthode multiniveau généralisée.Dans la seconde partie, nous montrons d’abord que l’utilisation de la somme pondérée des deux critères permet d’obtenir des solutions sans augmenter le temps de calcul. Pour notre seconde approche, nous nous inspirons des algorithmes évolutionnaires d’optimisation multiobjectif et adaptons la méthode multiniveau généralisée à l’optimisation multiobjectif. / In this work, we propose a solution to a problem issued by the DGA Techniques navales in order to survey a strategic area: determining the optimal spatio-temporal deployment of sensors that will maximize the detection probability of a mobile and smart target. The target is said to be smart because it is capable of detecting the threat of the sensors under certain conditions and then of adapting its behaviour to avoid it. The cost of a deployment is known to be very expensive and therefore it has to be taken into account. It is important to note that the wide spectrum of applications within this field of research also reflects the need for a highly complex theoretical framework based on stochastic mono or multi-objective optimisation. Until now, none of the existing works have dealt with the cost of the deployments. Moreover, the majority only treat one type of constraint at a time. Current works mostly rely on operational research algorithms which commonly model the constraints in both discrete space and time.In the first part, we present an algorithm which computes the most efficient spatio-temporal deployment of sensors, but without taking its cost into account. This optimisation method is based on an application of the generalised splitting method.In the second part, we first use a linear combination of the two criteria. For our second approach, we use the evolutionary multiobjective optimisation framework to adapt the generalised splitting method to multiobjective optimisation. Finally, we compare our results with the results of the NSGA-II algorithm.

La conception de procédé agroalimentaire est une activité complexe, caractérisée par la grande diversité des produits et des procédés étudiés, ainsi que par la disparité des contextes de production (artisanale ou industrielle). La conception de systèmes de transformation alimentaire adaptés est animée par d'importants enjeux humains, sanitaires, économiques, environnementaux et même culturels. Dans le cas des Pays du Sud, l'explosion démographique et l'urbanisation croissante impliquent de développer un système de production industriel capable de valoriser des produits issus de savoir-faire traditionnels, tout en répondant à des contraintes de coût et de productivité.Pour prévenir toute perte de temps causée par des analyses de type « essai-erreur », et afin d'éviter des coûts de développement superflus, il existe des outils spécifiques à l'analyse décisionnelle multicritères (MCDA) pouvant être déployé dès les phases préliminaires de la conception. En particulier, il est possible d'analyser le potentiel et les limites technologiques d'un concept défini dans un contexte donné, par l'analyse de l'ensemble de solutions les plus performantes, dites Pareto-optimales. Ces solutions se distinguent par les valeurs de leurs variables de conception, qui sont autant de degrés de liberté pour le dimensionnement du concept (géométrie, matériaux, conditions opératoires).Notre cas d'étude concerne l'évaluation d'un concept de fumage à chaud à plaques radiantes, pour la production de poisson fumé, traditionnellement consommé en Afrique Centrale et de l'Ouest. En effet, avant de prétendre à la diffusion de cette technologie déjà brevetée, il faut s'assurer que le procédé puisse satisfaire des objectifs de production et de performances énergétiques, tout en maintenant une qualité du produit satisfaisante. Ainsi, un outil d'optimisation multiobjectif spécifique a été développé en se basant sur la modélisation du comportement du procédé. Une première étude expérimentale a permis de construire un modèle de séchage du poisson dans des conditions d'air variables (température, vitesse et humidité), qui représente à la fois les flux d'évaporation et les flux liés aux écoulements gravitaires de graisses et d'eau. Dans un second temps, un outil de simulation existant a été amélioré afin de représenter des phénomènes ayant un impact significatif sur les performances du procédé, tels que l'aéraulique des fumées, le recyclage de l'air et la régulation thermique. Ainsi, un modèle d'observation a été établi. Il permet de prédire le comportement de différentes solutions possibles, définies par huit variables de conception, et d'évaluer leurs performances sur la base de six variables d'observation.Dans un dernier volet, la formalisation des préférences et de la connaissance experte du procédé permet d'interpréter les performances en termes de désirabilités (satisfaction), qui sont agrégées en un indice de satisfaction global (fonction objectif) par un principe de précaution. Un algorithme génétique permet alors de trouver une solution optimale qui maximise cette fonction objectif, en explorant l'espace des solutions possibles de manière combinatoire. Cette démarche de conception a été fructueuse car elle a permis de proposer un dimensionnement permettant d'obtenir des performances très satisfaisantes. Il a aussi été possible de proposer des améliorations ciblées pour redéfinir le concept actuel du fumoir à plaques. Par ailleurs, il est à noter que le modèle de comportement peut facilement être réadapté pour d'autre type de produits. Dans la perspective d'étendre l'utilisation de cette démarche à d'autres cas d'étude, un effort devra être mené pour la collecte de données fonctionnelles issues de l'expertise. / Food process design is a complex activity, given the wide diversity of existing product and processes, and the plurality of production contexts. Designer must meet the requirements derived from the critical stakes from human, sanitarian, economic, environmental and cultural point of views. In southern countries, the rapid growth of population drives the need of more industrial processes able to valorize traditional products.The savings of development time and extra-expenses are mainly determined by the quality of design choices from the early stage of the designing process, called embodiment design. Multiple criteria decision analysis (MCDA) techniques are used in this purpose, which enable to evaluate and criticize any technological concept. In a specific context, it is possible to generate the Pareto-set of a concept, which is composed of the most efficient possible alternatives. Indeed, every design alternative is defined by some design (or decision) variables which are the degree of freedom for the dimensioning of the system considered. Our case study focuses on a technological innovation to perform hot-smoking using radiant plates (for sanitarian purpose). It is aimed to be developed for the production of traditional hot-smoked catfish widely consumed in West and Central Africa. This is a multicriteria design problem since many objectives have to be satisfied, and concern the product quality, production and energetic performances.In a first work, the mass reduction of catfish dried in hot air conditions was modeled from empirical measurements. In particular, this model takes into account the influence of the drying air conditions (Temperature, Velocity and Relative Humidity) on the calculation of the mass fluxes of evaporation and drips. After that, a global simulation model of the radiant plate hot-smoking process was developed from a previous work. Some key phenomena were described (pressure losses, air recycling, thermal regulation) as they could strongly impact the process performances. The resulting observation model allows predicting the performances of any design alternative defined by a set of 8 design variables.In a final work, expert knowledge and preference were mathematically introduced in a multiobjective optimization tool, meaning some desirability functions. Therefore, every performance variable is converted into desirability indices (traducing the level of satisfaction) and then aggregated into a single global desirability index (thus defining a global objective function). The optimal design of the concept is found using a genetic algorithm.This multiobjective optimization method enabled to find very satisfactory design solution for the radiant plate hot smoking process. More to the point, the analysis of a wide range of Pareto-optimal solutions enabled to better understand what were the strengths and weaknesses, so it was possible to suggest some targeted improvement to the current radiant plate smoking technology. Also, it is noticeable that the current simulation model can be easily adapted to other products. For the purpose of a generalization of the use of such multiobjective methods for the design of food processes, it has been pointed out that efforts should be made to gather expert criteria other relevant functional data.

[pt] O problema da predição das estruturas de proteínas (Protein Structure Prediction (PSP)) é um dos desafios mais importantes na biologia molecular. Pelo fato deste problema ser muito difícil, têm sido propostos diferentes modelos simplificados para resolvê-lo. Um dos mais estudados é o modelo, Hidrofóbico-Polar (HP), o modelo HP fornece uma estimativa da energia da proteína com base na soma de interações entre pares de aminoácidos hidrofóbicos (contatos H-H). Entretanto, apesar das simplificações feitas no modelo HP, o problema permanece complexo, pertencendo à classe NP-Difícil. Muitas técnicas têm sido propostas para resolver este problema entre elas, técnicas baseadas em algoritmos genéticos. Em muitos casos, as técnicas baseadas em AG foram usadas com sucesso, mas, no entanto, abordagens utilizando AG muitas vezes não tratam adequadamente as soluções geradas, prejudicando o desempenho da busca. Além disso, mesmo que eles, em alguns casos, consigam atingir o mínimo de energia conhecido para uma conformação, estes modelos não levam em conta a forma da proteína um fator muito importante na hora de obter proteínas mais compactas. Foi desenvolvido um algoritmo genético multiobjetivo para PSP no modelo HP, de modo de avaliar de forma mais eficiente, as conformações produzidas. O modelo utiliza como avaliação uma combinação baseada no número de colisões, número de contatos hidrofóbicos, compactação dos aminoácidos hidrofóbicos e hidrofílicos, obtendo, desta forma estruturas mais naturais e de mínima energia. Os resultados obtidos demonstram a eficiência desse algoritmo na obtenção de estruturas proteicas compactas providenciando indicadores da compactação dos aminoácidos hidrofóbicos e hidrofílicos da proteína. / [en] The problem of protein structured prediction (PSP) is one of the most important challenges in molecular biology. Because this problem is very difficult, different simplified models have been proposed to solve it. One of the most studied is the Hydrophobic-Polar model HP this model provides an estimate of the protein energy based on the sum of hydrophobic contacts. However, despite the simplifications made in the HP model, the problem remains complex, belonging to the class of NP-Hard problems. Many techniques have been proposed to solve this problem as genetic algorithms. In many cases the GA techniques have been used successfully, but, however, with GA approaches often do not adequately address the generated solutions, impairing the performance of the search. Furthermore, in some cases would attain the minimum energy for a known conformation, these models do not take care the protein shape, a very important factor to obtain more compact proteins. This work developed a multiobjective genetic algorithm to PSP in HP model evaluating more efficiently, the conformations produced. This model is a combination of assessment based on the collisions numbers, hydrophobic contacts, hydrophobic and hydrophilic core compression, obtaining thus more natural structures with minimum energy. The results demonstrate the efficiency of this algorithm to obtain protein structures indicators providing compact compression of the hydrophobic and hydrophilic core protein.

L’objectif de cette thèse est le développement de méthodes d’optimisation multi-objectif pour la résolution de problèmes de conception des structures mécaniques. En effet, la plupart des problèmes réels dans le domaine de la mécanique des structures ont plusieurs objectifs qui sont souvent antagonistes. Il s’agit, par exemple, de concevoir des structures en optimisant leurs poids, leurs tailles, et leurs coûts de production. Le but des méthodes d’optimisation multi-objectif est la recherche des solutions de compromis entre les objectifs étant donné l’impossibilité de satisfaire tout simultanément. Les métaheuristiques sont des méthodes d’optimisation capables de résoudre les problèmes d’optimisation multi-objective en un temps de calcul raisonnable sans garantie de l’optimalité de (s) solution (s). Au cours des dernières années, ces algorithmes ont été appliqués avec succès pour résoudre le problème des mécaniques des structures. Dans cette thèse deux métaheuristiques ont été développées pour la résolution des problèmes d’optimisation multi-objectif en général et de conception de structures mécaniques en particulier. Le premier algorithme baptisé MOBSA utilise les opérateurs de croisement et de mutation de l’algorithme BSA. Le deuxième algorithme nommé NNIA+X est une hybridation d’un algorithme immunitaire et de trois croisements inspirés de l’opérateur de croisement original de l’algorithme BSA. Pour évaluer l’efficacité et l’efficience de ces deux algorithmes, des tests sur quelques problèmes dans littérature ont été réalisés avec une comparaison avec des algorithmes bien connus dans le domaine de l’optimisation multi-objectif. Les résultats de comparaison en utilisant des métriques très utilisées dans la littérature ont démontré que ces deux algorithmes peuvent concurrencer leurs prédécesseurs. / The objective of this thesis is the development of multi-objective optimization methods for solving mechanical design problems. Indeed, most of the real problems in the field of mechanical structures have several objectives that are often antagonistic. For example, it is about designing structures by optimizing their weight, their size, and their production costs. The goal of multi-objective optimization methods is the search for compromise solutions between objectives given the impossibility to satisfy all simultaneously. Metaheuristics are optimization methods capable of solving multi-objective optimization problems in a reasonable calculation time without guaranteeing the optimality of the solution (s). In recent years, these algorithms have been successfully applied to solve the problem of structural mechanics. In this thesis, two metaheuristics have been developed for the resolution of multi-objective optimization problems in general and of mechanical structures design in particular. The first algorithm called MOBSA used the crossover and mutation operators of the BSA algorithm. The second one named NNIA+X is a hybridization of an immune algorithm and three crossover inspired by the original crossover operator of the BSA algorithm. To evaluate the effectiveness and efficiency of these two algorithms, tests on some problems in literature have been made with a comparison with algorithms well known in the field of multi-objective optimization. The comparison results using metrics widely used in the literature have shown that our two algorithms can compete with their predecessors.

Le procédé d'hydroformage est largement utilisé dans les industries automobile et aéronautique. L'optimisation déterministe a été utilisée pour le contrôle et l'optimisation du procédé durant la dernière décennie. Cependant,dans des conditions réelles, différents paramètres comme les propriétés matériaux,les dimensions géométriques, et les chargements présentent des aléas qui peuvent affecter la stabilité et la fiabilité du procédé. Il est nécessaire d'introduire ces incertitudes dans les paramètres et de considérer leur variabilité. L'objectif principal de cette contribution est l'évaluation de la fiabilité et l'optimisation du procédé d'hydroformage en présence d'incertitudes.La première partie de cette thèse consiste à proposer une approche générale pour évaluer la probabilité de défaillance spatiale du procédé d'hydroformage, principalement dans les régions critiques. Avec cette approche, il est possible d'éviter les instabilités plastiques durant une opération d'hydroformage. Cette méthode est basée sur des simulations de Monte Carlo couplée avec des métamodèles. La courbe limite de formage est utilisée comme critère de défaillance pour les instabilités plastiques potentielles.La seconde partie de cette thèse est l'optimisation avec prise en compte d'incertitudes dans le procédé d'hydroformage. En utilisant des exemples illustratifs, on montre que l'approche probabiliste est une méthode efficace pour l'optimisation du procédé pour diminuer la probabilité de défaillance et laisser le procédé insensible ou peu sensible aux sources d'incertitudes. La difficulté est liée à la considération des contraintes fiabilistes qui nécessitent d'énormes efforts de calcul et impliquent des problèmes numériques classiques comme la convergence, la précision et la stabilité. Pour contourner ce problème, la méthode de surface de réponse couplée à des simulations Monte Carlo est utilisée pour évaluer les contraintes probabilistes.L'approche probabiliste peut assurer la stabilité et la fiabilité du procédé et minimise considérablement le pourcentage des pièces défectueuses. Dans cette partie, deux méthodes sont utilisées : l'optimisation fiabiliste et l'optimisation robuste.La dernière partie consiste à optimiser le procédé avec une stratégie Multi-Objectif(MO) avec prise en compte d'incertitudes. Le procédé d'hydroformage est un problème MO qui consiste à optimiser plus d'une performance simultanément.L'objectif principal est d'étudier l'évolution du front de Pareto lorsque des incertitudes affectent les fonctions objectifs ou les paramètres. Dans cette partie, on propose une nouvelle méthodologie qui présente les solutions dans un nouvel espace et les classifie suivant leurs probabilités de défaillances. Cette classification permet d'identifier la meilleure solution et fournit une idée sur la fiabilité de chaque solution. / Hydroforming process is widely used in automotive and aerospace industries. Deterministic design optimization have been used to control and optimize this process in the last decade. However, under realistic conditions, different parameters such as material properties, geometric dimensions, and load exhibits unavoidable scatter that can affect the stability and the reliability of the process.It is interesting to introduce the uncertainties in parameter and to consider their variability. The main objective of this contribution is to evaluate the reliability and optimization of the hydroforming process in the presence of uncertainties.The first part of this thesis proposes a general approach to evaluate the spatial probability of failure in hydroforming process mainly in the critical region. With the proposed approach it is possible to avoid failure during hydroforming process.This method is based on Monte Carlo simulation coupled with metamodels, the forming limit curve is used as failure criteria for potential plastic instabilities.The second part of this thesis is the optimisation of the hydroforming process under uncertainties. Using illustrative examples, it is shown that probabilistic approach is an efficient method to optimize the process, to decrease the probability of failure and make the process insensitive or less sensitive to sources of variability. The difficulty lies in the considerations of the reliability constraints, which require a large computational effort and involve classical numerical problems, such as convergence,accuracy and stability. To overcome this problem, response surface method with Monte Carlo simulations were used to evaluate the probabilistic constraints.Probabilistic approach can ensure a stable and reliable process and decrease the percentage of defects parts significantly. Through this part, two methods were used : Reliability-Based Design Optimization and robust optimization.The last part consists of optimizing the process with Multi-Objective (MO) strategy taking account of the uncertainty. Metal forming process is MO problem that consists of optimizing more than one performance simultaneously. The main goal isto study the evolution of the Pareto front when some uncertainties can affect the objective functions or the parameters. In this part, a new methodology is proposed which presents the solutions in a new space and classify the whole solution with their probability of failure. This classification allows to identify the best solutionand can provide an idea about the reliability of each solution.

La conception d’un plan de transport d’un service ferroviaire est un processus qui se réalise entre deux ans et six mois avant la mise en service de celui-ci. Les principales phases de la conception sont la définition des dessertes, le calcul de la grille horaire et enfin l’organisation des roulements de rames et des conducteurs. La manière dont le plan de transport est conçu peut avoir de nombreuses conséquences sur la qualité de service : fréquence en gare insuffisante qui peut entrainer une perte de clients, robustesse de la grille horaire face à de petits incidents... En zone dense, tous ces éléments sont à prendre en compte, dès la conception de la grille horaire.Aujourd’hui, SNCF Transilien conçoit ses plans de transport en prenant d’abord en compte l’optimisation des ressources de production (sillons, rames et agents de conduite). Toutefois, l’augmentation des ressources mises en œuvre n’améliore plus l’adéquation du plan de transport à la demande des voyageurs. Ce mode de conception ne permet donc plus de faire face à l’augmentation de la demande de mobilité. C’est pourquoi il faut repenser la conception du plan de transport en intégrant immédiatement la dimension voyageuse.Nos travaux se concentrent sur les problématiques de conception de dessertes et de grille horaire, en prenant en compte le point de vue des voyageurs. Nous présentons un modèle multiobjectif de conception de dessertes, puis nous présentons un modèle de conception de grille horaire intégrant le choix d’itinéraire des voyageurs. Ensuite, nous présentons une méthode cherchant à intégrer ces deux modèles. Enfin, nous présentons une évaluation de nos résultats grâce à des indicateurs de fiabilité / The design of a railway transportation plan is a process achieved between two years and six months before it is put into service. The main phases in the design of a transportation plan are the line planning, the timetabling, the rolling stock and the crew scheduling.The design of the transportation plan can have many consequences on the quality of service: an inadequate frequency in station can cause a loss of passengers, sufficient number of seated places, robustness of the timetable in the face of small incidents... In dense area, as in the Ile-de-France region, all these elements must be taken into account as the transportation plan is designed.Today, SNCF Transilien designs its transportation plans by first taking into account the optimization of production resources (train paths, rolling stock units and drivers). However, today, the increase in resources implemented no longer improves the adequacy of the transportation plan to passengers’ demand. This design method no longer makes it possible to cope with the increase in the demand for mobility (+3% each year since 2000). This is why we must rethink the design of the transport plan by immediately integrating the passenger dimension. Our work focuses on issues of line planning and timetabling in a passenger-oriented approach. First, we present a multi-objective model for line planning. Then, we present a model of timetabling incorporating passenger route choice. Then, we initiate a method to integrate these two models. Finally, we present an evaluation of our results thanks to reliability indicators from the literature and a macroscopic simulation of the timetables

O objetivo do presente trabalho é a investigação e o desenvolvimento de estratégias de otimização contínua e discreta para problemas de Fluxo de Potência Ótimo (FPO), onde existe a necessidade de se considerar as variáveis de controle associadas aos taps de transformadores em-fase e chaveamentos de bancos de capacitores e reatores shunt como variáveis discretas e existe a necessidade da limitação, e/ou até mesmo a minimização do número de ações de controle. Neste trabalho, o problema de FPO será abordado por meio de três estratégias. Na primeira proposta, o problema de FPO é modelado como um problema de Programação Não Linear com Variáveis Contínuas e Discretas (PNLCD) para a minimização de perdas ativas na transmissão; são propostas três abordagens utilizando funções de discretização para o tratamento das variáveis discretas. Na segunda proposta, considera-se que o problema de FPO, com os taps de transformadores discretos e bancos de capacitores e reatores shunts fixos, possui uma limitação no número de ações de controles; variáveis binárias associadas ao número de ações de controles são tratadas por uma função quadrática. Na terceira proposta, o problema de FPO é modelado como um problema de Otimização Multiobjetivo. O método da soma ponderada e o método &#949-restrito são utilizados para modificar os problemas multiobjetivos propostos em problemas mono-objetivos. As variáveis binárias associadas às ações de controles são tratadas por duas funções, uma sigmoidal e uma polinomial. Para verificar a eficácia e a robustez dos modelos e algoritmos desenvolvidos serão realizados testes com os sistemas elétricos IEEE de 14, 30, 57, 118 e 300 barras. Todos os algoritmos e modelos foram implementados em General Algebraic Modeling System (GAMS) e os solvers CONOPT, IPOPT, KNITRO e DICOPT foram utilizados na resolução dos problemas. Os resultados obtidos confirmam que as estratégias de discretização são eficientes e as propostas de modelagem para variáveis binárias permitem encontrar soluções factíveis para os problemas envolvendo as ações de controles enquanto os solvers DICOPT e KNITRO utilizados para modelar variáveis binárias não encontram soluções. / The aims of this study are the investigation and the development of continuous and discrete optimization strategies to Optimal Power Flow (OPF) problems, where the control variables are the tap ratios of on-load tap changing (OLTC) transformers and shunt susceptances of switchable capacitors and reactors banks. These controls are discrete variables and a need for the limitation and/or even the minimization of the number of control adjustments is required. In this work, three strategies for solving the OPF problem have been deviced. In the first strategy, the OPF problem is modeled as a nonlinear programming problem with continuous and discrete variables for active power losses minimization; Three approaches using discretization functions for handling discrete variables have been investigated. In the second proposal, the OPF problem with discrete OLTC transformers and continuous shunt susceptances of switchable capacitors and reactors banks has a limitation on the number of control adjustments; binary variables associated with control adjustments are handled by a quadratic function. In the third proposal, the OPF problem is modeled as a multiobjective optimization problem. The weighting method and the &#949-constraint method are used to modify the proposed multiobjective problems onto single-objective problems. The binary variables associated with the controls are handled by sigmoidal and polynomial functions. The efficiency and robustness of the models and algorithms are shown for IEEE benchmark test-systems with up to 300 buses. All algorithms and models were implemented in GAMS modeling language and the results are obtained by means of CONOPT, IPOPT, KNITRO and DICOPT solvers. The results confirm that the discretization strategies are efficient and the proposed modeling for binary variables allows finding feasible solutions to problems involving the of controls while DICOPT and KNITRO solvers used to handle binary variables fail to find solutions.

Este trabalho foca o desenvolvimento de algoritmos de otimização para o problema de PSP puramente ab initio. Algoritmos que melhor exploram o espaço de potencial de soluções podem, em geral, encontrar melhores soluções. Esses algoritmos podem beneficiar ambas abordagens de PSP, tanto o modelo ab initio quanto os baseados em conhecimento a priori. Pesquisadores tem mostrado que Algoritmos Evolutivos Multiobjetivo podem contribuir significativamente no contexto do problema de PSP puramente ab initio. Neste contexto, esta pesquisa investiga o Algoritmo Evolutivo Multiobjetivo baseado em Tabelas aplicado ao PSP puramente ab initio, que apresenta interessantes resultados para proteínas relativamente simples. Por exemplo, um desafio para o PSP puramente ab initio é a predição de estruturas com folhas-. Para trabalhar com tais proteínas, foi desenvolvido procedimentos computacionalmente eficientes para estimar energias de ligação de hidrogênio e solvatação. Em geral, estas não são consideradas no PSP por abordagens que combinam métodos de otimização e conhecimento a priori. Considerando somente van der Waals e eletrostática, as duas energias de interação que mais contribuem para a definição da estrutura de uma proteína, com as energias de ligação de hidrogênio e solvatação, o problema de PSP tem quatro objetivos. Problemas combinatórios (tais como o PSP), com mais de três objetivos, geralmente requerem métodos específicos capazes de lidar com muitos critérios. Para resolver essa limitação, este trabalho propõe um novo método para a otimização dos muitos objetivos, chamado Algoritmo Evolutivo Multiobjetivo com Muitas Tabelas (AEMMT). Esse método executa uma amostragem mais adequada do espaço de funções objetivo e, portanto, pode mapear melhor as regiões promissoras deste espaço. A capacidade de lidar com muitos objetivos capacita o AEMMT a utilizar melhor a informação oriunda das energias de solvatação e de ligação de hidrogênio, e então predizer estruturas com folhas- e algumas proteínas relativamente mais complexas. Do ponto de vista computacional, o AEMMT é um novo método que lida com muitos objetivos (mais de dez) encontrando soluções relevantes / This work focuses on the development of optimization algorithms for the purely ab initio Protein Structure Prediction (PSP) problem. Algorithms that better explore the space of potential solutions can in general find better solutions. Such algorithms can benefit both ab initio and template-based PSP, that uses priori knowledge. Researches have shown that Multiobjective evolutionary algorithms can contribute significantly in the context of purely ab initio PSP. In this context, this research investigates the Multiobjective Evolutionary Algorithm based on Tables applied to purely ab initio PSP, which has shown interesting results for relatively simple proteins. For example, one challenge for purely ab initio PSP is the prediction of structures with -sheets. To work with such proteins, this research has developed computationally efficient procedures to estimate hydrogen bond and solvation energies. In general, they are not considered by PSP approaches combining optimization methods with priori knowledge. Only by considering van der Waals and electrostatic, the two interaction energies that mostly contribute to defining a protein structure, and the hydrogen bond and solvation energies, the PSP problem has four objectives. Combinatorial problems (such as the PSP) with more than three objective usually require specific methods capable of dealing with many goals. To address this limitation, we propose a new method for many objective optimization, called Multiobjective Evolutionary Algorithm with Many Tables (MEAMT). This method performs a more adequate sampling of the space of objective functions and, therefore, can better map the promising regions of this space. The ability of dealing with many objectives enables the MEANT to better use information generated by solvation and hydrogen bond energies, and then predict structures with -sheets and some relatively complex proteins. From the computational point of view, the MEAMT is a new method for dealing with many objectives (more than ten) finding relevant solutions

A qualidade da água de abastecimento é de vital importância à saúde da população dos núcleos urbanos do mundo todo. Por essa razão, muitas pesquisas enfocam esse tema. Além disso, os ataques terroristas recentes ocorridos nos Estados Unidos e Europa, vêm fomentando a antiga preocupação relativa a possíveis injeções de contaminantes em redes de distribuição de água para abastecimento, evidenciando a importância da efetiva vigilância de tais sistemas. O presente trabalho investiga a rede de monitoramento ótima para detecção de injeções intencionais de poluentes e/ou contaminantes em concentrações e/ou quantidades suficientes para que se propaguem nas direções do fluxo da água no interior das redes, do ponto de vista de objetivos múltiplos. A metodologia aqui apresentada representa uma extensão de propostas anteriores e é demonstrada ilustrativamente, através de redes já utilizadas na literatura. Com base no conceito da rede auxiliar proposto por Kessler et al. (1998), propõe-se o emprego de algoritmos genéticos multiobjetivo para considerar os níveis de serviço em termos do volume consumido, do tempo e da extensão da rede atingida antes da detecção. São criadas matrizes de poluição para os níveis de serviço considerados e, então, o algoritmo genético multiobjetivo SPEA é aplicado para identificar as soluções não-dominadas, em conformidade com o conceito de otimalidade de Pareto. Os resultados demonstram o potencial do método proposto em identificar tais soluções / The water supply quality is very important to the healthy of urban nucleus populations around the world. This is the reason why many researches focus on such theme. Besides this, recent terrorist attacks occurred in USA and Europe, have incited the old apprehension related to possible deliberate intrusions of contaminants into the water supply networks, making evident the importance of the effective vigilance of such systems. This work investigates the optimal monitoring network for detection of deliberate intrusions of pollutes and/or contaminants at concentrations and/or quantities enough for propagation inside the networks, on the point of view of multiple objectives. The method here proposed represents an extension to earlier proposals and is demonstrated with the support of networks from literature. Based on the concept of auxiliary network proposed by Kessler et al. (1998), a multiobjective genetic algorithm is used in order to consider the levels of service in terms of the consumed volume, time period and length of the network reached before detection. Pollution matrixes are built for the levels of service considered and the multiobjective genetic algorithm SPEA applied in the identification of the non-dominated solutions, according to the Paretto optimality concept. The results demonstrate the potential of the method in the identification of such solutions

Um tema pouco estudado na literatura, mas frequentemente encontrado por empresas prestadoras de serviço, é o Problema de Escalonamento de Técnicos de Campos (Field Technician Scheduling Problem). O problema consiste em associar um número de tarefas - em diversos locais, com diferentes prioridades e com janelas de tempo - a uma quantidade de técnicos - com diferentes horários de expediente e com habilidades distintas - que saem no início do horário de trabalho da sede da empresa, para onde devem retornar antes do fim do expediente. Cada tarefa é atendida por um único técnico. Esse problema é estudado neste trabalho. A primeira parte do trabalho apresenta um modelo de programação linear inteira mista (PLIM) e, dada a complexidade do problema, heurísticas construtivas e meta-heurísticas foram desenvolvidas. Na função objetivo, procura-se principalmente maximizar o número ponderado de tarefas executadas em um dia de trabalho, de acordo com as suas prioridades. Em linhas gerais, as heurísticas construtivas ordenam as tarefas de acordo com um critério pré-estabelecido e, em seguida, designam cada uma a um dos técnicos capazes de realiza-la sem violar as restrições do problema. Tendo em conta o bom desempenho obtido em outros problemas semelhantes, foi adotado um Algoritmo Genético denominado Biased Random-Key Genetic Algorithms (BRKGA), que utiliza chaves aleatórias para codificar e decodificar as soluções. Codificadores e decodificadores adaptados ao problema foram desenvolvidos e testes computacionais são apresentados. As soluções obtidas em problemas de pequenas dimensões são comparadas com as soluções ótimas conhecidas e, para aprimorar a avaliação do desempenho nas instâncias médias e grandes, quatro procedimentos para obter limitantes superiores foram propostos. Testes computacionais foram realizados em 1040 instâncias. O BRKGA encontrou 99% das 238 soluções ótimas conhecidas e, nas 720 instâncias de dimensões médias e grandes, ficou em média a 3,8% dos limitantes superiores. As heurísticas construtivas superaram uma heurística construtiva da literatura em 90% das instâncias. A segunda parte do trabalho apresenta uma nova abordagem para o Problema de Escalonamento de Técnicos de Campo: um modelo biobjetivo, onde uma segunda função objetivo buscará que as tarefas prioritárias sejam realizadas o mais cedo possível. Uma versão multiobjectivo do BRKGA foi desenvolvida, considerando diversas estratégias para classificar a população do algoritmo e escolher as melhores soluções (estratégias de elitismo). Codificadores e decodificadores foram criados para o problema multiobjectivo. Os resultados computacionais obtidos são comparados com os resultados de um Algoritmo Genético conhecido na literatura, o Nondominated Sorting Genetic Algorithm II (NSGA II). Para instâncias de pequenas dimensões, os resultados da meta-heurística proposta também são comparados com a fronteira ótima de Pareto de 234 instâncias, obtidas por enumeração completa. Em média, o BRKGA multiobjectivo encontrou 94% das soluções da fronteira ótima de Pareto e, nas instâncias médias e grandes, superou o desempenho do NSGA-II nas medidas de avaliação adotadas (porcentagem de soluções eficientes, hipervolume, indicador epsílon e cobertura). / An important topic in service companies, but little studied until now, is the field technician scheduling problem. In this problem, technicians have to execute a set of jobs or service tasks. Technicians have different skills and working hours. Tasks are in different locations within a city, with different time windows, priorities, and processing times. Each task is executed by only one technician. This problem is addressed in this thesis. The first part of the research presents the mixed integer linear programming model (MILP) and, due to the complexity of this problem, constructive heuristics and metaheuristics were proposed. The objective function is to maximize the sum of the weighted performed tasks in a day, based on the priority of tasks. In general terms, in the proposed constructive heuristics, jobs are ordered according to a criterion and, after that, tasks are assigned to technicians without violating constraints. A Genetic Algorithm (the Biases Randon Key Genetic Algorithm - -RKGA) is applied to the problem, based on its success in similar problems; the BRKGA uses random keys and a decoder transforms each chromosome of the Genetic Algorithm into a feasible solution of the problem. Decoders and encoders adapted to the problem were developed and computational tests are presented. A comparison between the solutions of the heuristic methods and optimal solutions values was also conducted for small instances and, to analyze medium and large instances, four upper bound models were proposed. Computational experiments with 1040 instances were carried out. The BRKGA reached 99% of the 238 optimal solutions and, for 720 medium and large instances, the average upper bound gap was 3,8%. Constructive heuristics overcame a heuristic of the literature in 90% of the instances. The second part of this research presents a new approach of the Field Technician Scheduling Problem: a multiobjective model, with a second objective function to execute the priority tasks as soon as possible. A multiobjective BRKGA was developed, with different strategies to classify the Genetic Algorithm population and to select the elite solutions (elite strategies). Decoders and encoders were developed for the multiobjective problem too. The results were compared with a known Genetic Algorithm, the Nondominated Sorting Genetic Algorithm II (NSGA II). For 234 small instances, the results were compared with the Pareto optimal solutions, obtained by complete enumeration. On average, the BRKGA found 94% of the Pareto optimal solutions and, for 720 medium and large instances, outperformed the NSGA-II by means of the measures adopted (percentage of efficient solutions, hypervolume, epsilon and coverage).