Búsqueda Tabú No Obvia con Antipodales: Una Nueva Propuesta para el Problema MaxSAT - Prof, Apuntes de Estadística

¡Descarga Búsqueda Tabú No Obvia con Antipodales: Una Nueva Propuesta para el Problema MaxSAT - Prof y más Apuntes en PDF de Estadística solo en Docsity! Benemérita Universidad Autónoma de Puebla Facultad de Ciencias de la Computación Maestría en Ciencias de la Computación Determinación de Eficiencia y Factor de Garantía de un Algoritmo Basado en Búsqueda Local para el Tratamiento del Problema MaxSAT Tesis que para obtener el grado de Maestro en Ciencias de la Computación presenta: David Eduardo Pinto Avendaño Asesor: Dr. Guillermo De Ita Luna Con todo mi amor para mi querida esposa... Sofía. Tú que en todo momento has apoyado cada uno de mis pasos y me has hecho ser lo que ahora soy, porque sin ti, definitivamente no lo hubiese logrado. A mis padres y hermanos... Celso Pinto, Isabel Avendaño y Celso, Alejandro y Mauricio Ya que siempre me han alentado a terminar mis metas. A mi tía Fanny... Fundamento principal de mi carrera profesional. A mi asesor... Dr. Guillermo De Ita Luna Por todo el apoyo recibido y el conocimiento transmitido de manera desinteresada. 1 Introducción La aparición de una gran cantidad de problemas en los últimos años que han demostrado estar dentro de la categoría de problemas denominados NP (los cuales son reconocidos por requerir de una gran cantidad de recursos y tiempo para que su resolución se cumpla) ha motivado el buscar algoritmos eficientes para su resolución; sin embargo, a menos que P = NP, no habrá algoritmos de tiempo polinomial para solucionar tales problemas. En este trabajo se presentan diversas heurísticas para resolver eficientemente, aunque de manera aproximada dos problemas clásicos NP-Completos: SAT y MaxSAT. SAT y MaxSAT son dos problemas cruciales para el desarrollo de la demostración automática de teoremas (DAT) en el cálculo proposicional, su planteamiento puede resumirse en la forma siguiente: Dada una fórmula booleana F en forma normal conjuntiva (FNC), el problema SAT consiste en decidir si F es satisfactible. El problema de optimización MaxSAT consiste en determinar el número máximo de cláusulas que pueden satisfacerse simultáneamente. A la fecha, como para todo problema NP-Completo, no se ha construido algoritmo eficiente que resuelva a SAT y/o MaxSAT. Una alternativa en la búsqueda de resolver eficientemente los problemas de optimización es el desarrollo de algoritmos de aproximación, es decir, algoritmos que trabajando dentro de cotas polinomiales de tiempo encuentren soluciones cercanas al valor óptimo, y especialmente que garanticen que las soluciones halladas se encuentran dentro de un factor multiplicativo de la solución óptima. En este trabajo, se exploraron las técnicas de búsqueda local como algoritmos de aproximación para resolver MaxSAT. Es conocido que el factor de garantía de una búsqueda local para MaxSAT es de k/k+1, donde k es el número máximo de literales que hay en alguna cláusula de la fórmula booleana de entrada [HaP90]. Khanna propone un procedimiento de búsqueda local con una nueva función objetivo llamada función no obvia que obtiene un factor de garantía de (2k-1)/2k, siendo k, al igual que el caso anterior, el número máximo de literales que hay en alguna cláusula de la fórmula booleana de entrada [KhS96]. Como resultado de nuestras investigaciones, proponemos una nueva función objetivo que utilizada dentro del procedimiento de búsqueda local obtiene un mejor factor de garantía que el de la función objetivo propuesta por Khanna, esto para cierta clase de fórmulas booleanas. En este documento presentamos la demostración matemática para la obtención de este nuevo factor de garantía y corroboramos el resultado teórico a través de un análisis empírico sobre un universo de fórmulas booleanas generadas aleatoriamente. 2 Adicionalmente se diseñaron dos estrategias, una basada en una arreglo tabú para acelerar la búsqueda de óptimos locales y la otra basada en el uso de elementos antipodales como procedimiento para re-iniciar la búsqueda después de arribar a óptimos locales. Ambas estrategias se implementaron a la búsqueda local basada en la función objetivo que propusimos. El algoritmo resultante, según el análisis empírico, obtuvo mejores resultados dentro de tiempos comparables con los demás algoritmos probados. La organización del documento es la siguiente: En el capítulo I se revisa una serie de conceptos básicos que son el preámbulo teórico del trabajo, estos conceptos incluyen: máquinas de Turing, clases de complejidad, teoría de los problemas NP-Completos, y una descripción acerca de los problemas SAT y MaxSAT. Posteriormente, en el capítulo II se presentan diversas técnicas de aproximación basadas principalmente en la búsqueda local, en el capítulo III se revisan los elementos necesarios para el análisis de algoritmos; en el capítulo IV se determina la eficiencia y factor de garantía del algoritmo propuesto, además, se realiza el análisis de los algoritmos mediante pruebas computacionales, tablas y gráficas comparativas. Por último se presentan las conclusiones obtenidas de la investigación y se proponen diferentes trabajos a futuro en esta línea del diseño y análisis de algoritmos de aproximación para MaxSAT. 3 Capítulo I Fundamentos teóricos 1.1 Máquinas de Turing Alan Turing [TuA36] desarrolló un modelo matemático simple conocido con el nombre de máquina de Turing; este modelo matemático ha servido como base para poder expresar en términos sencillos lo que un mecanismo de computación puede o no hacer. En la actualidad, es muy común decir que cualquier problema que es resoluble bajo una máquina de Turing será resoluble también por cualquier otro mecanismo de cómputo, e inversamente, problemas que no pueden resolverse por máquinas de Turing tampoco serán resueltos por cualquier otro mecanismo de cómputo. Es importante entonces revisar el funcionamiento de este modelo matemático que parece ser sencillo y a la vez muy poderoso. Se definen diferentes máquinas de Turing de acuerdo a la manera en que trabajan, así, existen máquinas de Turing deterministas y máquinas de Turing no deterministas, cada una de éstas está orientada a resolver un tipo especial de problemas. 1.1.1 Máquina de Turing determinista Las máquinas de Turing deterministas (MTD) constan de un control finito, una cabeza de lecto-escritura y una cinta dividida en un número infinito de celdas; dichas celdas son etiquetadas usando números enteros. Una representación esquemática de una máquina de Turing determinista puede observarse en la figura 1.1. Cabeza de lecto-escritura CINTA ... ... ... -3 -2 -1 0 1 2 3 4 ... Figura 1.1 Representación esquemática de una máquina de Turing determinista CONTROL FINITO 6 Turing sea un algoritmo, es necesario que posea una condición de paro al procesar cualquier cadena del alfabeto de entrada. Las definiciones anteriores están orientadas al reconocimiento de un lenguaje, sin embargo, se puede corresponder dichas definiciones a la resolución de problemas, especialmente hablando de problemas de decisión. Un problema de decisión (PD) se plantea como una pregunta general que acepta como respuesta sólo una de dos opciones: la respuesta ‘SI’o la respuesta ‘NO’. En forma abstracta, un problema de decisión es una estructura del tipo PD:<D, S>, donde D es el dominio de instancias del problema y S ⊆ D es el conjunto de aquellas que lo resuelven afirmativamente. El planteamiento del PD es: SI si x ∈ S ∀x ∈ D : PD(x) = NO en otro caso En estos términos, se dice que una máquina de Turing M resuelve el problema de decisión PD:<D, S> si M se detiene para toda x en D y LM = S (LM es el lenguaje reconocido por M). Usando el modelo de máquinas de Turing, se dice que el espacio de una computación de aceptación es el número de casillas utilizadas por la máquina de Turing durante el cómputo de aceptación y el tiempo es el número de pasos de computación que realiza la máquina de Turing durante el cómputo de aceptación. Sea F:N→ℜ una función y M una máquina de Turing, se dice que M acepta su entrada en tiempo (espacio) F(n) si para cada x en LM hay una computación que lleva a aceptación de M sobre x tal que el tiempo (espacio) de la computación de aceptación no excede F(n), con n = long(x), donde long(x) es la longitud de la entrada x. En términos de problemas de decisión, la complejidad en tiempo de M se plantea de la siguiente manera: PD:<D, S> tal que LM = S. La función de complejidad de tiempo ƒM:Z+→Z+ se define como: ƒM(n) = max{m|∃x ∈ S, n=long(x), y m es el tiempo de la computación de aceptación de x} En este sentido, se dice que el programa de una máquina de Turing tiene complejidad polinomial en tiempo, si existe un polinomio p tal que, para todo n ∈ Z+, ƒM(n) ≤ p(n). En términos de los algoritmos, se dice que un algoritmo A es eficiente cuando su función de complejidad en tiempo se puede acotar por un polinomio. Es decir, si ƒA(n) es la función de complejidad en tiempo del algoritmo A y existe un polinomio p tal que, para todo n ∈ Z+ ƒA(n) ≤ p(n), entonces se conviene en decir que A es un algoritmo eficiente. 7 1.1.2 Máquina de Turing no determinista El modelo de máquina de Turing no determinista (MTND), definido en [GaM79], tiene la misma estructura que una máquina de Turing determinista, excepto que se le adiciona un módulo de adivinanza, el cual tiene su propia cabeza de sólo escritura y se usa con el solo propósito de que escriba la cadena que adivina. Una representación esquemática de este modelo se presenta en la figura 1.2. CINTA ... ... ... -3 -2 -1 0 1 2 3 4 ... Figura 1.2 Representación esquemática de una máquina de Turing no determinista El funcionamiento de la máquina de Turing no determinista se describe a continuación: Al inicio, se escribe una cadena x ∈ Σ* en las celdas numeradas de 1 hasta |x| de la cinta (y las demás celdas contienen el símbolo blanco), la cabeza del control finito está posicionada en la celda 1 y el control finito está inactivo. La principal diferencia de este modelo con el de la máquina de Turing determinista estriba en que el reconocimiento de la cadena x toma lugar en dos fases: la fase de adivinación y la fase de revisión. Fase de adivinación: el módulo que adivina mueve su cabeza de sólo escritura una celda a la vez para dejar escrito a partir de las celdas etiquetadas desde -1 hasta -|w|, una cadena w ∈ Σ*, pasando posteriormente a la fase de revisión en donde ahora el módulo que adivina permanecerá inactivo. La elección de la cadena w a escribir es realizada por el módulo que adivina de una forma totalmente arbitraria, y por tal razón, puede inclusive nunca parar al estar generando a w. Fase de revisión: inicia cuando el control de estados finitos es activado en el estado q0. A partir de este momento, la computación continúa en exactamente la misma forma en que trabaja la máquina de Turing determinista, puesto que no interviene en esta fase el MODULO QUE ADIVINA CONTROL FINITO 8 módulo que adivina. Aunque bien es posible que la cabeza del control finito visite la cadena w escrita por el módulo que adivina. La computación de la máquina de Turing no determinista M se detiene cuando el control finito pasa a un estado final, y se dice que es una computación de aceptación si el control finito se detiene en el estado de aceptacion qy. Nótese que para alguna combinación de la cadena wbx, M puede nunca parar. En general, M tiene un número infinito de posibles computaciones para una entrada x dada, una computación por cada cadena w generada por el módulo que adivina. Se dice que M acepta a x si al menos existe una cadena w que hace que M llegue a un estado de aceptación. El lenguaje reconocido por M es entonces: LM = {x ∈ Σ*∃w generado por el módulo que adivina tal que M acepta a x} El tiempo requerido por una máquina de Turing no determinista M que acepta a una cadena x ∈ LM, se define como el máximo (sobre todas las computaciones de aceptación de M sobre x), del número de pasos que ocurren tanto en la fase de adivinación como de revisión, hasta que esta última fase llega a un estado de aceptación. La función de complejidad de tiempo TM:Z +→Z+ para M es: TM(n) = max({1}∪{m∃x ∈ LM, long(x) = n, M acepta a x en m pasos de computación}) Nótese que la función de complejidad de tiempo para M depende sólo del número de pasos que ocurren en una computación de aceptación, y que por convención, TM(n) es igual a 1 cuando ninguna entrada de longitud igual a n es aceptada por M. Se dice que más que hallar una solución al problema de decisión PD, M comprueba soluciones para el PD, ya que dada una instancia x del PD, el módulo que adivina propone una propuesta de solución w, y M debe comprobar si w es realmente una solución En este sentido, la máquina de Turing no determinista M es usada como un mecanismo de verificación o comprobación de propuestas de solución. Se dice que un programa corre en tiempo polinomial para la máquina de Turing no determinista M, si existe un polinomio p tal que TM(n) ≤ p(n) para todo n ≥ 1. 1.1.3 Clases de complejidad definidas por las máquinas de Turing Con el fin de clasificar el esfuerzo computacional que se requiere al resolver problemas de decisión, originalmente se usaron las máquinas de Turing como el modelo formal de computación [HaJ65]. El concepto clave fue definir una clase de complejidad en términos de los lenguajes que reconoce una máquina de Turing con recursos acotados (se consideran aquí solo los recursos de tiempo y espacio). Las clases de complejidad permiten clasificar los lenguajes (problemas) según la complejidad intrínseca computacional 11 todos estos modelos son equivalentes en lo que respecta al tiempo polinomial, y por tal, a la definición de la clase NP. DTIME(F(n)) (DSPACE(F(n))) denota la clase de problemas que son aceptados por máquinas de Turing deterministas que reconocen su entrada dentro de un tiempo (espacio) F(n). En tanto que NTIME(F(n)) (NSPACE(F(n))) denota la clase de problemas aceptados por máquinas de Turing no deterministas que aceptan dentro de tiempo (espacio) F(n). Al especificar las cotas de clases, muchas veces se usa la notación de la función de orden O. Si G(n) es una función, G:N→ℜ, O(G(n)) es el conjunto de funciones G’ que satisfacen G’(n) ≤ c⋅G(n) para alguna constante real positiva c y para toda n ≥ n0, donde n0 depende de G. Nótese que si n0 es cero, entonces se cumple para todo n ∈ N. La notación O es usada dentro de las clases NTIME, DTIME, etc. Por ejemplo, DTIME(2O(n)) denota la unión de DTIME(2cn) tomadas sobre todas las constantes c. También se usa la notación poly(G(n)) que abrevia a O(G(n)O(1)), esta es la clase de funciones acotadas superiormente por algún polinomio de función de G, ya que O(1) denota a cualquier constante real positiva. Usando esta notación, podemos reescribir a las clases de complejidad como: • DLOG = DSPACE(log(n)), • NLOG = NSPACE(log(n)), • P = DTIME(poly(n)), • NP = NTIME(poly(n)) y • PSPACE = DSPACE(poly(n)). Las clases P y NP se pueden también identificarse de la siguiente manera: • P es la clase de problemas que poseen algoritmos deterministas de resolución que tardan tiempo polinomial. • NP es la clase de problemas que tienen un algoritmo determinista de resolución que corre en tiempo exponencial, pero para los cuales, también existe un algoritmo no determinista que corre en tiempo polinomial. A los problemas de la clase P se les reconoce como problemas tratables, puesto que para cualquiera de sus instancias, éstas se resuelven por algoritmos que corren en un tiempo acotado polinomialmente. Se dice que un problema no ha sido bien resuelto hasta que es hallado un algoritmo determinista de tiempo polinomial que lo resuelve [GaM79]. Se le asigna a un problema el término de intratable, si este se ha mostrado tan difícil que no se ha encontrado algoritmo determinista con complejidad polinomial en tiempo que lo resuelva, es decir, no se ha hallado algoritmo eficiente que lo resuelva. Entonces una primera clase de complejidad que contiene problemas intratables es la clase NP. 12 Todo algoritmo cuya función de complejidad de tiempo no pueda acotarse por una función polinomial, se dice que es un algoritmo de complejidad exponencial en tiempo, aún cuando debe notarse que esta definición incluye ciertas funciones de complejidad de tiempo, tales como, nlog(n), las cuales normalmente no son consideradas como funciones exponenciales. El término intratable, refleja el punto de vista de que los algoritmos de tiempo exponencial no son considerados “buenos” algoritmos y que, generalmente, tal clase de algoritmos reflejan variaciones de búsquedas exhaustivas, mientras que algoritmos de tiempo polinomial generalmente son construidos sólo a través de explotar las estructuras internas e inherentes del problema. Existen algoritmos de tiempo exponencial que han sido muy útiles en la práctica. La complejidad de tiempo de un algoritmo tal y como se ha definido, es una medida para el peor de los casos, y el hecho de que un algoritmo tenga complejidad exponencial, significa que existe al menos una instancia del problema que requiere mucho tiempo, aún y cuando muchas de las instancias del mismo problema se resuelvan en la práctica en tiempo polinomial. Aún y cuando ciertos algoritmos de complejidad exponencial para determinados problemas tienen un buen comportamiento en la práctica, esto no ha detenido el avance de las investigaciones por buscar algoritmos de tiempo polinomial que resuelvan los mismos problemas. Y de hecho, el comportamiento general de los algoritmos exponenciales, lleva a la sospecha de que hace falta capturar alguna propiedad crucial del problema cuyo refinamiento pueda llevarnos a mejores métodos. Un área de gran interés es sobre técnicas generales que permitan diseñar algoritmos deterministas de tiempo polinomial, ya sea para los problemas intratables o para variaciones de éstos. La habilidad de algoritmos no deterministas, de poder revisar un número exponencial de posibilidades en tiempo polinomial, genera la sospecha de que este tipo de algoritmos son estrictamente más poderosos que los algoritmos deterministas de complejidad polinomial. Sin embargo, contra todos los esfuerzos realizados, no se ha podido demostrar esta especulación. La pregunta ¿P = NP? es uno de los problemas abiertos más importantes en la ciencia de la computación. Aún más, sabiendo que se cumple la siguiente jerarquía entre las clases de complejidad: DLOG ⊆ NLOG ⊆ P ⊆ NP ⊆ PSPACE, sigue siendo una pregunta abierta decidir cuáles de estas contenciones son propias, aún cuando se sabe que DLOG≠PSPACE [StL87]. 1.2 Teoría de los problemas NP-Completos Iniciemos presentando una definición de la clase NP dada por Khanna [KhS96]. 13 Definición 1.1 Un lenguaje L ⊆ Σ* está en NP si existe máquina de Turing determinista M que trabaja usando cotas polinomiales de tiempo y se tiene una constante c tal que para todo x ∈ Σ*: • x ∈ L ⇒ ∃y ∈ Σ* con |y| = O(|x|c) y tal que M reconoce al par (x, y) cuando se le da como entrada. • x ∉ L ⇒ ∀y ∈ Σ*, M rechaza el par (x, y) cuando se le da como entrada. Una interpretación natural de la definición anterior significa que la cadena y es la prueba para la aseveración de que x ∈ L y la máquina M es el verificador de tal prueba. La teoría sobre los problemas NP-Completos fue desarrollada originalmente para estudiar problemas de decisión; Cook [CoS71] y Levin [LeL73] establecieron que todos los lenguajes en NP son “reducibles” al problema 3-SAT (el problema de decidir si una formula en 3-FNC es o no satisfactible), un poco después, Karp [KaR72] mostró que el problema 3-SAT es “equivalente” a una gran variedad de problemas de decisión NP. A continuación se formalizarán las nociones de reducción y equivalencia. Definición 1.2 Un lenguaje L1 ⊆ Σ1* es reducible en tiempo polinomial a otro lenguaje L2 ⊆ Σ2* (denotado como L1 αp L2) si existe una función computable en tiempo polinomial ƒ:Σ1*→Σ2* tal que para todo x ∈ Σ1*, x ∈ L1 si y solo si ƒ(x) ∈ L2. Esta noción de reducción es llamada reducción en tiempo polinomial de “muchos a uno” o simplemente “reducción Karp”. Un lenguaje L1 es equivalente en tiempo polinomial a otro lenguaje L2 si: L1 α p L2 y L2 αp L1. A partir de ahora, obviaremos αp con α. Definición 1.3 Un lenguaje L es NP-Difícil si para cualquier lenguaje L’ ∈ NP: L’ α L. Definición 1.4 Un lenguaje L es NP-Completo si L ∈ NP y L es NP-Difícil. El resultado de Cook y Levin estableció que el problema 3-SAT es NP-Completo. Karp mostró que el problema 3-SAT es reducible a muchos otros problemas importantes de decisión en NP, tales como: determinar si un grafo es k-coloreable, verificar si hay ciclos hamiltonianos en un grafo, verificar si un grafo tiene un “clique” de al menos tamaño k, y de aquí, que estos problemas son también NP-Difíciles. Se tiene que, o bien todos estos problemas son difíciles (es decir, P≠NP), o todos ellos son fáciles (es decir, P=NP). La teoría de los problemas NP-Completos proporciona un ambiente de trabajo para el estudio de la complejidad de otros problemas que pueden plantearse como problemas de optimización. 1.2.1 Caracterización sintáctica de los problemas en NP La noción de complejidad parece encontrarse inherentemente ligada a los modelos computacionales y recursos acotados en tiempo y espacio. Pero sorpresivamente, casi 16 A una solución que está dentro de un factor multiplicativo rA del valor óptimo se le conoce como una rA-aproximación, y decimos que un problema NPO es aproximable dentro de un factor rA si éste tiene un algoritmo de aproximación de tiempo polinomial con factor de garantía rA. A mediados de los 70’s, Johnson [JoD74] estudió la propiedad de aproximabilidad en tiempo polinomial de problemas en NPO y descubrió que mientras es posible encontrar buenas aproximaciones en tiempo polinomial para diversos problemas de optimización NP-difíciles, hay muchos otros que resisten ser aproximados dentro de factores constantes. Los trabajos subsecuentes realizados por diversos investigadores solamente han confirmado lo observado por Johnson. En la actualidad, se tienen diversos resultados que muestran que muchos problemas de optimización NP-difíciles no pueden ser “bien aproximados”, a menos que P = NP. La dificultad de hallar buenas aproximaciones podría deberse a que las reducciones usadas con los problemas de decisión no preservan la calidad de las soluciones aproximadas, por lo que se hace necesario desarrollar un ambiente de trabajo que permita estudiar los problemas de optimización, sin eliminar sus características esenciales. 1.2.3 Vista computacional de los problemas de optimización Un esquema de clasificación basado en la aproximabilidad computacional de los problemas en NPO fue usado implícitamente en el trabajo de Johnson. Así, se tiene la conformación de clases como: APX y PTAS. Definición 1.8 Un problema Π esta en la clase APX si existe un algoritmo de tiempo polinomial para Π cuyo factor de garantía está acotado por una constante. Definición 1.9 Un problema Π está en la clase PTAS si para cualquier racional ε > 0, existe un algoritmo de aproximación de tiempo polinomial para Π cuyo factor de garantía esta acotado por (1 + ε). Sea f una función, f-APX denota la clase de problemas en NPO que son aproximables dentro de un factor f, así, se obtiene una jerarquía de clases de complejidad. Por ejemplo, poly-APX y log-APX son las clases de problemas en NPO los cuales tienen, respectivamente, algoritmos de aproximación con un factor de garantía acotado polinomialmente y logarítmicamente, con respecto a la longitud de la entrada. La fortaleza de esta clasificación radica en la habilidad de capturar problemas que tienen un umbral específico de aproximabilidad. Podríamos estar interesados en restringir nuestra atención a subconjuntos polinomialmente acotados de estas clases. Definición 1.10 El subconjunto polinomialmente acotado de la clase de problemas C, con C ∈ APX, denotado como C-PB, es el conjunto de problemas Π ∈ C tal que para toda instancia I, n=|I|, existe un polinomio p(n) tal que OPT(I) ≤ p(|I|). 17 Entonces, APX-PB denota la clase de problemas en NPO que son aproximables dentro de factores constantes y que tienen valores óptimos acotados polinomialmente. Los problemas SAT y MaxSAT son problemas NP-Completos, en particular MaxSAT es un problema de la clase APX-PB. Ambos problemas son centrales para la Demostración Automática de Teoremas (DAT) y para la teoría de la complejidad computacional, por lo que es importante realizar un análisis a detalle de estos dos problemas. En la siguiente sección se hará una descripción general de estos problemas y posteriormente, en el siguiente capítulo, se presentará un análisis extenso de algoritmos aplicados en la resolución de ellos. 1.3 Problemas SAT y MaxSAT El problema de decisión asociado al problema de satisfactibilidad (SAT) de una fórmula proposicional en forma normal conjuntiva, puede expresarse como: Instancia: Un conjunto U = { u1 ,..., un } de variables booleanas y una colección F = { C1 ,..., Cm } de cláusulas definidas sobre U. Pregunta: ¿Existe una asignación de valores de verdad a los elementos de U, que haga que todas y cada una de las cláusulas de F tomen valor verdadero? Notación: Asignación: Es una función t: U → {‘Falso’, ’Verdadero’}. Literal: Las constantes ‘Falso’, ’Verdadero’ o una expresión de la forma u o ¬u, donde u es elemento de U. Frase: Es una conjunción de literales F = l1 ∧...∧ lk . Una frase es verdadera si todas sus literales lo son. Cláusula: Es una disyunción de literales, C = l1 ∨...∨ lk . Una cláusula es verdadera si alguna de sus literales lo es. Forma normal conjuntiva (FNC): Es una conjunción de cláusulas. Una k-FNC, k ∈ N, es una FNC con exactamente k literales en cada cláusula. Forma normal disyuntiva (FND): Es una disyunción de frases. Una k-FND, k ∈ N, es una FND con exactamente k literales en cada frase. Proposición 1.1: Toda fórmula proposicional es lógicamente equivalente a una FNC, y de hecho, la FNC equivalente es algorítmicamente calculable [GaJ87] Una FNC F es satisfactible si y solo si existe una asignación de valores de verdad para U, que simultáneamente satisfaga a cada una de las cláusulas en F. 18 Por ejemplo, una instancia específica del problema SAT puede ser la siguiente fórmula F, sobre la que se cuestiona si es o no satisfactible: F (x1,..., x7) = (¬x1 ∨ ¬x2) ∧ ( x1 ∨ x3 ∨ x4 ) ∧ ( x5 ∨ ¬x3 ) ∧ ( ¬x5 ∨ ¬x6 ) ∧ ( x1 ∨ x6 ∨ x7 ) ∧ ( ¬x5 ∨ ¬x7 ) ∧ (x2) ∧ ( ¬x3 ∨ ¬x7 ) La fórmula anterior es satisfactible con la asignación: t(x1) = t(x3) = t(x5) = t(x6) = ‘Falso’; t(x2) = t(x4) = t(x7) = ‘Verdadero’; Toda asignación que satisface a una fórmula F se dice que es un modelo para F. El problema SAT consiste en decidir, si dada una fórmula F de entrada, que sin pérdida de generalidad puede suponerse en FNC (de acuerdo a la proposición 1.1), se determine si acaso existe una asignación de U que haga que F tome el valor verdadero. F = { C1 ,..., Cn } - Conjunto clausular ALGORITPARA Figura 1.3 Planteamiento del problema SAT El primer problema que se demostró ser NP-Completo fue el problema SAT [CoS71]. Cook utilizó el problema SAT para delimitar la clase de los problemas NP-Completos. SAT es el clásico problema intratable, lo que significa que todos los algoritmos hasta ahora presentados requieren de mucho tiempo de cómputo o de mucho espacio para su resolución en la práctica, excepto quizás, para algunos casos triviales. Es una pregunta abierta hasta ahora, demostrar si acaso SAT podría ser un problema tratable, es decir, saber si se podrán construir algoritmos que resuelvan SAT de manera eficiente (en tiempo polinomial). Otro problema que se ha demostrado ser intratable, es la versión de optimización para el problema de satisfactibilidad, conocido como el problema de máxima satisfactibilidad MaxSAT, que consiste en encontrar una asignación a las variables que maximice el número de cláusulas que se satisfacen simultáneamente. Por ejemplo, si el conjunto original de cláusulas es insatisfactible, entonces MaxSAT busca conocer la asignación de valores veritativos que permitan que un número máximo de cláusulas se satisfagan simultáneamente. MaxSAT es NP-Completo aún cuando cada cláusula contenga a lo más dos literales (Max-2-SAT) [GaM76]. ALGORITMO PARA SAT F es satisfactible F no es satisfactible SI NO 21 asignación que mejore el valor de f. En todos los algoritmos implementados, se eligió la estrategia de pasar inmediatamente a un vecino que mejora la función objetivo, en lugar de revisar por un óptimo de la vecindad, ya que en la práctica, se ha visto que ambas estrategias alcanzan similares aproximaciones, pero sin embargo, la primera de éstas estrategias, reduce la complejidad del tiempo promedio del algoritmo. Figura 2.1 Pseudocódigo del algoritmo de búsqueda local [GuJ94]. 2.2 Búsqueda local aplicada al problema SAT y MaxSAT Como función objetivo se puede usar el polinomio que se obtiene de aritmetizar la fórmula booleana F. Sea F la fórmula en FNC, entonces: F = ∧ ∨ lij 1 ≤ i ≤ m 1 ≤ j ≤ lc El polinomio que codifica a F, y que es función objetivo en la búsqueda local es: ∑∏ = = = m i l j ij c lmf 1 1 )( con m(lij) = (1 - lij) si lij = xi , y m(lij) = lij si lij = ¬xi. Así por ejemplo, si F x x x x x x x x( , , ) ( ) ( )1 2 3 1 2 1 2 3= ∨ ¬ ∧ ¬ ∨ ∨ , el polinomio que codifica a F es: f p x x x( , , )1 2 3 = ( ) ( )( )1 1 11 2 1 2 3− + − −x x x x x . Procedure GSAT() begin m = 0; for (i=1; i<=MAX-INTENTOS; i++) begin S := Una asignación generada aleatoriamente for (j=1; j<=MAX-FLIPS; j++) begin if S satisface F then return (S, |F|) S := com(S, j) m := max{m, # de cláusulas satisfechas por S} end end return (“Número máximo de cláusulas que se logró satisfacer es: “, m) end 22 Para una asignación dada, el polinomio f cuenta el número de cláusulas que son insatisfechas por la asignación. Así pues, decidir la satisfactibilidad de F es propiamente equivalente a minimizar f. Entonces F es satisfactible si y sólo si el mínimo de f sobre el dominio de asignaciones de F es cero. Una explicación más amplia del proceso de aritmetización se puede ver en [DeG95]. Entrada: F - fórmula booleana, con n - No. de Variables, m - No. de cláusulas. Salida: xv - asignación hallada, Valor = número de cláusulas que logró satisfacer. Variables globales: Iter = Número de iteraciones, MAX_ITER = Cota que indica el número máximo de iteraciones a realizarse. Figura 2.2 Búsqueda local obvia. La búsqueda local implementada (LS) comienza a partir de un punto inicial x0 construido de forma aleatoria, se determina la vecindad del punto actual de búsqueda N(xi), y aplica un proceso iterativo tal que en cada iteración se obtenga un nuevo punto xi+1 en N(xi) de manera que f(xi+1)< f(xi) (o, alternativamente, f(xi+1)>= f(xi) si se tratase de maximizar), si tal punto existiese, y en tal caso, éste se convierte en el nuevo punto “solución” y se reitera el proceso. En otro caso, se retiene a xi como óptimo local. Un algoritmo con este mecanismo de búsqueda se observa en la figura 2.2. Procedure LS() begin x = AsignacionAleatoria(); /* Se obtiene una asignación aleatoria */ Valor = f(x); /* Aplica función objetivo a la asignación x */ Iter = 1; while (Valor < m) and (Iter < MAX_ITER) do begin Iter = Iter + 1; while (!SenaMin) begin /* Ciclo principal */ SenaMin = VERDADERO; /* Supóngase haber llegado a un mínimo */ for (j=1; j<=k; j++) begin /* k - posibles cambios de bits */ if (f(com(x,j)) > Valor) begin /* Se mejoró a MaxSAT ? */ x = xv = com(x, j); /* Intercambio del j-ésimo bit de x */ Valor = f(x); /* Cambiar valor de la mejor asignación */ SenaMin = FALSO; /* Seguir buscando */ end end end end return(xv, Valor); /* Regresa mejor asignación y su valor */ end 23 Si bien la búsqueda local ha demostrado ser una estrategia eficiente para resolver SAT y MaxSAT cuando las fórmulas F tienen varias asignaciones que las satisfacen, tiene el grave problema de bloquearse en óptimos locales, pero aún más grave, es que los factores de aproximación que garantizan estas estrategias son aún lejanos del umbral al que teóricamente puede aproximarse, por ejemplo, MaxSAT. 2.3 Búsqueda local no obvia La función objetivo en la búsqueda local ha expresado tradicionalmente y de forma directa, maximizar el número de cláusulas que se satisfacen en la fórmula. Pero diferentes tipos de búsquedas locales pueden obtenerse al usar diferentes funciones objetivos, inclusive al usar funciones que originalmente no muestran la opción natural de maximizar el número de cláusulas que se satisfacen por una asignación, a este tipo de búsqueda se le llama comúnmente, búsqueda local no obvia (LS-N). Un caso de búsqueda local no obvia fNOB para Max-k-SAT es la presentada por Khanna [KhS95], donde la función objetivo no obvia es de la forma siguiente: Ecuación 2.1 Función objetivo de la búsqueda local no obvia. Donde Si denota al conjunto de cláusulas, en las cuales, exactamente i literales son verdaderas bajo una asignación x. Es decir, Si es el conjunto de todas las cláusulas en donde se satisfacen exactamente i literales, W(Si) es la cardinalidad de Si; y los Ci’s (i=0,...,k), son constantes reales seleccionadas adecuadamente para cumplir ciertas condiciones del proceso de búsqueda y que ayudarán en la determinación del factor de aproximación (más adelante se definirá la manera de obtener los Ci’s). Por ejemplo, la función objetivo propuesta por Khanna [KhS95] para fórmulas del tipo 2-FNC (FNC donde hay exactamente 2 literales por cláusula), es: fNOB = 3/2 W(S1) + 2 W(S2) Los óptimos locales de la función objetivo “estándar” no son necesariamente los óptimos locales de esta nueva función objetivo. En este caso, la segunda función objetivo permite saltar sobre los óptimos locales de LS y de hecho, proporciona un comportamiento diferente de las direcciones en la trayectoria de búsqueda. Se espera que el comportamiento de LS-N sea mejor, debido a la manera en que trata cada asignación, por ejemplo, la función objetivo no obvia puede entre dos asignaciones que satisfacen el mismo número de cláusulas decidir que asignación es mejor para la búsqueda. ∑ = = k i iiNOB SWCf 0 )( 26 cuenta la historia de ésta. Es decir, el procedimiento trata de extraer información de lo sucedido y actuar en consecuencia. En este sentido, puede decirse que hay un cierto aprendizaje y que la búsqueda es inteligente. El principio de TS podría resumirse como: "Es mejor una mala decisión basada en información que una buena decisión al azar, ya que, en un sistema que emplea memoria, una mala elección basada en una estrategia proporcionará claves útiles para continuar la búsqueda. Una buena elección fruto del azar no proporcionará ninguna información para posteriores acciones" [DiA96]. TS comienza de la misma forma que cualquier procedimiento de búsqueda local, procede iterativamente de una solución x a otra dentro de su vecindad N(x). Sin embargo, en lugar de considerar toda la vecindad de la solución, TS define una nueva vecindad N'(x) tal que N'(x) ⊆ N(x). Existen muchas maneras de definir la vecindad reducida N’(x)de un punto x. La más sencilla consiste en etiquetar como tabú las soluciones previamente visitadas en un pasado cercano. Esta forma se conoce como memoria a corto plazo y está basada en guardar una lista tabú T de las soluciones visitadas recientemente. Así en una iteración determinada, N’(x) del punto actual x se obtendría a partir de N(x) eliminando las soluciones etiquetadas como tabú. El objetivo principal de etiquetar las soluciones visitadas como tabú es reducir la búsqueda evitando pasa por caminos ya visitados y se espera también que esto reduzca la posibilidad de que la búsqueda se cicle. Por ello se considera que tras un cierto número de iteraciones la búsqueda está en una región distinta y puede liberarse del status tabú (pertenencia a T) de las soluciones antiguas. En los orígenes de TS se sugerían listas tabús de tamaño pequeño, actualmente se considera que las listas pueden ajustarse dinámicamente según la estrategia que se esté utilizando. Es importante considerar que los métodos basados en búsqueda local requieren de la exploración de un gran número de soluciones en poco tiempo, por ello es crítico el reducir al mínimo el esfuerzo computacional de las operaciones que se realizan a menudo. En ese sentido, la memoria a corto plazo de TS está basada en atributos en lugar de ser explícita; esto es, en lugar de almacenar las soluciones completas (como ocurre en los procedimientos de búsqueda exhaustiva) se almacenan únicamente algunas características de éstas. La memoria mediante atributos produce un efecto más sutil y beneficioso en la búsqueda, ya que un atributo o grupo de atributos identifica a un conjunto de soluciones. Para diseñar una estrategia tabú al algoritmo de búsqueda local no obvia LS-NC0 que hemos propuesto, combinamos la propuesta de Hansen [HaP90] con una que propusimos anteriormente en [DeG96]. 27 Las ideas principales de esta estrategia tabú son: 1.- Llevar un recuento de la dirección de la búsqueda que llevó a un óptimo local, llamada dirección descendente, y entonces se prohiben movimientos inversos a tal dirección de descenso, al menos durante un número fijo de iteraciones. 2.- Aplicar la prohibición sólo durante un número fijo de iteraciones. Con los elementos descritos puede diseñarse un algoritmo básico de TS para un problema de Optimización dado. En la propuesta de búsqueda tabú presentada en [DeG96], se introduce una estrategia que permite acelerar el proceso de búsqueda durante la fase de 'meseta', que como se ha dicho, es la fase en la cual es difícil hallar vecinos que mejoren la función objetivo y que es donde se invierte la mayor cantidad de tiempo del proceso de búsqueda. Para llevar control de la dirección de descenso se introduce un arreglo Ind que indica las direcciones en las que ha habido cambios durante el proceso de búsqueda. Valores positivos en las posiciones j del arreglo Ind indican cambios locales (dirección de descenso) en la dirección j, por lo que al pasar a un nuevo punto de búsqueda después de arribar a un óptimo, significará invertir los valores de las variables que durante la búsqueda no hayan sufrido cambios, por ejemplo, que corresponden a valores 0 en la posición j del arreglo Ind. El uso del arreglo que indica la dirección de descenso es útil para reducir el tiempo de prueba de puntos en direcciones opuestas a la dirección de descenso, agilizando así la búsqueda durante la fase de 'meseta'. Este arreglo Ind es utilizado como una memoria a corto plazo basada en atributos que es la lista tabú. Llamaremos a la búsqueda tabú anteriormente presentada y que utiliza como función objetivo la función no obvia presentada en la ecuación 2.1, búsqueda tabú no obvia. 2.5.1 Búsqueda tabú no obvia con antipodales Otra mejora a los procedimientos basados en la búsqueda local, consiste en seleccionar una estrategia óptima, o al menos adecuada, para saltar al siguiente punto de la búsqueda después de arribar a óptimos. A diferencia del salto probabilístico que caracteriza a procedimientos de búsquedas con control probabilístico (como son por ejemplo las heurísticas de recocido simulado), en la propuesta de búsqueda tabú se ha realizado el salto a nuevos puntos de búsqueda sólo hasta llegar a configuraciones de óptimos locales, y así ir saltando aleatoriamente de un óptimo local a otro. Este salto se inicia mediante el uso de un nuevo punto de inicio x' para la búsqueda local; este punto de inicio se obtiene mediante la negación de cada uno de los bits que conforman al último local encontrado x, a este nuevo punto x' se le da el nombre de antipodal de x, en tal sentido, dos puntos x y x' son antipodales si y solo si x and x' ≅ 0 y x or x' ≅ 1 (vector 0 y vector 1). 28 Supongamos que x0 resultara ser un óptimo local, entonces se le puede aplicar una perturbación para hacerlo “saltar” a un nuevo punto x1 que difiera significativamente de x0. Contrariamente a como lo evaluaría la estrategia de recocido simulado, no se le aplica la prueba de “aceptar/rechazar” al nuevo punto, sino que a partir de x1 se llega a un nuevo óptimo local y sólo hasta ese momento se aplica la prueba de aceptación. En este esquema, es conveniente mantener un arreglo con los mínimos locales que se van visitando para evitar caer en ciclos. Como resultado del análisis empírico realizado a LS, LS-N y LS-NC0, al rastrear la lista de óptimos locales que se obtenían en cada corrida se observó que las trayectorias de búsqueda llegaban a pasar varias veces por regiones ya exploradas después de arribar a un óptimo local; esto depende principalmente de la definición del punto de re-inicio de búsqueda. Así que, cuando se arriba a un óptimo local, es importante controlar el punto de re-inicio de la búsqueda, primero para evitar caer en caminos ya explorados así como para ampliar el área de búsqueda. La forma idónea encontrada para definir al nuevo punto de búsqueda, fue usando el punto antipodal del último óptimo local hallado, o bien, si este punto perteneciera a una trayectoria ya visitada, entonces se puede construir un nuevo punto que difiera significativamente de cada uno de los óptimos locales que se tienen en la lista de óptimos. En la figura 2.4 se puede observar el algoritmo de búsqueda tabú no obvia con antipodales (LS-NTA) donde se utiliza el arreglo Ind como arreglo tabú de memoria corta basada en atributos. El éxito de esta propuesta está determinado primero por su habilidad de moverse exitosamente a través de la fase de 'meseta' en la búsqueda, reduciendo el tiempo de ésta fase y, segundo, por el uso de elementos antipodales del último óptimo local hallado como nuevo punto de re-inicio de la búsqueda, dando así amplitud al dominio de búsqueda. Después de haber definido la nueva propuesta algorítmica, es pertinente presentar los elementos para el análisis de algoritmos que permitan clarificar los métodos para el análisis del algoritmo propuesto y así determinar su factor de garantía. En el capítulo siguiente se presentan los elementos para el análisis de algoritmos. 31 otro tipo de problema se requiere generalmente rediseñarlo tanto que realmente resulta en un nuevo algoritmo. A la inversa, algoritmos generales son diseñados independientes al problema y para ser aplicados en un gran número de situaciones. Un algoritmo hecho a la medida en general se puede ejecutar comparativamente rápido, pero tiene una aplicabilidad limitada y, un algoritmo general es usualmente lento pero tiene un gran potencial de aplicación. La flexibilidad de un algoritmo es una característica importante. Un algoritmo flexible debe ser capaz de actualizarse fácilmente y adaptarse para tratar problemas relacionados. Un algoritmo robusto es capaz de producir buenos resultados bajo muy diferentes circunstancias, tales como cuando se trabajan con instancias patológicas del problema. Tomando ambas características, un algoritmo flexible y robusto resulta ser un algoritmo de propósito general y es posible el que pueda aplicarse en la resolución de muchos tipos de problemas. Un aspecto relevante de los algoritmos es referente a la consistencia de las soluciones que encuentra. Un algoritmo consistente no permite equivocaciones en sus respuestas. Por ejemplo, al tratar problemas de decisión, la solución que proporciona un algoritmo consistente debe ser siempre correcta y no permitir equivocaciones, como podría ser responder ‘SI’ cuando la respuesta correcta es ‘NO’ o a la inversa. Aunque ante la imposibilidad de hallar las respuestas correctas a un problema en un tiempo acotado de cómputo (generalmente acotado en un orden polinomial de tiempo) se han diseñado algoritmos con bases probabilísticas, es decir, que las soluciones encontradas tienen un factor de certeza (y a su vez de error) de ser la solución que se busca. Otra división que se considera al analizar las propuestas algorítmicas, es precisar si se tratan de algoritmos completos o incompletos. Los algoritmos completos siempre encuentran la solución correcta para toda instancia del problema. Los algoritmos incompletos encuentran soluciones parciales al problema, es decir, sólo para ciertas instancias del problema hallarán la solución correcta, en tanto que para otras instancias no podrán determinar cuál es la solución correcta [GuJ93]. Por ejemplo, un algoritmo de resolución para el problema SAT se dice que es completo, si para toda fórmula de entrada siempre puede verificar si existe o no una asignación que la satisfaga. En tanto, que un algoritmo incompleto puede encontrar sólo la correspondiente respuesta para una cierta clase de fórmulas y, no poder determinar cual es la respuesta correcta para otro tipo de instancias. Todos los algoritmos consistentes y completos hasta ahora conocidos para tratar el problema SAT, determinan la respuesta para muchas instancias del problema requiriendo sólo tiempo polinomial, pero también sucede que, por el tipo de búsqueda exhaustiva que en el peor de los casos deben realizar (aún y cuando incluyan estrategias que intentan acelerar el proceso de búsqueda), necesitan de un tiempo exponencial para llegar a la solución de las instancias. 32 La dificultad de diseñar algoritmos consistentes y completos, proviene de la cantidad de recursos computacionales que tales algoritmos requieren. Todos los algoritmos consistentes y completos diseñados para resolver problemas NP-difíciles son de complejidad exponencial en tiempo. Puesto que, de manera general, dada una instancia, no se sabe de antemano si un algoritmo completo lo podrá resolver en tiempo polinomial o bien tendrá que realizar una búsqueda exhaustiva, y como para el peor de los casos el algoritmo necesita tiempo exponencial para hallar la solución, esta clase de algoritmos son considerados algoritmos ineficientes. Algunos algoritmos para el problema SAT que son completos, consistentes, y de complejidad exponencial en tiempo para los peores casos son: • El Método de Davis y Putnam • Los procedimientos que construyen modelos mínimos • El procedimiento de resolución • Procedimientos que usan árboles semánticos • Búsqueda con retroceso • Sistemas que usan tablas sintácticas Al tratar problemas de optimización NP-difíciles (por ejemplo, problemas de la clase APX o PTAS) los algoritmos completos son aquellos que, para cualquier instancia, encuentran el punto del dominio que es óptimo global, pero nuevamente, son algoritmos que requieren tiempo exponencial en el peor de los casos. También para esta clase de problemas existen propuestas algorítmicas incompletas, en el sentido de que son algoritmos con complejidad polinomial en tiempo y que, sin importar la forma de las instancias, encuentran soluciones aproximadas a las óptimas, es decir, hallan valores cercanos a los óptimos globales. En general, los algoritmos que encuentran con rapidez soluciones buenas, aunque no necesariamente óptimas, se denominan algoritmos heurísticos, puesto que estos algoritmos frecuentemente se basan en reglas derivadas de la experiencia o del sentido común. Aunque las heurísticas tienden a ser específicas al problema, se han encontrado principios generales en algunas heurísticas que permiten su aplicación a una gran cantidad de problemas. Nótese que los algoritmos heurísticos son casos especiales de algoritmos incompletos. Entre los algoritmos eficientes o incompletos para los problemas SAT y MaxSAT, se tienen: • Búsqueda local • Recocido simulado • Búsqueda tabú • Algunos heurísticos para la programación entera • Estrategias voraces • Algoritmos genéticos 33 Una observación acerca de estos algoritmos incompletos es que la mayoría son de naturaleza iterativa, es decir, generalmente parten de uno o varios puntos del espacio de búsqueda y en cada iteración intentan irse acercando a los puntos solución. Dos aspectos relevantes de los algoritmos iterativos son su convergencia global y el promedio de convergencia local. La convergencia global de un algoritmo, es un análisis que determina si es posible que a partir de un punto inicial dado, la secuencia de puntos generados por el algoritmo (puntos intermedios) pueda converger a la solución final. El promedio de convergencia local de un algoritmo indica el promedio esperado de puntos (o el número promedio de pasos) en la secuencia que converge a una solución [GuJ93]. La calidad de la solución encontrada por un algoritmo puede medirse de diferentes maneras, tales como medir: el error absoluto, el error relativo, el factor de aproximación de la solución, etc. Pero todas estas medidas son esencialmente idénticas y tienen la intención de medir que tan cerca al óptimo es la solución dada por el algoritmo. Entre más corta sea la distancia entre la solución hallada y el óptimo, será mejor la calidad de la solución. En lo que respecta a la precisión y calidad de los resultados obtenidos por algoritmos para SAT y MaxSAT, todo depende de la clase de algoritmos que se trate. En el caso de algoritmos completos, la solución encontrada para SAT corresponde a una decisión correcta de la satisfactibilidad de la fórmula y a un óptimo global para el caso MaxSAT. La calidad de la respuesta que dan los algoritmos incompletos será un elemento de análisis en la determinación de la calidad del algoritmo. En la siguiente sección se tratará precisamente sobre un estudio en el análisis de la calidad de los resultados obtenidos por una clase particular de algoritmos incompletos, conocidos como algoritmos de aproximación y en el capítulo cuatro, se presenta el análisis de los algoritmos de interés, los cuales son algoritmos iterativos que usan heurísticas valiosas en la resolución del problema MaxSAT, y que en general, puede usarse en la resolución de una gran cantidad de problemas. 3.2 Métodos para determinar el factor de garantía de los algoritmos Existen diferentes métodos formales y probabilísticos usados en el análisis de los algoritmos, estas técnicas generalmente se utilizan para determinar la complejidad en tiempo y espacio de los algoritmos, así como en la determinación del factor de garantía de los algoritmos de aproximación. Reeves [ReC93] enuncia tres métodos generales comúnmente utilizados para la determinación del factor de garantía de los algoritmos de aproximación, los cuales son: • Métodos Analíticos. • Métodos Empíricos. • Análisis Estadístico. 36 probabilidad p/2 y esta ausente con probabilidad 1-p. El número promedio de literales en cada cláusula es de k. 2) Modelo práctico: Se usan como instancias de fórmulas en FNC, las formulas generadas a partir de problemas típicos, tales como: el problema de colorear una gráfica, el problema de colocar n-reinas, etc... o bien, instancias generadas a partir de aplicaciones reales. 3) Modelo regular: Como fórmulas a procesar se usan instancias que son reconocidas o reportadas en la literatura como casos difíciles de resolver por algún algoritmo en particular. Para entender la dificultad que cada instancia específica del problema de satisfactibilidad tiene, se definen los conceptos de dificultad de una instancia y el tipo de distribución de las instancias. La dificultad de una instancia para el problema SAT es una propiedad intrínseca a la fórmula F en FNC. La dificultad de una instancia es un indicador del grado de dificultad que tendrán los algoritmos para determinar su satisfactibilidad. Por ejemplo, una formula F con m cláusulas y n variables es más difícil de satisfacer cuando se incrementa el cociente m/n, (muchas cláusulas definidas sobre pocas variables incrementa la posibilidad de tener conjuntos insatisfactibles de cláusulas, por ejemplo: {x, ¬x}). O bien, cuando el número promedio k de literales por cláusula decrece, ya que pocas literales y un gran número de cláusulas reducen la posibilidad de hacer a todas las cláusulas satisfactibles [ChV92]. Esta es una de las razones por lo que el problema 3SAT es tan complejo como el SAT general, o el Max-2-SAT es tan difícil como el caso general MaxSAT. Evidencias empíricas [ChV92] sugieren que existe un umbral fino que denotaremos con ß tal que cuando c<ß entonces una fórmula generada aleatoriamente con m = c⋅n cláusulas es casi seguramente satisfactible y cuando c>ß tal fórmula es casi seguramente insatisfactible. En [KaA94] se conjetura que tal umbral es alrededor de 4.2, y muestran además que para c>4.758 una fórmula 3-FNC es insatisfactible con alta probabilidad. Tal umbral no ha sido probado de manera rigurosa, pero se conjetura que existe. Se define la dificultad-algorítmica de una serie de instancias de fórmulas en FNC, como la forma que deben tener las instancias para que la determinación de la satisfactibilidad se pueda decidir fácilmente por un determinado algoritmo, así como la forma que deben tener las instancias donde el algoritmo tiene más problemas (lo que generalmente significa que requiere de más tiempo o espacio de lo normal) para decidir si una fórmula es o no satisfactible. Entonces, la dificultad-algorítmica de las instancias depende no solo de las instancias, sino también del algoritmo. Por ejemplo con instancias que son claramente insatisfactibles 37 en donde existe un gran número de inconsistencias (casos frecuentes de ocurrencias del conjunto {(x), (¬x)}), un algoritmo completo para el problema SAT (como podría ser el algoritmo de Davis-Putnam) puede decidir la inconsistencia de estas instancias rápidamente, pero para algoritmos incompletos tales como las búsquedas locales, éstos podrían no darse cuenta de la inconsistencia de tales instancias. Y por el contrario, algoritmos incompletos para el problema SAT podrían decidir más rápidamente la satisfactibilidad de ciertas instancias de lo que podría hacerlo el algoritmo de Davis- Putnam. Los elementos presentados en este capítulo son útiles en el análisis de los algoritmos implementados en este trabajo. Para el análisis empírico de las propuestas algorítmicas (para el tratamiento del problema MaxSAT), se hace uso del modelo que se conoce con el nombre de “Modelo exacto k-SAT” y la técnica consiste en construir la formula FNC, formando cada cláusula de manera independiente a las demás y donde cada cláusula tiene exactamente k literales. Se realizó el análisis analítico para determinar el factor de garantía de uno de los algoritmos que proponemos (LS-NC0), y se realizó el análisis empírico a cada una de las propuestas algorítmicas presentadas LS, LS-N, LS-NC0 y LS-NTA. La información detallada acerca del análisis empírico y analítico se encuentra desarrollada en el capítulo siguiente. 38 Capítulo IV Determinación del factor de garantía y análisis experimental En el capítulo anterior se presentaron las técnicas más comunes para el análisis de algoritmos. En este capítulo, utilizaremos los conceptos presentados para aplicarse al análisis del algoritmo propuesto. Primeramente, en la sección 4.1 se realiza un análisis teórico del factor de garantía y, posteriormente, en la sección 4.2 se realiza un análisis empírico, el cual corrobora los resultados obtenidos en la sección 4.1. 4.1 Determinación del factor de garantía En esta sección se mostrará el poder de la búsqueda local no obvia, y se demostrará que para la función objetivo no obvia propuesta por Khanna se obtiene un factor de garantía de ¾ para Max-2-SAT y de (2k - 1) / 2k para Max-k-SAT. Así también, se demostrará que el algoritmo asegura un factor de garantía de 4/5 para Max-2-SAT sobre aquellas fórmulas FNC que cumplen la condición expresada posteriormente en la ecuación 8 de este capítulo. Para entender la estrategia general para la obtención del factor de garantía, recordemos que dentro de la función objetivo no obvia: Si indica el número de cláusulas que bajo una cierta asignación I, satisfacen exactamente i literales. W(Si) representa el peso asociado al conjunto de cláusulas Si. fNOB(z) es la evaluación de la función objetivo sobre la asignación z. Y además, si z1 es el vecino de z, entonces z1 es (z)j cuyo valor es igual a z excepto en el bit de la posición j y fNOB(z1) es la evaluación de la función objetivo f sobre z1. Denotemos como df/dz al diferencial de la función objetivo cuando es evaluada en puntos de la misma vecindad, en este caso: df/dz = f(z') - f(z), donde z' ∈ N(z). Y cuando explícitamente se quiera indicar al vecino de x, se expresará de la manera siguiente: df/dzj, donde df/dzj = f((z)j) - f(z) y (z)j es z excepto en el bit de la posición j. La estrategia seguida en el análisis del factor de garantía consiste en calcular df/dz y de esta manera se establecen los cambios que sufre la función objetivo cuando una literal cambia de un valor a otro (presupondremos que será de uno a cero binario), después se analiza que sucede cuando este cambio se realiza considerando un óptimo local. Los resultados se expresan en términos del número de cláusulas que no se satisfacen (S0), el cual puede ser fácilmente interpretado en función del número de cláusulas que se satisfacen. A continuación se presenta la determinación del factor de garantía para la búsqueda local no obvia. 41 Asumiendo C0=0 [KhS96], se infiere que C2=2 y C1=3/2 y la función objetivo no obvia propuesta por Khanna será: además, el lado derecho de la desigualdad de la ecuación 4.2 será: 2∆1W(S0) = 2⋅(3/2) W(S0) = 3 W(S0) Quedando la ecuación 4.2 como: W(S2) + W(S1) ≥ 3W(S0) Dado que se había planteado la utilización de una función de peso simple, significando esto que W(Si) es simplemente igual al número de cláusulas pertenecientes al conjunto Si, se cumple que: W(S0) + W(S1) + W(S2) = m Nótese que el total de cláusulas insatisfechas, que denotaremos por INSAT, es: INSAT = W(S0) Y por tal, se tiene que al sumar W(S0) en ambos lados de la ecuación 4.2, nos genera la siguiente desigualdad. 4W(S0) ≤ m Esto inmediatamente implica que el total de cláusulas insatisfechas en un óptimo local no es mayor que ¼ del total de todas las cláusulas; esto es, el algoritmo asegura un factor de garantía de ¾ . A continuación se presenta la versión generalizada (para Max-k-SAT, donde k es el número máximo de literales que hay en alguna cláusula de la fórmula booleana de entrada) de la obtención del factor de garantía para la búsqueda local no obvia con la función objetivo propuesta por Khanna [KhS96]. Teorema 4.2 La búsqueda no obvia sobre 1-vecindad tiene un factor de garantía de (2k-1) / 2k para Max-k-SAT. Prueba: De nuevo, sin pérdida de generalidad, asumimos que las variables han sido renombradas de tal manera que cada literal no negada bajo la asignación actual se le asigna al valor verdadero. Así el conjunto Si es el conjunto de cláusulas con exactamente ‘i’ literales verdaderas. )(2)( 2 3 )()()()( 21221100 SWSWSWCSWCSWCzf NOB +=++= 42 Sea : ∆i = Ci – Ci-1 Y denotemos con: al cambio del valor de la función cuando cambiamos el valor de zj cuando esta variable pasa del valor uno a cero. Se obtiene que: Esto a partir del análisis en el cambio de valor de zj mostrado en la tabla 4.2. zj = 1 zj = 0 ∂f /∂zj C1-P1,j P1,j → P0,j - C0 (C0 – C1)P1,j = -∆1 P1,j C2-P2,j P2,j → P1,j - C1 (C1 – C2)P2,j = -∆2 P2,j : : : : : : Ck-1-Pk-1,j Pk-1,j →P k-2,j - Ck-2 (Ck-2 – Ck-1)Pk-1,j = -∆k-1 Pk-1,j Ck-Pk,j Pk,j → Pk-1,j - Ck-1 (Ck-1 – Ck)Pk,j = -∆k Pk,j C0-N0,j N0,j → N1,j - C1 (C1 – C0)N0,j = ∆1 N0,j C1-N1,j N1,j → N2,j - C2 (C2 – C1)N1,j = ∆2 N1,j : : : : : : Ck-2-Nk-2,j Nk-2-,j → Nk-1,j - Ck-1 (Ck-1 – Ck-2)Nk-2,j = ∆k-1 Nk-2,j Ck-1-Nk-1,j Nk-1,j → Nk,j - Ck (Ck – Ck-1)Nk-1,j = ∆k Nk-1,j Tabla 4.2 Análisis sobre el cambio de valor de una variable zj perteneciente a una asignación z. Y dado que sabemos que cuando el algoritmo termina, como z es un óptimo local, entonces: jz f ∂ ∂ j k i jiijiijkk j NPNP z f ,01 2 ,11,1, )( ∆+∆−∆+∆−=∂ ∂ ∑ = −−− 0≤ ∂ ∂ jz f , ∀j ∈ {1, ..., n} 43 Entonces se cumple que: La cual puede ser escrita como: Ecuación 4.3 Efecto del cambio de valor de la variable zj bajo un óptimo local. Sumando bajo todas las variables zj (j = 1,2,...,n) la desigualdad de la ecuación 4.3 se transforma en: ó y usando las igualdades, Se obtiene que: Despejando y factorizando, obtenemos la siguiente desigualdad: Ecuación 4.4 Relación entre el número de cláusulas satisfechas e insatisfechas. ∑ = −−− ≤∆+∆−∆+∆− k i jjiijiijkk NPNP 2 ,01,11,1, 0)( ∑ − = + ≤∆+∆−∆+∆− )1( 1 ,01,,1, 0)( k i jjiijiijkk NPNP ∑ = = n j iji SiWP 1 , )( ∑ = −= n j iji SWikN 1 , )()( ∑ − = + ≤∆+∆−∆−+∆− )1( 1 011 0)())()()(()( k i iiiikk SWkSWiSWikSWk ∑ − = +∆−−∆+∆≤∆ )1( 1 101 )())(()()( k i iiikk SWikiSWkSWk ∑∑ − = + = ≤∆+∆−∆+∆− )1( 1 ,01,,1, 1 0))(( k i jjiijiijkk n j NPNP ∑ ∑∑∑∑ − = === + = ≤∆+∆−∆+∆− )1( 1 1 ,01 1 , 1 ,1 1 , 0)( k i n j j n j jii n j jii n j jkk NPNP 46 se puede reescribir la ecuación de la siguiente manera: 5⋅INSAT ≤ SAT+W(S1) ≤ SAT+W(S0) = SAT+INSAT = m Obteniendo que, 5⋅INSAT ≤ m Esto inmediatamente implica que el total de cláusulas insatisfechas en éste óptimo local no es mayor que 1/5 del total de todas las cláusulas; esto es, el algoritmo asegura un factor de garantía de 4/5 para aquellas fórmulas que cumplen la condición expresada en la ecuación 4.6. A partir de este momento se puede afirmar que la calidad de soluciones que encuentre un algoritmo, que utilice la nueva función objetivo no obvia, será mejor que la de los algoritmos que utilicen la función objetivo no obvia introducida por Khanna. Hubo dos elementos que nos llevaron a pensar en que se puede definir una función objetivo no obvia diferente a la propuesta por Khanna, tales elementos fueron: 1.- El buscar que en el lado izquierdo de la ecuación 4.2 quede el valor SAT facilita la obtención del factor de garantía, además de que se cumple para toda fórmula booleana, sin embargo no explota totalmente la desigualdad ya que podemos encontrar diferentes relaciones entre W(S0) con W(S1) y/o W(S2) que permitirían obtener mejores factores de garantía. 2.- El análisis de los resultados que se obtenían por la búsqueda local basada en la función objetivo propuesta por Khanna, mostraba un decremento en el factor de aproximación con fórmulas donde había un gran número de cláusulas insatisfechas, esto mostraba que el coeficiente C0 era importante para esta clase de fórmulas y el hecho de que Khanna minimizara su importancia indicaba que no habían sido capturados todos los parámetros que influyen en la técnica. Los resultados teóricos obtenidos en esta sección han sido corroborados en la práctica. En la sección siguiente presentamos los resultados del análisis empírico realizado a los algoritmos: LS, LS-N, LS-NC0 y LS-NTA, trabajando éstos sobre fórmulas booleanas en k-FNC generadas aleatoriamente. 4.2 Análisis experimental El análisis experimental sobre los algoritmos: LS, LS-N, LS-NC0 y LS-NTA consideró dos clases de instancias: por una parte, se retomaron un conjunto de instancias en 2-FNC generadas por Altamirano [AlL96] y que se presentan en la tabla 4.3 (de aquí en adelante las llamaremos ALT2SAT), y que resultaron ser útiles para mostrar que la calidad 47 de los resultados obtenidos son competitivos con los que se obtienen al aplicar técnicas basadas en programación semidefinida [GoM94],[GoM94a] y el algoritmo ávido de Johnson [JoD74]. El grupo de instancias ALT2SAT está formado por pequeños grupos de instancias distribuidos como se muestra en la tabla 4.3, los resultados obtenidos mostraban que estas instancias no eran lo suficientemente difíciles; lo que llevó a considerar otra clase de instancias para realizar el análisis empírico. Se hizo uso de uno de los modelos para la construcción aleatoria de instancias de formulas booleanas presentado en el capítulo III; este modelo se conoce con el nombre de “Modelo exacto k-SAT” y la técnica consiste en construir una fórmula en FNC, formando cada cláusula de manera independiente a las demás. Cada cláusula debe contener exactamente k literales. Cada literal l es uniformemente elegida sin reemplazo del conjunto de variables, por ejemplo para u∈U, Prob(l=u) = 1 / |U|, y la probabilidad de que la variable elegida tenga una ocurrencia negativa es p (parámetro de entrada, que en este caso, se utilizó con un valor de ½). Mediante el modelo exacto k-SAT se generó un grupo de 160 instancias del tipo 2-FNC y un grupo de 160 instancias del tipo 3-FNC (de aquí en adelante las llamaremos INS2SAT e INS3SAT respectivamente). Las 160 instancias de INS2SAT y las de INS3SAT se agruparon de la manera que se muestra en la tabla 4.4. Grupo Instancias (F) n – No. de variables m – No. de cláusulas 1 De la instancia 1 a la instancia 10 15 variables 25 cláusulas 2 De la instancia 11 a la instancia 20 15 variables 50 cláusulas 3 De la instancia 21 a la instancia 30 15 variables 75 cláusulas 4 De la instancia 31 a la instancia 40 15 variables 100 cláusulas 5 De la instancia 41 a la instancia 50 20 variables 25 cláusulas 6 De la instancia 51 a la instancia 60 20 variables 50 cláusulas 7 De la instancia 61 a la instancia 70 20 variables 75 cláusulas 8 De la instancia 71 a la instancia 80 20 variables 100 cláusulas 9 De la instancia 81 a la instancia 90 25 variables 25 cláusulas 10 De la instancia 91 a la instancia 100 25 variables 50 cláusulas 11 De la instancia 101 a la instancia 110 25 variables 75 cláusulas 12 De la instancia 111 a la instancia 120 25 variables 100 cláusulas Tabla 4.3 Distribución de variables y cláusulas para el grupo de instancias ALT2SAT. 48 Grupo Instancias (F) n – No. de variables m – No. de cláusulas 1 De la instancia 1 a la instancia 10 25 variables 50 cláusulas 2 De la instancia 11 a la instancia 20 25 variables 75 cláusulas 3 De la instancia 21 a la instancia 30 25 variables 100 cláusulas 4 De la instancia 31 a la instancia 40 25 variables 125 cláusulas 5 De la instancia 41 a la instancia 50 50 variables 100 cláusulas 6 De la instancia 51 a la instancia 60 50 variables 150 cláusulas 7 De la instancia 61 a la instancia 70 50 variables 200 cláusulas 8 De la instancia 71 a la instancia 80 50 variables 250 cláusulas 9 De la instancia 81 a la instancia 90 75 variables 150 cláusulas 10 De la instancia 91 a la instancia 100 75 variables 225 cláusulas 11 De la instancia 101 a la instancia 110 75 variables 300 cláusulas 12 De la instancia 111 a la instancia 120 75 variables 375 cláusulas 13 De la instancia 121 a la instancia 130 100 variables 200 cláusulas 14 De la instancia 131 a la instancia 140 100 variables 300 cláusulas 15 De la instancia 141 a la instancia 150 100 variables 400 cláusulas 16 De la instancia 151 a la instancia 160 100 variables 500 cláusulas Tabla 4.4 Tamaño de las instancias construidas tanto para INS2SAT como para INS3SAT. Como se puede observar, cada renglón en las tablas 4.3 y 4.4 representa un grupo conformado por 10 instancias (fórmulas) diferentes con el mismo número de variables y el mismo número de cláusulas. Para realizar el análisis empírico, primeramente se obtuvo el valor exacto de MaxSAT para cada instancia (el número máximo de cláusulas que pueden satisfacerse para cada instancia), posteriormente se ejecutó 10 veces cada algoritmo sobre cada instancia, los resultados obtenidos de las 10 ejecuciones sobre una instancia dada se promediaron y posteriormente se dividió este promedio entre el valor exacto de la instancia, dándonos el cociente de aproximación para la instancia, el cociente de aproximación obtenido en cada instancia del grupo de 10 instancias del mismo tipo se promedia con los 10 cocientes de aproximación del grupo, y el resultado es el que se presenta como cociente de aproximación en la tabla 4.5, en este caso particular, para el grupo de instancias denominado ALT2SAT. El mismo proceso se sigue para obtener los cocientes de aproximación de cada uno de los algoritmos probados sobre las instancias: INS2SAT e INS3SAT, con la diferencia de que el cociente de aproximación no puede ser obtenido sobre las instancias que poseen más de 75 variables por cláusula, debido a la dificultad de obtener el valor exacto, así que, para este tipo de instancias, el procedimiento seguido fue dividir el promedio del valor obtenido de ejecutar 10 veces cada instancia entre el número total de cláusulas en la formula; el resto del proceso es igual. 51 Figura 4.3 Cociente de aproximación de los algoritmos para 2-FNC con 25 variables. Promedio del número de cambios Grupo Variables Cláusulas LS LS-N LS-NCo LS-NTA 1 15 25 86.2 46.89 49.36 100.55 2 15 50 60.4 42.21 44.75 102.7 3 15 75 58.01 40.61 41.92 109.04 4 15 100 63.63 40.19 43.08 106.26 5 20 25 343.25 96.85 102.18 132.14 6 20 50 174.66 81.06 77.76 138.08 7 20 75 130.26 72.69 80.96 132.86 8 20 100 142.07 72.3 77.17 158.68 9 25 50 544.6 139.95 142.69 176.52 10 25 75 322.38 97.45 103.6 187.38 11 25 100 269.71 105.15 119.35 176.66 12 25 125 205.18 83.14 90.19 194.79 Tabla 4.6 Promedio del número de cambios realizados por cada algoritmo sobre las instancias: ALT2SAT. 50 75 100 125 Número de Cláusulas 0.984 0.988 0.992 0.996 C oc ie nt e d e A pr ox im ac ió n LS-NTA LS-NCo LS-N LS 100 120 e C am bi os 52 Figura 4.4 Promedio del número de cambios realizados por cada algoritmo para 2-FNC con 15 variables. Figura 4.5 Promedio del número de cambios realizados por cada algoritmo para 2-FNC con 25 variables. Cociente de Aproximación 50 75 100 125 Número de Cláusulas 0 200 400 600 P ro m ed io d e l N úm er o de C am bi os LS-NTA LS-NCo LS-N LS 53 Grupo Variables Cláusulas LS LS-N LS-NCo LS-NTA 1 25 50 0.978 0.994 0.994 0.997 2 25 75 0.939 0.942 0.943 0.945 3 25 100 0.91 0.907 0.91 0.916 4 25 125 0.906 0.9 0.907 0.917 5 50 100 0.949 0.958 0.959 0.961 6 50 150 0.927 0.929 0.932 0.937 7 50 200 0.918 0.918 0.92 0.926 8 50 250 0.897 0.893 0.898 0.903 9 75 150 0.953 0.959 0.96 0.963 10 75 225 0.921 0.923 0.924 0.928 11 75 300 0.911 0.909 0.913 0.918 12 75 375 0.899 0.897 0.902 0.904 13 100 200 0.957 0.963 0.967 0.969 14 100 300 0.926 0.928 0.932 0.935 15 100 400 0.913 0.916 0.917 0.92 16 100 500 0.897 0.897 0.901 0.901 Tabla 4.7 Cocientes de aproximación de los algoritmos sobre las instancias INS2SAT. Figura 4.6 Cociente de aproximación de los algoritmos para 2-FNC con 25 variables. 50 75 100 125 Número de Cláusulas 0.88 0.92 0.96 1.00 C oc ie nt e d e A pr ox im ac ió n LS-NTA LS-NCo LS-N LS 0 94 0.96 0.98 m ac ió n 56 Figura 4.10 Promedio del número de cambios realizados por cada algoritmo para 2-FNC con 25 variables. Figura 4.11 Promedio del número de cambios realizados por cada algoritmo para 2-FNC con 100 variables. Cociente de Aproximación Grupo Variables Cláusulas LS LS-N LS-NCo LS-NTA 1 25 50 0.999 1 1 1 200 300 400 500 Número de Cláusulas 0 2000 4000 6000 8000 10000 P ro m ed io d e l N úm er o de C a m bi o s LS-NTA LS-NCo LS-N LS 57 2 25 75 0.997 0.999 0.999 1 3 25 100 0.982 0.985 0.986 0.988 4 25 125 0.975 0.978 0.979 0.981 5 50 100 0.995 0.997 0.999 1 6 50 150 0.989 0.995 0.996 0.997 7 50 200 0.982 0.986 0.987 0.991 8 50 250 0.975 0.979 0.98 0.982 9 75 150 0.996 0.999 1 1 10 75 225 0.988 0.992 0.993 0.994 11 75 300 0.985 0.989 0.989 0.993 12 75 375 0.975 0.978 0.979 0.981 13 100 200 0.996 1 1 1 14 100 300 0.989 0.995 0.996 0.997 15 100 400 0.983 0.982 0.986 0.99 16 100 500 0.976 0.979 0.981 0.983 Tabla 4.9 Cocientes de aproximación de los algoritmos sobre las instancias: INS3SAT. Figura 4.12 Cociente de aproximación de los algoritmos para 3-FNC con 25 variables. 50 75 100 125 Número de Cláusulas 0.975 0.980 0.985 0.990 0.995 1.000 C oc ie nt e d e A pr ox im ac ió n LS-NTA LS-NCo LS-N LS 58 Figura 4.13 Cociente de aproximación de los algoritmos para 3-FNC con 50 variables. Figura 4.14 Cociente de aproximación de los algoritmos para 3-FNC con 75 variables. 100 150 200 250 Número de Cláusulas 0.975 0.980 0.985 0.990 0.995 1.000 C oc ie nt e d e A pr ox im ac ió n LS-NTA LS-NCo LS-N LS 150 225 300 375 Número de Cláusulas 0.975 0.980 0.985 0.990 0.995 1.000 C oc ie nt e d e A pr ox im ac ió n LS-NTA LS-NCo LS-N LS 61 En estos casos, el cociente de aproximación de LS-N está por debajo de los demás algoritmos, incluso de la búsqueda local sola (LS). En las gráficas se puede observar que este comportamiento puede ser corregido utilizando la nueva función objetivo que proponemos. Como ya se ha comentado, el número de cláusulas insatisfechas (para cláusulas donde existen una gran cantidad de ellas) tiene un peso importante en el comportamiento de la búsqueda, y el hecho que la función objetivo propuesta por Khanna no considere este punto no le permite capturar dicha propiedad (al hacer el coeficiente C0=0 en ∑ = = k i iiNOB SWCzf 0 )()( ). El análisis de estos casos nos llevó a experimentar con diferentes valores para C0, y nos permitió inferir que su signo debería ser opuesto al de los otros coeficientes, el análisis teórico nos confirmó tal conjetura. El algoritmo resultante que denominamos LS-NC0, mostró en la práctica un mejor comportamiento que LS y LS-N. Con el fin de acelerar el proceso de búsqueda, se le adicionó a LS-NC0 dos heurísticas: una estrategia tabú y el uso de puntos antipodales como punto para re-iniciar la búsqueda después de arribar a óptimos locales, al algoritmo resultante se le llamó: LS-NTA. El análisis sobre el comportamiento en la práctica de LS-NTA mostró que el uso de elementos antipodales para re-iniciar la búsqueda permite ampliar el dominio de ésta y en general, salta sobre caminos ya explorados. Si a esto añadimos una lista de los óptimos locales hallados para evitar ciclos (tabú), obtenemos una propuesta algorítmica que resultó ser robusta y, que de acuerdo al resultado del análisis empírico, mejora el comportamiento de los procedimientos basados en la búsqueda local. El análisis experimental realizado, mostró que la aplicación de las estrategias: búsqueda tabú y uso de puntos antipodales, mejora en la práctica la calidad de las soluciones halladas. Así también, se corrobora los resultados obtenidos en la sección 4.1, en donde se determinó mediante el factor de garantía que la nueva propuesta LS-NC0 tendría un mejor comportamiento que LS y LS-N. 62 Conclusiones El objetivo de la demostración automática de teoremas (DAT) es diseñar algoritmos eficientes para demostrar la validez de una fórmula. Para el caso del cálculo proposicional, es bien sabido que la complejidad en tiempo de algoritmos dentro de la DAT para fórmulas booleanas generales es de orden exponencial y, consecuentemente, existen aún limitaciones para demostrar teoremas o probar satisfactibilidad en forma automática de manera eficiente. El problema de Máxima Satisfactibilidad (MaxSAT) es un problema central en la DAT y en la teoría de complejidad computacional. Existe un gran interés en la búsqueda de algoritmos eficientes para la resolución de este problema. El hecho de que MaxSAT sea un problema representativo de su clase de complejidad (APX), implica que cualquier mejora que se encuentre a los algoritmos que resuelven MaxSAT, puede transformarse en mejoras a algoritmos que resuelvan los demás problemas de su clase de complejidad. Aun más, el hallar un algoritmo eficiente para este problema, repercute en la resolución de problemas abiertos trascendentales en las ciencias de la computación, tal como la pregunta abierta: ¿P = NP? En esta investigación se analizaron diferentes propuestas algorítmicas basadas en la búsqueda local para solucionar el problema de MaxSAT, debido a que el objetivo principal del trabajo fue proponer un nuevo algoritmo basado en búsqueda local aplicado a la resolución del problema MaxSAT, así como determinar su factor de garantía, para mostrar que éste era competitivo con los algoritmos ya conocidos. En este trabajo se construyeron dos algoritmos clásicos, de los cuales se ha determinado su factor de garantía. Para una fórmula booleana F (donde k es el número máximo de literales por cláusula), se tiene que la búsqueda local obvia (LS) obtiene un factor de garantía de k/k+1, mientras que la búsqueda local no obvia (LS-N) obtiene un factor de garantía de (2k-1)/2k. Partiendo de estos dos algoritmos, proponemos uno nuevo al que denominamos: LS -NC0, basado fundamentalmente en una modificación al coeficiente C0 de la función objetivo propuesta por Khanna[KhS96] (sobre LS-N). Se demostró analíticamente que nuestra propuesta obtiene un factor de garantía de 4/5 para Max2SAT, para ciertas clases de fórmulas, según se especificó en el capítulo II, mejorando el factor de ¾ del algoritmo propuesto por Khanna. Posteriormente, con el fin de agilizar el proceso de búsqueda se adicionaron dos estrategias: una heurística tabú y el uso de elementos antipodales para re-iniciar la búsqueda después de arribar a óptimos locales. Esta nueva propuesta, que denominamos LS-NTA, mostró según el análisis empírico realizado y mostrado en el capítulo IV, que obtiene los mejores resultados de todos los algoritmos desarrollados. 63 Todos los algoritmos presentados preservan la complejidad polinomial en tiempo y mejoran el comportamiento general de la búsqueda local clásica. De estos algoritmos analizados, LS-NC0 y LS-NTA son propuestas originales de este trabajo. El éxito del algoritmo LS-NTA está determinado primero por su habilidad para moverse a través de la fase de ‘meseta’ de la búsqueda, reduciendo el tiempo de ésta fase y, segundo, por el uso de elementos antipodales del último óptimo local hallado como nuevo punto de re-inicio de la búsqueda, dando así amplitud al dominio de ésta. Es de particular importancia mencionar el comportamiento del algoritmo LS-N (propuesto por Khanna[KhS96]), ya que se observa que el rendimiento decrece sobre cierto tipo de instancias donde hay un gran número de cláusulas insatisfechas. En estos casos, el cociente de aproximación de LS-N está por debajo de los demás algoritmos, incluso de la búsqueda local sola (LS). En las gráficas se puede observar que este comportamiento se corrigió utilizando la nueva función objetivo no obvia (aunque estos resultados son empíricos). Parte de la explicación de este comportamiento es que LS-N no contempla en su función objetivo al conjunto de cláusulas S0, es decir, el conjunto de cláusulas que no se satisfacen, así que cuando las instancias son grandes (tienen un mayor número de cláusulas), es evidente que se incrementa el número de cláusulas que no se satisfacen, en este caso, la función objetivo de LS-N empieza a carecer de elementos para discriminar correctamente entre dos asignaciones similares y decidir cual asignación es mejor en la búsqueda de la solución del problema. En nuestro caso, fue suficiente incluir una nueva función objetivo donde el coeficiente C0=-1, sin embargo, aún queda pendiente determinar en detalle la razón de este comportamiento. Se demostró que en la nueva función objetivo no obvia se obtiene un factor de garantía mejor que en la función objetivo no obvia propuesta por Khanna, esto para el tipo de instancias que cumplen que W(S1) ≤ p⋅W(S0), p∈ℜ+. El análisis empírico realizado a LS-NC0 verifica los resultados obtenidos a través del análisis teórico. Las gráficas y las tablas presentadas en la segunda sección del capítulo IV muestran los resultados obtenidos del análisis empírico, se observa que la propuesta LS-NTA obtiene en todos los casos un mejor cociente de aproximación que los demás algoritmos. Esto debido principalmente al control de la trayectoria de búsqueda a través de los antipodales. Se puede observar además que el uso de elementos antipodales para re-iniciar la búsqueda permite ampliar el dominio de ésta y en general, saltar sobre caminos ya explorados. Si a esto añadimos una lista de los óptimos locales hallados para evitar caer en ciclos, obtenemos una propuesta algorítmica que resulta ser robusta y, que de acuerdo al resultado del análisis empírico mejora el comportamiento de los procedimientos basados en la búsqueda local. Aunque, el análisis empírico resulta ser una herramienta valiosa para determinar el comportamiento de un algoritmo, el análisis teórico determina con exactitud éste, es por 66 [GoM94a] Goemans M. X., Williamson D. P., ¾-Approximation Algorithms for the Maximum Satisfiability Problem, SIAM Journal of Discrete Mathematics, Vol. 7, No. 4, 1994. [GuJ93] Gu J., Local Search for Satisfactibility (SAT) Problem, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 23, No. 4, July / Autugst 1993. [GuJ94] Gu J., Global optimization for Satisfactibility (SAT) Problem, IEEE Transaction on Knowledge and Data Engineering, Vol. 6, No.3, 361-381, June 1994. [HaJ65] Hartmanis J., Stearns R., On the computational complexity of algorithms, Trns. Am. Math. Soc., 177 285-306, 1965. [HaP90] Hansen P., B Jaumard, Algorithms for the Maximum SATisfiability Problem, Computing 44, 279-303, 1990. [HoJ93] Hopcroft John E., Ullman Jeffrey D., Introducción a la Teoría de Autómatas, Lenguajes y Computación, CECSA 1993. [ImN95] Immerman N., Descriptive Complexity: a Logician’s Approach to Computation. In Notices of the American Mathematical Society, 42(10): 1127-1133, 1995. [JoD74] Johnson D. S., Approximation Algorithms for Combinatorial Problems. Journal of Computer and System Sciences, vol. 9, pp. 256-278, 1974. [KaA94] Kamath A., Motwani R., Khisna P., Spirakis P., Tail Bounds for Occupancy and the Satisfiability Threshold Conjecture, Proc. 35th Annual Symp. On Foundations of Computer Science, 1994. [KaR72] Karp R. M., Reducibility among combinatorial problems. In Complexity of Computer Computations (R.E. Miller and J.W. Thatcher, Eds.), pp. 85-103, Plenum, New York, 1972. [KhS95] Khanna Sanjeev, R. Motwani, M. Sudan and U. Vazirani, On Syntactic versus Computational Views of Approximability, TR95-023 ECCC Electronic Colloquium on Computational Complexity, Series 1995, pp. 13. [KhS96] Khanna S., A structural view of approximation. Dissertation submitted to the department of computer science and the committee on graduate studies of stanford university, 1996. [LeL73] Levin L. A., Universal sorting problems. Problems of Information Transmission, 9, pp. 265-266, 1973. [ReC93] Reeves C. R., Modern Heuristic Techniques for Combinatorial Problems, John Wiley & Sans, Inc., 1993. 67 [StL87] Stockmeyer L. J., Classifying the Computational Complexity of Problems, The Journal of Symbolic Logic, March 1987. [TuA36] Turing A. On computable numbers, with an application to the entscheidungs problem. Proc. London Math. Soc. Ser. 2, 42 and 43, 1936. 68 Lista de acronismos SAT Problema de satisfactibilidad. MaxSAT Versión de optimización del problema de satisfactibilidad. Max-k-SAT MaxSAT, donde se utilizan fórmulas que poseen k literales por cláusula. DAT Demostración automática de teoremas. FNC Fórmula en forma normal conjuntiva. FND Fórmula en forma normal disyuntiva. k-FNC FNC donde hay exactamente k literales por cláusula. MTD Máquina de Turing determinista. PD Problema de decisión. MTND Máquina de Turing no determinista. RAM Máquinas de acceso aleatorio. DLOG Clase de complejidad para la que existe una MTD que resuelve un PD usando espacio logarítmico. NLOG Clase de complejidad para la que existe una MTND que comprueba soluciones de PD usando espacio logarítmico. PSPACE Clase de complejidad para la que existe una MTD que resuelve un PD usando espacio polinomial. NPSPACE Clase de complejidad para la que existe una MTND que comprueba soluciones de PD usando espacio polinomial. P Es la clase de problemas que poseen algoritmos deterministas de resolución que tardan tiempo polinomial. NP Es la clase de problemas que tienen un algoritmo determinista de resolución que corre en tiempo exponencial, pero para los cuales, también existe un algoritmo no determinista que corre en tiempo polinomial. NPO Problemas de optimización derivados de problemas en NP. APX Clase de complejidad que posee problemas cuyos algoritmos de resolución tienen un factor de garantía acotado por una constante. PTAS Clase de problemas con esquemas de aproximación de tiempo polinomial. Clase de complejidad que posee problemas cuyos algoritmos de resolución tienen un factor de garantía acotado por (1+ε). f-APX Clase de problemas en NPO que son aproximables dentro de un factor f. poly-APX Clase de problemas en NPO que tienen algoritmos de aproximación con un factor de garantía acotado polinomialmente, con respecto a la longitud de entrada. log-APX Clase de problemas en NPO que tienen algoritmos de aproximación con un factor de garantía acotado logarítmicamente, con respecto a la longitud de entrada.