Source: http://docplayer.es/317800-Resolucion-del-problema-de-set-covering-utilizando-un-algoritmo-genetico.html
Timestamp: 2019-01-20 05:28:21+00:00

Document:
Resolución del Problema de Set-Covering utilizando un Algoritmo Genético - PDF
Download "Resolución del Problema de Set-Covering utilizando un Algoritmo Genético"
Esteban Villalba Carrasco
1 Resolución del Problema de Set-Covering utilizando un Algoritmo Genético Pablo Itaim Ananias Valparaíso, 20 de Junio del 2005 Resumen El Set Covering Problem (SCP)es un problema clásico, 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ón de servicios, selección de archivos en un banco de datos, simplificación de expresiones booleanas, balanceo de líneas de producción, 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. 1. Introducción El Set Covering Problem (SCP), el Set Packing 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 por varios conjuntos de elementos o datos que tienen algún elemento en común. En general, estos problemas consisten en encontrar el número mínimo de conjuntos que contengan un cierto número 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ón es la selección de columnas que cubren en forma óptima al conjunto de filas. Estos tres problemas tienen la misma función objetivo y se diferencian en las restricciones que deben cumplir. En este trabajo nos vamos a enfocar en el Set-Covering Problem, poniendo énfasis en el estado del arte del problema y en la descripción de un algoritmo genético diseñado para resolverlo. Para ello, el trabajo ha sido organizado de la siguiente manera: en el punto 2 se da una definición formal del problema, en el punto 3 se presenta una visión del estado del arte respecto a los algoritmos y técnicas incompletas utilizadas para la resolución de problemas del tipo Set-Covering. Aquí se plantean las relajaciones más comunes del modelo y los algoritmos basados en heurísticas y exactos más difundidos en la literatura. El punto 4, presenta el modelo matemático planteado para la resolución de un problema específico. En el punto 5 se discute respecto a la representación utilizada para el modelamiento del problema, para luego pasar al punto 6 en donde se describe el algoritmo genético desarrollado. El punto 7 indica los experimentos que se efectuaron principalmente en la etapa de sintonización de los parámetros del algoritmo y el punto 8 muestra los resultados obtenidos al ejecutar la aplicación con problemas de test. Finalmente, en el punto 9 se presentan las principales conclusiones del trabajo realizado. 2. Definición del Problema Como dijimos en el punto anterior, el problema de Set-Covering consiste en encontrar el número 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ón de servicios, selección de archivos en un banco de datos, simplificación de expresiones booleanas, balanceo de líneas de producción, entre otros. [2].
2 Una definición más formal es la siguiente. Sea: A = (a ij ) una matriz binaria (0, 1) de dimensiones m x n C = (c j ) un vector n dimensional de enteros M = {1,..., m} N = {1,..., n} El valor c j (j N) representa el costo de la columna j, y podemos asumir, sin pérdida de generalidad, c j > 0 para j N. Así, decimos que una columna j N cubre una fila i M si a ij = 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) = c j x j (1) Sujeto a: a ij x j 1 i M (2) x j = { 1 si j S 0 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ón de servicios Tenemos el vector de costos C = {c 1, c 2, c 3, c 4, c 5, c 6, c 7, c 8, c 9, c 10 }, M = {1,..., 20} y N = {1,..., 10}. De la Figura 1, podemos construir la Matriz de cobertura A. Así, un a ij = 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
3 Ahora, habría que encontrar el vector binario X = {x 1, x 2, x 3, x 4, x 5, x 6, x 7, x 8, x 9, x 10 } tal que se cumpla lo siguiente: mín(z) = 10 c j x j Sujeto a: 10 a ij x j 1 i M x j = { 1 si se instala el servicio en la ubicación j 0 si no j N A = La Solución de este problema nos indicará 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ón óptima (es un problema NP-difícil) y el gran tamaño de los problemas reales, es que se han ideado varios algoritmos de solución óptima y algoritmos basados en Heurística. Aunque se ha probado que la existencia de un algoritmo polinomial que se aproxime a la solución óptima en un valor cercano a 1 4 log m, implica que P=NP [3], en la práctica la mayoría de las heurísticas que aparecen en la literatura se acercan muy eficientemente a las soluciones óptimas [4]. En general, dada la estructura del problema en los casos del mundo real y al considerable esfuerzo en desarrollar algoritmos que rindan más 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 óptimos y los casos con unos miles de filas y unos millones de columnas pueden resolverse obteniendo un valor dentro del 1 % alrededor del óptimo en un tiempo de ejecución computacional razonable [5]. Fisher y Kedia [6] presentaron un algoritmo de solución óptima 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ón cercana a la óptima están basados en procedimientos de árboles de búsqueda. Entre los métodos basados en heurísticas, Beasley [9] presentó un algoritmo heurístico Lagrangiano e informó que su heurística había dado resultados de mejor calidad que otras heurísticas [10] [11] para problemas 3
4 que involucraran hasta 1000 filas y columnas. Por otra parte, Jacobs y Brusco [12] desarrollaron una heurística basada en Simulated Annealing e informaron un éxito considerable en problemas de hasta 1000 filas y columnas. Sen [13] investigó el rendimiento de un algoritmo de simulated annealing y de un algoritmo genético simple en el SCP de costo mínimo, pero dio pocos resultados computacionales. En otro estudio, Beasley [14] desarrolló una heurística para SCP sin costo único basado en algoritmos genéticos. Los resultados computacionales indicaron que dicha heurística era capaz de generar soluciones óptimas para problemas de tamaño pequeño y soluciones de alta calidad para problemas de gran tamaño. Adicionalmente, en la literatura se ilustran varios procedimientos que reducen el tamaño de un SCP mediante la remoción de filas o columnas redundantes. Los procedimientos más comúnmente usados consideran: La eliminación de una columna j tal que existe una columna k j para la cual I j I k y c j c k La eliminación de una columna j tal que c j i I j mín{c k : k J i } La eliminación de una fila i tal que existe una fila h i para la cual J h J i La inclusión en la solución de la columna j cuando J i = {j} Estas reglas se deben aplicar en forma muy cuidadosa, ya que la implementación directa de los correspondientes chequeos puede consumir muchísimo tiempo en casos de gran tamaño. Por otro lado, estos chequeos pueden reducir considerablemente el tamaño del caso [5] Relajaciones del Modelo En general, muchas de las heurísticas más efectivas y de las aproximaciones exactas a SCP están basadas en la solución a la relajación de Programación Lineal (PL) del SCP, definida como: mín(z) = c j x j Sujeto a: a ij x j 1 i M 0 x j 1 j N Sin embargo, como la solución exacta de esta relajación por códigos PL de propósito general es típicamente alta en consumo de tiempo, muchos algoritmos SCP recurren a la relajación Lagrangiana combinada con una optimización sub-gradiente en orden de determinar soluciones cercanas al óptimo u del dual de la relajación PL 1, dado por: máx u i : u i c j (j N), u i 0(i M) i I j i M La Relajación Lagrangiana del modelo SCP original se define como: vector u R m + de multiplicadores Lagrangianos asociados a la restricción del modelo, el sub problema Lagrangiano queda: L(u) = mín j N Sujeto a: x j {0, 1} j N c j (u)x j + i M u i donde c j (u) = c j i I j u i es el costo Lagrangiano asociado con la columna j N. Ahora, una solución óptima al modelo planteado estaría dada por x j (u) = 1 si c j (u) < 0, x j (u) = 0 si c j (u) > 0 y x j (u) {0, 1} cuando c j (u) = 0. Además, dado u, se puede determinar x(u) en un tiempo O(q). El problema Lagrangiano dual asociado con este modelo consiste en encontrar un vector multiplicador Lagrangiano u R+ m que maximice el corte inferior L(u). Como el modelo tiene la propiedad de integralidad, cualquier solución óptima u del dual de la relajación PL del SCP es también una solución óptima del problema Lagrangiano dual [6]. 1 con cada modelo PL, existe otro modelo PL dual que tiene el mismo óptimo [15] 4
5 Pero este no es el ú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 filas en M, mantiene en forma explícita en el problema relajado las filas en un subconjunto M tal que J i Jh = 0, i,h M, i 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ón es igual al valor obtenido a través del problema PL relajado. Una alternativa a la relajación Lagrangiana es la relajación sustituta (surrogate relaxation), utilizada por Lorena en [17]. Para un vector de multiplicadores sustitutos v R m +, el problema de relajación sustituta de un SCP tiene la siguiente forma: S(u) = mín j N Sujeto a: v i x j v i j N i Ij i M c j x j x j {0, 1} j N Además, Lorena [17] relaja la restricción x j {0, 1} y resuelve en un tiempo O(n) la relajación continua del problema. Aunque esta última relajación sigue siendo equivalente a la relajación PL del SCP, los resultados experimentales indicados por Lorena, sugieren que el uso de relajación sustituta en vez de la Lagrangiana dentro de la optimización de sub gradiente, permite obtener multiplicadores cercanos al óptimo en tiempos de computación más pequeños. Muchos de los métodos presentados hasta ahora son utilizados dentro de los algoritmos basados en heurística. Así, su objetivo principal no es el encontrar el valor más cercano al óptimo, sino dirigir la búsqueda de soluciones cercanas al óptimo en los problemas SCP Algoritmos basados en Heurísticas Muchos Algoritmos basados en Heurísticas utilizan un enfoque Greedy, ya que les permite ser más simples y más eficientes en términos del tiempo computacional. La idea básica consiste en inicializar una solución S como vacía e igualar el conjunto de filas no cubiertas M con M. Después, en forma iterativa, la columna j con el mejor valor de un puntaje σ j es sumado a S y M se actualiza. El puntaje σ j es una función del costo original c j, del número de filas en M 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ón óptima de las columnas redundantes implica la resolución de un SCP definido por las columnas en R y las filas en M\(U j S\R I j ). En otras palabras, se construye una solución comenzando de S = 0, incluyendo en S, en cada iteración, 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 y eliminar I j de F ; S := S {I j }; reducir(f ) end end El procedimiento reducir(f ) elimina de F aquellos subconjuntos dominados por subconjuntos previamente seleccionados en la solución. La selección de los subconjuntos se puede hacer de acuerdo a los criterios propuestos por Chvátal [18]: { } Ik I j = arg máx : I k F c k 5
6 Otros criterios atribuyen valores diferentes al numerador o al denominador en la formula anterior, dándole más fuerza a la cardinalidad de un subconjunto o a su costo. Para más detalles se puede revisar [10]. Otro Algoritmo basado en heurística es el propuesto por Beasley [9], el cual entrega soluciones cuyos valores están muy cercanos al óptimo. Es una especie de algoritmo Primal-Dual. La idea es considerar el dual Lagrangiano del problema original, donde se relajan las restricciones n a ijx j 1. El problema consiste en: máx{ϕ(u) : u 0} y la función Lagrangiana es ( ) m mín c j a ij u i x j : x j {0, 1}, j = 1,..., n i=1 El Dual Lagrangiano es aproximado mediante un método de sub-gradiente simple y estándar. En cada iteración, se fijan los multiplicadores u i en un valor tentativo y se calcula la función Lagrangiana ϕ(u). Después, se actualiza el valor de u y el procedimiento itera hasta que se cumple alguna condición de término. En cada iteración del algoritmo de sub gradiente, se mantiene a mano una solución dual u. Las variables duales u son utilizadas para calcular el costo reducido asociado a cada subconjunto de F. La reducción de costos del subconjunto j esta dado por la siguiente expresión: c j m a ij u i i=1 Al seleccionar todos los subconjuntos que no tengan reducción de costos positivos, se puede obtener una cobertura posible y si aún hay elementos de I sin cubrir, la solución se completa seleccionando los subconjuntos remanentes de una manera similar al greedy. Finalmente, el algoritmo minimiza la solución, eliminando de la posible solución los subconjuntos redundantes. El Algoritmo de Lorena [17], por su parte, utiliza la relajación sustituta descrita en la sección anterior e incluye, dentro del procedimiento de optimización del sub-gradiente, una heurística greedy idéntica a la propuesta por Beasley en [9]. Aunque la mayoría de las aproximaciones heurísticas exitosas para el problema SCP están basadas en la relajación Lagrangiana, existen algunas excepciones dignas de mencionar. Entre las más 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ón genética para solucionar el problema mientras que los dos últimos se basan en simulated annealing. El algoritmo de Beasley y Chu [14], mantiene una población de soluciones del SCP codificadas como vectores x, con valores 0, 1. Inicialmente, se genera una población aleatoria de p soluciones. Después, en cada iteración, se seleccionan dos soluciones, x 1 y x 2, en forma aleatoria desde la población actual y se combinan en una tercera solución x 3 tal que x 3 j = x1 j cuando x1 j = x2 j, y x3 j = x1 j con probabilidad c(x2 )/(c(x 1 ) + c(x 2 )) si x 1 j x2 j, donde c(x) es el costo correspondiente a x. Después de la definición de x3 de x 1 y x 2, se cambian un cierto número de componentes de x 3 seleccionados en forma aleatoria. Después, x 3 es transformado en una solución mínima factible a través de un greedy, en forma análoga al utilizado por Beasley en [9]. Finalmente, la nueva solución x 3 es sumada a la población actual en lugar de la solución previa elegida aleatoriamente. El proceso se detiene luego de un número determinado de iteraciones. Por otro lado, en [19], se genera una solución inicial S por medio de un algoritmo greedy el cual, en cada iteración, seleccione aleatoriamente una fila no cubierta y agrega a la solución la columna con el menor índice que cubre esa fila. Después de esta adición, se remueven todas las posibles columnas redundantes de la solución y el proceso itera hasta que se determina la solución mínima posible. Posteriormente, se ejecutan un número de iteraciones en las cuales se eliminan de la solución actual S, d columnas elegidas aleatoriamente. A su vez, la solución actual S se completa hasta obtener una nueva solución mínima S a través de una proceso greedy, en forma análoga al utilizado por Beasley en [9]. S se vuelve solución actual si es mejor que S, de lo contrario S es reemplazado por S con una probabilidad que decrece exponencialmente con la diferencia entre los valores de S y S y con el número de iteraciones realizadas. Por su parte, en [2], Parada, Calderón, Flores y Pradenas, verificaron el comportamiento de la búsqueda Tabu en Problemas de Optimización Combinatoria. Con respecto al SCP, los resultados no fueron muy alentadores. Si bien el método consigue acercarse a la solución óptima conocida, no logra superar la eficiencia de otras estrategias empleadas en este tipo de problemas. 6
7 3.3. Algoritmos exactos Las aproximaciones exactas más efectivas para SCP se basan en algoritmos del tipo Branch-and-Bound [5], en los cuales los cortes inferiores se calculan resolviendo la relajación PL del SCP, posiblemente de una forma de heurística dual como se vio en la sección anterior. La razón principal del éxito 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étodos alternativos que son computacionalmente más caros. Dado que las técnicas completas, como Branch-and-Bound, escapan a los objetivos del presente trabajo, no serán tratadas aquí. Sin embargo, si el lector desea obtener más información respecto a este tipo de algoritmos, puede consultar las siguientes publicaciones: [8], [7] y [16]. 4. Modelo matemático Se tiene el siguiente problema: Se dispone de las encuestas sobre los hábitos de lectura de M personas, referidos a N revistas de circulación nacional (se sabe qué revistas leen las personas). Y también se conoce el costo de publicar un aviso en cada una de las revistas. Una nueva empresa, que ha definido como su público objetivo a estas personas, desea optimizar sus costos de publicidad en una o más revistas. Se requiere un modelo Set Covering que les permita resolver las siguientes preguntas: Encontrar el máximo número de personas a las que puede llegar un anuncio publicitario dado cierto presupuesto. Cuál es el costo mínimo de llegar a todo el público? Cada pregunta plantea un modelo distinto, por lo que el problema se divide en dos. Así, es posible formular dos modelos que resolverán cada una de las preguntas Modelo 1 La primera pregunta plantea la incógnita de cuánto es el máximo número 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úmero de Personas : M={1,...,m} Número de Revistas : N={1,...,n} Presupuesto disponible: P Costo de publicar un aviso en la revista j : c j j N { 1 si la persona i lee la revista j Información respecto a qué revistas leen las personas: A ij = 0 si no Variables: Las variables necesarias para modelar el problema son: { 1 si se publica en la revista j x j = 0 si no { 1 si no se considera a la persona i y i = 0 si no Así, podemos plantear la función objetivo como: mín(z) = m i=1 y i 7
8 Sujeto a: c j x j P a ij x j + y i 1 i M 4.2. Modelo 2 La segunda pregunta plantea la incógnita de cuánto sería el costo mínimo que debo pagar para poder llegar a todo el público. 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 x j = 0 si no Así, podemos plantear la función objetivo como: Sujeto a: mín(z) = c j x j a ij x j 1 i M Para los efectos de este trabajo, resolveremos el Modelo 2 utilizando un algoritmo genético (AG). Para comprobar su efectividad, trataremos de solucionar algunos de los problemas de la OR-Library de J. E. Beasley, que es una Colección de benchmarks (test data sets) que se encuentran en: mastjjb/ jeb/orlib/scpinfo.html. 5. Representación Al tratar de resolver un problema, lo primero que hay que definir es la representación a utilizar. Por ejemplo, en los modelos del punto anterior se utilizó una representación binaria (el dominio de todas las variables era {0,1}). Así, tenemos un vector de n bits (con n el número de columnas del problema) en donde un 1 en el bit i indica que esa columna (i) es parte de la solución. Por definición, los AG utilizan representación binaria, sin embargo, esta representación tiene el problema que al aplicarle los operadores genéticos a los individuos, los resultados no siempre serán soluciones factibles. Esto obliga a aplicar una función de penalización en la función de evaluación para que quede representado el grado de no satisfacción de la solución. Otra forma de resolver este problema es aplicando una heurística que arregle la solución no factible, convirtiéndola en una factible. Pero esta no es la única representación que se puede utilizar. Si definimos un vector de largo igual al número de filas y en cada posición guardamos el número de la columna que cubre dicha fila, tendremos una representación que resuelve el problema de crear soluciones no factibles por la utilización de los operadores genéticos. Sin embargo, como una misma columna puede cubrir más de una fila, se debe crear un método que elimine esta redundancia para la evaluación de su fitness 2. Es decir, al momento de aplicar la función de evaluación, solo se cuenta una vez cada columna. Lamentablemente, la evaluación del fitness se vuelve ambigua ya que la misma solución puede ser representada de diferentes formas y cada forma puede dar un valor distinto de fitness dependiendo de cómo fue definido el vector. 2 Fitness: valor obtenido de la función de evaluación. Mide que tan buena es la solución analizada. En ocasiones, coincide con el valor de la función objetivo. 8
9 Beasley [14] efectuó pruebas que indicaron que el rendimiento de un Algoritmo Genético utilizando una representación no binaria fue más bajo que el mismo utilizando una representación binaria. Por tal motivo, en nuestra implementación se utilizó la representación binaria junto con una función que toma en consideración las soluciones no factibles. Dicha función se explicará más adelante. 6. Descripción del Algoritmo Una vez definida la representación, se puede comenzar el desarrollo del algoritmo que resolverá el problema. Para entender mejor el trabajo realizado, primero se explicará, en forma breve, las características principales de un AG, para luego explicar cómo se aplican dichas características al problema en cuestión El Algoritmo Genético estándar Los Algoritmos Genéticos (AG) son atribuidos a los estudios efectuados por Holland [21] y son Meta- Heurísticas que imitan el proceso de evolución de la naturaleza. Los AG estándar, por su parte, no fueron desarrollados para solucionar problemas de optimización y por lo tanto no consideran las restricciones que pueda tener un problema determinado. Sin embargo, con pequeñas modificaciones, se pueden obtener muy buenos resultados en problemas de optimización. Los AG copian el proceso evolucionario mediante el procesamiento simultaneo de una población de soluciones. Por lo general, se comienza con una población generada de manera aleatoria, cuyos individuos se van recombinando de acuerdo al valor que tengan en la función de evaluación. Así, mientras mejor sea el valor obtenido por el individuo, más 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és de un proceso iterativo, llegar a un valor que eventualmente podría ser el óptimo. Para hacer las combinaciones, el AG estándar posee dos operadores genéticos que son: el cruzamiento y la mutación. El primero toma dos individuos y forma un tercero mediante la combinación de los componentes de los individuos padres, permitiendo de esta forma que el algoritmo efectúe una explotación del espacio de búsqueda. Por otra parte, la mutación toma un individuo y por medio de un proceso genera otro individuo para la nueva población. Esto permite que el algoritmo efectúe una exploración del espacio de búsqueda. En líneas generales, un AG estándar se puede ver como un proceso que efectúa lo siguiente: Algoritmo Genético begin Generar una población inicial; Evaluar el fitness de los individuos de la población; repetir: Seleccionar individuos padres desde la población; Aplicar los operadores genéticos para generar nuevos individuos; Evaluar el fitness de los individuos hijos; Reemplazar algunos o todos los individuos de la población por los hijos; hasta condición de término end Para implementar un AG es necesario definir los siguientes puntos: Representación:Este es el punto de partida en la definición de un AG. De esta definición va a depender gran parte de la estructura final del AG. Como comentamos anteriormente, los AG utilizan una representación 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án diseñados para trabajar con restricciones, es necesario definir un criterio o un mecanismo para tratar los individuos no factibles. Inicialización:Se refiere a cómo se va a generar la población inicial. Generalmente, dicha población se genera de manera aleatoria. Condición de término:se debe establecer hasta cuando va a correr el algoritmo. Generalmente se utiliza un número determinado de generaciones (iteraciones) o una medida de convergencia. 9
10 Funciones de Evaluación o Fitness:Es la función que va a determinar que tan buena es una solución. La función de evaluación puede ser igual o diferente a la función objetivo. Operadores Genéticos:Los operadores genéticos son los encargados de efectuar la reproducción de la población, siendo los más comunes el cruzamiento y la mutación. Selección:Se refiere a como se van a seleccionar los individuos para aplicarles los operadores genéticos. La selección debe dirigir el proceso de búsqueda en favor de los miembros más aptos. Reemplazo:Este punto se refiere a cómo se va a reemplazar la población con los individuos generados, lo cuál puede diferir del cómo se seleccionan. Es decir, los criterios de selección y reemplazo no tienen por qué ser iguales. Parámetros de funcionamiento:un AG necesita que se le proporcionen ciertos parámetros de funcionamiento, tales como el tamaño de la población, la probabilidad de aplicación de los operadores genéticos 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ón del AG Algoritmo propuesto Basándonos en lo anteriormente descrito y en los trabajos de Beasley [14] y Cormier [22], se desarrolló un Algoritmo Genético 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 = el conjunto de todas las filas J = el conjunto de todas las columnas a i = el conjunto de columnas que cubren la fila i, i I b j = el conjunto de filas cubiertas por la columna j, j J S = el conjunto de columnas en una solución U = el conjunto de filas no cubiertas w i = el número de columnas que cubren la fila i, i I en S c j = costo de la columna j A continuación se describe el cómo se desarrollaron los distintos puntos que definen un AG Representación Como se indicó anteriormente, lo primero que se debe definir es la representación que se va a utilizar. En nuestro caso utilizaremos la representación binaria ya que es la representación más natural para el problema de set covering. Además, del trabajo de Beasley se desprende que la representación binaria es la más 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ón. columna (gen) n 1 n string de bits Tabla 1: Representación binaria de un individuo Proceso previo Una vez definida la representación y dada la estructura de los archivos de la OR-Library, se debió programar una rutina que tomara los datos de un archivo y transformara dicha información a una representación binaria. La función inivar() es la encargada de tomar los datos desde un archivo determinado y crear las matrices a i, b j 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és del teclado. 10
11 Tratamiento de los individuos no factibles Las soluciones modificadas por los operadores genéticos no siempre se van a mantener factibles, por lo que hay que aplicar algún método o función 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ón no factible y la convierte en una factible. Dicha heurística se implementa en la función arregla() y provee, además, un paso de optimización local con el fin de hacer al AG más eficiente. Los pasos requeridos para hacer factible una solución pasa por determinar cuales filas aún no han sido cubiertas y escoger las columnas necesarias para su cobertura. La búsqueda de dichas columnas se basa en la proporción: costo de una columna cantidad de filas no cubiertas que cubre Una vez que la solución se ha vuelto factible, se aplica un paso de optimización que elimina aquellas columnas redundantes. Una columna redundante es aquella que si se quita, la solución sigue siendo factible. La heurística efectúa, a grandes rasgos, lo siguiente: procedimiento arregla(); begin Inicializar w i := S a i, i I; Inicializar U := {i w i = 0, i I}; Para cada fila i en U (en orden creciente de i): encontrar la primera columna j (en orden creciente de j) en a i, que minimice c j U b j ; incluir j en S y hacer w i := w i + 1, i b j. Hacer U := U b j ; Para cada columna j en S (en orden decreciente de j), si w i 2, i b j, hacer S := S j y w i := w i 1, i b j ; Ahora S es una solución factible del problema que no contiene columnas redundantes. end La segunda estrategia utilizada, fue el aplicar una función de penalización en la función de evaluación, la cual incrementa el valor de esta última de acuerdo a la cantidad de filas que no sean cubiertas. El problema principal de esta técnica es que es difícil encontrar un valor adecuado para el factor de penalización Inicialización El tamaño de la población, así como la población inicial son elegidos de manera tal que el dominio de las soluciones asociadas con la población este cubierto adecuadamente. El tamaño de la población depende de cómo se genere la población inicial. En nuestro caso, la población inicial se generó aleatoriamente utilizando un método que genera una solución factible y sin columnas redundantes. Dicho método lo implementa la función inicia() de acuerdo a lo siguiente: procedimiento inicia(); begin Inicializar w i := 0, i I; Inicializar S := 0; Para cada fila i en I: seleccionar en forma aleatoria una columna j desde a i ; incluir j en S y hacer w i := w i + 1, i b j ; Hacer T := S; repetir Seleccionar, al azar, una columna j, con j T, y hacer T := T j; Si w i 2, i b j, hacer S := S j y w i := w i 1, i b j ; hasta que T = 0. end El tamaño de la población se determinó en el proceso de sintonización del AG y será explicado más adelante. 11
12 Condición de término Los AG poseen básicamente dos condiciones de término: número máximo de generaciones y convergencia en solución. En el primer caso, el algoritmo itera un número 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ón converjan en un único valor. En nuestro caso, se eligió el número máximo de generaciones como condición de término Función de Evaluación 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ón y objetivo son iguales y son implementadas a través de la función evalúa(). Así, la función de evaluación queda: c j x j De la misma manera, en la segunda estrategia, donde se utiliza una función de penalización, a la función objetivo se le agrega un factor proporcional a la cantidad de filas no cubiertas. De esta forma, la función de evaluación queda: (c j x j + (k factor de penalización)) Dicho factor de penalización debe tener un valor adecuado de forma tal que afecte al resultado final. Es decir, si el valor de dicho factor es muy pequeño y el problema es de minimización, no habrá diferencias notables en la función de evaluación respecto a una solución válida. Lo anterior es implementado por la función eval() Operadores Genéticos Los operadores genéticos utilizados en el desarrollo del algoritmo fueron el cruzamiento y la mutación. En ambos casos se probaron dos estrategias distintas para comprobar el funcionamiento del algoritmo. En el caso del cruzamiento, primero se implementó el operador de fusión propuesto por Beasley [14] en la función cruzam(), la cual toma dos individuos padres y genera un solo individuo hijo. Su funcionamiento es el siguiente: dadas las soluciones P 1 y P 2, con sus respectivos valores de fitness f P1 y f P2 y el individuo hijo C, se tiene i = 1,..., n: begin Si P 1 [i] = P 2 [i], entonces C[i] := P 1 [i] = P 2 [i]; Si P 1 [i] P 2 [i], entonces: end C[i] := P 1 [i] con probabilidad p = C[i] := P 2 [i] con probabilidad 1 p; p2 p 1+p 2 ; Lo destacable de este operador es que considera los valores de fitness para determinar que elementos se copian en el hijo, logrando pasar información de mayor valor a las descendencias. Por otro lado, se implementó un operador de cruzamiento en un punto en la función cruzamiento(). Esta función toma dos individuos de la población, 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ón se implementó por la función mutación() 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áximo definido por un coeficiente. Esto le permite al algoritmo efectuar más exploración a medida que avanza en generaciones. En ambos casos, la función de mutación toma un individuo, y de acuerdo con la probabilidad de mutación cambia sus componentes: si hay un 0 lo cambia por un 1 y si hay un 1, lo cambia por un 0. 12
13 Selección Los operadores genéticos necesitan que se les entregue uno o dos individuos para procesarlos. Esto hace necesario que se defina un criterio de selección de los individuos. En nuestro caso, la selección se efectuó de acuerdo al método de la ruleta, en donde los individuos son seleccionados de acuerdo a una probabilidad determinada a partir de la función de fitness. Así, un individuo con mayor valor de fitness tendrá más posibilidades de ser seleccionado. Esta idea fue implementada en la función selección(). Por su parte, dado que el problema de set covering es de minimización, la probabilidad que un individuo sea seleccionado esta determinado por: p i = 1 f i m i=1 1 f i Donde f i es el valor obtenido por la solución i en la función de evaluación Reemplazo Una vez generada la nueva población con los individuos hijos, se evalúan y pasa completa como población de padres a la nueva generación Parámetros de funcionamiento El AG posee varios parámetros de funcionamiento entre los que se encuentran: Tamaño de la población (TAMPOB) Número máximo de generaciones (MAXGEN) Probabilidad de aplicación del operador de cruzamiento (PCRUZA) Probabilidad de aplicación del operador de mutación (PMUTA) Factor de penalización (PENA) Además de los anteriores, se pueden variar la forma de evaluación y los operadores de cruzamiento y mutación. Una vez codificado el algoritmo, los parámetros de funcionamiento fueron determinados por medio de la sintonización del AG. Es decir, se ejecutó el algoritmo varias veces y de acuerdo a los resultados obtenidos se fueron modificando los valores de los parámetros Funcionamiento general del Algoritmo En líneas generales el AG desarrollado tiene el siguiente funcionamiento: procedimiento AG; begin Generar una población inicial de N soluciones aleatorias. Hacer t = 0; repetir Seleccionar 2 soluciones P 1 y P 2 de la población utilizando el método de la ruleta; Combinar P 1 y P 2 para formar una nueva solución C utilizando el operador de cruzamiento; Mutar k columnas seleccionadas de C en forma aleatoria, donde k esta determinado por la probabilidad de aplicación del operador de mutación; Hacer C válida 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ón encontrada es la con el menor fitness en la población. end El algoritmo entrega el archivo salida.txt con los datos de columnas incluidas en la solución y valor de la solución. 13
14 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ón fue el scp41.txt. Ejecución MAXGEN TAMPOB PCRUZA PMUTA f()evaluación PENA salida arregla penaliza arregla penaliza penaliza arregla penaliza var arregla var penaliza var arregla var arregla var arregla penaliza arregla penaliza var arregla var arregla var arregla Tabla 2: Principales ejecuciones realizadas para sintonizar el AG Adicionalmente se probó el algoritmo con parámetros intermedios entre el 17 y el 18, pero la eficiencia no mejoró lo suficiente como para que valiese la pena utilizar dichos valores. Lo anterior, dado los altos tiempos de ejecución necesarios. Por ejemplo, la ejecución del algoritmo con los parámetros del punto 18 duro 20 horas y 36 minutos, contra los 23 minutos que demoró en correr con los parámetros del punto 17. Finalizada la sintonización, se definieron los parámetros de funcionamiento del algoritmo de acuerdo a lo siguiente: Tamaño de la población (TAMPOB): 110 Número máximo de generaciones (MAXGEN): 50 Probabilidad de aplicación del operador de cruzamiento (PCRUZA): 0.87 Probabilidad de aplicación del operador de mutación (PMUTA): variable Tipo de evaluación: con arreglo de soluciones no factibles. Tipo de operador de Cruzamiento: con operador de fusión. 8. Resultados Con los parámetros anteriormente descritos, se ejecutó 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ó el mejor valor obtenido. La Tabla 3 muestra un listado de los problemas, con sus valores óptimos conocidos y los mejores resultados obtenidos mediante el AG. 14
15 Problema Valor Óptimo Mejor solución Conclusiones Tabla 3: Resultados obtenidos para los diferentes problemas Se puede observar que, si bien sólo se alcanzó el óptimo en el problema 6.3, los valores entregados por el AG se acercan bastante a él en la mayoría de los problemas. En general, los tiempos de ejecución no son menores, por lo que queda pendiente el efectuar una revisión de la implementación con el objeto de mejorar la eficiencia y exactitud del AG. El AG desarrollado permite variar una serie de parámetros, entre los que destacan la función de evaluación 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ón, el AG propuesto es una alternativa válida para la resolución 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, [2] M. Flores L. Pradenas V. Parada, M. Calderon. Resolución 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., [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,
16 [5] M. Fischetti A. Caprara and P. Toth. Algorithms for the set covering problem. Annals of Operations Research 98, pages , [6] M.L. Fisher and P. Kedia. Optimal solution of set covering/partitioning problems using dual heuristics. Management Science, 36: , [7] J.E. Beasley and K. Jornsten. Enhancing an algorithm for set covering problems. European Journal of Operational Research., 58: , [8] J.E. Beasley. An algorithm for set covering problems. European Journal of Operational Research., 31:85 93, [9] J. E. Beasley. A lagrangean heuristic for set covering problems. Naval Research Logistics, 37: , [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, [11] F.J. Vasko and G.R. Wilson. An efficient heuristic for large set covering problems. Naval Research Logistics Quarterly, 31: , [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, [13] S. Sen. Minimal cost set covering using probabilistic methods. ACM/SIGAPP Symposium on Applied computing, pages , [14] J. E. Beasley and P.C. Chu. A genetic algoritm for the set covering problem [15] J.J.Franken. Algorithmic modeling and complexity. Lecture Notes., [16] E. Balas and M.C. Carrera. A dynamic subgradient-based branch-and-bound procedure for set covering. Operations Research, 44: , [17] L.A.N Lorena and F.B. Lopez. A surrogate heuristic for set covering problems. European Journal of Operational Research, 79: , [18] V. Chvatal. A greedy heuristic for the set covering problem. Mathematics of Operations Research, 4(3): , [19] L.W. Jacobs and M.J. Brusco. A local search heuristic for large set-covering problems. Naval Research Logistics, 52: , [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, [21] J. Holland. Adaptation in natural and artificial systems. Ann Arbor, University of Michigan Press., [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

References: Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución