Fish

”Resoluci´n del Problema de Set-Covering
o
utilizando un Algoritmo Gen´tico”
e
Pablo Itaim Ananias
Valpara´ 20 de Junio del 2005
ıso,
Resumen
El Set Covering Problem (SCP)es un problema cl´sico, que consiste en encontrar un conjunto de
a
soluciones que permitan cubrir un conjunto de necesidades al menor costo posible. Existen muchas
aplicaciones de este tipo de problemas, siendo lasprincipales la localizaci´n de servicios, selecci´n de
o
o
archivos en un banco de datos, simplificaci´n de expresiones booleanas, balanceo de l´
o
ıneas de producci´n,
o
entre otros. En el presente trabajo se muestra el estado del arte del problema de Set-Covering y se presenta
un Algoritmo Gen´tico para su resoluci´n.
e
o

1.

Introducci´n
o

El Set Covering Problem (SCP), el SetPacking Problem (SPP) y el Set Partitioning Problem (SPaP),
son unos problemas cl´sicos, que pertenecen a la clase NP-Completo [1] y en donde la entrada esta dada
a
por varios conjuntos de elementos o datos que tienen alg´n elemento en com´n. En general, estos problemas
u
u
consisten en encontrar el n´mero m´
u
ınimo de conjuntos que contengan un cierto n´mero de elementos de
u
todos losconjuntos. En otras palabras, consiste en encontrar un conjunto de soluciones que permitan cubrir
un conjunto de necesidades al menor costo posible. Un conjunto de necesidades corresponde a las filas, y el
conjunto soluci´n es la selecci´n de columnas que cubren en forma ´ptima al conjunto de filas. Estos tres
o
o
o
problemas tienen la misma funci´n objetivo y se diferencian en lasrestricciones que deben cumplir.
o
En este trabajo nos vamos a enfocar en el Set-Covering Problem, poniendo ´nfasis en el estado del arte
e
del problema y en la descripci´n de un algoritmo gen´tico dise˜ado para resolverlo. Para ello, el trabajo ha
o
e
n
sido organizado de la siguiente manera: en el punto 2 se da una definici´n formal del problema, en el punto 3
o
se presenta una visi´n del estadodel arte respecto a los algoritmos y t´cnicas incompletas utilizadas para la
o
e
resoluci´n de problemas del tipo Set-Covering. Aqu´ se plantean las relajaciones m´s comunes del modelo y
o
ı
a
los algoritmos basados en heur´
ısticas y exactos m´s difundidos en la literatura. El punto 4, presenta el modelo
a
matem´tico planteado para la resoluci´n de un problema espec´
a
o
ıfico. En elpunto 5 se discute respecto a la
representaci´n utilizada para el modelamiento del problema, para luego pasar al punto 6 en donde se describe
o
el algoritmo gen´tico desarrollado. El punto 7 indica los experimentos que se efectuaron principalmente en
e
la etapa de sintonizaci´n de los par´metros del algoritmo y el punto 8 muestra los resultados obtenidos
o
a
al ejecutar la aplicaci´n conproblemas de test. Finalmente, en el punto 9 se presentan las principales
o
conclusiones del trabajo realizado.

2.

Definici´n del Problema
o

Como dijimos en el punto anterior, el problema de Set-Covering consiste en encontrar el n´mero m´
u
ınimo
de conjuntos que contengan todos los elementos de todos los conjuntos dados. Existen muchas aplicaciones
de este tipo de problemas, siendolas principales la localizaci´n de servicios, selecci´n de archivos en un banco
o
o
de datos, simplificaci´n de expresiones booleanas, balanceo de l´
o
ıneas de producci´n, entre otros. [2].
o

Una definici´n m´s formal es la siguiente.
o
a
Sea:
A
C
M
N

= (aij ) una matriz binaria (0, 1) de dimensiones m x n
= (cj ) un vector n dimensional de enteros
= {1, . . . , m}
= {1, . . ., n}

El valor cj (j ∈ N ) representa el costo de la columna j , y podemos asumir, sin p´rdida de generalidad,
e
cj > 0 para j ∈ N . As´ decimos que una columna j ∈ N cubre una fila i ∈ M si aij = 1. El SCP busca un
ı,
subconjunto de columnas de costo m´
ınimo S ⊆ N , tal que cada fila i ∈ M esta cubierta por al menos una
columna j ∈ S .
As´ el problema de Set-Covering se puede plantear...