Búsqueda multiobjetivo basada en RBFS y punto ideal

DRAFT B´usqueda multiobjetivo basada en RBFS y Punto Ideal Javier Coego, Lawrence Mandow y Jos´e Luis P´erez de la Cruz* Universidad de M´alaga, Andaluc´ıa Tech. Departamento de Lenguajes y Ciencias de la Computaci´on.{jcoego, lawrence, perez}@lcc.uma.es Resumen Muchos problemas reales precisan del tratamiento simult´aneo de objetivos contrapuestos, donde la mejora de la calidad de uno de ellos conlleva el empeoramiento de otros. Este art´ıculo presenta RIP S, un algoritmo multiobjetivo exacto, basado en RBFS y en el concepto de punto ideal, que localiza el conjunto de soluciones ´optimas de Pareto. Se presentan los resultados de diferentes experimentos entre este algoritmo y algunas adaptaciones anteriores de RBFS al caso multiobjetivo. Los resultados muestran que RIP S supone una mejora sobre estos algoritmos. 1. Introducci´on La b´usqueda del camino ´optimo en un grafo es un problema fundamental en inteligencia artificial. En muchos problemas, la elecci´on del camino ´optimo involucra a m´as de un objetivo, cada uno con su propia funci´on de coste. Las soluciones ´optimas son los denominados ´optimos de Pareto, en los que no es posible mejorar un objetivo sin empeorar al menos otro. Dentro de la b´usqueda multiobjetivo exacta, la b´usqueda depth-first con profundizaci´on iterativa ha sido ampliamente tratada en diferentes trabajos [6] [1] [2]. Si bien el algoritmo RBFS (Recursive Best-First Search)[7] ha mostrado un buen comportamiento frente a las variantes de profundizaci´on iterativa en la b´usqueda con un objetivo [9], esta opci´on apenas ha sido explorada para el caso multiobjetivo. RBFS expande siempre los nodos por primera vez en un orden primero el mejor. RBFS mantiene en memoria ´unicamente la rama que est´a explorando en cada momento, eliminando de memoria el resto de ramas visitadas y recordando el mejor coste calcanzado por cualquiera de esas ramas olvidadas. Si la rama actual supera dicho coste c, se reconsidera la mejor rama olvidada. Una extensi´on de RBFS al caso multiobjetivo debe contemplar, entre otras cosas, que en las ramas discontinuadas puede haber distintos vectores ´optimos de Pareto. Que tengamos constancia, la ´unica generalizaci´on de RBFS al caso multiobjetivo es el algoritmo, MOMA∗0 [4]. Este algoritmo impone un orden lexicogr´afico en la exploraci´on del grafo, lo que le permite utilizar un ´unico vector *La presentaci´on de este trabajo est´a subvencionada por Plan Propio de Investigaci´on de la Universidad de M´alaga - Campus de Excelencia Internacional Andaluc´ıa Tech. DRAFT como cota de profundizaci´on. Esta estrategia, no obstante, puede necesitar de un gran n´umero de profundizaciones para encontrar la soluci´on. Este art´ıculo presenta RIPS, una generalizaci´on alternativa de RBFS al caso multiobjetivo. El nuevo algoritmo utiliza el concepto de punto ideal para el c´alculo de las cotas de profundizaci´on, sacrificando parcialmente el car´acter primero el mejor de RBFS en aras de una mayor eficiencia. El uso del punto ideal permite mantener un ´unico vector como cota de profundizaci´on, reduciendo a la vez el n´umero de estas, al considerar simult´aneamente todos los objetivos. La estructura de este art´ıculo es la siguiente. En la secci´on 2 se ilustran los conceptos principales de la b´usqueda RBFS escalar y multiobjetivo. A continuaci´on se describe el nuevo algoritmo RIP S y se presenta un ejemplo. La secci´on 4 analiza el rendimiento de RIPS frente a MOMA∗0. Por ´ultimo, se destacan las conclusiones de este trabajo y posibles l´ıneas de trabajo futuro. 2. Antecedentes 2.1. RBFS Dado un ´arbol, posiblemente infinito, con ra´ız en s, y un conjunto de nodos objetivo Γ, consideremos el problema de buscar un camino ´optimo desde shasta cualquier γ∈Γ. El coste de un camino P= (s=n0, n1, . . . , nk) es la suma de los costes positivos de sus arcos g(P) = Pk−1 i=0 c(ni, ni+1), y disponemos de un heur´ıstico (o cota inferior) ∀n h(n)≥0 del coste desde cada nodo ndel ´arbol hasta un nodo de Γ. La evaluaci´on heur´ıstica del coste de un camino Psn = (s, . . . , n) vendr´a dada por la funci´on f(Psn) = g(Psn) + h(n). RBFS [7] resuelve el problema mediante una b´usqueda tipo backtrack con profundizaciones progresivas, garantizando que los nodos se expanden por primera vez en orden primero el mejor seg´un f, sea ´esta mon´otona o no. Se define nodo abierto como aquel ya visitado alguna vez por el algoritmo, pero a´un no expandido. RBFS mantiene en memoria ´unicamente los nodos del camino actualmente explorado, as´ı como sus hermanos. La implementaci´on es recursiva1, con par´ametros n(nodo a expandir), F(n) (evaluaci´on almacenada de n), y B (cota de profundizaci´on local). La llamada inicial es RBFS(s, f(s),∞). Resumimos a continuaci´on las caracter´ısticas principales de las operaciones avance y retroceso: 1. En su operaci´on de avance, RBFS expande todos los nodos n0en el sub´arbol bajo ntales que su valor f(n0) es menor o igual que la cota superior local, i.e. f(n0)≤B. Aquellos nodos con f(n0)> B quedan abiertos y definen la frontera de b´usqueda bajo n. El valor Bcorresponder´a siempre al menor valor fde todos los nodos que quedaron abiertos en el resto del ´arbol (ramas que no pasan por n), garantizando as´ı el orden de expansi´on primero el mejor. 2. Una vez completada la exploraci´on bajo el nodo n, el algoritmo retroceder´a hasta aquel nodo bajo el que se encuentre en ese momento el nodo 1V´ease [5] para una versi´on iterativa equivalente. DRAFT abierto con menor valor de f. Sea mfa(n) el menor valor de fde los nodos que quedaron abiertos bajo n. El retroceso de RBF S(n, F (n), B) devuelve a su antecesor el valor mfa(n). Esto permitir´a calcular las cotas de profundizaci´on en los siguientes avances. Si no hubiera sucesores, devuelve un valor infinito. 3. Destacamos por ´ultimo una operaci´on propia del avance sobre ramas previamente exploradas. Cuando el algoritmo expande un nodo n, almacena para cada sucesor inmediato niuna evaluaci´on Fi.´ Esta coincidir´a inicialmente con f(ni), pero se actualiza con los valores mfa(ni) cada vez que se realiza una llamada recursiva sobre ni. Cada llamada sobre nihace crecer Fide manera estricta. Cuando en una llamada RBF S(n, F(n), B) se cumple que f(n)< F(n) es porque el nodo nya fue explorado previamente. En tal caso los sucesores nide npueden tomar como valor inicial Fi=max(F(n), f(ni)), reduciendo el n´umero de reexpansiones que debe realizar el algoritmo. La b´usqueda contin´ua hasta que: (a) se realiza una llamada sobre un nodo objetivo, devolviendo el camino encontrado hasta ´el; (b) se produce un retroceso desde s, terminando entonces con fracaso. 2.2. B´ usqueda multiobjetivo Consideremos ahora el caso en el que los arcos est´an etiquetados con un vector de coste q-dimensional c(n, n0) = (c1, . . . , cq), donde ci>0 representa el coste asociado al i-´esimo objetivo. El coste asociado a un camino g(P), los valores heur´ısticos h(n), y las evaluaciones f(P) = g(P) + h(n) ser´an de tipo vectorial. Dados dos vectores v,v0∈Rq, la relaci´on de orden parcial ≺(denotada como relaci´on de dominancia) se define como v≺v0⇔ ∀i(1 ≤i≤q),(vi≤v0 i)∧(v, v0), donde videnota el i-´esimo elemento del vector v. Se define la relaci´on de orden parcial ∼(denotada como relaci´on de indiferencia) como v∼v0⇔(v⊀ v0)∧(v0⊀v). Dado un conjunto de vectores X, se definen los ´optimos de Pareto ofrontera de Pareto de dicho conjunto, nd(X), como el conjunto de vectores no dominados de X, es decir, nd(X) = {x∈X|@y∈Xy≺x}. El problema de b´usqueda multiobjetivo consiste en encontrar el conjunto de todos los caminos desde sa nodos en Γcon costes no dominados. El conjunto de tales costes no dominados se denota por C∗. Las siguientes definiciones ser´an ´utiles m´as adelante. Dados dos vectores v,v0∈Rqdecimos que ves mejor lexicogr´afico que v0(v≺Lv0) sii (∃i vi< v0 i)∧(∀j < i vj=v0 j). Dado un conjunto de vectores, el mejor lexicogr´afico es trivialmente un ´optimo de Pareto. N´otese que ≺Ldefine un orden total. Asimismo, se dice que ves mejor lineal que v0(v≺lin v0) sii Pq i=1 vi<Pq i=1 v0 i Dado un conjunto de vectores X, el punto ideal de X(IP (X)) es un vector formado por los valores m´as peque˜nos que pueden ser localizados en cualquier vector del conjunto Xpara cada componente, es decir, ∀j, 1≤j≤q, IP (X)j= m´ın{vj|v∈X}. Definimos la relaci´on estrictamente mejor () como g g0⇔ ∀j(1 ≤j≤q),gj<g0 j. DRAFT 2.3. MOMA*0 MOMA∗0 [4] es una generalizaci´on de RBFS al problema multiobjetivo descrito en la secci´on 2.2. Por simplicidad, en este trabajo consideraremos una versi´on de MOMA∗0 restringida a un ´unico vector heur´ıstico por nodo. En la b´usqueda multiobjetivo no existe un ´unico valor m´ınimo entre todos los nodos abiertos. En general, existe un conjunto de vectores Pareto-´optimos. La generalizaci´on m´as directa de RBFS pasar´ıa por sustituir los valores F(n) y Bpor conjuntos de vectores Pareto-´optimos. Esto aportar´ıa la ventaja de que el algoritmo profundizase simult´aneamente en la b´usqueda de todas las soluciones ´optimas, resolviendo el problema en un n´umero m´ınimo de profundizaciones. Sin embargo, esta estrategia acarrear´ıa tambi´en una sobrecarga computacional muy elevada. La comprobaci´on para discontinuar la b´usqueda en una rama ya no implicar´ıa simplemente una comparaci´on escalar con la cota, sino comprobaciones de dominancia contra un conjunto de vectores. El c´alculo y almacenamiento de estos conjuntos es tambi´en en s´ı mismo un desaf´ıo, ya que su tama˜no puede crecer exponencialmente con la profundidad de la b´usqueda en el peor caso. Los algoritmos multiobjetivo primero el mejor solucionan en parte este problema usando un orden total en el conjunto de nodos abiertos que garantice que el mejor elemento es siempre un ´optimo de Pareto. MOMA∗0 adopta esta estrategia, explorando las ramas del ´arbol seg´un una estrategia primero el mejor en base a un orden lexicogr´afico. En este caso F(n) y Bser´an vectores2. Otra alternativa ser´ıa emplear un orden lineal. Otra diferencia con RBFS es que MOMA∗0 no termina tras encontrar la primera soluci´on, sino que contin´ua la b´usqueda hasta encontrar todas las soluciones ´optimas de Pareto. Para ello guarda en un conjunto COST S los costes de todas las soluciones encontradas. Este conjunto act´ua como una cota superior global de la b´usqueda, de modo que si en alguna llamada F(n) est´a dominado por alg´un vector de COSTS, se fuerza un retroceso devolviendo un vector de costes infinitos. La llamada inicial es MOMA∗0(s, f(s),∞,∅). En relaci´on a lo expuesto en la secci´on 2 para RBFS, las principales operaciones de MOMA∗0 quedan as´ı: 1. Al realizar un avance,MOMA∗0 expande todos los nodos n0en el sub´arbol bajo ntales que f(n0)LBy no est´an dominados por COST S. La cota B ser´a el mejor flexicogr´afico entre los nodos abiertos del resto del ´arbol. 2. El retroceso de MOMA∗0(n, F(n),B, COSTS) devuelve en este caso mfa(n), definido como el mejor lexicogr´afico de los nodos abiertos bajo n, y los costes de las soluciones encontradas. Si nno tiene sucesores, o todos est´an dominados por COST S devuelve un vector con valores infinitos y ∅. 3. La propagaci´on de valores cuando se avanza sobre ramas previamente exploradas se realiza mediante una funci´on denominada Minf. Los detalles pueden consultarse en [4]. 2En [4] se utiliza una terminolog´ıa diferente. No obstante, utilizaremos estos nombres para proporcionar una correspondencia m´as clara con la notaci´on est´andar de RBFS. DRAFT 3. Algoritmo RIPS En esta secci´on se describe RIP S (Recursive Ideal Point Search), una nueva generalizaci´on RBFS al caso multiobjetivo. Como ya se coment´o en la secci´on 2.3, usar una cota de profundizaci´on vectorial en MOMA∗0 evita tests de dominancia contra la cota, que resultar´ıan computacionalmente muy costosos. Sin embargo, el orden lexicogr´afico empleado por MOMA∗0 prioriza los objetivos de modo que no se profundizar´a en la consecuci´on del primer objetivo hasta que se hayan probado (profundizado en) todos los valores del segundo, y as´ı sucesivamente. En ´ultima instancia, esto puede propiciar un progreso muy lento del algoritmo, ya que si disponemos de qobjetivos y costes ´optimos enteros acotados por d, el n´umero de cotas de profundizaci´on distintas puede ser O(dq) en el peor caso. RIPS utiliza una cota de profundizaci´on que supone un compromiso entre la informaci´on proporcionada por toda la frontera de Pareto de los nodos abiertos, y la eficiencia de usar un ´unico vector de cota (como el ´optimo lexicogr´afico). Concretamente, RIPS utiliza una cota basada en el punto ideal de la frontera de Pareto de los nodos abiertos [2]. Al usar un ´unico vector como cota, se mantiene la eficiencia computacional en las comparaciones. Sin embargo, el punto ideal condensa en un s´olo vector informaci´on de toda la frontera, ya que refleja el mejor coste alcanzado para cada uno de los objetivos durante la profundizaci´on en cualquiera de las ramas. Al igual que en MOMA∗0, el algoritmo RIPS utiliza un conjunto COST S como cota superior global de la b´usqueda. El pseudoc´odigo de RIP S se muestra en la tabla 1. La llamada inicial es RIP S(s, f(s),∞,∅). Las principales operaciones pueden resumirse as´ı: 1. Al realizar un avance,RIPS expande todos los nodos n0en el sub´arbol bajo ntales que f(n0)B. En este caso, Bcorresponde al punto ideal de los vectores de coste no dominados entre los nodos abiertos del resto del ´arbol. 2. El retroceso de RIP S(n, F(n),B, COST S) devuelve el punto ideal de los costes de nodos abiertos bajo n, y los costes de las soluciones encontradas. Si nno tiene sucesores, o todos est´an dominados por COST S, devuelve un vector con valores infinitos y ∅. 3. La propagaci´on de valores cuando se avanza sobre ramas previamente exploradas se realiza a trav´es de la funci´on MaxVector, an´aloga a la funci´on Minf usada por MOMA∗0 (ver [3] para m´as detalles de MaxVector). En general, no es posible emplear el punto ideal como cota y discontinuar la b´usqueda cuando los sucesores est´en dominados por ella. Consid´erese un nodo n con cota de profundizaci´on B= (1,1) y dos sucesores con valores f(n1) = (2,1) yf(n2) = (1,2). Supongamos que la b´usqueda contin´ua hasta n1y se discontin´ua al ser B≺f(n1). La b´usqueda contin´ua por n2, discontinu´andose igualmente al ser B≺f(n2). La nueva cota de nse calcular´ıa como IP({(2,1),(1,2)}) = (1,1), produci´endose un bucle infinito. Por este motivo RIP S utiliza la relaci´on estrictamente mejor para discontinuar la b´usqueda, sacrificando as´ı el car´acter primero el mejor del algoritmo. No obstante, esto garantiza que si disponemos DRAFT RIPS-base () COST S ←∅ (FA, COST S)←RIPS (s, nodomset(H(s)), ∞,COST S) return (COST S) RIPS (n,F An,csup,COST S) NSol ←Vectores de F(n)no dominados por soluciones SI (NSol =∅) devolver (∞,COST S) Ncsup ←Vectores de NSol no estrictamente peores que csup SI (Ncsup =∅) devolver (NSol,COST S) SI (nes un nodo soluci´ on) devolver (∞, nodomset (COST S ∪ {f(n)})) SI (nno tiene sucesores) devolver (∞,COST S) Para cada sucesor nide na˜ nadir elemento en F A con los valores -nodomset(F(ni)), si nno ha sido expandido previamente -nodomset(MaxVector (f,F A(n),∀f∈F(ni))), en caso contrario Disc ←∅ LOOP SI (no quedan sucesores por procesar en F A) SI (Disc =∅) devolver (∞,COST S) SINO Discnds ←Vectores de Disc no dominados por soluciones devolver (IP(Discnds), COST S) fa ←Escoger primer elemento de F A N1←Vectores de fa no dominados por soluciones y no estrictamente peores que la cota SI (N1 = ∅) Eliminar fa de F A Disc ←Disc ∪Vectores de fa no dominados por soluciones SINO SI (en N1hay vectores de la frontera de Pareto de F A) ipcsup ←IP ({csup ∪(F A −fa)) SI (hay alg´ un vector en N1no estrictamente peor que ipcsup) (FA[1], COST S)←RIPS (n1,N1,ipcsup,COST S) SINO Mover fa al final de F A END LOOP Cuadro 1: Algoritmo RIPS. DRAFT de costes ´optimos enteros acotados por d, el n´umero de cotas de profundizaci´on distintas ser´a O(d) en el peor caso. Una detalle importante en RIPS es que la lista FA que contiene los sucesores no est´a ordenada. Cada elemento de la lista contiene los vectores de coste de un sucesor del nodo actual, y se actualiza con la expansi´on de los nodos bajo dicho sucesor. Siempre se procesa el primer elemento de la lista. Un nodo se elimina de FA cuando sus costes est´an dominados por soluciones ya encontradas o son estrictamente peores que la cota superior. En este segundo caso se usan estos vectores para el c´alculo del punto ideal que servir´a como nuevo vector de coste del padre n, al referenciar costes de caminos discontinuados, pero no descartados definitivamente. Si un sucesor es estrictamente peor que otros, se pasa al final de la lista FA, dando preferencia a los estrictamente mejores. En otro caso, el nodo se expande usando por un lado su estimaci´on almacenada, y como cota superior el punto ideal de los vectores de coste de los caminos pendientes. Si la lista F A est´a vac´ıa, se devuelve al nodo ninformaci´on de los caminos discontinuados de inter´es en reexpansiones futuras. Esta informaci´on se almacena en el conjunto Discontinued.RIP S calcula el punto ideal de dicho conjunto, el cual ser´a el nuevo coste de n. Si no hubiera nodos en esta situaci´on, porque fueran soluciones ya encontradas o porque su coste exceda el de las mismas, entonces nrecibe como actualizaci´on de su coste el vector ∞para descartarlo definitivamente. Para mayores detalles sobre el algoritmo RIPS y demostraciones formales de su completitud y admisibilidad, puede consultarse [3]. 3.1. Ejemplo A continuaci´on aplicaremos RIP S al ´arbol de la figura 1a con Γ={γ1, γ2, γ3, γ4}. En la figura 1b se muestra la expansi´on del nodo s, desempatando de izquierda a derecha. FAstoma como valor inicial f(s), y como cota de profundizaci´on el vector ∞, al ser el nodo ra´ız. Dado que sus tres sucesores son no dominados entre s´ı, y suponiendo desempate de izquierda a derecha, se procesa en primer lugar n1(figura 1c). Al no haber expansiones previas de n1,FAn1=f(n1) y su cota de profundizaci´on es el punto ideal de los vectores de coste de los caminos a trav´es de sus hermanos n2yn3, el vector (2,1). Se explorar´a el sub´arbol bajo n1 hasta que todas las ramas exploradas sean estrictamente peores que dicha cota. Al expandir n1(figura 1c), se generan los nodos γ1yγ2. Al ser ambos estrictamente peores que la cota, la b´usqueda se discontin´ua. El punto ideal de sus costes (3,6) y (5,5) ser´a el nuevo vector de coste de n1. Este vector, (3,5), es estrictamente peor que el de n2yn3, con lo cual se aplaza el procesamiento de n1. Al procesar n2, su cota superior se calcula de modo an´alogo a la de n1, resultando en el vector (3,1). La expansi´on de n2(figura 1d) genera γ3, con (3,8). Se expande γ3, y como es un nodo soluci´on (aunque sub´optimo), se a˜nade al conjunto COSTS. Al no haber ramas pendientes, la estimaci´on de n2se actualiza a ∞. A continuaci´on se expande n3(figura 1e), calcul´andose su cota atendiendo a n1. Se expande su ´unico sucesor, γ4, y al ser soluci´on se a˜nade a COST S. Dado que los costes de las dos soluciones encontradas son no dominados entre s´ı, DRAFT (a) Grafo base (b) Paso 1 (c) Paso 2 (d) Paso 3 (e) Paso 4 (f) Paso 5 Figura 1: Resoluci´on mediante RIP S. DRAFT ambas soluciones se mantienen. Al no haber ramas pendientes a trav´es de n3, su estimaci´on ser´a ∞. Al estar dominado por COST S, se descarta. La ´unica rama pendiente es explorar n1, con cota ∞(figura 1f). La rama n1 ya fue explorada, por lo que la estimaci´on almacenada de n1se propaga a sus sucesores, γ1yγ2empleando la funci´on MaxV ector. Se expande γ1y se a˜nade al conjunto COSTS, eliminando a su vez el coste de γ3, ya que lo domina. Al estar γ2dominado por COST S, se discontin´ua de modo definitivo. La estimaci´on almacenada de n1se actualiza a ∞, finalizando la b´usqueda. 4. Evaluaci´on emp´ırica Esta secci´on eval´ua el rendimiento de diversas variantes multiobjetivo de RBFS. Concretamente se comparan RIP S yMOMA∗0. Tambi´en se ha implementado y comparado una variante lineal de MOMA∗0, que usa un orden lineal para la expansi´on. Los experimentos se han realizado sobre ´arboles binarios infinitos aleatorios [8] con la siguiente configuraci´on: 2 objetivos; soluciones a profundidades 16, 18, 20, 22 y 24 del ´arbol de b´usqueda; rango de costes [1,50] para ambos objetivos; heur´ıstico h(n) = 0,∀n; porcentaje de la cantidad de nodos soluci´on en la profundidad fijada para las soluciones 1 %, 10 %, 25 %, 40 %, 60 %, 80 % y 100 %; 10 problemas aleatorios por cada combinaci´on (profundidad soluciones, cantidad soluciones). Se estableci´o un l´ımite temporal para los experimentos igual a 5 ×tip, donde tip es el tiempo medio obtenido por RIP S para cada tipo de problemas. La figura 2 muestra tiempos medios de procesamiento (segundos, escala logar´ıtmica) para cada una de las profundidades fijadas para los nodos soluci´on. No se muestran los experimentos que excedieron el l´ımite temporal fijado. Las gr´aficas de la figura 2, muestran que los algoritmos MOMA∗0 y MOMA∗0lineal ´unicamente fueron capaces de solucionar los problemas en los cuales las soluciones se encontraban a un nivel de profundidad 16. Por lo tanto para las profundidades superiores (18, 20, 22 y 24) s´olo se muestran los resultados obtenidos por RIP S. El rendimiento de los algoritmos mejora a medida que aumenta la cantidad de soluciones disponibles, ya que esto favorece las podas de la cota global COSTS. La principal diferencia entre los algoritmos analizados es la cota de profundizaci´on. El rendimiento observado de MOMA∗0 y MOMA∗0-lineal es similar, dado que el coste lineal de un nodo (suma de las componentes de su vector de coste) tampoco permite determinar de modo individual la calidad de dicho nodo para cada uno de los objetivos considerados. La cota empleada por RIPS facilita una profundizaci´on m´as eficiente con respecto a la de MOMA∗0. Por ´ultimo, el hecho de que RIP S incluya temporalmente soluciones sub´optimas no influye notoriamente en su rendimiento, present´andose como la mejor opci´on dentro de las variantes analizadas.