Optimización online

Trabajo Fin de Grado Grado en Matem´ aticas Facultad de Matem´aticas Optimizaci´on online Online optimization Estudiante: Luc´ıa G´omez Toscano Tutor: Diego Ponce L´opez Departamento: Estad´ıstica e Investigaci´on Operativa Fecha: 4 de junio de 2024 A las mujeres de mi vida. Por ser mi ejemplo a seguir, hacerme sentir capaz y apoyarme en el proceso. Resumen La Investigaci´on Operativa es una ciencia que estudia m´etodos anal´ıticos y aplicados para tomar decisiones ´optimas sobre un problema. Sin embargo, hay muchas situaciones de la vida real en las que estas decisiones deben tomarse bajo incertidumbre y esas elecciones afectar´an a estados futuros. Para tomar una buena decisi´on bas´andose solo en datos pasados y actuales, se han estudiado ampliamente diferentes t´ecnicas como los procesos de decisi´on de Markov o la optimizaci´on estoc´astica. No obstante, estos enfoques suponen alg´un modelo probabil´ıstico del futuro para resolver el problema. Por otro lado, en la optimizaci´on robusta, la incertidumbre se caracteriza por su pertenencia a conjuntos, en lugar de distribuciones. En este trabajo exploramos otro enfoque: la optimizaci´on online. Esta metodolog´ıa, popularizada a finales del siglo pasado en inform´atica, sienta las bases del an´alisis competitivo, que nos permite medir la calidad de una estrategia o pol´ıtica de decisi´on. La idea principal es comparar la evaluaci´on de una estrategia teniendo informaci´on incompleta sobre el futuro (online) con su versi´on cl´asica de optimizaci´on, donde se asume informaci´on completa (offline). El documento est´a estructurado de forma que se introducen los conceptos de optimizaci´on online de manera formal utilizando ejemplos para su comprensi´on. En primer lugar, se explican otras t´ecnicas que resuelven problemas con incertidumbre para que el lector tenga una visi´on completa y comprenda mejor las caracter´ısticas de la optimizaci´on online. En segundo lugar, se hacen definiciones formales de optimizaci´on offline y online para luego trabajar con el concepto de ratio competitivo. En el resto del documento, se analiza la competitividad te´oricamente desde problemas m´as simples hasta m´as complejos. Esto nos permite introducir conceptos como el ratio competitivo (estricto) de un algoritmo o problema, adversario, m´etodo de funci´on potencial o m´etodo del promedio. Los problemas cl´asicos que utilizamos como ejemplos son: el problema del alquiler de esqu´ıs como un primer contacto con la notaci´on de la optimizaci´on online; el problema de paginaci´on para ilustrar c´omo demostrar resultados de competitividad y desarrollar un an´alisis computacional emp´ırico que nos permita una mejor comprensi´on de los ratios competitivos en la pr´actica; el problema de actualizaci´on de listas que es un problema m´as complejo, por lo que aprovechamos para introducir las ideas del m´etodo de funci´on potencial y el promedio para estudiar te´oricamente su competitividad; finalizamos con el problema de k-servidores y algunas de sus extensiones con el fin de dar al lector una visi´on general de problemas de optimizaci´on online m´as realistas. Abstract Operations Research is a mathematical science that studies analytical and application methods to optimally make decisions on a problem. However, there are many real-life situations where these decisions have to be made under incomplete information besides those choices affect following states. In order to make a good decision based only in the past and the current data, different techniques as Markov decision processes or stochastic optimization has been widely studied. Nevertheless, these approaches assume some probabilistic model of the future to solve the problem. On the other hand, in robust optimization, uncertainty is characterized by set membership, rather than distributions. In this dissertation, we explore another approach: online optimization. This methodology, popularized at the end of the past century in computer science, lays the foundations of competitive analysis which lets us measure the quality of a decision strategy or policy. The main idea is to compare the evaluation of a strategy having incomplete information about the future (online) with its classical optimization version where complete information is assumed (offline). The document is structured to introduce online optimization concepts formally using examples to clarify them. Firstly, other techniques that solve problems with incomplete information are explained so the reader has a complete picture to better understand online optimization features. Secondly, formal definitions of offline and online optimization are made to later work with the concept of competitive ratio. In the rest of the document, competitiveness is analyzed theoretically from easier to more difficult problems. This lets us introduce concepts such as (strictly) competitive ratio of an algorithm or a problem, adversary, potential function method, or averaging method. The classic problems that we use as examples are: the ski rental problem as a first contact with online optimization notation; the paging problem to illustrate how to proofs competitiveness results and to develop an empirical computational analysis which let us better understanding about competitive ratios in practice; the list update problem is a more complex problem so we take advantage to introduce the ideas of potential function method and averaging to theoretically study its competitiveness; we finish with the k-server problem and some of its extensions in order to give the reader an overview of more realistic online optimization problems. ´ Indice general 1. Introducci´on 1 1.1. M´etodos de decisi´on bajo incertidumbre . . . . . . . . . . . . 1 1.2. Optimizaci´on offline . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3. Optimizaci´on online . . . . . . . . . . . . . . . . . . . . . . . . 6 2. Problema de alquiler de esqu´ıs 9 3. El problema de paginaci´on 13 3.1. Descripci´on ............................ 13 3.2. An´alisis competitivo . . . . . . . . . . . . . . . . . . . . . . . 13 3.3. Estudio computacional . . . . . . . . . . . . . . . . . . . . . . 20 4. Problema de actualizaci´on de una lista 33 4.1. Descripci´on ............................ 34 4.2. An´alisis competitivo . . . . . . . . . . . . . . . . . . . . . . . 35 4.2.1. M´etodo de la funci´on potencial . . . . . . . . . . . . . 35 4.2.2. M´etodo del promedio . . . . . . . . . . . . . . . . . . . 40 5. Problema k-servidores 43 5.1. Sistemas de tareas m´etricas . . . . . . . . . . . . . . . . . . . 43 5.2. Problema k-servidores ...................... 46 6. Conclusiones 53 Referencias 55 6CAP´ ITULO 1. INTRODUCCI ´ ON c:I × S → R≥0es la funci´on objetivo (costes o servicios). type ∈ {min, max}expresa si queremos minimizar el coste co maximizar los sevicios c. Las siguientes definiciones estar´an en base a problemas donde P= (I, Sol, c, min) con cuna funci´on de costes, es decir, problemas de minimizaci´on de costes que podremos generalizar a problemas de maximizar servicios. A continuaci´on definimos algunos conceptos para poder resolver nuestros problemas mediante un algoritmo. Definici´on 5 Un algoritmo de programaci´on offline ALG busca una soluci´on factible ALG[I]∈Sol(I)con costes c(I, ALG[I]),∀I∈ I. Definici´on 6 Denotamos como OPT un algoritmo ´optimo tal que OPT(I) = minS∈Sol c(I, S),∀I∈ S. La estructura de la programaci´on offline es demasiado restrictiva para problemas en los que los datos se van actualizando continuamente. En estos casos recurriremos a la optimizaci´on online que definiremos a continuaci´on. 1.3. Optimizaci´on online De acuerdo con Krumke (2002), los problemas de optimizaci´on online han sido estudiados desde los a˜nos 80. Aunque el t´ermino an´alisis competitivo, que definiremos a lo largo de este documento, fue acu˜nado en Karlin, Manasse, Rudolph, y Sleator (1988), Sleator y Tarjan (1985) sentaron las bases de la optimizaci´on online comparando los algoritmos de optimizaci´on offline y online. En estos problemas no partimos de todo el conjunto de datos inicialmente sino que los iremos introduciendo, a medida que pasa el tiempo, de forma secuencial y tendremos que crear una respuesta de inmediato. Definici´on 7 Un problema de optimizaci´on online es una 4-tupla (R, Σ, A, C)donde: Res el conjunto de posibles datos del problema. 1.3. OPTIMIZACI ´ ON ONLINE 7 Σ⊆Si∈NRies el conjunto de todos los posibles casos, es decir, las entradas recibidas en las ietapas. Aes el conjunto de posibles respuestas. C= (ci)i∈Nes una sucesi´on de funciones de costes (servicios) ci:Ri× Ai→R≥0∪{∞} que proporciona el coste de las respuestas dadas hasta la etapa de tiempo icon c0= 0 . Para un caso σ= (r1, . . . , rn)∈Σde longitud n∈Nnotamos σ≤i:= (r1, . . . , ri)tal que i≤nyσ≤0= 0. El problema de optimizaci´on online ser´a finito si R, A, Σson finitos. Definici´on 8 Un algoritmo determinista de optimizaci´on online ALG calcula una sucesi´on de funciones (fi:Ri→A)i∈N. La soluci´on de ALG para la secuencia de entradas σ= (r1, . . . , rn)∈Σ∩Rnes ALG[σ]=(a1, . . . , an)∈ An, donde ai=fi(σ≤i), su coste total ser´a ALG(σ) = cn(σ, ALG[σ]), y su coste en la etapa i∈ {1, . . . , n}es ALGi(σ) = ALG(σ≤i)−ALG(σ≤i−1). Como punto de partida, vamos a comparar c´omo act´ua un algoritmo de programaci´on online suponiendo que conocemos los datos de antemano. Luego vamos a ver cu´al ser´ıa la mejor soluci´on offline de nuestro problema. Definici´on 9 La soluci´on ´optima offline de nuestro problema de programaci´on online OPT[σ]para la secuencia σ= (r1, . . . , rn)∈Σ∩Rnse determina de manera que OPT[σ]∈arg m´ına∈Ancn(σ, a). Su coste total es OPT(σ) = cn(σ, OPT[σ]) y su coste ´optimo en la etapa i∈ {1, . . . , n}es OPTi(σ) = OPT(σ≤i)−OPT(σ≤i−1). El algoritmo OPT no necesita ser consistente con los pasos de tiempo a diferencia de la soluci´on a un algoritmo online. Con esto queremos decir que el ´optimo online puede ser completamente diferente para σn−1yσn. Definici´on 10 Un algoritmo determinista online ALG es ρ-competitivo, ρ≥ 1, si ∃α≥0tal que ∀σ∈Σverifica ALG(σ)≤ρ·OPT(σ) + α, donde ρpodr´a ser una funci´on de σy cualquier otro par´ametro del problema. ALG es estrictamente ρ-competitivo si se verifica para α= 0. 8CAP´ ITULO 1. INTRODUCCI ´ ON Es decir, es ρ-competitivo si, para cualquier secuencia, la funci´on objetivo no es mayor que ρveces el coste del problema offline ´optimo m´as una constante positiva. Definici´on 11 Si ρ∈Res una constante para la cual el algoritmo online ALG es (estrictamente) ρ-competitivo decimos que ALG es (estrictamente) competitivo. Definici´on 12 El ratio competitivo (estricto) es el ´ınfimo sobre todo ρpara el cual exista un algoritmo (estrictamente) ρ-competitivo. Proposici´on 1 Un algoritmo online ALG tiene ratio competitivo al menos ρ > 1si y solo si existe una sucesi´on (σ(i))i∈Ncon l´ımi→∞ ALG(σ(i)) = ∞y l´ım supi→∞ ALG(σ(i)) OPT(σ(i))≥ρ. Las ´ultimas definiciones y proposiciones pueden consultarse en Disser (2023); Jaillet y Wagner (2014) y sus referencias. Adem´as del concepto ya explicado de ratio competitivo, existe el concepto de ratio competitivo aleatorio basado en las esperanzas de la funci´on objetivo de los algoritmos online. Este concepto va m´as all´a del objetivo de este trabajo, pero si el lector est´a interesado, puede consultar dichas referencias. En conclusi´on, la optimizaci´on online se enfoca en el desarrollo de pol´ıticas que minimicen el arrepentimiento. Su objetivo es tomar decisiones secuenciales que resulten lo m´as cercanas posible a las decisiones ´optimas que se habr´ıan tomado con conocimiento de la informaci´on futura. De esta manera, buscamos reducir la diferencia acumulada entre el rendimiento de la pol´ıtica aplicada y el rendimiento ´optimo posible. O dicho de otra forma, minimizar el arrepentimiento. Cap´ıtulo 2 Problema de alquiler de esqu´ıs Vamos a utilizar el problema de alquiler de equ´ıs para ejemplificar algunos de los conceptos m´as b´asicos de optimizaci´on online. Este problema se nos plantea comunmente en nuestra vida cotidiana cuando nos cuestionamos el siguiente dilema: si no sabemos cu´anto tiempo vamos a darle utilidad a un objeto, ¿cu´anto tiempo deber´ıamos alquilarlo antes de tomar la decisi´on de comprarlo? Para plantear nuestro problema de optimizaci´on online usaremos el esquema explicativo que encontramos en la Tabla 2.1 siguiendo las notas de Disser (2023). Problema de alquiler de esqu´ıs Datos conocidos: Alquilar unos esqu´ıs tiene un coste de una unidad monetaria al d´ıa, comprar los esqu´ıs tendr´a un coste B∈N. Datos online: σ= (d1, . . . , dn)∈1nson los d´ıas que necesitamos los esqu´ıs, la variable desconocida ser´a n, solo nos importan los d´ıas que los necesitamos pues el resto de d´ıas no aportar´an ning´un coste. Posibles respuestas: Alquilar / Comprar / Usar esqu´ıs ya comprados Objetivo: Minimizar el coste total Pn i=1 ALGi(σ). Tabla 2.1: Esquema explicativo del problema de alquiler de esqu´ıs. A continuaci´on, veamos una definici´on formal de nuestro problema, en el que la ´unica entrada desconocida es el n´umero de d´ıas que necesitaremos 9 10 CAP´ ITULO 2. PROBLEMA DE ALQUILER DE ESQU´ IS los esqu´ıs. Tenemos que el conjunto de posibles entradas del problema ser´a R={necesitar unos esqu´ıs}, luego Σ = Si∈NRi. El conjunto de respuestas ser´a A={alquilar , comprar , usar}. Por ´ultimo, veamos cu´al es la funci´on de costes en cada etapa i: ci(a1, . . . , ai) = ci−1(a1, . . . , ai−1)+       1, si ai= alquilar, B, si ai= comprar, 0, si ai= usar y (comprar ∈Si−1 j=1 aj), ∞,c.c. Luego, la ´unica informaci´on que va almacenando el algoritmo online en la etapa ies que n≥i. Adem´as podemos deducir que todo algoritmo ser´a de la forma ALGicuando tomemos la decisi´on de comprar en la etapa ioALG∞si no compramos nunca, pues una vez compramos podemos parar el algoritmo. Teorema 1 ALGBes estrictamente (2 −1/B)-competitivo. Demostraci´on.- Por la definici´on 10 el algoritmo ALGBser´a estrictamente ρ-competitivo si ∀σ∈Σ se tiene ALGB(σ)≤ρ·OPT(σ). Veamos qu´e sabemos sobre OPT, OPT(σ) = m´ın{n, B} pues ser´ıa la mejor soluci´on en el caso de que conociesemos previamente σ. El coste de ALGBser´a ALGB(σ) = n, si n≤B, 2B−1, c.c. Por lo tanto, podemos separar dos casos: Caso n≤B ALGB(σ) = n=OPT(σ). Caso n>B ALGB= 2B−1 = (2 −1/B)B= (2 −1/B)·OPT(σ). 11 En conclusi´on, ∀n∈Nse verifica ALGB(σ)≤(2 −1/B)·OPT(σ). □ Teorema 2 Para todo i=B,ALGino es estrictamente (2−1/B)-competitivo. Demostraci´on.- Separamos en tres posibles casos teniendo en cuenta que la ´unica decisi´on que podemos tomar es la elecci´on de n, el n´umero de d´ıas que queremos ir a esquiar: Caso i=∞ ALG∞es un algoritmo en el que nunca tomamos la decisi´on de comprar unos esqu´ıs. El peor de los casos posibles ser´ıa querer ir siempre a esquiar, es decir, σ= (d1, d2, . . . ). De esta manera ALG∞(σ)−−−→ n→∞ ∞. Entonces ALG∞(σ)≥ρ·OPT(σ),∀ρ. Por lo tanto, ALG∞no ser´ıa un algoritmo competitivo. Caso i≤B−1 Poni´endonos en el lugar del adversario, el peor caso posible, tomamos σ= (d1, . . . , di), dejar de ir a esquiar justo el d´ıa que compramos los esqu´ıs, de esta manera tendremos ALG(σ) = i−1 + B≥2i= 2 ·OPT(σ)>(2 −1/B)·OPT(σ). Caso i>B+ 1 Siguiendo el mismo procedimiento cogemos σ= (d1,· · · , di). Entonces, ALG(σ) = i−1 + B≥2B= 2 ·OPT(σ)>(2 −1/B)·OPT(σ). □ Corolario 1 El problema de alquiler de esqu´ıs tiene un ratio competitivo estricto de (2 −1/B). Demostraci´on.- Por los teoremas 1 y 2 tenemos que el ratio competitivo del problema de alquiler de esqu´ıs es al menos (2 −1/B), nos queda ver que este valor es el ´ınfimo posible para ALGB. 12 CAP´ ITULO 2. PROBLEMA DE ALQUILER DE ESQU´ IS Poni´endonos en el peor de los casos, σ= (d1, . . . , dB) tendremos ALGB= 2B−1 = (2 −1/B)·OPT(σ). □ En definitiva, hemos visto que el algoritmo m´as adecuado para minimizar el coste de nuestro problema es ALGB, comprar los esqu´ıs en la etapa correspondiente al precio de compra de nuestros esqu´ıs. Como ya hemos dicho, esto es una forma de explicar problemas que nos surgen en nuestra vida cotidiana. Por ejemplo, podemos extrapolar el problema de alquiler de esqu´ıs al caso m´as sencillo de costes en la nube. Es decir, realizamos una consulta web y tenemos dos opciones: volver a cargar la web con un coste Ben la etapa de tiempo que se solicite o bien almacenar la busqueda con un coste 1 por unidad de tiempo. El sistema no sabr´a de antemano en qu´e etapa se volver´a a solicitar dicha web luego tendr´a que aplicar un algoritmo online semejante al estudiado en este cap´ıtulo para su resoluci´on. Cap´ıtulo 3 El problema de paginaci´on El problema de paginaci´on es un tema importante en el ´ambito de la computaci´on, especialmente en la administraci´on de la memoria del sistema operativo de los ordenadores. Este problema consiste en la organizaci´on eficaz de las p´aginas distribuidas en la memoria cach´e o en la memoria general, con el objetivo de reducir el n´umero de fallos de p´agina. En otras palabras, se busca disminuir la cantidad de veces que se accede a la memoria general, ya que esto resulta ser m´as costoso. 3.1. Descripci´on Consideramos un sistema con memoria para mp´aginas y un espacio con capacidad kde memor´ıa r´apida (cach´e), donde k < m. Este problema modelar´a la capacidad de elecci´on del sistema para introducir las p´aginas en la memoria cach´e o no, para as´ı agilizar el procesador de nuestro sistema haciendo que no tenga que recurrir a la memoria general en gran cantidad de ocasiones, queremos minimizar el n´umero de veces que accedemos a la memoria principal. En la tabla 3.1 veremos una descripci´on formal del problema. 3.2. An´alisis competitivo Nuestro primer paso para realizar el an´alisis competitivo del problema de paginaci´on ser´a estudiar el algoritmo ´optimo offline. Si conociesemos la secuencia de p´aginas que vamos a consultar a lo largo del tiempo, podemos usar 13 14 CAP´ ITULO 3. EL PROBLEMA DE PAGINACI ´ ON Problema de paginaci´on Datos conocidos: Memoria general P={p1, . . . , pm}. Capacidad de la memoria cach´e k∈N. Cach´e Ccon contenido inicial C0⊂Ptal que |C0|=k. Datos online: Secuencia σ= (r1, . . . , rn)∈Pnde p´aginas a las que queremos acceder en orden. Posibles respuestas: Eliminar p´aginas de C (gratis). Cargar cualquier n´umero mi≤k− |C|de p´aginas de P\CaC(con coste). Al final de cada etapa idebemos tener ri∈C, es decir, ridebe estar incluida en C. Objetivo: Minimizar el coste total Pn i=1 ALGi(σ) = Pn i=1 mi. Tabla 3.1: Esquema explicativo del problema de paginaci´on de memoria. para el modelado del problema offline la estrategia LFD (longest-forward distance), que consiste en que en cada error de cach´e eliminemos de la memoria r´apida cualquier p´agina que no volver´a a ser solicitada o bien reemplacemos en la memoria cach´e la p´agina cuya proxima solicitud est´e m´as alejada. Por ejemplo, considerando la secuencia σ= (a, a, b, e, f, b, b, c, d, a, b) en la memoria general, tendremos almacenado en el cach´e C0={a, b, c, d}con k= 4. El primer error de cach´e (como llamaremos al momento en el que nuestro sistema no puede encontrar la p´agina en su memor´ıa de r´apido acceso) ser´a en r4=e, el LFD desaloja ay lo reemplaza por een la etapa 4. Teorema 3 LFD es un algoritmo offline de reemplazo de p´aginas ´optimo. Demostraci´on.- Procedemos por reducci´on al absurdo. Supongamos que el algoritmo LFD no es ´optimo, luego existe una secuencia finita σ= (r1, . . . , rn), para la cual no tenemos una soluci´on ´optima de nuestro problema. Sea OPT un algoritmo ´optimo que toma las mismas decisiones que LFD en σ≤i−1hasta que en la etapa idesaloja una p´agina diferente. Construimos OPT′[σ] de forma que se comporta de manera id´entica al LFD para σ≤i. N´otese que para etapas posteriores a idefiniremos OPT′seg´un el caso, de forma que OPT′sea ´optimo. Y si en alguno de los casos, OPT′(σ)<OPT(σ), habremos llegado a una contradicci´on. 3.2. AN ´ ALISIS COMPETITIVO 15 Sea pla p´agina desalojada por el LFD yp∗=pla p´agina desalojada por el algoritmo OPT, ambas en la etapa i. Definimos j∗=max{j∈ {1, . . . , n}: p∗/∈ {ri, ri+1, . . . , rj}}, es decir, j∗nos dar´a la ´ultima etapa consecutiva desde i en la que no se vuelve a solicitar la p´agina p∗, entonces rj+1 =p∗. Por definici´on del LFD sabremos que pno se solicita en {i, . . . , j∗}, pues si LDF desaloja en la etapa ila p´agina p, en vez de p∗, solo puede haber dos opciones: pno se vuelve a solicitar o p∗se solicita antes que p. Distinguimos 3 casos: Caso 1 Desalojamos pcon OPT en alguna etapa {i+ 1, . . . , j∗}. Dado que OPT es un algoritmo por demanda y pyp∗no son solicitadas en los pasos i+ 1, . . . , j, con jun paso intermedio entre i+ 1 y j∗, OPT[σ] no tiene ni a pni a p∗en su cach´e al final de la etapa j. Luego construiremos OPT′de manera que desloja pen la etapa i, desaloja p∗en la etapa jy en el resto de etapas copia las decisiones de OPT. De esta forma no a˜nadimos ning´un fallo de p´agina adicional y obtenemos OPT′(σ)≤OPT(σ), Llegando a la conclusi´on de que OPT′es un algoritmo ´optimo. A continuaci´on veamos en la figura 3.1 una representaci´on gr´afica para una mejor comprensi´on: ri. . . . . . rjrj∗ LFD OPT OPT′ ⇝p ⇝p∗ ⇝p ⇝p ⇝p∗mismo cach´e Figura 3.1: Representaci´on esquem´atica del caso 1 donde ⇝anos indica desalojar la p´agina a(Disser, 2023). Caso 2 No desalojamos pcon OPT en ninguna etapa {i, . . . , j∗} con j∗=n. Dado que pyp∗no se solicitan m´as despu´es de la etapa i, es decir no se vuelven a solicitar, no hay diferencias entre desalojar pop∗en dicha etapa. 22 CAP´ ITULO 3. EL PROBLEMA DE PAGINACI ´ ON 4for iin range (0,n) : 5if sigma [i] not in Cache : 6f+= 1 7Cache . pop (0) 8Cache . append ( sigma [i]) 9return f Algoritmo 3.2: Script del algoritmo FIFO en Python. FWF: En este caso inicializamos el cach´e como una lista vac´ıa, si rino est´a en el cach´e y este no est´a lleno lo a˜nadimos, mientras que si el cach´e est´a lleno lo vaciamos e introducimos dicho elemento. 1def FWF (sigma ,C_0 ,n,k): 2Cache = [] 3f=0 4for iin sigma : 5if inot in Cache : 6f +=1 7if len( Cache ) < k: 8Cache . append (i) 9else: 10 Cache = [] 11 Cache . append (i) 12 return f Algoritmo 3.3: Script del algoritmo FWF en Python. LFU: Este algoritmo sigue una estructura algo distinta al resto debido a su complejidad. En cada etapa i, si la p´agina rino est´a en el cach´e y el cach´e est´a lleno (no ser´ıa necesario comprobarlo pues estamos suponiendo que siempre partimos de un cach´e inicial lleno), eliminamos la p´agina que menos veces se ha solicitado en total hasta dicha etapa, y en caso de empate la que se solicit´o antes de estas. A˜nadimos un fallo de p´agina y redefinimos la frecuencia y la antiguedad de la p´agina solicitada. 1def LFU (sigma ,C_0 ,n,k): 2Cache = C_0 3f=0 4frecuencia = defaultdict(int) 5antiguedad = defaultdict(int) 3.3. ESTUDIO COMPUTACIONAL 23 6for i, pagina in enumerate ( sigma ): 7if pagina not in Cache : 8if len( Cache ) < k: 9Cache . append ( pagina ) 10 else: 11 lfu_pagina = min(Cache , key = lambda p: ( frecuencia [p], antiguedad [p ])) 12 # El minimo se decide primero segun el contador de frecuencia y si hay empate segun la pagina cargada en la etapa mas antigua 13 Cache . remove ( lfu_pagina ) 14 del frecuencia [ lfu_pagina ] 15 del antiguedad [ lfu_pagina ] 16 Cache . append ( pagina ) 17 f += 1 18 frecuencia [ pagina ] += 1 19 antiguedad [ pagina] = i 20 return f Algoritmo 3.4: Script del algoritmo LFU en Python. LIFO: En cada etapa icomprobamos si el elemento correspondiente est´a en el cach´e. En caso negativo a˜nadimos un fallo de p´agina y eliminamos la ´ultima p´agina a˜nadida. 1def LIFO (sigma ,C_0 ,n,k): 2Cache = C_0 3f=0 4for iin range (0,n) : 5if sigma [i] not in Cache : 6f+= 1 7Cache . pop (k -1) 8Cache . append ( sigma [i]) 9return f Algoritmo 3.5: Script del algoritmo LIFO en Python. LRU: Si riest´a en el cach´e la eliminamos y la volvemos a a˜nadir para que aparezca en la ´ultima posici´on de nuevo, mientras que si no est´a, eliminamos el primer elemento del cach´e y a˜nadimos el nuevo al final, de esta forma iremos conservando las p´aginas a las que se ha accedido m´as recientemente. 24 CAP´ ITULO 3. EL PROBLEMA DE PAGINACI ´ ON 1def LRU (sigma ,C_0 ,n,k): 2f=0 3Cache = C_0 4for iin range (0,n): 5if sigma [i] in Cache : 6Cache . remove ( sigma [i]) 7Cache . append ( sigma [i]) 8else: 9f += 1 10 Cache . pop (0) 11 Cache . append ( sigma [i]) 12 return f Algoritmo 3.6: Script del algoritmo LRU en Python. Estudio de competitividad sobre datos moderados Una vez tenemos todos los algoritmos programados, pasamos al an´alisis de sus funciones objetivo. Para ello vamos a generar vectores aleatorios con distintos par´ametros y distribuciones. De esta forma podremos comprobar emp´ıricamente la relaci´on entre las cotas en la pr´actica con las vistas en los resultados te´oricos sobre la competitividad de estos algoritmos y, adem´as, veremos que algunos funcionan mejor que otros en ciertas situaciones. Vamos a tomar 10 vectores que siguen una distribuci´on uniforme, es decir, todas las p´aginas tendr´an la misma probabilidad de ser solicitadas, para las siguientes combinaciones de par´ametros: seg´un el tama˜no del cach´e asociado, k∈ {4,10}; la longitud de σ,n∈ {50,100}; y el rango de las p´aginas, m=j·k,j= 2,3,4. Respecto a este ´ultimo par´ametro m, el tama˜no de la memoria total ser´ıa jveces mayor que la memoria que podemos guardar en cach´e. Por ejemplo, para j= 3, tendremos el triple de elementos que pueden ser requeridos de los que la memoria cach´e es capaz de almacenar. Esto nos genera un total de 120 vectores σpara nuestro estudio. Adem´as, generaremos otros 120 vectores de forma que la primera mitad de las p´aginas tengan el doble de probabilidad de ser requeridas que el resto (asim´etrica con peso 2). Bas´andonos en Dorrigiv, Ehmsen, y L´opez-Ortiz (2015) y resultados probados en la secci´on anterior, los algoritmos LFU yLIFO no tienen ratio competitivo constante mientras que FIFO,LRU son algoritmos estrictamente kcompetitivos y FWF es k-competitivo, es decir, puede haber un peque˜no desfase en los par´ametros de competitividad calculados debido a la constante 3.3. ESTUDIO COMPUTACIONAL 25 Tabla 3.2: Media de la ρ-competitividad de los algoritmos de paginaci´on. k n Distribuci´on mFIFO FWF LFU LIFO LRU 4 50 asim´etrica con peso 2 8 1,7731 2,8443 1,6503 1,4908 1,7779 12 1,6225 1,8932 1,5209 1,4486 1,5846 16 1,5511 1,7019 1,4876 1,4263 1,5197 uniforme 8 1,7489 2,4738 1,7525 1,7082 1,7161 12 1,5826 1,9275 1,5864 1,6452 1,5882 16 1,4489 1,7235 1,4981 1,4990 1,4726 100 asim´etrica con peso 2 8 1,8758 2,8569 1,6783 1,5062 1,7246 12 1,6416 2,0143 1,5875 1,4950 1,6205 16 1,5532 1,7316 1,5191 1,4313 1,5311 uniforme 8 1,7845 2,5163 1,8300 1,7097 1,7973 12 1,5706 1,9255 1,5929 1,5752 1,5839 16 1,4636 1,6922 1,4771 1,4901 1,4850 10 50 asim´etrica con peso 2 20 2,01394 3,2211 1,9922 1,5885 2,0462 30 1,8034 2,2312 1,8006 1,6586 1,7831 40 1,5900 1,8540 1,5697 1,4793 1,5847 uniforme 20 1,8496 2,7244 1,8266 1,8443 1,8092 30 1,6387 2,0062 1,5944 1,6521 1,6170 40 1,4799 1,7315 1,4837 1,5803 1,4806 100 asim´etrica con peso 2 20 2,1267 3,3264 2,0284 1,6600 2,0974 30 1,8657 2,2945 1,8059 1,6391 1,8063 40 1,6333 1,9400 1,6065 1,5082 1,6462 uniforme 20 1,9454 2,8307 1,8905 1,8621 1,9701 30 1,7015 2,0639 1,6289 1,6824 1,6814 40 1,5519 1,8155 1,5988 1,6003 1,5518 Resultado Total: 1,7007 1,8035 1,6670 1,5909 1,6865 aditiva. Los resultados obtenidos sobre el valor medio de la competitividad son los que aparecen en la tabla 3.2. Podemos ver como en promedio, para FIFO yLRU, los valores de competitividad son mucho mejores que k, que es su cota te´orica. Incluso para los otros algoritmos, los cuales no tienen asegurada una cota estricta o bien no tienen cota, tambi´en tienen un comportamiento emp´ırico bastante bueno. En la tabla 3.2, las celdas coloreadas en verde indican el menor valor del promedio de ρpara la fila de par´ametros correspondiente, es decir, el algoritmo m´as cercano al ´optimo. Por otro lado, las celdas coloreadas en rojo muestran el algoritmo menos competitivo. De esta manera, es f´acil observar que el algoritmo m´as eficiente para nuestros vectores aleatorios es LIFO, mientras que el peor, por unanimidad, es FWF. Recordemos que algunos de 26 CAP´ ITULO 3. EL PROBLEMA DE PAGINACI ´ ON estos algoritmos te´oricamente son (estrictamente) k-competitivos, por lo que es de destacar que emp´ıricamente est´en dando, en promedio, valores bastante menores que 4 y 10, respectivamente. Adem´as, la dispersi´on de los valores del algoritmo LIFO es una de las m´as bajas, ya que se encuentran comprendidos entre 1,4y1,8. En contraste, FWF presenta una dispersi´on m´as alta debido a su irregularidad en los datos. Intentemos comprender el por qu´e de estos resultados. El algoritmo FWF no es un algoritmo eficiente independientemente de la distribuci´on y las dimensiones del problema que estemos realizando pues no sigue ninguna estrategia, simplemente a˜nade la p´agina cuando se necesita y borra todo del cach´e cuando no caben m´as. Por otra parte, con el algoritmo LIFO podemos hacer un an´alisis m´as exhaustivo. Cuando la distribuci´on est´a ponderada podemos ver que LIFO es el m´as eficiente en todos los casos. Este suceso podr´ıamos explicarlo debido a la recurrencia de las primeras p´aginas, como su propio nombre indica “Last-In-First-Out”, elimina la ´ultima p´agina en entrar en el cach´e. Como las primeras p´aginas del rango tienen m´as probabilidad y partimos de C0 (cach´e inicial) con las primeras kp´aginas, es decir, C0= [1, . . . , k], los fallos de p´agina disminuir´an. Esto podemos verlo con m´as claridad cuando kes mayor, en los resultados para k= 10 vemos que los resultados del promedio de competitividad son muy parecidos para FIFO,LFU yLRU mientras que para LIFO disminuye significativamente. Usando este razonamiento, la competitividad de LIFO deber´ıa mejorar cuanto m´as aumentamos la probabilidad de recurrencia de los primeros valores del rango. Para ello, vamos a utilizar 60 nuevos vectores asim´etricos σ con pesos 4 y 6. Los resultados se muestran en la tabla 3.3. El an´alisis confirma que LIFO es el algoritmo m´as eficiente cuando las primeras p´aginas tienen una mayor probabilidad de ser requeridas, con distribuciones asim´etricas ponderadas. LFU, aunque competitivo en ciertos escenarios, no es tan consistentemente eficiente como LIFO. En una distribuci´on ponderada, las p´aginas con mayor peso son referenciadas m´as frecuentemente, lo que lleva a un buen desempe˜no de LFU. Sin embargo, LFU puede ser menos eficiente en escenarios donde la distribuci´on cambia r´apidamente, ya que no se adapta tan bien como LIFO a cambios en el patr´on de referencias.. Estos resultados apoyan la hip´otesis de que LIFO mejora su competitividad cuanto m´as aumentamos la probabilidad de recurrencia de los primeros valores del rango, haciendo de LIFO una excelente elecci´on en entornos con distribuciones asim´etricas. 3.3. ESTUDIO COMPUTACIONAL 27 Tabla 3.3: Media de la ρ-competitividad con vectores aleatorios asim´etricos. k n Distribuci´on mFIFO FWF LFU LIFO LRU 10 50 asim´etrico con peso 4 20 2,4200 4,1064 2,0918 1,7114 2,3734 30 1,7923 2,4087 1,7008 1,3851 1,7883 40 1,6208 2,0105 1,6505 1,2994 1,6846 asim´etrico con peso 6 20 2,7066 4,9777 2,2105 1,9479 2,3921 30 1,8113 2,6823 1,7989 1,5001 1,9220 40 1,7275 2,2172 1,7487 1,3929 1,7422 100 asim´etrico con peso 4 20 2,4810 3,8848 1,8857 2,1934 2,2896 30 1,9128 2,5048 1,7932 1,7086 1,8825 40 1,7418 2,1117 1,6539 1,5512 1,7488 asim´etrico con peso 6 20 2,8623 4,6142 1,7956 2,0634 2,3300 30 1,9979 2,7579 1,8134 1,7924 1,9409 40 1,7736 2,2568 1,6804 1,5490 1,7650 Resultado Total: 2,0707 3,0444 1,8186 1,6746 1,9883 A continuaci´on, veamos qu´e conclusiones podemos sacar acerca del resto de algoritmos compar´andolos entre ellos y descartando el mejor y el peor hasta el momento (LIFO yFWF). Visualizamos la tabla 3.4 para la cual hemos modificado la tabla 3.2 eliminando las columnas de los algoritmos LIFO yFWF y se˜nalando los nuevos mejores y peores resultados. A simple vista volvemos a tener un resultado ganador claro para los vectores aleatorios ponderados, el algoritmo LFU. Recordamos que este algoritmo realiza un recuento de las entradas que van llegando y elimina la menos solicitada. Luego tendr´a sentido que este algoritmo sea bastante eficaz debido de nuevo a la mayor probabilidad de que se soliciten ciertas p´aginas. Adem´as, nos fijamos en que a medida que aumenta m, es decir, hay m´as p´aginas que pueden ser solicitadas, mejora la competitividad. Esto se debe a que no estamos comparando los valores de la funci´on objetivo de cada algoritmo consigo mismo sino con el algortimo offline. El lector puede observar, por ejemplo, los casos k= 10, n = 100 y σasim´etrico con peso 2. Por ´ultimo, finalizamos nuestro an´alisis con la comparaci´on de los algoritmos FIFO yLRU. Apreciamos que son dos algoritmos bastante igualados a nivel de competitividad para el problema de paginaci´on. No obstante, en la literatura algunos autores consideran que LRU es “mejor” que FIFO (Chrobak y Noga, 1999; Hamkalo, 2010). Una raz´on para ello puede ser el hecho de que las secuencias de solicitudes t´ıpicas exhiben localidad de referencia, o dicho de otro modo, cada vez que se 28 CAP´ ITULO 3. EL PROBLEMA DE PAGINACI ´ ON Tabla 3.4: Media de la ρ-competitividad de los algoritmos de paginaci´on. k n Distribuci´on mFIFO LFU LRU 4 50 asim´etrica con peso 2 8 1,7730 1,6503 1,7779 12 1,6225 1,5209 1,5846 16 1,5511 1,4876 1,5197 uniforme 8 1,7489 1,7525 1,7161 12 1,5826 1,5864 1,5882 16 1,4489 1,4981 1,4726 100 asim´etrica con peso 2 8 1,8758 1,6783 1,7246 12 1,6416 1,5875 1,6205 16 1,5532 1,5191 1,5311 uniforme 8 1,7845 1,8300 1,7973 12 1,5706 1,5929 1,5839 16 1,4636 1,4771 1,4850 10 50 asim´etrica con peso 2 20 2,0139 1,9922 2,0462 30 1,8034 1,8006 1,7831 40 1,5900 1,5697 1,5847 uniforme 20 1,8496 1,8266 1,8092 30 1,6387 1,5944 1,6170 40 1,4799 1,4837 1,4806 100 asim´etrica con peso 2 20 2,1267 2,0284 2,0974 30 1,8657 1,8059 1,8063 40 1,6333 1,6065 1,6462 uniforme 20 1,9454 1,8905 1,9701 30 1,7015 1,6289 1,6814 40 1,5519 1,5988 1,5518 Resultado Total: 1,7007 1,6670 1,6865 solicita una p´agina es muy probable que la siguiente solicitud se elija de un peque˜no conjunto de p´aginas cercanas a esta. Parece que LRU aprovecha la localidad de manera m´as efectiva que FIFO pese a que el an´alisis competitivo te´orico no refleje esta superioridad. LRU tiende a tener mejor rendimiento que FIFO en la mayor´ıa de los casos, especialmente cuando hay una distribuci´on asim´etrica y una mayor cantidad de p´aginas disponibles (m). Esto se debe a que LRU es capaz de mantener en cach´e las p´aginas m´as recientemente utilizadas, reduciendo los fallos de p´agina en escenarios donde las p´aginas m´as recientes son m´as relevantes. FIFO puede superar a LRU en ciertos casos, especialmente con una distribuci´on uniforme y un menor n´umero de p´aginas, pero la ventaja no es significativa. En general, LRU es un algoritmo m´as competitivo que FIFO, ya que su adaptabilidad para mantener las p´aginas m´as relevantes en cach´e le permite manejar mejor diferentes patrones de acceso. 3.3. ESTUDIO COMPUTACIONAL 29 Estudio de competitividad sobre datos realistas Tras analizar el comportamiento de los algoritmos de paginaci´on FIFO, LRU,LFU,LIFO yFWF con un conjunto de datos de tama˜no moderado para facilitar su comprensi´on, entendemos que estos resultados, aunque ilustrativos, no capturan completamente la complejidad y las demandas de un entorno realista. En esta segunda parte del estudio, llevamos nuestro an´alisis a un escenario m´as realista y representativo de situaciones pr´acticas encontradas en sistemas inform´aticos actuales. Utilizaremos una configuraci´on con un mayor n´umero de p´aginas posibles, m´as etapas de acceso y una capacidad de cach´e significativa, pero a´un limitada en comparaci´on con el total de p´aginas disponibles. Este enfoque nos permitir´a observar c´omo los algoritmos de paginaci´on FIFO,LRU,LFU yLIFO (excluimos FWF) manejan patrones de acceso en condiciones similares a las de un entorno real de memoria virtual o gesti´on de cach´e en sistemas operativos y bases de datos. A trav´es de esta configuraci´on, evaluaremos el desempe˜no y la competitividad de estos algoritmos, proporcionando una visi´on m´as completa y aplicable de sus ventajas y limitaciones en la pr´actica. Adem´as, vamos a generar vectores siguiendo distribuciones que se asemejen m´as a la realidad con k = 30, n = 2000 y m = 100. Crearemos 50 instancias de cada uno de los siguientes tipos: Accesos vecinos: accesos aleatorios pero con una probabilidad mayor de acceder a p´aginas cercanas a la ´ultima accedida. Explosi´on: vectores con explosiones que son accesos intensivos a un subconjunto de 50 p´aginas en intervalos de 500 etapas. Asim´etrico: vectores ponderados con el doble de peso en la primera mitad. Secuencial: vectores con accesos en orden secuencial de 1 a 500 repetidos a lo largo de las 2000 etapas. Uniforme: sigue la distribuci´on uniforme tal y como se explic´o en el estudio anterior. Veamos qu´e algoritmo funciona mejor con cada distribuci´on analizando los resultados resumidos en la tabla 3.5 por filas. En el an´alisis, se observa 30 CAP´ ITULO 3. EL PROBLEMA DE PAGINACI ´ ON Tabla 3.5: Media de la ρ-competitividad. Distribuci´on FIFO LFU LIFO LRU accesos vecinos 1,8552 1,9743 2,0402 1,8464 explosi´on 1,8818 1,8763 1,8781 1,8816 asim´etrico 1,9431 1,8577 1,7250 1,9285 secuencial 1,4071 1,4071 1,0136 1,4071 uniforme 1,8823 1,8824 1,8880 1,8833 Resultado Total: 1,7939 1,7996 1,7090 1,7894 que para la distribuci´on de accesos vecinos, el algoritmo LIFO es el menos eficiente. Esto se debe a que en esta distribuci´on no existe un patr´on repetitivo que contenga algunos de los primeros elementos, ni una mayor probabilidad de que estos aparezcan con m´as frecuencia. Por el contrario, LRU es el m´as eficiente debido a su capacidad para aprovechar la localidad temporal de las solicitudes consecutivas. Para los vectores con explosiones de un conjunto de datos, FIFO resulta ser el peor algoritmo, mientras que LFU es el m´as efectivo. Este resultado es l´ogico, ya que la frecuencia de los elementos del conjunto correspondiente a cada explosi´on aumentar´a durante las 500 etapas que dura la secuencia, mejorando as´ı las predicciones de las p´aginas solicitadas a medida que avanza el tiempo. En la distribuci´on asim´etrica, LIFO se presenta como el algoritmo m´as adecuado, mientras que FIFO es el menos eficiente. Este comportamiento se asemeja al observado en la distribuci´on de accesos vecinos, donde FIFO tambi´en mostr´o un desempe˜no deficiente. Para la distribuci´on secuencial, LIFO se destaca notablemente como el algoritmo que toma las mejores decisiones debido a la repetici´on sucesiva de p´aginas. En cambio, en la distribuci´on uniforme, FIFO yLRU muestran rendimientos muy similares, y LIFO obtiene los peores resultados, posiblemente debido a que su estrategia de descarte no se adapta bien a la uniformidad de los accesos. Por ´ultimo, tambi´en podemos estudiar cu´al es la distribuci´on que se amolda mejor a cada algoritmo haciendo un an´alisis por columnas de la tabla 3.5. Se observa que la distribuci´on secuencial es la que mejor se adapta a todos los algoritmos debido a su patr´on de repetici´on claro. Sin embargo, esta distribuci´on es demasiado artificial para ocurrir repetidamente en entornos realistas. Ser´a ´util en casos espec´ıficos, como cuando se accede a las mismas 3.3. ESTUDIO COMPUTACIONAL 31 p´aginas durante d´ıas consecutivos, pero no deber´ıa ser la base para elegir un algoritmo para un sistema donde la distribuci´on m´as frecuente sea diferente. FIFO obtiene sus peores resultados con la distribuci´on asim´etrica y los mejores con la distribuci´on de accesos vecinos. Este resultado es l´ogico, ya que al eliminar del cach´e el elemento que lleva m´as tiempo, si los elementos vecinos aparecen en etapas cercanas, tienen m´as probabilidad de seguir en el cach´e cuando sean requeridos. En el caso de LFU, el peor resultado se observa en la distribuci´on de accesos vecinos, donde las frecuencias de los elementos se mantendr´an uniformes. Por otro lado, el rendimiento m´as eficiente se logra con la distribuci´on asim´etrica, ya que los elementos con mayor frecuencia tienen m´as probabilidad de aparecer. El algoritmo LIFO se adapta bastante bien a las distribuciones asim´etricas, reforzando el resultado obtenido en estudios previos, mientras que muestra los peores resultados para la distribuci´on de accesos vecinos debido a los accesos a p´aginas superiores a k. Por ´ultimo, para el algoritmo LRU, la distribuci´on que mejor se adapta es la de accesos vecinos, aprovechando la localidad temporal, y la menos adecuada es la asim´etrica, donde la predictibilidad de los accesos disminuye considerablemente. La baja eficacia de los algoritmos LFU yLIFO con la distribuci´on de solicitudes vecinas puede atribuirse a que estos algoritmos no retienen en el cach´e las solicitudes m´as recientes. En contraste, FIFO yLRU s´ı mantienen las solicitudes recientes en el cach´e, lo que resulta en un mejor rendimiento para estos algoritmos bajo dicha distribuci´on. Adem´as, se observa que las distribuciones uniforme y con explosiones presentan par´ametros de competitividad estables entre todos los algoritmos analizados. Por lo tanto, este estudio computacional nos permite determinar el algoritmo de paginaci´on m´as adecuado para estructurar un sistema de memoria con dos niveles (memoria cach´e y memoria general). Al analizar el rendimien- to de diferentes algoritmos en diversas distribuciones de solicitudes, podemos identificar cu´al es el m´as eficiente para las secuencias de accesos esperadas en un entorno real. Esto permitir´a optimizar el uso de la memoria cach´e y mejorar el rendimiento global del sistema. 38 CAP´ ITULO 4. PROBLEMA DE ACTUALIZACI ´ ON DE UNA LISTA s∗ ique ser´a el n´umero de elementos que hay delante de ri, respectivamente, en cada lista al comienzo de cada etapa. Adem´as p∗ ies el n´umero de trasposiciones pagadas del algoritmo OPT en el paso i, que lo conocemos pues el algoritmo ´optimo es un algoritmo offline. Entonces OPTi(σ) = s∗ i+p∗ i, y como MFT no usa respuestas pagadas pues su ´unica respuesta es mover el elemento solicitado, tendremos que MTFi(σ) = si. Ahora definimos una funci´on potencial que al final de la etapa ialmacene una cantidad suficiente como para pagar las etapas en las que OPT es significativamente m´as barato que MTF: Φi(σ) := |{(x, y)∈X2:xantes que yen Lipero yantes que xen L∗ i}|. Es decir, la cantidad de elementos de Xque se encuentran invertidos entre las dos listas, uno antes que el otro y viceversa. Observamos que Φi(σ)≥Φ0(σ) = 0, pues las listas iniciales las consideramos identicas para ambos algoritmos Queda por demostrar que esta funci´on potencial cumple su objetivo, es decir, que MTF no paga demasiado en atapas baratas y tiene suficiente potencial para pagar etapas costosas. Para determinar el coste amortizado ai(σ), necesitamos calcular la diferencia de potencial ∆Φi(σ) := Φi(σ)−Φi−1(σ) en cada paso i. Para ello, utilizamos el enfoque de movimientos alternos (corolario 3), donde asumimos que MTF se mueve primero y OPT despu´es. Esto resulta en un valor de potencial intermedio de: Φ′ i(σ) := |{(x, y)∈X2:xantes que yen Lipero yantes que xen L∗i−1}| despu´es del movimiento de MTF pero antes del movimiento de OPT. Luego podemos calcular por separado ∆ΦMTF i(σ) := Φ′ i(σ)−Φi−1(σ) ∆ΦOPT i(σ) := Φi(σ)−Φ′ i(σ) para obtener ∆Φi(σ) = ∆ΦMTF i(σ) + ∆ΦOPT i(σ). Sea Xiel conjunto de elementos que est´an delante de rien Li−1, pero detr´as de rien L∗ i−1. Dado que MTF mueve rial frente en Li, entonces a la funci´on potencial intermedia solo puede introducir pares invertidos adicionales que estaban delante de rien Li−1pero no pertenecen al conjunto Xi, pues esos ya estaban incluidos al comienzo de la etapa. El n´umero de estos 4.2. AN ´ ALISIS COMPETITIVO 39 elementos es exactamente si− |Xi|y, por definici´on, debe ser como m´aximo s∗ i, por lo tanto, obtenemos si− |Xi| ≤ s∗ i. Por otro lado, todos los pares invertidos entre riy los elementos en Xiya no lo ser´an tras ejecutar el algoritmo MFT pues movemos rial frente en Liy ya no tendr´a elementos delante. Por lo tanto, consideramos el cambio en el potencial causado por MTF, ∆ΦMTF i(σ) = si−2|Xi|. Ahora consideremos la acci´on de OPT en la etapa i, despu´es de que MTF ya haya movido rial frente de su lista. Si OPT mueve rihacia adelante, esto garantiza disminuir el n´umero de pares invertidos, ya que riest´a al frente en la lista de MTF. Sin embargo, cada trasposici´on (acci´on pagada) puede aumentarlo en como m´aximo uno. El cambio en el potencial debido a las decisiones de OPT est´a, por lo tanto, acotado por ∆ΦOPT i(σ)≤p∗ i. Obtenemos: ∆Φi(σ) = ∆ΦMTF i(σ) + ∆ΦOPT i(σ)≤si−2|Xi|+p∗ i. Para el coste amortizado, esto implica ai(σ) = MTFi(σ) + ∆Φi(σ) ≤si+si−2|Xi|+p∗ i ≤2s∗ i+p∗ i ≤2·OPTi(σ). Entonces podemos aplicar inmediatamente el Lema 2 con α=β= 0 para obtener que MTF es estrictamente 2-competitivo. Es decir, MTF no requiere m´as del doble de operaciones que la mejor soluci´on offline que conoce el orden en el que se solicitar´an los elementos con antelaci´on. □ 40 CAP´ ITULO 4. PROBLEMA DE ACTUALIZACI ´ ON DE UNA LISTA 4.2.2. M´etodo del promedio Por ´ultimo, vamos a introducir otro m´etodo para estudiar la competitividad de problemas de optimizaci´on online, el m´etodo del promedio. Ahora que tenemos un l´ımite superior del ratio competitivo del problema de actualizaci´on de una lista con el algoritmo MTF, es natural preguntarse si existen mejores algoritmos que el ya mencionado. Es decir, por la definici´on de competitividad de un problema buscamos un l´ımite inferior en el ratio competitivo ALG(σ) OPT(σ)para el problema de actualizaci´on de listas. Primero obtendremos un l´ımite superior general en el coste del ´optimo offline y luego construiremos la secuencia m´as desfavorable para cualquier algoritmo online dado y as´ı llegar a un l´ımite inferior. Usaremos el m´etodo del promedio: una t´ecnica eficaz que se utiliza a menudo para obtener l´ımites superiores en el coste de las soluciones ´optimas. La idea general es la siguiente: 1. Introducir una clase uniforme Ade algoritmos offline con una estructura simple. 2. Para cualquier secuencia de solicitudes σdada, calcular el coste promedio cavg sobre todos los algoritmos en A. Este promedio idealmente deber´ıa ser independiente de σ, ya que elegimos una clase uniforme de algoritmos, y deber´ıa ser f´acil de calcular, ya que elegimos una estructura simple para todos ellos. 3. Usar el hecho de que existe al menos un algoritmo ALG ∈ A con ALG(σ)≤cavg y que OPT(σ)≤ALG(σ) para obtener el l´ımite OPT(σ)≤ cavg. Vamos a aplicar esta t´ecnica al problema de actualizaci´on de listas para obtener un l´ımite superior en OPT(σ), seguidamente acotar ALG(σ) OPT(σ)y llegar al resultado de que el problema de actualizaci´on de una lista tiene ratio competitivo estricto 2. Lema 3 El ´optimo offline para el problema de actualizaci´on de listas est´a acotado por OPT(σ)≤n·l−1 2+αpara todo σ∈Σyαfijo (α:= α(l)∈N). Demostraci´on.- Consideramos la clase simple y uniforme de todos los algoritmos que ordenan la lista en una de las l! posibilidades que usan trasposiciones en la 4.2. AN ´ ALISIS COMPETITIVO 41 primera etapa, y luego nunca cambian el orden nuevamente. Por definici´on, existen l! algoritmos en esta clase. El coste m´aximo en la etapa 1 sobre todos estos algoritmos es l 2=l(l−1) 2, por lo tanto, el coste de configuraci´on promedio α(l)<l(l−1) 2solo depende del n´umero lde elementos en la lista. Como segundo paso de la t´ecnica del promedio, calculamos el coste promedio cavg sobre todos los l! algoritmos para cualquier entrada σ= (r1, . . . , rn). En cada paso i, hay exactamente (l−1)! algoritmos que tienen rien la posici´on j, para cada j∈ {1, . . . , l}. El coste promedio cavg,i del paso i≥2 sobre todos los algoritmos en nuestra clase es por lo tanto cavg,i =1 l! l X j=1 (j−1)(l−1)! = (l−1)! l!·l(l−1) 2=l−1 2. Observese que elegimos nuestra clase de algoritmos de tal manera que cavg,i es independiente tanto de icomo de σy es f´acil de calcular. Para acotar el coste de OPT ahora solo queda calcular cavg, ya que al menos un algoritmo de nuestra clase no supera el coste promedio y, por lo tanto, tampoco lo hace OPT. Obtenemos OPT(σ)≤cavg =α(l) + n X i=2 cavg,i = (n−1) ·l−1 2+α(l) = n·l−1 2+α′(l), donde α′(l) = α(l)−l−1 2, es decir, una constante. □ Teorema 7 Todo algoritmo para el problema de actualizaci´on de listas tiene un ratio competitivo de al menos 2. Demostraci´on.- Fijamos un algoritmo online ALG. Una secuencia de solicitudes trivial que podemos pensar cuando queremos ponernos en el peor de los casos es la instancia que siempre solicita el ´ultimo elemento en la lista de ALG, es decir, riser´a el ´ultimo elemento de la lista Li−1, lo que fuerza un coste total de ALG(σ)≥n(l−1) n→∞ −−−→ ∞ (m´as de n(l−1) si ALG usa trasposiciones). Gracias a esto, junto con el Lema 3, llegamos a que ALG(σ) OPT(σ)≥n(l−1) n(l−1) 2+α(l)=2(l−1) (l−1) + 2α(l) n −−−→ n→∞ 2. 42 CAP´ ITULO 4. PROBLEMA DE ACTUALIZACI ´ ON DE UNA LISTA Por la Proposici´on 1 y dado que ALG fue elegido arbitrariamente obtenemos el resultado. □ Corolario 4 El problema de actualizaci´on de listas tiene ratio competitivo estricto 2. En conclusi´on, validando la eficiencia de los algoritmos presentados mediante el uso del m´etodo de la funci´on potencial y el m´etodo del promedio hemos hallado el ratio competitivo de nuestro problema. Pasaremos ahora a explorar el problema k-servidores, un problema muy estudiado dentro de los sistemas de tareas m´etricas, que tambi´en definiremos. Cap´ıtulo 5 Problema k-servidores En el ´ambito de la optimizaci´on online, uno de los problemas m´as estudiados es el problema de kservidores, junto con su versi´on general, conocida como problemas de tareas m´etricas. Estos plantean algunos problemas abiertos pese a haber sido objeto de muchas investigaciones debido a su relevancia en m´ultiples aplicaciones pr´acticas (v´ease Fiat y Mendel, 2003; Manasse, Mc- Geoch, y Sleator, 1988). 5.1. Sistemas de tareas m´etricas Los sistemas de tareas m´etricas son problemas dise˜nados para optimizar la planificaci´on y ejecuci´on de una lista de tareas, cada una con sus correspondientes costes. En estos sistemas, cada tarea est´a asociada con un cierto peso o m´etrica de transici´on entre estados y un coste de respuesta a cada tarea en un estado determinado. Hasta ahora, todos los problemas que hemos visto comparten la caracter´ıstica de que el sistema subyacente (como el cach´e o la lista) se encuentra en alg´un estado espec´ıfico despu´es de cada paso, y el coste en cada paso est´a determinado ´unicamente por la solicitud m´as reciente, el estado actual del sistema (por ejemplo, la posici´on de un elemento en la lista), y c´omo cambia ese estado en el paso actual (por ejemplo, cu´antas trasposiciones son necesarias para cambiar el orden de la lista). Sin embargo, en contraposici´on, en este caso el coste en cada paso puede depender de manera compleja de las acciones y solicitudes anteriores. Para comprender esta estructura, definimos formalmente un sistema de tareas m´etricas, que incluye la condici´on 43 44 CAP´ ITULO 5. PROBLEMA k-SERVIDORES de que los costes asociados con las transiciones de estado deben cumplir las propiedades de una m´etrica (v´ease Manasse et al., 1988). Sistemas de tareas m´etricas Datos conocidos: Un espacio m´etrico (S, d) donde Ses el conjunto de estados con Nelementos y duna distancia. Un conjunto Rcon cardinal |R|=mde las posibles tareas que se pueden solicitar. Una matriz de costes C∈RN×m, que nos dar´a el precio de realizar la tarea ridesde el estado si, donde iser´a la etapa en la que nos encontremos. Estado inicial s0∈S. Datos online: Secuencia de solicitudes σ= (r1, . . . , rn)∈Rn, tareas solicitadas en orden. Posibles respuestas: En la etapa i, tomar la decisi´on de pasar del estado si−1asiy en este estado llevar a cabo la tarea ri requerida. El coste de transici´on de estados es d(si−1, si) mientras que el coste por realizar la tarea es C(si, ri). Objetivo: Minimizar el coste total Pn i=1 ALGi(σ) = Pn i=1 d(si−1, si) + C(si, ri). Tabla 5.1: Esquema explicativo de los sistemas de tareas m´etricas. Por lo tanto, un algoritmo de planificaci´on para (S, d) es una funci´on ALG que asocia a cada secuencia de tareas σun coste ALG(σ). Veamos un anal´ısis de competitividad de nuestro problema bas´andonos en resultados de Borodin, Linial, y Saks (1992). Teorema 8 Cualquier sistema de tareas m´etricas (S, d)con Nestados tiene un ratio competitivo menor que (2N−1). Demostraci´on.- Para hallar una cota inferior sobre el mejor ratio competitivo posible para cualquier sistema de tareas m´etricas (S, d) de tama˜no N > 1, como siempre necesitamos adoptar la perspectiva de la peor secuencia posible solicitada. Un candidato obvio para ello ser´a σ= (r1, . . . , rn) para un algoritmo dado 5.1. SISTEMAS DE TAREAS M ´ ETRICAS 45 ALG que presenta tareas de manera que ALG se encuentre en el peor estado posible para cada tarea. Introduciendo un par´ametro ε > 0, podemos lograr esto estableciendo la siguiente definici´on de la matriz de costes: C(s, ri) = ε, si s=si−1, 0, c.c. Es decir, tendremos coste si el estado no var´ıa del principio al final de la etapa i. Supongamos que ALG cambia su estado n′≤nveces en total, y tomamos , si1, ..., sin′, (s0=si0) los estados a los que ALG hace transici´on, en este orden. Entonces, ALG(σ) = (n−n′)ε+ n′ X j=1 d(sij−1, sij).(5.1) Se observa que, debido a la positividad de dyε, tenemos que l´ımn→∞ ALG(σ) = ∞. Si l´ımn→∞ OPT(σ) est´a acotado, entonces ALG tiene una raz´on competitiva no acotada. Por lo tanto, en lo siguiente, vamos a asumir que l´ımn→∞ OPT(σ) = ∞. Ahora vamos a obtener un l´ımite superior del coste de OPT utilizando la t´ecnica del promedio. Utilizamos una clase de algoritmos Aque depende del comportamiento de ALG. Espec´ıficamente, Aconsiste en (2N−1) algoritmos, de modo que, despu´es de cada paso, exactamente 2 algoritmos de Aest´an en cada estado no ocupado por ALG y exactamente 1 algoritmo est´a en el mismo estado que ALG, mientras que como m´aximo un algoritmo en Acambia de estado en cada paso. Observe que podemos lograr esto cambiando un algoritmo de estado sia estado si−1siempre que ALG haga la transici´on de si−1asi. Sea B0=B0(S, d)>0 el coste total (constante) de configuraci´on requerido en la etapa 1 para distribuir los algoritmos en Asobre los estados iniciales seg´un el sistema que acabamos de describir. Para calcular el coste promedio cavg(σ) de los algoritmos en A, tengamos en cuenta que los algoritmos en el estado si−1despu´es del paso itienen un coste no nulo ε, por (5.1), mientras que todos los dem´as algoritmos tienen un coste de 0. Si ALG cambia de estado lejos de si−1en el paso i, dos algoritmos en Atienen un coste de ε. De lo contrario, solo un algoritmo tiene un coste de ε. Adem´as, cada vez que ALG hace transiciones entre estados, tambi´en lo hace un solo algoritmo en A; de lo contrario, no hay transiciones de estado. 46 CAP´ ITULO 5. PROBLEMA k-SERVIDORES Dado que ALG hace exactamente n′transiciones entre estados, obtenemos cavg(σ) = 1 2N−1h(n−n′)ε+ n′ X j=1 d(sij, sij−1)+2n′ε+B0i. Por lo tanto, OPT(σ)≤cavg(σ) = ALG(σ)+2n′ε+B0 2N−1. Adem´as, sabemos que ALG(σ)≥Pn′ j=1 d(sij−1, sij)≥n′dmin, luego 2ε dmin + 1·ALG(σ)≥2n′ε+ALG(σ)≥(2N−1) ·OPT(σ)−B0. Finalmente, por la proposici´on 1, podemos probar que el ratio competitivo de nuestro problema no va a mejorar (2N−1) pues ALG(σ) OPT(σ)≥2N−1 2ε dmin + 1−B0 (2ε dmin + 1) ·OPT(σ)−−→ ε→0(2N−1)−B0 OPT(σ)−−−→ n→∞ 2N−1. □ Ahora podemos ver un caso concreto de los sistemas de tareas m´etricas como es el problema k-servidores. 5.2. Problema k-servidores El problema k-servidores en un espacio m´etrico (o grafo ponderado) es el problema de mover eficientemente kservidores para atender solicitudes que aparecen en tiempo real en los puntos de dicho espacio m´etrico. Los kservidores comienzan en un conjunto fijo de kpuntos, S0, que ser´a la configuraci´on inicial. Luego, en cada etapa i, aparece una solicitud en alg´un punto del espacio m´etrico y alg´un servidor debe moverse a ese punto para atender la solicitud. Suponemos que las solicitudes aparecen secuencialmente y que una nueva solicitud aparece solo despu´es de que se haya atendido la solicitud actual. El objetivo es minimizar la distancia total recorrida por los servidores (Koutsoupias, 2009). 5.2. PROBLEMA k-SERVIDORES 47 Podemos ver este problema como una particularizaci´on de los sistemas de tareas m´etricas. Tendr´ıamos que el conjunto de estados ser´an las posibles localizaciones de cada uno de los servidores y su coste asociado solo permite distinguir entre estados posibles y prohibidos (coste 0 o ∞). Por tanto, la matriz de costes Cen estos casos particulares no aportar´a ning´un valor pues solo moveremos los servidores entre estados permitidos. Como en cap´ıtulos anteriores, veamos una descripci´on formal del problema k-servidores en la tabla 5.2. Problema de k-servidores Datos conocidos: Un espacio m´etrico (P, d) donde Pes un conjunto de puntos con cardinal Nyduna distancia. Vector de localizaciones iniciales de los servidores S0= (S0,1, . . . , S0,k)∈Pk. Datos online: Secuencia de solicitudes σ= (r1, . . . , rn)∈Pn, es decir, los puntos a los que queremos acceder. Posibles respuestas: En la etapa i, para cada j∈ {1, . . . , k}, mover el servidor ja la posici´on Si,j que tendr´a un coste de d(Si−1,j, Si,j), luego, al principio de la etapa i el servidor jestar´a en la posici´on Si−1,j y al final en la Si,j. Objetivo: Minimizar el coste total Pn i=1 ALGi(σ) = Pn i=1 Pk j=1 d(Si−1,j, Si,j). Tabla 5.2: Esquema explicativo del problema de k-servidores. Vamos a restringir la soluci´on de nuestro problema a algoritmos perezosos. Llamaremos a un algoritmo perezoso cuando mueve un solo servidor para manejar cada solicitud en un v´ertice no ocupado, pero no mueve servidores de otra manera. El siguiente lema muestra que podemos restringir nuestra atenci´on a dichos algoritmos. Lema 4 (Manasse et al. (1988)) Para cualquier algoritmo ALG, podemos encontrar un algoritmo modificado ALG′que es perezoso, no aumenta el coste y es online si ALG lo es. 54 CAP´ ITULO 6. CONCLUSIONES el m´etodo de la funci´on potencial previamente explicado. Adem´as, desarrollamos un m´etodo para estudiar la competitividad de problemas online, el m´etodo del promedio. Gracias a estos resultados se ha llegado a la conclu- si´on de que el problema de actualizaci´on de una lista tiene ratio competitivo estricto 2. Por ´ultimo, hemos estudiado el problema de k-servidores, explicando primero su versi´on m´as general, los sistemas de tareas m´etricas, y acotando superiormente el ratio de estos por (2N−1). A continuaci´on se ha realizado el an´alisis competitivo del problema de k-servidores. Este problema tiene una cuesti´on abierta, ya que se intuye que existe un algoritmo k-competitivo para este problema, aunque sin embargo, no se ha podido demostrar, a nuestro mejor entendimiento. ´ Unicamente se ha probado para k=N−1 usando el algoritmo BAL y, en el caso k= 2, en otros estudios. En conjunto, el trabajo subraya la importancia de la optimizaci´on online como herramienta para la toma de decisiones en tiempo real. Los diferentes algoritmos estudiados ofrecen soluciones efectivas para distintos tipos de problemas, demostrando que, aunque no existe un ´unico enfoque que sea ´optimo para todos los casos, la adaptaci´on y la selecci´on del algoritmo adecuado seg´un el contexto son cruciales para maximizar la eficiencia y minimizar los costes. Referencias Amb¨uhl, C. (2002). On the list update problem (Tesis Doctoral, ETH Zurich). doi:https://doi.org/10.3929/ETHZ-A-004394113 Bein, W. W., Chrobak, M., y Larmore, L. L. (2002). The 3-server problem in the plane. Theoretical Computer Science,289(1), 335-354. doi:https://doi.org/10.1016/S0304-3975(01)00305-X Ben-Tal, A., El Ghaoui, L., y Nemirovski, A. (2009). Robust optimization (Vol. 28). Princeton University Press. doi:https://doi.org/10.1515/9781400831050 Ben-Tal, A., y Nemirovski, A. (2002). Robust optimization – methodology and applications (Vol. 92). Springer. doi:https://doi.org/10.1007/s101070100286 Beyer, H.-G., y Sendhoff, B. (2007). Robust optimization – a comprehensi- ve survey. Computer Methods in Applied Mechanics and Engineering, 196(33), 3190-3218. doi:https://doi.org/10.1016/j.cma.2007.03.003 Birge, J. R., y Louveaux, F. (2011). Introduction to stochastic programming. Springer Science & Business Media. Borodin, A., Linial, N., y Saks, M. E. (1992). An optimal on-line algorithm for metrical task system. Journal of the ACM (JACM),39(4), 745–763. doi:https://doi.org/10.1145/146585.146588 Chrobak, M., Larmore, L. L., Reingold, N., y Westbrook, J. (1997). Page migration algorithms using work functions. Journal of Algorithms, 24(1), 124-157. doi:https://doi.org/10.1006/jagm.1996.0853 Chrobak, M., y Noga, J. (1999). LRU is better than FIFO. Algorithmica, 23, 180–185. doi:https://doi.org/10.1007/PL00009255 Cook, S. A. (1971). The complexity of theorem proving procedures. En Proceedings of the Third Annual ACM Symposium (pp. 151–158). New York. doi:https://doi.org/10.1145/800157.805047 Disser, Y. (2023). Online optimization (Inf. T´ec.). Darms- 55 56 REFERENCIAS tadt: Technische Universit¨at Darmstadt. Descargado de https://www2.mathematik.tu-darmstadt.de/~disser/pdfs/ scripts/OnlineOptimization.pdf (Lecture notes, summer term) Dorrigiv, R., Ehmsen, M. R., y L´opez-Ortiz, A. (2015). Parameterized analysis of paging and list update algorithms. Algorithmica,71, 330–353. doi:https://doi.org/10.1007/s00453-013-9800-5 Fiat, A., y Mendel, M. (2003). Better algorithms for unfair metrical task systems and applications. SIAM Journal on Computing,32(6), 1403- 1422. doi:https://doi.org/10.1137/S0097539700376159 Gorissen, B. L., ˙ Ihsan Yanıko˘glu, y den Hertog, D. (2015). A practical guide to robust optimization. Omega,53, 124-137. doi:https://doi.org/10.1016/j.omega.2014.12.006 Hamkalo, B., Jos´e L. ; Cernuschi-Frias. (2010). An´alisis de una pol´ıtica de reemplazo basada en las distancias de pila LRU. En Cisci 2010. Descargado de https://www.iiis.org/CDs2010/CD2010CSC/ CISCI 2010/PapersPdf/CA424IT.pdf Irani, S. (1991). Two results on the list update problem. Information Processing Letters,38(6), 301–306. doi:https://doi.org/10.1016/0020- 0190(91)90086-W Jaillet, P., y Wagner, M. R. (2014). Online optimization—an introduction. En Risk and optimization in an uncertain world (pp. 142–152). INFORMS TutORials in Operations Research. doi:https://doi.org/10.1287/educ.1100.0072 Karlin, A. R., Manasse, M. S., Rudolph, L., y Sleator, D. D. (1988). Competitive snoopy caching. Algorithmica,3, 79–119. doi:https://doi.org/10.1007/BF01762111 Karp, R. (1972). Reducibility among combinatorial problems. En R. Miller y J. Thatcher (Eds.), Complexity of computer computations (pp. 85–103). Plenum Press. doi:https://doi.org/10.1007/978-1-4684-2001-2 9 Koutsoupias, E. (2009). The k-server problem. Computer Science Review, 3(2), 105–118. doi:https://doi.org/10.1016/j.cosrev.2009.04.002 Krumke, S. (2002). Online optimization: Competitive analysis and beyond (n.o02-25). Descargado de https://nbn-resolving.org/urn:nbn: de:0297-zib-6925 Manasse, M., McGeoch, L., y Sleator, D. (1988). Competitive algorithms for on-line problems. En Proceedings of the twentieth annual acm symposium on theory of computing (pp. 322–333). doi:https://doi.org/10.1145/62212.62243 REFERENCIAS 57 Manasse, M., McGeoch, L., y Sleator, D. (1990). Competitive algorithms for server problems. Journal of Algorithms, 208-230. doi:https://doi.org/10.1016/0196-6774(90)90003-W Newell, A., y Shaw, J. C. (1957). Programming the logic theory machine. En Papers presented at the february 26-28, 1957, western joint computer conference: Techniques for reliability (pp. 230–240). doi:https://doi.org/10.1145/1455567.1455606 Pr´ekopa, A. (2013). Stochastic programming (Vol. 324). Springer Science & Business Media. doi:https://doi.org/10.1007/978-94-017-3087-7 Robinson, J. J. (1949). On the hamiltonian game (a Traveling Salesman Problem) (Inf. T´ec.). Santa Monica, CA: The RAND Corporation. Descargado de https://www.rand.org/pubs/research memoranda/ RM303.html Schneider, J., y Kirkpatrick, S. (2007). Stochastic optimization. Springer Science & Business Media. doi:http://dx.doi.org/10.1007/978-3-540- 34560-2 Sleator, D. D., y Tarjan, R. E. (1985). Amortized efficiency of list update and paging rules. Communications of the ACM ,28(2), 202–208. doi:https://doi.org/10.1145/2786.2793 Winston, W. (1991). Operations research: Applications and algorithms. PWS-Kent Publishing Company.