Spelling suggestions: "subject:"memetic"" "subject:"emetic""
51 |
Um algoritmo h?brido para o problema de roteamento de ve?culos com frotas heterog?neasFerreira, Vanessa Danielle Santos 13 July 2011 (has links)
Made available in DSpace on 2014-12-17T14:53:00Z (GMT). No. of bitstreams: 1
VanessaDSF_DISSERT.pdf: 862759 bytes, checksum: d1e5a8faf841592d593e48b4f4218e61 (MD5)
Previous issue date: 2011-07-13 / Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico / This paper aims to propose a hybrid meta-heuristics for the Heterogeneous Fleet Vehicle Routing Problem (HVRP), which is a combinatorial optimization problem NP-hard, and is characterized by the use of a limited fleet consists of different vehicles with different capacities. The hybrid method developed makes use of a memetic algorithm associated with the component optimizer Vocabulary Building. The resulting hybrid meta-heuristic was implemented in the programming language C + + and computational experiments generated good results in relation to meta-heuristic applied in isolation, proving the efficiency of the proposed method. / O presente trabalho visa propor uma meta-heur?stica h?brida para o Problema de Roteamento de Ve?culos com Frotas Heterog?neas (PRVFH), que ? um problema de otimiza??o combinat?ria NP-dif?cil, e que se caracteriza pelo uso de uma frota limitada composta por ve?culos distintos com capacidades distintas. O m?todo h?brido desenvolvido utiliza-se de um algoritmo mem?tico associado ao componente otimizador Vocabulary Building. A meta-heur?stica h?brida resultante foi implementada na linguagem de programa??o C++ e os experimentos computacionais geraram bons resultados em rela??o ? meta-heur?stica aplicada isoladamente, comprovando a efici?ncia do m?todo proposto.
|
52 |
Algoritmo mem?tico com infec??o viral: uma aplica??o ao problema do caixeiro viajante assim?trico / Memetic algorithm with viral infection: an application to the assimetric travelling salesman problemFontes, F?bio Francisco da Costa 19 May 2006 (has links)
Made available in DSpace on 2014-12-17T14:53:23Z (GMT). No. of bitstreams: 1
FabioFCF.pdf: 875120 bytes, checksum: 089fb9e8e722351411a9dbd3d86bbef4 (MD5)
Previous issue date: 2006-05-19 / The Combinatorial Optimization is a basic area to companies who look for competitive advantages in the diverse productive sectors and the Assimetric Travelling Salesman Problem,
which one classifies as one of the most important problems of this area, for being a problem of the NP-hard class and for possessing diverse practical applications, has increased interest of researchers in the development of metaheuristics each more efficient to assist in its resolution, as it is the case of Memetic Algorithms, which is a evolutionary algorithms that it is used of the genetic operation in combination with a local search procedure. This work explores the technique of Viral Infection in one Memetic Algorithms where the infection
substitutes the mutation operator for obtaining a fast evolution or extinguishing of species (KANOH et al, 1996) providing a form of acceleration and improvement of the solution . For this it developed four variants of Viral Infection applied in the Memetic Algorithms for resolution of the Assimetric Travelling Salesman Problem where the agent and the virus pass for a symbiosis process which favored the attainment of a hybrid evolutionary algorithms and
computational viable / A Otimiza??o Combinat?ria ? uma ?rea fundamental para empresas que buscam vantagens competitivas nos diversos setores produtivos, e o Problema do Caixeiro Viajante Assim?trico, o qual se classifica como um dos mais importantes problemas desta ?rea, devido a ser um
problema da classe NP-dif?cil e tamb?m por possuir diversas aplica??es pr?ticas, tem despertado interesse de pesquisadores no desenvolvimento de Metaheur?sticas cada vez mais eficientes para auxiliar na sua resolu??o, como ? o caso do Algoritmo Mem?tico, o qual ? um algoritmo evolutivo que se utiliza dos operadores gen?ticos em combina??o com um procedimento de busca local. Este trabalho explora a t?cnica de Infec??o Viral em um Algoritmo Mem?tico, onde a infec??o substitui o operador de muta??o por conseguir uma
r?pida evolu??o ou extin??o de esp?cies (KANOH et al., 1996), proporcionando uma forma de acelera??o e melhoria da solu??o. Para isto se desenvolveu quatro variantes de Infec??o Viral aplicadas no Algoritmo Mem?tico para resolu??o do Problema do Caixeiro Viajante Assim?trico, onde o agente e o v?rus passam por um processo de Simbiose, as quais
favoreceram a obten??o de um algoritmo evolutivo h?brido e computacionalmente vi?vel
|
53 |
Aplica?a? das t?cnicas Path-relinking e Vocabulary buiding na melhoria de performance do algoritmo mem?tico para o problema do caixeiro viajante assim?tricoSilva Neto, Jo?o Saturnino da 10 July 2009 (has links)
Made available in DSpace on 2014-12-17T15:26:37Z (GMT). No. of bitstreams: 1
JoaoSSN.pdf: 5224762 bytes, checksum: 4021177e0509af10223ad40751ece2f0 (MD5)
Previous issue date: 2009-07-10 / The present essay shows strategies of improvement in a well succeded evolutionary metaheuristic to solve the Asymmetric Traveling Salesman Problem. Such steps consist in a Memetic Algorithm projected mainly to this problem. Basically this improvement applied optimizing techniques known as Path-Relinking and Vocabulary Building. Furthermore, this
last one has being used in two different ways, in order to evaluate the effects of the improvement on the evolutionary metaheuristic. These methods were implemented in C++ code and the experiments were done under instances at TSPLIB library, being possible to observe that the procedures purposed reached success on the tests done / O presente trabalho prop?e estrat?gias de melhoria em uma bem sucedida metaheur ?stica evolucionaria para a resolu??o do Problema do Caixeiro Viajante Assim?trico. Tal procedimento consiste em um algoritmo mem?tico projetado especificamente para esse problema. Essas melhorias t?m por base a aplica??o de t?cnicas de otimiza??o conhecidas como Path-Relinking e Vocabulary Building, sendo essa ?ltima t?cnica utilizada de dois modos distintos, com o intuito de avaliar os efeitos de melhoria sobre a metaheur?stica evolucion?ria empregada. Os m?todos propostos foram implementados na linguagem de programa??o C++
e os experimentos computacionais foram realizados sobre inst?ncias disponibilizadas na biblioteca TSPLIB, tornando poss?vel observar que os procedimentos propostos alcan?aram ?xito nos testes realizados
|
54 |
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
|
55 |
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
|
56 |
Le problème de job-shop avec transport : modélisation et optimisation / Job-shop with transport : its modelling and optimisationLarabi, Mohand 15 December 2010 (has links)
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.
|
Page generated in 0.1068 seconds