Solving the Set Covering Problem with the Soccer League Competition Algorithm
The Soccer League Competition (SLC) algorithm is a new metaheuristic approach intendended to solve complex optimization problems. It is based in the interaction model present in soccer teams and the goal to win every match, becoming the best team and leag
- PDF / 189,883 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 14 Downloads / 171 Views
ificia Universidad Cat´ olica de Valpara´ıso, Valpara´ıso, Chile {adrian.jaramillo.s,sebastian.mansilla.v,alvaro.gomez.r, juan.salas.f}@mail.pucv.cl, {broderick.crawford,ricardo.soto}@ucv.cl 2 Universidad Aut´ onoma de Chile, Santiago, Chile 3 Universidad Cient´ıfica del Sur, Lima, Peru 4 Universidad San Sebastian, Santiago, Chile [email protected]
Abstract. The Soccer League Competition (SLC) algorithm is a new metaheuristic approach intendended to solve complex optimization problems. It is based in the interaction model present in soccer teams and the goal to win every match, becoming the best team and league of players. This paper presents adaptations to the initial mode of SLC for the purpose of being applied to the Set Covering Problem (SCP) with a Python implementation. Keywords: Soccer League Competition · Combinatorial tion · Set Covering Problem · Constraint satisfaction
1
·
Optimiza-
Introduction
The Set Covering Problem (SCP) is a widely studied optimization problem present in many real-life scenarios like operations research, machine learning, planning, data mining, data quality and information retrieval. Its main goal in general terms is to find the smallest subcollection of items from a given universe so that its union is that universe and a set of constraints are met. In the last decades, several techniques have been proposed to find the best solutions for complex scenarios of SCP as is discussed in [3–6,11,12]. Soccer League Competition (SCL) is a newly metaheuristic approach based on the soccer competitions, as discussed in [8–10]. This model considers feasible solutions as soccer players, sets of them as soccer teams, and certain movement operators applied on players, emulating the dynamic generated in the competition process to reach the team’s victory and become the best soccer player of the seasson. Mapped to a mathematical model, the goal is to find the best feasible solution that achieves the best value of an evaluation function defined for the problem, using specific explotation and exploration movement operators. c Springer International Publishing Switzerland 2016 H. Fujita et al. (Eds.): IEA/AIE 2016, LNAI 9799, pp. 884–891, 2016. DOI: 10.1007/978-3-319-42007-3 75
Solving the Set Covering Problem with the Soccer League
885
We propose a derived model from SLC to solve optimization problems inside a binary search space, specially applied to solve the Set Covering Problem. This derived model is built in Python programming language and it can lead to a wide variety of benchmarks.
2
The Set Covering Problem
Set Covering Problem, defined as NP-hard problem, establishes a set of m constraints over n decision variables in the {0,1} domain. Its formulation is as follow: min
C=
n
c j xj
(1)
∀i ∈ I = {1, 2, ..., m}
(2)
j=1
s.a.:
n
aij xj ≥ 1
j=1
xj ∈ {0, 1}
∀j ∈ J = {1, 2, ..., n}
(3)
The main idea is to find the solution vector X ∈ {0, 1} such every constraint is verified and C : Rn → R is minimum. n
3
Soccer League Competition
SLC intends to find the solution vector X fo
Data Loading...
