La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

Archive for the ‘Optimización Combinatoria’ Category

Computación humana para automatización de diseño electrónico

Posted by Carlos en agosto 10, 2009

El artículo que describe el trabajo del que hablábamos hace algo más de una semana sobre la resolución del instancias de SAT mediante un juego está ya disponible online. Se trata de

de Andrew DeOrio y Valeria Bertacco. El artículo es muy corto, sólo dos páginas, y no proporciona muchos más detalles acerca del sistema. Sí menciona algún aspecto de interés, como es el hecho de que la disposición espacial de las cláusulas intenta corresponderse con las variables que la afectan (lamentablemente no entra en detalles sobre cómo  han atacado este extremo, ya que es un problema de optimización geométrica muy interesante).

Con todo, lo más relevante del artículo sean las referencias a la escalabilidad (que ya anticipamos el otro día como uno de los cuellos de botella del enfoque). Al parecer, la idea básica es que cada nivel sea una visión local de una parte del problema completo, visión que se irá ampliando al ir aumentando de dificultad. En instancias de gran tamaño sugieren emplear un enfoque multi-jugador en el que cada participante juega sobre una parte del problema. Obviamente hay interrelaciones entre estas partes (si modificamos una variable podemos alterar el estado de una cláusula de otro tablero), por lo que la división debería hacerse de manera astuta de forma que estas interrelaciones sean mínimas. La mala noticia es que tendríamos entonces un problema de corte mínimo en grafos, que es NP-hard si se introducen restricciones sobre el número de interrelaciones entre subconjuntos.

Posted in Complejidad, Juegos, Optimización Combinatoria | Etiquetado: , , , , | 1 Comment »

Resuelve problemas NP-completos mientras juegas

Posted by Carlos en julio 29, 2009

La clase NP -de la que ya hemos hablado en alguna ocasión- abarca aquellos problemas de decisión que pueden resolverse en tiempo polinómico no determinista, o lo que es lo mismo, aquellos problemas para los que es posible verificar en tiempo polinómico la validez de una solución dada. Esta clase ha sido tradicionalmente empleada como sucedáneo de la idea de intratabilidad computacional. No se trata de la mejor caracterización, ni siquiera de la más apropiada, puesto que admite mucha patología y en ocasiones tiene un impacto práctico limitado, pero eso será tema de algún futuro post. Sea como fuere, es común que allá donde nos enfrentemos a un problema NP-hard se emplee este hecho como justificación para el empleo de algún tipo de (meta)heurística.

Nuestra comprensión sobre cómo aplicar metaheurísticas para resolver problemas específicos ha avanzado enormemente en la última década. Una de las claves está en ser capaces de explotar conocimiento del problema durante el proceso de búsqueda. Técnicas tales como los algoritmos meméticos se basan fundamentalmente en esta idea. Evidentemente no se trata de algo trivial de conseguir, y aquí es donde es posible que la mente humana eche una mano y no en la ingeniería del proceso sino contribuyendo capacidad de búsqueda pura y dura. No se trata por supuesto de cálculo numérico ni de búsqueda sistemática, sino de explotar algunas de las cualidades que nuestros cerebros han ido desarrollando durante millones de años de evolución: estrategia y procesamiento visual.

La capacidad de extraer información de un torrente de datos visuales es una de nuestras grandes bazas. Estamos programados para buscar orden en el caos, patrones en el ruido blanco, formas conocidas en el desorden. Áreas tales como la minería de datos visual intentan explotar precisamente esta característica. Por otra parte nuestra visión estratégica, la capacidad de trazar planes y seleccionar heurísticamente las ramificaciones más relevantes es también bien conocida en el ámbito -por ejemplo- de los juegos de tablero. Es precisamente en este área en el que investigadores de la Universidad de Michigan han intentado aunar ambas capacidades y dirigirlas hacia la resolución de problemas NP-completos. Andrew DeOrio y Valeria Bertacco, del departamento de ingeniería eléctrica e informática de la citada universidad, han desarrollado un entorno en el que se pueden resolver instancias del problema de la satisfacibilidad lógica mediante un juego lejanamente relacionado con el clásico lights off.

FunSAT - Pulsa sobre la imagen para jugar

FunSAT - Pulsa sobre la imagen para jugar

En el tablero tenemos una matriz de burbujas que representan las cláusulas de la instancia del problema (esto es, las restricciones que debemos satisfacer). Estas cláusulas dependen de un conjunto de variables, representadas como rectángulos en los bordes del tablero. Pulsando sobre éstos podemos fijar una cierta variable a cierto/falso o dejarla indefinida. De resultas de cualquiera de estas acciones algunas cláusulas pasarán a estar satisfechas (lo que se indicará mediante el color verde) o insatisfecha (un tono grisáceo, tanto más oscuro cuantas menos variables que puedan afectar a dicha cláusula nos queden sin asignar). El tamaño de cada burbuja indica el número de variables que intervienen en ella (se puede jugar también a 3-SAT, variante clásica en la que todas las cláusulas tienen 3 variables involucradas).

