[pt] ESTRATÉGIAS PARA O CONTROLE DE PARÂMETROS NO ALGORITMO GENÉTICO COM CHAVES ALEATÓRIAS ENVIESADAS

[en] STRATEGIES FOR PARAMETER CONTROL IN THE BIASED RANDOM-KEY GENETIC ALGORITHM

[pt] LUISA ZAMBELLI ARTMANN R VILELA

[pt] OTIMIZACAO COMBINATORIA

[pt] PARAMETRIZACAO ONLINE

[pt] ALGORITMO GENETICO COM CHAVES ALEATORIAS VICIADAS

[en] COMBINATORIAL OPTIMIZATION

[en] PARAMETER CONTROL

[en] BIASED RANDOM KEY GENETIC ALGORITHM

[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.

LUCIANA DE SOUZA PESSOA

CARLOS EDUARDO DE ANDRADE

LUCIANA DE SOUZA PESSOA

CARLOS EDUARDO DE ANDRADE

MAURICIO GUILHERME DE CARVALHO RESENDE

FABIO LUIZ USBERTI

2022-11-08

2022-10-03

[pt] TEXTO

application/pdf

INGLÊS

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=61145@1

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=61145@2

https://doi.org/10.17771/PUCRio.acad.61145