Use este identificador para citar ou linkar para este item: http://riu.ufam.edu.br/handle/prefix/3756
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.advisor1Jorge Yoshio Kanda-
dc.creatorRenata Costa de Melo-
dc.date.accessioned2016-09-23T15:39:21Z-
dc.date.available2016-09-23T15:39:21Z-
dc.date.issued2014-07-31-
dc.identifier.urihttp://riu.ufam.edu.br/handle/prefix/3756-
dc.description.resumoO Problema do Caixeiro Viajante (PCV) é um problema clássico na área de computacional. Informalmente, um PCV é dado por um conjunto de cidades, um conjunto de conexões entre pares de cidades e o custo para viajar entre duas cidades adjacentes. Uma solução factível para o PCV é uma rota que inicia em uma das cidades do problema, vista as demais cidades uma única vez e retorna para a cidade inicial (Gutin e Punnen, 2002). Para o PCV, a melhor solução (uma solução ótima) é a rota de menor custo possível dado pela função objetivo que avalia as soluções representadas pelas combinações dos diferentes valores para as variáveis do problema (Arenales et al., 2007). Uma alternativa para encontrar uma solução ótima para um PCV seria analisar todas as soluções factíveis e selecionar a que tem o melhor valor de otimização. Contudo, essa análise é impraticável para muitas instâncias do PCV, pois o tempo computacional pode ser alto, já que o número de diferentes soluções factíveis é o resultado de uma função fatorial que depende do número de cidades do problema (Winston, 1994). Esse tempo pode ser reduzido se for gerada uma boa solução, próxima a uma solução ótima. Para isso, existem diferentes abordagens, tais como: os métodos exatos e os métodos heurísticos. A primeira abordagem processa soluções de forma determinística por meio de mecanismos subjacentes aos mesmos que direcionam as buscas no espaço de soluções, enquanto a segunda é aplicável quando não se tem um modelo exato, sendo necessária a flexibilidade para manipular as características do problema. No entanto, as heurísticas não garantem a qualidade da solução gerada, pois muitas vezes não se conhece uma solução ótima para comparar com a solução gerada (Arenales et al., 2007). Por isso, meta-Heurísticas (MHs) são bastante usadas para obter boas soluções para o PCV. MHs são técnicas que processam uma interação entre os procedimentos de melhoria local e estratégias de alto nível, capazes de escapar das soluções ótimas locais de baixa qualidade e realizar uma busca robusta no espaço de soluções (Gendreau e Potvin, 2010). O PCV é usado para modelar aplicações de diferentes áreas, como por exemplo: problema de roteamento de veículos. Para essa aplicação, algoritmos genéticos têm sido usados com sucesso (Subramanian et al., 2010). O método embutido nesses algoritmos considera que Indivíduos mais aptos têm maiores chances de sobrevivência e de produzirem filhos cada vez mais aptos. Uma solução factível para um PCV representa um indivíduo. Todos os indivíduos da população são avaliados por uma função de aptidão que mensura a sua capacidade de sobrevivência. A evolução das espécies é feita a partir da seleção dos indivíduos mais aptos cujos genes são combinados por meio de operadores genéticos e/ou de mutação para gerar novos indivíduos. O aspecto probabilístico inerente ao processo de seleção garante a diversidade populacional, permitindo que uma boa solução seja obtida de maneira rápida. (Goldberg, 1989).pt_BR
dc.description.sponsorshipUFAMpt_BR
dc.formatPDF-
dc.languagept_BRpt_BR
dc.publisherUniversidade Federal do Amazonaspt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentInstituto de Ciências Exatas e Tecnologia - Itacoatiarapt_BR
dc.publisher.programPROGRAMA PIBIC 2013pt_BR
dc.publisher.initialsUFAMpt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectAlgoirtmos-
dc.subjectOtimização-
dc.subject.cnpqCIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃOpt_BR
dc.titleEstudo, análise e implementação de algoritmo baseado no método de otimização evolucionário para resolver problemas do caixeiro viajantept_BR
dc.typeRelatório de Pesquisapt_BR
dc.pibic.cursoSistemas de Informaçãopt_BR
dc.pibic.nrprojetoPIB-E/0025/2013-
dc.pibic.projetoEstudo, análise e implementação de algoritmo baseado no método de otimização evolucionário para resolver problemas do caixeiro viajante-
dc.pibic.dtinicio2013-08-01-
dc.pibic.dtfim2014-07-31-
Aparece nas coleções:Relatórios finais de Iniciação Científica - Ciências Exatas e da Terra

Arquivos associados a este item:
Arquivo TamanhoFormato 
PIB-E-0025.pdf4,44 MBAdobe PDFVisualizar/Abrir
Mostrar registro simples do item Recomendar este item


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.