A Biased Random-key Genetic Algorithm with a Local Search Component for the Optimal Bucket Order Problem

Autor(es)

Nogueira Lorena, Luiz Henrique ; Chaves, Antonio Augusto ; Nogueira Lorena, Luiz Antonio ; IEEE

• Tipo de documento: Artigo Científico
• Fonte: 2021 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC 2021); v. N/A, p. 8-pg., 2021-01-01.

Resumo

Aggregating ranks into a consensus is an important task applied in different fields of science. This paper deals with a specific variation that aggregate ranks into a consensus considering ties between its elements. This approach is more flexible and meaningful for modeling some circumstances where a strict order is considered too restrictive. A ranking considering ties is also known as a bucket order in literature, and the problem that considers the rank aggregation of bucket orders is defined as the Optimal Bucket Order Problem (OBOP). It is an NP-hard problem, hence several heuristics have been proposed in the literature. The current state-of-the-art results for this problem were achieved through an Evolution Strategy (ES) metaheuristic. This paper proposes the application of the adaptive Biased Random-key Genetic Algorithm (A-BRKGA) with Variable Neighborhood Descent (VND) as a local search to solve it. The A-BRKGA is a metaheuristic with on-line parameter control, in which the strategy for parameter tuning is based on deterministic rules and self-adaptive schemes. The proposed approach was compared with ES in 152 instances, improving the fitness of the best solutions in 35.52% of the instances, providing better average solutions for 70.39%, and equal results for the remaining instances. (AU)

• Processo FAPESP: 18/15417-8 - Desenvolvimento de uma meta-heurística híbrida com fluxo de controle e parâmetros adaptativos
• Beneficiário: Antônio Augusto Chaves
• Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores - Fase 2