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

Autor(es)

Chaves, Antonio Augusto ^[1] ; Goncalves, Jose Fernando ^{[2, 3]} ; Nogueira Lorena, Luiz Antonio ^[1]

Afiliação do(s) autor(es)

^[1] Univ Fed Sao Paulo, BR-12231280 Sao Jose Dos Campos - Brazil

^[2] Univ Porto, INESC TEC, Porto - Portugal

^[3] Univ Porto, Fac Econ, Porto - Portugal

• Tipo de documento: Artigo Científico
• Fonte: COMPUTERS & INDUSTRIAL ENGINEERING; v. 124, p. 331-346, OCT 2018.
• Citações Web of Science: 3

Resumo

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. (AU)

• Processo FAPESP: 16/07135-7 - Desenvolvimento de um método híbrido flexível com calibração automática de parâmetros
• Beneficiário: Antônio Augusto Chaves
• Linha de fomento: Bolsas no Exterior - Pesquisa