Made available in DSpace on 2015-03-05T14:01:22Z (GMT). No. of bitstreams: 0 Previous issue date: 12 / Bolsa para curso e programa de Pós Graduação / Este trabalho aborda o uso de uma metaheurística populacional para a solução do problema de otimização conhecido, na Pesquisa Operacional, como Programação de Horário de Cursos Baseada em Currículos. O problema de Programação de Horário de Cursos Baseada em Currículos consiste na construção das grades de horário de cursos em instituição de ensino que indicam em quais períodos semanais cada disciplina destes cursos deverá ocorrer, alocando professores e salas e respeitando um conjunto de requisitos organizacionais, pedagógicos e pessoais. Este trabalho apresenta uma formulação matemática para o problema e especifica um algoritmo de solução baseado na técnica metaheurística Busca Dispersa, combinada com o método de Reconexão por Caminhos. Além disso, é apresentado o registro de testes realizados com instâncias de problemas utilizadas na International Timetabling Competition e também em um problema real de uma instituição local de esino superior. / This paper discusses the use of a populational metaheuristic to solve the optimization problem known in Operational Research, as Curriculum Based Timetabling. The Curriculum Based Timetabling problem is the construction of schedule of courses in educational institutions that indicate which weekly times each subject of these courses should occur, allocating rooms and teachers and a respecting a set of organizational, pedagogical and personal requirements. This paper presents a mathematical formulation for the problem and specify a solution algorithm based on the Scatter Search metaheuristic technique, combined with the method Path Relinking. Furthermore, it is present the record of tests with instances of problems used in the International Timetabling Competition and also a real problem of a local institution.

Orientador: Rubén Augusto Romero Lázaro / Resumo: O principal objetivo deste trabalho é a implementação de uma metodologia que, utilizando a meta-heurística de busca dispersa (BD) resolva o problema de fluxo de potência ótimo (FPO) considerando o desligamento de linhas de transmissão (OTS) para a redução dos custos de ope-ração. Com o objetivo de avaliar o potencial da meta-heurística, o algoritmo de BD foi imple-mentado para otimizar funções multimodais restritas, metodologia denominada BD-FMR, e para resolver o problema de FPO, metodologia denominada BD-FPO. Foram realizados testes com onze problemas de funções multimodais restritas disponíveis na literatura especializada, utili-zando a metodologia BD-FMR, sendo que os resultados obtidos são comparáveis com os me-lhores resultados disponíveis na literatura. O problema de FPO foi resolvido pela metodologia BD-FPO utilizando três sistemas teste de 6, 14 e 57 barras, sendo que os resultados não foram satisfatórios quando comparados com as soluções do modelo exato do problema obtidas pelo solver KNITRO. Entretanto, o algoritmo BD-FPO serviu de base para a implementação da me-todologia principal deste trabalho. Por fim, a metodologia BD-OTS foi implementada em lin-guagem de programação C/C++, com a utilização de recursos de programação paralela através da biblioteca OpenMP. Neste trabalho a formulação utilizada para representar a operação da rede considera o modelo AC (corrente alternada), que consiste em um problema de programa-ção não linear inteira mista (PNLIM) devido a pre... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The main objective of this work is the implementation of a methodology that, using the scatter search meta-heuristic (SS) solves the problem of optimal power flow (OPF) considering trans-mission switching (TS) to reduce the operation costs. In order to evaluate the potential of the meta-heuristic, the SS algorithm was implemented to optimize constrained multimodal func-tions, a methodology called BD-FMR, and to solve the OPF problem, a methodology called BD-FPO. Eleven constrained multimodal problems available in the specialized literature were solved using the BD-FMR method, and the results obtained are comparable with the best results available in the literature. The OPF problem was solved by the BD-FPO methodology using three test systems with 6, 14, and 57 buses, and the results were not satisfactory when compared to the solutions of the exact formulation of the problem obtained by the KNITRO solver. How-ever, the BD-FPO algorithm served as the basis for the implementation of the main method of this work. Finally, the BD-OTS method was implemented in the C/C ++ programming lan-guage, using parallel programming resources through the OpenMP library. In this work, the formulation used to represent the operation of the grid considers the alternating current (AC) model, which consists of a mixed-integer nonlinear programming (MINLP) problem due to the presence of discrete variables related to the operation state a line, transformer tap position and the operating state of the s... (Complete abstract click electronic access below) / Doutor

