Resolución del Problema de Set-Covering utilizando un Algoritmo Genético

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

1.

Introducci´ on

El Set Covering Problem (SCP), el Set Packing Problem (SPP) y el Set Partitioning Problem (SPaP), son unos problemas cl´ asicos, que pertenecen a la clase NP-Completo [1] y en donde la entrada esta dada por varios conjuntos de elementos o datos que tienen alg´ un elemento en com´ un. En general, estos problemas consisten en encontrar el n´ umero m´ınimo de conjuntos que contengan un cierto n´ umero de elementos de todos los conjuntos. 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´ on es la selecci´ on de columnas que cubren en forma ´optima al conjunto de filas. Estos tres problemas tienen la misma funci´ on objetivo y se diferencian en las restricciones que deben cumplir. En este trabajo nos vamos a enfocar en el Set-Covering Problem, poniendo ´enfasis en el estado del arte del problema y en la descripci´ on de un algoritmo gen´etico dise˜ nado para resolverlo. Para ello, el trabajo ha sido organizado de la siguiente manera: en el punto 2 se da una definici´on formal del problema, en el punto 3 se presenta una visi´ on del estado del arte respecto a los algoritmos y t´ecnicas incompletas utilizadas para la resoluci´on de problemas del tipo Set-Covering. Aqu´ı se plantean las relajaciones m´as comunes del modelo y los algoritmos basados en heur´ısticas y exactos m´as difundidos en la literatura. El punto 4, presenta el modelo matem´atico planteado para la resoluci´ on de un problema espec´ıfico. En el punto 5 se discute respecto a la representaci´on utilizada para el modelamiento del problema, para luego pasar al punto 6 en donde se describe el algoritmo gen´etico desarrollado. El punto 7 indica los experimentos que se efectuaron principalmente en la etapa de sintonizaci´ on de los par´ ametros del algoritmo y el punto 8 muestra los resultados obtenidos al ejecutar la aplicaci´ on con problemas de test. Finalmente, en el punto 9 se presentan las principales conclusiones del trabajo realizado.

2.

Definici´ on del Problema

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

Una definici´ on m´ as formal es la siguiente. 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´erdida de generalidad, 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 de la siguiente manera: m´ın(z)

=

n X

cj xj

(1)

j=1

Sujeto a: n X aij xj ≥ 1

∀i ∈ M

(2)

j=1

 xj

=

1 0

si j ∈ S si no

∀j ∈ N

(3)

Para entender mejor el planteamiento, supongamos el ejemplo de la Figura 1. Se tiene una ciudad dividida en 20 sectores y 10 lugares en donde pueden ser instalados ciertos servicios, como por ejemplo Cuarteles de Bomberos, Hospitales, etc. Cada lugar puede dar servicio a las comunas adyacentes. Se pide determinar donde ubicar los servicios de tal forma de minimizar los costos, pero asegurar que se cubran todos los sectores.

Figura 1: Sectores de una Ciudad y posibles lugares de instalaci´on de servicios Tenemos el vector de costos C = {c1 , c2 , c3 , c4 , c5 , c6 , c7 , c8 , c9 , c10 }, M = {1, . . . , 20} y N = {1, . . . , 10}. De la Figura 1, podemos construir la Matriz de cobertura A. As´ı, un aij = 1 indica que la columna j cubre a la fila i. Por ejemplo, la columna j = 2 cubre a las filas i = 1, i = 2 , i = 6 e i = 7 mientras que la columna j = 10 cubre a las filas i = 17, i = 19 e i = 20.

2

Ahora, habr´ıa que encontrar el vector binario X = {x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 , x9 , x10 } tal que se cumpla lo siguiente: m´ın(z)

=

10 X

cj xj

j=1

Sujeto a: 10 X aij xj ≥ 1

∀i ∈ M

j=1

 xj

=

1 0

si se instala el servicio en la ubicaci´on j si no                   A=                 

0100000000 1100000000 1010000000 0010000000 0010000000 0100000000 0101000000 0011000000 0000000100 0001010000 0001100000 0001110000 0001101000 0000000110 0000010010 0000110000 0000101001 0000001100 0000000011 0000000001

∀j ∈ N

                                   

La Soluci´on de este problema nos indicar´a donde debemos ubicar los servicios para que cubran todos los sectores a un costo m´ınimo.

3.

Estado del Arte

Dada la dificultad de determinar la soluci´on ´optima (es un problema NP-dif´ıcil) y el gran tama˜ no de los problemas reales, es que se han ideado varios algoritmos de soluci´on ´optima y algoritmos basados en Heur´ıstica. Aunque se ha probado que la existencia de un algoritmo polinomial que se aproxime a la soluci´on ´optima en un valor cercano a 41 log m, implica que P=NP [3], en la pr´actica la mayor´ıa de las heur´ısticas que aparecen en la literatura se acercan muy eficientemente a las soluciones ´optimas [4]. En general, dada la estructura del problema en los casos del mundo real y al considerable esfuerzo en desarrollar algoritmos que rindan m´as y mejor en esos casos, el actual estado del arte del SCP es que los casos con unos cientos de filas y unos miles de columnas pueden resolverse obteniendo resultados ´optimos y los casos con unos miles de filas y unos millones de columnas pueden resolverse obteniendo un valor dentro del 1 % alrededor del ´optimo en un tiempo de ejecuci´ on computacional razonable [5]. Fisher y Kedia [6] presentaron un algoritmo de soluci´on ´optima basado en una heur´ıstica dual y aplicado a SCP con hasta 200 filas y 2000 columnas. Beasley [7] combina heur´ıstica Lagrangiana con una estrategia de Branch mejorada para aumentar las capacidades de su algoritmo anterior [8] y resolver problemas de hasta 400 filas y 4000 columnas. Estos algoritmos de soluci´on cercana a la ´optima est´an basados en procedimientos de ´arboles de b´ usqueda. Entre los m´etodos basados en heur´ısticas, Beasley [9] present´o un algoritmo heur´ıstico Lagrangiano e inform´o que su heur´ıstica hab´ıa dado resultados de mejor calidad que otras heur´ısticas [10] [11] para problemas 3

