Página 1 dos resultados de 97 itens digitais encontrados em 0.039 segundos

Rede neural recorrente com perturbação simultânea aplicada no problema do caixeiro viajante; Recurrent neural network with simultaneous perturbation applied to traveling salesman problem

Benini, Fabriciu Alarcão Veiga
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 15/12/2008 PT
Relevância na Pesquisa
126.67%
O presente trabalho propõe resolver o clássico problema combinatorial conhecido como problema do caixeiro viajante. Foi usado no sistema de otimização de busca do menor caminho uma rede neural recorrente. A topologia de estrutura de ligação das realimentações da rede adotada aqui é conhecida por rede recorrente de Wang. Como regra de treinamento de seus pesos sinápticos foi adotada a técnica de perturbação simultânea com aproximação estocástica. Foi elaborado ainda uma minuciosa revisão bibliográfica sobre todos os temas abordados com detalhes sobre a otimização multivariável com perturbação simultânea. Comparar-se-á também os resultados obtidos aqui com outras diferentes técnicas aplicadas no problema do caixeiro viajante visando propósitos de validação.; This work proposes to solve the classic combinatorial optimization problem known as traveling salesman problem. A recurrent neural network was used in the system of optimization to search the shorter path. The structural topology linking the feedbacks of the network adopted here is known by Wang recurrent network. As learning rule to find the appropriate values of the weights was used the simultaneous perturbation with stochastic approximation. A detailed bibliographical revision on multivariable optimization with simultaneous perturbation is also described. Comparative results with other different techniques applied to the traveling salesman are still presented for validation purposes.

Uso de meta-aprendizado na recomendação de meta-heurísticas para o problema do caixeiro viajante; Using meta-learning on the recommendation of meta-heuristics for the traveling salesman problem

Kanda, Jorge Yoshio
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 07/12/2012 PT
Relevância na Pesquisa
126.6%
O problema do caixeiro viajante (PCV) é um problema clássico de otimização que possui diversas variações, aplicações e instâncias. Encontrar a solução ótima para muitas instâncias desse problema é geralmente muito difícil devido o alto custo computacional. Vários métodos de otimização, conhecidos como meta-heurísticas (MHs), são capazes de encontrar boas soluções para o PCV. Muitos algoritmos baseados em diversas MHs têm sido propostos e investigados para diferentes variações do PCV. Como não existe um algoritmo universal que encontre a melhor solução para todas as instâncias de um problema, diferentes MHs podem prover a melhor solução para diferentes instâncias do PCV. Desse modo, a seleção a priori da MH que produza a melhor solução para uma dada instância é uma tarefa difícil. A pesquisa desenvolvida nesta tese investiga o uso de abordagens de meta-aprendizado para selecionar as MHs mais promissoras para novas instâncias de PCV. Essas abordagens induzem meta-modelos preditivos a partir do treinamento das técnicas de aprendizado de máquina em um conjunto de meta-dados. Cada meta-exemplo, em nosso conjunto de meta-dados, representa uma instância de PCV descrita por características (meta-atributos) do PCV e pelo desempenho das MHs (meta-atributo alvo) para essa instância. Os meta-modelos induzidos são usados para indicar os valores do meta-atributo alvo para novas instâncias do PCV. Vários experimentos foram realizados durante a investigação desta pesquisa e resultados importantes foram obtidos; The traveling salesman problem (TSP) is a classical optimization problem that has several variations...

Relax and cut: limitantes duais para o problema do caixeiro viajante

