Rafael de Paula Garcia

Título

ALGORITMOS EVOLUTIVOS APLICADOS A PROBLEMAS ENVOLVENDO FUNÇÕES COMPUTACIONALMENTE CUSTOSAS EM DOMÍNIOS RESTRITOS

Orientador(es)


Beatriz de Souza Leite Pires de Lima
Afonso Celso de Castro Lemonge

Resumo

A aplicação de algoritmos evolutivos na otimização de problemas reais e complexos de engenharia tem se mostrado bastante eficiente. Porém, como a maioria destes problemas são definidos por funções objetivo e restrições caras computacionalmente, novas técnicas de modelagem e tratamento de restrições têm sido propostas. Neste cenário, esta tese propõe um tratamento de restrições denominado Multiple Constraint Ranking (MCR) e um algoritmo de aproximação de funções baseado em similaridade. Eles auxiliam algoritmos evolutivos na busca de soluções ótimas em
problemas de otimização com restrições e função objetivo dispendiosa computacionalmente. O MCR calcula a aptidão das soluções segundo a soma de suas posições em várias filas, com base nos valores da função objetivo, da violação em cada restrição e do número de restrições violadas. A aproximação baseada em similaridade estima o valor da função objetivo de uma solução por uma média ponderada dos valores originais da função objetivo de soluções “vizinhas”pelas distâncias. Tais soluções são selecionadas a partir de um banco de dados, cuja atualização é base- ada na contribuição das soluções no processo de aproximação. Três algoritmos são propostos: i) MCR acoplado a um algoritmo genético; ii) evolução diferencial utilizando aproximação da função objetivo por similaridade; e, iii) evolução diferencial assistida pelo MCR e a aproximação de funções. Eles foram submetidos a problemas complexos sugeridos pelas competições do IEEE-CEC e em problemas clássicos de engenharia estrutural. Seus resultados foram comparados com relevantes algoritmos da literatura, onde comprovou-se a robustez de todos eles.

Abstract

The use of evolutionary algorithms in the optimization of real and complex engineering problems has proved to be quite efficient. However, since most of these problems are defined by expensive objective function and constraints, new modeling and constraint handling techniques have been proposed. In this scenario, this thesis proposes a constraint handling technique called Multiple Constraint Ranking (MCR) and a similarity-based surrogate algorithm. They assist evolutionary algorithms in the search for optimal solutions in optimization problems in which both objective function and constraints are costly. The MCR calculates the fitness of the solutions according to the sum of their positions in several queues, based on the values of the objective function, the violation in each constraint and the number of constraints violated. The similarity-based approach estimates the value of the objective function of a solution by a weighted average of the original objective func- tion values of “neighboring” solutions by their distances. Such solutions are selected from a database, whose updating is based on the contribution of the solutions in the approximation process. Three algorithms are proposed: i) MCR coupled with a genetic algorithm; ii) differential evolution using similarity-based approximation; and, iii) differential evolution assisted by the MCR and the approximation. Theywere applied to complex problems suggested by the IEEE-CEC competitions and classical structural engineering problems. Their results were compared with relevant algorithms in the literature, where were proved the robustness of all of them.

Imprimir