que involucraran hasta 1000 filas y 10000 columnas. Por otra parte, Jacobs y Brusco [12] desarrollaron una heur´ıstica basada en Simulated Annealing e informaron un ´exito considerable en problemas de hasta 1000 filas y 10000 columnas. Sen [13] investig´ o el rendimiento de un algoritmo de simulated annealing y de un algoritmo gen´etico simple en el SCP de costo m´ınimo, pero dio pocos resultados computacionales. En otro estudio, Beasley [14] desarroll´ o una heur´ıstica para SCP sin costo u ´nico basado en algoritmos gen´eticos. Los resultados computacionales indicaron que dicha heur´ıstica era capaz de generar soluciones ´optimas para problemas de tama˜ no peque˜ no y soluciones de alta calidad para problemas de gran tama˜ no. Adicionalmente, en la literatura se ilustran varios procedimientos que reducen el tama˜ no de un SCP mediante la remoci´ on de filas o columnas redundantes. Los procedimientos m´as com´ unmente usados consideran: La eliminaci´ on de una columna j tal que existe una columna k 6= j para la cual Ij ⊆ Ik y cj ≥ ck P La eliminaci´ on de una columna j tal que cj ≥ i∈Ij m´ın{ck : k ∈ Ji } La eliminaci´ on de una fila i tal que existe una fila h 6= i para la cual Jh ⊆ Ji La inclusi´ on en la soluci´ on de la columna j cuando Ji = {j} Estas reglas se deben aplicar en forma muy cuidadosa, ya que la implementaci´on directa de los correspondientes chequeos puede consumir much´ısimo tiempo en casos de gran tama˜ no. Por otro lado, estos chequeos pueden reducir considerablemente el tama˜ no del caso [5].

3.1.

Relajaciones del Modelo

En general, muchas de las heur´ısticas m´as efectivas y de las aproximaciones exactas a SCP est´an basadas en la soluci´on a la relajaci´ on de Programaci´ on Lineal (PL) del SCP, definida como: m´ın(z)

n X

=

cj xj

j=1

Sujeto a: n X aij xj ≥ 1

∀i ∈ M

j=1

0 ≤ xj

≤ 1

∀j ∈ N

Sin embargo, como la soluci´ on exacta de esta relajaci´on por c´odigos PL de prop´osito general es t´ıpicamente alta en consumo de tiempo, muchos algoritmos SCP recurren a la relajaci´on Lagrangiana combinada con una optimizaci´on sub-gradiente en orden de determinar soluciones cercanas al ´optimo u del dual de la relajaci´on PL 1 , dado por:   X  X m´ ax ui : ui ≤ cj (j ∈ N ), ui ≥ 0(i ∈ M )   i∈M

i∈Ij

m La Relajaci´ on Lagrangiana del modelo SCP original se define como: ∀ vector u ∈ R+ de multiplicadores Lagrangianos asociados a la restricci´ on del modelo, el sub problema Lagrangiano queda: X X L(u) = m´ın cj (u)xj + ui j∈N

Sujeto a: xj

∈

{0, 1}

i∈M

j∈N

P

donde cj (u) = cj − i∈Ij ui es el costo Lagrangiano asociado con la columna j ∈ N . Ahora, una soluci´on ´optima al modelo planteado estar´ıa dada por xj (u) = 1 si cj (u) < 0, xj (u) = 0 si cj (u) > 0 y xj (u) ∈ {0, 1} cuando cj (u) = 0. Adem´ as, dado u, se puede determinar x(u) en un tiempo O(q). El problema Lagrangiano m dual asociado con este modelo consiste en encontrar un vector multiplicador Lagrangiano u∗ ∈ R+ que maximice el corte inferior L(u). Como el modelo tiene la propiedad de integralidad, cualquier soluci´on ´optima u∗ del dual de la relajaci´ on PL del SCP es tambi´en una soluci´on ´optima del problema Lagrangiano dual [6]. 1 con

cada modelo PL, existe otro modelo PL dual que tiene el mismo ´ optimo [15]

4

Pero este no es el u ´nico procedimiento, existiendo en la literatura algunas variaciones al procedimiento anterior. As´ı, Balas y Carrera [16], en vez de relajar las restricciones correspondientes a todas las T filas en M , mantiene en forma expl´ıcita en el problema relajado las filas en un subconjunto M tal que Ji Jh = 0, ∀i,h ∈ M , i 6= h, y relajan de manera Lagrangiana las filas en M \ M . Este problema relajado puede resolverse en un tiempo O(q) y el mejor valor obtenido por esta relajaci´on es igual al valor obtenido a trav´es del problema PL relajado. Una alternativa a la relajaci´ on Lagrangiana es la relajaci´ on sustituta (surrogate relaxation), utilizada por m Lorena en [17]. Para un vector de multiplicadores sustitutos v ∈ R+ , el problema de relajaci´on sustituta de un SCP tiene la siguiente forma: X S(u) = m´ın cj xj j∈N

Sujeto a:  X X  vi  xj ≥ 

j∈N

X

vi

i∈M

i∈Ij

xj

∈

{0, 1}

j∈N

Adem´as, Lorena [17] relaja la restricci´ on xj ∈ {0, 1} y resuelve en un tiempo O(n) la relajaci´on continua del problema. Aunque esta u ´ltima relajaci´ on sigue siendo equivalente a la relajaci´on PL del SCP, los resultados experimentales indicados por Lorena, sugieren que el uso de relajaci´on sustituta en vez de la Lagrangiana dentro de la optimizaci´ on de sub gradiente, permite obtener multiplicadores cercanos al ´optimo en tiempos de computaci´ on m´ as peque˜ nos. Muchos de los m´etodos presentados hasta ahora son utilizados dentro de los algoritmos basados en heur´ıstica. As´ı, su objetivo principal no es el encontrar el valor m´as cercano al ´optimo, sino dirigir la b´ usqueda de soluciones cercanas al ´ optimo en los problemas SCP.

3.2.

Algoritmos basados en Heur´ısticas