Lo interesante es que las instancias de SAT que se plantean en este juego corresponden supuestamente a problemas de diseño VLSI.  El análisis de lo que el juego puede dar de sí lo han publicado en un artículo titulado

  • Human computing for EDA

que presentarán en la próxima Design Automation Conference, que se celebra en San Francisco en estos días. El artículo aún no está disponible, por lo que se puede añadir poco más a lo ya comentado. Esperaremos a leerlo para ver cuál es el planteamiento a largo plazo del invento, que a priori diríase que adolece de un problema de escalabilidad. Y es que el ser humano es extraordinario, pero dentro de un límite.

Posted in Complejidad, Juegos, Optimización Combinatoria | Etiquetado: , , , | 2 Comments »

La vuelta al mundo en 10 minutos (o en 156 días)

Posted by Carlos en octubre 24, 2007

El Degree Confluence Project es una curiosa iniciativa colaborativa consistente en visitar y tomar fotografías de todos los puntos del globo terráqueo con latitud y longitud enteras, esto es, de los puntos en los que se cruzan paralelos y meridianos correspondientes a un número entero (i.e., sin decimales) de grados de latitud o longitud respectivamente. Dado que la longitud puede tomar 360 valores enteros, y que la latitud puede tomar 181 (de 1º a 90º N o S, más el Ecuador), pero hay que descontar los polos en los que no hay variación de longitud, tenemos 360 x 179 + 2 = 64,442 confluencias. De éstas, una gran parte (más de 39,000) estarán en mitad de los mares u océanos, o se apiñarán cerca de los polos. Las restantes se hallan en tierra firme, o cerca de la costa, y definen una cuadrícula uniformemente distribuida por todos los continentes. Pueden considerarse en cierta medida como una muestra sistemática de lo que hay sobre la faz de la Tierra (de la tierra firme, claro).

Una vez identificados estos puntos, cabría considerar la tarea de dar una auténtica vuelta al mundo. No sólo circumnavegar el planeta, sino visitar cada pedacito de tierra firme del mismo, asumiendo estas confluencias como representativas de un área de ±0.5º de latitud/longitud (0.5º representa menos de 60 km en cualquiera de las cuatro direcciones principales en el Ecuador; en otros puntos la distancia E/W es todavía menor debido a la convergencia de los meridianos), lo que no parece descabellado. Tenemos entonces una instancia de nuestro bien conocido problema del viajante de comercio (TSP) con 16,189 “ciudades”. El vídeo inferior muestra un camino óptimo para recorrer todos estos puntos y volver al punto de partida. La longitud total del camino es de 1,628,716 km, lo que supone unos 156 días sin parar en una avioneta como la Mooney Acclaim.

La resolución del problema se ha realizado mediante Concorde, un paquete de optimización para el TSP que incorpora técnicas exactas tales como ramificación y corte, y heurísticas como el algoritmo de Lin-Kernighan. Es fácil ver que la solución óptima a una instancia del TSP sobre un plano no tendrá aristas que se crucen. La eliminación de estos cruces es precisamente una de las heurísticas más simples y efectivas para mejorar una solución obtenida mediante algún otro método. De hecho, es muy común incorporar una heurística de este tipo dentro de alguna otra metaheurística, e.g, un algoritmo genético. Estamos entonces hablando de algoritmos meméticos, a los que les dedicaremos algo más de tiempo más adelante.

Posted in Viajar, Lugares, Computación Evolutiva, Optimización Combinatoria, Algorítmica | Etiquetado: , , | Comentarios desactivados

Fomentando las redes sociales

Posted by Carlos en julio 9, 2007

Aunque la organización del congreso es francamente mejorable (ya habrá ocasión de dar un repaso general al final de la misma), hoy nos han sorprendido con un detalle curioso: un programa personalizado en el que indican a cada uno qué presentaciones pueden ser de su interés, e incluso a qué gente debería intentar conocer. El mecanismo que han empleado no es muy sofisticado a priori: se buscan coincidencias entre las palabras clave que cada cual introduce en los trabajos que presenta, o que proporcionó al registrarse en el congreso. Claro que la cosa puede hacerse más complicada si se tiene en cuenta que a todo el mundo se le proporciona una lista de n personas, y que debe maximizarse el ajuste global de las recomendaciones, sujeto a la restricción de que todo el mundo sea recomendado un número similar de veces (o al menos una vez). No se si lo hacen así, y de hecho me temo que no es el caso, dado que eso plantearía un interesante problema de optimización, y que la organización no está siendo desbordantemente buena.

En mi caso, de la gente que me recomiendan ya conocía a una persona de anteriores ocasiones, y otra de ellas se nos acercó ayer tras el tutorial (lo que es un punto a favor de la lista, ya que todavía no la teníamos). En lo que posiblemente no han pensado es que encontrar a una persona la que no conoces físicamente en un congreso de estas dimensiones es tarea complicada (salvo que presente algún artículo, y puedas ir a tiro fijo), pero bueno, la intención es lo que cuenta.

Posted in Optimización Combinatoria, Sistemas Complejos | 4 Comments »

Transiciones de fase: una lección vital

Posted by Carlos en febrero 7, 2007

