| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 9.32 MB | Adobe PDF | |||
| 1.74 KB | License |
Authors
Advisor(s)
Abstract(s)
Da panóplia de meta-heurísticas disponíveis verifica-se uma tendência de utilizar um pequeno número de meta-heurísticas para resolver problemas de características semelhantes. Nos últimos anos tem-se verificado a continuada investigação das meta-heurísticas na resolução dos problemas onde demostram ser mais promissoras, permitindo cada vez melhores prestações, mas, apenas, nesses problemas específicos. Quando os problemas mais complexos são semelhantes, as metaheurísticas especializadas são as mais adequadas, porém, perante problemas mais diversificados torna-se necessário o recurso a múltiplas meta-heurísticas. Isto devido à escassez de métodos estocásticos capazes de resolver, pelos menos satisfatoriamente, problemas diversificados. Neste trabalho, pretende-se atribuir versatilidade a uma ferramenta originalmente criada para resolver problemas contínuos, a Otimização por Enxame de Partículas, ao desenvolver uma versão que consiga resolver, satisfatoriamente, problemas de otimização discretos. A Otimização por Enxame de Partículas sendo o algoritmo simples, consegue resolver efetivamente uma ampla gama de problemas, mas quando aplicado a problemas de otimização discreta, como o Problema do Caixeiro Viajante, necessita de ser adaptado para a correta interpretação e resolução do problema. Nesse sentido, foi desenvolvida a codificação adequada para a interpretação do problema discreto, a representação discreta dos resultados bem como alterações ao procedimento da meta-heurística para o devido tratamento e processamento dos dados discretos, dando origem à Otimização por Enxame de Partículas Discretas. Para a parametrização do algoritmo foi elaborado um plano de experiências com recurso à rotina de planeamento, execução, verificação e reação de cada experiência. Ao utilizar os resultados quantitativos das experiências foi possível descrevem quais as variáveis de teste que mais afetam a resposta, obter informações sobre as inter-relações entre essas mesmas variáveis ao descrever o seu efeito combinado. Embora exista espaço para melhorias, o potencial do algoritmo aqui desenvolvido torna-se evidente ao longo do trabalho. A Otimização por Enxame de Partículas Discretas foi analisado em quatro instâncias do Problema do Caixeiro Viajante, tendo obtido resultados não muito distantes dos resultados ótimos em uma das instâncias. Assim, a meta-heurística proposta evidencia que, com as devidas alterações, a Otimização por Enxame de Partículas pode obter tão bons resultados na resolução de problemas discretos, como na resolução de problemas contínuos.
From the set of meta-heuristics available, there is a tendency to use a reduced number of metaheuristics to solve problems with similar properties. In recent years, the study of meta-heuristics has continued for problems where they demonstrated to the best fit, which allowed to improve their performance, but only of that specific problem. When the most complex problems are similar, specialized meta-heuristics are best, however, to approach a multitude of problems, it is necessary to resort to multiple meta-heuristics. This is because there are few stochastic methods capable of solving diversified problems at least satisfactorily. In this work, we intend to make Particle Swarm Optimization, which was designed for continuous problems, more versatile by developing a version that can satisfactorily solve discrete optimization problems. Particle Swarm Optimization is a simple algorithm that can effectively solve a wide range of problems. But when applied to discrete optimization problems like the Traveling Salesman Problem, it needs to be adapted for proper interpretation of the problem. In this sense, a suitable coding for the interpretation of the discrete problem was developed, the discrete representation of the results and modifications to the meta-heuristic procedure for the proper treatment and processing of discrete data, resulting in the development of the Discrete Particle Swarm Optimization. An experiment plan was devised for the parameterization of the algorithm, using the Plan, Do, Check and Act routine for each experiment. Based on the quantitative results of the experiments, it was possible to describe which test variables had the greatest impact on the response. This gave us information about the relationships between these same variables when we described their combined effect. Although there is room for improvement, the potential of the algorithm developed here becomes clear as the work progresses. The Discrete Particle Swarm Optimization was analysed in four instances of the traveling salesman problem, attaining results very close to the optimal solution in one of the instances. And once the limitations observed here are overcome, the proposed metaheuristic shows that, with the necessary modifications, Particle Swarm Optimization can perform as well in solving discrete problems as it does in solving continuous problems.
From the set of meta-heuristics available, there is a tendency to use a reduced number of metaheuristics to solve problems with similar properties. In recent years, the study of meta-heuristics has continued for problems where they demonstrated to the best fit, which allowed to improve their performance, but only of that specific problem. When the most complex problems are similar, specialized meta-heuristics are best, however, to approach a multitude of problems, it is necessary to resort to multiple meta-heuristics. This is because there are few stochastic methods capable of solving diversified problems at least satisfactorily. In this work, we intend to make Particle Swarm Optimization, which was designed for continuous problems, more versatile by developing a version that can satisfactorily solve discrete optimization problems. Particle Swarm Optimization is a simple algorithm that can effectively solve a wide range of problems. But when applied to discrete optimization problems like the Traveling Salesman Problem, it needs to be adapted for proper interpretation of the problem. In this sense, a suitable coding for the interpretation of the discrete problem was developed, the discrete representation of the results and modifications to the meta-heuristic procedure for the proper treatment and processing of discrete data, resulting in the development of the Discrete Particle Swarm Optimization. An experiment plan was devised for the parameterization of the algorithm, using the Plan, Do, Check and Act routine for each experiment. Based on the quantitative results of the experiments, it was possible to describe which test variables had the greatest impact on the response. This gave us information about the relationships between these same variables when we described their combined effect. Although there is room for improvement, the potential of the algorithm developed here becomes clear as the work progresses. The Discrete Particle Swarm Optimization was analysed in four instances of the traveling salesman problem, attaining results very close to the optimal solution in one of the instances. And once the limitations observed here are overcome, the proposed metaheuristic shows that, with the necessary modifications, Particle Swarm Optimization can perform as well in solving discrete problems as it does in solving continuous problems.
Description
Keywords
Otimização por Enxame de Partículas Discretas Algoritmo Discretização Meta-heurísticas Problema do Caixeiro Viajante Planeamento de Experiências Discrete Particle Swarm Optimization Algorithm Discretization Meta-heuristics Traveling Salesman Problem Design of Experiments