Muchos Algoritmos basados en Heur´ısticas utilizan un enfoque Greedy, ya que les permite ser m´as simples y m´as eficientes en t´erminos del tiempo computacional. La idea b´asica consiste en inicializar una soluci´on S como vac´ıa e igualar el conjunto de filas no cubiertas M 0 con M . Despu´es, en forma iterativa, la columna j con el mejor valor de un puntaje σj es sumado a S y M 0 se actualiza. El puntaje σj es una funci´on del costo original cj , del n´ umero de filas en M 0 cubiertas por la columna j y por un multiplicador asociado con esas filas. Al final del procedimiento, el conjunto S contiene un conjunto R de columnas redundantes. La eliminaci´on ´optima de las columnas redundantes implica la resoluci´on de un SCP definido por las columnas en R y las filas en M \(Uj∈S\R Ij ). En otras palabras, se construye una soluci´on comenzando de S = 0, incluyendo en S, en cada iteraci´on, el mejor de los subconjuntos restantes. Existen varios criterios para determinar el mejor subconjunto. Estos criterios caracterizan a los diferentes algoritmos. El esquema general del algoritmo Greedy es el siguiente: procedimiento greedy; begin S := 0; while S no cubra a I do begin seleccionar S y eliminar Ij de F ; S := S {Ij }; reducir(F ) end end El procedimiento reducir(F ) elimina de F aquellos subconjuntos dominados por subconjuntos previamente seleccionados en la soluci´ on. La selecci´on de los subconjuntos se puede hacer de acuerdo a los criterios propuestos por Chv´ atal [18]:   |Ik | : Ik ∈ F Ij = arg m´ax ck 5

Otros criterios atribuyen valores diferentes al numerador o al denominador en la formula anterior, d´andole m´as fuerza a la cardinalidad de un subconjunto o a su costo. Para m´as detalles se puede revisar [10]. Otro Algoritmo basado en heur´ıstica es el propuesto por Beasley [9], el cual entrega soluciones cuyos valores est´an muy cercanos al ´ optimo. Es una especie de algoritmo Primal-Dual. Pn La idea es considerar el dual Lagrangiano del problema original, donde se relajan las restricciones j=1 aij xj ≥ 1. El problema consiste en: m´ax{ϕ(u) : u ≥ 0} y la funci´on Lagrangiana es m´ın

 n X 

j=1

cj −

m X

! aij ui

xj : xj ∈ {0, 1}, j = 1, . . . , n

  

i=1

El Dual Lagrangiano es aproximado mediante un m´etodo de sub-gradiente simple y est´andar. En cada iteraci´on, se fijan los multiplicadores ui en un valor tentativo y se calcula la funci´on Lagrangiana ϕ(u). Despu´es, se actualiza el valor de u y el procedimiento itera hasta que se cumple alguna condici´on de t´ermino. En cada iteraci´ on del algoritmo de sub gradiente, se mantiene a mano una soluci´on dual u. Las variables duales u son utilizadas para calcular el costo reducido asociado a cada subconjunto de F . La reducci´on de costos del subconjunto j esta dado por la siguiente expresi´on: cj −

m X

aij ui

i=1

Al seleccionar todos los subconjuntos que no tengan reducci´on de costos positivos, se puede obtener una cobertura posible y si a´ un hay elementos de I sin cubrir, la soluci´on se completa seleccionando los subconjuntos remanentes de una manera similar al greedy. Finalmente, el algoritmo minimiza la soluci´on, eliminando de la posible soluci´ on los subconjuntos redundantes. El Algoritmo de Lorena [17], por su parte, utiliza la relajaci´on sustituta descrita en la secci´on anterior e incluye, dentro del procedimiento de optimizaci´on del sub-gradiente, una heur´ıstica greedy id´entica a la propuesta por Beasley en [9]. Aunque la mayor´ıa de las aproximaciones heur´ısticas exitosas para el problema SCP est´an basadas en la relajaci´on Lagrangiana, existen algunas excepciones dignas de mencionar. Entre las m´as destacadas se encuentran [14] de Beasley y Chu, [19] de Jacobs y Brusco y [20] de Brusco, Jacobs y Thompson. El primero sigue una aproximaci´ on gen´etica para solucionar el problema mientras que los dos u ´ltimos se basan en simulated annealing. El algoritmo de Beasley y Chu [14], mantiene una poblaci´ on de soluciones del SCP codificadas como vectores x, con valores 0, 1. Inicialmente, se genera una poblaci´on aleatoria de p soluciones. Despu´es, en cada iteraci´on, se seleccionan dos soluciones, x1 y x2 , en forma aleatoria desde la poblaci´on actual y se combinan en una tercera soluci´ on x3 tal que x3j = x1j cuando x1j = x2j , y x3j = x1j con probabilidad c(x2 )/(c(x1 ) + c(x2 )) si x1j 6= x2j , donde c(x) es el costo correspondiente a x. Despu´es de la definici´on de x3 de x1 y x2 , se cambian un cierto n´ umero de componentes de x3 seleccionados en forma aleatoria. Despu´es, x3 es transformado en una soluci´on m´ınima factible a trav´es de un greedy, en forma an´aloga al utilizado por Beasley en [9]. Finalmente, la nueva soluci´ on x3 es sumada a la poblaci´on actual en lugar de la soluci´on previa elegida aleatoriamente. El proceso se detiene luego de un n´ umero determinado de iteraciones. Por otro lado, en [19], se genera una soluci´on inicial S por medio de un algoritmo greedy el cual, en cada iteraci´on, seleccione aleatoriamente una fila no cubierta y agrega a la soluci´on la columna con el menor ´ındice que cubre esa fila. Despu´es de esta adici´on, se remueven todas las posibles columnas redundantes de la soluci´on y el proceso itera hasta que se determina la soluci´on m´ınima posible. Posteriormente, se ejecutan un n´ umero de iteraciones en las cuales se eliminan de la soluci´on actual S, d columnas elegidas aleatoriamente. A su vez, la soluci´ on actual S se completa hasta obtener una nueva soluci´on m´ınima S 0 a trav´es de una proceso greedy, en forma an´ aloga al utilizado por Beasley en [9]. S 0 se vuelve soluci´on actual si es mejor que S, de lo contrario S es reemplazado por S 0 con una probabilidad que decrece exponencialmente con la diferencia entre los valores de S y S 0 y con el n´ umero de iteraciones realizadas. Por su parte, en [2], Parada, Calder´ on, Flores y Pradenas, verificaron el comportamiento de la b´ usqueda Tabu en Problemas de Optimizaci´ on Combinatoria. Con respecto al SCP, los resultados no fueron muy alentadores. Si bien el m´etodo consigue acercarse a la soluci´on ´optima conocida, no logra superar la eficiencia de otras estrategias empleadas en este tipo de problemas. 6