El término científico transición de fase es muy interesante. Una transición de fase en un sistema indica un cambio brusco en sus propiedades al sobrepasar cierto valor crítico en alguna variable de control del mismo. Los ejemplos más habituales nos los encontramos en física. Consideremos por ejemplo el agua. A temperatura ambiente es líquida, pero si reducimos la temperatura por debajo de 0ºC se congela y pasa a ser sólida. Este cambio es brusco, esto es, el agua no empieza a espesarse, convirtiéndose en una especie de melaza cada vez más consistente a medida que baja la temperatura, sino que cristaliza rápidamente, en lo que se tarda en alcanzar el equilibrio térmico entre diferentes partes del líquido. Otro tanto podemos conseguir jugando por ejemplo con la presión del líquido en lugar de con la temperatura. Matemáticamente, podríamos decir que se produce una discontinuidad en las propiedades del sistema al pasar de una fase a otra, típicamente por haber alguna singularidad en alguna de dichas propiedades o en sus derivadas.

El fenómeno de las transiciones de fase no es particular de la física ni mucho menos. Son muy frecuentes por ejemplo en el área de la matemática discreta, y en particular en teoría de grafos o en optimización combinatoria. Podemos considerar un ejemplo bien simple: el problema de la sastisfacibilidad lógica (SAT). Imaginemos que tenemos una fórmula lógica, e.g., (x1 or ~x2 or ~x3) and (x1 or x2 or x4). Esta fórmula lógica está expresada en forma normal conjuntiva, es decir, tenemos un conjunto de cláusulas unidas por la conectiva and, cada una de las cuales es un conjunto de literales (variables lógicas o su negación, que pueden tomar un valor verdadero o falso) unidos por la conectiva or. El problema consiste en determinar si existe una asignación de valores (verdadero o falso) a las variables lógicas de manera que la fórmula sea cierta (i.e., que todas las cláusulas sean ciertas). En el ejemplo anterior, cualquier asignación que incluya x1 = verdadero valdría (no sería ésta la única solución en este ejemplo).

Puede parecer que no es difícil determinar si una fórmula lógica es satisfacible o no, y la verdad es que en la práctica esto es cierto. Por supuesto, si el número de variables crece mucho, el problema se hace pesado, pero no inherentemente difícil. De hecho, hay algoritmos que son capaces de resolver rápidamente el problema para miles de variables. A pesar de esto, el problema SAT es el ejemplo paradigmático de la clase de problemas NP: dada una fórmula arbitraria, en el peor caso no existe ningún algoritmo conocido que demuestre su satisfacibilidad o insatisfacibilidad en tiempo polinomial en el tamaño del problema (esto es, si el tamaño es n, en tiempo acotado por nc, donde c es una constante). ¿Cómo es eso posible en este problema? Pues porque hay una transición de fase de por medio.

Analicemos el problema para un número de variables fijo, en función del número de cláusulas que tiene. Si este número es muy pequeño, el problema será muy probablemente satisfacible, ya que tenemos muchos grados de libertad (variables cuyos valores podemos fijar), y pocas restricciones (cláusulas). Por el contrario, si el número de cláusulas es muy alto, la sitación es la inversa, y el problema es muy probablemente no satisfacible. ¿Que ocurre con valores intermedios? Ahí está lo interesante. Una instancia cualquiera del problema sigue siendo con probabilidad cercana a 1.0 satisfacible aunque aumentemos el número de cláusulas, hasta que llegamos a una relación entre el número de cláusulas y el número de variables de entre 4 y 5 cláusulas por variable. Ahí se pasa rápidamente a instancias que son insatisfacibles con probabilidad cercana a 1.0. El punto crítico está en aproximadamente de 4.24 cláusulas por variable (suponiendo siempre que cada cláusula tiene 3 literales). Una instancia situada ahí es prácticamente satisfacible/insatisfacible con el 50% de probabilidad.

SAT probability of satisfiability

La imagen superior está tomada de un trabajo clásico de D. Mitchell, B. Selman, y H. Levesque, publicado en la décima conferencia de la American Association for Artificial Intelligence, y titulado:

La resolución del problema es muy fácil en general, ya que un algoritmo especializado se da cuenta enseguida de si hay solución o no, salvo cuando estamos en la zona en la que se produce la transición de fase. En ella, la eficiencia de los algoritmos de resolución es enormemente limitada, y se ven obligados a explorar una cantidad significativa (no polinomial) de las posibles soluciones al problema. Se habla en este caso de una transición de fase fácil-difícil-fácil, ya que a medida que nos desplazamos por el eje X visitamos fugazmente una zona de dificultad entre dos amplias regiones de fácil resolución.

La belleza de este tipo de fenómenos está en lo que aprendemos de ellos, y luego podemos aplicar a nosotros mismos. En numerosas ocasiones nuestra vida experimentará transiciones de fase y zonas de extrema complejidad, pero uno debe pensar que tras el pico de dificultad, nos adentraremos de nuevo en la región fácilmente resoluble. Al menos, eso pienso yo.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Posted in Física, Matemáticas, Optimización Combinatoria, Singularidad | Etiquetado: , , , | 11 Comments »