Please use this identifier to cite or link to this item: https://repositorio.ufrn.br/jspui/handle/123456789/25896
Title: Órbita Perpétua e outras técnicas de otimização global robusta para os algoritmos Simulated Annealing Acoplado e Nelder-Mead
Authors: Silva, Kayo Gonçalves e
Keywords: Nelder-Mead Simplificado;Simulated Annealing Acoplado;Órbita perpétua;Otimização global;Otimização livre de parâmetros;Abordagem menos é mais;Paralelismo
Issue Date: 28-Jun-2018
Citation: SILVA, Kayo Gonçalves e. Órbita Perpétua e outras técnicas de otimização global robusta para os algoritmos Simulated Annealing Acoplado e Nelder-Mead. 2018. 150f. Tese (Doutorado em Engenharia Elétrica e de Computação) - Centro de Tecnologia, Universidade Federal do Rio Grande do Norte, Natal, 2018.
Abstract: Metaheuristics are algorithms whose strategy is to reduce the computational load to the detriment of the optimal quality of solutions. They are widely used to approximate solutions of computationally intractable optimization problems. Although typically simple to implement, some metaheuristics suffer because of lack of robustness for tuning some initialization parameters, which requires a very expensive tuning process due to its empirical nature. In this paper, we present some solutions to this problem by proposing three new metaheuristics based on free-parameter, less is more (LIMA) and parallel approaches, aiming to make some metaheuristics robust. As results, the algorithms Simplified Nelder-Mead algorithm (SNM), Syncrhonous (SCSA) and Asynchronous Coupled Simulated Annealing (ACSA), and Perpetual Orbit Coupled Simulated Annealing (PO-CSA) were proposed. The SNM is the result of the LIMA approach and the Nelder-Mead (NM) method. While its implementation has far fewer points than the original algorithm, its ability to perform several simple steps makes it able to find better results than the original NM even for non-convex functions. The SCSA and the ACSA are parallel implementations of Simulated Annealing Coupled (CSA) that allow the user to efficiently choose one or another version based on the size of the problem and the number of optimizer cores. The Perpetual Orbit (PO) technique was developed to control the generation temperature of the CSA to make it parameter free. The algorithm PO-CSA takes advantage of the PO technique combined to the CSA’s automatic quasi-optimal scheduling of the acceptance temperature to make optimization of the CSA more robust with respect to the initialization parameters. While the PO-CSA performed better than the reference algorithms for the majority of the objective functions, both in quality of solution and execution time, its control of the generation temperature also proved to be more effective than the original CSA with an exhaustively tuned initialization parameters.
Portuguese Abstract: As metaheurísticas são algoritmos cuja estratégia visa reduzir o custo computacional em detrimento da qualidade ótima das soluções. Elas são amplamente utilizadas para aproximar soluções de problemas de otimização computacionalmente intratáveis. Embora tipicamente de implementação simples, algumas metaheurísticas sofrem por não possuírem robustez quanto à sintonização de alguns parâmetros de inicialização, o que demanda um processo de tentativa de valoração muito oneroso devido à sua natureza empírica. Neste trabalho, apresentamos algumas soluções para esse problema propondo três novas metaheurísticas baseadas nas abordagens livres de parâmetro, menos é mais (LIMA) e paralelas, que visam tornar robusto algumas metaheurísticas. Como resultados, os algoritmos Nelder-Mead Simplificado (SNM), o Simulated Annealing Acoplado Síncrono (SCSA) e Assíncrono (ACSA), e o Simulated Annealing Acoplado com Órbita Perpétua (PO-CSA) foram propostos. O SNM é o resultado da abordagem LIMA ao método Nelder-Mead (NM). Além de sua implementação possuir muito menos pontos que o algoritmo original, sua capacidade de realizar vários passos simples o torna capaz de encontrar melhores resultados do que o NM original mesmo para funções não convexas. O SCSA e ACSA são implementações paralelas do Simulated Annealing Acoplado (CSA) que permitem ao usuário a escolha eficiente de uma ou outra versão baseado no tamanho do problema e no número de otimizadores. A técnica Órbita Perpétua (PO) foi desenvolvida no intuito de controlar a temperatura de geração do CSA para torná-lo livre de parâmetros de inicialização. O PO-CSA aproveita a técnica PO combinada com o escalonamento automático quase-ótimo da temperatura de aceitação do CSA para tornar a otimização do CSA mais robusta com relação aos parâmetros de inicialização. Enquanto que o PO-CSA tem melhor desempenho do que os algoritmos de referência para a maioria das funções objetivo, tanto em qualidade de solução como em tempo de execução, seu controle da temperatura de geração também se mostrou mais efetivo do que o CSA original com parâmetros de inicialização ajustados exaustivamente.
URI: https://repositorio.ufrn.br/jspui/handle/123456789/25896
Appears in Collections:PPGEE - Doutorado em Engenharia Elétrica e de Computação

Files in This Item:
File Description SizeFormat 
Órbitaperpétuaoutras_Silva_2018.pdf4,47 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.