3.3.

Algoritmos exactos

Las aproximaciones exactas m´ as efectivas para SCP se basan en algoritmos del tipo Branch-and-Bound [5], en los cuales los cortes inferiores se calculan resolviendo la relajaci´on PL del SCP, posiblemente de una forma de heur´ıstica dual como se vio en la secci´on anterior. La raz´on principal del ´exito de estas aproximaciones es el hecho de que, a pesar que el corte inferior PL no es siempre fuerte para estas instancias, aparentemente es muy dif´ıcil lograr cortes inferiores significativamente fuertes por m´etodos alternativos que son computacionalmente m´ as caros. Dado que las t´ecnicas completas, como Branch-and-Bound, escapan a los objetivos del presente trabajo, no ser´an tratadas aqu´ı. Sin embargo, si el lector desea obtener m´as informaci´on respecto a este tipo de algoritmos, puede consultar las siguientes publicaciones: [8], [7] y [16].

4.

Modelo matem´ atico Se tiene el siguiente problema: Se dispone de las encuestas sobre los h´abitos de lectura de M personas, referidos a N revistas de circulaci´ on nacional (se sabe qu´e revistas leen las personas). Y tambi´en se conoce el costo de publicar un aviso en cada una de las revistas. Una nueva empresa, que ha definido como su p´ ublico objetivo a estas personas, desea optimizar sus costos de publicidad en una o m´as revistas. Se requiere un modelo Set Covering que les permita resolver las siguientes preguntas: Encontrar el m´ aximo n´ umero de personas a las que puede llegar un anuncio publicitario dado cierto presupuesto. ¿Cu´ al es el costo m´ınimo de llegar a todo el p´ ublico?

Cada pregunta plantea un modelo distinto, por lo que el problema se divide en dos. As´ı, es posible formular dos modelos que resolver´ an cada una de las preguntas.

4.1.

Modelo 1

La primera pregunta plantea la inc´ ognita de cu´anto es el m´aximo n´ umero de personas a las cuales puedo llegar con mi publicidad dado un cierto presupuesto. Para determinar el modelo, debemos definir lo siguiente: Datos: Los datos conocidos son: N´ umero de Personas : M={1,. . .,m} N´ umero de Revistas : N={1,. . .,n} Presupuesto disponible: P Costo de publicar un aviso en la revista j : cj

j∈N 

Informaci´ on respecto a qu´e revistas leen las personas: Aij = Variables: Las variables necesarias para modelar el problema son:  1 si se publica en la revista j xj = 0 si no  1 si no se considera a la persona i yi = 0 si no As´ı, podemos plantear la funci´ on objetivo como: m´ın(z) =

m X i=1

7

yi

1 0

si la persona i lee la revista j si no

Sujeto a: n X

cj xj ≤ P

j=1 n X

aij xj + yi ≥ 1

∀i ∈ M

j=1

4.2.

Modelo 2

La segunda pregunta plantea la inc´ ognita de cu´anto ser´ıa el costo m´ınimo que debo pagar para poder llegar a todo el p´ ublico. Para determinar el modelo, debemos definir lo siguiente: Datos: Los datos conocidos son los mismos del punto anterior. Variables: Las variables necesarias para modelar el problema son:  1 si se publica en la revista j xj = 0 si no As´ı, podemos plantear la funci´ on objetivo como: m´ın(z) =

n X

cj xj

j=1

Sujeto a: n X

aij xj ≥ 1

∀i ∈ M

j=1

Para los efectos de este trabajo, resolveremos el Modelo 2 utilizando un algoritmo gen´etico (AG). Para comprobar su efectividad, trataremos de solucionar algunos de los problemas de la OR-Library de J. E. Beasley, que es una Colecci´ on de benchmarks (test data sets) que se encuentran en: http://people.brunel.ac.uk/ mastjjb/ jeb/orlib/scpinfo.html.

5.

Representaci´ on

Al tratar de resolver un problema, lo primero que hay que definir es la representaci´on a utilizar. Por ejemplo, en los modelos del punto anterior se utiliz´o una representaci´on binaria (el dominio de todas las variables era {0,1}). As´ı, tenemos un vector de n bits (con n el n´ umero de columnas del problema) en donde un 1 en el bit i indica que esa columna (i) es parte de la soluci´on. Por definici´ on, los AG utilizan representaci´on binaria, sin embargo, esta representaci´on tiene el problema que al aplicarle los operadores gen´eticos a los individuos, los resultados no siempre ser´an soluciones factibles. Esto obliga a aplicar una funci´ on de penalizaci´on en la funci´on de evaluaci´on para que quede representado el grado de no satisfacci´ on de la soluci´ on. Otra forma de resolver este problema es aplicando una heur´ıstica que ”arregle” la soluci´ on no factible, convirti´endola en una factible. Pero esta no es la u ´nica representaci´ on que se puede utilizar. Si definimos un vector de largo igual al n´ umero de filas y en cada posici´ on guardamos el n´ umero de la columna que cubre dicha fila, tendremos una representaci´on que resuelve el problema de crear soluciones no factibles por la utilizaci´on de los operadores gen´eticos. Sin embargo, como una misma columna puede cubrir m´as de una fila, se debe crear un m´etodo que elimine esta redundancia para la evaluaci´on de su fitness2 . Es decir, al momento de aplicar la funci´on de evaluaci´on, solo se cuenta una vez cada columna. Lamentablemente, la evaluaci´on del fitness se vuelve ambigua ya que la misma soluci´ on puede ser representada de diferentes formas y cada forma puede dar un valor distinto de fitness dependiendo de c´ omo fue definido el vector. 2 Fitness: valor obtenido de la funci´ on de evaluaci´ on. Mide que tan buena es la soluci´ on analizada. En ocasiones, coincide con el valor de la funci´ on objetivo.

