Um método estocástico para resolver problemas MINLP não suaves

Abstract

Muitos dos problemas de otimização que surgem com frequência numa vasta gama de aplicações reais, pertencem à área da Otimização Não Linear. Em geral, estes problemas são complexos, pois podem, eventualmente, incluir variáveis contínuas e inteiras, funções não lineares, não contínuas e não diferenciáveis. Nesta área existem duas classes de pro- blemas considerados de difícil resolução aos quais a comunidade científica se tem dedicado: os problemas de programação não linear (NLP) e os problemas de programação não linear inteira-mista (MINLP), não convexos e não suaves. Dada a sua complexidade, em muitos destes problemas não é possível calcular, nem sequer aproximar o cálculo de derivadas, sendo por isso necessário desenvolver outro tipo de abordagem diferente da convencional, para os resolver. Uma das abordagens mais promissoras e utilizadas para resolver este tipo de problemas é o uso de métodos estocásticos. Na literatura existem vários méto- dos estocásticos, baseados em populações, que têm sido usados com sucesso para resolver estes problemas. Recentemente, surgiu o Firefly Algorithm (FA) para resolver problemas de otimização contínuos e com restrições de limites simples, que se tem revelado ser bem sucedido na resolução de problemas práticos e complexos. Assim, o objetivo central desta tese prende-se com o desenvolvimento de extensões do FA capazes de resolver problemas de NLP e de MINLP, com restrições, não convexos e não suaves. Numa primeira fase, são desenvolvidos algoritmos para a resolução de problemas de NLP com restrições. São propostas duas extensões do FA baseadas em técnicas distintas, para o tratamento das restrições. Uma baseada em esquemas de ordenação dos pontos da população e outra baseada numa nova função de penalidade auto-adaptativa. Esta função de penalidade auto-adaptativa pode ser implementada em diversos métodos estocásticos de otimização global baseados em populações. O estudo da convergência do algoritmo com a função de penalidade auto-adaptativa, no contexto do FA, é demonstrada em termos probabilísticos. Numa segunda fase, foram desenvolvidos algoritmos para a resolução de problemas de MINLP. Primeiro desenvolveu-se a extensão do FA para resolver problemas de MINLP com restrições de limites simples e variáveis binárias, baseada em heurísticas. A seguir, foi desenvolvida uma extensão do FA que implementa um algoritmo de penalidade exata, para resolver os problemas de MINLP com restrições de limites simples e variáveis contínuas e inteiras. Neste contexto, foram propostas duas funções de penalidade exata, e o estudo da convergência do algoritmo de penalidade, no contexto do FA, é demonstrada em termos probabilísticos. Por fim, foi desenvolvida uma extensão do FA para resolver problemas de MINLP com restrições genéricas, que combina uma heurística e um esquema de ordenação dos pontos da população, para o tratamento das restrições do problema. As experiências numéricas realizadas mostraram que as extensões do FA propostas são eficazes, tendo-se obtido soluções de qualidade elevada, quando comparados com outros métodos disponíveis na literatura.

Many optimization problems that frequently arise in a wide range of real applications belong to the area of Nonlinear Optimization. In general, these problems are complex, and may eventually involve continuous and integer variables, and nonlinear, non continuous and non differentiable functions. In this area there are two classes of optimization problems considered hard to solve, that have been studied by the scientific community: NonLinear Programming (NLP) problems and Mixed-Integer NonLinear Programming (MINLP) pro- blems, nonconvex and nonsmooth problems. Since in many of these problems it is not possible to calculate or even approximate the derivatives, it is necessary to develop a new kind of approach different from the conventional one. The stochastic methods are the most commonly used to solve these type of problems. In the literature there are several population-based stochastic methods that have been successfully used to solve these pro- blems. Recently, the Firefly Algorithm (FA) has emerged to solve continuous optimization problems with simple bounds that have proven to be successful in solving practical and complex problems. Thus, the main goal of this thesis is to extend the FA to solve constrained nonconvex and nonsmooth NLP and MINLP problems. In the first phase, algorithms to solve constrained NLP problems are developed. Two extensions of FA using different techniques for handling the constraints are proposed. One is based on ordering schemes of population points and another based on a new self-adaptive penalty function. The self-adaptive penalty function can be implemented in several population-based stochastic methods. The convergence study of the algorithm based on the self-adaptive penalty function, in the FA context, in probabilistic terms is demonstrated. In a second phase, algorithms to solve MINLP problems were developed. First, an FA extension was developed to solve MINLP problems with simple bounds and binary variables based on heuristics. Next, an FA extension that implements an exact penalty algorithm to solve the MINLP problems with simple bounds and mixed variables was developed. In this context, two exact penalty functions were proposed and the convergence study of the penalty algorithm, in the context of the FA, in probabilistic terms is proved. Finally, an FA extension to solve constrained MINLP problems, which combines a heuristic and a scheme of ordering the points of the population, for handling the constraints was developed. Numerical experiments have shown that the proposed FA extensions are effective and produced high quality solutions when compared to other methods available in the litera- ture.