Definición: una heurística es una técnica para abordar un problema que consiste en un método práctico que no garantiza ser óptimo o perfecto, pero es suficiente para alcanzar metas inmediatas.
Objetivo: encontrar una buena solución en un tiempo razonable. Generalmente, no hay garantía de que esta solución sea óptima, pero puede resultar útil para resolver el problema en cuestión.
Ventajas:
- Obtener buenas soluciones para problemas NP
- Rapidez respecto de los algoritmos
- Ideas e implementación relativamente sencillas
- Muy importantes en el campo de Inteligencia Artificial
- Optimizar funciones no necesariamente diferenciables
Desventajas:
- ¿Podemos asegurar que la solución encontrada es óptima?
- Si existen varias soluciones óptimas, ¿puede encontrarlas a todas?
- ¿Podemos asegurar que la solución encontrada está a cierta distancia de la solución óptima?
- ¿Es la heurística elegida la mejor para abordar este problema?
Muchas veces la respuesta a estas preguntas es "probablemente no".
Repaso de Complejidad¶
Supongamos que tenemos un problema de decisión: la respuesta es SI o NO. Por ejemplo:
Input: Un número natural $n$
Pregunta: ¿Es $n$ par?
P¶
Es la clase de problemas de decisión que pueden ser resueltos eficientemente, es decir, que pueden ser resueltos por algoritmos que tienen complejidad polinomial.
El ejemplo anterior es un ejemplo de problema P, pues el siguiente algoritmo (implementado como una función en Python) lo resuelve en tiempo polinomial $\mathcal{O}(n)$:
def esPar(n):
for i in range(n):
if 2*i == n:
return True
return False
Ejemplos de problemas de clase P:
- ¿Existe un matching máximo en este grafo?
- ¿Es primo este número entero?
NP¶
Es la clase de problemas de decisión para los cuales existe un algoritmo de complejidad polinomial que puede corroborar si una solución dada es correcta. En otras palabras, si me dan un input y me dicen que la respuesta es SI, entonces puedo corroborarlo con un algoritmo de complejidad polinomial en el tamaño del input.
SAT (Boolean satisfiability problem) es un ejemplo de problema NP:
Input: Una fórmula de lógica proposicional $F$
Pregunta: ¿Existe una asignación de valores lógicos a las variables para que $F$ sea verdadera?
Por ejemplo, si $F=x_1\wedge(x_2\vee x_3)$, la respuesta es SI, porque podemos tomar $x_1=TRUE,\;x_2=FALSE,\; x_3=TRUE$ (no es la única posibilidad). Por otro lado, si $F=x_1\wedge (\neg x_1)$, la respuesta es NO, porque nunca podemos atribuirle un valor lógico a $x_1$ para que $F$ sea verdadera.
Notar que existen $2^n$ posibilidades de asignación de valor lógico a las variables. Ver que un problema es NP, no tiene que ver con hallar una solución, sino con poder corroborar una solución eficientemente.
SAT es un problema NP porque corroborar si una asignación de valores lógicos hace que cierta fórmula $F$ sea verdadera se hace en tiempo polinomial. Por ejemplo, si $F=x_1\wedge(\neg x_2\vee x_3)\wedge (\neg(x_3\wedge x_1))$ y me dicen que la asignación $(TRUE,FALSE,FALSE)$ hace VERDADERA a $F$, para corroborarlo puedo reemplazar a las variables por sus correspondientes valores y evaluar la expresión (complejidad $\mathcal{O}(n)$). Por ejemplo, este algoritmo (implementado como una función en Python) corrobora la solución en tiempo polinomial:
def valorF(x_1, x_2, x_3):
a = x_1
b = (not x_2) and x_3
c = not(x_3 and x_1)
return (a and b) and c
Se puede demostrar que $P\subseteq NP$, es decir, que todo problema que puede ser eficientemente resuelto puede ser eficientemente corroborado.
Problema abierto: ¿$P = NP$? ¿$P\neq NP$?
NP-Completo¶
Reducción: dados $A, B\in NP$, decimos que $A$ se reduce polinomialmente a $B$ (se nota $A\propto B$) si hay un algoritmo polinomial que convierte toda instancia $I_1$ de $A$ en $I_2$ de $B$ de manera tal que $I_1$ es verdadera $\Leftrightarrow$ $I_2$ es verdadera.
En criollo: $A\propto B$ si de existir un algoritmo que resuelva $B$ eficientemente, podría usarse ese algoritmo como subrutina para resolver $A$ eficientemente.
Obs.: si $A\propto B$, entonces resolver $A$ puede ser a lo sumo tan difícil como resolver $B$.
Ejemplo¶
Problema $A$: ciclo hamiltoniano:
Input: $G(V,E)$
Pregunta: ¿Existe un ciclo hamiltoniano en G?
Problema $B$: decisión TSP:
Input: $G(V,E)$ grafo completo, donde $e\in E$ tiene un costo $c_e$
Pregunta: Dado $k\in\mathbb{R}$, ¿existe un ciclo hamiltoniano que acumule costo $\leq k$?
El siguiente algoritmo reduce $A$ a $B$:
$G=(V,E)$ grafo del input de $A$
Tomar $\bar{G}$ el grafo completo con los nodos de $V$: $\bar{G}=(V,\bar{E})$
Establecer costos: $c_e = \begin{cases} 0 \quad \text{si } e\in E \\ 1 \quad \text{c.c}\end{cases}$
Responder si existe un ciclo hamiltoniano de costo $\leq 0$
Definición: un problema de decisión $A$ es NP-Completo si:
- $A\in NP$
- $B\propto A \; \forall B\in NP$
Proposición: si $A\propto B$ y $A$ es NP-Completo $\Rightarrow$ $B$ es NP-Completo
Obs.: los problemas NP-Completos son los problemas NP más difíciles.
Proposición: SAT es NP-Completo.
NP-Hard¶
Son aquéllos problemas que satisfacen la segunda condición de NP-Completitud. $A$ es NP-Hard si:
- $B\propto A \; \forall B\in NP$
Lo que quiere decir esto, informalmente, es que $A$ es por lo menos tan difícil como el problema más difícil de NP.
Proposición: si $A\propto B$ y $A$ es NP-Hard $\Rightarrow$ $B$ es NP-Hard
Proposición: SAT es NP-Hard
Proposición: TSP es NP-Hard pero no NP, dado que no es un problema de decisión
Algunos problemas NP-Completos:
- Programación Lineal Entera (NP-Hard)
- 3-SAT
- Número cromático
- Camino máximo
- Knapsack
- Buscaminas
Más problemas NP-Completos: https://en.wikipedia.org/wiki/List_of_NP-complete_problems
Heurísticas¶
Muchos de los problemas que surgen naturalmente en el mundo real, en especial los problemas de optimización, son al menos NP-Completos. Esto quiere decir que son problemas para los cuales todavía no existe un algoritmo que los resuelva eficientemente.
Generalmente, se utilizan heurísticas para hallar buenas soluciones a esos problemas. Por buenas soluciones, entendemos que, si bien no podemos asegurar que sean óptimas, resultan beneficiosas al aplicarse a los problemas que desean resolverse.
Además, muchos de los métodos que vimos en la materia funcionan bien para hallar mínimos locales, pero, como hemos visto, por sí mismos no alcanzan para hallar buenas soluciones.
De aquí en más vamos a pensar en calidad de una solución $s$ en relación al objetivo de nuestro problema:
- Si queremos minimizar $f$: $calidad(s)\geq calidad(s') \Leftrightarrow f(s)\leq f(s')$
- Si queremos maximizar $f$: $calidad(s)\geq calidad(s') \Leftrightarrow f(s)\geq f(s')$
Paseo Aleatorio (Random Walk)¶
Consiste en recorrer el dominio de la función objetivo de manera aleatoria, guardando el punto con la mejor calidad hasta el momento. Hay varias maneras de implementar un paseo aleatorio, dependiendo de cómo uno recorre el espacio. Una de ellas es discretizar el espacio (por ejemplo, con una cuadrícula), y nos movemos de un punto a alguno de sus vecinos con cierta probabilidad. (También podemos definir qué consideramos como vecinos!!)
En el siguiente ejemplo, dado un punto inicial $(x,y)$ se considera como el vecindario de ese punto a $N_{(x,y)}=\{(x+h,y), (x-h,y), (x,y+h), (x,y-h)\}$ y cada uno tiene probabilidad de $\frac{1}{4}$ de ser elegido como próximo paso.
Otra manera es, en cada paso, avanzar en una dirección aleatoria extraída a partir de alguna distribución, por ejemplo $\mathcal{N}(0,\sigma^2)$ con un valor de $\sigma$ adecuado. Esto puede ahorrarnos tener que discretizar el espacio si estamos trabajando con problemas en variables continuas.
Así, por ejemplo, si el punto actual es $(x,y)$ el próximo punto será $(x+\alpha, y+\beta)$, dónde $\alpha$ y $\beta$ provienen de una distribución $\mathcal{N}(0,0.1^2)$
Volvamos a un ejemplo de clases pasadas, donde los algoritmos de descenso no otorgaban el resultado deseado si comenzaban en un punto inicial malo. La función a optimizar era $$f(x, y) = 2(e^{-x^2-y^2}- e^{-(x-1)^2 - (y-1)^2})$$
Paseo aleatorio discreto¶
Paseo aleatorio normal¶
En ambos casos, los paseos aleatorios permitieron hallar soluciones casi óptimas. Sin embargo, esto se debe completamente a la aleatoriedad. Es muy poco probable que puedan obtenerse el mismo camino o incluso el mismo resultado si se vuelve a correr el algoritmo.
Observar que en ningún momento requerimos alguna característica de $f$: ni derivabilidad ni continuidad. Por esta razón, el camino aleatorio es aplicable a casi cualquier función y es muy rápido en cuanto a tiempo de ejecución. Esto último es importante para dar lugar a métodos Monte Carlo, que requieren gran cantidad de simulaciones.
El criterio de parada puede ser un límite de iteraciones o un límite de tiempo. Naturalmente, la idea del camino aleatorio por sí sola aplicada a problemas de optimización puede resultar poco práctica, pero más adelante vamos a ver que sirve para mejorar otros métodos.
Idea general de paseo aleatorio¶
mejor_s $\leftarrow$ punto al azar
REPETIR
s $\leftarrow$ punto al azar cercano a s
si calidad(s)$\geq$ calidad(mejor_s):
mejor_s $\leftarrow$ s
DEVOLVER mejor_s
Búsqueda Local¶
Dado un punto inicial, consiste en encontrar un vecino que mejore el valor de la función objetivo. Como ocurría en el caso del Paseo Aleatorio Discreto, se requiere definir una noción de vecindario de un punto, y ese conjunto debe ser finito. Esto implica que, si estamos trabajando en un problema con variables continuas, tengamos que discretizar el espacio. Si se trata de un problema de optimización combinatoria, la noción de vecino suele ser intuitiva.
Idea general de búsqueda local¶
mejor_s $\leftarrow$ punto inicial
REPETIR mientras se cumpla un criterio
s $\leftarrow$ vecino de mejor_s
si se cumple el criterio de aceptación de s:
mejor_s $\leftarrow$ s
DEVOLVER mejor_s
El criterio de parada puede ser un límite de iteraciones o un límite de tiempo. Varias heurísticas se definen a partir de cómo se recorre el vecindario y del criterio de aceptación de un vecino.
Hill climbing¶
Es uno de los métodos mas básicos de búsqueda local: consiste en recorrer los vecinos de un punto hasta encontrar alguno que mejore el valor de la función objetivo. Se puede establecer un orden para recorrer el vecindario de un punto o se lo puede hacer de manera aleatoria. Recorrer los vecinos ordenadamente da lugar al Simple Hill Climbing, mientras que hacerlo de forma aleatoria da lugar al Stochastic Hill Climbing.
Es un algoritmo greedy: toma automáticamente el primer vecino que mejore la función objetivo, sin considerar movimientos futuros o al resto del vecindario que quedó sin recorrer.
Generalmente se habla de este método en el contexto de un problema de maximización (de ahí su nombre) pero es perfectamente aplicable a problemas de minimización.
Idea básica de Hill-Climbing
mejor_s $\leftarrow$ punto inicial
local $\leftarrow$ FALSE
N $\leftarrow$ vecindario de mejor_s
REPETIR hasta agotar iteraciones o local = TRUE
si N$\neq\emptyset$:
s $\leftarrow$ vecino de mejor_s
si calidad(s)$>$ calidad(mejor_s):
mejor_s $\leftarrow$ s
N $\leftarrow$ vecindario de mejor_s
aumentar iteracion
si no:
N $\leftarrow$ N - {s}
si no:
local$\leftarrow$ TRUE
DEVOLVER mejor_s
Si bien es muy sencillo de implementar, Hill-Climbing tiene varias desventajas:
- No tiene en cuenta movimientos futuros
- Se queda atascado en mesetas o, peor aún, en lomos
- El resultado depende del punto inicial
- Método de optimización local
Algunas soluciones:
- Pasos laterales: en el criterio de aceptación, reemplazamos $>$ por $\geq$. Esto permite recorrer mesetas y lomos. La contrapartida es que podemos caminar en círculos.
- Búsqueda tabú: se agrega un registro de los últimos $n$ puntos visitados y se prohíbe volver a visitarlos hasta que salgan de la lista, con el fin de evitar caminar en círculos. La contrapartida es que se consume más memoria y más tiempo de cómputo.
- Ascenso más rápido (steepest ascent): en vez de quedarnos con el primer vecino de mejor calidad que encontremos, analizamos la calidad de todos los vecinos y nos quedamos con el mejor. Es muy similar al método de descenso por gradiente. La contrapartida es mayor tiempo de cómputo y rápida convergencia a mínimo local.
- Random restart Hill Climbing: ejecutar Hill-Climbing sobre muchos puntos iniciales aleatorios.
Aplicación de Hill-Climbing al ejemplo anterior. Se utilizó la noción de vecindad del paseo aleatorio discreto con $h=0.1$ :
Recocido Simulado (Simulated annealing)¶
Es un método de optimización global y está motivado por la técnica del recocido del acero utilizada en la herrería: el acero es calentado a altas temperaturas para que sea maleable y su posterior enfriamiento es controlado para mejorar su fuerza y durabilidad.
En este método, si un vecino mejora el valor de la función objetivo, es aceptado siempre. Sin embargo, también existe la probabilidad de aceptar a un vecino que empeore el valor de la función objetivo. Generalmente, la probabilidad de aceptación para problemas de minimización se define como: $$p(s, s') = exp\left(\dfrac{f(s)-f(s')}{T}\right)$$ donde $T$ es la temperatura actual, $s$ es el punto actual y $s'$ un vecino con peor valor de la función objetivo. La idea es tomar un número $r$ un número al azar con distribución $\mathcal{U}[0,1]$ y aceptar a $s'$ si $r<p(s,s')$
Observar que si $T$ es grande, $p\approx 1$, entonces se parece a un paseo aleatorio, ya que hay alta probabilidad de permitir pasos que empeoren la función objetivo. En cambio, si $T\rightarrow 0$ , $p\approx 0$ y se asemeja a Hill-Climbing. La idea es comenzar con un $T$ grande e ir disminuyéndolo luego de un número de iteraciones. $T$ simboliza la temperatura en el proceso de recocido, por lo que no hay que hacerla bajar ni muy rápido, ni muy lento.
Idea básica de Recocido Simulado (minimización)
T $\leftarrow$ Temperatura inicial
s$\leftarrow$ Punto inicial
mejor_s$\leftarrow$ s
REPETIR hasta que T < T_min:
t $\leftarrow$ vecino de s
Disminuir T (por ejemplo, T = a*T con a<1)
si calidad(t) > calidad(s):
s $\leftarrow$ t
si calidad(s) $\leq$ calidad(mejor_s):
mejor_s $\leftarrow$ s
de lo contrario, si $exp\left(\dfrac{f(s)-f(t)}{T}\right)>rand()$ :
s $\leftarrow$ t
DEVOLVER mejor_s
Donde $rand()$ es un número generado al azar con distribución $\mathcal{U}[0,1]$. En Python esto se logra con la función np.random.rand().
La dificultad de este método es establecer cuál es la temperatura inicial y la tasa de enfriamiento (a). Generalmente, tomar a=0.8 da buenos resultados. Muchas veces, estos parámetros se fijan a partir de experimentaciones. De nuevo, si $a\approx 1$ el recorrido no es eficiente y si $a\approx 0$ el método se asemeja demasiado a Hill Climbing.
Por la naturaleza probabilística de Recocido Simulado, podemos iniciarlo muchas veces en el mismo punto y obtener resultados distintos.
En el ejemplo con el que veníamos trabajando, se aplicó Recocido Simulado con $T_0=25000$ y $a=0.95$ y se obtuvo el siguiente resultado:
Cosas a tener en cuenta¶
- Comenzar en un mal punto perjudica a muchos de los algoritmos y métodos que hemos visto (excepto a paseo aleatorio).
- La idea de correr estos métodos en muchos puntos iniciales (random restart) y comparar resultados es muy importante. Es una técnica que se utiliza mucho en problemas de optimización.
- Se pueden aprovechar técnicas de multiprocesamiento para acelerar el random restart, ¡disminuyendo el tiempo de cómputo!
- ¡Se pueden combinar técnicas! Por ejemplo, puedo realizar un paseo aleatorio y, sobre el mejor punto encontrado, iniciar Hill Climbing.
- Muchos de estos métodos están pensados para problemas de optimización combinatoria (i.e. sobre espacios discretos) pero se pueden aplicar a problemas en variables continuas. En estos casos, generalmente se debe discretizar el espacio de alguna manera para poder definir el vecindario de un punto.