8

Beasley [14] efectu´ o pruebas que indicaron que el rendimiento de un Algoritmo Gen´etico utilizando una representaci´on no binaria fue m´ as bajo que el mismo utilizando una representaci´on binaria. Por tal motivo, en nuestra implementaci´ on se utiliz´ o la representaci´on binaria junto con una funci´on que toma en consideraci´on las soluciones no factibles. Dicha funci´ on se explicar´a m´as adelante.

6.

Descripci´ on del Algoritmo

Una vez definida la representaci´ on, se puede comenzar el desarrollo del algoritmo que resolver´a el problema. Para entender mejor el trabajo realizado, primero se explicar´a, en forma breve, las caracter´ısticas principales de un AG, para luego explicar c´omo se aplican dichas caracter´ısticas al problema en cuesti´on.

6.1.

El Algoritmo Gen´ etico est´ andar

Los Algoritmos Gen´eticos (AG) son atribuidos a los estudios efectuados por Holland [21] y son MetaHeur´ısticas que imitan el proceso de evoluci´on de la naturaleza. Los AG est´andar, por su parte, no fueron desarrollados para solucionar problemas de optimizaci´on y por lo tanto no consideran las restricciones que pueda tener un problema determinado. Sin embargo, con peque˜ nas modificaciones, se pueden obtener muy buenos resultados en problemas de optimizaci´on. Los AG copian el proceso evolucionario mediante el procesamiento simultaneo de una poblaci´on de soluciones. Por lo general, se comienza con una poblaci´on generada de manera aleatoria, cuyos individuos se van recombinando de acuerdo al valor que tengan en la funci´on de evaluaci´on. As´ı, mientras mejor sea el valor obtenido por el individuo, m´ as posibilidades tiene de ser seleccionado para generar nuevas soluciones. De esta forma, las nuevas generaciones de soluciones conservan lo bueno de las generaciones anteriores permitiendo, despu´es de un proceso iterativo, llegar a un valor que eventualmente podr´ıa ser el ´optimo. Para hacer las combinaciones, el AG est´andar posee dos operadores gen´eticos que son: el cruzamiento y la mutaci´on. El primero toma dos individuos y forma un tercero mediante la combinaci´on de los componentes de los individuos padres, permitiendo de esta forma que el algoritmo efect´ ue una explotaci´on del espacio de b´ usqueda. Por otra parte, la mutaci´ on toma un individuo y por medio de un proceso genera otro individuo para la nueva poblaci´ on. Esto permite que el algoritmo efect´ ue una exploraci´on del espacio de b´ usqueda. En l´ıneas generales, un AG est´ andar se puede ver como un proceso que efect´ ua lo siguiente: Algoritmo Gen´ etico begin Generar una poblaci´ on inicial; Evaluar el fitness de los individuos de la poblaci´on; repetir: Seleccionar individuos padres desde la poblaci´on; Aplicar los operadores gen´eticos para generar nuevos individuos; Evaluar el fitness de los individuos hijos; Reemplazar algunos o todos los individuos de la poblaci´on por los hijos; hasta condici´ on de t´ ermino end Para implementar un AG es necesario definir los siguientes puntos: Representaci´ on:Este es el punto de partida en la definici´on de un AG. De esta definici´on va a depender gran parte de la estructura final del AG. Como comentamos anteriormente, los AG utilizan una representaci´on binaria, pero existen variaciones como los Algoritmos Evolutivos que permiten otros tipos de representaciones. Tratamiento de los individuos no factibles:Dado que los AG no est´an dise˜ nados para trabajar con restricciones, es necesario definir un criterio o un mecanismo para tratar los individuos no factibles. Inicializaci´ on:Se refiere a c´ omo se va a generar la poblaci´on inicial. Generalmente, dicha poblaci´on se genera de manera aleatoria. Condici´ on de t´ ermino:Se debe establecer hasta cuando va a correr el algoritmo. Generalmente se utiliza un n´ umero determinado de generaciones (iteraciones) o una medida de convergencia. 9

Funciones de Evaluaci´ on o Fitness:Es la funci´on que va a determinar que tan buena es una soluci´on. La funci´ on de evaluaci´ on puede ser igual o diferente a la funci´on objetivo. Operadores Gen´ eticos:Los operadores gen´eticos son los encargados de efectuar la reproducci´on de la poblaci´ on, siendo los m´ as comunes el cruzamiento y la mutaci´on. Selecci´ on:Se refiere a como se van a seleccionar los individuos para aplicarles los operadores gen´eticos. La selecci´on debe dirigir el proceso de b´ usqueda en favor de los miembros m´as aptos. Reemplazo:Este punto se refiere a c´ omo se va a reemplazar la poblaci´on con los individuos generados, lo cu´al puede diferir del c´ omo se seleccionan. Es decir, los criterios de selecci´on y reemplazo no tienen por qu´e ser iguales. Par´ ametros de funcionamiento:Un AG necesita que se le proporcionen ciertos par´ametros de funcionamiento, tales como el tama˜ no de la poblaci´on, la probabilidad de aplicaci´on de los operadores gen´eticos y la cantidad de generaciones, entre otros. Una vez definidos los puntos anteriores, se tiene una estructura adecuada para comenzar el desarrollo y la implementaci´ on del AG.

6.2.

Algoritmo propuesto

Bas´andonos en lo anteriormente descrito y en los trabajos de Beasley [14] y Cormier [22], se desarroll´o un Algoritmo Gen´etico para resolver el problema de Set Covering teniendo los datos de los archivos de la OR-Library de J.E.Beasley como entrada. Para efectos del algoritmo, se definieron las siguientes variables: I J ai bj S U wi cj

= = = = = = = =

el conjunto de todas las filas el conjunto de todas las columnas el conjunto de columnas que cubren la fila i, i ∈ I el conjunto de filas cubiertas por la columna j, j ∈ J el conjunto de columnas en una soluci´on el conjunto de filas no cubiertas el n´ umero de columnas que cubren la fila i, i ∈ I en S costo de la columna j

A continuaci´ on se describe el c´ omo se desarrollaron los distintos puntos que definen un AG. 6.2.1.

