Title
Balancing exploration-exploitation in the set covering problem resolution with a self-adaptive intelligent water drops algorithm
Date Issued
01 January 2021
Access level
open access
Resource Type
journal article
Author(s)
Crawford B.
Astorga G.
Lemus-Romani J.
Misra S.
Castillo M.
Cisternas-Caneo F.
Tapia D.
Becerra-Rozas M.
Pontificia Universidad Católica de Valparaíso
Publisher(s)
ASTES Publishers
Abstract
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.
Start page
134
End page
145
Volume
6
Issue
1
Language
English
OCDE Knowledge area
Matemáticas
Ingeniería de sistemas y comunicaciones
Subjects
Scopus EID
2-s2.0-85101049226
Source
Advances in Science, Technology and Engineering Systems
ISSN of the container
24156698
DOI of the container
10.25046/aj060115
Source funding
ANID
National Agency for Research and Development
Sponsor(s)
Acknowledgment Felipe Cisternas-Caneo and Marcelo Becerra-Rozas are supported by Grant DI Investigación Interdisciplinaria del Pregrado/VRIEA/PUCV/039.324/2020. Broderick Crawford is supported by Grant CONI-CYT/FONDECYT/REGULAR/1171243. Ricardo Soto is supported by Grant CONICYT/FONDECYT/REGULAR/1190129. José Lemus-Romani is supported by National Agency for Research and Development (ANID)/Scholarship Program/DOCTORADO NACIONAL/2019-21191692.
Sources of information:
Directorio de Producción Científica
Scopus