Dos estrategias de búsqueda anytime basadas en programación lineal entera para resolver el problema de selección de requisitos

Dos estrategias de b´usqueda anytime basadas en programaci´on lineal entera para resolver el problema de selecci´on de requisitos Francisco Chicano1, Miguel ´ Angel Dom´ınguez1, Isabel del ´ Aguila2, Jos´e del Sagrado2y Enrique Alba1 1Universidad de M´alaga, Andaluc´ıa Tech, Espa˜na [email protected],[email protected],[email protected] 2Universidad de Almer´ıa, Espa˜na {imaguila,jsagrado}@ual.es Resumen El problema de selecci´on de requisitos (o Next Release Problem, NRP) consiste en seleccionar el subconjunto de requisitos que se va a desarrollar en la siguiente versi´on de una aplicaci´on software. Esta selecci´on se debe hacer de tal forma que maximice la satisfacci´on de las partes interesadas a la vez que se minimiza el esfuerzo empleado en el desarrollo y se cumple un conjunto de restricciones. Trabajos recientes han abordado la formulaci´on bi-objetivo de este problema usando t´ecnicas exactas basadas en resolutores SAT y resolutores de programaci´on lineal entera. Ambos se enfrentan a dificultades cuando las instancias tienen un gran tama˜no. En la pr´actica, no es necesario calcular todas las soluciones del frente de Pareto (que pueden llegar a ser muchas) y basta con obtener un buen n´umero de soluciones no dominadas bien distribuidas en el espacio objetivo. Las estrategias de b´usqueda basadas en ILP que se han utilizado en el pasado para encontrar un frente bien distribuido en cualquier instante de tiempo solo buscan soluciones que pueden obtenerse minimizando una suma ponderada de los objetivos (soluciones soportadas). En este trabajo proponemos dos estrategias basadas en ILP que son capaces de encontrar el frente completo con suficiente tiempo y que, adem´as, tienen la propiedad de aportar un conjunto de soluciones bien distribuido en el frente objetivo en cualquier momento de la b´usqueda. 1. Introducci´on La Ingenier´ıa de Requisitos define el proceso, o conjunto de tareas, para descubrir el prop´osito de cualquier sistema, identificando las personas involucradas y sus necesidades [10]. Este proceso es esencial en el desarrollo de sistemas software, ya que debido a la naturaleza l´ogica del software, la principal medida de ´exito del sistema desarrollado vendr´a dada por el grado de consecuci´on o cumplimiento de los requisitos. Los procesos relacionados con los requisitos no son f´aciles de llevar a cabo porque residen en el espacio del problema y no en el de la soluci´on, adem´as son procesos difusos en el ciclo de vida de desarrollo de software, en el que ideas informales deben ser traducidas a ideas formales; clientes y organizaciones deben colaborar para alcanzar un acuerdo preciso y sin ambig¨uedades de lo que debe ser desarrollado. La planificaci´on de versiones, es decir, la definici´on de c´omo va a ir evolucionando un producto software a lo largo de su vida ´util, es una tarea fundamental ligada al campo de la Ingenier´ıa de Requisitos. En general, los clientes proponen numerosas nuevas caracter´ısticas o requisitos que en la mayor´ıa de los casos no todas pueden completarse dentro de las limitaciones impuestas por el tiempo y los recursos y que, por tanto, deben acotarse de alguna manera [2]. Estas decisiones suelen tener que considerar varios objetivos diferentes e incluso conflictivos, como las interacciones o dependencias entre las caracter´ısticas candidatas, las preferencias de los clientes o las limitaciones en los recursos. En otras palabras, la planificaci´on de versiones, en general, implica la optimizaci´on basada en m´ultiples criterios [7]. Los clientes, que buscan su propio inter´es, demandan las mejoras que consideran importantes, pero no todas ellas pueden ser satisfechas. Por un lado, cada requisito significa un coste en t´erminos de esfuerzo que la empresa tiene que asumir, y por otro lado, ni todos los clientes son igualmente importantes para la empresa, ni todas las caracter´ısticas son igualmente importantes para los clientes. Los factores de mercado tambi´en pueden influir en este proceso de selecci´on: la empresa puede estar interesada en satisfacer las necesidades de los clientes m´as nuevos o en garantizar que cada cliente ve cumplido al menos uno de sus requisitos propuestos. Este problema de planificaci´on multi-objetivo se ha resuelto en el pasado usando tanto metaheur´ısticas [11], que no aseguran la calidad de las soluciones obtenidas pero son capaces de obtener soluciones de calidad aceptable en tiempos cortos, como t´ecnicas exactas que calculan el frente ´optimo de Pareto [1,13]. En este trabajo nos acercamos a este segundo enfoque. En particular, hemos observado que en el trabajo de Veerapen et al. [13] el algoritmo empleado para encontrar el frente completo requiere mucho tiempo para las instancias grandes, mientras que el algoritmo que utilizan para encontrar soluciones no dominadas bien distribuidas en el espacio objetivo s´olo es capaz de encontrar soluciones soportadas3. En este trabajo proponemos dos estrategias (descritas en las secciones 4.4 y 4.5) que tratan de encontrar soluciones del frente que est´en bien distribuidas, pero sin renunciar a la completitud, es decir, con suficiente tiempo, los algoritmos pueden calcular el frente de Pareto completo. Adem´as, comparamos estas estrategias con otras tres m´as basadas en programaci´on lineal entera y con t´ecnicas metaheur´ısticas. Adem´as de la propuesta de las dos estrategias de b´usqueda, respondemos las siguientes preguntas de investigaci´on: RQ1: ¿Cu´al es la calidad de la parte del frente de Pareto encontrada por los distintos algoritmos comparados cuando limitamos el tiempo de ejecuci´on de los mismos? RQ2: ¿Cu´ando conviene utilizar metaheur´ısticas para resolver el problema y cu´ando es mejor usar algoritmos basados en programaci´on lineal entera? 3Se denominan soluciones soportadas a aquellas que pueden obtenerse minimizando una suma ponderada de los objetivos. Para responder a ellas hemos realizado un estudio experimental con 19 instancias del problema y un total de ocho algoritmos diferentes. El resto del art´ıculo est´a organizado como sigue. En la secci´on 2 formalizamos el problema de la siguiente versi´on y la secci´on 3 presenta los programas lineales enteros usados para resolverlo. En la secci´on 4 presentamos los distintos algoritmos basados en ILP que utilizamos. La secci´on 5 presenta los resultados de un estudio experimental realizado para comparar los distintos algoritmos. Por ´ultimo, la secci´on 6 presenta las conclusiones y el trabajo futuro. 2. El problema de la siguiente versi´on Partimos de un conjunto de requisitos con dependencias R={r1, r2, . . . , rn} que a´un no han sido desarrollados y que han sido propuestos por un conjunto de mclientes. Cada cliente itiene un peso asociado wi∈Rque mide su importancia dentro del proyecto. Cada requisito rj∈Rtiene un coste cjpara la empresa, es decir cada rjconsumir´a cjrecursos si se desarrolla. El mismo requisito puede ser sugerido por varios clientes y su valor puede ser diferente para cada uno de ellos. El valor del requisito rjpara el cliente ise representa con vij ∈R. En este punto cabe mencionar dos formas de valorar un conjunto de requisitos seleccionado. Por un lado, Xuan et al. [14] consideran que un cliente est´a satisfecho s´olo cuando todos sus requisitos se implementan y, en este caso, sumamos su peso wial grado de satisfacci´on asociado al conjunto de requisitos. Los elementos vij toman dos posibles valores: 1 si el requisito interesa al cliente (tiene valor para ´el) y 0 si no est´a interesado en ´el. Por otro lado, Del Sagrado et al. [11] definen la satisfacci´on asociada a un requisito, sj, como la suma ponderada del valor que le dan los clientes, sj= Pm i=1 wi∗vij. Seg´un esta interpretaci´on, no es necesario implementar todos los requisitos que interesan a un cliente para obtener una cierta satisfacci´on del mismo. En cualquier caso, los requisitos presentan dependencias o interacciones entre ellos, imponiendo un orden de desarrollo determinado, lo que limita las alternativas para ser elegidos [3,8]. Las interacciones entre los requisitos representan restricciones al problema y se agrupan en dos tipos: dependencias funcionales o estructurales ydependencias por recursos consumidos [12]. En este trabajo nos centramos en las dependencias funcionales, que pueden definirse como: Implicaci´on o precedencia.ri⇒rj. El requisito rino se puede seleccionar si el requisito rjno ha sido ya implementado. Combinaci´on o acoplamiento.rirj. Los requisitos riyrjdeben ser incluidos de forma conjunta en el software. Exclusi´on.ri⊕rj. El requisito rino puede incluirse junto al requisito rj. El objetivo ser´a encontrar ˆ R⊆Rde forma que se maximice el valor a la vez que se minimiza el coste para el conjunto de requisitos seleccionados ˆ R. El coste viene dado por la funci´on: coste(ˆ R) = n X j,rj∈ˆ R cj,(1) mientras que el valor viene dado por las funciones: valor(ˆ R) = m X i=1 wiY j,rj∈ˆ R vij yvalor(ˆ R) = n X j,rj∈ˆ R sj,(2) en las interpretaciones de Xuan et al. [14] y Del Sagrado et al. [11], respectivamente. El problema es multi-objetivo y, por tanto no existe una soluci´on ´unica, sino un conjunto de soluciones Pareto ´optimas, tambi´en llamadas no dominadas oeficientes [6]. 3. Formulaci´on del problema como ILP bi-objetivo A partir de la descripci´on del problema, su formulaci´on es bastante directa como programa lineal entero. Para ello, utilizaremos una variable binaria (puede tomar valores 0 y 1) por cada requisito seleccionable. Por simplicidad, aqu´ı usaremos para dichas variables el mismo nombre que los requisitos asociados: r1, r2, etc. Para formar el programa lineal, es necesario transformar cada interacci´on funcional entre requisitos en una igualdad o desigualdad de expresiones lineales. Estas transformaciones se realizan de acuerdo al siguiente esquema: Implicaci´on ri⇒rj:ri≤rj. Combinaci´on rirj:ri=rj. Exclusi´on ri⊕rj:ri+rj≤1 . La funci´on de coste es: coste(r) = n X j=1 cjrj.(3) Las funciones de valor en las interpretaciones de Xuan et al. y Del Sagrado et al. son: valor(t) = m X i=1 witiyvalor(r) = n X j=1 sjrj.(4) donde las variables tique aparecen en la funci´on de valor de Xuan et al. indican si un cliente est´a o no satisfecho. La exigencia de que un cliente est´e satisfecho s´olo cuando todos sus requisitos est´an implementados en la interpretaci´on de Xuan et al., implica la incorporaci´on de restricciones de la forma ti≤rjsi y s´olo si vij = 1. 4. Algoritmos de resoluci´on En esta secci´on presentamos los distintos algoritmos basados en programaci´on lineal entera utilizados para calcular el frente de Pareto del problema de selecci´on de requisitos. Para la exposici´on de los algoritmos se considerar´a, sin p´erdida de generalidad, que los dos objetivos deben ser minimizados. Llamaremos Xal conjunto de soluciones que cumplen con todas las restricciones. Decimos que una soluci´on x∈Xes d´ebilmente eficiente cuando no existe y∈Xtal que fi(y)< fi(x) para i= 1,2, es decir, no existe soluci´on que mejore a xen todos los objetivos. Un soluci´on y∈Xdomina ax∈Xsi fi(y)≤fi(x) para i= 1,2 y existe j∈ {1,2}tal que fj(y)< fj(x). Una soluci´on x∈Xes eficiente si no existe y∈Xque la domine. Toda soluci´on eficiente es d´ebilmente eficiente [6]. Una soluci´on x∈Xse denomina soluci´on soportada si existe un vector de valores reales αi∈Rtal que xtambi´en es soluci´on del problema de minimizaci´on de P2 i=1 αifi(x) sujeto a x∈X. Las principales contribuciones de este art´ıculo son los algoritmos descritos en las secciones 4.4 y 4.5. 4.1. Algoritmo ε-constraint con un ILP por iteraci´on Este algoritmo se muestra en el Algoritmo 1 y es el utilizado en [13] para encontrar el frente de Pareto completo. Al principio calcula una soluci´on zque minimice f2y la introduce en el conjunto FP, de soluciones ´optimas de Pareto. A continuaci´on asigna a εel valor f1(z)−1. Al entrar en el bucle, trata de minimizar f2sujeto a que el valor de f1sea menor que ε. El valor de f1en la nueva soluci´on servir´a para establecer el nuevo l´ımite para f1. El bucle termina cuando no existen soluciones con f1por debajo de , garantiz´andose de esta forma que no existir´an m´as soluciones eficientes. El algoritmo resuelve un ´unico subproblema en cada iteraci´on (l´ınea 5) y s´olo puede garantizar obtener soluciones d´ebilmente eficientes. Esto exige eliminar soluciones dominadas al finalizar el bucle (l´ınea 9). Algoritmo 1 ε-constraint con un ILP por iteraci´on 1: z←resolver {m´ın f2(x),sujeto a x∈X} 2: FP ← {z}// Frente de Pareto 3: ε←f1(z)−1 4: while ∃x∈X, f1(x)≤εdo 5: z←resolver {m´ın f2(x),sujeto a f1(x)≤ε, x ∈X} 6: FP = FP ∪{z} 7: ε←f1(z)−1 8: end while 9: Eliminar de FP las soluciones dominadas 4.2. Algoritmo ε-constraint con dos ILPs por iteraci´on En el Algoritmo 2 mostramos una variante de ε-constraint que resuelve dos subproblemas por iteraci´on en lugar de uno. El objetivo es encontrar en cada iteraci´on una soluci´on eficiente, que se puede a˜nadir a FP sin filtrar. El funcionamiento del bucle es el mismo que en el caso anterior. Este algoritmo fue propuesto para el NRP en [1], donde se us´o un resolutor SAT en lugar de un resolutor ILP para resolver los problemas de optimizaci´on. Podr´ıa parecer que el Algoritmo 1 es m´as r´apido que el Algoritmo 2, ya que el esfuerzo computacional es menor, pero esta diferencia va disminuyendo a medida que el problema a resolver posea un conjunto mayor de soluciones d´ebilmente eficientes. Sup´ongase el caso en que |N|=ky|wN|>2k, siendo NywN los conjuntos de puntos eficientes (no dominados) y d´ebilmente eficientes, respectivamente. El Algoritmo 1 tendr´a que realizar en el bucle m´as de 2kiteraciones y el Algoritmo 2 s´olo 2kiteraciones. Algoritmo 2 ε-constraint con dos ILPs por iteraci´on 1: z←resolver {m´ın f2(x),sujeto a x∈X} 2: z←resolver {m´ın f1(x),sujeto a f2(x)≤f2(z), x ∈X} 3: FP ← {z}// Frente de Pareto 4: ε←f1(z)−1 5: while ∃x∈X, f1(x)≤εdo 6: z←resolver {m´ın f2(x),sujeto a f1(x)≤ε, x ∈X} 7: z←resolver {m´ın f1(x),sujeto a f2(x)≤f2(z), x ∈X} 8: FP = FP ∪{z} 9: ε←f1(z)−1 10: end while 4.3. Algoritmo ε-constraint aumentado (Aε-con) El Algoritmo 3, conocido como augmented ε-constraint o AUGMECON, elimina las deficiencias de los Algoritmos 1 y 2. Por un lado, solo se resuelve un subproblema en cada iteraci´on, y por otro, se garantiza que el punto no dominado obtenido es eficiente. El lector interesado puede consultar [9] para m´as detalles. En cada iteraci´on, el algoritmo fija un valor positivo para la constante λ, que debe ser suficientemente peque˜no para evitar que el algoritmo omita algunas de las soluciones eficientes, y lo bastante grande como para evitar problemas num´ericos. En general, es suficiente tomar un valor de λen [10−3,10−6] (v´ease [9]). En nuestro caso, hemos optado por calcular el valor de λen cada iteraci´on teniendo en cuenta el punto eficiente obtenido anteriormente. En particular la expresi´on que usamos es: λ= 1/(f1(z)−u1), donde u1es una cota inferior de m´ın f1(x), x ∈X, es decir, la primera componente de un punto ut´opico. Algoritmo 3 ε-constraint aumentado 1: z←resolver {m´ın f2(x),sujeto a x∈X} 2: z←resolver {m´ın f1(x),sujeto a f2(x)≤f2(z), x ∈X} 3: FP ← {z}// Frente de Pareto 4: ε←f1(z)−1 5: while ∃x∈X, f1(x)≤εdo 6: Estimar un valor para λ > 0 7: z←resolver {m´ın f2(x)−λl, sujeto a f1(x) + l=ε, x ∈X} 8: FP = FP ∪{z} 9: ε←f1(z)−1 10: end while 4.4. Algoritmo anytime basado en augmented weighted Tchebycheff (AAWTcheby) Todos los algoritmos anteriores encuentran las soluciones eficientes en orden lexicogr´afico de sus objetivos. El principal problema de ese orden se pone de manifiesto cuando se trata de resolver una instancia tan grande que requiere mucho tiempo de c´omputo. En ese caso, los algoritmos encontrar´an s´olo un extremo del frente. Desde un punto de vista pr´actico al decisor le interesa tener un conjunto de soluciones eficientes que se encuentren lo mejor distribuidas posible en el espacio objetivo. Esto puede conseguirse dise˜nando algoritmos que “salten” en el espacio objetivo en busca de soluciones eficientes. Estas estrategias se conocen en ingl´es como anytime. Veerapen et al. [13] utilizaron una b´usqueda dicot´omica para lograr este objetivo. La b´usqueda dicot´omica, sin embargo, adolece de un grave problema: s´olo es capaz de encontrar soluciones eficientes soportadas. Como consecuencia, en frentes c´oncavos, la calidad del frente que calcula puede ser muy baja. En el presente trabajo proponemos dos t´ecnicas aytime que son capaces de encontrar el frente completo con suficiente tiempo. Comenzamos en esta secci´on describiendo la primera de ellas. El algoritmo aumentado y ponderado de Tchebycheff permite encontrar soluciones eficientes en una zona cualquiera del frente usando una sola ejecuci´on de resolutor ILP. La zona a explorar viene determinada por un par de puntos (generalmente eficientes) (z(1), z(2)), que asumimos ordenados de tal forma que z(1) 1< z(2) 1. A partir de estos puntos, el algoritmo resuelve el siguiente problema lineal en cada iteraci´on: m´ın y(5) sujeto a y≥ −(ζ1−ζ0)(f1(x)−ξ1)+(ξ1−ξ0)(f2(x)−ζ1) (6) y≥ −(ζ2−ζ1)(f1(x)−ξ1)+(ξ2−ξ1)(f2(x)−ζ1) (7) f1(x)≤ξ2(8) f2(x)≤ζ0(9) donde los valores de ζiyξison: ξ0=z(1) 1,ζ0=z(1) 2,ξ1=z(2) 1−1/2, ζ1= z(1) 2−1/2, ξ2=z(2) 1,ζ2=z(2) 2. El problema anterior devuelve una soluci´on eficiente que se encuentra entre z(1) yz(2). Para m´as detalles consultar [4]. A partir de este programa podemos construir un algoritmo que primero calcula los dos ´optimos lexicogr´aficos (l´ıneas 1 y 2) y, a continuaci´on, explora el espacio entre ellos. Cada vez que encuentra un nuevo punto eficiente entre dos existentes, lo a˜nade al frente de Pareto y divide el rect´angulo explorado en dos para explorarlos m´as adelante (l´ınea 10). Cuando ya no quedan m´as rect´angulos sin explorar el algoritmo termina. En nuestra implementaci´on los rect´angulos son explorados por orden de ´area, el de mayor ´area se explora primero. Esto permite obtener un punto en cada iteraci´on con potencial para maximizar el hipervolumen cubierto hasta ese momento. Algoritmo 4 Anytime augmented weighted Tchebycheff 1: z(1) ←calcular ´optimo lexicogr´afico para el orden (f1, f2) 2: z(2) ←calcular ´optimo lexicogr´afico para el orden (f2, f1) 3: FP ← {z(1), z(2)}// Frente de Pareto 4: Cola ← {(z(1), z(2))} 5: while Cola 6=∅do 6: (z(1), z(2))←extraerParDeMayorArea(Cola) 7: z←resolverTchebycheff((z(1), z(2))) 8: if zno dominado en (z(1), z(2))then 9: FP = FP ∪{z} 10: Cola ←Cola ∪{(z(1), z),(z, z(2))} 11: end if 12: end while 4.5. Algoritmo anytime basado en ε-constraint aumentado (AAε-con) El Algoritmo 5 act´ua de forma similar al anterior, analizando el rect´angulo en el espacio objetivo delimitado por pares de puntos. La diferencia fundamental entre ambos algoritmos es que en AAε-con se utiliza el algoritmo ε-constraint aumentado para encontrar la soluci´on eficiente dentro de ese rect´angulo. El algoritmo ε-constraint aumentado necesita un valor de ε, que establecemos al punto medio entre z(1) yz(2) (l´ınea 7). Si existe una soluci´on eficiente con f1 menor que dicho ε, el algoritmo la encontrar´a y la incorporar´a a FP, salvo que sea una soluci´on dominada (es decir, que la haya encontrado antes). Si no encuentra ninguna soluci´on, entonces debe a˜nadir a la cola de exploraci´on la mitad del rect´angulo que no ha sido explorado, es decir, aquella con f1mayor que ε. Algoritmo 5 Anytime ε-constraint aumentado 1: z(1) ←calcular ´optimo lexicogr´afico para el orden (f1, f2) 2: z(2) ←calcular ´optimo lexicogr´afico para el orden (f2, f1) 3: FP ← {z(1), z(2)}// Frente de Pareto 4: Cola ← {(z(1), z(2))} 5: while Cola 6=∅do 6: (z(1), z(2))←extraerParDeMayorArea(Cola) 7: ε←(z(1) 1+z(2) 1)/2 8: z←resolver {m´ın f2(x)−λl, s.a. f1(x) + l=ε, x ∈X} 9: if zno dominado en (z(1), z(2))then 10: FP = FP ∪{z} 11: Cola ←Cola ∪{(z(1), z),(z, z(2))} 12: else 13: Cola ←Cola ∪{((ε, z(1) 2), z(2))} 14: end if 15: end while 5. Estudio experimental En esta secci´on comparamos los resultados obtenidos por los distintos algoritmos de programaci´on lineal entera. En particular, estamos interesados en estudiar la calidad del frente de Pareto cuando limitamos el tiempo de ejecuci´on de los algoritmos. Este escenario puede corresponderse con el habitual en la pr´actica, en especial, cuando se usan metodolog´ıas ´agiles y debe resolverse el problema de determinar los requisitos a implementar en la siguiente iteraci´on. Por otro lado, nos gustar´ıa comparar los resultados de programaci´on lineal entera con los algoritmos metaheur´ısticos que se han venido utilizando para resolver este problema hasta el momento. El c´odigo con la implementaci´on de los algoritmos utilizados en el estudio est´a publicado en la URL https://github.com/jfrchicanog/NextReleaseProblem. En dicha URL tambi´en puede encontrarse un enlace a las instancias. 5.1. Instancias Utilizaremos dos conjuntos de instancias para los experimentos. Por un lado, usaremos las 17 instancias de Xuan et al. [14], utilizadas tambi´en en el trabajo de Veerapen et al. [13]. Este conjunto a su vez contiene cinco instancias cl´asicas y 12 realistas. Tienen entre 140 y 4368 requisitos y la ´unica posible relaci´on entre requisitos es la implicaci´on. El segundo conjunto de instancias est´a formado por dos instancias que han sido previamente utilizadas en el trabajo de Del Sagrado et al. [11]. Las instancias tienen 20 y 100 requisitos, respectivamente, y se caracterizan porque, adem´as de la implicaci´on, aparece la relaci´on de simultaneidad. En la primer columna de la tabla 1 aparece el n´umero de requisitos de cada instancia junto a su nombre.