Representaci´ on

Como se indic´ o anteriormente, lo primero que se debe definir es la representaci´on que se va a utilizar. En nuestro caso utilizaremos la representaci´ on binaria ya que es la representaci´on m´as natural para el problema de set covering. Adem´ as, del trabajo de Beasley se desprende que la representaci´on binaria es la m´as adecuada para este problema. As´ı, tendremos un vector de igual largo que la cantidad de filas a ser cubiertas. La Tabla 1 muestra un ejemplo de dicha representaci´on. columna (gen) string de bits

1 0

2 1

3 0

4 0

5 1

··· ···

n−1 1

n 0

Tabla 1: Representaci´on binaria de un individuo

6.2.2.

Proceso previo

Una vez definida la representaci´ on y dada la estructura de los archivos de la OR-Library, se debi´o programar una rutina que tomara los datos de un archivo y transformara dicha informaci´on a una representaci´on binaria. La funci´ on inivar() es la encargada de tomar los datos desde un archivo determinado y crear las matrices ai , bj y el vector de costos c, lo que permite que el algoritmo trabaje con esos datos. El nombre del archivo de entrada es indicado al programa a trav´es del teclado. 10

6.2.3.

Tratamiento de los individuos no factibles

Las soluciones modificadas por los operadores gen´eticos no siempre se van a mantener factibles, por lo que hay que aplicar alg´ un m´etodo o funci´ on que trabaje con las soluciones no factibles. Para considerar lo anterior, se probaron dos estrategias. La primera esta basada en el trabajo de [14] y consiste en aplicar una heur´ıstica que arregla una soluci´ on no factible y la convierte en una factible. Dicha heur´ıstica se implementa en la funci´on arregla() y provee, adem´ as, un paso de optimizaci´on local con el fin de hacer al AG m´as eficiente. Los pasos requeridos para hacer factible una soluci´on pasa por determinar cuales filas a´ un no han sido cubiertas y escoger las columnas necesarias para su cobertura. La b´ usqueda de dichas columnas se basa en la proporci´ on: costo de una columna cantidad de filas no cubiertas que cubre Una vez que la soluci´ on se ha vuelto factible, se aplica un paso de optimizaci´on que elimina aquellas columnas redundantes. Una columna redundante es aquella que si se quita, la soluci´on sigue siendo factible. La heur´ıstica efect´ ua, a grandes rasgos, lo siguiente: procedimiento arregla(); begin Inicializar wi := |S ∩ ai |, ∀i ∈ I; Inicializar U := {i|wi = 0, ∀i ∈ I}; Para cada fila i en U (en orden creciente de i): cj ; encontrar la primera columna j (en orden creciente de j) en ai , que minimice U ∩b j incluir j en S y hacer wi := wi + 1, ∀i ∈ bj . Hacer U := U − bj ; Para cada columna j en S (en orden decreciente de j), si wi ≥ 2, ∀i ∈ bj , hacer S := S − j y wi := wi − 1, ∀i ∈ bj ; Ahora S es una soluci´ on factible del problema que no contiene columnas redundantes. end La segunda estrategia utilizada, fue el aplicar una funci´on de penalizaci´on en la funci´on de evaluaci´on, la cual incrementa el valor de esta u ´ltima de acuerdo a la cantidad de filas que no sean cubiertas. El problema principal de esta t´ecnica es que es dif´ıcil encontrar un valor adecuado para el factor de penalizaci´on. 6.2.4.

Inicializaci´ on

El tama˜ no de la poblaci´ on, as´ı como la poblaci´on inicial son elegidos de manera tal que el dominio de las soluciones asociadas con la poblaci´ on este cubierto adecuadamente. El tama˜ no de la poblaci´on depende de c´omo se genere la poblaci´ on inicial. En nuestro caso, la poblaci´on inicial se gener´o aleatoriamente utilizando un m´etodo que genera una soluci´ on factible y sin columnas redundantes. Dicho m´etodo lo implementa la funci´on inicia() de acuerdo a lo siguiente: procedimiento inicia(); begin Inicializar wi := 0, ∀i ∈ I; Inicializar S := 0; Para cada fila i en I: seleccionar en forma aleatoria una columna j desde ai ; incluir j en S y hacer wi := wi + 1, ∀i ∈ bj ; Hacer T := S; repetir Seleccionar, al azar, una columna j, con j ∈ T , y hacer T := T − j; Si wi ≥ 2, ∀i ∈ bj , hacer S := S − j y wi := wi − 1, ∀i ∈ bj ; hasta que T = 0. end El tama˜ no de la poblaci´ on se determin´o en el proceso de sintonizaci´on del AG y ser´a explicado m´as adelante.

11

6.2.5.

Condici´ on de t´ ermino

Los AG poseen b´ asicamente dos condiciones de t´ermino: n´ umero m´aximo de generaciones y convergencia en soluci´on. En el primer caso, el algoritmo itera un n´ umero determinado de veces, luego se detiene y entrega el mejor valor que tenga hasta ese momento. En el segundo caso, el algoritmo itera hasta que los individuos de la poblaci´on converjan en un u ´nico valor. En nuestro caso, se eligi´ o el n´ umero m´ aximo de generaciones como condici´on de t´ermino. 6.2.6.

Funci´ on de Evaluaci´ on

Como se dijo anteriormente, para trabajar con soluciones no factibles se utilizaron dos estrategias. En la primera, utilizando una heur´ıstica que repara las soluciones, las funciones de evaluaci´on y objetivo son iguales y son implementadas a trav´es de la funci´on eval´ ua(). As´ı, la funci´on de evaluaci´on queda: n X

cj ∗ xj

j=1

De la misma manera, en la segunda estrategia, donde se utiliza una funci´on de penalizaci´on, a la funci´on objetivo se le agrega un factor proporcional a la cantidad de filas no cubiertas. De esta forma, la funci´on de evaluaci´on queda: n X

(cj ∗ xj + (k ∗ factor de penalizaci´on))

j=1

Dicho factor de penalizaci´ on debe tener un valor adecuado de forma tal que afecte al resultado final. Es decir, si el valor de dicho factor es muy peque˜ no y el problema es de minimizaci´on, no habr´a diferencias notables en la funci´ on de evaluaci´ on respecto a una soluci´on v´alida. Lo anterior es implementado por la funci´on eval(). 6.2.7.