Kawashima, Makswell Seyiti
Fonte: Universidade Estadual Paulista (UNESP) Publicador: Universidade Estadual Paulista (UNESP)
Tipo: Dissertação de Mestrado Formato: 80 f. : il., tabs.
POR
Relevância na Pesquisa
126.68%
Pós-graduação em Matemática - IBILCE; The Traveling Salesman Problem (TSP) is a classical Combinatorial Optimization problem. Given a set of cities and travel costs between each pair of them, the objective is to find a tour through all the cities, visiting each city once, and returning to the city of origin with minimum total cost. The simple enunciate and non-trivial resolution enchanted many people through the years. In the literature various formulations for the Traveling Salesman Problem are presented, and the quality of the linear relaxation of such formulations is compared. The classical TSP formulation is strong, but have an exponencial number of constraints, and is equivalent to the multi-commodity formulation, of polinomial order. The computational cost to solve the linear relaxation of the multi-commodity formulation is high, stimulating the search of new ways of obtaining dual bounds. In the literature, procedures to obtain dual bounds to the TSP using the relax and cut technique are proposed, starting from the assignment problem (AP) and dualizing violated valid inequalities by the AP’s optimal solution. In this work, we propose an application of the relax and cut technique to the multi-commodity formulation for the TSP. The results obtained by the computational study are encouraging...

Algoritmo memetico para o problema do caixeiro viajante assimetrico como parte de um framework para algoritmos evolutivos

Luciana Salete Buriol
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 21/02/2000 PT
Relevância na Pesquisa
126.81%
Dentre a gama de técnicas heurísticas e exatas existentes para a resolução de problemas combinatórios, os algoritmos populacionais genéticos e meméticos têm se destacado devido a sua boa performance. Em especial, os algoritmos meméticos podem ser considerados atualmente como uma das técnicas melhores sucedidas para a resolução de vários problemas combinatórios, dentre eles, o problema do caixeiro viajante. Nesta dissertação será apresentado um algoritmo memético aplicado ao problema do caixeiro viajante assimétrico, com a proposta de uma nova busca local: Recursive Arc Insertion. Os resultados computacionais considerando as 27 instâncias assimétricas da TSPLIB são apresentados, analisados e comparados com resultados obtidos por outros métodos propostos para o problema. O mesmo algoritmo é também aplicado a 32 outras instâncias assimétricas e a 30 instâncias reduzidas do problema de ciclos hamiltonianos não direcionados. Um framework para algoritmos evolutivos é apresentado, já incluindo o algoritmo memético implementado e a redução de instâncias do problema de ciclos hamiltonianos não direcionados para o problema do caixeiro viajante simétrico. Além disso, dois geradores portáveis de instâncias com solução ótima conhecida são descritos: um para o problema do caixeiro viajante assimétrico e outro para o problema de ciclos hamiltonianos; Among the range of heuristic and exact techniques for solving combinatorial problems...

Aplicações de meta-heuristica genetica e fuzzy no sistema de colonia de formigas para o problema do caixeiro viajante; Aplications of genetic and fuzzy metaheusistic in the ant colony system for the traveling salesman problem

Marcia Braga de Carvalho
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 27/07/2007 PT
Relevância na Pesquisa
126.66%
Dentre as várias técnicas heurísticas e exatas existentes para a resolução de problemas combinatórios, os algoritmos populacionais de otimização por colônia de formigas e genéticos têm se destacado devido à sua boa performance. Em especial os algoritmos de colônia de formigas são considerados atualmente como uma das técnicas mais bem sucedidas para a resolução de vários problemas combinatórios, dentre eles o problema do caixeiro viajante. Neste trabalho é apresentado um algoritmo híbrido que trabalha com as meta-heurísticas de sistema de colônia de formigas e genético conjuntamente aplicados no problema do caixeiro viajante simétrico. Além disso, apresentamos uma proposta para o algoritmo de formigas quando temos incertezas associadas aos parâmetros do problema. Os resultados obtidos com as metodologias propostas apresentam resultados satisfatórios para todas as instâncias utilizadas; Amongst the several existing heuristical and accurate techniques for the resolution of combinatorial problems, the population algorithms ant colony optimization and genetic have been detached due to their good performance. In special the ant colony algorithms are considered currently as one of the techniques most succeeded for the resolution of some combinatorial problems...

Grupos de visitação na AMAN : um estudo de caso do problema do caixeiro viajante; Groups visiting the Military Academy of Agulhas Negras : a case study of the travelling salesman problem

