Spelling suggestions: "subject:"metaheur?sticas"" "subject:"metaheuris?sticas""
11 |
O problema do caixeiro viajante alugador : um estudo algor?tmicoSilva, Paulo Henrique Asconavieta da 19 December 2011 (has links)
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
|
12 |
Otimiza??o em comit?s de classificadores: uma abordagem baseada em filtro para sele??o de subconjuntos de atributosSantana, Laura Emmanuella Alves dos Santos 02 February 2012 (has links)
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
|
13 |
Um estudo algor?tmico para otimiza??o do plano de tratamento da radioterapia conformalAra?jo, Frederiko Stenio Lu?s Neves de 16 February 2006 (has links)
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
|
14 |
Algor?tmo evolucion?rio para a distribui??o de produtos de petr?leo por redes de polidutosSouza, Thatiana Cunha Navarro de 02 March 2010 (has links)
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
|
15 |
O problema do caixeiro alugador com coleta de bonus: um estudo algoritmico / Prize Collecting Traveling Car Renter Problem: an Algotithm StudyMenezes, Matheus da Silva 21 March 2014 (has links)
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
|
Page generated in 0.0497 seconds