| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 3.69 MB | Adobe PDF |
Advisor(s)
Abstract(s)
A seleção dos parâmetros de (Meta-) Heurísticas é um processo complexo e por vezes trabalhoso, havendo casos em que abordagens baseadas em modelos de Aprendizagem Automática permitem melhorar esse processo por forma a obter combinações de parâmetros adequadas de modo automático, eficaz e eficiente. Neste trabalho é proposta uma abordagem que integra uma heurística, Elitist Particle Swarm Algorithm (EPSA), com uma camada de Clustering e outra de Classificação, com o intuito de prever as combinações de parâmetros mais promissoras para a heurística, tendo em conta a instância do problema que se pretende resolver. A heurística, EPSA, baseada no conceito das Meta-Heurísticas Particle Swarm Optimization (PSO) aplicadas a problemas de otimização discreta, é também apresentada. Esta heurística exibe duas características que, em conjunto, a diferenciam de grande parte das abordagens PSO: a existência de um grupo especial de partículas, Elite, com um comportamento distinto das restantes partículas e uma velocidade que depende apenas da qualidade das soluções. À abordagem integrada da heurística EPSA com as camadas de Clustering e Classi cação foi dado o nome Auto Tuned Elitist Particle Swarm Algorithm (ATEPSA). Esta abordagem baseia-se no uso de histórico de resolução de determinadas instâncias de um problema, com diferentes combinações de parâmetros, para proceder a uma a nação de cariz off-line, servindo-se da experiência anterior de resolução de instâncias semelhantes à que se quer resolver. A abordagem é aplicada ao problema de escalonamento Single Machine Total Weighted Tardiness que é um NP-Difícil bem conhecido. A abordagem ATEPSA apresenta resultados promissores, conseguindo prever boas combinações de parâmetros para uma parte considerável dos casos estudados. A heurística EPSA mostra resultados bastante satisfatórios em tempos de resolução baixos e exibe uma variabilidade baixa numa grande gama de instâncias, o que indica que tende a ter resultados consistentes.
The Metaheuristics' parameter tuning is a complex and hardworking process that, in some cases, is approached with Machine Learning based models which grant improvements to this process so that suitable parameters' combinations are obtained in an automatic, effective and efficient manner. In this work, an approach that integrates a heuristic, Elitist Particle Swarm Algorithm (EPSA), with a Clustering layer and a Classification layer, aiming to predict the most promising parameter combinations for the heuristic, considering the instance of the problem to be solved is proposed. The EPSA heuristic, based on the concept of Particle Swarm Optimization (PSO) for discrete optimization problems, is also presented. This heuristic has two characteristics that, together, make it different from most of the PSO approaches: the existence of a special group of particles, Elite, with a behavior that is different from the rest of the particles and a velocity that only depends on the quality of the solutions. The integration of EPSA, Clustering layer and Classification layer was given the name Auto Tuned Elitist Particle Swarm Algorithm (ATEPSA). This approach is based on the usage of the history of solving certain instances of the problem, with different parameter combinations, to proceed with the tuning process in an o -line mode, taking advantage of the experience in previously solved instances that are similar to the one to be solved. This approach is applied to the Single Machine Total Weighted Tardiness scheduling problem which is a well-known NP-Hard. The ATEPSA approach shows promising results, being able to predict good parameter combinations for a substantial portion of the studied cases. The EPSA heuristics shows good results with low running times and exhibits a low variability in a wide range of instances, which indicates that it tends to have consistent results.
The Metaheuristics' parameter tuning is a complex and hardworking process that, in some cases, is approached with Machine Learning based models which grant improvements to this process so that suitable parameters' combinations are obtained in an automatic, effective and efficient manner. In this work, an approach that integrates a heuristic, Elitist Particle Swarm Algorithm (EPSA), with a Clustering layer and a Classification layer, aiming to predict the most promising parameter combinations for the heuristic, considering the instance of the problem to be solved is proposed. The EPSA heuristic, based on the concept of Particle Swarm Optimization (PSO) for discrete optimization problems, is also presented. This heuristic has two characteristics that, together, make it different from most of the PSO approaches: the existence of a special group of particles, Elite, with a behavior that is different from the rest of the particles and a velocity that only depends on the quality of the solutions. The integration of EPSA, Clustering layer and Classification layer was given the name Auto Tuned Elitist Particle Swarm Algorithm (ATEPSA). This approach is based on the usage of the history of solving certain instances of the problem, with different parameter combinations, to proceed with the tuning process in an o -line mode, taking advantage of the experience in previously solved instances that are similar to the one to be solved. This approach is applied to the Single Machine Total Weighted Tardiness scheduling problem which is a well-known NP-Hard. The ATEPSA approach shows promising results, being able to predict good parameter combinations for a substantial portion of the studied cases. The EPSA heuristics shows good results with low running times and exhibits a low variability in a wide range of instances, which indicates that it tends to have consistent results.
Description
Keywords
Afinação de parâmetros Particle Swarm Optimization Classificação Clustering Escalonamento Parameter tuning Classification Scheduling