Made available in DSpace on 2014-12-17T15:46:59Z (GMT). No. of bitstreams: 1 PauloHAS_TESE.pdf: 9268945 bytes, checksum: 08c0c5f93ed7b964b99c6df2ee26ab1b (MD5) Previous issue date: 2011-12-19 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / The Car Rental Salesman Problem (CaRS) is a variant of the classical Traveling Salesman Problem which was not described in the literature where a tour of visits can be decomposed into contiguous paths that may be performed in different rental cars. The aim is to determine the Hamiltonian cycle that results in a final minimum cost, considering the cost of the route added to the cost of an expected penalty paid for each exchange of vehicles on the route. This penalty is due to the return of the car dropped to the base. This paper introduces the general problem and illustrates some examples, also featuring some of its associated variants. An overview of the complexity of this combinatorial problem is also outlined, to justify their classification in the NPhard class. A database of instances for the problem is presented, describing the methodology of its constitution. The presented problem is also the subject of a study based on experimental algorithmic implementation of six metaheuristic solutions, representing adaptations of the best of state-of-the-art heuristic programming. New neighborhoods, construction procedures, search operators, evolutionary agents, cooperation by multi-pheromone are created for this problem. Furtermore, computational experiments and comparative performance tests are conducted on a sample of 60 instances of the created database, aiming to offer a algorithm with an efficient solution for this problem. These results will illustrate the best performance reached by the transgenetic algorithm in all instances of the dataset / O Problema do Caixeiro Alugador (CaRS) ? uma variante ainda n?o descrita na literatura do cl?ssico Problema do Caixeiro Viajante onde o tradicional tour de visitas do caixeiro pode ser decomposto em caminhos cont?guos e que podem ser realizados em diferentes carros alugados. O problema consiste em determinar o ciclo hamiltoniano que resulte em um custo final m?nimo, considerando o custo da rota adicionado ao custo de uma prov?vel penaliza??o paga em cada troca de ve?culos na rota, penaliza??o devida ao retorno do carro descartado at? a sua cidade base. Sem perda para a generalidade do caso, os custos do aluguel do carro podem ser considerados embutidos nos custos da rota do carro. O presente trabalho introduz o problema geral e o exemplifica, caracterizando igualmente algumas variantes associadas. Uma an?lise geral da complexidade desse problema combinat?rio ? descrita, visando justificar sua classifica??o na classe NP-dif?cil. Um banco de inst?ncias para o problema ? apresentado, descrevendo-se a metodologia de sua constitui??o. O problema proposto tamb?m ? objeto de um estudo algor?tmico experimental baseado na aplica??o de seis metaheur?sticas de solu??o, representando adapta??es do melhor do estado da arte em programa??o heur?stica. Novas vizinhan?as, procedimentos construtivos, operadores de busca, agentes evolucion?rios, coopera??o por multiferom?nios, s?o criados para o caso. Experimentos computacionais comparativos e testes de desempenho s?o realizados sobre uma amostra de 60 inst?ncias, visando oferecer um algoritmo de solu??o competitivo para o problema. Conclui-se pela vantagem do algoritmo transgen?tico em todos os conjuntos de inst?ncias