Operadores Gen´ eticos

Los operadores gen´eticos utilizados en el desarrollo del algoritmo fueron el cruzamiento y la mutaci´on. En ambos casos se probaron dos estrategias distintas para comprobar el funcionamiento del algoritmo. En el caso del cruzamiento, primero se implement´o el operador de fusi´on propuesto por Beasley [14] en la funci´on cruzam(), la cual toma dos individuos padres y genera un solo individuo hijo. Su funcionamiento es el siguiente: dadas las soluciones P1 y P2 , con sus respectivos valores de fitness fP1 y fP2 y el individuo hijo C, se tiene ∀i = 1, . . . , n: begin Si P1 [i] = P2 [i], entonces C[i] := P1 [i] = P2 [i]; Si P1 [i] 6= P2 [i], entonces: 2 ; C[i] := P1 [i] con probabilidad p = p1p+p 2 C[i] := P2 [i] con probabilidad 1 − p; end Lo destacable de este operador es que considera los valores de fitness para determinar que elementos se copian en el hijo, logrando pasar informaci´on de mayor valor a las descendencias. Por otro lado, se implement´ o un operador de cruzamiento en un punto en la funci´on cruzamiento(). Esta funci´on toma dos individuos de la poblaci´on, elige un punto de cruce al azar, intercambia los elementos iniciales entre los individuos y genera dos individuos hijos. Por su parte, el operador de mutaci´ on se implement´o por la funci´on mutaci´ on() con una probabilidad fija y con una variable. Esta ultima va aumentando de acuerdo a la cantidad de generaciones que van pasando y posee un valor m´ aximo definido por un coeficiente. Esto le permite al algoritmo efectuar m´as exploraci´on a medida que avanza en generaciones. En ambos casos, la funci´ on de mutaci´ on toma un individuo, y de acuerdo con la probabilidad de mutaci´on cambia sus componentes: si hay un 0 lo cambia por un 1 y si hay un 1, lo cambia por un 0.

12

6.2.8.

Selecci´ on

Los operadores gen´eticos necesitan que se les entregue uno o dos individuos para procesarlos. Esto hace necesario que se defina un criterio de selecci´on de los individuos. En nuestro caso, la selecci´on se efectu´o de acuerdo al m´etodo de la ruleta, en donde los individuos son seleccionados de acuerdo a una probabilidad determinada a partir de la funci´ on de fitness. As´ı, un individuo con mayor valor de fitness tendr´a m´as posibilidades de ser seleccionado. Esta idea fue implementada en la funci´on selecci´ on(). Por su parte, dado que el problema de set covering es de minimizaci´on, la probabilidad que un individuo sea seleccionado esta determinado por: 1 f

pi = Pmi

1 i=1 fi

Donde fi es el valor obtenido por la soluci´on i en la funci´on de evaluaci´on. 6.2.9.

Reemplazo

Una vez generada la nueva poblaci´ on con los individuos hijos, se eval´ uan y pasa completa como poblaci´on de padres a la nueva generaci´ on. 6.2.10.

Par´ ametros de funcionamiento

El AG posee varios par´ ametros de funcionamiento entre los que se encuentran: Tama˜ no de la poblaci´ on (TAMPOB) N´ umero m´ aximo de generaciones (MAXGEN) Probabilidad de aplicaci´ on del operador de cruzamiento (PCRUZA) Probabilidad de aplicaci´ on del operador de mutaci´on (PMUTA) Factor de penalizaci´ on (PENA) Adem´as de los anteriores, se pueden variar la forma de evaluaci´on y los operadores de cruzamiento y mutaci´on. Una vez codificado el algoritmo, los par´ametros de funcionamiento fueron determinados por medio de la sintonizaci´on del AG. Es decir, se ejecut´ o el algoritmo varias veces y de acuerdo a los resultados obtenidos se fueron modificando los valores de los par´ametros. 6.2.11.

Funcionamiento general del Algoritmo

En l´ıneas generales el AG desarrollado tiene el siguiente funcionamiento: procedimiento AG; begin Generar una poblaci´ on inicial de N soluciones aleatorias. Hacer t = 0; repetir Seleccionar 2 soluciones P1 y P2 de la poblaci´on utilizando el m´etodo de la ruleta; Combinar P1 y P2 para formar una nueva soluci´on C utilizando el operador de cruzamiento; Mutar k columnas seleccionadas de C en forma aleatoria, donde k esta determinado por la probabilidad de aplicaci´ on del operador de mutaci´on; Hacer C v´ alida y remover las columnas redundantes en C aplicando el operador de heur´ıstica; Hacer t = t + 1; hasta que t = M soluciones se hayan generado. La mejor soluci´on encontrada es la con el menor fitness en la poblaci´ on. end El algoritmo entrega el archivo salida.txt con los datos de columnas incluidas en la soluci´on y valor de la soluci´on.

13

7.

Experimentos

Las primeras ejecuciones del AG tuvieron por finalidad sintonizar el algoritmo. La Tabla 2 muestra las principales ejecuciones realizadas con este fin con los respectivos valores de salida registrados. El archivo de entrada utilizado para la sintonizaci´ on fue el scp41.txt. Ejecuci´ on 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

MAXGEN 10 10 10 20 20 20 30 30 30 40 40 40 50 50 50 50 50 1000

TAMPOB 10 20 30 30 40 50 50 60 70 70 80 90 90 100 110 100 110 10000

PCRUZA 0.95 0.90 0.87 0.85 0.80 0.75 0.70 0.75 0.80 0.85 0.87 0.87 0.87 0.87 0.87 0.87 0.87 0.87

PMUTA 0.10 0.10 0.15 0.15 0.20 0.20 0.25 var var var var var 0.15 0.15 0.15 var var var

f()evaluaci´on arregla penaliza arregla penaliza penaliza arregla penaliza arregla penaliza arregla arregla arregla penaliza arregla penaliza arregla arregla arregla

PENA 5000 10000 10000 10000 10000 10000 10000 -

