An Artificial Fish Swarm Optimization Algorithm to Solve Set Covering Problem
The Set Covering Problem (SCP) consists in finding a set of solutions that allow to cover a set of necessities with the minor possible cost. There are many applications of this problem such as rolling production lines or installation of certain services l
- PDF / 213,841 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 33 Downloads / 206 Views
ificia Universidad Cat´ olica de Valpara´ıso, Valpara´ıso, Chile {broderick.crawford,ricardo.soto}@ucv.cl, {sebastian.mansilla.v,alvaro.gomez.r, adrian.jaramillo.s,juan.salas.f}@mail.pucv.cl 2 Universidad San Sebasti´ an, Santiago, Chile [email protected] 3 Universidad Aut´ onoma de Chile, Temuco, Chile 4 Universidad Cientifica del Sur, Lima, Peru
Abstract. The Set Covering Problem (SCP) consists in finding a set of solutions that allow to cover a set of necessities with the minor possible cost. There are many applications of this problem such as rolling production lines or installation of certain services like hospitals. SCP has been solved before with different algorithms like genetic algorithm, cultural algorithm or firefly algorithm among others. The objective of this paper is to show the performance of an Artificial Fish Swarm Algorithm (AFSA) in order to solve SCP. This algorithm, simulates the behavior of a fish shoal inside water and it uses a population of points in space to represent the position of a fish in the shoal. Here we show a study of its simplified version of AFSA in a binary domain with its modifications applied to SCP. This method was tested on SCP benchmark instances from OR-Library website. Keywords: Set Covering Problem · Artificial fish swarm optimization algorithm · Metaheuristics · Combinatorial optimization
1
Introduction
SCP is a classical combinatorial optimization problem which has many practical applications in the world such as deciding construction of firemen stations in different places or installing of cell phone networks in order to obtain the maximum coverage with a minimal possible cost. The SCP can be formulated as follows [1]: n cj xj (1) minimize Z = j=1 c Springer International Publishing Switzerland 2016 H. Fujita et al. (Eds.): IEA/AIE 2016, LNAI 9799, pp. 892–903, 2016. DOI: 10.1007/978-3-319-42007-3 76
An Artificial Fish Swarm Optimization Algorithm
Subject to:
n
aij xj ≥ 1 ∀i ∈ I
893
(2)
j=1
xj ∈ {0, 1}
∀j ∈ J
(3)
Let A = (aij ) be a m × n 0–1 matrix with I = {1, . . . , m} and J = {1, . . . , n} be the row and column sets respectively. Column j can cover a row i if aij = 1. Where cj is a nonnegative value that represents the cost of selecting the column j and xj is a decision variable, it can be 1 if column j is selected or 0 otherwise. The objective is to find a minimum cost subset S ⊆ J, such that each row i ∈ I is covered by at least one column j ∈ S. The SCP was also successfully solved with meta-heuristics such as artificial bee colony [2,3], cultural algorithm [4], swarm optimization particles [5], ant colony optimization [6], firefly algorithm [7,8], shuffled frog leaping algorithm [9] or genetic algorithm [10].
2
Artificial Fish Swarm Algorithm
According to [11] AFSA simulates the behavior of a fish swarm inside the water and this algorithm was proposed and applied in order to solve problems of optimization in an engineering context. Moreover, this method was applied in global optimization problems and bound constrained global optimization problems. In o
Data Loading...
