An Argentine ant system algorithm for partial set covering problem
| DOI | https://doi.org/10.1108/DTA-08-2021-0205 |
| Published date | 13 April 2022 |
| Date | 13 April 2022 |
| Pages | 762-781 |
| Subject Matter | Library & information science,Librarianship/library management,Library technology,Information behaviour & retrieval,Metadata,Information & knowledge management,Information & communications technology,Internet |
| Author | Xiaofan Liu,Yupeng Zhou,Minghao Yin,Shuai Lv |
An Argentine ant system algorithm
for partial set covering problem
Xiaofan Liu
College of Information Science and Technology, Northeast Normal University,
Changchun, China
Yupeng Zhou and Minghao Yin
College of Information Science and Technology, Northeast Normal University,
Changchun, China and
Key Laboratory of Applied Statistics of MOE, Northeast Normal University,
Changchun, China, and
Shuai Lv
Urban Construction Archives, Changchun, China
Abstract
Purpose –The paper aims to provide an efficient meta-heuristic algorithm to solve the partial set covering
problem (PSCP). With rich application scenarios, the PSCP is a fascinating and well-known non-deterministic
polynomial (NP)-hard problem whose goal is to cover at least k elements with as few subsets as possible.
Design/methodology/approach –In this work, the authors present a novel variant of the ant colony
optimization (ACO) algorithm, called Argentine ant system (AAS), to deal with the PSCP. The developedAAS
is an integrated system of different populations that use the same pheromone to communicate. Moreover, an
effective local search framework with the relaxed configuration checking (RCC) and the volatilization-fixed
weight mechanism is proposed to improve the exploitation of the algorithm.
Findings –A detailed experimental evaluation of 75 instances reveals that the proposed algorithm
outperforms the competitors in terms of the quality of the optimal solutions. Also, the performance of AAS
gradually improves with the growing instance size, which shows the potential in handling complex practical
scenarios. Finally, the designed components of AAS are experimentally proved to be beneficial to the whole
framework. Finally, the key components in AAS have been demonstrated.
Originality/value –At present, there is no heuristic method to solve this problem. The authors present the
first implementation of heuristic algorithm for solving PSCP and provide competitive solutions.
Keywords Partial set covering problem, Ant colony optimization, Relaxed configuration checking,
Volatilization-fixed weight, Local search, Meta-heuristic
Paper type Research paper
1. Introduction
The minimum set covering problem (MSCP) is a well-known and widely studied NP-hard
combinatorialoptimizationproblem. Given a 0–1 sparse matrixAof m3n,wherea
ij
51ifand
only if row (element)iis covered by column (set)j(i≤m,j≤n), the goal of MSCP is to determine
a set cover of minimum cardinality so that all rows are fully covered (Hartmanis, 1982). This
problem is widespread to be transformed into many real-world applications, such as the
converter placement problem (Lu et al.,2001), the lifetime maximizationof the wireless sensor
network(Zhang et al.,2015), the optimalcamera placement problem(Kritter et al., 2019), the fire-
stationproblem (Snyder, 2011), the locationof telecommunicationantennas (Murray, 2016),etc.
With the development of the era of big data, the amount of data are explosively growing,
which makes it more challenging to find the optimal solution of the problem under the limited
computing resources and time. In this case, the partial set covering problem (PSCP), a
DTA
56,5
762
Funding: This work is supported by the Fundamental Research Funds for the Central Universities
2412019ZD013 and 2412019FZ051, NSFC under Grant No. 61976050, 61972384.
The current issue and full text archive of this journal is available on Emerald Insight at:
https://www.emerald.com/insight/2514-9288.htm
Received 5 August 2021
Revised 24 February 2022
Accepted 20 March 2022
Data Technologies and
Applications
Vol. 56 No. 5, 2022
pp. 762-781
© Emerald Publishing Limited
2514-9288
DOI 10.1108/DTA-08-2021-0205
generalized version of the MSCP, emerged. Given the parameter k, the PSCP aims to find the
smallest subset Sof the column set so that the number of rows covered by Sis no smaller than
k. Note that MSCP is a special case of PSCP when k5m, where mis the total number of rows.
In addition to its importance as a classical combinatorial optimization problem, the PSCP is
more flexible for its ability to formulate a number of applications.
For example, some service stations, each of which can serve a fixed number of residents
within a certain area, are planned to be established in the city to provide handy service for the
public. Given a great deal of candidate sites, the decision-maker should select appropriate
sites as the service stations so that all the residents can be served. Each resident can be
considered an element of the set cover problem (SCP), and each candidate site can be seen as a
set that covers certain elements. This scene can be clearly formulated as the minimum SCP if
we seek for minimum service stations from economic concerns. However, what happens often
is that the budget is restricted, especially for very large cities. In this case, the decision-maker
should guarantee that most residents should be served. If we quantify the number of
residents as the parameter k, it is transformed into the partial set covering problem.
Since PSCP is an NP-hard problem (Lewis, 1983), there exists no algorithm that can solve it
in polynomial time unless NP 5P. Thus, some approximation algorithms are introduced by
researchers. Unlike the famous MSCP for which various solution methods are available,
literature reviews on PSCP from an algorithmic aspect is still in scarcity. Inspired by
geometric set system, Inamdar and Varadarajan (2018) obtained a simple and elegant method
to reduce PSCP to SCP through natural linear programming (LP) relaxation. In recent work,
Chekuri et al. (2019) improved the approximation of PSCP to (1 1/e)(βþ1) with the same
setting as in (Inamdar and Varadarajan, 2018). However, the quality of the results obtained by
approximation algorithms still cannot meet the requirements of many practical applications.
In the meanwhile, with the data scale grows, exact algorithms need more computing efforts
that are unbearable in a real scenario. In this way, the heuristic algorithm becomes a good
choice. Although a large number of heuristic methods have been proposed to solve various
optimization problems (Zhou et al., 2018,2020;Arasteh et al., 2020;Shomali and Arasteh,
2020), as far as we know, no heuristic algorithms exist to solve the PSCP. Therefore, the
purpose of this work is to enrich the repertory of solution methods for PSCP by presenting a
novel Argentine ant system (AAS) algorithm.
The concept of the ant system was proposed in (Dorigo et al., 1996), introducing an
optimization technique inspired by the foraging behavior of natural ant colonies when
finding the shortest path. In such a framework, solutions are generated based on the greedy
information calculated from the instance and the current values of the probability model
(pheromone value in ant colony optimization [ACO] terminology) in each ant colony iteration.
Then, the pheromone value is updated according to the better or optimal solution generated in
the current iteration or early iteration. Soon afterward, St€
utzle and Hoos tried to overcome the
precocious shortcomings of the original ACO through the introduction of an upper and lower
threshold mechanism and called it the MAX-MIN ant system (MMAS) (St€
utzle and Hoos,
2000). Since then, a variety of ACO or MMAS variants have been studied, such as the novel
game-based ACO (Kang et al., 2020), the beam ACO (Blum, 2008), the k-elitist MMAS
(Abdelbar and Mokhtar, 2003), the hybrid MMAS (Al-Shihabi, 2016), etc. Due to the
prosperity of the ACO algorithms, many applications have been solved accordingly, e.g. the
multi-compartment vehicle routing problem (Reed et al., 2014), the resource-constrained
project scheduling problem (Wang et al., 2010), the environmental/economic dispatch
problem (Chen et al., 2009), the urban traffic path planning (Zhou, 2019), the color image
segmentation problem (Tan and Isa, 2011) and so on. For more information, one can refer to
the surveys (Dorigo and St€
utzle, 2019;Blum, 2005;Mohan and Baskaran, 2012).
In this paper, we propose a novel meta-heuristic method based on the ACO algorithm,
called the AAS, which is inspired by the living habits of the Argentine ant colony (Vogel et al.,
The Argentine
ant system
algorithm
763
To continue reading
Request your trial