salida 4395 4064 3051 2955 2848 2940 2885 2536 2467 2591 2341 2466 2034 1964 1625 930 441 430

Tabla 2: Principales ejecuciones realizadas para sintonizar el AG Adicionalmente se prob´ o el algoritmo con par´ametros intermedios entre el 17 y el 18, pero la eficiencia no mejor´o lo suficiente como para que valiese la pena utilizar dichos valores. Lo anterior, dado los altos tiempos de ejecuci´on necesarios. Por ejemplo, la ejecuci´on del algoritmo con los par´ametros del punto 18 duro 20 horas y 36 minutos, contra los 23 minutos que demor´o en correr con los par´ametros del punto 17. Finalizada la sintonizaci´ on, se definieron los par´ametros de funcionamiento del algoritmo de acuerdo a lo siguiente: Tama˜ no de la poblaci´ on (TAMPOB): 110 N´ umero m´ aximo de generaciones (MAXGEN): 50 Probabilidad de aplicaci´ on del operador de cruzamiento (PCRUZA): 0.87 Probabilidad de aplicaci´ on del operador de mutaci´on (PMUTA): variable Tipo de evaluaci´ on: con arreglo de soluciones no factibles. Tipo de operador de Cruzamiento: con operador de fusi´on.

8.

Resultados

Con los par´ ametros anteriormente descritos, se ejecut´o el AG para los sets de problemas de la OR-Library 4, 5 y 6. Se efectuaron 10 ejecuciones por cada problema y se guard´o el mejor valor obtenido. La Tabla 3 muestra un listado de los problemas, con sus valores ´optimos conocidos y los mejores resultados obtenidos mediante el AG.

14

Problema 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10 6.1 6.2 6.3 6.4 6.5

´ Valor Optimo 429 512 516 494 512 560 430 492 641 514 253 302 226 242 211 213 293 288 279 265 138 146 145 131 161

Mejor soluci´on 430 547 538 517 586 615 435 501 734 519 276 325 268 253 223 227 302 299 281 279 158 148 145 145 163

Tabla 3: Resultados obtenidos para los diferentes problemas

9.

Conclusiones Se puede observar que, si bien s´ olo se alcanz´o el o´ptimo en el problema 6.3, los valores entregados por el AG se acercan bastante a ´el en la mayor´ıa de los problemas. En general, los tiempos de ejecuci´ on no son menores, por lo que queda pendiente el efectuar una revisi´on de la implementaci´ on con el objeto de mejorar la eficiencia y exactitud del AG. El AG desarrollado permite variar una serie de par´ametros, entre los que destacan la funci´on de evaluaci´on y el operador de cruzamiento. Lo anterior, permite ajustar de mejor manera el funcionamiento del algoritmo de acuerdo a los distintos tipos de problemas que se deseen resolver. A pesar de los largos tiempos de ejecuci´on, el AG propuesto es una alternativa v´alida para la resoluci´on de problemas de Set covering.

Referencias [1] M.R. Garey and D.S.Johnson. Computers and intractability: A guide to the theory of np-completeness. W.H. Freeman and Co., San Francisco, 1979. [2] M. Flores L. Pradenas V. Parada, M. Calderon. Resoluci´on de problemas combinatoriales mediante busqueda tabu. Technical report, Depatamento de Ingenieria Informatica, Universidad de Santiago de Chile. [3] C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. 33rd IEEE Symposium on Foundations of Computer Science., 1992. [4] M. Fischetti A. Caprara and P. Toth. A heuristic method for the set covering problem. Proc. of the Fifth IPCO Conference, Lecture Notes on Computer Science., 1084:72–84, 1995. 15

[5] M. Fischetti A. Caprara and P. Toth. Algorithms for the set covering problem. Annals of Operations Research 98, pages 353–371, 2000. [6] M.L. Fisher and P. Kedia. Optimal solution of set covering/partitioning problems using dual heuristics. Management Science, 36:674–688, 1990. [7] J.E. Beasley and K. Jornsten. Enhancing an algorithm for set covering problems. European Journal of Operational Research., 58:293–300, 1992. [8] J.E. Beasley. An algorithm for set covering problems. European Journal of Operational Research., 31:85–93, 1987. [9] J. E. Beasley. A lagrangean heuristic for set covering problems. Naval Research Logistics, 37:151–164, 1990. [10] E. Balas and A. Ho. Set covering algoritms using cutting planes, heuristics and subgradient optimization. a computational study. Mathematical Programming Study, 12:37–60, 1980. [11] F.J. Vasko and G.R. Wilson. An efficient heuristic for large set covering problems. Naval Research Logistics Quarterly, 31:163–171, 1984. [12] L.W. Jacobs and M.J. Brusco. A simulated annealing-based heuristic for the set covering problem. Working paper, Operations Management and Information Systems Department, Dekalb, IL 60115, USA, 1993. [13] S. Sen. Minimal cost set covering using probabilistic methods. ACM/SIGAPP Symposium on Applied computing, pages 157–164, 1993. [14] J. E. Beasley and P.C. Chu. A genetic algoritm for the set covering problem. 1994. [15] J.J.Franken. Algorithmic modeling and complexity. Lecture Notes., 2003. [16] E. Balas and M.C. Carrera. A dynamic subgradient-based branch-and-bound procedure for set covering. Operations Research, 44:875–890, 1996. [17] L.A.N Lorena and F.B. Lopez. A surrogate heuristic for set covering problems. European Journal of Operational Research, 79:138–150, 1994. [18] V. Chvatal. A greedy heuristic for the set covering problem. Mathematics of Operations Research, 4(3):233–235, 1979. [19] L.W. Jacobs and M.J. Brusco. A local search heuristic for large set-covering problems. Naval Research Logistics, 52:1129–1140, 1995. [20] L.W.Jacobs M.J.Brusco and G.M.Thompson. A morphing procedure to supplement a simulated annealing heuristic for cost- and coverage-correlated weighted set-covering problems. Working Papers, 1996. [21] J. Holland. Adaptation in natural and artificial systems. Ann Arbor, University of Michigan Press., 1976. [22] D. Cormier and S.S.Raghavan. A very simple real-coded genetic algorithm. North Carolina State University and University of North Carolina at Charlotte.

16