Rogerio Carvalho Mendes Tavora
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 07/01/2011 PT
Relevância na Pesquisa
126.53%
Comemorando os 200 anos de Academia Militar no Brasil a partir de março de 2011, estão previstas várias implementações e melhorias na estrutura de visitação da AMAN que, consequentemente, vão gerar um aumento substancial no número de grupos visitantes no ano de seu bicentenário. Diante dos fatos percebe-se a necessidade de um modelo matemático eficiente cuja finalidade seja permitir aos grupos visitantes percorrerem trajetos otimizados, ou seja, que passem pelos pontos principais de visitação no menor tempo e distância possíveis. O modelo matemático a ser adotado neste trabalho é o Problema do Caixeiro Viajante (Traveling Salesman Problem - TSP), um clássico da Otimização Combinatória pertencente `a classe de problemas NP - difícil, que já possui eficientes algoritmos desenvolvidos. Serão utilizadas heurísticas próprias para a resolução do TSP com o intuito de se obter numericamente itinerários ótimos de visitação, considerando os diferentes grupos visitantes e suas dificuldades de acesso, dentre outras particularidades.; Celebrating 200 years of the Military Academy in Brazil from March 2011, provides a lot of implementations and improvements in the structure of visitation of AMAN, consequently, will generate substantial growth in the number of visiting groups in the year of its bicentennial. Given the facts we see the need for an efficient mathematical model whose purpose is to allow visitors to wander paths optimized groups...

O problema do caixeiro viajante com restrições de empacotamento tridimensional; The traveling salesman problem with three-dimensional loading constraints

Pedro Henrique Del Bianco Hokama
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 14/10/2011 PT
Relevância na Pesquisa
126.69%
Nesta dissertação de mestrado apresentamos um método exato para o Problema do Caixeiro Viajante com Restrições de Empacotamento Tridimensional, que combina o Problema do Caixeiro Viajante o Problema de Empacotamento Tridimensional com Restrição de Ordem. Neste problema, um veículo deve partir carregado de um depósito e entregar caixas em pontos pré-definidos para seus clientes. Cada cliente tem um conjunto de caixas que deve receber e o objetivo é minimizar o custo de deslocamento do veículo. As caixas devem ser retiradas a partir da porta do contêiner do veículo e a remoção das caixas de um cliente não podem ser obstruídas pelas caixas a serem descarregadas posteriormente. Propomos uma abordagem exata baseada em branch-and-cut para buscar uma rota de custo mínimo. Apresentamos algumas adaptações de algoritmos da literatura e uma formulação em Programação por Restrições para encontrar um empacotamento que obedece restrições de ordem. Realizamos testes computacionais em instâncias geradas aleatoriamente e comparamos resultados com os algoritmos adaptados da literatura. Os resultados foram bastante satisfatórios resolvendo instâncias de tamanho médio em tempo computacional aceitável na prática.; We present an exact method for the Traveling Salesman Problem with Three-dimensional Loading Constraints. This problem combines the Traveling Salesman Problem...

Problema do caixeiro viajante

Rodrigues, Marco Antonio Pereira
Fonte: Florianópolis, SC Publicador: Florianópolis, SC
Tipo: Dissertação de Mestrado Formato: xii, 125f.| il., tabs.
POR
Relevância na Pesquisa
126.53%
Dissertação (Mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico.; Neste trabalho é proposto um algoritmo para a resolução do Problema do Caixeiro Viajante (PCV), baseado em estratégia de particionamento, que atua em conjunto com a recém a apresentada metaheurística Busca Local Dirigida (BLD). Testes são realizados para avaliar a qualidade desse algoritmo, frente a um outro procedimento, também baseado em estratégia de particionamento, sobre problemas da biblioteca TSPLIB de Reinelt. Verificou-se que o algoritmo proposto é capaz de gerar bons resultados, em tempo relativamente curto. Algumas sugestões e considerações são apresentadas para o desenvolvimento de futuros trabalhos.

Implementação e análise do problema caixeiro viajante usando uma nova abordagem através dos algoritmos genético e simulated annealing

Ramos, José Márcio Benite
Fonte: Florianópolis, SC Publicador: Florianópolis, SC
Tipo: Dissertação de Mestrado Formato: ii, 218 f.| il., tabs., grafs.
POR
Relevância na Pesquisa
106.57%
Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação.; Atualmente observa-se uma forte tendência em se utilizar métodos aproximados na resolução de problemas de otimização combinatorial. Esses métodos, que muitas vezes vêm em substituição a métodos exatos, nem sempre garantem uma solução ótima para um problema, porém, normalmente são capazes de oferecer solução aproximada de boa qualidade, em um tempo de processamento aceitável. Neste trabalho é apresentada e investigada uma nova proposta de um método de aproximação baseado na combinação dos algoritmos Genético (AG) e Simulated Annealing (SA). Na observação do seu comportamento foi utilizado o notório problema de otimização combinatorial, de complexidade NP-completo, conhecido como o Problema do Caixeiro Viajante (PCV).

Problema do caixeiro viajante

Carla Sofia de Assunção Gomes
Fonte: Universidade de Aveiro Publicador: Universidade de Aveiro
Tipo: Dissertação de Mestrado
POR
Relevância na Pesquisa
126.6%
O Problema do Caixeiro Viajante (PCV) pode ser entendido como o problema de um vendedor que deseja visitar um conjunto de cidades, passando exactamente uma vez por cada uma e voltando ao ponto de partida no final do seu percurso. O PCV está classificado como NP- Completo, o que faz com que seja de muito difícil resolução. A grande dificuldade na obtenção da solução óptima deste tipo de problemas, deve-se ao elevado número de restrições que cresce exponencialmente com o número de clientes. Neste trabalho, começamos por introduzir o problema com exemplos bastante simples, onde são exibidos métodos heurísticos para a sua resolução. De seguida, é feita uma abordagem mais formal, onde são apresentados vários resultados que permitem reduzir substancialmente o número de restrições. Posteriormente, é feito um estudo de várias instâncias do problema, de forma a averiguar o comportamento das restrições de eliminação de sub-ciclos e o modo como estas se influenciam mutuamente. A grande parte dos testes efectuados neste trabalho apontam para a existência de uma forte redundância, do ponto de vista prático, na maior parte das restrições de eliminação de sub- -ciclos. Assim, os resultados obtidos indicam que apenas uma pequena percentagem das restrições de eliminação de sub-ciclos é necessária para a obtenção da solução óptima do problema.; The Travelling Salesman Problem (TSP) can be seen as a problem of a salesman that wants to visit a set of cities...

Metaheurísticas híbridas para resolução do problema do caixeiro viajante com coleta de prêmios

Chaves,Antonio Augusto; Biajoli,Fabrício Lacerda; Mine,Otávio Massashi; Souza,Marcone Jamilson Freitas
Fonte: Associação Brasileira de Engenharia de Produção Publicador: Associação Brasileira de Engenharia de Produção
Tipo: Artigo de Revista Científica Formato: text/html
Publicado em 01/08/2007 PT
Relevância na Pesquisa
126.61%
O Problema do Caixeiro Viajante com Coleta de Prêmios (PCVCP) pode ser associado a um caixeiro que coleta um prêmio em cada cidade visitada e paga uma penalidade para cada cidade não visitada, com um custo de deslocamento entre as cidades. O problema encontra-se em minimizar o somatório dos custos da viagem e penalidades, enquanto inclui na sua rota um número suficiente de cidades que lhe permita coletar um prêmio mínimo preestabelecido. Este trabalho contribui com o desenvolvimento de metaheurísticas híbridas para o PCVCP, baseadas em GRASP e métodos de busca em vizinhança variável (VNS/VND) para solucionar aproximadamente o PCVCP. De forma a validar as soluções obtidas, propõe-se uma formulação matemática a ser resolvida por um solver comercial, objetivando encontrar a solução ótima para o problema, sendo este solver aplicado a problemas de pequeno porte. Resultados computacionais demonstram a eficiência da abordagem híbrida proposta, tanto em relação à qualidade da solução final obtida quanto em relação ao tempo de execução.

Algoritmos Evolucionários Aplicados ao Problema do Caixeiro Viajante Multiobjetivo.

Farias, Max Santana Rolemberg
Fonte: Universidade Federal de Alagoas; BR; Modelagem Computacional de Conhecimento; Programa de Pós-Graduação em Modelagem Computacional de Conhecimento; UFAL Publicador: Universidade Federal de Alagoas; BR; Modelagem Computacional de Conhecimento; Programa de Pós-Graduação em Modelagem Computacional de Conhecimento; UFAL
Tipo: Dissertação Formato: application/pdf
POR
Relevância na Pesquisa
126.61%
This work presents a general vision about the main concepts of combinatorial multi-objective optimization, where we present the more used technique for the resolution of problems of this nature. To the speech of the techniques we will also argue important aspects how much to the involved parameters in each technique, swing the main used boardings. Initially we implement and test the Multiple Objective Genetic Algorithm MOGA to generate a set of dominant solutions near to the Pareto optimal set for the biobjective Traveling Salesman Problems. In a second phase, we will go to implement the Strength Pareto Evolutionary Algorithm (SPEA) applied to biobjective Traveling Salesman Problems; Este trabalho apresenta uma visão geral sobre os principais conceitos da otimização combinatória multiobjetivo, onde apresentamos as técnicas mais utilizadas para a resolução de problemas desta natureza. Ao falarmos das técnicas, discutiremos também aspectos importantes quanto aos parâmetros envolvidos em cada técnica, mostrando as principais abordagens utilizadas. Inicialmente, implementamos e testamos o Multiple Objective Genetic Algorithm (MOGA) para gerar um conjunto de soluções dominantes próximo ao conjunto de Pareto ótimo para o problema do caixeiro viajante biobjetivo. Em uma segunda fase...

Modelagem e otimização do problema do caixeiro viajante com restrições de tempo, distância e confiabilidade via algoritmos genéticos

Augusto Silva Braga, Edgar; Andrés López Droguett, Enrique (Orientador)
Fonte: Universidade Federal de Pernambuco Publicador: Universidade Federal de Pernambuco
Tipo: Outros
PT_BR
Relevância na Pesquisa
126.69%
Neste trabalho, propõe-se uma metodologia de modelagem para problemas de roteirização de veículos baseada no Problema do Caixeiro Viajante. Mais especificadamente, busca-se tornar o Problema do Caixeiro Viajante com Coletas de Prêmios mais coerente com a realidade do contexto logístico, levando em conta a capacidade operacional da organização e restrições mercadológicas. Para tal, são introduzidos novos elementos como a confiabilidade do caixeiro e restrições de tempo para realizar o roteiro. O modelo consiste, então, em maximizar o lucro obtido através da coleta de prêmios e do custo associado ao roteiro, sujeito a restrições de tempo máximo e confiabilidade mínima aceita ao final do percurso. Esta nova abordagem é modelada e resolvida via Algoritmos Genéticos e é ilustrada através de um estudo de caso

Proposta de otimização e sistematização na entrega de bens permanentes no Poder Judiciário do Paraná

Cardoso Neto, João
Fonte: Universidade Federal do Paraná Publicador: Universidade Federal do Paraná
Tipo: Dissertação Formato: application/pdf
PORTUGUêS
Relevância na Pesquisa
116.37%
Resumo: Os bens permanentes adquiridos pelo Poder Judiciário estadual ficam centralizados em Curitiba, este Poder possui o total de 160 (cento e sessenta) Comarcas espalhadas espacialmente por todo o território paranaense. Para tanto, considerando que os serviços prestados pela administração pública devem ser norteados pelo princípio da eficiência, no qual está inserido o uso racional do serviço público e do dinheiro público, a entrega destes bens permanentes às Comarcas do estado deve ser feita de forma otimizada. Para tanto, esta Dissertação de Mestrado apresenta uma proposta de otimização e sistematização na entrega de bens permanentes no Poder Judiciário do Paraná. A fim de atingir o objetivo a que se propõe, mensalmente são determinadas medianas, considerando as Comarcas que necessitam de entrega de bens permanentes, para a determinação destas medianas é utilizado o algoritmo de Teitz e Bart. Com a definição de quais são as medianas, estas servem de semente para o agrupamento das Comarcas demandantes, o que é feito com a aplicação do algoritmo de Gillet e Johnson modificado. Com as Comarcas já agrupadas, é traçado o roteiro ótimo para a entrega dos bens permanentes, utilizando o método exato...

Estratégias de aplicações sequenciais e paralelas da metaheurística otimização por enxame de partículas ao problema do caixeiro viajante

Silva, Thales Lima
Fonte: Universidade Federal do Rio Grande do Norte; BR; UFRN; Programa de Pós-Graduação em Engenharia de Produção; Estratégia; Qualidade; Gestão Ambiental; Gestão da Produção e Operações Publicador: Universidade Federal do Rio Grande do Norte; BR; UFRN; Programa de Pós-Graduação em Engenharia de Produção; Estratégia; Qualidade; Gestão Ambiental; Gestão da Produção e Operações
Tipo: Dissertação Formato: application/pdf
POR
Relevância na Pesquisa
136.54%
Particle Swarm Optimization is a metaheuristic that arose in order to simulate the behavior of a number of birds in flight, with its random movement locally, but globally determined. This technique has been widely used to address non-liner continuous problems and yet little explored in discrete problems. This paper presents the operation of this metaheuristic, and propose strategies for implementation of optimization discret problems as form of execution parallel as sequential. The computational experiments were performed to instances of the TSP, selected in the library TSPLIB contenct to 3038 nodes, showing the improvement of performance of parallel methods for their sequential versions, in executation time and results; Otimização por Enxame de Partículas ou Particle Swarm Optimization (PSO) é uma metaheurística que surgiu na intenção de simular o comportamento de um conjunto de pássaros em vôo, com seu movimento localmente aleatório, mas globalmente determinado. Esta técnica tem sido muito utilizada na resolução de problemas contínuos não-lineares e ainda pouco explorada em problemas discretos. Este trabalho apresenta o funcionamento desta metaheurística, além de propor estratégias para sua aplicação em problemas de otimização discreta tanto na sua forma de execução seqüencial quanto paralela. Os experimentos computacionais foram realizados para instâncias do problema do caixeiro viajante...

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 problem

Fontes, Fábio Francisco da Costa
Fonte: Universidade Federal do Rio Grande do Norte; BR; UFRN; Programa de Pós-Graduação em Engenharia de Produção; Estratégia; Qualidade; Gestão Ambiental; Gestão da Produção e Operações Publicador: Universidade Federal do Rio Grande do Norte; BR; UFRN; Programa de Pós-Graduação em Engenharia de Produção; Estratégia; Qualidade; Gestão Ambiental; Gestão da Produção e Operações
Tipo: Dissertação Formato: application/pdf
POR
Relevância na Pesquisa
136.67%
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...

Metodologia estatística na solução do problema do caixeiro viajante e na avaliação de algoritmos : um estudo aplicado à transgenética computacional

Ramos, Iloneide Carlos de Oliveira
Fonte: Universidade Federal do Rio Grande do Norte; BR; UFRN; Programa de Pós-Graduação em Engenharia Elétrica; Automação e Sistemas; Engenharia de Computação; Telecomunicações Publicador: Universidade Federal do Rio Grande do Norte; BR; UFRN; Programa de Pós-Graduação em Engenharia Elétrica; Automação e Sistemas; Engenharia de Computação; Telecomunicações
Tipo: Tese de Doutorado Formato: application/pdf
POR
Relevância na Pesquisa
136.55%
The problems of combinatory optimization have involved a large number of researchers in search of approximative solutions for them, since it is generally accepted that they are unsolvable in polynomial time. Initially, these solutions were focused on heuristics. Currently, metaheuristics are used more for this task, especially those based on evolutionary algorithms. The two main contributions of this work are: the creation of what is called an -Operon- heuristic, for the construction of the information chains necessary for the implementation of transgenetic (evolutionary) algorithms, mainly using statistical methodology - the Cluster Analysis and the Principal Component Analysis; and the utilization of statistical analyses that are adequate for the evaluation of the performance of the algorithms that are developed to solve these problems. The aim of the Operon is to construct good quality dynamic information chains to promote an -intelligent- search in the space of solutions. The Traveling Salesman Problem (TSP) is intended for applications based on a transgenetic algorithmic known as ProtoG. A strategy is also proposed for the renovation of part of the chromosome population indicated by adopting a minimum limit in the coefficient of variation of the adequation function of the individuals...

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étrico

Silva Neto, João Saturnino da
Fonte: Universidade Federal do Rio Grande do Norte; BR; UFRN; Programa de Pós-Graduação em Matemática Aplicada e Estatística; Probabilidade e Estatística; Modelagem Matemática Publicador: Universidade Federal do Rio Grande do Norte; BR; UFRN; Programa de Pós-Graduação em Matemática Aplicada e Estatística; Probabilidade e Estatística; Modelagem Matemática
Tipo: Dissertação Formato: application/pdf
POR
Relevância na Pesquisa
136.56%
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...

O problema do caixeiro viajante alugador : um estudo algorítmico

Silva, Paulo Henrique Asconavieta da
Fonte: Universidade Federal do Rio Grande do Norte; BR; UFRN; Programa de Pós-Graduação em Sistemas e Computação; Ciência da Computação Publicador: Universidade Federal do Rio Grande do Norte; BR; UFRN; Programa de Pós-Graduação em Sistemas e Computação; Ciência da Computação
Tipo: Tese de Doutorado Formato: application/pdf
POR
Relevância na Pesquisa
126.63%
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...

Uma análise experimental de abordagens heurísticas aplicadas ao problema do caixeiro viajante

Prestes, álvaro Nunes
Fonte: Universidade Federal do Rio Grande do Norte; BR; UFRN; Programa de Pós-Graduação em Sistemas e Computação; Ciência da Computação Publicador: Universidade Federal do Rio Grande do Norte; BR; UFRN; Programa de Pós-Graduação em Sistemas e Computação; Ciência da Computação
Tipo: Dissertação Formato: application/pdf
POR
Relevância na Pesquisa
126.5%
Due to great difficulty of accurate solution of Combinatorial Optimization Problems, some heuristic methods have been developed and during many years, the analysis of performance of these approaches was not carried through in a systematic way. The proposal of this work is to make a statistical analysis of heuristic approaches to the Traveling Salesman Problem (TSP). The focus of the analysis is to evaluate the performance of each approach in relation to the necessary computational time until the attainment of the optimal solution for one determined instance of the TSP. Survival Analysis, assisted by methods for the hypothesis test of the equality between survival functions was used. The evaluated approaches were divided in three classes: Lin-Kernighan Algorithms, Evolutionary Algorithms and Particle Swarm Optimization. Beyond those approaches, it was enclosed in the analysis, a memetic algorithm (for symmetric and asymmetric TSP instances) that utilizes the Lin-Kernighan heuristics as its local search procedure; Devido à grande dificuldade de solução exata dos Problemas de Otimização Combinatória, vários métodos heurísticos têm sido desenvolvidos e durante muitos anos, a análise de desempenho dessas abordagens não foi realizada de maneira sistemática. A proposta deste trabalho é fazer uma análise estatística de abordagens heurísticas aplicadas ao Problema do Caixeiro Viajante. O foco da análise é avaliar o desempenho de cada abordagem em relação ao tempo computacional necessário até a obtenção da solução ótima para uma determinada instância do PCV. Para essa análise...