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

Author(s)

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

Affiliation

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

• Document type: Journal article
• Source: COMPUTERS & INDUSTRIAL ENGINEERING; v. 124, p. 331-346, OCT 2018.
• Web of Science Citations: 3

Abstract

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)

• FAPESP's process: 16/07135-7 - Development of a flexible hybrid method with automatic tuning of parameters
• Grantee: Antônio Augusto Chaves
• Support Opportunities: Scholarships abroad - Research