Repository logo
 
No Thumbnail Available
Publication

Adaptação automática de algoritmos de otimização metaheurística

Use this identifier to reference this record.
Name:Description:Size:Format: 
DM_JoaoCarvalho_2022_MEIA.pdf4.41 MBAdobe PDF Download

Abstract(s)

A maioria dos problemas do mundo real tem uma multiplicidade de possíveis soluções. Além disso, usualmente, são encontradas limitações de recursos e tempo na resolução de problemas reais complexos e, por isso, frequentemente, não é possível aplicar um método determinístico na resolução desses problemas. Por este motivo, as meta-heurísticas têm ganho uma relevância significativa sobre os métodos determinísticos na resolução de problemas de otimização com múltiplas combinações. Ainda que as abordagens meta-heurísticas sejam agnósticas ao problema, os resultados da otimização são fortemente influenciados pelos parâmetros que estas meta-heurísticos necessitam para a sua configuração. Por sua vez, as melhores parametrizações são fortemente influenciadas pela meta-heurística e pela função objetivo. Por este motivo, a cada novo desenvolvimento é necessária uma otimização dos parâmetros das metas heurísticas praticamente partindo do zero. Assim, e, atendendo ao aumento da complexidade das meta-heurísticas e dos problemas aos quais estassão normalmente aplicadas, tem-se vindo a observar um crescente interesse no problema da configuração ótima destes algoritmos. Neste projeto é apresentada uma nova abordagem de otimização automática dos parâmetros de algoritmos meta-heurísticos. Esta abordagem não consiste numa pré-seleção estática de um único conjunto de parâmetros que será utilizado ao longo da pesquisa, como é a abordagem comum, mas sim na criação de um processo dinâmico, em que a parametrização é alterada ao longo da otimização. Esta solução consiste na divisão do processo de otimização em três etapas, forçando, numa primeira etapa um nível alto de exploração do espaço de procura, seguida de uma exploração intermédia e, na última etapa, privilegiando a pesquisa local focada nos pontos de maior potencial. De forma a permitir uma solução eficiente e eficaz, foram desenvolvidos dois módulos um Módulo de Treino e um Módulo de Otimização. No Módulo de Treino, o processo de fine-tuning é automatizado e, consequentemente, o processo de integração de uma nova meta-heurística ou uma nova função objetivo é facilitado. No Módulo de Otimização é usado um sistema multiagente para a otimização de uma dada função seguindo a abordagem de pesquisa proposta. Com base nos resultados obtidos através da aplicação de otimização por enxame de partículas e algoritmos genéticos a várias funções benchmark e a um problema real na área dos sistemas de energia, o Módulo de Treino permitiu automatizar o processo de fine-tuning e, consequentemente, facilitar o processo de introdução no sistema de uma nova meta-heurística ou de uma nova função relativa a um novo problema a resolver. Utilizando a abordagem de otimização proposta através do Módulo de Otimização, obtém-se uma maior generalização e os resultados são melhorados sem comprometer o tempo máximo para a otimização.
Most real-word problems have a large solution space. Due to resource and time constraints, it is often not possible to apply a deterministic method to solve such problems. For this reason, metaheuristic optimization algorithm has earned increased popularity over the deterministic methods in solving complex combination optimization problems. However, despite being problem-agnostic techniques, metaheuristic’s optimization results are highly impacted by the defined parameters. The best parameterizations are highly impacted by the metaheuristic version and by the addressed objective function. For this reason, with each new development it is necessary to optimize the metaheuristic parameters practically from scratch. Thus, and given the increasing complexity of metaheuristics and the problems to which they are normally applied, there has been a growing interest in the problem of optimal configuration of these algorithms. In this work, a new approach for automatic optimization of metaheuristic algorithms parameters is presented. This approach does not consist in a static pre-selection of a single set of parameters that will be used throughout the search process, as is the common approach, but in the creation of a dynamic process, in which the parameterization is changed during the optimization. This solution consists of dividing the optimization process into three stages, forcing, in a first stage, a high level of exploration of the search space, followed by an intermediate exploration and, in the last stage, fostering local search focused on the points of greatest potential. In order to allow an efficient and effective solution, two modules are developed, a Training Module and an Optimization Module. In the Training Module, the finetuning process is automated and, consequently, the process of integrating a new metaheuristic or a new objective function is facilitated. In the Optimization Module, a multi-agent system is used to optimize a given function following the proposed research approach. Based on the results obtained using particle swarm optimization and genetic algorithms to solve several benchmark functions and a real problem in the area of power and energy systems, the Training Module made it possible to automate the fine-tuning process and, consequently, facilitate the process of introducing in the system a new metaheuristic or a new function related to a new problem to be solved. Using the proposed optimization approach through the Optimization Module, a greater generalization is obtained, and the results are improved without compromising the maximum time for the optimization.

Description

Keywords

Algoritmos genéticos Configuração automática de algoritmos Otimização meta-heurística Otimização por enxame de partículas Parametrização dinâmica Sistemas multiagente Automatic algorithm configuration Dynamic parameterization Genetic algorithms Metaheuristic optimization Multi-agent systems Particle swarm optimization

Citation

Research Projects

Organizational Units

Journal Issue