Developing models of the cardiovascular system that simulates the dynamic behavior of a virtual patient’s condition is fundamental in the medical domain for predictive outcome and hypothesis generation. These models are usually described through Ordinary Differential Equation (ODE). To obtain a patient-specific representative model, it is crucial to have an accurate and rapid estimate of the hemodynamic model parameters. Moreover, when adequate model parameters are found, the resulting time series of state variables can be clinically used for predicting the response to treatments and for non-invasive monitoring. In the Thesis, we address the parameter estimation or inverse modeling, by solving an optimization problem, which aims at minimizing the error between the model output and the target data. In our case, the target data are a set of user-defined state variables, descriptive of a hospitalized specific patient and obtained from time-averaged state variables. The Thesis proposes a comparison of both state-of-the-art and novel methods for the estimation of the underlying model parameters of a cardiovascular simulator Aplysia. All the proposed algorithms are selected and implemented considering the constraints deriving from the interaction with Aplysia. In particular, given the inaccessibility of the ODE, we selected gradient-free methods, which do not need to estimate numerically the derivatives. Furthermore, we aim at having a small number of iterations and objective function calls, since these importantly impact the speed of the estimation procedure, and thus the applicability of the knowledge gained through the parameters at the bedside. Moreover, the Thesis addresses the most common problems encountered in the inverse modeling, among which are the non-convexity of the objective function and the identifiability problem. To assist in resolving the latter issue an identifiability analysis is proposed, after which the unidentifiable parameters are excluded. The selected methods are validated using heart failure data, representative of different pathologies commonly encountered in Intensive Care Unit (ICU) patients. The results show that the gradient-free global algorithms Enhanced Scatter Search and Particle Swarm estimate the parameters accurately at the price of a high number of function evaluations and CPU time. As such, they are not suitable for bedside applications. Besides, the local algorithms are not suitable to find an accurate solution given their dependency on the initial guess. To solve this problem, we propose two methods: the hybrid, and the prior-knowledge algorithms. These methods, by including prior domain knowledge, can find a good solution, escaping the basin of attraction of local minima and producing clinically significant parameters in a few minutes. / Utveckling av modeller av det kardiovaskulära systemet som simulerar det dynamiska beteendet hos en virtuell patients är grundläggande inom det medicinska området för att kunna förutsäga resultat och generera hypoteser. Dessa modeller beskrivs vanligtvis genom Ordinary Differential Equation (ODE). För att erhålla en patientspecifik representativ modell är det viktigt att ha en exakt och snabb uppskattning av de hemodynamiska modellparametrarna. När adekvata modellparametrar har hittats kan de resulterande tidsserierna av tillståndsvariabler dessutom användas kliniskt för att förutsäga svaret på behandlingar och för icke-invasiv övervakning. I avhandlingen behandlar vi parameteruppskattning eller invers modellering genom att lösa ett optimeringsproblem som syftar till att minimera följande felet mellan modellens utdata och måldata. I vårt fall är måldata en uppsättning användardefinierade tillståndsvariabler som beskriver en specifik patient som är inlagd på sjukhus och som erhålls från tidsgenomsnittliga tillståndsvariabler. I avhandlingen föreslås en jämförelse av befintlinga och nya metoder. för uppskattning av de underliggande modellparametrarna i en kardiovaskulär simulator, Aplysia. Alla föreslagna algoritmer är valts och implementerade med hänsyn tagna till de begränsningar som finnis i simulatorn Aplysia. Med tanke på att ODE är otillgänglig har vi valt gradientfria metoder som inte behöver uppskatta derivatorna numeriskt. Dessutom strävar vi efter att ha få interationer och funktionsanrop eftersom dessa påverkar hastigheten på estimeringen och därmed den kliniska användbartheten vid patientbehandling. Avhandlingen behandlas dessutom de vanligaste problemen vid inversmodellering som icke-konvexitet och identifierbarhetsproblem. För att lösa det sistnämnda problemet föreslås en identifierbarhetsanalys varefter de icke-identifierbara parametrarna utesluts. De valda metoderna valideras med hjälp av data om hjärtsvikt som är representativa för olika patologier som ofta förekommer hos Intensive Care Unit (ICU)-patienter. Resultaten visar att de gradientfria globala algoritmerna Enhanced Scatter Search och Particle Swarm uppskattar parametrarna korrekt till priset av ett stort antal funktionsutvärderingar och processortid. De är därför inte lämpliga för tillämpningar vid sängkanten. Dessutom är de lokala algoritmerna inte lämpliga för att hitta en exakt lösning eftersom de är beroende av den ursprungliga gissningen. För att lösa detta problem föreslår vi två metoder: hybridalgoritmer och algoritmer med förhandsinformation. Genom att inkludera tidigare domänkunskap kan dessa metoder hitta en bra lösning som undviker de lokala minimernas attraktionsområde och producerar kliniskt betydelsefulla parametrar på några minuter.