Made available in DSpace on 2014-12-17T15:46:59Z (GMT). No. of bitstreams: 1 LauraEASS_TESE.pdf: 2447411 bytes, checksum: 3e442431965058383423623bc7751de0 (MD5) Previous issue date: 2012-02-02 / Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico / Traditional applications of feature selection in areas such as data mining, machine learning and pattern recognition aim to improve the accuracy and to reduce the computational cost of the model. It is done through the removal of redundant, irrelevant or noisy data, finding a representative subset of data that reduces its dimensionality without loss of performance. With the development of research in ensemble of classifiers and the verification that this type of model has better performance than the individual models, if the base classifiers are diverse, comes a new field of application to the research of feature selection. In this new field, it is desired to find diverse subsets of features for the construction of base classifiers for the ensemble systems. This work proposes an approach that maximizes the diversity of the ensembles by selecting subsets of features using a model independent of the learning algorithm and with low computational cost. This is done using bio-inspired metaheuristics with evaluation filter-based criteria / A aplica??o tradicional da sele??o de atributos em diversas ?reas como minera??o de dados, aprendizado de m?quina e reconhecimento de padr?es visa melhorar a acur?cia dos modelos constru?dos com a base de dados, ao retirar dados ruidosos, redundantes ou irrelevantes, e diminuir o custo computacional do modelo, ao encontrar um subconjunto representativo dos dados que diminua sua dimensionalidade sem perda de desempenho. Com o desenvolvimento das pesquisas com comit?s de classificadores e a verifica??o de que esse tipo de modelo possui melhor desempenho que os modelos individuais, dado que os classificadores base sejam diversos, surge uma nova aplica??o ?s pesquisas com sele??o de atributos, que ? a de encontrar subconjuntos diversos de atributos para a constru??o dos classificadores base de comit?s de classificadores. O presente trabalho prop?e uma abordagem que maximiza a diversidade de comit?s de classificadores atrav?s da sele??o de subconjuntos de atributos utilizando um modelo independente do algoritmo de aprendizagem e de baixo custo computacional. Isso ? feito utilizando metaheur?sticas bioinspiradas com crit?rios de avalia??o baseados em filtro

Made available in DSpace on 2014-12-17T15:47:46Z (GMT). No. of bitstreams: 1 FrederikoSLNA.pdf: 5281687 bytes, checksum: 9fe12b6bcc355f7c67cf2f2c3ad9812b (MD5) Previous issue date: 2006-02-16 / This work performs an algorithmic study of optimization of a conformal radiotherapy plan treatment. Initially we show: an overview about cancer, radiotherapy and the physics of interaction of ionizing radiation with matery. A proposal for optimization of a plan of treatment in radiotherapy is developed in a systematic way. We show the paradigm of multicriteria problem, the concept of Pareto optimum and Pareto dominance. A generic optimization model for radioterapic treatment is proposed. We construct the input of the model, estimate the dose given by the radiation using the dose matrix, and show the objective function for the model. The complexity of optimization models in radiotherapy treatment is typically NP which justifyis the use of heuristic methods. We propose three distinct methods: MOGA, MOSA e MOTS. The project of these three metaheuristic procedures is shown. For each procedures follows: a brief motivation, the algorithm itself and the method for tuning its parameters. The three method are applied to a concrete case and we confront their performances. Finally it is analyzed for each method: the quality of the Pareto sets, some solutions and the respective Pareto curves / O presente trabalho realiza um Estudo Algor?tmico para Otimiza??o do Plano de Tratamento da Radioterapia Conformal. Inicialmente s?o apresentadas: uma vis?o geral sobre o c?ncer, o tratamento com radioterapia e no??es sobre a intera??o do feixe de radia??es ionizantes com a mat?ria. Uma proposta para Otimiza??o do Plano de Tratamento Radioter?pico ? desenvolvida de modo sistem?tico. ? apresentado o paradigma de problemas multicrit?rio, os conceitos de Pareto otimalidade e Pareto Domin?ncia. Um modelo Gen?rico de Otimiza??o para o Plano de Tratamento Radioter?pico ? proposto. S?o constru?das suas entradas, ? calculada a dose depositada no corpo do paciente atrav?s do conceito de matriz de dose, e ? apresentada a fun??o objetivo deste modelo. A complexidade dos problemas de otimiza??o do tratamento radioter?pico s?o classificados como de complexidade NP, este resultado justifica o desenvolvimento de m?todos heur?sticos para a sua resolu??o. S?o propostas tr?s metaheur?sticas para a Otimiza??o do Plano de Tratamento Radioter?pico: MOGA, MOSA e MOTS de acordo como o modelo gen?rico de otimiza??o proposto. Os projetos desses procedimentos metaheur?sticos s?o devidamente apresentados. Para cada m?todo se faz uma introdu??o liter?ria, dos seus algoritmos e a da metodologia usada para a afina??o dos par?metros. Os m?todos s?o aplicados a um caso concreto e confrontados atrav?s de medidas de performance. Finalmente ? analisado a qualidade dos conjuntos de Pareto produzidos por cada m?todo, s?o exibidas algumas solu??es geradas e as respectivas curvas de Pareto associadas

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

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