Allan Fonseca da Silva
Título
Otimização de Problemas com Restrição Utilizando-se o Algoritmo de Enxame de Partículas Assistido por Metamodelos
Orientador(es)
Beatriz de Souza Leite Pires de Lima
Afonso Celso de Castro Lemonge
Resumo
O uso dos algoritmos evolutivos tem aumentado ao longo dos anos como alternativa viável para solução de problemas de otimização e, um deles, em especial, tem se mostrado efetivo quando usado para a otimização de problemas complexos: o algoritmo de exame de partículas. Conhecido como PSO, este algoritmo tem se mostrado competitivo se comparado a outros algoritmos populacionais inspirados na natureza. Ainda assim, com a crescente complexidade dos problemas avaliados através de métodos computacionais o uso dos algoritmos evolutivos pode se tornar altamente custoso devido ao grande número de soluções candidatas no processo evolutivo que devem ser avaliadas com a função que representa o problema avaliado. Neste sentido, o uso de metamodelos, também conhecidos como modelos de substituição, em conjunto com esses algoritmos, se apresenta como alternativa interessante para a redução do número de avaliações das soluções candidatas substituindo as avaliações através da função que representa o problema pela utilização do metamodelo reduzindo também o tempo computacional durante o processo evolutivo. Esta tese apresenta o PSO associado ao método de vizinhos mais próximos (KNN), utilizado como metamodelo, propondo uma nova forma de atualização do conjunto de treinamento do metamodelo como uma alternativa viável para minimizar o erro na avaliação de soluções candidatas através do metamodelo em relação a sua avaliação através da função que representa o problema.
Abstract
The use of evolutionary algorithms has been increasing over the years as a viable alternative to solve optimization problems, and one technique in particular has demonstrated effectiveness when used to solve complex optimization problems: the Particle Swarm. Known as PSO, this technique has been shown to be competitive when compared to other nature-inspired population algorithms. Still, with the increasing complexity of problems evaluated through computational methods the use of evolutionary algorithms can become very expensive due to the large number of candidate solutions in the evolutionary process to be evaluated with the function that represents problem assessed. In this sense, the use of metamodels, also known as surrogate models, in conjunction with these algorithms, presents as an interesting alternative to reduce the number of candidate solutions evaluations by replacing the evaluations using the function representing the problem by using the surrogate motel also reducing the computational time during the evolutionary process. This work presents PSO associated with the k-Nearest Neighbors method (KNN), used as a surrogate model, proposing a new way to update the surrogate model training set as a viable alternative to minimize the evaluation of candidate solutions error through the surrogate model relative their evaluation by the function that represents the problem.