Cette thèse comporte des résultats théoriques et pratiques sur deux métaheuristiques, la Recherche Dispersée et la Recherche Voisinage variable (RVV), ainsi que sur des Matheuristiques. Au niveau théorique, la contribution principale de cette thèse est la proposition d’un algorithme de recherche dispersée avec l’arrondi directionnel convergent pour les programmes en nombres entiers mixtes (0-1 MIP), avec une preuve de cette convergence en un nombre fini d’itérations. En se basant sur cet algorithme convergeant, deux implémentations et plusieurs heuristiques sont proposées et testées sur des instances de 0-1 MIP. Les versions testées reposent sur des implémentations non optimisées pour mettre en évidence la puissance des approches dans une forme simplifiée. Nos résultats démontrent l’efficacité de ces approches initiales, ce qui les rend attractives lorsque des solutions de très haute qualité sont recherchées avec un investissement approprié en termes d’effort de calcul. Cette thèse inclut également quelques nouvelles variantes de la métaheuristique Recherche Voisinage Variable telles qu’une recherche voisinage variable deux niveaux, une recherche voisinage variable imbriquée, une descente voisinage variable cyclique et une heuristique de plongée voisinage variable. En outre, plusieurs implémentations efficaces de ces algorithmes basés sur la recherche voisinage variable ont été appliquées avec succès à des problèmes NP-Difficiles apparaissant en transport, logistique, production d’énergie, ordonnancement, et segmentation. Les heuristiques proposées se sont avérées être les nouvelles heuristiques de référence sur tous les problèmes considérés. La dernière contribution de cette thèse repose sur la proposition de plusieurs matheuristiques pour résoudre le problème de Conception de Réseau Multi-flots avec Coût fixe (CRMC). Les performances de ces matheuristiques ont été évaluées sur un ensemble d’instances de référence du CRMC. Les résultats obtenus démontrent la compétitivité des approches proposées par rapport aux approches existantes de la littérature. / This thesis consists of results obtained studying Scatter Search, Variable Neighbourhood Search (VNS), and Matheuristics in both theoretical and practical context. Regarding theoretical results, one of the main contribution of this thesis is a convergent scatter search with directional rounding algorithm for 0-1 Mixed Integer Programs (MIP) with the proof of its finite convergence. Besides this, a convergent scatter search algorithm is accompanied by two variants of its implementation. Additionally, several scatter search based heuristics, stemming from a convergent scatter search algorithm have been proposed and tested on some instances of 0-1 MIP. The versions of the methods tested are first stage implementations to establish the power of the methods in a simplified form. Our findings demonstrate the efficacy of these first stage methods, which makes them attractive for use in situations where very high quality solutions are sought with an efficient investment of computational effort.This thesis also includes new variants of Variable Neighborhood Search metaheuristic such as a two-level variable neighborhood search, a nested variable neighborhood search, a cyclic variable neighborhood descent and a variable neighborhood diving. Additionally, several efficient implementation of those variable neighborhood search algorithms have been successfully applied for solving NP-Hard problems appearing in transportation, logistics, power generation, scheduling and clustering. On all tested problems, the proposed VNS heuristics turned out to be a new state-of-the art heuristics. The last contribution of this thesis consists of proposing several matheuristics for solving Fixed-Charge Multicommodity Network Design (MCND) problem. The performances of these matheuristics have been disclosed on benchmark instances for MCND. The obtained results demonstrate the competitiveness of the proposed matheuristics with other existing approaches in the literature.