Balancing exploration-exploitation in the set covering problem resolution with a self-adaptive intelligent water drops algorithm

Broderick Crawford, Ricardo Soto, Gino Astorga, José Lemus-Romani, Sanjay Misra, Mauricio Castillo, Felipe Cisternas-Caneo, Diego Tapia, Marcelo Becerra-Rozas

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


The objective of the metaheuristics, together with obtaining quality results in reasonable time, is to be able to control the exploration and exploitation balance within the iterative processes of these methodologies. Large combinatorial problems present ample search space, so Metaheuristics must efficiently explore this space; and exploits looking in the vicinity of good solutions previously located. The objective of any metaheuristic process is to achieve a”proper” balance between intensive local exploitation and global exploration. In these processes two extreme situations can occur, on the one hand an imbalance with a bias towards exploration, which produces a distributed search in the search space, but avoiding convergence, so the quality of the solutions will be low, the other case is the bias towards exploitation, which tends to converge prematurely in local optimals, impacting equally on the quality of the solutions. To make a correct balance of exploration and exploitation, it is necessary to be able to control adequately the parameters of the Metaheuristics, in order to infer in the movements taking advantage of the maximum capacity of these. Among the most widely used optimization techniques to solve large problems are metaheuristics, which allow us to obtain quality results in a short period of time. In order to facilitate the use of the tools provided by the metaheuristic optimization techniques, it is necessary to reduce the difficulties in their configuration. For this reason, the automatic control of parameters eliminates the difficult task of obtaining a correct configuration. In this work we implemented an autonomous component to the Intelligent Water Drops algorithm, which allows the control of some parameters dynamically during the execution of the algorithm, achieving a good exploration-exploitation balance of the search process. The correct functioning of the proposal is demonstrated by the Set Covering Problem, which is a classic problem present in the industry, along with this we have made an exhaustive comparison between the standard algorithm and the autonomous version that we propose, using the respective statistical tests. The proposal presents promising results, along with facilitating the implementation of these techniques to industry problems.

Original languageEnglish
Pages (from-to)134-145
Number of pages12
JournalAdvances in Science, Technology and Engineering Systems
Issue number1
StatePublished - 2021


  • Autonomous Search
  • Combinatorial Optimization
  • Intelligent Water Drops
  • Metaheuristics
  • Set Covering Problem


Dive into the research topics of 'Balancing exploration-exploitation in the set covering problem resolution with a self-adaptive intelligent water drops algorithm'. Together they form a unique fingerprint.

Cite this