A carregar...
Publicação
INCORPORATING RADIAL BASIS FUNCTIONS IN GLOBAL AND LOCAL DIRECT SEARCH
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 4.18 MB | Adobe PDF |
Orientador(es)
Resumo(s)
GLODS is a global derivative-free optimization algorithm, relying on local directional
direct search, aided by a clever multistart strategy that does not conduct all the lines of
search until the end. In 2015, time of the first release of the corresponding solver, GLODS
was shown to be competitive when compared to state-of-the-art algorithms, such as MCS
or DIRECT.
GLODS resorts to sampling techniques to look for minima on a global scale, not
taking advantage of the information gathered in previous iterations. As such, the main
goal of this work is to replace the pseudo-random sampling approach, used by GLODS
to initialize new lines of search, by the minimization of global models of the objective
function, defined using radial basis functions, and computed using the points previously
evaluated by the algorithm. This should allow a better placement of the starting points for
new local lines of search, and, in turn, significantly increase the numerical performance
of the algorithm.
Naturally, incorporating radial basis functions in GLODS poses new challenges. In
this work, we will address questions such as which radial basis functions to use, which
points should be selected to compute them, how to minimize these functions, and how to
take advantage of their minima in the execution of the algorithm.
The new version of GLODS, incorporating radial basis functions, was calibrated to
its best numerical performance, and then compared against other state-of-the-art solvers,
such as MCS, DIRECT, MATSuMoTo, and ZOOpt. The results obtained are strongly
positive. The new algorithm clearly outperforms its previous version, and is competitive
with the other solvers tested.
Finally, parallel strategies were implemented and tested. Results showed that it is
very beneficial to evaluate multiple points simultaneously, for objective functions whose
evaluation time is as low as 0.1 seconds. The proposed algorithm, called BoostGLODS, is
a cutting-edge, powerful and efficient parallel global derivative-free optimization algo-
rithm.
O algoritmo GLODS é um método de otimização global sem recurso a derivadas, ba- seado em procura direta direcional, aliada a uma estratégia de reinicialização inteligente, que não leva todas as linhas de procura até ao final. Em 2015, ano em que foi disponi- bilizada a primeira versão do correspondente código, o algoritmo GLODS mostrou-se competitivo com outros algoritmos do estado da arte, como sejam o MCS e o DIRECT. O algoritmo GLODS usa técnicas de amostragem pseudo-aleatórias para procurar mínimos numa escala global, não tirando partido da informação adquirida em iterações anteriores. Assim, o objetivo principal deste trabalho é substituir as estratégias de amos- tragem pseudo-aleatória, usadas pelo GLODS para inicializar novas linhas de pesquisa, pela minimização de modelos globais da função objetivo, definidos à custa de funções de base radial, que são construídos usando pontos que o algoritmo já avaliou em itera- ções anteriores. Esta substituição deverá permitir ao GLODS um melhor posicionamento dos pontos para inicialização de procuras locais, o que, por sua vez, deverá levar a um aumento significativo do desempenho numérico do algoritmo. Naturalmente, incorporar funções de base radial no GLODS traz desafios adicionais. Neste trabalho, iremos responder a perguntas como que funções de base radial usar, que pontos selecionar para as construir, como minimizar estas funções e como incorporar essa informação na execução do algoritmo. A nova versão do GLODS, que já contempla o uso de funções de base radial, foi calibrada com vista a ter o melhor desempenho numérico. Posteriormente, foi comparada com outros algoritmos do estado da arte, como sejam o MCS, o DIRECT, o MATSuMoTo, e o ZOOpt. Os resultados obtidos são muito positivos. O novo algoritmo mostra um desempenho claramente superior à sua anterior versão, e é competitivo com os restantes algoritmos testados. Finalmente, foram implementadas e testadas estratégias de paralelismo. Os resulta- dos mostram que é bastante benéfico avaliar vários pontos em simultâneo, para funções objetivo cujo tempo de avaliação é tão baixo como 0.1 segundos. O algoritmo proposto, designado por BoostGLODS, é um algoritmo paralelo de otimização global sem recurso a derivadas, com estratégias de ponta, poderoso e eficiente.
O algoritmo GLODS é um método de otimização global sem recurso a derivadas, ba- seado em procura direta direcional, aliada a uma estratégia de reinicialização inteligente, que não leva todas as linhas de procura até ao final. Em 2015, ano em que foi disponi- bilizada a primeira versão do correspondente código, o algoritmo GLODS mostrou-se competitivo com outros algoritmos do estado da arte, como sejam o MCS e o DIRECT. O algoritmo GLODS usa técnicas de amostragem pseudo-aleatórias para procurar mínimos numa escala global, não tirando partido da informação adquirida em iterações anteriores. Assim, o objetivo principal deste trabalho é substituir as estratégias de amos- tragem pseudo-aleatória, usadas pelo GLODS para inicializar novas linhas de pesquisa, pela minimização de modelos globais da função objetivo, definidos à custa de funções de base radial, que são construídos usando pontos que o algoritmo já avaliou em itera- ções anteriores. Esta substituição deverá permitir ao GLODS um melhor posicionamento dos pontos para inicialização de procuras locais, o que, por sua vez, deverá levar a um aumento significativo do desempenho numérico do algoritmo. Naturalmente, incorporar funções de base radial no GLODS traz desafios adicionais. Neste trabalho, iremos responder a perguntas como que funções de base radial usar, que pontos selecionar para as construir, como minimizar estas funções e como incorporar essa informação na execução do algoritmo. A nova versão do GLODS, que já contempla o uso de funções de base radial, foi calibrada com vista a ter o melhor desempenho numérico. Posteriormente, foi comparada com outros algoritmos do estado da arte, como sejam o MCS, o DIRECT, o MATSuMoTo, e o ZOOpt. Os resultados obtidos são muito positivos. O novo algoritmo mostra um desempenho claramente superior à sua anterior versão, e é competitivo com os restantes algoritmos testados. Finalmente, foram implementadas e testadas estratégias de paralelismo. Os resulta- dos mostram que é bastante benéfico avaliar vários pontos em simultâneo, para funções objetivo cujo tempo de avaliação é tão baixo como 0.1 segundos. O algoritmo proposto, designado por BoostGLODS, é um algoritmo paralelo de otimização global sem recurso a derivadas, com estratégias de ponta, poderoso e eficiente.
Descrição
Palavras-chave
Global optimization Derivative-free optimization Radial basis functions Surrogate models Direct search methods Pattern search methods