Navegar por:

Uma nova abordagem na resolução do problema do caixeiro viajante

Use este link compartilhar ou citar este material: http://educapes.capes.gov.br/handle/1884/2562
Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorScheer, Sérgio, 1957--
Autor(es): dc.contributorSteiner, Maria Teresinha Arns, 1957--
Autor(es): dc.contributorUniversidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Métodos Numéricos em Engenharia-
Autor(es): dc.creatorSiqueira, Paulo Henrique-
Data de aceite: dc.date.accessioned2025-09-01T11:54:51Z-
Data de disponibilização: dc.date.available2025-09-01T11:54:51Z-
Data de envio: dc.date.issued2025-04-29-
Data de envio: dc.date.issued2025-04-29-
Data de envio: dc.date.issued2005-
Fonte completa do material: dc.identifierhttps://hdl.handle.net/1884/2562-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/1884/2562-
Descrição: dc.descriptionOrientador: Sergio Scheer-
Descrição: dc.descriptionCoorientadora: Maria Teresinha Arns Steiner-
Descrição: dc.descriptionTese (doutorado) - Universidade Federal do Paraná, Setores de Tecnologia e Ciências Exatas, Programa de Pós-Graduação em Métodos Numéricos em Engenharia. Defesa: Curitiba, 2005-
Descrição: dc.descriptionInclui bibliografia-
Descrição: dc.descriptionResumo: Neste trabalho são apresentadas duas Redes Neurais Recorrentes para resolver o problema da Designação Linear. Na fase inicial do problema, onde os elementos da matriz de custos do problema da Designação devem ser determinados, utiliza-se Mapas de Kohonen, conhecidos também como Mapas Auto-Organizáveis, e na resolução do problema da Designação propriamente dito, a técnica utilizada é a Rede Neural Recorrente de Wang, com a aplicação de um princípio aqui proposto, denominado Winner Takes All. A fase de definição dos custos na resolução de um problema da Designação é de grande importância, pois se os custos não forem determinados de forma adequada, a solução final não será a ideal. O cálculo de custos para problemas da Designação com a utilização de Redes Neurais Artificiais é um assunto pouco explorado, que depende do tipo de aplicação pretendida. Quando a matriz de custos do problema da Designação é tal que admite múltiplas soluções ótimas, ou soluções ótimas locais muito próximas, a Rede Neural de Wang não converge, e a proposta apresentada neste trabalho mostra a utilização do princípio Winner Takes All para esta rede, obtendo-se soluções ótimas globais na maioria das matrizes testadas, utilizando-se aproximadamente 1% do número necessário de iterações da Rede de Wang original. Neste trabalho são apresentados os resultados da aplicação desta técnica (a Rede Neural Recorrente de Wang com o princípio Winner Takes All) para 73 matrizes com custos definidos aleatoriamente para o problema da Designação, além de alguns critérios para ajustes de parâmetros da Rede Neural de Wang, entre eles alguns tradicionais, e outros que utilizam medidas de dispersão entre os elementos da matriz de custos do problema. A metodologia proposta neste trabalho é aplicada em um estudo de caso: o Problema de Alocação de Salas de Aula para disciplinas de graduação e pós-graduação da UFPR, onde são testados mapas com diversas dimensões para a determinação dos custos deste problema. Os resultados encontrados com a aplicação desta metodologia no estudo de caso são considerados satisfatórios, com erro médio na solução final da Designação inferior a 3% para os melhores mapas encontrados. Uma outra aplicação da Rede Neural de Wang com o princípio Winner Takes All é a resolução do problema clássico do Caixeiro Viajante, com soluções ótimas globais em vários problemas do banco de dados TSPLIB, e com soluções ótimas locais com erros inferiores a 16%. Para aplicar a metodologia proposta neste trabalho para o problema do Caixeiro Viajante uma adaptação do princípio Winner Takes All é feita, obtendo-se sempre rotas factíveis para este problema. A mesma técnica é utilizada para problemas do Caixeiro Viajante simétricos e assimétricos, e a técnica 2-opt é utilizada para melhorar as soluções encontradas.-
Descrição: dc.descriptionAbstract: In this work two Recurrent Neural Networks are presented to solve the Linear Assignment problem. In the initial phase of the problem, where the Assignment problem’s costs’ must be determined, uses Kohonen Maps, also known as Self-Organizing Maps, and in the Assignment’s problem resolution properly said, the used technique is the Wang’s Recurrent Neural Network, with the application of a called "Winner Takes All" principle, proposal in this work. The phase of definition of the costs in the resolution of the Assignment problem is of great importance, therefore if the costs will not be determined of adjusted form, the final solution will not be the ideal. The calculation of costs for Assignment problems with the use of Artificial Neural Networks is a subject little explored, that depends on the type of intended application. When the Assignment problem’s cost’s matrix is such that admits multiple global optimal solutions, or very next local optimal solutions, the Wang’s Neural Network does not converge, and the proposal presented in this work shows the use of the principle "Winner Takes All" fo r this network, getting global optimal solutions in the majority of the tested matrices, using approximately 1% of the necessary number of iterations of the original Wang’s Network. In this work the results of the application of this technique (Wang’s Recurrent Neural Network with the principle "Winner Takes All") are presented for 73 matrices with random costs to the Assignment problem, beyond some criteria for adjustments of parameters of the Wang’s Neural Network, between them some traditional, and others that use measured of dispersion enter the problem’s costs. The methodology proposal in this work is applied in a case study: the Problem of Allocation of Classrooms for disciplines of graduation and post-graduation of the UFPR, where maps with many dimensions for the determination of the problem’s costs are tested. The results found with the application of this methodology in the case study are considered satisfactory, with average error in the solution of the Assignment problem less than 3% for the best-founded maps. Another application of the Wang’s Neural Network with the principle "Winner Takes All" is the resolution of the classic Traveling Salesman problem, with global optimal solutions in some problems of the data base TSPLIB, and with local optimal solutions with errors less than 16%. To apply the methodology proposal in this work for the Traveling Salesman problem an adaptation of "Winner Takes All" principle is made, getting always feasible routes for this problem. The same technique is used for symmetrical and asymmetrical Traveling Salesman problems, and the technique 2-opt is used to improve the founded solutions.-
Formato: dc.formatxiii, 102f. : il., grafs., tabs.-
Formato: dc.formatapplication/pdf-
Formato: dc.formatapplication/pdf-
Relação: dc.relationDisponível em formato digital-
Palavras-chave: dc.subjectOtimização matemática-
Palavras-chave: dc.subjectCaixeiros-viajantes-
Palavras-chave: dc.subjectRedes neurais (Computação)-
Palavras-chave: dc.subjectAnálise numérica-
Título: dc.titleUma nova abordagem na resolução do problema do caixeiro viajante-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositório Institucional - Rede Paraná Acervo

Não existem arquivos associados a este item.
Mostrar registro simples do item Visualizar estatísticas

Avaliação