Portal de Periódicos da CAPES

Adaptive biased random-key genetic algorithm with local search for the capacitated centered clustering problem

2018; Elsevier BV; Volume: 124; Linguagem: Inglês

10.1016/j.cie.2018.07.031

1879-0550

Antônio Augusto Chaves, José Fernando Gonçalves, Luiz Antônio Nogueira Lorena,

Metaheuristic Optimization Algorithms Research

This paper proposes an adaptive Biased Random-key Genetic Algorithm (A-BRKGA), a new method with on-line parameter control for combinatorial optimization problems. A-BRKGA has only one problem-dependent component, the decoder and all other parts can be reused. To control diversification and intensification, a novel adaptive strategy for parameter tuning is introduced. This strategy is based on deterministic rules and self-adaptive schemes. For exploitation of specific regions of the solution space we propose a local search in promising communities. The proposed method is evaluated on the Capacitated Centered Clustering Problem (CCCP), which is an NP-hard problem where a set of n points, each having a given demand, is partitioned into m clusters each with a given capacity. The objective is to minimize the sum of the Euclidean distances between the points and their geometric cluster centroids. Computational results show that the A-BRKGA with local search is competitive with other methods of literature.