A carregar...
Publicação
Contributions in Global Derivative-free Optimization to the development of an integrated toolbox of solvers
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 4.76 MB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
This dissertation is framed in the research project "BoostDFO: Improving the performance
and moving to newer directions in Derivative-Free Optimization", funded by Fundação
para a Ciência e Tecnologia, whose objective is to develop efficient and robust algorithms
for Global and Multiobjective Derivative-Free Optimization. The demand for algorithms
belonging to this class appears in different application areas, such as robotics, electrical
engineering, aeronautics or oceanography, where, for several reasons, it is not possible to
use derivatives.
Global and Local Optimization using Direct Search (GLODS) is an algorithm belonging
to this class of optimization methods, which aims at identifying the global minimum of
a given problem by computing all the local minima. However, identifying points as
global minimizers is always a hard task, being of increased complexity when the function
to optimize is computational expensive and time-consuming. Typically, the higher the
dimension and complexity of the problem, the more computational effort and time will
be required to run the algorithm.
The current version of GLODS is developed sequentially, and it is not fully optimized.
The present work will analyze in detail the execution and behavior of GLODS, and will
propose and evaluate the numerical performance of different parallelization strategies,
implemented using the MATLAB Parallel Computing Toolbox (PCT). The parallelization
structure will have a primary purpose of allowing to distribute objective function evaluations
among different processors of the hardware platforms, both host locally or in public
clouds.
Three strategies for GLODS parallelization were designed and implemented centered
on the poll phase of the algorithm. The first two - parallelization of the poll step with
one and two poll centers - were successful and gave good results in terms of solution
quality and execution time reduction. The third level of parallelization introduced
the possibility of dynamically selecting the number of poll centers, according with the
number of processors available, a functionality that can be particularly useful in future
work in the area.
Esta dissertação enquadra-se no projeto de investigação "BoostDFO: Aumentando o desempenho e abordando novas dimensões em optimização sem recurso a derivadas", financiado pela Fundação para a Ciência e a Tecnologia, cujo objetivo é desenvolver algoritmos eficientes e robustos para Otimização Global e/ou Multiobjectivo sem recurso a derivadas. A procura e utilização de algoritmos pertencentes a esta classe ocorre em diferentes áreas, como a robótica, a engenharia eletrotécnica, a aeronáutica ou a oceanografia, onde, por diversas razões, não é possível a utilização de derivadas. Global and Local Optimization using Direct Search (GLODS) é um algoritmo pertencente a esta classe de métodos de otimização, que visa identificar o mínimo global de um certo problema através do cálculo dos diferentes mínimos locais. No entanto, identificar pontos como minimizantes globais é sempre uma tarefa difícil, sendo de maior complexidade quando a função a otimizar apresenta elevados custos computacionais e tempo de execução. Normalmente, quanto maior a dimensão e a complexidade de um problema, mais recursos e tempo computacional serão necessários para a execução do algoritmo. A versão atual do algoritmo GLODS encontra-se implementada sequencialmente e não está totalmente otimizada. O presente trabalho analisará em detalhe a execução e o comportamento deste algortimo, propondo e avaliando o desempenho númerico de diferentes estruturas de paralelização para o mesmo, implementadas recorrendo às ferramentas de paralelismo do MATLAB. A estrutura de paralelização terá como objetivo principal a distribuição das avaliações da função objetivo entre diferentes processadores, num ambiente local ou na cloud pública. Delinearam-se e implementaram-se três estratégias para a paralelização do GLODS, centradas na fase de sondagem do algoritmo. As primeiras duas - paralelização do passo de sondagem com um e com dois centros de sondagem - foram bem sucedidas, permitindo bons resultados em termos de qualidade da solução e também uma redução no tempo de execução do algoritmo. O terceiro nível de paralelização introduziu a possibilidade de selecionar o número de centros de sondagem de foma dinâmica, considerando o número de processadores disponíveis, uma funcionalidade que será particularmente útil no trabalho futuro a desenvolver na área.
Esta dissertação enquadra-se no projeto de investigação "BoostDFO: Aumentando o desempenho e abordando novas dimensões em optimização sem recurso a derivadas", financiado pela Fundação para a Ciência e a Tecnologia, cujo objetivo é desenvolver algoritmos eficientes e robustos para Otimização Global e/ou Multiobjectivo sem recurso a derivadas. A procura e utilização de algoritmos pertencentes a esta classe ocorre em diferentes áreas, como a robótica, a engenharia eletrotécnica, a aeronáutica ou a oceanografia, onde, por diversas razões, não é possível a utilização de derivadas. Global and Local Optimization using Direct Search (GLODS) é um algoritmo pertencente a esta classe de métodos de otimização, que visa identificar o mínimo global de um certo problema através do cálculo dos diferentes mínimos locais. No entanto, identificar pontos como minimizantes globais é sempre uma tarefa difícil, sendo de maior complexidade quando a função a otimizar apresenta elevados custos computacionais e tempo de execução. Normalmente, quanto maior a dimensão e a complexidade de um problema, mais recursos e tempo computacional serão necessários para a execução do algoritmo. A versão atual do algoritmo GLODS encontra-se implementada sequencialmente e não está totalmente otimizada. O presente trabalho analisará em detalhe a execução e o comportamento deste algortimo, propondo e avaliando o desempenho númerico de diferentes estruturas de paralelização para o mesmo, implementadas recorrendo às ferramentas de paralelismo do MATLAB. A estrutura de paralelização terá como objetivo principal a distribuição das avaliações da função objetivo entre diferentes processadores, num ambiente local ou na cloud pública. Delinearam-se e implementaram-se três estratégias para a paralelização do GLODS, centradas na fase de sondagem do algoritmo. As primeiras duas - paralelização do passo de sondagem com um e com dois centros de sondagem - foram bem sucedidas, permitindo bons resultados em termos de qualidade da solução e também uma redução no tempo de execução do algoritmo. O terceiro nível de paralelização introduziu a possibilidade de selecionar o número de centros de sondagem de foma dinâmica, considerando o número de processadores disponíveis, uma funcionalidade que será particularmente útil no trabalho futuro a desenvolver na área.
Descrição
Palavras-chave
Derivative-free Optimization Directional Direct Search GLODS algorithm Parallel computing Cloud computing MATLAB