[pt] O Algoritmo Genético de Chaves Aleatórias Enviesadas (BRKGA) é
uma metaheurística populacional utilizada na obtenção de soluções ótimas ou
quase ótimas para problemas de otimização combinatória. A parametrização
do algoritmo é crucial para garantir seu bom desempenho. Os valores dos
parâmetros têm uma grande influência em determinar se uma boa solução
será encontrada pelo algoritmo e se o processo de busca será eficiente. Uma
maneira de resolver esse problema de configuração de parâmetros é por
meio da abordagem de parametrização online (ou controle de parâmetros).
A parametrização online permite que o algoritmo adapte os valores dos
parâmetros de acordo com os diferentes estágios do processo de busca e
acumule informações sobre o espaço de soluções nesse processo para usar as
informações obtidas em estágios posteriores. Ele também libera o usuário da
tarefa de definir as configurações dos parâmetros, resolvendo implicitamente
o problema de configuração. Neste trabalho, avaliamos duas estratégias para
implementar o controle de parâmetros no BRKGA. Nossa primeira abordagem
foi adotar valores de parâmetros aleatórios para cada geração do BRKGA.
A segunda abordagem foi incorporar os princípios adotados pelo irace, um
método de parametrização do estado da arte, ao BRKGA. Ambas as estratégias
foram avaliadas em três problemas clássicos de otimização (Problema de
Permutação Flowshop, Problema de Cobertura de Conjuntos e Problema do
Caixeiro Viajante) e levaram a resultados competitivos quando comparados ao
algoritmo tunado. / [en] The Biased Random-Key Genetic Algorithm (BRKGA) is a populationbased metaheuristic applied to obtain optimal or near-optimal solutions to
combinatorial problems. To ensure the good performance of this algorithm
(and other metaheuristics in general), defining parameter settings is a crucial
step. Parameter values have a great influence on determining whether a good
solution will be found by the algorithm and whether the search process will
be efficient. One way of tackling the parameter setting problem is through
the parameter control (or online tuning) approach. Parameter control allows
the algorithm to adapt parameter values according to different stages of the
search process and to accumulate information on the fitness landscape during
the search to use this information in later stages. It also releases the user
from the task of defining parameter settings, implicitly solving the tuning
problem. In this work, we evaluate two strategies to implement parameter
control in BRKGA. Our first approach was adopting random parameter values
for each of BRKGA s generations. The second approach was to introduce
the principles adopted by Iterated Race, a state-of-the-art tuning method,
to BRKGA. Both strategies were evaluated in three classical optimization
problems (Flowshop Permutation Problem, Set Covering Problem, and the
Traveling Salesman Problem) and led to competitive results when compared
to the tuned algorithm.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:61145 |
| Date | 08 November 2022 |
| Creators | LUISA ZAMBELLI ARTMANN R VILELA |
| Contributors | LUCIANA DE SOUZA PESSOA, LUCIANA DE SOUZA PESSOA |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | English |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0024 seconds